Differences round a ring

Here is a puzzle that takes ten seconds to explain, and that has been independently rediscovered by schoolchildren many times over. Write four whole numbers around a ring. Replace each by the size of the difference between it and its neighbour. Repeat. The Italian mathematician Enrico Ducci is credited with noticing, in about the 1930s, that the numbers always run down to nought. Its first published treatment is a 1937 paper of Ciamberlini and Marengoni, and it has appeared in hundreds of places since, often under the name of the four-number game.

The process has no parameters and it is hard to imagine a simpler way of iterating something. It shares its first idea with the cobweb diagrams for one-dimensional maps: follow the orbit until it does something recognisable. But the state is a whole ring, and the map is not smooth. What it does depends on the number of entries, and the dependence is the interesting part. Four entries finish. Three entries do not. In general a ring of $n$ always reaches nought exactly when $n$ is a power of two. And the proof of that is a statement about Pascal’s triangle.

Why four numbers stop #

The largest entry can never go up, since a difference of two non-negative numbers is no larger than either of them. So the entries stay bounded, and the orbit has to repeat. The only question is what it repeats through. There are two steps to the answer, and neither requires more than parity.

Suppose all four are even. Then they stay even, and dividing them all by 2 at any time changes nothing about the behaviour except the scale. So the only question is what happens to the pattern of odd and even. Working modulo 2, the absolute value disappears, since $|a - b| \equiv a + b$. The map on the pattern of parities is then a linear one: each new bit is the sum of two neighbours. Starting from any of the sixteen patterns on four bits, four steps of this reach all zeros. Therefore, after four steps all entries are even. After four more steps all entries are divisible by four, and so on. Since the largest entry does not grow, the only number divisible by every power of two below it is nought.

So the four-number game has a very short proof, and it reveals what matters. The numbers themselves do almost nothing. Everything is decided by the parity map, and the question of whether a ring of a given size finishes becomes the question of whether that map on bits is nilpotent.

Pascal’s triangle on a cylinder #

The bit map is the most familiar linear rule there is. A cell is replaced by the sum of itself and its neighbour modulo 2. Read the ring of $n$ bits as the coefficients of a polynomial in $x$, where multiplying by $x$ rotates the ring: that is, work modulo $x^n + 1$. One step of the map is multiplication by $1 + x$. After $t$ steps it is multiplication by $(1 + x)^t$, whose coefficients are the row $t$ of Pascal’s triangle modulo 2, which is the Sierpiński pattern.

The key fact is one of the prettiest in the arithmetic of the triangle, and it is the case $p = 2$ of the row that proves a prime. Row $2^k$ modulo 2 has only its two ends: $(1 + x)^{2^k} = 1 + x^{2^k}$. So if $n = 2^k$, then $(1 + x)^n = 1 + x^n$, which is nought modulo $x^n + 1$. Every start dies in at most $n$ steps. In the left part of the figure, that is what happens to a random ring of sixteen: the triangle grows, its right edge wraps round the cylinder, and at step sixteen the two ends of the row land on the same cell and cancel.

For $n$ not a power of two, write $n = 2^a m$ with $m$ odd and greater than 1. The polynomial $x^n + 1$ has a factor $x^m + 1$, which contains factors other than $1 + x$. Then multiplication by $1 + x$ is not nilpotent on the ring: it acts invertibly on the part corresponding to the other factors. So a ring whose parity falls in that part cycles for ever with period equal to the multiplicative order of $1 + x$ there. The ring of fifteen in the figure settles into exactly that behaviour. There is no finishing, because there is nothing that could finish it.

That also explains the behaviour of whole numbers on a general ring. After some steps, the entries are all either nought or a single value $c$. That is a binary ring multiplied by $c$, and from there on it behaves just as in the figure. The arithmetic has been washed out in a finite number of steps, and only the binary dynamics remains.

The periods #

The period at each size is a quantity of number theory, and it is unexpectedly erratic.

The values run 1, 3, 1, 15, 6, 7, 1, 63, 30, 341, 12, 819, 14, 15, 1, 255, 126, 9,709, 60, 63, 682, 2,047, 24, 25,575, 1,638, 13,797, 28, 475,107, 30, 31, 1, 1,023, 510, 4,095, 252, 3,233,097, from $n = 2$ to $n = 37$. The order of $1 + x$ modulo a polynomial depends on how $x^n + 1$ breaks into irreducible factors over the field of two elements, and that depends on the order of 2 modulo $n$, the least $e$ with $2^e \equiv 1 \pmod n$. Each irreducible factor of $x^n + 1$ has degree dividing $e$ for odd $n$, the arithmetic of the fields built from two elements, and $e$ is itself a divisor of the exponent Carmichael found smaller than Euler’s. A prime such as 7 has $e = 3$, the small value $2^3 \equiv 1$, and so 7 has period only 7. By contrast 19 has 2 as a primitive root, $e = 18$, and its period is 9,709. A prime for which 2 generates all the residues has a very large field to work in. That is the question Artin’s conjecture on how often two generates every remainder addresses, and which is open for this very reason.

At Mersenne numbers the pattern collapses. For $n = 2^k - 1$, the period is exactly $n$: 3 at 3, 7 at 7, 15 at 15, 31 at 31. Here $2^k \equiv 1 \pmod n$ and so $(1 + x)^{2^k} = 1 + x^{2^k} = 1 + x$ in the ring, which is to say $(1 + x)^{2^k - 1} = 1$ on the part that matters. The period is forced to be small by the same identity that kills a power-of-two ring. It is the same identity with an extra rotation.

So 31 has a period of only 31, despite being large and prime. And a little further on, the next Mersenne prime 127 has a period of only 127, whereas 37 has 3,233,097. These jumps have nothing to do with how large or how prime $n$ is. Numbers of the form $2^k + 1$ are a neat case too, with period $(n - 1)^2 - 1$: the table shows 9 with 63, 17 with 255, 33 with 1,023. Between such families the values look random, and that is exactly what the arithmetic of the order of 2 predicts.

Most of the words are on cycles #

A cycle can be long and yet the map might waste a lot of time getting there. On odd rings it wastes none.

The map adds a word to its own rotation, so what comes out always has an even number of ones, since each one is counted twice. On an odd ring that is the only restriction: the map sends the $2^{n}$ words onto the $2^{n-1}$ even-weight ones, and each of those has exactly two preimages, a word and its complement. So after one step the orbit is already on a cycle. Reading across the table, seven has 64 cycle states among ten cycles, the longest of length 7. Fifteen, with a tiny period, has 1,096 cycles. Five has only 2 cycles, the zero word and one huge cycle of 15, which is the shape of a maximal linear feedback register.

That is worth pausing on. A ring of five bits under this map behaves very like the shift registers that generate pseudorandom sequences. Those work on the same linear algebra, multiplying by $x$ modulo a chosen polynomial. Here the multiplier is $1 + x$, and the polynomial is not a free choice. When the order happens to be large the behaviour is like a good register, and when it is small the map is merely periodic. Even-length rings behave differently, because $1 + x$ is then not a unit even on part of the ring, and a transient appears whose length is the power of 2 dividing $n$. The nilpotent part and the cycling part sit side by side in the ring, one killing its share of a word, and the other cycling.

Three numbers, and why rotation matters #

The smallest ring that does not finish is the ring of three, and its whole behaviour can be written down in a line. Start from 0, 0, 1. The differences go round to 0, 1, 1, then 1, 0, 1, then 1, 1, 0, then 0, 1, 1 again, and it never leaves that cycle. Every whole-number start on three cells falls onto a multiple of this cycle. So a triangle of numbers is the mirror image of a square of them: the square always dies and the triangle only ever dies if it started with all three equal, in which case it needs just one step.

Rotating a ring changes nothing about how it evolves, except that the result is rotated too. So cycles come in families, each a rotation of the others, in exactly the way that necklaces do, and the counts of cycles in the table are constrained by that symmetry. On the ring of five, the fifteen states of the long cycle consist of three rotation classes, and a word and its five rotations appear at regularly spaced positions along the cycle. That spacing is a fact about the map as well: multiplying by $x$ commutes with multiplying by $1 + x$, so a rotation sends each orbit to an orbit. On the ring of five, $x$ is itself a power of $1 + x$, and this means that one rotation is the same as running the map forward by a fixed number of steps. In other words the ring cannot tell turning from waiting.

The same algebra says what a single 1 among noughts does. Its orbit is the row-by-row picture of the powers of $1 + x$, wrapped round. It reaches the longest cycle of the ring because it generates, under multiplication and rotation, everything that can be reached. So one bit is enough to learn the period, and the computation for each $n$ needs only one orbit and no search over starts. That is what makes it possible to compute the period at 37 with more than three million steps, whereas enumerating even the words of that length would need over a hundred billion.

Four numbers: how long it can take #

Now return to whole numbers and ask a quantitative question about the case that does finish. How long can four numbers last? The parity proof gives a bound in terms of the size of the entries. An exhaustive search gives the truth.

Searching every start with smallest entry nought, up to a largest entry of 149, the slowest starts have a distinct shape. For the largest entry 149, the slowest start is $0, 24, 68, 149$, and it takes sixteen steps. Each entry is a running sum of the numbers 24, 44, 81, consecutive terms of the tribonacci sequence, $T_{m+1} = T_m + T_{m-1} + T_{m-2}$, which runs 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149. So four numbers below 150 cannot last more than sixteen steps. The number of steps is a logarithm of the size, and the base comes from the growth of that sequence, $q = 1.8392867\ldots$, the real root of $x^3 = x^2 + x + 1$. The process runs a tribonacci recurrence backwards, as it were: the differences of four consecutive running sums reproduce a smaller instance.

That points to the next surprise. If whole numbers in that shape give the slowest finish, there should be real numbers in that shape that do not finish at all.

They do not. Start with $1, q, q^2, q^3$. The differences are $q - 1$, $q(q - 1)$, $q^2(q - 1)$, and $q^3 - 1$. The last is also $q^3(q - 1)$, because $q^4 - 2q^3 + 1$ factors as $(q - 1)(q^3 - q^2 - q - 1)$, and the second factor is nought. So the new ring is exactly $(q - 1)$ times the old one. So the shape repeats at each step at a smaller size, with a ratio of $q - 1 = 0.8393$, and it never reaches nought. The exact run goes on for ever. A computer in double precision follows it for forty steps, falling steadily, until the rounding of the numbers makes the shape inexact and the parity argument takes over. Real starts do not behave any better for most of the possible shapes: for real numbers almost all starts reach nought in finite steps, a theorem going back to work of the 1940s and 50s. This one and its images are the exceptions, and so the proof that whole numbers stop rests entirely on the fact that whole numbers cannot shrink for ever.

A map without a derivative #

It is worth comparing this with the smooth iterations of a cobweb diagram. Those are maps on an interval, with derivatives that say whether a fixed point attracts or repels. The present map is piecewise linear, on a space with one dimension per ring cell, and it has an absolute value in it. Almost nowhere does the absolute value change its sign pattern at any given point, so locally the map is linear: at each stage it can be read as an integer matrix, with the signs dictated by which cell of a pair is larger. That matrix has entries 0 and $\pm 1$. So on each region of the space it can be analysed as a linear map, and the regions are polyhedra. The tribonacci constant comes from one such matrix, the one that the geometric start keeps selecting.

This gives a clean way of seeing the case $n = 4$. For the map to keep the same order of entries on every step, the matrix must have a positive eigenvector, and its eigenvalue is the scaling. There is exactly one such pattern, up to symmetry, and that is what the geometric start exhibits. Every other arrangement passes to another region. Most orbits switch regions until their parity collapses. The behaviour is an accidental analogue of the stable and unstable directions of a saddle: the geometric start lies on a special direction which is unstable in the arithmetic, and any whole-number perturbation falls off it.

What the computations show #

The figures here rest on exact arithmetic except where noted. The periods to 37 come from running the bit map itself on large integers and using a cycle-finding method from a single 1 among the noughts. It was checked against the published table through 23. In principle a ring can have different cycles with different lengths, and the printed value is the order of $1 + x$, the largest. The even-weight count on odd rings was tested for each size up to 17. The slowest four-number starts come from an exhaustive search with the smallest entry nought, at each largest entry shown, and so they are exact for those values. The statement that the record starts continue in the same pattern for all sizes is a theorem, cited rather than derived.

The real-number run is carried out in double precision and shown as such. It is included to illustrate the scaling, which the short algebra above establishes exactly. The statement about almost all real starts, and the accounts of the regions of the piecewise-linear map, are given in outline. The relationship between the order of 2 and the period has been stated informally: the exact result depends on the factorisation of $x^n + 1$, in which each factor needs its own analysis. Nothing computed here decides any case of Artin’s conjecture.

Still open: a formula for the period #

Is there a formula for $P(n)$? Bounds are known. For odd $n$ with $e$ the order of 2 modulo $n$, the same identity gives $(1 + x)^{2^e} = 1 + x^{2^e} = 1 + x$, so the period divides $2^e - 1$, and Michael Ehrlich’s paper of 1990 sharpened this when $-1$ is a power of 2 modulo $n$. At 19 the bound $2^{18} - 1$ is 27 times the true period. Which divisor is the period, as a function of the factorisation of $x^n + 1$, is not known. Nor is it known for how many $n$ the period is as large as possible; that requires the sort of control over the multiplicative order of $1 + x$ in a finite field that has no general theory, since the element $1 + x$ is not chosen for being a generator. A proof that $1 + x$ is usually a primitive element in fields of this shape would contain a version of Artin’s conjecture, and that is out of reach.

Two arguments at once #

Every ring of whole numbers falls within finitely many steps onto a cycle of entries nought and $c$, because modulo two the map is multiplication by $1 + x$. When the ring’s size is a power of two, a single identity in Pascal’s triangle kills everything; otherwise the period is the order of $1 + x$ in a ring of polynomials, which swings from 31 at $n = 31$ to 3,233,097 at $n = 37$ with the order of 2 modulo $n$. Four real numbers can avoid the end altogether by being a geometric sequence with the tribonacci ratio, and the slowest whole-number starts are its integer shadows.

So one puzzle holds two very different kinds of behaviour. There is an elementary parity argument which says the numbers can only go down. And there is a question about finite fields, hiding underneath, that nobody can finish. Both come out of the same absolute differences, and the size of the ring decides which of them is in play.