When does iterating $z \mapsto z^2 + c$ have an exact solution?

Question

If one iterates the map $z \mapsto z^2 + c$ there is obviously a simple formula for the sequence one gets if $c=0$. Less obviously, there is also a simple formula when $c = -2$ (use the identity $2 \cos(2x) = (2\cos(x))^2 - 2)$. Are there any other values of $c$ for which one can solve this recurrence explicitly? (For all initial values of course: there are many trivial explicit solutions for special initial values, such as fixed points.)

Related links:
http://en.wikipedia.org/wiki/Mandelbrot_set (the points $c$ where 0 remains bounded under iteration of this map: this strongly suggests that there is no simple exact solution for general $c$).
http://en.wikipedia.org/wiki/Logistic_map (gives the explicit solutions above, after a change of variable)

Motivation: I once used the map with $c=-2$ in a lecture to show that one could prove limits exist even without a formula for the exact solution. A first year calculus student pointed out the non-obvious exact solution above, and I don't want to be caught out like this again.

Although congratulations to the first-year calculus student would definitely be in order... I think Rota used to hand out little chocolate bars for such clever observations. — Todd Trimble, Sep 09 '18 at 15:09

score 38 · Accepted Answer · answered Aug 08 '10 at 19:26

38

No, there are no others.

Analytically, one can show that if a Julia set contains an analytic arc, it is in fact a straight line or a circle (up to conjugation). For the class $z^2+c$, $0$ and $-2$ are the only values where this occurs.

This does not quite imply that there are no closed-form solutions of the recurrence for any other value of $c$, but such a closed form would naturally describe a fractal. As far as I know, there are no "closed form" functions which directly have a fractal as one of its level set.

answered Aug 08 '10 at 19:26

Jacques Carette

11,669

6

I guess it is unreasonable to expect a completely watertight answer since my question was a bit vague, but looking at the Julia sets does indeed seem to be the key point. I should have looked at http://en.wikipedia.org/wiki/Julia_set which also points out that 0 and -2 have special Julia sets. It seems I managed to pick at random the only non-zero real number that did not have the property I claimed. – Richard Borcherds Aug 09 '10 at 00:44
7

In the Pollard rho method for factoring the integer n, one iterates the map $n\to f(n)$, reducing modulo $n$, for an appropriate $f$, and calculates certain GCDs. It's common to use $f(n)=n^2+c$, and one has to avoid $c=0$ and $c=-2$, for reasons similar to those given in this thread. – Gerry Myerson Aug 09 '10 at 04:21
10
The substitution $z=w+w^{-1}$ that conjugates $z\to z^2-2$ to $w\to w^2$ is the twice the "Zhukovsky function" of complex analysis (which was used for modeling airfoils). 2. The principle behind the Lucas-Lehmer test is an explicit formula for the $n$th iterate of $z\mapsto z^2-2$ that involves raising to the power $2^n.$ 3. There is an algebraic explanation of the special character of $c=2:$ the only monic quadratic polynomials that belong to a family of commuting polynomials of all natural degrees are $z^2$ and $z^2-2$ (for $z^2-2$, the family consists of rescaled Chebyshev polynomials).

Victor Protsak

Aug 09 '10 at 05:44

Sorry to contradict you, but there is no reason that a closed form soluiion of the shape $z_n=f(k^nZ_0) (with Z_0=g(z_0)) would "describe" a fractal. See my answer below... – Feldmann Denis Aug 27 '11 at 22:17

Bill Thurston · Answer 2 · 2010-09-20T01:04:20.480

I'd like to add a little more context for the record here, to amplify and extend Jacques Carrette's answer as well as the extra information in the comments:

The Chebyshev polynomials, together with their close relatives the maps $z \to z^n$, are the the only polynomials exhibiting the property described in the question, up to affine coordinate change. Geometrically, the map $z \to z^n$ is an $n$-fold covering map of the cylinder $\mathbb C \setminus 0$ over itself. This cylinder has an order 2 symmetry $z \to z^{-1}$ that commutes with the covering map. The quotient of the cylinder by the symmetry is equivalent to $\mathbb C$, or preserving a little more information, it's an orbifold structure on $\mathbb C$, with two order 2 cone points at $\pm 2$.

The expression $z + z^{-1}$ is the formula for the quotienting map $\mathbb C \setminus 0 \to \mathbb C$. The cylinder can be unwrapped further to the universal cover (also $\mathbb C$) of $\mathbb C \setminus 0$; the quotient maps from the universal cover to the two quotients are $\exp$ and $\cos$, and so the Chebyshev polynomials (up to affine normalization) are the formulas for $\cos$ of a multiple angle in terms of $\cos$ of an angle.

There are however other rational functions which admit explicit analytic formulas for iteration. These are called Lattès examples, named after Samuel Lattès who discovered them in 1918 (although according to Milnor's article in the Bodil Branner festschrift, Schöder described similar examples almost 50 yeasr earlier, but they appear to have been forgotten).

The Lattès examples are symmetry quotients of isomorphisms of wall-paper groups to proper subgroups. For every orientation-preserving wall-paper group except the group of translations, the quotient space (wallpaper modulo symmetry) is topologically a sphere. Every such group is isomorphic to subgroups of itself in infinitely many ways. These isomorphisms descend to branched coverings of the quotient space over itself: in the language of complex functions these are rational maps, in the language of orbifolds these are self-coverings.

They have a significant role as exceptional examples in complex dynamics, and are well understaood, with lots of nice pictures available someplace in the literature. For example, an endomorphism of the tiling groups whose formula is multiplication by the complex number $\lambda$ can be used for a kind of base $\lambda$ expansion of complex numbers, associated with a self-similar tiling of $\mathbb C$ (with basic tile is those numbers starting after the lambdimal point). At least for some cases, the digits can be arranged in an order that defines a sphere-filling curve invariant under multiplication by $\lambda$.

All these examples have explicit analytic formulas for iterations, completely analogous to the formula $z \to 2 \cos (k^n \arccos ( z/2))$ for the $n$th iterate of the $k$th Chebyshev polynomial. In the Chebyshev formula, $\cos$ is the universal covering map of $\mathbb C$ for the $(22\infty)$ orbifold. For wallpaper groups, the universal covering maps are elliptic functions instead of $\cos$. The rational map lifts to multiplication by a complex number $\lambda$, so you lift to the cover, multiply by a power of $\lambda$, and map back down.

Feldmann Denis · Answer 3 · 2012-04-14T04:29:00.587

Actually, there are many other cases : if $f$ is a surjective map from $C$ to $C$ such that $f(az)=f(z)^2+c$, we get the simple formula $z_n=f(a^nZ0)$, where $f(Z_0)=z_0$. So the question is : for which values of $a$ and $c$ does such an $f$ exists, with perhaps some more constraints on $f$ such as smoothness. It turns out that for any $c$ large enough (at least of module greater than 1) there exists exactly one such entire function $f$, with $f'(0)=1$ and $a=2f(0)=1+\sqrt{1-4c}$ (this is shown by an elementary, but tedious calculation of the coefficients of the series by recurrence (done in French here, page 8)), followed by a simple argument of domination of those coefficients, proving convergence for $R>0$ ; then, analytic continuation shows that the radius of convergence is infinite) ; $f$ is (almost) surjective by Picard theorem. Of course, those $f$ are never "usual" or elementary functions, except for $c=0$ or $c=-2$, but so what?

When does iterating $z \mapsto z^2 + c$ have an exact solution?

3 Answers3