The non-convergence of f(f(x))=exp(x)-1 and labeled rooted trees - MathOverflow

The non-convergence of f(f(x))=exp(x)-1 and labeled rooted trees

2010-11-03T22:11:42Z

This question is closely related to MO f(f(x))=exp(x)-1 and other functions “just in the middle” between linear and exponential. Consider $e^{e^x-1}$, this is the generating function of the Bell numbers. A more general way to look at Bell numbers is as rooted trees, hierarchies of height 2. Given $g(x)=e^x-1$, $g^n(x), n \in \mathbb{N}$ is the generating function of hierarchies of height n. See page 107 - 110 of Analytic Combinatorics. The ECS should have the integer sequences associated with hierarchies of different heights. Also see OEIS

    Integer sequence                      height OEIS
    {1,1/2,1/8,0,1/32,-7/128,1/128,159/256}  1/2 A052122
    {0,1,1,1,1,1,1,1,1}                        1
    {1,2,5,15,52,203,877,4140}                 2 A000110
    {1,3,12,60,358,2471,19302,167894}          3 A000258
    {1,4,22,154,1304,12915,146115,1855570}     4 A000307
    {1,-1,2,-6,24,-120,720,-5040}             -1 A000142
    {1,-2,7,-35,228,-1834,17582,-195866}      -2 A003713

Several solutions for $f(f(x))=e^x-1$ have been proposed on MO, but the work of I.N. Baker is cited as proving that $f(x)$ has no convergent solution, "even in an ϵ-ball around 0." I am currently trying to read the original German, to understand Baker's proof.

Question 1 Could someone summarize Baker's proof? It is frequently referred to and an explanation in English would be wonderful.

Question 2 Formal power series can contain useful information, even if the are divergent. It seems that divergent series are not treated with quite the contempt they used to be. I believe on the Tetration Forum that someone raised the possibility of $f(x)$ being Borel summable. What are the potential options for "rehabilitating" a series that is not nicely convergent.

Question 3 If $g(x)=e^x-1$, $g^n(x), n \in \mathbb{N}$ is the generating function of hierarchies of height n, doesn't $g(x)=e^x-1$, $g^n(x), n \in \mathbb{R}$ consists of labeled rooted trees of fractional height? So shouldn't $f(x)=g^\frac{1}{2}(x)$ be the generating function for labeled rooted trees of height $\frac{1}{2}$?
Doesn't the divergence of $f(x)=g^\frac{1}{2}(x)$ imply that a label rooted tree of height $\frac{1}{2}$ have infinitely many leaves, that the width of the tree is infinite. Can't be use the fact that we are working with a labeled rooted tree to constrain the width of the tree from becoming infinite?

Answer by Gottfried Helms for The non-convergence of f(f(x))=exp(x)-1 and labeled rooted trees

2010-11-04T07:50:53Z

1) Concerning Bell-numbers and generalizations: you might be interested in the treatize

http://go.helms-net.de/math/binomial_new/04_5_SummingBellStirling.pdf

where I deal with continuous interpolations based on E.T.Bell's original article and then using the matrix-approach for a comparision.

2) ad Question 2: the most intuitive problem for series to be summable by some summation is the rate of growth of the coefficients (but this is not the only relevant one). A very short example: if we are in a context of powerseries, then if the sequence of coefficients grows with a constant rate (the ratio $c_{k+1} / c_k$ is constant, in other words, it has "geometric growth") and the sign is alternating, then the series can be summed for instance by Euler-summation.

If the rate is hypergeometric (and signs are alternating), where the ratio $c_{k+1}/c_k$ is linearly increasing with the index, for instance $1!x - 2!x^2+3!x^3 -...+...$ Borel-Summation can assign a meaningful value. The growthrate of the powerseries for fractional iterates of $exp(x)-1$ seems to be even more than hypergeometric, so even Borel-summation may not be sufficient. I fiddled with Noerlund-summation adapted to such growthrate, but have only heuristics so far, no thorough analysis of the validity of the results.

The key reference should be G.H.Hardy, "Divergent series"; if I recall right you can look at parts of it using google-books to get some impression of that work.

I have some discussion of this matter on my homepage http://go.helms-net.de/math/tetdocs

Answer by Anixx for The non-convergence of f(f(x))=exp(x)-1 and labeled rooted trees

2010-11-05T10:35:26Z

Let $\sigma(x)=\exp(x)-1$ We know that e^{\sigma(x)-1} is a generating function for Bell numbers

$$\exp(\sigma^{[p]}(t))=\sum_{n=0}^{\infty}B_n^p\frac{t^n}{n!}$$

where $B_n^p$ are the Bell's numbers of p-th order.

So to find $\sigma^{[1/2]}(t)$ we have to generalize Bell's numbers to fractional order. We can do that by induction as follows:

$$A_0^x=1$$ $$A_{n+1}^x=\sum_{k=0}^{x-1} A_n^x\star A_n^k$$

And then $$B_n^x=A_{n-1}^{x+1}$$

where $f(n)\star g(n)$ is the binomial convolution as described by David Knuth:

$$f(n)\star g(n)=\sum_{k=0}^n \binom nkf(n-k)g(k)$$

To obtain the value for any real x, we can note that the right part in $A_{n+1}^x=\sum_{k=0}^{x-1} A_n^x\star A_n^k$ is a polynomial of x and k of degree n-1 and integer coefficients and we can take indefinite sum of it symbolically following the rule

$$\sum_x ax^n=\frac{B_{a+1}(x)}{a+1}$$

Where $B_a(x)$ are the Bernoulli polynomials.