(asked by Nathaniel Hellerstein on the Q&A board at JMM)
Is there a "half-exponential" function $h(x)$ such that $h(h(x))=e^x$? Is it unique? Is it analytic?
Related question: Is there an invertible smooth function $E$ such that $E(x+1)=e^{E(x)}$? Is it unique? If so, then we can take $h(x)=E(E^{-1}(x)+1/2)$.
There is no entire (holomorphic everywhere) function $f(z)$ with $f(f(z)) = e^z$. To see this, one can use Picard's little theorem, and do case analysis. For example, $f(z)$ cannot take all values, for then so does $f(f(z))$, while $e^z$ omits zero. The case that $f(z)$ has an omitted value can also be excluded, this is not difficult.
EDIT: Perhaps I should be more explicit. If $f(z)$ omits a value, that has to be zero, for $e^z$ takes all other values. Thus there is an entire function $h(z)$ such that $f(z) = e^{h(z)}$ (the complex plane is simply connected). Now
$ e^{h(e^{h(z)})} = e^z $
and so $h(e^{h(z)}) = z + 2{\pi}ik$ for some fixed integer $k$. Since the right hand side takes all values, so does the left hand side. So $h(z)$ takes the two values $0$ and $2{\pi}i$, say $h(a) = 0$ and $h(b) = 2{\pi}i$. Now
$ a + 2{\pi}ik = h(e^{h(a)}) = h(e^0) = h(e^{2{\pi}i}) = h(e^{h(b)}) = b + 2{\pi}ik $
and so $a = b$. Contradiction!
Alternatively, use the theorem of Polya that if $f(z)$ and $g(z)$ are entire functions, then $f(g(z))$ is of infinite order unless (i) $f(z)$ is of finite order and $g(z)$ is a polynomial, or (ii) $f(z)$ has order zero and $g(z)$ is of finite order. The exponential function has order $1$.
EDIT: Here $f(f(z)) = e^z$ yields the absurd conclusion that $e^z$ is a polynomial in case (i). While in case (ii) we find that $f(z)$ is an entire function of order zero with $f(f(z)) = e^z$. But an entire function of order zero that is not a polynomial takes every value infinitely often (by the Hadamard factorization theorem), so we are led to the absurd conclusion that $e^z$ takes the value zero infinitely often.
Yes, there exists a real-analytic injective $E$.
Its inverse $E^{-1}$ is constructed in the paper of Kneser [1].
Uniqueness: $E^{-1}$ is the only holomorphic and injective Abel function (up to an additive constant) on the "sickle" $G$ given in the following way: Let $z_0$ and its conjugate $z_0^\ast$ be the both fixpoints of $e^z$ closest to the real axis, let $\ell$ be the straight line segment connecting $z_0$ and $z_0^\ast$ and let $\ell_1$ be the image of $\ell$ under $e^z$. Now let $G$ be the region bounded by $\ell$ and $\ell_1$ inclusive and $z_0$, $z_0^\ast$ exclusive. See also [2].
For the general theory of Abel functions between two complex fixed points (which is a relatively new development in holomorphic dynamics which is unaware of its application to the exponential), see [3].
[3] Shishikura, M. (2000). Bifurcation of parabolic fixed points. In Lei, Tan, The Mandelbrot set, theme and variations. Cambridge: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 274, 325-363.
For many references see http://reglos.de/lars/ffx.html.
To avoid repetition see What’s a natural candidate for an analytic function that interpolates the tower function? for my general explanation of tetration.
A distinguishing feature of the exponential function is that it has an infinite number of complex fixed points, for example $0.318132 + 1.33724 i$. The lack of real fixed points results in $f: \mathbb{R} \rightarrow \mathbb{C}$, where $f(f(x))=e^x$.
I recommend at least three books for anyone serious about this subject:
In fact, a picture of the exponential map is on the cover of Devaney's book. Both dynamics and functional equations address fractional iteration. Elements of dynamics are covered in functional equations and the reverse is also true, at least when discussing fractional iteration.
One way to validate or invalidate a proposed solution is to see if it is consistent or inconsistent with the theorems of complex dynamics. If a solution doesn't treat a fixed point as a fixed point, then it is defective. If the solution is inconsistent with the linearization theorem in the neighborhood of a fixed point, then the solution is defective. If the solution is inconsistent with the classification of fixed points and violates topological conjugacy the solution is defective.
Re: second question.
Yes, there are many of them on a half-line. Just take any smooth increasing function on $[0,1]$ with the property that $E(1)$ and $E'1(1)$ have desired values and extend it by the rule above. Since $E(x) > x$ the function will be increasing, thus invertible.
No, there are none on the whole line. For any number $x$, the sequence $\mathop{\text{ln}} \mathop{\text{ln}} \dots \mathop{\text{ln}} x$ cannot be continued indefinitely; at some point you encounter negative numbers.
Here are graphics of various iterates of exponent to various values of base; see http://mizugadro.mydns.jp/t/index.php/File:E1e14z600.jpg for more details:
The non-existence of a holomorphic compositional square root of the exponential can be proved by an elementary argument, which does not used Picard's theorem.
The range of $h$ contains that of $\exp$, so is either ${\mathbb C}$ or ${\mathbb C}^\times$. If $h$ was onto, then $h\circ h$ would be onto, which is false. Therefore $h({\mathbb C})={\mathbb C}^\times$.
The function $h'/h$ is thus entire. It admits a (unique) primitive $g$ with a given initial condition $g(0)$ such that $h(0)=\exp g(0)$. Then $(he^{-g})'\equiv0$ gives $h=\exp\circ g$.
We have $\exp\circ g\circ \exp\circ g=\exp.$ Hence, for every $z\in {\mathbb C}$, there exists an integer $k(z)$ such that $g\circ\exp\circ g(z)=z+2ik(z)\pi$. The function $z\mapsto 2ik(z)\pi=g\circ\exp\circ g(z)-z$ is continuous from ${\mathbb C}$ (connected) to $2i\pi{\mathbb Z}$ (discrete): it is constant.
Let $T$ denote the translation $z\mapsto z+2ik\pi$, which is a bijection. From $g\circ(\cdots)=T$, we see that $g$ is onto. From $(\cdots)\circ g=T$, we see that $g$ is one-to-one. Hence $g$ is bijective.
Finally, $\exp=g^{-1}\circ T\circ g^{-1}$ is bijective, an obviously false statement.
Edit. Actually, the proof works almost the same for a continuous compositional square root. We only need to prove the existence of a continuous $g:{\mathbb C}\rightarrow{\mathbb C}$ such that $h=\exp\circ g$. This is guaranted by the fact that $\exp:{\mathbb C}\rightarrow{\mathbb C}^\times$ is a covering with ${\mathbb C}$ simply connected (universal cover).
If you take an exponential with a base $a < e^{1/e}$, finding the iterative square root of $f(x)=a^x$ is not so difficult.
You can use one of the following formulas:
$$f^{[1/2]}(x)=\sum_{m=0}^{\infty} \binom {1/2}m \sum_{k=0}^m \binom mk (-1)^{m-k}\exp_a^{[k]}(x)$$
$$f^{[1/2]}(x)=\lim_{n\to\infty}\binom {1/2} n\sum_{k=0}^n\frac{x-n}{x-k}\binom nk(-1)^{n-k}\exp_a^{[k]}(x)$$
$$f^{[1/2]}(x)=\lim_{n\to\infty}\frac{\sum_{k=0}^{2n} \frac{(-1)^k \exp_a^{[k]}(x)}{(1/2-k)k!(2n-k)!}}{\sum_{k=0}^{2n} \frac{(-1)^k }{(1/2-k) k!(2n-k)!}}$$
$$f^{[1/2]}(x)=\lim_{n\to\infty} \log_a^{[n]}\left(\left(1-\left(\ln \left(\frac{W(-\ln a)}{-\ln a}\right)\right)^{1/2}\right)\frac{W(-\ln a)}{-\ln a}+\ln \left(\frac{W(-\ln a)}{-\ln a}\right)\exp_a^{[n]}(x)\right)$$
Here is a graph of an iterative square root of a function $f(x)=(\sqrt{2})^x$:
Regarding second part of the question, such a specially constructed function is called a superfunction or flow. For bases $a \le e^{1/e}$ superfunctions can be easily constructed from the above formulas by substituting a variable for 1/2. Of course the superfunction is not unique but there are certain more "natural" solutions.
The question becomes more difficult when speaking about the base $a>e^{1/e}$. But in this case the superfunction can also be constructed, see this article.
In an excerpt of this post from my blog, I have constructed a non-analytic (but continuous and differentiable) half-iterate of $e^x$.
Okay, this piecewise definition gets a bit gross, so bear with me.
Define a sequence $a_n$ as follows: $$a_{-1}=-\log(2),\space\space a_0=0$$ $$a_{n+2}=\exp(a_n)$$ and define a sequence of functions $H_n$ as follows: $$H_{-2}(x)=\log(e^x+0.5)$$ $$H_{n+1}(x)=\exp(H^{-1}_n(x))$$ Then one may show verify rather simply that the function $$h(x) = \left\{ \begin{array}{lr} H_{-2}(x) & : -\infty \lt x \le -\log(2)\\ H_n(x) & : a_n\lt x \le a_{n+1} \end{array} \right.\\$$ satisfies $(h\circ h)(x)=e^x$. If it helps, I can write the definition out for you this way: $$h(x) = \left\{ \begin{array}{lr} \ln(e^x+0.5) & : -\infty \lt x \le -\log(2)\\ e^x-0.5 & : -\log(2)\lt x \le 0\\ x+0.5 & : 0\lt x \le 0.5\\ e^{x-0.5} & : 0.5\lt x \le 1\\ \text{etc}...\\ \end{array} \right.\\$$ With a bit more difficulty (and induction), one may prove that it is differentiable on $\mathbb R$ (unfortunately, it is not twice differentiable). Here is its graph (in orange) alongside a graph of $y=e^x$ (in purple):
One more interesting fact about half-exponential functions: there are infinitely many increasing and continuous half-iterates $f$ of $e^x$. For every single one of them, it can be proven that the following is true: $$1\lt \int_0^1 f(x)dx\lt \ln^2(2)-2\ln(2)+2\approx 1.0942$$ If anyone asks, I'll add a proof of this, but I won't add one now since it's not entirely relevant to the question.
For any nonpositive $x$, define the sequence $(x_0, x_1, ...)$ by $x_0 = x$, $x_{i+1} = e^{x_i}$. If we let $y$ be another nonpositive real number, and define $(y_0, ...)$ similarly, then if we define $h$ on the union of these two sequences by $h(x_i) = y_i$, $h(y_i) = x_{i+1}$, we get $h(h(x_i)) = x_{i+1}$, $h(h(y_i)) = y_{i+1}$. So, to define $h$ everywhere, we just pair off the nonpositive reals any old way and define $h$ as above for each pair (every number can be written as an $x_i$ for a unique $i \ge 0, x \le 0$, so this defines $h$ on the entire real line). Thus, there are actually uncountably many square roots of the exponential function, almost all of which are horribly discontinuous.
Edit: in fact, any such $h$ must be of this form - if $h(x_0) = y_i$, then we must have $h(y_i) = x_1, h(x_1) = y_{i+1}, ..., h(y_{i+j}) = x_{j+1}, h(x_j) = y_{i+j}$, if $y = x$ then we have a problem when we plug in $j = i$, so we must have $y \ne x$, and by a similar argument if $h(y_0) = z_k$ for some $k$, then $x_1 = h(y_i) = z_{i+k}$ so $x = z, i+k = 1$, so either $h(x_0) = y_0, h(y_0) = x_1$ or vice-versa.
To find such a pairing producing a continuous $h$, you can take any homeomorphism $f : (-\infty, -1] \rightarrow (-1, 0]$, such as $f(x) = e^{x+1}-1$, and have your pairs be of the form $(x, f(x))$.
Assume that this half-exponential function $h(x)$ is of the form $a+bx+cx^2$, or a quadratic function. Attempting to expand out $h(h(x))$ gives us the following: $$h(h(x)) = a+ab+b^{2}x+bcx^{2}+a^{2}c+2abcx+2ac^{2}x^{2}+b^{2}cx^{2}+2bc^{2}x^{3}+c^{3}x^{4}$$
If we solve for the Taylor series expansion of $e^x$ at n=2, $\frac{x^2}{2}+x+1$, then the large expansion can be reduced down to a system of equations:
$$a+ab+a^{2}c = 1,$$ $$b^{2} + 2abc = 1,$$ $$bc+2ac^{2}+b^{2}c = \frac{1}{2}$$
I asked WolframAlpha to solve this system of equations, and the only real solution it came out with was $a≈0.497894, b≈0.878113, c≈0.261795$. So $h(x)$ would be roughly equal to $0.261795x^{2}+0.878113x+0.497894$. The inverse of $h(x)$ (or the compositional square root of $ln(x)$), is, according to Wolfram, $-1.6771 ± 1.90989×10^{-6} \sqrt{1.04718×10^{12} x + 2.49698×10^{11}}$.
Of course, given that the previously mentioned Taylor series expansion of $e^x$ isn't a very good approximation, these approximations are rather innacurate, and are only accurate to about 1 or 2 digits for small $x$. But computing this for cubics or higher would be a nightmare, so that's the best I could find. Here's a plot of $h(x)$: (plot)
