MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## 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?

I'm not entirely what the tag should be, so please feel free to edit it.

-
See mathoverflow.net/questions/17614/solving-ffxgx and the links contained in that question. – Steven Gubkin May 31 2011 at 12:24
Another related question mathoverflow.net/questions/59302/… – quid May 31 2011 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 2011 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 2011 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 2011 at 16:00
show 1 more comment