11
$\begingroup$

Time ago, dealing with a generalization of the Stirling numbers, I stumbled on the following implicit recurrence $$ \mu (n):\;\;\prod\limits_{k = 0}^{n - 1} {\left( {\mu (n) - \mu (k)} \right)} = 1\quad \left| \matrix{ \,0 \le n \in Z \hfill \cr \,0 \le \mu (n) \in R \hfill \cr \,\mu (0) = 0 \hfill \cr} \right. $$

Using a good CAS it is not difficult to compute the first few values and plot them

Uniprod_1

Clearly, the sequence is monotonically increasing, and its finite difference is monotonically decreasing (1).

Such a regular behaviour leads me to expect that it might be extended over the reals and that $\mu (x)$ might be expressible through a combination of conventional functions.

From time to time I am returning to this challenge with some inspiration for a new approach, but the combination difference & product has frustrated all my attempts.
I couldn't even succeed to establish its asymptotic behaviour (now, thanks to @AMarino answer I know it's logarithmic) .

So I am asking for hints, suggestions.

-- addendum --

Putting $\rho _{\,n,\,m} = \mu _{\,n + 1} - \mu _{\,m} $ , an alternative way to express the problem is $$ \left\{ \matrix{ \prod\limits_{0\,\, \le \,k\, \le \,n} {\rho _{\,n,\,k} } = 1 \hfill \cr \rho _{\,n,\,k} - \rho _{\,n - 1,\,k} = \mu _{\,n + 1} - \mu _{\,n} \hfill \cr} \right. $$ which means to find a family of functions whose product wrt $k$ is $1$ and whose difference wrt $n$ is constant, as shown

Uniproduct_2

My last tentative has been to take two discrete pmf's on the support $[0,n]$ and put $$ \rho \left( {n,m} \right) = e^{\,h(n)\left( {p(m\,|n) - q(m\,|n)} \right)} $$ which by definition gives the unitary product, but cannot go yet through keeping the difference constant.

-- note 1 --

That the difference is monotonically decreasing comes from being $$ \eqalign{ & \prod\limits_{k = 0}^{n - 1} {\left( {\mu (n) - \mu (k)} \right)} = \prod\limits_{k = 0}^{n - 1} {\left( {\mu (n) - \mu (n - 1) + \mu (n - 1) - \mu (k)} \right)} = \cr & = \prod\limits_{k = 0}^{n - 1} {\left( {x + \left( {\mu (n - 1) - \mu (k)} \right)} \right)} = p_n (x)\quad \Rightarrow \cr & \Rightarrow \quad \left\{ \matrix{ p_n (0) = 0 \hfill \cr p_n (x) < p_{n + 1} (x)\quad \left| {\,0 < x} \right. \hfill \cr 1 = p_n (\mu (n) - \mu (n - 1)) < p_{n + 1} (\mu (n + 1) - \mu (n)) \hfill \cr} \right.\quad \Rightarrow \cr & \Rightarrow \quad \mu (n + 1) - \mu (n) < \mu (n) - \mu (n - 1) \cr} $$ which tells the interesting fact that $\Delta \mu (n-1)$ comes as the root of $p_n(x)=1$, which in turn is added to its zeros, shifting them to the left as to start from $0$ and making them the zeros of $p_{n+1}(x)$.

$\endgroup$
3
  • 1
    $\begingroup$ What makes this function "eely"? $\endgroup$ Commented Dec 8, 2020 at 14:17
  • 2
    $\begingroup$ @AlexKruckman: I called it so because many times I was thinking to hold it in my grasp, but ..remained with empty hands! $\endgroup$
    – G Cab
    Commented Dec 8, 2020 at 14:30
  • $\begingroup$ I opened this chat to comment / discuss further $\endgroup$
    – G Cab
    Commented Jan 9, 2021 at 17:30

1 Answer 1

5
+50
$\begingroup$

This is only a partial answer.

If your claim is correct, i.e. differences are decreasing, then the sequence is sublogarithmic. Indeed, let $s(n) := \mu(n+1) -\mu(n) $. The recurrence relation, using the claim $s(j) > s(n)$ for $j<n$, rewrites as

$$ 1 = \prod_{k=0}^n (\sum_{j=k}^n s(j) ) > \prod_{k=0}^n (n-k+1) s(n) = (n+1)! s(n) ^{n+1} $$

Which implies that

$$ s(n) < \left ( \frac{1}{(n+1)! } \right ) ^{1/(n+1) }$$

The Stirling approximation can be written as $m! \approx (m/e) ^{m}$. Substituting we get that $s(n) < \frac{e}{n+1}$ . Thus we have

$$ \mu(n) = s(n-1) +\ldots+s(0) < $$ $$ e \sum_{k=0}^{n-1} \frac{1}{k+1} \approx e \log(n) $$

We also have a sort of converse to this. Suppose that for all n we have $$(*) \ \ s(n) > \left ( \frac{1}{(n+2)! } \right ) ^{1/(n+2) }$$

That is, the sequence is also superlogarithmic. We want to show that differences are decreasing. Suppose that at some point $n$ we have for the first time that the difference increase, aka $s(n) \ge s(n-1) $. Then we get

$$ 1 = \prod_{k=0}^n (\sum_{j=k}^n s(j) ) \ge \prod_{k=0}^n (n-k+1) s(n-1) = (n+1)! s(n-1) ^{n+1} $$

From which we get, using again Stirling approximation, the opposite (*) inequality, yielding a contradiction.

This argument can be made precise with inequalities instead of plain Stirling approximation, but since it is not a strong result with respect to your requests, I think it's not worth. Hope it can inspire someone else for a more sophisticated approach :)

Edit. I have an approach for the lower bound. By substituting each factor with the biggest $s$ appearing we get a reversed inequality

$$ 1\le n s(0) \cdot (n-1)s(1) \ldots 1 \cdot s(n-1) $$

Rearranging terms and taking the logarithms we get

$$ 0 \le \log ns(n-1) + \ldots +\log 1\cdot s(0) $$

Let us define $$\sigma(n) := \frac{1}{n} \sum_{j=0} ^{n-1} \log (j+1) s(j) $$ Equation above ensures that $\limsup \sigma(n) \ge 0$. Now the plot twist: by Stolz Cesaro the limsup of the general term is greater or equal than the average one, so that

$$ \limsup \log s(n) (n+1) \ge \limsup \sigma(n) \ge 0$$

Which implies that

$$ \limsup s(n) (n+1) \ge 1$$

Which provides a lower bound like estimate. If this can be refined to be a limit, than by summing over n we would get that $\mu(n) \ge \log(n) $ asymptilotically.

$\endgroup$
15
  • 2
    $\begingroup$ very interesting, thanks. Now there is an approach to bound the asymptotic $\endgroup$
    – G Cab
    Commented Dec 8, 2020 at 14:22
  • $\begingroup$ I added the proof that the difference is decreasing $\endgroup$
    – G Cab
    Commented Dec 8, 2020 at 14:33
  • $\begingroup$ That's very cool! Joint forces make the difference :D good team job man! I'm also convinced that the sequence is superlogarithmic but I can't show this.. I think a similar approach could work: we have to show a reverse bound like $s(n) > s(n-1) c_n$ to apply an argument similar to mine and obtain the other side of the inequality. $\endgroup$ Commented Dec 8, 2020 at 17:17
  • $\begingroup$ I saw now (didn't get notice on inbox) that you could find the lower bound as well: good job, thanks. I would ask, if you are interested, further help in fixing some other interesting properties $\endgroup$
    – G Cab
    Commented Dec 14, 2020 at 17:31
  • 1
    $\begingroup$ I went a bit deeper onto your suggestion for $\ni (n)$ but could not catch it. $\endgroup$
    – G Cab
    Commented Jan 9, 2021 at 17:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .