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

Question

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 1

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 2

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).

Answer 3

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.

Answer 4

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 Donald 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.