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

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?

-
Yes, indeed, One of the solutions I already posted converges well for negative x. –  Anixx Nov 3 '10 at 23:24
I believe the omitted sequence is A057427. –  Charles Nov 4 '10 at 0:53

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

-
Thanks Gottfried. Yes, in your treatise on Bell-Numbers the $n^{th}$ ξ matrix column is the same as the integer sequence for the hierarchy of height $n$. –  Daniel Geisler Nov 4 '10 at 8:30

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.

-
Anixx, please note reread questions being asked. Several solutions that agree have already been given for $f(x)$ where $f(f(x))=e^x-1$. The question regards the non-convergence of the solution. –  Daniel Geisler Nov 5 '10 at 11:24
What is "non-convergence of a solution"? There may exist non-convergence of a series, then another series may be suggested which converges to the same value. If the Taylor series for the solution does not converge, then another series can be proposed, like in this case. –  Anixx Nov 5 '10 at 11:29
Anixx, instead of posting the same answer verbatim to different questions, can you give a actual example of your technique being used to generate the Taylor series of $f(x)$ where the Taylor series is convergent. –  Daniel Geisler Nov 6 '10 at 0:12
It seems that Mathematica sometimes evaluates the indefinite sums not symbolically, but numerically and even rounding the limits to the integers. I still have to learn in which cases it uses which approach and how to make it evaluate the sums always symbolically. –  Anixx Nov 6 '10 at 0:39
Anixx, I have similar problems with Mathematica evaluating sums on its own. The HoldForm[] function may help. –  Daniel Geisler Nov 6 '10 at 0:43