A solvable chaos of every degree

The same map in different coordinates found that the logistic map at four, the tent map and the doubling map are one map seen three ways. In the right coordinate an orbit of the logistic map is nothing but an angle doubling, round and round a circle, and the chaos is entirely the chaos of binary digits being shifted. That essay also noted the identity underneath it, $2\cos^2\theta - 1 = \cos 2\theta$, and named the family it belongs to as deserving a treatment of its own: one solvable map of every degree.

The family is the Chebyshev polynomials. For every whole number $n$ there is a polynomial $T_n$ with the defining property

$$T_n(\cos\theta) = \cos(n\theta).$$

Read as a map of the interval from $-1$ to $1$ to itself, $T_n$ multiplies angles by $n$. The logistic map at four is $T_2$ in disguise; $T_3$, $T_4$, $T_5$ are the same idea with a larger multiplier, and everything that was true of the logistic map because of the doubling is true of each of them because of the multiplication.

Why each one is a polynomial #

It is not obvious that $\cos(n\theta)$ is a polynomial in $\cos\theta$ at all. The reason is a recurrence. Adding the formulas for $\cos((n+1)\theta)$ and $\cos((n-1)\theta)$ gives

$$\cos((n+1)\theta) = 2\cos\theta\,\cos(n\theta) - \cos((n-1)\theta),$$

so $T_{n+1}(x) = 2x\,T_n(x) - T_{n-1}(x)$, starting from $T_0 = 1$ and $T_1 = x$. Each step multiplies by $2x$ and subtracts, which raises the degree by one and keeps whole-number coefficients. So $T_2 = 2x^2 - 1$, $T_3 = 4x^3 - 3x$, $T_4 = 8x^4 - 8x^2 + 1$, and so on, with leading coefficient $2^{n-1}$.

The graphs show what the defining property means geometrically. As $\theta$ runs from $0$ to $\pi$, $x = \cos\theta$ runs once from $1$ down to $-1$, while $\cos(n\theta)$ runs back and forth between $1$ and $-1$ exactly $n$ times. So the graph of $T_n$ over the interval has $n$ monotone laps, each sweeping the full height of the square. The map folds the interval onto itself $n$ times, and every point of the interval has $n$ preimages. The doubling map’s two-to-one fold is the case $n = 2$.

The same curves turn up in a place that has nothing to do with iteration. A point moving round two circles at once, one $n$ times as fast as the other, traces $x = \cos t$, $y = \cos(nt)$ — a Lissajous figure, the subject of when two circular motions come home. With the two motions in step, the Lissajous figure is exactly the graph of $T_n$, traced back and forth: the Chebyshev polynomials are what a frequency ratio of $1 : n$ draws.

The logistic map is the first of them #

The claim that the logistic map at four is $T_2$ is a claim about a change of coordinates, and it is worth seeing done rather than taken on trust.

The figure carries the tent map to the logistic map through a sine squared. One more linear change of variable, $u = 1 - 2x$, turns the logistic map $4x(1-x)$ into $2u^2 - 1$, which is $T_2$: expanding, $1 - 2 \cdot 4x(1 - x) = 2(1 - 2x)^2 - 1$. So the three maps — tent, logistic, Chebyshev — are one map, and the angle $\theta$ with $u = \cos\theta$ is the coordinate in which it becomes angle doubling.

The same chain works at every degree. $T_n$ is carried by $u = \cos\theta$ to multiplication of the angle by $n$, and by the tent-like change of variable to a zigzag map with $n$ straight pieces of slope $\pm n$. Every solvable map of this family is a straight-line zigzag bent into a polynomial, and every one of them shares the logistic map’s special status at a single parameter value.

Chebyshev’s own reason for them #

Chebyshev did not meet these polynomials through iteration. In 1854 he was designing linkages that turn circular motion into nearly straight motion, and asked which polynomial of a given degree, with leading coefficient one, stays closest to zero over the whole interval from $-1$ to $1$. The answer is $2^{1-n}T_n$, whose largest value on the interval is $2^{1-n}$ and cannot be beaten by any other monic polynomial of degree $n$.

The reason it wins is the same shape the graphs show. $T_n$ touches the top and bottom of the square alternately, $n + 1$ times. Any monic polynomial that stayed strictly smaller would differ from it by a polynomial of lower degree that changes sign at each of those $n + 1$ points, and a polynomial of degree less than $n$ cannot change sign $n$ times. The alternating touches that make $T_n$ the best approximation are exactly the full-height folds that make it an $n$-fold chaotic map. One property, equioscillation, does both jobs.

That is why the same polynomials run through numerical analysis: the points where $T_n$ reaches $\pm1$, and the points where it vanishes, are the best places to sample a function for interpolation, because they spread the error evenly instead of letting it pile up at the ends. The arcsine density that every Chebyshev orbit follows is the same crowding towards the ends that those sample points show.

An orbit that is a formula #

Because $T_n$ multiplies the angle by $n$, iterating it multiplies by $n$ again and again. Starting from $x_0 = \cos\theta$,

$$x_k = \cos(n^k \theta),$$

and the whole future of the orbit is written down at once.

The staircase looks exactly like the staircase that shows the whole orbit of any chaotic map: it jumps unpredictably across the square, never settling. It is also completely known in advance, twelve cosines of twelve powers of three. There is no contradiction. Solvable and chaotic are not opposites; the formula says exactly where the orbit goes, and what it says is that the orbit’s position depends on the digits of the starting angle in base $n$, which are as unpredictable as the digits of a number usually are.

The rate at which nearby orbits separate follows from the formula too. Two starting angles a distance $\varepsilon$ apart are $n^k\varepsilon$ apart after $k$ steps, so the separation grows by a factor $n$ per step and the map’s Lyapunov exponent is $\log n$ — the number that measures how fast two orbits part, here found exactly. The number of laps of the $k$-th iterate is $n^k$, so its topological entropy, which the folds that measure chaos defined as the growth rate of laps, is $\log n$ as well. For these maps the two measures of chaos agree, and both are the logarithm of the multiplier.

Counting the periodic points exactly #

For most maps the number of periodic points of each period can only be found by searching. For the Chebyshev maps it is a formula.

Applying $T_n$ $k$ times multiplies the angle by $n^k$, so it is the Chebyshev polynomial $T_{n^k}$. Its fixed points are the $x = \cos\theta$ with $\cos(N\theta) = \cos\theta$, where $N = n^k$ — which happens exactly when $N\theta = \pm\theta$ plus a whole number of turns. That gives the angles $2\pi j/(N-1)$ and $2\pi j/(N+1)$, and on the half-turn $[0, \pi]$ they number exactly $N$, once the two shared endpoints are counted once. So $T_n$ has exactly $n^k$ points of period dividing $k$, all real, all in the interval, and each is a cosine of a rational multiple of $\pi$. The figure checks the count and the composition identity for every entry of the table.

The smallest cases can be done by hand. $T_2 = 2x^2 - 1$ has the two fixed points $x = 1$ and $x = -\tfrac12$, the cosines of $0$ and $2\pi/3$, and $2 \cdot \tfrac14 - 1 = -\tfrac12$ confirms the second. Its four points of period dividing two add the pair $\cos 72° \approx 0.309$ and $\cos 144° \approx -0.809$, which $T_2$ swaps: doubling $72°$ gives $144°$, and doubling $144°$ gives $288°$, whose cosine is that of $72°$ again. Those two numbers are $(\sqrt5 - 1)/4$ and $-(\sqrt5 + 1)/4$, so the first two-cycle of the logistic map’s chaos is the golden ratio in disguise — the pentagon’s angles, halved and folded onto an interval.

The periodic points are therefore close relatives of the roots of unity: $\cos(2\pi j/(N \pm 1))$ is the real part of a root of unity of order $N \pm 1$. The whole periodic structure of a chaotic map is written in the arithmetic of the circle — how many points of each period, where they are, which ones are primitive — and a question about the map is a question about which fractions of a turn stay fractions when multiplied by $n$.

One distribution for the whole family #

The histogram of a long orbit of the logistic map settles on the arcsine density, piled up at the ends of the interval. In the Chebyshev coordinate that density is $1/(\pi\sqrt{1 - x^2})$, and it is exactly the distribution of $\cos\theta$ when $\theta$ is uniform — which is why it is preserved: multiplying a uniformly distributed angle by $n$ leaves it uniformly distributed round the circle.

The three histograms lie on top of one another and on the shaded prediction. Every Chebyshev map preserves the same distribution, because multiplying a uniform angle by any whole number leaves it uniform. And almost every orbit is fair applies to each of them unchanged: the map of angles is $\theta \mapsto n\theta$, which in base $n$ is the shift of digits, and its ergodicity is proved by the same argument about Fourier coefficients being pushed to frequency $nm$. Almost every orbit of every Chebyshev map is distributed by the arcsine density.

The histograms are computed by iterating the polynomials in floating point, which, unlike the doubling map’s, does not collapse — the rounding at each step is absorbed by the fold rather than discarding digits. The orbit drawn is then not the true orbit of its starting point but, as the orbit a computer draws explained, a true orbit of some nearby point, which is enough for a histogram.

Maps that commute #

The last property is the rarest, and it is what makes the family special among all polynomials. Multiplying an angle by 2 and then by 3 is the same as multiplying by 3 and then by 2, so

$$T_2 \circ T_3 = T_3 \circ T_2 = T_6,$$

and in general $T_m \circ T_n = T_{mn}$ for every $m$ and $n$. The Chebyshev maps commute with one another.

Two polynomials chosen almost at random do not commute, as the right-hand panel shows: squaring and then subtracting one is not the same as subtracting one and then squaring. Joseph Ritt proved in 1923 that commuting is extraordinarily rare. If two polynomials of degree at least two commute, then either both are iterates of a single polynomial, or, after a linear change of coordinates, they are both power maps $x^m$ and $x^n$, or both Chebyshev maps $T_m$ and $T_n$ — up to the sign of the Chebyshev maps. The power maps are the Chebyshev maps’ counterpart on the circle, $z \mapsto z^n$ being angle multiplication in its native form, as in multiplying is turning. Angle multiplication is the only source of commuting polynomials.

Ritt’s work came out of the study of polynomial dynamics begun by Pierre Fatou and Gaston Julia, and in their terms the Chebyshev maps are the extreme cases. The map $z \mapsto z^2 - 2$ is $T_2$ in the coordinate $z = 2\cos\theta$, and its Julia set — the boundary between points that escape to infinity and points that do not — is the segment from $-2$ to $2$, the thinnest a Julia set can be. The parameter $-2$ is the leftmost tip of the Mandelbrot set, and the Chebyshev map sits there as the one point where the whole complicated structure collapses to a line.

The same polynomials over a finite field #

The recurrence $T_{n+1} = 2xT_n - T_{n-1}$ has whole-number coefficients, so it makes sense in arithmetic modulo a prime $p$, where there are no angles and no interval, only the numbers $0$ to $p - 1$. The commuting identity $T_m \circ T_n = T_{mn}$ survives, because it is an identity between polynomials and holds in any arithmetic. What becomes interesting is whether $T_n$ shuffles the numbers modulo $p$ — whether every number is hit exactly once.

It does exactly when $n$ shares no factor with $p^2 - 1$. Modulo $7$, where $p^2 - 1 = 48$, the maps $T_2$ and $T_3$ fail and $T_5$ and $T_7$ succeed; modulo $13$, where $p^2 - 1 = 168$, it is $T_5$ that succeeds and $T_7$ that fails. The rule comes from the same picture as the real case: the role of the circle of angles is played by the multiplicative group of a finite field with $p^2$ elements, whose size is $p^2 - 1$, and multiplying “angles” by $n$ is a shuffle exactly when $n$ is invertible there. These shuffles are the Dickson permutation polynomials, and a collision that finds a factor iterates a squaring map in the same modular arithmetic for a different purpose — to find repetitions, which angle multiplication modulo $p$ must eventually produce.

What the curves cannot show #

The Julia set and the complex picture. Every figure here is on the real interval. The Chebyshev maps are polynomials of a complex variable too, and their commuting, their periodic points and their invariant distribution all have complex versions that explain the real ones. None of that appears; the real interval is the shadow of a picture in the plane.

Why commuting forces the family. The right-hand panel shows one non-commuting pair; Ritt’s theorem says that every commuting pair is of one of three kinds. The proof is long, uses the dynamics of the maps in the complex plane, and has no drawing in it that would convince anyone. The figure illustrates that commuting is rare and cannot show that it is this rare.

What a floating-point orbit is. The density figure iterates in floating point for forty thousand steps. The formula $x_k = \cos(n^k\theta)$ would need $k \log_{10} n$ extra digits of $\theta$ to evaluate at step $k$, so the computed orbit and the true orbit of the stated starting point part company within a few dozen steps. What is drawn is honest about the distribution and not about any one orbit.

Still open: whether this orbit is a fair one #

The staircase figure started at $\cos 1$, and under $T_2$ the same starting point has the orbit $\cos(2^k)$ — the cosines of the powers of two, measured in radians. Whether those numbers are distributed by the arcsine density, as almost every orbit is, depends on whether the angles $2^k$ are spread evenly round the circle, which is the question of whether the binary digits of $1/(2\pi)$ are normal.

That is not known. Almost every starting angle gives a fair orbit, and the angle $1$ radian gives one that has been computed far out and looks perfectly fair; there is no proof. The same is true for every Chebyshev map and every starting angle anyone can name that is not a rational multiple of $\pi$. The family is solvable in every sense a formula can give, and whether a particular orbit of it is typical is exactly as open as the normality of a particular constant.

Multiplying angles, in every degree #

The Chebyshev polynomials turn angle multiplication into maps of an interval. For each whole number $n$ the map $T_n$ folds the interval $n$ times, sends $\cos\theta$ to $\cos n\theta$, and so has orbits given by a formula, $n^k$ periodic points of each period listed by that formula, a Lyapunov exponent and an entropy both equal to $\log n$, and the arcsine distribution preserved by all of them at once.

They commute, because multiplying angles commutes, and Ritt proved that polynomials almost never do otherwise. The logistic map at four is the first of them, and the solvable chaos that seemed a lucky accident of degree two is the first member of a family with one member for every degree — with the question of whether any particular orbit is fair left exactly as open as it was for the doubling map.