"Closed-form" functions with half-exponential growth - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T08:22:24Z http://mathoverflow.net/feeds/question/45477 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/45477/closed-form-functions-with-half-exponential-growth "Closed-form" functions with half-exponential growth Scott Aaronson 2010-11-09T18:51:19Z 2011-05-02T16:51:26Z <p>Let's call a function f:N&rarr;N <i>half-exponential</i> if there exist constants 1&lt;c&lt;d such that for all sufficiently large n,</p> <p>c<sup>n</sup> &lt; f(f(n)) &lt; d<sup>n</sup>.</p> <p>Then my question is this: <i>can we prove that no half-exponential function can be expressed by composition of the operations +, -, *, /, exp, and log, together with arbitrary real constants?</i></p> <p>There have been at least two previous MO threads about the fascinating topic of half-exponential functions: see <a href="http://mathoverflow.net/questions/12081/does-the-exponential-function-have-a-square-root" rel="nofollow">here</a> and <a href="http://mathoverflow.net/questions/4347/ffxexpx-1-and-other-functions-just-in-the-middle-between-linear-and-expo" rel="nofollow">here</a>. See also the comments on an <a href="http://www.scottaaronson.com/blog/?p=263" rel="nofollow">old blog post</a> of mine. However, unless I'm mistaken, none of these threads answer the question above. (The best I was able to prove was that no half-exponential function can be expressed by <i>monotone</i> compositions of the operations +, *, exp, and log.)</p> <p>To clarify what I'm asking for: the answers to the previous MO questions already sketched arguments that if we want (for example) f(f(x))=e<sup>x</sup>, or f(f(x))=e<sup>x</sup>-1, then f can't even be <i>analytic</i>, let alone having a closed form in terms of basic arithmetic operations, exponentials, and logs.</p> <p>By contrast, I don't care about the precise form of f(f(x)): all that matters for me is that f(f(x)) has an asymptotically exponential growth rate. I want to know: is that hypothesis <i>already</i> enough to rule out a closed form for f?</p> http://mathoverflow.net/questions/45477/closed-form-functions-with-half-exponential-growth/45479#45479 Answer by Gerald Edgar for "Closed-form" functions with half-exponential growth Gerald Edgar 2010-11-09T19:30:29Z 2010-11-09T19:39:07Z <p>Yes</p> <p>All such compositions are transseries in the sense here:<br> G. A. Edgar, "Transseries for Beginners". <em>Real Analysis Exchange</em> <strong>35</strong> (2010) 253-310</p> <p>No transseries (of that type) has this intermediate growth rate. There is an integer "exponentiality" associated with each (large, positive) transseries; for example Exercise 4.10 in:<br> J. van der Hoeven, <em>Transseries and Real Differential Algebra</em> (LNM 1888) (Springer 2006)<br> A function between $c^x$ and $d^x$ has exponentiality $1$, and the exponentiality of a composition $f(f(x))$ is twice the exponentiality of $f$ itself. </p> <p>Actually, for this question you could just talk about the Hardy space of functions. These functions also have an integer exponentiality (more commonly called "level" I guess).</p> http://mathoverflow.net/questions/45477/closed-form-functions-with-half-exponential-growth/48596#48596 Answer by John Sidles for "Closed-form" functions with half-exponential growth John Sidles 2010-12-07T22:36:11Z 2011-05-02T16:51:26Z <p>On <a href="http://rjlipton.wordpress.com/2011/04/28/succinct-constant-depth-arithmetic-circuits-are-weak/#comment-11771" rel="nofollow">Dick Lipton's weblog</a>, I posted a brief essay on demi-exponential functions, which I repeat here:</p> <hr> <p>To expand upon Ken's remarks regarding demi-exponential functions (which is a fine name for them!), the analytic structure of these functions derives from the Lambert $W$ function, which is the subject of a classic article <i><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.9305&amp;rep=rep1&amp;type=pdf" rel="nofollow">On the Lambert W Function</a></i> (1996) by Corless, Gonnet, Hare, Jeffrey, and Knuth (yes, one somehow knew that Donald Knuth's name would arise in connection to such an interesting function ... to date this article has received more than 1600 references).</p> <p>The connection arises via the following construction. Suppose that a demi-exponential function $d$ satisfies $d \circ d \circ \dots \circ d \circ z = \gamma \beta^z$, where $d$ is composed $k$ times. We say that $k$ is the <em>order</em> of the demi-function, $\gamma$ is the <em>gain</em> and $\beta$ is the <em>base</em>. It is easy to show that the fixed points of $d$ are given explicitly in terms of the $n$-th branch of the Lambert function as $z_f = -W_n(-\gamma \ln \beta)/\ln \beta$. Then by a series expansion about these fixed points (optionally augmented by a Pade resummation) it is straightforward to construct the demi-exponential functions both formally and numerically. </p> <p>Provided the demi-exponential base and gain satisfy $\gamma \le 1/(e \ln \beta)$, such that the fixed points associated to the $n=-1$ branch of the $W$-function are real and positive, this construction yields smooth demi-exponential functions that pleasingly accord with our intuition of what demi-exponential functions should'' look like. </p> <p>Counter-intuitively though, whenever the specified gain and base are sufficiently large that $\gamma > 1/(e \ln \beta)$, then the demi-exponential function has no real-valued fixed points, but rather develops jump-type singularities. In particular, the seemingly reasonable parameters $\beta=e$ and $\gamma=1$ have no smooth demi-exponential function associated to them (at least, that's the numerical evidence). </p> <p>Perhaps this is one reason that demi-exponential functions have a reputation for being difficult to construct ... it is indeed very difficult to construct smooth functions for ranges of parameters such that no function has the desired smoothness! </p> <p>It might be feasible (AFAICT) to write an article <i>On demi-exponential functions associated to the Lambert W Function</i>, and to include these functions in standard numerical packages (SciPy, MATLAB, Mathematica, etc.). </p> <p>Some tough challenges would have to be met, however. Especially, there is at present no known integral representation of the demi-exponential functions (known to me, anyway), and yet such a representation would be very useful (perhaps even essential) in rigorously proving the analytical structures that the numerical Pade approximants show us so clearly.</p> <p><i>Mathematica</i> script <a href="http://faculty.washington.edu/sidles/Litotica_reading/Litotica_half_exp.pdf" rel="nofollow">here (PDF)</a>.</p> <hr> <p>Here's what these functions look like:</p> <p><img src="http://faculty.washington.edu/sidles/Litotica_reading/halfexp.png" alt="halfexpPicture"> </p> <hr> <p><b>Final note:</b> Inspired by the recent burst of interest in these demi-exponential functions, and mainly for my own recreational enjoyment, I have verified (numerically) that demi-exponential functions $d$ having (1) fixed point $z_f = d(z_f) = 1$, and (2) any desired <i>asymptotic</i> order, gain, and base can readily be constructed. </p> <p>I'd be happy to post details of this construction ... but it's not clear that anyone has any practical interest in computing numerical values of demi-exponential functions.</p> <p>What folks mainly wanted to know was: (1) Do smooth demi-exponential functions exist? (answer: yes), (2) Can demi-exponential functions be computed to any desired accuracy? (answer: yes), and (3) Do demi-exponential functions have a tractable closed form, either exact or asymptotic? (answer: no such closed-form expressions are known).</p>