MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

When does the sequence of iterates of a rational function converge?

Darsh asks at the 20-questions seminar:

Let f:P^1 -> P^1 be rational function.

Can you say when the sequence {f^n(x)}_n = {x, f(x), f(f(x)), ...} converges? What about the sequence of averages {1/(n+1) \sum_i=0^n f^i(x)}_n? Anything else?

-
Is there a requirement that it converge to a rational function - because my first suspicion is that considering Q is not complete, there are going to turn out to be many cases where the sequence converges, but the resulting function takes irrational values. – streklin Oct 7 2009 at 12:39
In most interesting cases, the sequence will probably not converge to a rational (or even continuous) function. What I want to know is whether, for arbitrary x, the sequence x, (x + f(x))/2, (x + f(x) + f^2(x))/3, ... converges to something. For example, whenever the sequence of iterates is attracted to a periodic orbit, the sequence of averages will converge to the mean value of the attracting orbit. – Darsh Ranjan Oct 15 2009 at 5:27
Perhaps say what is $P\wedge 1$. – Gerald Edgar Aug 26 at 12:42

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:

a) $f^n(x)=a$ for some $n$, so the sequence becomes constant from some place, and trivially converges, or

b) $f^n(x)\to a$ but $f^n(x)\neq a$ for all $n$.

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.

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.

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

But one can obtain very good pictures of them with a computer.

-

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

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 R) 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 τ := 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 τ 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 τ/2, but we can certainly consider its periods to be 1 and τ instead, forgetting the extra periodicity. Thus, g is a rational function of p, say f(p). In other words, we have:

p(2z) = f(p(z)),

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-1(U). p is surjective and continuous (as a function with domain C and codomain P1), so V is a nonempty open subset of C. But iterating the definition of f, we have:

fn(p(z)) = p(2nz), so

fn(U) = fn(p(V)) = p(2nV).

But V is nonempty and open, so 2nV must eventually contain a fundamental domain of p as n grows. The restriction of p to 2nV is then surjective, so the restriction of fn to U is also surjective, as claimed. Also, if z = p(w), then fn(z) = p(2nw). For a "randomly chosen" z, {2nw mod (Z + τZ)} will be dense in the fundamental domain of p, so {fn(z)} will be dense in P1. (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.)

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 another 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. [edit: I did manage to prove it after I posted this.] One example, for τ = i, seems to be:

f(z) = 4/(1/z - z + (z-1)/(z+1) + (1+z)/(1-z)).

That has degree 4, but for a degree-2 example, try:

f(z) = (1 + i z2)/(i + z2) or

f(z) = 2iz/(1 - z2).

Those are based on the extra symmetry when τ = 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.

-
 More algebrao-geometrically, one can take take any elliptic curve, quotient out by the map sending an element to its inverse, and you will end up with the projective line. Any endomorphism of this elliptic curve descends to a rational function on the projective line, known in the literature as a Lattes map. This gives a family of rational maps where you can actually compute the dynamics in a reasonably explicit manner. – Peter McNamara May 19 2010 at 23:43

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.

In everything that follows, f(x) = (ax + b)/(cx + d), and {an(x)}n is the sequence of averages starting at x.

First a few obvious things:

(1) If x is a fixed point of f, then clearly an(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).

(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 an(x) converges to infinity.

The behavior of an(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.

(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 an(x) must diverge to infinity. If a ≠ infinity, then for all x in C, f^n(x) converges to a, and thus an(x) also converges to a (except as noted in point (2)).

(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| ≠ 1. Then

an(x) = x(r^(n+1)-1)/((n+1)*(r-1)),

which converges to 0 for all x if |r| < 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 an(x) then converge to the attracting fixed point for all x (except as noted in points (1) and (2)).

(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 an(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

f(x) = (cos(t)x - sin(t))/(sin(t)x + cos(t))

for some fixed t. If t is a rational multiple of π, then f has finite order, and an(x) actually converges to a rational function of x. Otherwise, let r = |(x - i)/(-ix + 1)|. If r ≠ 1, then an(x) converges to the integral

(1/(2π))∫0(re^(iθ) + i)/(ire^(iθ) + 1)dθ

which can be computed without too much difficulty (say, by residue calculus) to be i if r < 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 R. However, if x is real and not in this set, then I believe (but haven't proved) that an(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/(π(1+x^2)) for x∈R. This distribution has pathological properties, such as not being integrable. In fact, if X1, ..., Xm are independent variables picked from this distribution, then (X1 + ... + Xm)/m actually has the same distribution. Based on that, a reasonable conjecture might be that the distribution of the averages an(x) also converges to the same Cauchy distribution, which would certainly preclude any kind of convergence of the values of the sequence. [edit: Actually, I can't support that conjecture numerically; it might be false, or the distribution might just converge very slowly.]

-

I haven't really studied complex dynamics much, but here's a suggestion for the general case:

In the Fatou set of f, you should use Sullivan's classification of Fatou components to help figure out the behavior of your sequence of averages.

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?

-
 Thanks, that theorem is probably pretty useful here. Regarding the Julia set J: in cases where it's a compact subset of C (i. e., doesn't contain infinity), I think that there should again be an f-invariant probability measure supported on J to whose mean value the average of the iterates will converge from any point on J. That's just intuition, though... – Darsh Ranjan Oct 16 2009 at 5:53

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.

-
 Good reply. In your example, there will be a probability measure supported on that circle, invariant under f, to whose expected value the averages converge. In fact, it should be easy to compute. I'm happy to consider the case of Mobius transformations before attacking the general case, and I expect we can solve it completely. – Darsh Ranjan Oct 15 2009 at 21:09 Is it true for more general Mobius transformations than just rotations, though? I played around a bit with "random" Mobius transformations and I'm not convinced either way. – Michael Lugo Oct 16 2009 at 1:02