The question is about the function f(x) so that f(f(x))=exp (x)-1.
The question is open ended and it was discussed quite recently in the comment thread in Aaronson's blog here http://scottaaronson.com/blog/?p=263
The growth rate of the function f (as x goes to infinity) is larger than linear (linear means O(x)), polynomial (meaning exp (O(log x))), quasi-polynomial (meaning exp(exp O(log log x))) quasi-quasi-polynomial etc. On the other hand the function f is subexponential (even in the CS sense f(x)=exp (o(x))), subsubexponential (f(x)=exp exp (o(log x))) subsubsub exponential and so on.
What can be said about f(x) and about other functions with such an intermediate growth behavior? Can such an intermediate growth behavior be represented by analytic functions? Is this function f(x) or other functions with such an intermediate growth relevant to any interesting mathematics? (It appears that quite a few interesting mathematicians and other scientists thought about this function/growth-rate.)
Related MO questions:
- solving $f(f(x))=g(x)$
- How to solve $f(f(x)) = \cos(x)$?
- Does the exponential function has a square root
- Closed form functions with half-exponential growth
- $f\circ f=g$ revisited
- The non-convergence of f(f(x))=exp(x)-1 and labeled rooted trees
- The functional equation $f(f(x))=x+f(x)^2$
- Rational functions with a common iterate
- Smoothness in Ecalle's method for fractional iterates.
Best Answer
Let me see if I can summarize the conversation so far. If we want $f(f(z)) = e^z+z-1$, then there will be a solution, analytic in a neighborhood of the real axis. See either fedja's Banach space argument, or my sketchier iteration argument. The previous report of numerical counter-examples were in error; they came from computing $(k! f_k)^{1/k}$ instead of $f_k^{1/k}$. We do not know whether this function is entire. If it is, then there must be some place on the circle of radius $R$ where it is larger than $e^R$. (See fedja's comment here.)
If we want $f(f(z)) = e^z-1$, there is no solution, even in an $\epsilon$-ball around $0$. According to mathscinet, this is proved in a paper of Irvine Noel Baker, Zusammensetzungen ganzer Funktionen, Math. Z. 69 (1958), 121--163. However, there are two half-iterates (or associated Fatou coordinates $\alpha(e^z - 1) = \alpha(z) + 1$) that are holomorphic with very large domains. One is holomorphic on the complex numbers without the ray $\left[ 0,\infty \right)$ along the positive real axis, the other is holomorphic on the complex numbers without the ray $\left(- \infty,0\right]$ along the negative real axis. And both have the formal power series of the half-iterate $f(z)$ as asymptotic series at 0.
If we want $f(f(z))=e^z$, there are analytic solutions in a neighborhood of the real line, but they are known not to be entire.
I'll make this answer community wiki. What else have I left out of my summary?
Here is a related MO question. The answers to the new question contain further interesting information. Let me mention here a link with many references on "iterative roots and fractional iterations" one particular link on the iterative square root of exp (x) is here.
The following two links mentioned in the old blog discussion may be helpful
http://www.math.niu.edu/~rusin/known-math/99/sqrt_exp (outdated link)
http://web.archive.org/web/20140521065943/http://www.math.niu.edu/~rusin/known-math/97/sqrt.exp