A chaotic map that always comes back

A difference too small to draw showed two starting points a ten-thousandth apart, under one deterministic rule, losing all trace of each other within forty steps. That is sensitive dependence, the property most people mean by chaos, and how fast two orbits part turned it into a number, the Lyapunov exponent: the average rate at which nearby orbits separate. A positive exponent means that any error in the starting point grows exponentially, and prediction beyond a short horizon is impossible.

This essay is about a map with a positive Lyapunov exponent that nonetheless returns every starting configuration exactly to where it began, after a number of steps that can be computed in advance. There is no contradiction, and the way the two facts sit together says something about what chaos is and is not. The map is the one Vladimir Arnold used to illustrate chaotic mixing in the 1960s, with a picture of a cat drawn on a square and smeared across it; it has been called the cat map ever since.

Scrambled in three steps, restored in thirty #

The map acts on points $(x, y)$ of a square whose opposite edges are glued together, a torus:

$$(x, y) \mapsto (2x + y, \; x + y) \pmod 1.$$

It is linear before the wrapping, given by the matrix $\begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}$, which has determinant 1 and so preserves area. Applied to a picture drawn in pixels on an $N \times N$ grid, it becomes $(x, y) \mapsto (2x + y, x + y) \bmod N$: each pixel is sent to another pixel, and no two are sent to the same one.

After one step the picture is sheared and wrapped round the square in long diagonal strips. After two the strips have been sheared again, and after three they are fine stripes covering the whole square. By step 7 the picture is noise: the 693 lit pixels are scattered with no visible trace of the disc, the square and the bar they started as. Step 22 looks the same. And at step 30 every pixel is exactly where it began, the picture restored to the last pixel.

Why it must come back #

The return is forced by finiteness. The map on the grid is a permutation of the $N^2$ pixels — each pixel goes to exactly one pixel and each pixel comes from exactly one — and applying a permutation over and over must eventually return everything to its start, because there are only finitely many arrangements and the map can be undone. The orbit that must come back made the same argument for any system with finitely many states, and Poincaré’s theorem extended it, in a weaker form, to continuous systems that preserve volume: almost every point returns arbitrarily close to where it started.

The cat map is a particularly clean case of both. On the continuous torus, Poincaré recurrence says points return close to their starts, though after times that can be astronomically long and different for every point. On the grid, the return is exact and simultaneous, and its time is a single number for the whole picture. The chaos has not gone anywhere; it is simply that a chaotic map on a finite set of states is still a map on a finite set of states.

There is a second way to see the grid inside the continuous map. A pixel $(x, y)$ of the $N \times N$ grid is the point $(x/N, y/N)$ of the torus, a point with rational coordinates of denominator $N$, and the cat map sends such points to such points. So every rational point of the torus lies on a periodic orbit of the continuous map, and since rational points are everywhere dense, the periodic orbits are too. Sensitivity comes free showed that dense periodic orbits together with an orbit that visits everywhere already force sensitive dependence; the cat map has both, and the pictures on grids are the periodic orbits made visible. Every grid is a finite net of periodic points threaded through a chaotic map, and the period of the picture is the period of the net.

Exact return also means exact reversal. The cat map has an inverse, $(x, y) \mapsto (x - y, \; -x + 2y)$, again a whole-number matrix with determinant 1, so on a grid the picture at step 22 can be turned back into the original by applying the inverse 22 times — or, equivalently, by applying the map itself 8 more times, since $22 + 8 = 30$. Running forwards past the scramble and running backwards out of it are the same journey round a cycle, seen from opposite ends.

A difference that grows by the golden ratio squared #

The chaos is real, and it is easy to measure on the continuous torus. Take two points, one a million-millionth to the right of the other, and apply the map to both.

The distance grows by a factor of 2.618 at every step, so on a logarithmic scale it climbs in a straight line, and after about 27 steps a difference too small to measure has become a difference as large as the square itself. The factor is $\varphi^2$, the square of the golden ratio $\varphi = 1.618\ldots$, and it is the larger eigenvalue of the matrix: the map stretches the square by $\varphi^2$ along one direction and shrinks it by $1/\varphi^2$ along the perpendicular one, keeping the area fixed. The Lyapunov exponent is $\ln \varphi^2 \approx 0.962$, the same at every point, which is why the cat map is the textbook example of a uniformly chaotic system rather than one whose chaos lives on a set nobody lands on.

On the grid, the same stretching is what scrambles the picture. Each step shears the image along the expanding direction, so features are drawn out into long thin strips that wrap round the square many times; after a handful of steps the strips are thinner than a pixel and the picture is gone. What the grid adds is that the pixels cannot be smeared out indefinitely. They can only be rearranged, and rearrangements repeat.

The Fibonacci numbers inside the map #

How long the return takes is set by an old sequence. The cat map’s matrix is the square of the Fibonacci matrix,

$$\begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^2,$$

and the powers of the Fibonacci matrix contain the Fibonacci numbers $F_n$: its $n$-th power is $\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}$. So applying the cat map $t$ times multiplies by a matrix whose entries are $F_{2t+1}$, $F_{2t}$ and $F_{2t-1}$, and the map returns every pixel exactly when those entries are 1, 0 and 1 modulo $N$ — when the Fibonacci numbers, taken modulo $N$, have come back round to where they began.

The Fibonacci numbers modulo $N$ always repeat, with a period called the Pisano period, studied by Joseph-Louis Lagrange and later by D. D. Wall. The cat map’s period is exactly half of it. The stretching factor $\varphi^2 = (3 + \sqrt 5)/2$ is a unit of the ring of numbers $a + b\varphi$ — a number of that form whose reciprocal is also of that form — and the cat map is multiplication by that unit, written in coordinates. One solution that makes all the others found the same structure behind Pell’s equation, where every solution is a power of one fundamental unit; here the powers of $\varphi^2$ are the iterates of the map, and their coordinates are the Fibonacci numbers. The golden ratio that governs the stretching and the Fibonacci numbers that govern the return are the same object seen from two sides: $\varphi$ is the limit of ratios of consecutive Fibonacci numbers, as the rectangle that eats itself found by cutting squares off a rectangle, and the cat map is that limiting process run as a dynamical system. Fractions repeat and roots look random met the Pisano period in yet another role, as the time the digits of a fraction take to repeat in base $\varphi$.

No grid takes longer than three times its size #

Computing the period for every grid size shows how varied it is.

For every $N$ from 3 to 600, the period is exactly half the Pisano period, and it never exceeds $3N$. It reaches $3N$ only at $N = 10$, 50 and 250 — twice a power of five — and Freeman Dyson and Harold Falk proved in 1992 that this is the general rule: the period is at most $3N$, with equality exactly when $N = 2 \cdot 5^k$. Most periods are far smaller. In 167 of the 598 grid sizes the picture returns in fewer than $N/4$ steps, and for a prime $p$ that leaves remainder 1 or 4 on division by 5, such as 61 or 101, the period divides $(p - 1)/2$: 30 for 61 and 25 for 101.

The scatter is not noise either. Each grid size’s period is determined by the prime factors of $N$ and how the Fibonacci numbers behave modulo each of them, and for a prime $p$ the period is controlled by whether 5 is a square modulo $p$ — a quadratic-reciprocity question in disguise. The points on the $3N$ line are the grid sizes built from 2 and powers of 5, the prime that divides the discriminant of $x^2 - x - 1$, the polynomial whose root is $\varphi$.

Every pixel on a cycle that divides the period #

The period is when the whole picture returns. Individual pixels may return sooner.

On a 120 × 120 grid, whose period is 60, the pixels fall into cycles of ten different lengths: the corner $(0, 0)$ never moves, four pixels return every 2 steps, fifteen every 3, and so on up to 10,080 pixels on cycles of 60. Every length divides 60, as it must, since a cycle’s length divides the order of the permutation. The picture returns when every one of its pixels has completed a whole number of laps, which happens first at the least common multiple of the lengths — the period itself, unless the picture happens to avoid the longest cycles. A picture drawn only on pixels of cycle length 12 would return after 12 steps, chaos notwithstanding. The short cycles have a simple source. A pixel whose coordinates are both multiples of 40 lives on a 3 × 3 grid hidden inside the 120 × 120 one, and the map treats it exactly as it would treat a pixel of a 3 × 3 grid, whose period is 4; a pixel whose coordinates are multiples of 12 lives on a hidden 10 × 10 grid, whose period is 30. Every divisor of 120 hides a coarser grid of this kind, and the pixels on it can return no later than the coarser grid’s period allows. The long cycles of 60 belong to the pixels that share no such factor and see the whole fine grid.

Halfway round, upside down #

There is one more structure in the return, and it is visible to the eye.

On a 74 × 74 grid the period is 114, and at step 57, exactly halfway, the picture reappears intact but turned through half a turn: every pixel $(x, y)$ has gone to $(-x, -y)$ modulo 74. That happens when the cat map’s matrix raised to half its period is minus the identity matrix, which is true for some grid sizes — 50, 74, 125 and 250 among them — and false for others, such as 64, 100 and 128. Between the start and the halfway point the image looks scrambled, and at steps 19 and 38 it shows scattered fragments; then, without warning, a coherent and recognisable upside-down picture appears and dissolves again. Anyone watching the map run would conclude that the picture had been destroyed, and would be wrong twice.

Chaos is not randomness #

The cat map is sometimes proposed as a way to scramble images for privacy, and its properties show why it is a poor one. It is linear, so knowing what it does to a few pixels reveals what it does to all of them; and it is periodic with a short, computable period, so anyone can unscramble a picture by applying the map the remaining number of times. The scrambled frames look random, but they contain the picture exactly, encoded by a rule that can be inverted at a glance. The planes a recurrence cannot leave found the same weakness in linear random-number generators, whose outputs look random and lie on a few planes.

What sensitive dependence describes is a loss of predictability from approximate knowledge. A measurement of a starting point to twelve decimal places is useless after 27 steps of the continuous cat map. Exact knowledge loses nothing: on a grid, where every state is known exactly, the map is perfectly predictable, and it is only the eye, looking for a picture and not finding one, that sees randomness. The chaos lives in what an observer with finite precision can tell, not in the map. On the continuous torus the same point can be made about pictures rather than points. The cat map is mixing: take any two regions of the square, and after enough steps the share of the first region that lies in the second approaches the second region’s area, as if the first had been spread uniformly. That is what the noisy frames show, and it is a statement about averages over regions, which is all an observer with finite resolution ever sees. On a grid the averages even out in the same way for a while, and then the finiteness reasserts itself and the picture comes back.

What the pictures cannot show #

The periods are computed for every grid up to 600 and the bound $3N$ holds for all of them; that it holds for every grid is Dyson and Falk’s theorem, not the figure’s. The relation between the cat map’s period and the Pisano period is checked for each $N$ in that range and proved in general by the matrix identity above. The separation curve is computed in double-precision arithmetic, which holds a millionth of a millionth accurately for the 27 steps that matter; after the points are a square apart the curve shows only that they are far apart, not where they are.

The figures also cannot show the continuous map’s long-term behaviour, which is where its chaos lives. The grid’s exact return is a property of the grid; on the true torus most points never return exactly, and the pictures of pixels show a finite shadow of a map whose orbits are infinite.

Still open: grids where the period does not grow #

How the period changes from a grid of side $p$ to a grid of side $p^2$ is usually simple: for a prime $p$, the period on the $p^2$ grid is $p$ times the period on the $p$ grid. No prime is known for which the period stays the same — for which the Fibonacci numbers modulo $p^2$ repeat as soon as they do modulo $p$. Such a prime is called a Wall–Sun–Sun prime, after D. D. Wall, who asked the question in 1960, and the brothers Zhi-Hong Sun and Zhi-Wei Sun, who connected it in 1992 with Fermat’s last theorem. Computer searches have checked every prime into the quadrillions and well beyond, and found none.

Heuristics suggest there should be infinitely many, very rare, since each prime has roughly a one-in-$p$ chance of the coincidence. No one has found one, and no one has proved there are none. For the cat map the question is concrete: is there a prime $p$ such that a picture on a $p^2 \times p^2$ grid returns as quickly as one on a $p \times p$ grid? The map that scrambles a picture in three steps and restores it in thirty leaves that one open.