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.
On
Hmm, if we look at $g(x) = f(f(x)) = x^2-2$ and find the fixpoints $t_0=-1,t_1=2$ then we might assume a solution $h(x)$ for $g(x) = h(x-2)+2 $ and then from this we search for the half-iterate of $h(x)$ defining $h(x-2)+2 = w(w(x-2))+2$ and shall have a solution of the problem by $f(x)=w(x+2)-2$, hopefully having nonzero range of convergence at least in the vicinity of the fixpoint $t_1$.
With this ansatz we find that $$h(x) = g(x+2)-2 = (x+2)^2-4 = 4x+1x^2$$ could be a replacement for $g(x)$ and from this we get the leading terms for the power series of its half-iterate $$w(x) = 2 x + 1/6 x^2 - 1/90 x^3 + 1/720 x^4 - 7/32400 x^5 \\ + 161/4276800 x^6 - 391/55598400 x^7 + O(x^8) $$ by standard algebraic manipulations. (To check this insert $w(x)$ for $x$ in that leading terms)
Thus $f(x)$ can be written as a power series around (fixpoint) $2$: $$f(x) = 2+ 2 (x-2) + 1/6 (x-2)^2 - 1/90 (x-2)^3 + 1/720 (x-2)^4 - 7/32400 (x-2)^5 \\ + 161/4276800 (x-2)^6 - 391/55598400 (x-2)^7 + O(x^8) $$ (The link gives a confirmation using WolframAlpha and a $\cosh()$ /$\text{arccosh}()$-formula, see my other answer)
By the first $64$ terms it looks as if $w(x)$ has a positive range of convergence; and computing a couple of examples gives $$ \begin{array} {c|c|c|c} x &g(x)=h(1-t_1)+t_1 & f(x) = w(x-t_1)+t_1 & f(f(x))=w(w(x-t_1))+t_1\\ \hline\\ 1 & -1 & 0.17942912356439677341 & -1.0 \\ 1.5 & 0.25 & 1.0431497617870845281 & 0.25 \\ 2.5 & 4.25 & 3.0403583699367069623& 4.25 \\ \end{array}$$ while the results for $f(x)$ are only (but well) approximated because I've only the truncation to say 32 or 64 terms so far and not yet an analytical description for the coefficients which only would allow an exact result.
More Explanations
1) Generalities (Remark: $f(x)$ is meant here in general, not yet your sought function)
There is consent (see for instance L. Comtet, "Advanced Combinatorics", pg 144-148) that for power series without constant term there is a meaningful fractional iterate using the Bell-polynomials based on the formal power series for the function. One can express this more elegantly and concise in terms of Bell/Carleman matrixes (see wikipeda but for convenience I use the Carleman matrix here in transposed form) , which have a form such that for a function $f(x)$ we have $$ V(x) \cdot B = V(f(x)) \\ V(x) \cdot B^2 = V(f(f(x))) \\ \cdots\\ V(x) \cdot B^n = V(f^{[n]}(x)) \\ $$ where the notation $V(x)=[1,x,x^2,x^3,...]$ and thus $V(f(x))=[1,f(x),f(x)^2,f(x)^3,...]$ means infinite vectors of an indeterminate argument $x$.
This notation allows to isolate the required coefficients of the power series of $f(x)$ into the (infinite, lower triangular) matrix $B$ . Then for the operation of composition and self-composition (aka iteration) via the Bell-polynomials it suffices to denote powers of the matrix $B$ - because they implicitely define that required Bell-polynomial driven operations on the formal powerseries .
If the power series for $f(x) = \sum_{k=1}^\infty b_k\cdot x^k$ has no constant term, then the associated Bell-/Carleman-matrix is lower triangular, and powers of it can be computed also on the finitely truncated versions - giving exact coefficients which are valid also for the untruncated/infinite-size case.
Moreover this is also possible for fractional powers, and in particular for the square-root, which provides then the solution that you are searching.
2) How this concerns your problem (here $f(x)$ means your function)
The procedure is now to find an equivalent power series (or polynomial) for your function (let's call it $g(x)=f(f(x))$) which has no constant term - by shifting the $x$ and $y$-coordinate, such that $g(x) = x^2-2 $ which has a constant term, is rewritten as $h(x) = 4x + x^2$ which has no constant term and then we have modeled for any number of iterations $$g(x) = h(x-2) + 2 \\ g(g(x)) = h(h(x-2))+2 \\ \cdots$$.
Then for the function $h(x)$ we build the (lower triangular) Carleman-matrix $H$ which begins as $$ H= \small \begin{bmatrix} 1 & . & . & . & . & . \\ 0 & 4 & . & . & . & . \\ 0 & 1 & 16 & . & . & . \\ 0 & 0 & 8 & 64 & . & . \\ 0 & 0 & 1 & 48 & 256 & . \\ 0 & 0 & 0 & 12 & 256 & 1024 \end{bmatrix} \qquad \text{ matrix H is of infinite size} $$ and obviously the dot product with a $V(x)$-vector evaluates then to a $V(h(x))$-vector: $$ V(x) \cdot H = V(h(x))$$
Then the squareroot (let's call it $W$) of $H$ such that $W^2 = H$ can be determined by solution of an infinite equation system or by diagonalization.
One solution is again lower triangular and instead of a polynomially function like $h(x)$ it provides the coefficients of a power series. It begins like
$$ W = \small \begin{bmatrix}
1 & . & . & . & . & . \\
0 & 2 & . & . & . & . \\
0 & 1/6 & 4 & . & . & . \\
0 & -1/90 & 2/3 & 8 & . & . \\
0 & 1/720 & -1/60 & 2 & 16 & . \\
0 & -7/32400 & 1/540 & 1/30 & 16/3 & 32
\end{bmatrix} \qquad \text{ matrix W is of infinite size}$$
(You can check it by hand when you compute the square of W)
The second column gives the coefficients for the power series of $w(x)$ with the property $w(w(x-2))+2 = g(x)$ and thus gives an acceptable solution $f(x)=w(x-2)+2$.
Additional remark: Often with fractional iterates the occuring power series have very small or zero range of convergence - then additional measures must be introduced to make the solution usable and meaningful, but the powerseries for $w(x)$ here seems to have a convergence-radius of about $4$ and can be used for a not-too-small range of $x$ -values.
On
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.
On
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$).
On
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.
On
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}\ .$$
On
There is another way to arrive by a meaningful generalization to a result. (Btw., this is essentially the same result which I got using the Carlemanmatrix; if we recenter the function $w(x)$ of my previous posting we get $f(x)$ with all displayed digits correct.)
The resulting function has the following power series: $$ f(x) = -1.21139973416 + 1.12528011714 x + 0.302849933539 x^2 - 0.0468866715477 x^3 + 0.0126187472308 x^4 - 0.00410258376042 x^5 + 0.00147218717693 x^6 - 0.000561663252915 x^7 + O(x^8) \\ f(f(x)) = -2 + x^2 $$
The key here is to observe, that the basic function $g_2(x)=-2 + x^2$ is a rescaled Chebychev-polynomial $T_2(x)$ such that $g_2(x) = 2 \cdot T_2(x/2)$
Now the iterates of $g_2^{\circ h} (x)$ are in a similar way as the Chebychev-polynomials expressible by the composition
$$ g_2(x) = 2 \cdot \cosh(2 \cdot \mathrm{arccosh}(x/2)) $$
and the h'th iterate
$$ g_2^{\circ h}(x) = 2 \cdot \cosh(2^h \cdot \mathrm{arccosh}(x/2)) $$
This composition allows a natural extension to the fractional iteration heights h; using $h=1/2$ we get
$$ \begin{array} {llll} g_2^{\circ 1/2}(x) &=& f(x) \\ &=& -1.21139973416 + 1.12528011714 x + 0.302849933539 x^2 \\ & & - 0.0468866715477 x^3 + 0.0126187472308 x^4 - 0.00410258376042 x^5 \\ & & + 0.00147218717693 x^6
- 0.000561663252915 x^7 + O(x^8) \\ & & \text{ and }\\
f(f(x)) &=& -2 + x^2 \end{array} $$
Of course we have to reflect restrictions for the domain. If we work only over the reals then we have because of the inner arccosh-function $ x \in (2,\infty) $. However, if we extend the domain to complex numbers this can be extended. (While multivaluedness might then occur - I don't have the exact description at hand yet, Pari/GP which has complex arithmetic builtin works with the complete disk around the complex origin.)
On
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:-
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.
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.
(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.