When does the sequence of iterates of a rational function converge? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T03:27:39Z http://mathoverflow.net/feeds/question/155 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/155/when-does-the-sequence-of-iterates-of-a-rational-function-converge When does the sequence of iterates of a rational function converge? 20 questions 2009-10-06T22:05:32Z 2012-08-26T11:44:58Z <p><a href="http://math.berkeley.edu/~dranjan/" rel="nofollow">Darsh</a> asks at the 20-questions seminar:</p> <p>Let <code>f:P^1 -&gt; P^1</code> be rational function.</p> <p>Can you say when the sequence <code>{f^n(x)}_n = {x, f(x), f(f(x)), ...}</code> converges? What about the sequence of averages <code>{1/(n+1) \sum_i=0^n f^i(x)}_n</code>? Anything else?</p> http://mathoverflow.net/questions/155/when-does-the-sequence-of-iterates-of-a-rational-function-converge/630#630 Answer by Michael Lugo for When does the sequence of iterates of a rational function converge? Michael Lugo 2009-10-15T18:49:24Z 2009-10-15T18:49:24Z <p>Consider a Mobius transformation f := z -> (az+b)/(cz+d) which rotates the Riemann sphere by an angle theta, where theta/Pi is not rational. Then the sequence of iterates of f is not periodic. But iterating f gives values which are uniformly distributed and dense on a certain circle on the Riemann sphere. Change coordinates back to the plane and I suspect the sequence of averages converges to the mean value on that circle. I haven't actually done the computation, though.</p> http://mathoverflow.net/questions/155/when-does-the-sequence-of-iterates-of-a-rational-function-converge/685#685 Answer by jc for When does the sequence of iterates of a rational function converge? jc 2009-10-15T23:27:29Z 2009-10-15T23:27:29Z <p>I haven't really studied complex dynamics much, but here's a suggestion for the general case:</p> <p>In the Fatou set of f, you should use Sullivan's <a href="http://en.wikipedia.org/wiki/Classification%5Fof%5FFatou%5Fcomponents" rel="nofollow">classification of Fatou components</a> to help figure out the behavior of your sequence of averages. </p> <p>On the Julia set, the behavior of the sequence of averages is going to be some kind of a weighted average of f, but as the the orbit of a generic point in J is dense in J, would the sequence of averages of such a point converge to something like a center of mass?</p> http://mathoverflow.net/questions/155/when-does-the-sequence-of-iterates-of-a-rational-function-converge/715#715 Answer by Darsh Ranjan for When does the sequence of iterates of a rational function converge? Darsh Ranjan 2009-10-16T05:47:17Z 2009-10-19T10:43:40Z <p>I think I've essentially solved the problem for Mobius transformations (rational maps of degree 1). The situation can basically be summarized as "nothing to see here, folks" except for the one interesting case brought up by Michael Lugo. I think I know what happens in that case, but I haven't proved all of it. For brevity, I'm not going to prove everything rigorously because there are many cases. </p> <p>In everything that follows, f(x) = (ax + b)/(cx + d), and {a<sub>n</sub>(x)}<sub>n</sub> is the sequence of averages starting at x. </p> <p>First a few obvious things: </p> <p>(1) If x is a fixed point of f, then clearly a<sub>n</sub>(x) = x for all n and thus converges to x trivially. A non-identity Mobius transformation typically has two fixed points, or one fixed point if f is parabolic (conjugate to a translation). </p> <p>(2) Infinity has to be treated specially because if it appears anywhere in the sequence, then the sequence from that point on is constant at infinity and thus converges trivially to infinity. Thus, if x = f^(-n) (infinity) for any n, then a<sub>n</sub>(x) converges to infinity. </p> <p>The behavior of a<sub>n</sub>(x) for general x depends on the classification of f as parabolic, hyperbolic/loxodromic, or elliptic. Also, whether or not infinity is one of the fixed points can be important. </p> <p>(3) If f is parabolic, having a unique fixed point a: if a = infinity, then f is a translation, and it's easy to see that a<sub>n</sub>(x) must diverge to infinity. If a &ne; infinity, then for all x in C, f^n(x) converges to a, and thus a<sub>n</sub>(x) also converges to a (except as noted in point (2)). </p> <p>(4) If f is loxodromic or hyperbolic, having two fixed points: if one of them is infinity, then conjugating by a Euclidean similarity, f(x) = rx for some complex r, where |r| &ne; 1. Then </p> <p>a<sub>n</sub>(x) = x(r^(n+1)-1)/((n+1)*(r-1)),</p> <p>which converges to 0 for all x if |r| &lt; 1 or diverges to infinity for all x if |r| > 1 (except as noted in point (1)). If infinity is not one of the fixed points, then f has two fixed points in the complex plane, one of them attracting and one of them repelling. f^n(x) and a<sub>n</sub>(x) then converge to the attracting fixed point for all x (except as noted in points (1) and (2)). </p> <p>(5) If f is elliptic, having two fixed points: if one of them is infinity, then f is a Euclidean rotation, and it's easy to see that a<sub>n</sub>(x) converges to the center of rotation for all x. If infinity isn't a fixed point, then conjugating by a Euclidean similarity, the two fixed points are +/- i, so </p> <p>f(x) = (cos(t)x - sin(t))/(sin(t)x + cos(t))</p> <p>for some fixed t. If t is a rational multiple of &pi;, then f has finite order, and a<sub>n</sub>(x) actually converges to a rational function of x. Otherwise, let r = |(x - i)/(-ix + 1)|. If r &ne; 1, then a<sub>n</sub>(x) converges to the integral</p> <p>(1/(2&pi;))&int;<sub>0</sub><sup>2&pi;</sup>(re^(i&theta;) + i)/(ire^(i&theta;) + 1)d&theta;</p> <p>which can be computed without too much difficulty (say, by residue calculus) to be i if r &lt; 1 (if x is in the upper half-plane) or -i if r > 1 (if x is in the lower half-plane). If r = 1, then x is real. Then things get interesting, because {f^(-n)(infinity)} is a countable dense subset in <b>R</b>. However, if x is real and not in this set, then I <em>believe</em> (but haven't proved) that a<sub>n</sub>(x) does not converge or diverge to infinity. My thinking: the distribution of the iterates f^n(x) can be shown to converge to the Cauchy distribution, with density 1/(&pi;(1+x^2)) for x&isin;<b>R</b>. This distribution has pathological properties, such as not being integrable. In fact, if X<sub>1</sub>, ..., X<sub>m</sub> are independent variables picked from this distribution, then (X<sub>1</sub> + ... + X<sub>m</sub>)/m actually has the same distribution. Based on that, a reasonable conjecture might be that the distribution of the <i>averages</i> a<sub>n</sub>(x) also converges to the same Cauchy distribution, which would certainly preclude any kind of convergence of the values of the sequence. [<b>edit:</b> Actually, I can't support that conjecture numerically; it might be false, or the distribution might just converge very slowly.]</p> http://mathoverflow.net/questions/155/when-does-the-sequence-of-iterates-of-a-rational-function-converge/1195#1195 Answer by Darsh Ranjan for When does the sequence of iterates of a rational function converge? Darsh Ranjan 2009-10-19T10:39:17Z 2009-10-19T18:06:33Z <p>In case anyone was wondering, it is not the case that for a general rational function, you can expect the sequence of averages of iterates to converge for most x. I wasn't sure about that until a couple days ago, when I discovered that there are rational functions that are actually topologically mixing. In fact, the result is a bit stronger: there are rational maps f such that, for any nonempty open subset U of the Riemann sphere, there is a positive integer n such that f<sup>n</sup>(U) is the entire Riemann sphere. That means for typical x, the orbit will be dense in the sphere, and that makes it unlikely for the averages of the iterates to converge to something. That intuition is confirmed by empirical evidence. I didn't prove the last part rigorously, but I didn't try very hard, since I guess I was too fascinated by the examples of such functions that I had found. </p> <p>How to find such functions: recall that an elliptic function is a doubly periodic meromorphic function on the complex plane. In other words, there should be linearly independent (over <b>R</b>) periods w1 and w2 such that g(z) = g(z + w1) = g(z + w2) for all z. We may as well fix w1 = 1 by rotating the plane if necessary. Then, after choosing the second period &tau; := w2, we can define the Weierstrass elliptic function p as usual, which is an even elliptic function of order 2. It's an easy theorem that any even elliptic function with periods 1 and &tau; is a rational function of the Weierstrass function p. Consider g(z) = p(2z): g is even and doubly periodic with periods 1/2 and &tau;/2, but we can certainly consider its periods to be 1 and &tau; instead, forgetting the extra periodicity. Thus, g is a rational function of p, say f(p). In other words, we have:</p> <p>p(2z) = f(p(z)),</p> <p>where f is some rational function. Now let's prove the claim: let U be any open subset of the Riemann sphere, and let V = p<sup>-1</sup>(U). p is surjective and continuous (as a function with domain <b>C</b> and codomain P<sup>1</sup>), so V is a nonempty open subset of <b>C</b>. But iterating the definition of f, we have:</p> <p>f<sup>n</sup>(p(z)) = p(2<sup>n</sup>z), so</p> <p>f<sup>n</sup>(U) = f<sup>n</sup>(p(V)) = p(2<sup>n</sup>V).</p> <p>But V is nonempty and open, so 2<sup>n</sup>V must eventually contain a fundamental domain of p as n grows. The restriction of p to 2<sup>n</sup>V is then surjective, so the restriction of f<sup>n</sup> to U is also surjective, as claimed. Also, if z = p(w), then f<sup>n</sup>(z) = p(2<sup>n</sup>w). For a "randomly chosen" z, {2<sup>n</sup>w mod (<b>Z</b> + &tau;<b>Z</b>)} will be dense in the fundamental domain of p, so {f<sup>n</sup>(z)} will be dense in P<sup>1</sup>. (We don't need to be too careful about the probability distribution, I think, as long as it agrees with Lebesgue measure on sets of measure zero.)</p> <p>It sounds stupid, but I wondered about that for years. I suppose it should be obvious that for an arbitrarily chosen rational function, one shouldn't expect the orbit of a point to behave well at all, but I didn't have any explicit examples of very bad behavior. Now I do. :-) Also, strangely enough, this answers <em>another</em> question I've been wondering about for a while, namely how to compute an elliptic function. I didn't say how to find explicit descriptions of the rational functions f defined above, but I think I know the answer; I just haven't proved it yet. [<b>edit:</b> I did manage to prove it after I posted this.] One example, for &tau; = i, seems to be:</p> <p>f(z) = 4/(1/z - z + (z-1)/(z+1) + (1+z)/(1-z)).</p> <p>That has degree 4, but for a degree-2 example, try:</p> <p>f(z) = (1 + i z<sup>2</sup>)/(i + z<sup>2</sup>) or</p> <p>f(z) = 2iz/(1 - z<sup>2</sup>).</p> <p>Those are based on the extra symmetry when &tau; = i, namely p((1+i)z) is also a rational function of p(z), since it is even and has periods (1-i)/2 and (1+i)/2, but again, we can forget the extra periodicity and use w1 = (1-i)/2 + (1+i)/2 = 1, w2 = (1+i)/2 - (1-i)/2 = i.</p> http://mathoverflow.net/questions/155/when-does-the-sequence-of-iterates-of-a-rational-function-converge/105520#105520 Answer by Alexandre Eremenko for When does the sequence of iterates of a rational function converge? Alexandre Eremenko 2012-08-26T11:44:58Z 2012-08-26T11:44:58Z <p>If a trajectory $f^n(x)$ converges, the limit must be a fixed point, that is it satisfies $f(a)=a$. The number of fixed points is finite, and they can be all found by solving an algebraic equation. Now the question is for given $x$ and $a$ to decide whether $f^n(x)\to a$. This can happen in two ways:</p> <p>a) $f^n(x)=a$ for some $n$, so the sequence becomes constant from some place, and trivially converges, or</p> <p>b) $f^n(x)\to a$ but $f^n(x)\neq a$ for all $n$.</p> <p>Whether a) happens for a given $x$ might be difficult to decide. The set of all $x$ for which $f^n(x)=a$ for some $n$ is usually dense on the Julia set, and the Julia set is quite complicated. One can show that it is not semi-algebraic in most cases, with a few trivial exceptions when it is a circle or an arc of a circle.</p> <p>Of course one can give various meanings to the words "given $x$" and "to find out". The question can be easier if, for example, $x$ is rational, and coefficients of $f$ are rational. Or algebraic. Otherwise it is not clear in what form $x$ can be "given", etc.</p> <p>In the case $b$, there is a reasonable description of the sets of convergence. The fixed points are divided into several categories according to the multiplier $\lambda=f'(a)$. For convergence b) to happen, this multiplier has to satisfy $|\lambda|&lt;1$, or $\lambda^n=1$. This is a very deep result of R. Perez Marco. In these two cases, convergence b) happens in the so-called "domains of attraction", which are open but not necessarily connected. The boundary of such domain of attraction coincides with the Julia set, so the "domains" can be quite complicated.</p> <p>But one can obtain very good pictures of them with a computer. </p>