How to solve f(f(x)) = cos(x) ? - MathOverflow

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

2010-03-09T14:30:05Z

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)$ ?

Answer by Gerald Edgar for How to solve f(f(x)) = cos(x) ?

2010-03-09T14:47:30Z

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

Answer by HenrikRüping for How to solve f(f(x)) = cos(x) ?

2010-03-09T14:50:35Z

If you assume, that $f$ can be written as a power series, lets say $f(x)=\sum_i a_ix^i$ (and the power series converges everywhere absolutely), then one can write down a power series for $f\circ f$, where the i-th coefficient is a polynomial in the lower coefficients. Comparing the coefficients of this power series to the one of $cos$, we have to solve a system of algebraic equations (which might lead to the disambiguity). This is just a first idea from a non expert.

Answer by Dmytro Yeroshkin for How to solve f(f(x)) = cos(x) ?

2010-03-09T15:01:37Z

Henrik's idea is good, but it doesn't quite work for $\cos x$ since the power series must have a non-zero leading term, and so can't be substituted into a power series. To fix this, consider a power series about a root of $\cos x$, for example $f(x) = \sum_i a_i (x-\pi/2)^i$ with $a_0=0$.

Answer by Joel David Hamkins for How to solve f(f(x)) = cos(x) ?

2010-03-09T15:10:48Z

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.

Answer by Sergei Ivanov for How to solve f(f(x)) = cos(x) ?

2010-03-09T18:55:56Z

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.

Answer by asmaier for How to solve f(f(x)) = cos(x) ?

2010-03-09T23:15:04Z

About literature related to the topic of this question:

In the answer to the question f(f(x))=exp(x)-1 and other functions “just in the middle” between linear and exponential. one can find an interesting link with many references related to the problem:

Lars Kindermann: Iterative Roots and Fractional Iteration

There is also Kindermanns PhD thesis about finding solutions to iterative functional equations using a neural network (in german only)

Kindermann(2001): Neuronale Netze zur Berechnung Iterativer Wurzeln und Fraktionaler Iterationen

which might be helpful.

Answer by asmaier for How to solve f(f(x)) = cos(x) ?

2010-03-11T13:19:00Z

Joels answer made me think a bit and I believe I found an interesting solution for $f(x)$ :

$ f(x) = \begin{cases} ix & \text{if } Im(x) = 0, x\neq 0 \\ \cos(ix) & \text{if } Re(x) = 0,x \neq 0 \\ 2\pi i & \text{if } x = 0 \end{cases}$

It is of course a bit of a trick (reminds me of Wick Rotation), but I it works for all $x\ \epsilon\ R$, because

$f(f(x)) = \cos(i(ix))=\cos(-x) = \cos(x)$

Update: Added the case $x=0$. For this we have

$f(f(0)) = \cos(i(2\pi i))=\cos(-2\pi) = \cos(0)$

Answer by Anixx for How to solve f(f(x)) = cos(x) ?

2010-11-03T20:58:44Z

This answer has been deleted for the first time, so this is a re-post. The first answer also had an error in the plot. Since the questioner asked the following question "Is there a general solution strategy to equations of this kind?" I'll try to respond.

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