# Finding f such that f(f(x))=g(x) given g

Suppose $g(x)$ is a smooth increasing function defined for $x \ge 0$ such that $g(x) \ge x$ for all $x$. Does there exist a function $f$ with similar properties such that $f(f(x))=g(x)$ for all $x \ge 0$? (You can interpret "similar" as widely as you'd like - smoothness would be great, but even continuity would be nice.)

I asked the question given these conditions on $g$ since it seems reasonable that they would produce a positive answer. However, I'm just as interested in the same question for more general classes of $g$. For example, suppose we only assume $g$ is continuous, or even measurable - can we find an $f$ with the same properties? And let's suppose we relax the requirement $g(x) \ge x$, etc (I included that because it helps ensure the existence of a set-theoretic $f$).

Under the given conditions, how many such $f$ exist?

-
See mathoverflow.net/questions/17614/solving-ffxgx and the links contained in that question. – Steven Gubkin May 31 '11 at 12:24
Another related question mathoverflow.net/questions/59302/… – quid May 31 '11 at 12:32
Yet another closely related MathOverflow question is "Closed-form” functions with half-exponential growth", 'mathoverflow.net/questions/45477/…; – John Sidles May 31 '11 at 13:27
I tried to use the standard algorithm $x\mapsto (x+\frac ax)/2$ for finding the square root of an increasing continuous bijection $g$ from $[0,1]$ to itself. The $f\mapsto (f+f^{-1}\circ g)/2$ version is ugly and the $f\mapsto (f+g\circ f^{-1})/2$ is extremely nice. Can anybody offer any explanation of this effect? – fedja May 31 '11 at 15:12
@fedja: this seems interesting, but I cannot understand fully what you did from your description. What did you compute exactly? What do you mean by "nice" and "ugly"? – Federico Poloni May 31 '11 at 16:00

I do not know for "the same properties", but Newton series does the trick for a large class of functions.

$$f(x)=g^{[1/2]}(x)=\sum_{m=0}^{\infty} \binom {1/2}m \sum_{k=0}^m\binom mk(-1)^{m-k}g^{[k]}(x)$$

-
I am unfamiliar with the use of your series for iterated functions. Do you have a reference for it being used with iterated functions? The series makes no mention of fixed points, yet they shape the dynamics in their neighborhood. – Daniel Geisler Mar 31 '14 at 4:48

My previous answer gives you a hint at analytic solution, but one may ask how to find the result in closed form.

To do so, one has to find family of flows $\phi_C(t)$ of the function $g(x)$ from the condition $\phi_C(t+1)=g(\phi_C(t))$. Then evaluate $\phi_C(1/2)$ and finally substitute $x$ instead of $C$.

For example, for the problem $f^{[2]}(x)=x^2$ the flow equation will be $\phi_C(t+1)=\phi_C(t)^2$ Taking logarithm with $C$ base one arrives at $\Delta\log_C(\phi_C(t))=\log_C\phi_C(t)$. Substituting $p(t)=\log_C\phi_C(t)$ we get a first-order linear difference equation $\Delta p(t)=p(t)$. Since $2^t$ is the only non-trivial function known to satisfy this equation, we get $\log_C\phi_C(t)=2^t$, and so $\phi_C(t)=C^{2^t}$. Evaluating at $1/2$ and substituting $x$ for $C$ we get $f(x)=x^{\sqrt{2}}$.

Of course, in many cases the equation may be non-linear and difficult to solve.

In general, any iterative equation of order $n$ (that is involving $f^{[n]}(x)$) is reducible to difference equation of order $n-1$ over flows. Such equation is expeted to have no more than $n-1$-dimentional space of solutions, except maybe some trivial cases so the original equation is also in non-trivial cases experted to have no more than $n-1$ solutions. Since your problem is iterative equation of order $2$, the solution is eqpected unique if exists, except some trivial cases such as $f^{[2]}(x)=x$ and $f^{[2]}(x)=-x$ where any 1-periodic and 1-antiperiodic functions (respectively) will satisfy as a flow.

-
This appears to be the first derivative only and of a specific iterated function. – Daniel Geisler Mar 31 '14 at 4:52
@Daniel Geisler I did not mention derivatives in the answer. – Anixx Mar 31 '14 at 9:34

Assume that $f(x)$ and $g(x)$ are analytic and that $f$ has a fixed point, without loss of generality $f(0)=0$ and therefore $f(f(0))=g(0)=0$. The Taylors series of $g^n(x)$ can be constructed. using Bell polynomials of iterated functions and then the iterate can be evaluated at $1/2$.

## Taylors series of iterated functions

Let $$f(x)=g^{1/2}(x)$$ then \begin{eqnarray*} g^n(x) &=& g_1^n x+ \frac{1}{2} g_2(\sum_{k_1=0}^{n-1}g_1^{2n-k_1-2}) x^2 \\ &+& \frac{1}{6}[g_3(\sum_{k_1=0}^{n-1}g_1^{3n-2k_1-3}) +3g_2^2 (\sum_{k_1=0}^{n-1} \sum_{k_2=0}^{n-k_1-2} g_1^{3n-2k_1-k_2-5}) ] x^3 + \cdots \end{eqnarray*}

Proof.

Let $h(x)=g^{n-1}(x)$, then

\begin{eqnarray*} Dg(h(z))&=&g'(h(x))h'(x)\\ &=&g'(g^{n-1}(x))Dg^{n-1}(x)\\ &=&\prod^{n-1}_{k_1=0}g'(g^{n-k_1-1}(x))\\ \end{eqnarray*}
\begin{eqnarray} Dg^n(0)&=&g'(0)^n \\ &=&g_1^n = g_1^{1/2} \end{eqnarray} For the second derivative \begin{eqnarray} D^2g^n(0)&=&g_2g_1^{2n-2}+g_1 D^2g^{n-1}(0) \\ &=&g_1^0g_2 g_1^{2n-2} \\ &&+g_1^1g_2 g_1^{2n-4} \\ &&+\cdots \\ &&+g_1^{n-2}g_2 g_1^2 \\ &&+g_1^{n-1}g_2 g_1^0 \\ &=&g_2\sum_{k_1=0}^{n-1}g_1^{2n-k_1-2} \end{eqnarray} For the third derivative \begin{eqnarray} D^3g^n(0)&=&g_3g_1^{3n-3}+3 g_2^2\sum_{k_1=0}^{n-1}g_1^{3n-k_1-5} +g_1 D^3g^{n-1}(0) \\ &=&g_3\sum_{k_1=0}^{n-1}g_1^{3n-2k_1-3} +3g_2^2 \sum_{k_1=0}^{n-1} \sum_{k_2=0}^{n-k_1-2} g_1^{3n-2k_1-k_2-5} \end{eqnarray}

Note that the index $k_1$ from the second derivative is renamed $k_2$ in the final summation of the third derivative. A certain amount of renumbering is unavoidable in order to use a simple index scheme.

$\blacksquare$

Algebraic expansion shows that $$g^m(g^n(x))=g^{m+n}(x)$$.

## Classification of Fixed Points

Note that $g^n(x)$ was not evaluated at $n=1/2$. What at first may appear to be a defect is a strength as it reveals the impact of the classification of fixed points. If $g'(0)$ equals a root of unity, then the geometrical progressions evaluate very differently than the standard method of evaluation. This formula works regardless of whether dealing with hyperbolic fixed points, parabolically neutral fixed points and rationally and irrationally neutral fixed points.

-