"Closed-form" functions with half-exponential growth

Question

Let's call a function f:N→N half-exponential if there exist constants 1<c<d such that for all sufficiently large n,

cⁿ < f(f(n)) < dⁿ.

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))=e^x, or f(f(x))=e^x-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?

Answer 1

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

Answer 2

On Dick Lipton's weblog, I posted a brief essay on demi-exponential functions, which I repeat here:

---

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 On the Lambert W Function (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).

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 order of the demi-function, $\gamma$ is the gain and $\beta$ is the base. 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.

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.

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

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!

It might be feasible (AFAICT) to write an article On demi-exponential functions associated to the Lambert W Function, and to include these functions in standard numerical packages (SciPy, MATLAB, Mathematica, etc.).

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.

Mathematica script here (PDF).

---

Here's what these functions look like:

halfexpPicture http://faculty.washington.edu/sidles/Litotica_reading/halfexp.png

---

Final note: 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 asymptotic order, gain, and base can readily be constructed.

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.

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