Let's call a function f:N→N half-exponential if there exist constants 1<c<d such that for all sufficiently large n,
cn < f(f(n)) < dn.
Then my question is this: can we prove that no half-exponential function can be expressed by composition of the operations +, -, *, /, exp, and log, together with arbitrary real constants?
There have been at least two previous MO threads about the fascinating topic of half-exponential functions: see here and here. See also the comments on an old blog post 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 monotone compositions of the operations +, *, exp, and log.)
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))=ex, or f(f(x))=ex-1, then f can't even be analytic, let alone having a closed form in terms of basic arithmetic operations, exponentials, and logs.
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 already enough to rule out a closed form for f?
Best Answer
Yes
All such compositions are transseries in the sense here:
G. A. Edgar, "Transseries for Beginners". Real Analysis Exchange 35 (2010) 253-310
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:
J. van der Hoeven, Transseries and Real Differential Algebra (LNM 1888) (Springer 2006)
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.
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).