Find $f(x)$ such that $f(f(x)) = x^2 - 2$ 
Find all $f(x)$ satisfying $f(f(x)) = x^2 - 2$.

Presumably $f(x)$ is supposed to be a function from $\mathbb R$ to $\mathbb R$ with no further restrictions (we don't assume continuity, etc), but the text of the problem does not specify further. 
Possibly Helpful Links: Information on similar problems can be found here and here.
Source: This question. It is about to be closed for containing too many problems in one question. I'm posting each problem separately. 
 A: The following observation comes from a comment by Sergei Ivanov in this MathOverflow post. It discusses the existence of $f : \mathbb{C} \to \mathbb{C}$ such that $f(f(z)) = g(z)$ where $g(z) = z^2 - 2$. I am aware that this is not precisely what the question asks for, but it may be helpful.

Let $g : \mathbb{C} \to \mathbb{C}$ be a quadratic polynomial such that $g(z) - z$ has distinct roots, then there are four solutions of $g(g(z)) = z$: the two roots of $g(z) - z$ and two points $a$, $b$ such that $g(a) = b$ and $g(b) = a$. If $g(z) = f(f(z))$ then the point $f(a)$ must be another solution to $g(g(z)) = z$. Note, this doesn't assume $f$ is continuous.

(Note: I have paraphrased the above text; the original comment can be found here.)
Now note that if $g(z) = z^2 - 2$, then $g(z) - z = z^2 - z - 2 = (z - 2)(z + 1)$, so the above observation applies to $z^2 - 2$.

Here are some details about the second paragraph.
Why are there four solutions to $g(g(z)) = z$?
$g(z)$ is a quadratic, so $g(g(z))$ is a quartic, as is $g(g(z)) - z$. By the fundamental theorem of algebra, there are four roots of the equation $g(g(z)) - z = 0$, though some may be repeated.
Why are the zeroes of $g(z) - z$ solutions to $g(g(z)) = z$?
As $g(z) - z$ has distinct zeroes, call them $w_1, w_2$. As $g(w_1) - w_1 = 0$, $g(w_1) = w_1$. Therefore $g(g(w_1)) = g(w_1) = w_1$. Likewise, $g(w_2) = w_2$ and $g(g(w_2)) = w_2$.
Why must the other two roots of $g(g(z)) = z$ be $a, b$ such that $g(a) = b$ and $g(b) = a$?
Let $a$ be a zero of $g(g(z)) = z$ other than $w_1$ and $w_2$. Now let $b = g(a)$. Then $a = g(g(a)) = g(b)$ and $g(g(b)) = g(a) = b$, so $b$ is the final zero.
Why must $f(a)$ be another solution to $g(g(z)) = z$?
Note that $f(f(a)) = g(a) = b$ and $f(f(b)) = g(b) = a$ so 
$$g(g(f(a))) = g(f(f(f(a)))) = g(f(g(a))) = g(f(b)) = f(f(f(b))) = f(g(b)) = f(a).$$
To see that this is a new solution, note that $f(a) \neq w_1$ otherwise 
$$b = g(a) = f(f(a)) = f(w_1),$$ 
then 
$$f(b) = f(f(w_1)) = g(w_1) = w_1.$$ Therefore 
\begin{align*}
f(a) &= f(b)\\
f(f(a)) &= f(f(b))\\
g(a) &= g(b)\\
b &= a,
\end{align*}
which is a contradiction. Likewise, $f(a) \neq w_2$. 
If $f(a) = a$ then 
$$f(a) = a = g(g(a)) = g(f(f(a))) = g(f(a)) = g(a) = b,$$ which is a contradiction.
Finally, if $f(a) = b$ then
$$b = g(a) = f(f(a)) = f(b)$$
which leads to a similar contradiction as in the $f(a) = a$ case.
A: Michael's answer is fine, but here is a more in-depth analysis.
We want to look at the connected components of the graph whose vertices are the reals and where there is an arrow from $x$ to $y$ when $y = f^2(x) = x^2-2$.
It is clear that $f$ has to send connected components to connected components, so that given one component, either $f$ sends it onto itself (though it is not always possible), either $f$ goes back and forth with another component. Furthermore if two components are isomorphic (there is a bijective $\pi : X \to Y$ commuting with $f^2$), then we can always do so : pick $f_X = \pi$ and $f_Y = \pi^{-1} \circ f^2$.
If $|x|>2$, $x$ is among a component of the shape
$\begin{array} 
& &\cdot & & \cdot & &  \cdot & &  \cdot & \\
 &\downarrow & & \downarrow & &  \downarrow & &  \downarrow & \\
\cdots \rightarrow &\cdot &\rightarrow &\cdot &\rightarrow& \cdot& \rightarrow &\cdot \rightarrow &\cdots \end{array}$
where the top row has negative reals, the bottom row has positive reals, the limit on the left is $\pm 2$ and the limit on the right is $\pm \infty$.
There are uncountably many such components, so we can pair them up and define $f $ appropriately ($f$ can even be chosen continuous on $(-\infty ; -2) \cup (2 ; \infty)$)
For $|x| \le 2$, we have $f^2(2\cos a) = 2\cos(2a)$.  
If $a/\pi$ is irrational, $2\cos a$'s component is made of all the $2\cos(2^ka + b\pi)$ with $k \in \Bbb Z$ and $b$ a dyadic rational, and takes the form of an infinite complete binary "tree" (it's not a tree because it's infinite both ways, and there is no root). Again, there are uncountably many such components, so using the axiom of choice, we can partition them into isomorphic pairs and define a square root $f$.
Next, we have the components with rational $a/\pi$. Those have cycles.
If $(f^2)^n(x) = x$, then $(f^2)^n(f(x)) = f((f^2)^n(x)) = f(x)$, so $n$-cycles of $f^2$ have to be sent to $n$-cycles of $f^2$. Moreover, if $n$ is even, you can't send an $n$-cycle to itself, so you necessarily need another $n$-cycle in another component.
There are two (non-isomorphic) components with a $1$-cycle,
$ \cdots \rightrightarrows 0 \rightarrow -2 \rightarrow 2 \\ 
\cdots \rightrightarrows 1 \rightarrow -1  $
(with infinite complete binary trees on the left)
The first one can't be mapped to itself, but we can pair those up by $0 \rightarrow 1 \rightarrow -2 \rightarrow -1 \leftrightarrow 2$
All the other cycles component are $n$-cycles with infinite complete binary trees attached to each vertex of the cycle. And even for odd length cycles, you can't send the component to itself. In any case, you need to pair them up in order to define $f$.
It is quick to compute the numbers of cycles of length $k$ : they are all neatly embedded in $(\Bbb Z / (2^k \pm 1) \Bbb Z,\times)/\{\pm 1\}$ via the map $(x \mod m) \mapsto 2\cos(2x\pi/m)$. So we pick those two semigroups, remove every smaller-length cycle they contain, get the number of elements left, and divide by $k$ to get the number of cycles.
We get $1,2,3,6,9,18,30,\ldots$ cycles of respective length $2,3,4,5,6,7,8,\ldots$. Unfortunately, it seems we often get an odd number of cycles of a given length. Simply knowing there is only one $2$-cycle (between $2\cos{\frac{2\pi}5}$ and $2\cos{\frac{4\pi}5}$) shows that we can't define $f$ properly. 
A: There is no such $f$.
From http://yaroslavvb.com/papers/rice-when.pdf , the question of existence is determined by the theorem: 
Theorem 6. Let $\mathbb{R}$ be the real line. Let $g$ be a real quadratic polynomial, so that 
$$g(x)=ax^2+ (b + 1)x+c,$$
for all real $x$, where $a\ne 0$, $b$, and $c$ are in $\mathbb{R}$. ... set $\Delta(g)= b^2-4ac$. If $\Delta(g)> 1$, 
then g has no iterative roots of any order whatever. [That is, there is no $f$ such $f\circ f = g$.]  If $\Delta(g) =1$, then $g$ can be embedded in a 2-sided 
flow on $\mathbb{R}$, all of whose members are continuous functions. If $\Delta(g) <1$, then $g$ can be embedded in a 
1-sided flow on $\mathbb{R}$, all of whose members are continuous functions; but $g$ cannot be embedded in any 
2-sided flow on $\mathbb{R}$.
As $\Delta(g) = 0 - 4(1)(-2) = 8 > 1$ in your case, the question of existence is negative.
Looking closely at the article, the main point is that no function with only one 2-cycle can have a square root. In our case that means that there can be no partial solution $f:D\to D$ of the funcional equation $f(f(x))=x^2-2$ in $D\subset\Bbb{R}$ if $x_0=\frac{-1+\sqrt{5}}{2}\approx 0.61803$ or 
$x_2=\frac{-1-\sqrt{5}}{2}\approx -1.61803$ are in $D$. 
In fact, clearly $x_0^2-2=x_2$ and $x_2^2-2=x_0$ (this implies that $x_0\in D$ if and only if $x_2\in D$). 
There can be no other pair $y_1\ne y_2$ with $y_1^2-2=y_2$ and $y_2^2-2=y_1$, since then 
$$
\{-1,2,x_0,x_2,y_1,y_2\}
$$ 
would be roots of the polynomial $P(x)=x^4 - 4 x^2 - x + 2$, since
$y_1^2-2=y_2$ and $y_2^2-2=y_1$ implies 
$$
(y_1^2-2)^2-2=y_1\quad\Rightarrow \quad y_1^4-4y_1^2+2=y_1
\quad\Rightarrow \quad P(y_1)=0
$$
and similarly $P(y_2)=0$.
Now, if $x_0\in D$ (or $x_2\in D$) and $f:D\to D$ satisfy $f(f(x))=x^2-2$, then $x_1:=f(x_0)$ and $x_3:=f(x_2)$ would be such a pair, a contradiction that proves $x_0\notin D$ (and $x_2\notin D$).
A: Any solutions to this problem should be findable via conjugacy; the key is that the given quadratic is topologically conjugate to the 'critical' logistic map, which in turn is known to be topologically conjugate to the so-called bit shift map.  Let $f(x) = x^2-2$, $g(x) = 4x(1-x)$, $p(x) = 2-4x$.  Then we can confirm that $f(p(x)) = (2-4x)^2-2 = 16x^2-16x+2$, while $p(g(x)) = 2-4(4x(1-x)) = 16x^2-16x+2$.
But now, taking $q(x) = \sin^2(2\pi x)$, it can be shown that $g(q(x)) = q(h(x))$ on $[0,1]$, where $h(x)$ is the bit-shift map $h(x) = 2x\bmod 1$ (this works because $g(q(x))$ $= 4(\sin^2(2\pi x))(1-\sin^2(2\pi x))$ $= 4\sin^2(2\pi x)\cos^2(2\pi x)$ $= \sin^2(2\cdot 2\pi x)$, etc).
Now, suppose we have a 'functional square root' $H(x)$ of the bit-shift map; that is, a function $H(x)$ such that $H(H(x)) = h(x)$.  Then by 'chasing the chain' of conjugacies, we can turn this into a functional square root $F(x)$ of the original $f()$: letting $r = p\circ q$ (that is, defining $r(x) = p(q(x))$) we have $f\circ r=r\circ h$, so $f = r\circ h\circ r^{-1}$..  But then setting $F=r\circ H\circ r^{-1}$ we get $F\circ F = r\circ H\circ r^{-1}\circ r\circ H\circ r^{-1} = r\circ H\circ H\circ r^{-1} = r\circ h\circ r^{-1} = f$.
The problem thus reduces to finding an $H$ such that $H\circ H(x)=h(x) = 2x\bmod 1$.  For $x$ in a limited range (e.g., $x\lt \frac12$ — and I haven't translated back to see what interval of the original problem this represents), we can simply take $H(x) = \sqrt{2}x$ as a solution, but this piecewise-linear behavior can't be extended to the whole of $[0,1]$: requiring $H(x) = \sqrt{2}x$ on $x\lt\frac12$ implies that it must in fact be true for $x\lt\frac1{\sqrt{2}}$ so that $H(H(x)) = 2x$ for all $x\lt\frac12$; but now consider $x=\frac12+\epsilon$, which then yields $H(H(x))$ $= H(\frac1{\sqrt{2}}+\sqrt{2}\epsilon)$ $=2\epsilon$, and then $H(H(\frac1{\sqrt{2}}+\sqrt{2}\epsilon))$ $= H(2\epsilon)$ $= 2\sqrt{2}\epsilon$, contradicting the requirement that $H(H(\frac1{\sqrt{2}}+\sqrt{2}\epsilon))$ $=h(\frac1{\sqrt{2}}+\sqrt{2}\epsilon)$ $=\sqrt{2}-1+2\sqrt{2}\epsilon$.  This argument might be extendible to show there are no piecewise-continuous solutions outside a specific range, but that's well beyond my ken.
A: We are looking for maps $f$ satisfying $$f\circ f=h\ ,\tag{1}$$ where $h$ is given by
$$h:\quad x\mapsto h(x):=x^2-2\ .$$
The map $h$ has the two fixed points $p=-1$, $q=2$ with $h'(p)=-2$, $h'(q)=4$.
Writing $x=2+t$ with a new coordinate $t$ the map $h$ assumes the form $$h:\ t\mapsto 4t+t^2\ .\tag{2}$$
By Koenig's theorem (see John Milnor: Dynamics in one complex variable, Theorem 8.2) one can replace $t$ in the neighborhood of $t=0$ by a new local variable $\tau=\phi(t)$ such that $h$ now appears as
$$h:\quad \tau\mapsto 4\tau\ .$$
Coming back to $f$ there might be solutions of $(1)$  with $f(2)=c\ne2$, $f(c)=2$. In any case  we now can look for solutions $f$ for which $2$ is a fixed point as well. In terms of the variable $\tau$ these would satisfy
$$f\bigl(f(\tau)\bigr)\equiv4\tau\ ,\tag{3}$$
and it should not be difficult to show that the only analytical solutions to $(3)$ are $f(\tau)=\pm 2\tau$. When we want $f$ in terms of $t$ we have to write
$$f(t):=\pm2t+\sum_{k=2}^\infty a_k t^k$$ and to determine the coefficients $a_k$ from $(2)$, i.e. using
$$f\bigl(f(t)\bigr)\equiv 4t + t^2\ .$$
A similar analysis can be done with the fixed point $p=-1$ of $h$. There we would  write $x=-1+t$ and obtain two $f$'s of the form
$$f(t)=\pm \sqrt{2} i\> t +{\rm higher\ terms}\ .$$
A: The solution that I have seen, I think due to John Horton Conway, is 
$$f(x) = 2 \cos\Big(\sqrt2 \arccos\frac x2\Big)$$
This was alleged to work for $-2\leqslant x\leqslant 2$.
$$\begin{align*}
f(f(x))&= 2 \cos\Big(\sqrt2 \arccos\frac12\Big(2 \cos\big(\sqrt2 \arccos\frac x2\big)\Big)\Big)\\
&= 2 \cos\Big(\sqrt2 \arccos\cos\big(\sqrt2 \arccos\frac x2\big)\Big)\\
&= 2 \cos\Big(\sqrt2 \sqrt2 \arccos\frac x2\Big)\\
&= 2 \cos\Big(2 \arccos\frac x2\Big)\\
&= 2\Big(2 \cos^2\arccos\frac x2- 1\Big)    \qquad{[\cos 2\theta=2\cos^2\theta-1]}\\
&= 2\Big(2\Big(\frac x2\Big)^2- 1\Big)\\
&= 2(x^2/2 - 1)\\
&=x^2- 2
\end{align*}$$
It looks right, but, as I discovered many years later when trying to draw the graphs of $f(x)$ and $f(f(x))$, it isn't. The problem is that $\arccos\theta$ isn't single-valued, so the simplification of
$\arccos\cos(\sqrt2 \arccos(x/2))$ to $\sqrt2 \arccos(x/2)$ isn't valid. You have to choose a branch of $\arccos\theta$, and it isn't possible to consistently choose a branch which makes it work over the domain specified. In fact, if we impose the reasonable restrictions:-


*

*$f(x)$ has to be continuous

*for some domain $D$ of $x$, if $x\in D$, $f(x)\in D$


then it impossible to pick a domain of $x$ for which the solution given above works. I believe that with these restrictions there is no solution at all.
If you don't require the domain of $x$ to be continuous,
$$f(x) = 2 \cosh\Big(\sqrt2 \operatorname{arccosh}\frac{|x|}2\Big)$$
works for $|x|\geqslant 2$. Of course $\operatorname{arccosh}\theta$ isn't single-valued either, but it doesn't matter which branch you choose because $\cosh \theta = \cosh -\theta$. For $|x| < 2$, $\operatorname{arccosh} x/2$ is undefined, so $f(x)$ isn't defined over this domain either.
