Characterising functions $f$ that can be written as $f = g \circ g$?

I'd like to characterise the functions that ‘have square roots’ in the function composition sense. That is, can a given function $f$ be written as $f = g \circ g$ (where $\circ$ is function composition)?

For instance, the function $f(x) = x+10$ has a square root $g(x) = x+5$.

Similarly, the function $f(x) = 9x$ has a square root $g(x) = 3x$.

I don't know if the function $f(x) = x^2 + 1$ has a square root, but I couldn't think of any.

Is there a way to determine which functions have square roots? To keep things simpler, I'd be happy just to consider functions $f: \mathbb R \to \mathbb R$.

-
Your second example is wrong, by the way. –  Qiaochu Yuan Jul 29 '10 at 7:25
For your second example, I think you want either $f(x) = 9x$ or $g(x) = \sqrt{6}x$ (but not both!). –  Pete L. Clark Jul 29 '10 at 7:25
Thanks - fixed it. –  bryn Jul 29 '10 at 7:37
@Qiaochu -- thanks for finding that for me. Could you put it as an answer to the question, optionally with a brief summary? –  bryn Jul 29 '10 at 7:38

I showed you the link to the MO question mostly to convince you that this is a hard question. I will "answer" it in the special case that $f$ is a bijection.

Recall that given a bijection $f : S \to S$, where $S$ is a set, a cycle of $f$ length $n$ is a set of distinct points $x, f(x), ... f^{n-1}(x)$ such that $f^n(x) = x$. A cycle of infinite length is a set of distinct points $x, f(x), f^2(x), ...$. It is not hard to see that $S$ is a disjoint union of cycles of $f$.

Claim: A bijection $f : S \to S$ has a square root if and only if there are an even number of cycles of $f$ of any given even length. (For the purposes of this result, infinity is an even number; so there can be an infinite number of cycles, and you need to consider cycles of infinite length.)

Proof. First we show that any bijection with a square root has this property. Let $g : S \to S$ be a bijection such that $g(g(x)) = f(x)$. Then each cycle of $g$ corresponds to either one or two cycles of $f$, as follows. If the cycle has odd length, it corresponds to one cycle of $f$. For example, the cycle $1 \to 2 \to 3 \to 1$ of $g$ would correspond to the cycle $1 \to 3 \to 2 \to 1$ of $f$. If the cycle has even length, it corresponds to two cycles of $f$. For example, the cycle $1 \to 2 \to 1$ of $g$ would correspond to the pair of cycles $1 \to 1$ and $2 \to 2$, and the cycle $1 \to 2 \to 3 \to ...$ would correspond to the pair of cycles $1 \to 3 \to ...$ and $2 \to 4 \to ...$. In particular, cycles of $f$ of odd length can come from cycles of $g$ one at a time or two at a time, but cycles of $f$ of even length can only come from cycles of $g$ two at a time.

Now we show the reverse implication. Given a cycle of $f$ of odd length $2k+1$, consider the corresponding cycle of $f^{k+1}$ of odd length. Since $f^{2k+2} = f$ when restricted to this cycle, make this a cycle of $g$. Given a pair of cycles of $f$ of the same even length, just weave them together to get a cycle of $g$.

I say "answer" instead of answer because it's not obvious if you can always find the cycle decomposition of some complicated bijection on an infinite set. In any case, if $f$ isn't assumed to be a bijection this question becomes much harder; the analogue of cycle decomposition is much more difficult to work with. I suggest you look at some examples where $S$ is finite if you really want to get a grip on this case; best of luck.

-
Here is a nontrivial application: the function f(x) = -x has a square root. But none of its square roots are continuous. –  Qiaochu Yuan Jul 29 '10 at 8:15
If I'm not mistaken, your answer and proof extend naturally to arbitrary injections $f:S\to S$, except that we have to count singly and doubly infinite chains separately. It's the non-injective case that's difficult. –  Ilmari Karonen Dec 25 '11 at 12:39
If the function is not injective, then you'll have "incoming chains" leading into the cycles (for infinite cycles, it's of course not obvious which of the incoming chains is to be considered the cycle and which one an initial chain; basically you get a "river structure" where many chains merge into one). If I see it correctly, for even cycles, you must to be able to map the initial chains of two even cycles onto each other. There should be also some condition for odd chains; I'd guess the condition there is that either there are no incoming chains, or each node of the cycle has one. –  celtschk Jun 14 '13 at 6:06
Actually the "incoming chains" also have "river structure", therefore an additional condition for off loops should be that all incoming chains of an odd cycle are structurally equal. –  celtschk Jun 14 '13 at 6:10
I think over the real numbers, $f(x)=x^2+1$ has no square root because it has an infinite "extended cycle" for every $x_0\in[0,1)$, but the cycle belonging to $x_0=0$ has a different structure than all the others (because there's no distinct incoming "chain" from $-x_0$). –  celtschk Jun 14 '13 at 6:20