f(f(x))=exp(x)-1 and other functions "just in the middle" between linear and exponential 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.

 A: If all you want is a compositional square root of something like $e^z-1$ analytic in some disk around the origin, I would go for $e^z-1-\frac 34 z=\frac z4+h(z)$. Then, putting $f(z)=\frac z2+g(z)$, we see that we need to solve
$$
g(z)=Tg(z)=-2g(\tfrac z2+g(z))+2h(z).
$$
Now consider the Banach space of all analytic in the disk $D$ of radius $r>0$ functions $g$ satisfying $\|g\|= \sup_{D}|g(z)|\cdot|z|^{-3/2}<+\infty$. If $r$ is small enough, then $T$ maps the unit ball in this space to itself and is a contraction there. 
A: This doesn't seem to be immediately germane to complexity theory, but the specific case of exp(x)-1 is somewhat interesting from the standpoint of formal groups.  exp(x)-1 gives a distinguished isomorphism between the formal additive group law and the formal multiplicative group law (and such an isomorphism only exists in characteristic zero).  There are two square roots of this isomorphism, yielding intermediate formal group laws.  For each prime p, both isomorphisms converge on a p-adic disc of small positive radius.  Similar behavior holds for n-th roots.
A: You can find the half-iterate of a function from known integer iterates by using Newton series, for example:
$$f^{[1/2]}(x)=\sum_{m=0}^{\infty} \binom {1/2}m \sum_{k=0}^m\binom mk(-1)^{m-k}f^{[k]}(x)$$
This does not converge for $f(x)=a^x$ where $a>e^{1/e}$ but since your function is somewhat different you can try this method.
Update. Here is a plot for $x<0$:
    (source)
For positive $x$ it seems the formula mostly does not converge.
A: And this is another construction.
Let $\sigma(x)=\exp(x)-1$ From this paper http://arxiv.org/abs/0812.4047 we know that
$$\exp(\sigma^{[p]}(t))=\sum_{n=0}^{\infty}B_n^p\frac{t^n}{n!}$$
where $B_n^p$ are the Bell's numbers of p-th order.
So to find $\sigma^{[1/2]}(t)$ we have to generalize Bell's numbers to fractional order.
We can easily do that by induction as follows:
$$A_0^x=1$$
$$A_{n+1}^x=\sum_{k=0}^{x-1} A_n^x\star A_n^k$$
And then
$$B_n^x=A_{n-1}^{x+1}$$
where $f(n)\star g(n)$ is the binomial convolution as described by Donald Knuth:
$$f(n)\star g(n)=\sum_{k=0}^n \binom nkf(n-k)g(k)$$
To obtain the value for any real x, we can note that the right part in $A_{n+1}^x=\sum_{k=0}^{x-1} A_n^x\star A_n^k$ is a polynomial of x and k of degree n-1 and integer coefficients and we can take indefinite sum of it symbolically following the rule
$$\sum_x ax^n=\frac{a B_{n+1}(x)}{n+1}$$
Where $B_a(x)$ are the Bernoulli polynomials.
A: The following link and references contained therein might be of interest: http://www.math.niu.edu/~rusin/known-math/99/sqrt_exp
A: Regarding the question
"Is this function f(x) or other functions with such an intermediate growth relevant to any interesting mathematics?"
you might be interested in the Grigorchuk group and other groups of intermediate growth. 
A: Consider $g(x)=e^x-1$. Then 
$g^n(x)= x+\frac{1}{2!}n x^2+\frac{1}{3!} \left(\frac{3 n^2}{2}-\frac{n}{2}\right)
   x^3+\frac{1}{4!} \left(3 n^3-\frac{5
   n^2}{2}+\frac{n}{2}\right) x^4 $
$+\frac{1}{5!}
   \left(\frac{15 n^4}{2}-\frac{65 n^3}{6}+5
   n^2-\frac{2 n}{3}\right) x^5 $
$ +\frac{1}{6!}
   \left(\frac{45 n^5}{2}-\frac{385 n^4}{8}+\frac{445
   n^3}{12}-\frac{91 n^2}{8}+\frac{11 n}{12}\right)
   x^6 $
$ +\frac{1}{7!}\left(\frac{315 n^6}{4}-\frac{1827
   n^5}{8}+\frac{6125 n^4}{24}-\frac{1043
   n^3}{8}+\frac{637 n^2}{24}-\frac{3 n}{4}\right)
   x^7 + \cdots$
Note that $g^0(x)=x, g^1(x)=e^x-1$ and that
$g^\frac{1}{2}(x)=x+\frac{x  ^2}{4}+ \frac{x^3}{48} +\frac{x^5}{3840}-\frac{7 x^6}{92160} +\frac{x^7}{645120}$ which is consistent with what Greg Kuperburg obtained.
A symbolic mathematical program will also confirm that $g^m(g^n(x))=g^{m+n}(x) +O(x^8)$
See The Euler-Arnold equation for more information.
A: 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/97/sqrt.exp (outdated link)

*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

*http://web.archive.org/web/20140521065943/http://www.math.niu.edu/~rusin/known-math/99/sqrt_exp
A: Non-convergence of the formal powerseries does not bother
Several times it was mentioned in the answers that the formal powerseries of the half iterate does not converge. That is true, however 
there is an elaborated theory about the fractional iteration of analytic functions with a fixed point $z_0$ which gives more far reaching answers.
Here we have the case of a parabolic fixpoint, i.e. $f'(z_0)=1$.
These functions have mostly no fractional iterates analytic at the fixpoint.
But
They have unique fractional iterates to the sides of the fixpoint, i.e. there are several domains bounded by/around the fixpoint which have the formal powerseries as asymptotic powerseries.
The arrangement of these domains is called Leau-Fatou flower (See the online book of Milnor [3] for details). The petals are alternating attractive and repellent when following the circle around the fixpoint. The number of these domains/petals is determined by number $m$ of zeros after the coefficient 1 in the powerseries development of $f$ at $z_0$. The number of domains is $2(m+1)$. 
In our case the fixpoint is 0 and the development is $e^z-1=z+\frac{z^2}{2}+\dots$, so $m=0$ and the number of petals is 2. One petal (the repelling) is on the positive axis and one petal (the attracting) is on the negative axis. On these two petals (which overlap in the complex plane) are the two (different, not being analytic continuations) solutions defined, that have the formal powerseries as asymptotic powerseries.
There are several (general) formulas possible to numerically compute these two solutions.
The classic formula of Lévy for the Abel function (with $\alpha_u(u)=0$) is too slow for computations:
$$\alpha_u(z) =\lim_{n\to\infty}\frac{f^{[n]}(z) -
    f^{[n]}(u)}{f^{[n+1]}(u)-f^{[n]}(u)} $$
The Newton formula for the regular fractional iteration is also too slow:
$$f^{[t]}(z) = \sum_{n=0}^\infty \binom{t}{n} \sum_{m=0}^n
  \binom{n}{m} (-1)^{n-m} f^{[m]}(z)$$
But the following formulas for the Abel function (adapted to $f(x)=e^x-1$) are quickly converging:
$$\alpha_1(z) = \lim_{n\to\infty} \frac{1}{3}\log(-f^{[n]}(z)) - \frac{2}{f^{[n]}(z)} - n, \quad z<0$$
$$\alpha_2(z) = \lim_{n\to\infty} \frac{1}{3}\log(f^{[-n]}(z)) -
  \frac{2}{f^{[-n]}(z)} + n, \quad z>0$$
You get the half iterate from the Abel function by $f^{[1/2]}(z)=\alpha^{-1}(1/2+\alpha(z))$ (independent on any additive constant of the Abel function). The non-Lévy formulas are probably first discovered by Écalle in his thesis [2] which deals completely with the parabolic case $f'(z_0)=1$.
[1] Kuczma, M., Choczewski, B., & Ger, R. (1990). Iterative functional equations. Encyclopedia of Mathematics and Its Applications, 32. Cambridge University Press. 
[2] Écalle, J. (1974). Théorie des invariants holomorphes. Publications math'ematiques d'Orsay, 67-74 09. Orsay: Univ. Paris-XI. 
[3] Milnor, J. (2006). Dynamics in one complex variable. 3rd ed. Princeton Annals in Mathematics 160. Princeton, NJ: Princeton University Press. viii, 304 p.
A: Here is light-hearted Mathematica holiday gift for everyone who has ever wondered (as I have) whether (smooth) half-exponential functions exist, and if so, what their graphs look like.   
The short answer is, yes, half-exponential functions do exist ... and their graphs look pretty much as we might (in retrospect) expect.  Be advised, however, that the  Mathematica notebook linked-to above uses engineering-grade mathematical methods (meaning, fans of rigor may be disappointed).  
The key idea is to specify the half-exponential composition relation as f(f(x)) = α exp(x-α), where α is an arbitrary real constant; this provides a starting fixed-point identity f(α)=α.  The rest of the construction is straightforward: we construct a series expansion about this fixed point, then Padé-approximate the series (to expand its convergence radius).
Needless to say, this approach tells us nothing about the analytic structure of f ... but the numerical robustness of the above Padé construction hints that a general integral representation for f (for example) might possibly be found.
If for some reason anyone needs a concrete numerical instantiation of a half-exponential function, these Padé methods might perhaps be useful ... my own motivation was pure fun.
Happy Holidays to everyone! :)
A: Allow me to leave alone the particular equation you mention and the issue of series, and focus instead on the general idea of finding functions "in the middle" between two families of functions. There is some extremely interesting mathematics in that idea.
The  essence of this part of your question is that you have two families of functions, in your case the linear functions and the exponential functions, and the first family lies below the second in the sense that every function in the lower family is eventually dominated by every function in the upper family. Because of this, it is very natural to want to understand the functions that lie between the two classes. In what circumstances and for which types of families $L$ and $U$ can we always find a function $f$ filling the gap? That is, we seek a function $f$ that eventually dominates the functions in the lower family $L$  and is eventually dominated by the functions in the upper family $U$. It is natural to consider the cases where the families are maximal in some sense, and as a special case, one might consider what happens when they are linearly ordered by eventual domination. 
Much of the content of this  question is present already in the case of functions $f:\mathbb{N}\to \mathbb{N}$, and indeed, it turns out that much of the fundamental phenomenon occurs already for functions $g:\mathbb{N}\to 2$, which amounts to considering the quotient $P(\omega)/Fin$, as in this MO answer.  
This way of thinking is intimately connected with the phenomenon of Hausdorff gaps.


*

*First, if both families are countable (or are determined by a countable sub-family, which is true in your case), then it is an enjoyable exercise to show that one may always fill the gap (first proved by Hausdorff). That is, given two countable families of functions, members of the first always eventually dominated by members of the second, then there is a function filling the gap. 

*Second, Hausdorff constructed examples of families of functions that do not admit any function in the middle; these gaps cannot be filled. That is, he produced a lower family $L$ and and upper family $U$, such that every function in the lower family was eventually dominated by every function in the upper family, but there is no function just in the middle, filling the gap. His examples were 
unfilled gaps having uncountable order type $(\omega_1,\omega_1)$, in the sense that the both the lower and upper families are determined by an almost-increasing $\omega_1$-sequence of functions. 

*The unfillable nature of these gaps, however, admits extensive set-theoretic independence, in the sense that an unfilled gap can sometimes be filled by a function that is added by forcing, that is, by moving to a larger set-theoretic universe. At the same time, there are methods of sealing a gap, that prevent it from ever being filled in a cardinal-preserving forcing extension. 

*Kunen  proved that it is consistent with Martin's axiom plus $\neg CH$ that there are unfilled gaps of type $(\omega_1,c)$ and $(c,c)$, where $c$ is the continuum, and also consistent that all such gaps are filled. 
A: There is a unique formal power series solution with $f(0) = 0$ and $f'(0) = 1$.  I had supposed that the coefficients would all be positive, which would imply that they are smaller than for $\exp(x)$ itself and thus that $f(x)$ is entire.  No such luck.  Maple gives me this:
$$f(x) = x + \frac{x^2}4 + \frac{x^3}{48} + \frac{x^5}{3840} - \frac{7x^6}{92160} + \frac{x^7}{645120} + \frac{53x^8}{3440640} + \cdots.$$
This doesn't say much about the possible radius of convergence of this series.  On the other hand, expecting it to be entire may have been naive from the beginning, because it seems unlikely that $f(f(x))$ would be periodic in the imaginary direction.

Since Michael Lugo has found evidence that the Taylor series has zero radius of convergence, it's not a very good way to describe or even define $f(x)$.  Is it clear that there is a unique $f(x)$ which is convex (at least for $x \ge 0$), and that that $f$ is smooth at 0 and real analytic away from $0$?  There is a book on fractional iteration of functions that presumably addresses these issues.
