# “Closed-form” functions with half-exponential growth

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?

-
The remark can't even be analytic needs explanation. "Analytic in the whole complex plane" is, indeed, ruled out. But in fact $\log x$ "can't even be analytic" in that sense... – Gerald Edgar Nov 9 '10 at 19:35
What are you asking for is just to find an elementary function with the cited properties. Any elementary function can be expressed by composition of the operations +, -, *, /, exp, and log, together with arbitrary real constants and the opposite: any combination thereof is an elementary function by definition. No need to invoke the term "closed form". – Anixx Nov 10 '10 at 2:15

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

-
Indeed, I think that you don't even need to get into transseries per se; looking at the Hardy field should be enough, so that looking at older references like Rosenlicht's papers might be enough to prove it. See e.g. jstor.org/stable/1999639 – Thierry Zell Nov 9 '10 at 19:33
When Scott reads this, he may think of adding inverse function to his operations. That may get you outside of the original Hardy space, but still keeps you within the transseries. – Gerald Edgar Nov 9 '10 at 19:48
Thanks so much, Gerald! Yeah, I also made the observation that every montone composition of *, +, exp, log has an integer-valued "exponentiality level" associated with it. But I didn't know how to prove that this "level property" is preserved under subtraction and division. I'll take a look at the references you gave! – Scott Aaronson Nov 9 '10 at 21:22
The analytic structure of the Lambert W function points to an even stronger conjecture: for values d>e^(1/e), no smooth function satisfies the composition f(f(n))=d^n. It's no wonder that these demi-exponential functions (as Dick Lipton and Ken Regan call them) have earned a reputation for being difficult to construct. – John Sidles Apr 29 '11 at 18:00

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:

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

-
There is a paper (I don't have the reference handy) that as I recall does this: Using the idea of the fixed-point construction of the fractional iterate, but in case there is no real fixed point, uses a pair of complex-conjugate fixed points to construct a real fractional iterate. I think some contour integrals were in there, too. – Gerald Edgar Apr 29 '11 at 19:19
here it is... H.Trappmann, D.Kouznetsov. Uniqueness of Analytic Abel Functions in Absence of a Real Fixed Point. Aequationes Mathematicae, v.81, p.65-76 (2011) – Gerald Edgar May 4 '11 at 15:19
Thank you very much, Gerald! It appears that these authors and I are solving somewhat different problems, using rather similar methods ... and they too are reporting mainly numerical results. It seems there is an opportunity here for someone (not me!) to advance our analytical understanding of these functions. – John Sidles May 5 '11 at 14:06