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.
The square root always exists and, except for the special case where $f$ is the identity, there are uncountably many square roots.
Case I: $f$ has no fixed points in $(0,1)$. By the intermediate value theorem, we either have
- $f(x) > x$ for all $x\in(0,1)$ or,
- $f(x) < x$ for all $x\in(0,1)$.
I will consider (1) (the situation with $f(x) < x$ can be handled similarly). Choose any $x_0\in(0,1)$ and set $x_k=f^k(x_0)$, which is a strictly increasing sequence over $k\in\mathbb{Z}$. The limits of $x_k$ as $k\to\pm\infty$ are fixed points of $f$, so are equal to $1$ and $0$ respectively.
Now, choose any increasing homeomorphism $\theta\colon[0,1]\to[x_0,x_1]$. Extend $\theta$ to all of $\mathbb{R}$ by setting
$$
\theta(k+x)=f^k(\theta(x))
$$
for $k\in\mathbb{Z}$ and $x\in[0,1)$. This defines a homeomorphism from $\mathbb{R}$ to $(0,1)$. Furthermore,
$$
f(\theta(x))=\theta(x+1).
$$
We can define a square root by
$$
g(x) = \theta(\theta^{-1}(x)+1/2)
$$
for $x\in(0,1)$, and $g(0)=0$, $g(1)=1$. Note that $g(x_0)=\theta(1/2)$, which can be chosen to be any value in $(x_0,x_1)$, so there are infinitely many square roots.
Case II: Now, for the general case.
Let $S\subseteq[0,1]$ be the set of fixed points of $f$. We define the square root to also be the identity on $S$. As $S$ is closed, its complement is a countable union of disjoint open intervals $(a,b)$ and, restricted to each such interval, $f$ gives a homeomorphism of $[a,b]$ with no fixed points in $(a,b)$. So, applying the construction above, there are uncountably many square roots on each such interval. So, $f$ has a square root and, except in the case where $S$ is all of $[0,1]$, there are uncountably many square roots.
Best Answer
Introduce a new coordinate system with a fixed point of $f$ as origin, e.g. the point $\omega:=e^{\pi i/3}$. Writing $x=\omega+\xi$ with a new independent variable $\xi$ one has $\phi(\omega+\xi)=\omega +\psi(\xi)$ for a new unknown function $\psi$ with $\psi(0)=0$. This function $\psi$ satisfies in a neighbourhood of $\xi=0$ the functional equation $\psi(\psi(\xi))=2\omega\xi+\xi^2$. Now you can recursively determine the Taylor coefficients of $\psi$. If you are lucky the resulting formal series actually defines an analytical function in a neighbourhood of $\xi=0$.