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](https://mathoverflow.net/questions/12081/does-the-exponential-function-have-a-square-root) and [here](https://mathoverflow.net/questions/4347/ffxexpx-1-and-other-functions-just-in-the-middle-between-linear-and-expo). See also the comments on an [old blog post](http://www.scottaaronson.com/blog/?p=263) 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?



"Closed-form" functions with half-exponential growth
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).


