The non-convergence of f(f(x))=exp(x)-1 and labeled rooted trees - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T18:19:28Z http://mathoverflow.net/feeds/question/44740 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/44740/the-non-convergence-of-ffxexpx-1-and-labeled-rooted-trees The non-convergence of f(f(x))=exp(x)-1 and labeled rooted trees Daniel Geisler 2010-11-03T22:11:42Z 2010-11-05T17:55:11Z <p>This question is closely related to MO <a href="http://mathoverflow.net/questions/4347/ffxexpx-1-and-other-functions-just-in-the-middle-between-linear-and-expo" rel="nofollow">f(f(x))=exp(x)-1 and other functions “just in the middle” between linear and exponential.</a> 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 <a href="http://algo.inria.fr/flajolet/Publications/books.html" rel="nofollow">Analytic Combinatorics</a>. The ECS should have the integer sequences associated with hierarchies of different heights. Also see OEIS </p> <pre> 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 </pre> <p>Several solutions for $f(f(x))=e^x-1$ have been proposed on MO, but the work of <a href="http://www.ams.org/mathscinet-getitem?mr=97532" rel="nofollow">I.N. Baker</a> 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.</p> <p><strong>Question 1</strong> Could someone summarize Baker's proof? It is frequently referred to and an explanation in English would be wonderful. </p> <p><strong>Question 2</strong> 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.</p> <p><strong>Question 3</strong> 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}$?<br> 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?</p> http://mathoverflow.net/questions/44740/the-non-convergence-of-ffxexpx-1-and-labeled-rooted-trees/44787#44787 Answer by Gottfried Helms for The non-convergence of f(f(x))=exp(x)-1 and labeled rooted trees Gottfried Helms 2010-11-04T07:50:53Z 2010-11-04T07:50:53Z <p>1) Concerning Bell-numbers and generalizations: you might be interested in the treatize</p> <p><a href="http://go.helms-net.de/math/binomial_new/04_5_SummingBellStirling.pdf" rel="nofollow">http://go.helms-net.de/math/binomial_new/04_5_SummingBellStirling.pdf</a></p> <p>where I deal with continuous interpolations based on E.T.Bell's original article and then using the matrix-approach for a comparision.</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>I have some discussion of this matter on my homepage <a href="http://go.helms-net.de/math/tetdocs" rel="nofollow">http://go.helms-net.de/math/tetdocs</a> </p> http://mathoverflow.net/questions/44740/the-non-convergence-of-ffxexpx-1-and-labeled-rooted-trees/44937#44937 Answer by Anixx for The non-convergence of f(f(x))=exp(x)-1 and labeled rooted trees Anixx 2010-11-05T10:35:26Z 2010-11-05T10:35:26Z <p>Let $\sigma(x)=\exp(x)-1$ We know that e^{\sigma(x)-1} is a generating function for Bell numbers</p> <p>$$\exp(\sigma^{[p]}(t))=\sum_{n=0}^{\infty}B_n^p\frac{t^n}{n!}$$</p> <p>where $B_n^p$ are the Bell's numbers of p-th order.</p> <p>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:</p> <p>$$A_0^x=1$$ $$A_{n+1}^x=\sum_{k=0}^{x-1} A_n^x\star A_n^k$$</p> <p>And then $$B_n^x=A_{n-1}^{x+1}$$</p> <p>where $f(n)\star g(n)$ is the binomial convolution as described by David Knuth:</p> <p>$$f(n)\star g(n)=\sum_{k=0}^n \binom nkf(n-k)g(k)$$</p> <p>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 </p> <p>$$\sum_x ax^n=\frac{B_{a+1}(x)}{a+1}$$</p> <p>Where $B_a(x)$ are the Bernoulli polynomials.</p>