# 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

This is an attempt to summarize some work related to question 2 which I do not fully understand myself. I am summarizing Sections 1.1 and 1.2 of Dudko's thesis, whose exposition is excellent (including work of earlier authors which he describes).

Set $F(z) = e^z-1$, so $F(z) = z+z^2/2+z^3/6+O(z^4)$. This discussion will apply to functional square roots of any $F(z)$ of the form $z+c z^2+O(z^3)$ for $c \neq 0$. Set $f(w) = 1/F(1/w)$, so $f(w) = w - 1/2 + w/12 + O(w^2)$. We will attempt to find a composition square root $f^{\langle 1/2 \rangle}(w)$ for $w$, the change of coordinates $w \mapsto 1/z$ will then change it into a compositional square root for $F$.

Suppose that we had an invertible holomorphic function $\alpha$ obeying $$\alpha(f(w)) = \alpha(w)-1/2. \quad (\ast)$$ For now, I'll be sloppy about on what region $\alpha$ is defined; this will eventually be a crucial issue. Such an $\alpha$ is called a Fatou coordinate.

Then we could define fractional compositions $f^{\langle s \rangle}$ by $f^{\langle s \rangle}(w) = \alpha^{-1}(\alpha(w)-s/2)$ and we would clearly have $f^{\langle s \rangle} \circ f^{\langle t \rangle} = f^{\langle s+t \rangle}$ and $f^{\langle 1 \rangle}=f$.

There is a unique formal power series solution $$\alpha(w) = w+\frac{1}{6} \log w + \sum_{n \geq 1} c_n w^{-n}$$ to $(\ast)$.

Dudko shows (Theorem 37) that, for any $\delta>0$ there is an $R>0$ such that the sum $\sum c_n z^{-n}$ is Borel summable on a region of the form $U_+ = \{ r e^{i \theta}: r > R, \theta \in (-\pi+\delta, \pi - \delta) \}$ and is separately Borel summable on a region of the form $U_- = \{ r e^{i \theta}: r > R, \theta \in (\delta, 2 \pi - \delta) \}$. Here the integral defining the first Borel sum is along the positive real axis, and the integral for the second is on the negative real axis. However, the two Borel summations have different values! I'm not sure how to translate that Borel summability into the Borel summability you are looking for, but it seems in the same neighborhood.

-

A late rereading of the question, related to question 2 ...

Here I provide example-data for the Nörlund-summation of $g^{0.5}(1)$ - a function whose power series has convergence radius zero.

I document the index of the coefficients, the coefficients of the formal power series, the running partial sums (obviously diverging), the running partial sums when handled by Nörlund-summation up to 128 terms.
The latter (Nörlund-summation) gives the approximation to 16 digits
$$\small g^{0.5}(1) \approx 1.271027413889951$$ then giving with the same power series
$$\small g^{0.5}(g^{0.5}(1)) \approx 1.718281828459040 \approx g^1(1)=\exp(1)-1$$
(for my reference: Noer(1.3,1.2) and Noer(1.34,1.2))

 index              coefficients         partial sums      partial Nörlund sums
0                           0                      0                   0
1           1.000000000000000      1.000000000000000  0.4545454545454545
2          0.2500000000000000      1.250000000000000  0.7341208525402143
3         0.02083333333333333      1.270833333333333  0.9122301942629915
4            1.063167461E-204      1.270833333333333   1.028380048523427
5       0.0002604166666666667      1.271093750000000   1.105395948273426
6     -0.00007595486111111111      1.271017795138889   1.157107826068413
7     0.000001550099206349206      1.271019345238095   1.192174488130708
8      0.00001540411086309524      1.271034749348958   1.216146699756881
9    -0.000009074539103835979      1.271025674809854   1.232646365045238
10  -0.00000008281997061700838      1.271025591989884   1.244069536947741
11     0.000003607407276764577      1.271029199397161   1.252018906051541
12    -0.000001695149726331486      1.271027504247434   1.257576297540362
13    -0.000001330899163478246      1.271026173348271   1.261477587525010
14     0.000001775214449095200      1.271027948562720   1.264226661243389
15    0.0000003703539766582192      1.271028318916697   1.266170561643206
16    -0.000001914756847756720      1.271026404159849   1.267549548079902
17    0.0000003446734340420570      1.271026748833283   1.268530729059900
18     0.000002419134116158984      1.271029167967399   1.269230827010272
19    -0.000001477058740408431      1.271027690908659   1.269731687404952
20    -0.000003604626020230427      1.271024086282638   1.270090905997125
21     0.000004260305997230663      1.271028346588636   1.270349148757409
22     0.000006194017818376879      1.271034540606454   1.270535217577928
23     -0.00001262529253358556      1.271021915313920   1.270669571083534
24     -0.00001173608871098117      1.271010179225209   1.270766781424156
25      0.00004139522857744976      1.271051574453787   1.270837254916568
26      0.00002220303021195429      1.271073777483999   1.270888441247675
27      -0.0001531085667691717      1.270920668917230   1.270925685984437
28     -0.00002783278714724943      1.270892836130082   1.270952833420203
29       0.0006410186618993425      1.271533854791982   1.270972654084612
30      -0.0001113075163193871      1.271422547275662   1.270987148728057
31       -0.003030266662738394      1.268392280612924   1.270997765023375
32        0.001676669629987329      1.270068950242911   1.271005552420707
33         0.01609511545446779      1.286164065697379   1.271011273062360
34        -0.01570841597837842      1.270455649719001   1.271015481401015
35        -0.09548046450386031      1.174975185215140   1.271018581472949
36          0.1394896068274663      1.314464792042607   1.271020868180893
37          0.6285206494008848      1.942985441443492   1.271022557108857
38          -1.276941658102089     0.6660437833414022   1.271023806094929
39          -4.559563990209507     -3.893520206868104   1.271024730868634
40           12.40277245639567      8.509252249527565   1.271025416405595
41           36.18545468158323      44.69470693111080   1.271025925186280
42          -129.3055947197559     -84.61088778864508   1.271026303212701
43          -311.6084412226098     -396.2193290112549   1.271026584398604
44           1453.716433759844      1057.497104748589   1.271026793777736
45           2883.754997334037      3941.252102082626   1.271026949851834
46          -17648.60560271502     -13707.35350063240   1.271027066311483
47          -28323.26661214272     -42030.62011277512   1.271027153299087
48           231312.8420701555      189282.2219573803   1.271027218337061
49           289837.7069253053      479119.9288826857   1.271027267010861
50          -3269335.965621651     -2790216.036738965   1.271027303472263
51          -2992168.607240367     -5782384.643979333   1.271027330810652
52           49750634.15865189      43968249.51467256   1.271027351327275
53           28980063.03304947      72948312.54772203   1.271027366738048
54          -813616473.7718550     -740668161.2241330   1.271027378323717
55          -201961594.9493848     -942629756.1735177   1.271027387041152
56           14271686431.89481      13329056675.72129   1.271027393605935
57          -1325490857.724441      12003565817.99685   1.271027398553703
58          -267978508282.5182     -255974942464.5213   1.271027402285766
59           119319788075.7697     -136655154388.7516   1.271027405103068
60           5375636695985.663      5238981541596.912   1.271027407231483
61          -4370130464683.851      868851076913.0608   1.271027408840690
62          -114977800862292.5     -114108949785379.5   1.271027410058262
63           137951986893846.1      23843037108466.65   1.271027410980194
64           2617098057614844.      2640941094723311.   1.271027411678780
65          -4212853788526752.     -1571912693803442.   1.271027412208507
66       -6.327578887427343E16  -6.484770156807687E16   1.271027412610473
67        1.295151921379894E17   6.466749056991250E16   1.271027412915705
68        1.622105836430362E18   1.686773327000275E18   1.271027413147640
69       -4.080511635797134E18  -2.393738308796859E18   1.271027413323998
70       -4.401285994345274E19  -4.640659825224960E19   1.271027413458185
71        1.329598675921515E20   8.655326933990194E19   1.271027413560352
72        1.261810711284499E21   1.348363980624401E21   1.271027413638190
73       -4.502994272734458E21  -3.154630292110057E21   1.271027413697530
74       -3.815898137477292E22  -4.131361166688298E22   1.271027413742796
75        1.589510357283413E23   1.176374240614583E23   1.271027413777347
76        1.215279478983343E24   1.332916903044801E24   1.271027413803736
77       -5.856838083870504E24  -4.523921180825703E24   1.271027413823903
78       -4.069420268487934E25  -4.521812386570504E25   1.271027413839324
79        2.254363727114728E26   1.802182488457678E26   1.271027413851123
80        1.430449732486330E27   1.610667981332097E27   1.271027413860156
81       -9.066878257880019E27  -7.456210276547921E27   1.271027413867075
82       -5.269916435175674E28  -6.015537462830467E28   1.271027413872378
83        3.810128260159724E29   3.208574513876677E29   1.271027413876445
84        2.031546413213409E30   2.352403864601077E30   1.271027413879565
85       -1.672451699340111E31  -1.437211312880003E31   1.271027413881960
86       -8.181381032687473E31  -9.618592345567476E31   1.271027413883800
87        7.665194160108786E32   6.703334925552038E32   1.271027413885214
88        3.436056128874324E33   4.106389621429528E33   1.271027413886301
89       -3.666325917508468E34  -3.255686955365515E34   1.271027413887137
90       -1.502242471921400E35  -1.827811167457951E35   1.271027413887781
91        1.829081759464824E36   1.646300642719028E36   1.271027413888276
92        6.823558558710339E36   8.469859201429367E36   1.271027413888658
93       -9.511909998580164E37  -8.664924078437227E37   1.271027413888952
94       -3.213048706394277E38  -4.079541114237999E38   1.271027413889179
95        5.153030222975494E39   4.745076111551694E39   1.271027413889355
96        1.564420559054480E40   2.038928170209649E40   1.271027413889490
97       -2.906296636306224E41  -2.702403819285259E41   1.271027413889594
98       -7.852110799212833E41  -1.055451461849809E42   1.271027413889675
99        1.705371721461914E43   1.599826575276933E43   1.271027413889737
100        4.046956642541135E43   5.646783217818069E43   1.271027413889786
101       -1.040446475669077E45  -9.839786434908963E44   1.271027413889823
102       -2.130674826639912E45  -3.114653470130808E45   1.271027413889852
103        6.595741465439851E46   6.284276118426770E46   1.271027413889874
104        1.137365713197478E47   1.765793325040155E47   1.271027413889891
105       -4.341857322962722E48  -4.165277990458707E48   1.271027413889905
106       -6.083877870045516E48  -1.024915586050422E49   1.271027413889915
107        2.966091259417512E50   2.863599700812469E50   1.271027413889923
108        3.194458155882020E50   6.058057856694489E50   1.271027413889930
109       -2.101475311494295E52  -2.040894732927350E52   1.271027413889934
110       -1.577243236979305E52  -3.618137969906655E52   1.271027413889938
111        1.543241565024140E54   1.507060185325073E54   1.271027413889941
112        6.493669502776779E53   2.156427135602751E54   1.271027413889943
113       -1.173972421356822E56  -1.152408150000794E56   1.271027413889945
114       -1.018000648229130E55  -1.254208214823707E56   1.271027413889947
115        9.245841501996471E57   9.120420680514100E57   1.271027413889948
116       -2.335480802976352E57   6.784939877537748E57   1.271027413889949
117       -7.534518737073237E59  -7.466669338297859E59   1.271027413889949
118        4.506009101510347E59  -2.960660236787512E59   1.271027413889950
119        6.349606802091966E61   6.320000199724091E61   1.271027413889950
120       -6.035304045288526E61   2.846961544355646E60   1.271027413889950
121       -5.530798404541739E63  -5.527951442997383E63   1.271027413889951
122        7.249751716274017E63   1.721800273276634E63   1.271027413889951
123        4.976816000600169E65   4.994034003332935E65   1.271027413889951
124       -8.359915867436089E65  -3.365881864103154E65   1.271027413889951
125       -4.623988107014070E67  -4.657646925655102E67   1.271027413889951
126        9.517379026260588E67   4.859732100605486E67   1.271027413889951
127        4.433709238493628E69   4.482306559499682E69   1.271027413889951


Some change of Nörlund-parameters seem to indicate that indeed that parameters allow to limit the partial Nörlund sums to that approximate finite value (Noer(1.4,1.2) allow to arrive at 1.2710274138899515214 with 256 terms).

-

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