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$.

Solution 1:

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.