How to solve $f(f(x)) = \cos(x)$?

I found the following interesting equation on some web page I cannot remember:

$f(f(x))=\cos(x)$

Out of curiosity I tried to solve it, but realized that I do not have a clue how to approach such an iterative equation except for trial and error. I also realized that the solution might not be unique, from the solution of a simpler problem

$f(f(x)) = x$

which has for example the solutions $f(x) = x$ or $f(x) = \frac{x+1}{x-1}$.

Is there a general solution strategy to equations of this kind? Can you perhaps point me to some literature about these kind of equations? And what is the solution for $f(f(x))=\cos(x)$ ?

• Are you looking for continuous solutions or arbitrary maps? – Sergei Ivanov Mar 9 '10 at 17:49
• There is a collection of references and links for the general problem of solving $f(f(x))=g(x)$ for $f$, given $g$, at reglos.de/lars/ffx.html – Gerry Myerson Mar 9 '10 at 23:02
• After Sergey Ivanov's solution, I wonder how many discontinuity points a solution of $f(f(x)) = \cos(x)$ must have? – Anonymous Mar 10 '10 at 1:22
• Sergei's impossibility argument only applies to real functions, right? (Because it uses monotonicity.) Cosine is a perfectly healthy complex function, so you could ask the same question in the complex setting. As far as I can tell no one has answered that version of the question conclusively yet. – Noah Snyder May 29 '12 at 3:48
• @Noah: for complex solution, see my reply mathoverflow.net/questions/17605/how-to-solve-ffx-cosx/… – Gerald Edgar May 29 '12 at 11:57

The half-iterate of a function can be found by expressing its superfunction in a form of Newton series:

$$f^{[1/2]}(x)=\sum_{m=0}^{\infty} \binom {1/2}m \sum_{k=0}^m\binom mk(-1)^{m-k}f^{[k]}(x)$$

Where $f^{[k]}(x)$ means k-th iterate of $f(x)$ This series converges if two criteria are met:

1) The superfunction(flow) of f(x) grows not faster than an exponent

2) Runge phenomenon does not appear.

There is a number of strategies to combat Runge phenomenon which are outside of this answer's scope. It is worth noting though that trying to find a half iterate of the function $f(x)=\cos x$ leads to this Runge swamp and one needs to employ one of the mentioned techniques to acheve convergence.

Opposite case is with the function $f(x)=\sin x$. The superfunction is limited by $\pm 1$ and the series converges without any problem.

Below is a plot of half-iterate of $\sin x$, obtained with this formula. It is periodic with the same period as $\sin x$. The blue curve is the half-iterate, and the red curve is the half-iterate, repeated twice, and we can see that it is indeed very similar to sine function. This plot is made from the first 50 terms of the above series.

This formula for the half-iterate can be used to find not only half-itertes but any real (or even complex!) iterate of a function by substituting the needed value instead of 1/2.

The formula can be also written in the following forms:

$$f^{[s]}(x)=\lim_{n\to\infty}\binom sn\sum_{k=0}^n\frac{s-n}{s-k}\binom nk(-1)^{n-k}f^{[k]}(x)$$

$$f^{[s]}(x)=\lim_{n\to\infty}\frac{\sum_{k=0}^{n} \frac{(-1)^k f^{[k]}(x)}{(s-k)k!(n-k)!}}{\sum_{k=0}^{n} \frac{(-1)^k }{(s-k) k!(n-k)!}}$$

There are also some other formulas giving the same result.

• This is a truly great answer. But you use"Newton series" and "superfunction" in a way that will be misleading. By the "Newton series" you mean expansion of (1+x)^(1/2) in powers of x, not "Newton's iteration method", which is how some people read it. By "Superfunction" you mean an abstract iteration operator which when applied to functions composes them with other functions. This formula is a little hard to make precise. – Ron Maimon Jul 30 '11 at 6:19
• Newton series is the following series: $$f(x) = \sum_{k=0}^\infty \binom{x-a}k \Delta^k f\left (a\right)$$ It is equivalent to the above formula (just expand the deltas). Wikipedia: en.wikipedia.org/wiki/Finite_difference#Newton_series – Anixx Jul 30 '11 at 6:47
• A frustrating aspect of this construction is $f^{}(x) = x.$ The infinite sum of all the coefficients of $x$ is 0. This must be true, $\sin x$ is periodic. The partial sum of a finite number of terms gives a nonzero coefficient for $x.$ This nonzero coefficient is necessary for uniform convergence on, say, the interval $(0,\pi - \varepsilon), \; \varepsilon > 0.$ On the other hand, by the time we have, say, $x > 2 \pi,$ the nonzero coefficient on $x$ itself (where all the other terms are periodic functions of $x$) makes matters worse, the partial summed function increases without bound. – Will Jagy Jul 30 '11 at 20:22
• One can take the sum not from k=0 but from k=1. The limit will be the same, and the coefficient of x will be zero. But this will also converge very slowly. – Anixx Jul 30 '11 at 21:26
• This is like Taylor series. To get a function you do not necessary have to make the series around zero point, you can take any point if you know derivatives of higher orders there (and we can find the differences of higher order not only in 0 bus in 1 as well). – Anixx Jul 30 '11 at 21:54

There are no continuous solutions. Since the cosine has a unique fixed point $x_0$ (such that $\cos x_0=x_0$), it should be a fixed point of f. And f should be injective and hence monotone (increasing or decreasing) in a neighborhood of $x_0$. Then f(f(x)) is increasing in a (possibly smaller) neighborhood of $x_0$ while the cosine is not.

As for discontinuous ones, there are terribly many of them ($2^{\mathbb R}$) and you probably cannot parametrize them in any reasonable way. You can describe them in terms of orbits of iterations of $\cos x$, but I doubt this would count as a solution of the equation.

UPDATE: Here is how to construct a solution (this is technical and I might overlook something).

Let X be an infinite set and $g:X\to X$ is a map, I am looking for a sufficient conditions for the existence of a solution of $f\circ f=g$. Define the following equivalence relation on X: x and y are equivalent iff $g^n(x)=g^m(y)$ for some positive integers m and n. Equivalence classes will be referred to as orbits (the term is wrong but I don't know what is a correct one). Two orbits are said to be similar is there is a bijection between them commuting with g. If Y and Z are two similar orbits, one can define f on $Y\cup Z$ as follows: on Y, f is that bijection to Z, and on Z, f is the inverse bijection composed with g.

So if the orbits can be split into pairs of similar ones, we have a desired f. Now remove from the real line the fixed point of cos and all its roots ($\pi/2$ and the like). Then, if I am not missing something, in the remaining set X all orbits of cos are similar, so we can define f as above. Define f so that 0 has a nonempty pre-image (that is, the orbit containing 0 should be used as Z and not as Y). Finally. map the fixed point of cos to itself, and the roots of cos to some pre-image of 0.

• Sergei: how can you see there exists a discontinuous solution? what formal properties of cos(x) do you need to come to this conclusion? – Kevin Buzzard Mar 9 '10 at 19:20
• Im confused as to why x_0 must be a fixed point of f. Can't it be an involution (order two) point of f? – Ben Weiss Mar 9 '10 at 21:06
• @Ben: then there will be two fixed points of $f\circ f$. – Sergei Ivanov Mar 9 '10 at 21:09
• since $f$ is continuous, if it has no fixed point you have e.g. $f(x)>x$ for all $x$, and thus $g(x)>x$ also. – Homology Apr 30 '10 at 10:20
• See my new answer. – Anixx May 29 '12 at 3:10

There are a truly enormous number of solutions, if one only wants the solution to work on an interval. Indeed, one can find solutions to f(f(x)) = g(x) for any function g defined on an interval.

Specifically, I claim that if g:[a,b] to R, then there are 2|R| many functions f from R to R with f(f(x)) = g(x) for all x in [a,b].

One such solution f is obtained as follows. First choose a z such that [a,b] and [a + z, b + z] are disjoint. Now let f(x) = x + z, for x in [a,b], and f(x) = g(x - z), for x in [a + z, b + z]. Thus, f(x) first translates x to another interval, when x is in [a,b], and then f computes g of the reverse translate, when x is not in [a,b]. So f(f(x)) = g(x).

When g is continuous, then this function f will be continuous also, and can be made total by linearly extending.

More generally, if h is bijection of [a,b] with another interval [a',b'] disjoint from [a,b], then let f(x) = h(x) for x in [a,b], and f(x) = g(h-1(x)) for x in [a',b']. It follows that f(f(x)) = g(x). And since there are 2|R| many such functions h, there are similarly many functions f satisfying the equation.

• OK but I don't see how to generalise this trick so that it works for all x in the reals. – Kevin Buzzard Mar 9 '10 at 15:33
• I've just asked an explicit question about this: mathoverflow.net/questions/17614/solving-ffxgx – Kevin Buzzard Mar 9 '10 at 15:43
• Can you please show us a plot of a solution for cosine on interval say $[-\pi/2,\pi/2]$? – Anixx Aug 23 '11 at 23:44
• Anixx, I could give you a plot, but I think you can get the idea without one. (Or you could make a plot.) The function $f$ is the straight line $y=x+z$ on the interval $[a,b]$, with $z$ constant. This maps the interval $[a,b]$ to $[a+z,b+z]$. On this interval, the function $f$ looks exactly like $g$ does on $[a,b]$, but translated by $z$. Thus, the function $f$ applied once moves you from $[a,b]$ to $[a+z,b+z]$, and applied again, gives you the result of $g$. So $f\circ f=g$ on the interval $[a,b]$, as desired. – Joel David Hamkins Aug 24 '11 at 21:50
• Sorry if I'm misunderstanding this: You said "When g is continuous, then this function f will be continuous also", but the answer with the most upvotes claims that there is no continous solution. – Ovi Jun 25 '17 at 4:34

Near a fixed point of cos(x) use the method of Schr"oder (1871) ...
http://en.wikipedia.org/wiki/Schr%C3%B6der%27s_equation

Best historical reference: Daniel S. Alexander, A History of Complex Dynamics from Schr"oder to Fatou and Julia (1994).

It seems that contrary to some other answers a continuous solution can be constructed.

First of all we interpolate with Newton series the flow of function $\cos(\cos(z))$:

$$\phi_{1/2}(x,z)=\cases { \arccos^{[x]}(z), & \text{if } x < 0 \cr \cos^{[x]}(z), & \text{if } x \ge 0 }$$

$$\phi_{1}(x,z)=\sum_{m=0}^\infty \binom{x/2+1}{m} \sum_{k=0}^m (-1)^{k-m} \binom{m}{k} \phi_{1/2}(k-1,z)$$

We interpolate from the first integer point where the value is real, i.e. from x=-1.

We now obtain the approximation of the other half-flow of cos x by taking arccos on the above function:

$$\phi_{2}(x,z)=\arccos(\phi_{1}(x+1,z))$$

We know that the flow of cos(x) should coincide with the first function in even integers and with the second function in odd integers.

So we make a stub of the flow following this knowledge (we also want that its absolute value to be monotonous).

$$\phi(x,z)=\frac{1}{2} \left((-1)^{x+1}+1\right) (\phi_{1}(x,z)-\text{FP})+\frac{1}{2} \left((-1)^x+1\right) (\phi_{2}(x,z)-\text{FP})+\text{FP}$$

where FP is the cosine fixed point.

This function coincides with the flow in integer points but still disagrees in between. To get a real flow we have to take a limit of repeated arccosine on the our stub:

$$\Phi(x,z)=\lim_{n\to\infty} \arccos^{[n]} (\phi(x+n,z))$$

Numerically this limit converges quite fast. If the limit exists, it by definition, satisfies the equation

$$\cos(\Phi(x,z))=\Phi(x+1,z)$$

so it is the true flow.

The above can be illustrated by the graphic: Here upper semi-flow (flow of cos(cos z)) ) is blue, lower semi-flow is red, real part of the flow is yellow, imaginable part of the flow is green. All flows are taken as point z=1.

Following this we can build a graphic of half-iterate of cosine $\Phi(1/2,z)$: Here blue is the real part and red is the imaginary part.

We can verify that the half-iterate repeated twice $\Phi(1/2,\Phi(1/2,z))$ (blue) follows cosine (red) quite well at positive half-periods, and anywhere the cone is positive (that is, on the imaginary axis as well): I think this coincodes with the answer by Gerald Edgar above. A modified function, iterated twice gives cosine in all real axis: This is a true half-iterate of cosine, which works on the whole real axis, producing exactly cosine: But as has been noted by Joel David Hamkins above, there is infinite number of such solutions, none of which work for the whole complex numbers.

This function can be considered though as the true solution on the complex plane if interpreted as a multi-valued function. To do this, take the function on the each interval and analytically extend it to the whole complex plane.

A mathematica notebook that produces the above is as follows: