# Is there a function such that $f(f(n)) = 2^n$?

In this question, I was looking for a specific "middle family" of functions between polynomials and "anti-polynomial exponentials", as I will call them, which are functions like like $2^{\sqrt{n}}$ that become exponential when chained to a polynomial (in the above case, $f(n^2) = 2^n$).

Now what I'm wondering is whether there exists a function that lies "exactly halfway" between linear and exponential in this way. Does there exist a continuous, monotone function $f: \mathbb{R}^+ \rightarrow \mathbb{R}^+$ such that $f(f(x)) = 2^x$ for all $x > 0$? Is there a closed form for it?

• aha! possible duplicate of this (if it's not too hard to change the base) math.stackexchange.com/questions/65876/thoughts-about-ffx-ex – Jam Jul 16 '14 at 2:57
• That question didn't appear at all in the list of suggested questions while I was writing this question. I wonder why. – Joe Z. Jul 16 '14 at 2:59
• possibly because of the different variables and base even though similar content? – Jam Jul 16 '14 at 3:00
• That is indeed a possibility. – Joe Z. Jul 16 '14 at 3:00

I'm having trouble getting the 2; Helmut Kneser showed that there is a real analytic function, call it $h(x),$ such that $$h(h(x)) = e^x.$$

It might be necessary to redo the whole argument to get $2.$ Kneser and related papers at MEEEEEEEEEEEEEEEEEEEEE

A good example is the half iterate of $\sin x,$ it took me quite a while, but see https://mathoverflow.net/questions/45608/formal-power-series-convergence/46765#46765

on average, a decreasing function rules out any half iterate, $\sin x$ is an extremely special case.

Note that if we just ask for differentiabilty, there is a theorem in the KCG book that gives it. I think I included that in the excerpts on my website.

• Unfortunately, I can't read German :( – Joe Z. Jul 16 '14 at 3:01
• There was a thread a while ago where someone translated a whole paper from German. I wouldn't get your hopes up though; I'm looking for a translation. – Jam Jul 16 '14 at 3:07
• @JoeZ., as far as I know the upshot is this: given a real, increasing real analytic function such that we always have $g(x) \neq x,$ we can construct a half iterate. The hard part comes when there is a fixed point, it is no longer possible to arrange analyticity. – Will Jagy Jul 16 '14 at 3:07
• @WillJagy - is there an explicit form? Can you plot the function? – nbubis Jul 16 '14 at 3:13
• @WillJagy: Perhaps this was discussed in the linked question, but is there are there any obvious bases for which a half iterate cannot be constructed? – Semiclassical Jul 16 '14 at 3:15

It is possible to define such function piecewise, too. Assume that $f(0)=\frac{1}{2}$, then $f(1/2)=1$.

Let $I_0=[0,1/2]$ and define $f$ over $I_0$ as $$f(x)=x+\frac{1}{2}.$$ Since $f(1)=\sqrt{2}$, we can take $I_1=[1/2,1]$ and define $f$ over $I_1$ as $$f(x)=2^{x-1/2},$$ then $f$ over $I_2=[1,\sqrt{2}]$ as $$f(x)=x\sqrt2,$$ $f$ over $I_3=[\sqrt{2},2]$ as $$f(x)=2^{x/\sqrt2},$$ $f$ over $I_4=[2,2^\sqrt2]$ as $$f(x)=x^\sqrt{2},$$ $f$ over $I_5=[2^\sqrt2,4]$ as $$f(x)=2^{x^{1/\sqrt2}},$$ $f$ over $I_6=[4,2^{2^\sqrt2}]$ as $$f(x)=2^{(\log_2 x)^{\sqrt2}},$$ $f$ over $I_7=[2^{2^\sqrt 2},16]$ as $$f(x)=2^{2^{(\log_2 x)^{1/\sqrt2}}},$$ $f$ over $I_8=[16,2^{2^{2^\sqrt2}}]$ as $$f(x)=2^{2^{(\log_2 \log_2 x)^{\sqrt2}}}$$ and so on.

We have $I_{n+1}=[\max I_n,2^{\min I_n}]$ and given that $g_n$ is the inverse function of $f_{|I_n}$, $$f_{|I_{n+1}}=2^{g_n}.$$ Continuity and monotonicity are met.

• Apparently real-analytic is what I was looking for, because it's a stronger condition and actually doable. – Joe Z. Nov 21 '15 at 20:19

This doesn't seem to work but if someone could tell me what exactly is wrong with this reasoning, I'd be most appreciative.

$$\text{let}\quad f\circ f(x):=a^x, \quad f(x)=a^{kx} \quad\text{for arbitrary a}$$ $$a^{\displaystyle{ka^{kx}}}=a^x$$ $$(kx)e^{(kx)}=x^{1+1/\ln(a)}$$ $$k=\frac{\mathrm{W}\left(x^{1+1/\ln(a)}\right)}{x}$$ $$\therefore\quad f(x)=e^{\left(\mathrm{W}\left(x^{1+1/\ln(a)}\right)\right)}$$

I'm fairly sure it's wrong but can't see why.