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$ 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
    Dec 8, 2020 at 14:30
  • $\begingroup$ I opened this chat to comment / discuss further $\endgroup$
    – G Cab
    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
    Dec 8, 2020 at 14:22
  • $\begingroup$ I added the proof that the difference is decreasing $\endgroup$
    – G Cab
    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$ 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
    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
    Jan 9, 2021 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.