How to solve f(f(x)) = cos(x) ? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T22:13:19Z http://mathoverflow.net/feeds/question/17605 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/17605/how-to-solve-ffx-cosx How to solve f(f(x)) = cos(x) ? asmaier 2010-03-09T14:30:05Z 2012-05-31T11:15:13Z <p>I found the following interesting equation on some web page I cannot remember:</p> <p>$f(f(x))=\cos(x)$</p> <p>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</p> <p>$f(f(x)) = x$</p> <p>which has for example the solutions $f(x) = x$ or $f(x) = \frac{x+1}{x-1}$. </p> <p>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)$ ?</p> http://mathoverflow.net/questions/17605/how-to-solve-ffx-cosx/17607#17607 Answer by Gerald Edgar for How to solve f(f(x)) = cos(x) ? Gerald Edgar 2010-03-09T14:47:30Z 2010-03-09T14:47:30Z <p>Near a fixed point of cos(x) use the method of Schr"oder (1871) ...<br> <a href="http://en.wikipedia.org/wiki/Schr%C3%B6der%27s_equation" rel="nofollow">http://en.wikipedia.org/wiki/Schr%C3%B6der%27s_equation</a> </p> <p>Best historical reference: Daniel S. Alexander, <em>A History of Complex Dynamics from Schr"oder to Fatou and Julia</em> (1994).</p> http://mathoverflow.net/questions/17605/how-to-solve-ffx-cosx/17609#17609 Answer by HenrikRüping for How to solve f(f(x)) = cos(x) ? HenrikRüping 2010-03-09T14:50:35Z 2010-03-09T14:50:35Z <p>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.</p> http://mathoverflow.net/questions/17605/how-to-solve-ffx-cosx/17611#17611 Answer by Dmytro Yeroshkin for How to solve f(f(x)) = cos(x) ? Dmytro Yeroshkin 2010-03-09T15:01:37Z 2010-03-09T15:01:37Z <p>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$.</p> http://mathoverflow.net/questions/17605/how-to-solve-ffx-cosx/17613#17613 Answer by Joel David Hamkins for How to solve f(f(x)) = cos(x) ? Joel David Hamkins 2010-03-09T15:10:48Z 2010-03-09T15:10:48Z <p>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. </p> <p>Specifically, I claim that if g:[a,b] to R, then there are 2<sup>|R|</sup> many functions f from R to R with f(f(x)) = g(x) for all x in [a,b].</p> <p>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).</p> <p>When g is continuous, then this function f will be continuous also, and can be made total by linearly extending.</p> <p>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<sup>-1</sup>(x)) for x in [a',b']. It follows that f(f(x)) = g(x). And since there are 2<sup>|R|</sup> many such functions h, there are similarly many functions f satisfying the equation.</p> http://mathoverflow.net/questions/17605/how-to-solve-ffx-cosx/17639#17639 Answer by Sergei Ivanov for How to solve f(f(x)) = cos(x) ? Sergei Ivanov 2010-03-09T18:55:56Z 2010-03-09T21:04:02Z <p>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.</p> <p>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.</p> <p>UPDATE: Here is how to construct a solution (this is technical and I might overlook something).</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/17605/how-to-solve-ffx-cosx/17669#17669 Answer by asmaier for How to solve f(f(x)) = cos(x) ? asmaier 2010-03-09T23:15:04Z 2010-03-09T23:15:04Z <p>About literature related to the topic of this question:</p> <p>In the answer to the question <a href="http://mathoverflow.net/questions/4347/ffxexpx-1-and-other-functions-just-in-the-middle-between-linear-and-expo/4423#4423" rel="nofollow">f(f(x))=exp(x)-1 and other functions “just in the middle” between linear and exponential.</a> one can find an interesting link with many references related to the problem:</p> <ul> <li><a href="http://reglos.de/lars/ffx.html" rel="nofollow">Lars Kindermann: Iterative Roots and Fractional Iteration</a></li> </ul> <p>There is also Kindermanns PhD thesis about finding solutions to iterative functional equations using a neural network (in german only)</p> <ul> <li><a href="http://archiv.tu-chemnitz.de/pub/2002/0154/index.htm" rel="nofollow">Kindermann(2001): Neuronale Netze zur Berechnung Iterativer Wurzeln und Fraktionaler Iterationen</a></li> </ul> <p>which might be helpful.</p> http://mathoverflow.net/questions/17605/how-to-solve-ffx-cosx/17856#17856 Answer by asmaier for How to solve f(f(x)) = cos(x) ? asmaier 2010-03-11T13:19:00Z 2010-03-11T14:26:54Z <p>Joels answer made me think a bit and I believe I found an interesting solution for $f(x)$ :</p> <p>$f(x) = \begin{cases} ix &amp; \text{if } Im(x) = 0, x\neq 0 \\ \cos(ix) &amp; \text{if } Re(x) = 0,x \neq 0 \\ 2\pi i &amp; \text{if } x = 0 \end{cases}$</p> <p>It is of course a bit of a trick (reminds me of <a href="http://en.wikipedia.org/wiki/Wick_rotation" rel="nofollow">Wick Rotation</a>), but I it works for all $x\ \epsilon\ R$, because</p> <p>$f(f(x)) = \cos(i(ix))=\cos(-x) = \cos(x)$</p> <p>Update: Added the case $x=0$. For this we have</p> <p>$f(f(0)) = \cos(i(2\pi i))=\cos(-2\pi) = \cos(0)$</p> http://mathoverflow.net/questions/17605/how-to-solve-ffx-cosx/44727#44727 Answer by Anixx for How to solve f(f(x)) = cos(x) ? Anixx 2010-11-03T20:58:44Z 2011-07-30T03:22:00Z <p>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.</p> <p>The half-iterate of a function can be found by expressing its superfunction in a form of Newton series:</p> <p>$$f^{[1/2]}(x)=\sum_{m=0}^{\infty} \binom {1/2}m \sum_{k=0}^m\binom mk(-1)^{m-k}f^{[k]}(x)$$</p> <p>Where $f^{[k]}(x)$ means k-th iterate of $f(x)$ This series converges if two criteria are met:</p> <p>1) The superfunction of f(x) grows not faster than an exponent</p> <p>2) <a href="http://en.wikipedia.org/wiki/Runge_phenomenon" rel="nofollow">Runge phenomenon</a> does not appear.</p> <p>There is a <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.148.4870&amp;rep=rep1&amp;type=pdf" rel="nofollow">number of strategies to combat Runge phenomenon</a> 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.</p> <p>Opposite case is with the function $f(x)=\sin x$. The superfunction is limited by $\pm 1$ and the series converges without any problem.</p> <p>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.</p> <p><img src="http://storage8.static.itmages.ru/i/11/0727/h_1311791669_284ac40d42.png" alt="alt text"></p> <p>This plot is made from the first 50 terms of the above series.</p> <p>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.</p> <p>The formula can be also written in the following forms:</p> <p>$$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)$$</p> <p>$$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)!}}$$</p> <p>There are also some other formulas giving the same result.</p>