Differences Around a Circle

Write non-negative whole numbers around a ring. For each position, find the absolute difference between its value and the value immediately clockwise, subtracting the smaller from the larger. The last position is compared with the first. Calculate every difference from the old ring, then replace all the entries together.

For 0, 1, 2, 3, the four comparisons give 1, 1, 1, 3. Subsequent rings are 0, 0, 2, 2; then 0, 2, 0, 2; then 2, 2, 2, 2; and finally 0, 0, 0, 0. The ring still has four places, but every value is zero after five steps.

The four-place integer rule always reaches all zeroes. With three places, a different outcome is possible: 0, 1, 1 becomes 1, 0, 1, then 1, 1, 0, then 0, 1, 1 again. Once an entire ring repeats, the same calculations repeat forever.

Two observations get you most of the way, and both of them are things you can see in the plate above.

The largest entry cannot increase. Every entry of a new row is a distance between two entries of the old one, so if the largest number in the ring is 9, no distance can exceed 9. The ring is therefore trapped: there are only finitely many rows it can ever hold, and it has infinitely many steps to take. So it must eventually revisit a row. And the rule looks only at the row it is given, so the moment a row recurs, everything after it recurs too. Every run either lands on all zeroes or ends up going round in a loop. There is no third possibility, and no run can wander forever.

Only evenness matters for a while. If you are wondering whether an entry is odd or even, the subtraction is easier than it looks: odd minus even is odd, even minus odd is odd, and like with like is even. That is the same table as addition. So if you throw away everything except the parity of each entry, the rule becomes "add the two neighbours" - and that rule you can follow with Pascal's triangle, because after $k$ steps each place is the sum of the entries $k$ places along weighted by binomial coefficients.

Put those together and you can see where the ring length gets its say. In a ring of four, after four steps the binomial weights are 1, 4, 6, 4, 1, and the four in the middle are all even; only the two ends survive, and both of them point at the same place, because going four steps round a ring of four is going nowhere. They cancel. Every entry is even. Halve the whole ring and start again with smaller numbers, and repeat until there is nothing left.

In a ring of three that never happens, and 0, 1, 1 is the reason why: it is odd in two places, and every row it produces is odd in two places too.

The sentence worth carrying away is this one.

The ring length decides whether the rule finishes. The numbers only decide how long it takes.

That is unusual. For nearly every other iteration on this site, the interesting variation is in the starting value: some Collatz orbits climb and some fall, some reverse-and-add starts land in three steps and one has never landed at all. Here the starting value barely matters. Shift the whole ring by a constant and the run is identical from the first step; double it and the run is the same run with everything doubled. The behaviour lives in the shape of the ring, and the crudest fact about that shape is how many places it has.

Two things are being claimed on this page and they are not the same claim.

• This laboratory ran all ten thousand rings of four single digits and every one reached zero. That is a complete check of a finite box. It is a proof about those ten thousand rings and about nothing else, and if you raise the entries above 9 it covers none of them.
• Every ring whose length is a power of two reaches zero, from any start at all. That is a theorem, it is cited here, and this page does not prove it. What the page can do is show you the mechanism behind it, which is the parity argument in layer 5.

The failure cases go the other way round. To show that 0, 1, 2 never reaches zero you do not need a search at all: you need five rows and the observation that the fifth is the third. That is a proof, and the ledger marks it as one.

Let $v=(v_0,v_1,\dots ,v_{n-1})$ be a ring of non-negative integers, with indices read modulo $n$, and define the Ducci map

Write $D^k$ for $k$ applications, and call $v$ vanishing if $D^k(v)=0$ for some $k$.

1. ${\max }_{i}D(v{)}_i\le {\max }_i{v}_i$ for every $v$. Proved.
2. Consequently every orbit is eventually periodic: it reaches $0$ or enters a cycle. Proved.
3. $D(v+c1)=D(v)$ and $D(cv)=cD(v)$ for every constant $c\ge 0$. Proved.
4. Every $v\in \{0,\dots ,9{\}}^4$ is vanishing, and ${\max }_v\min \{k:D^k(v)=0\}=8$. Exhaustively checked over exactly that set.
5. Every $v\in {\mathbb{Z}}_{\ge 0}^n$ is vanishing if and only if $n$ is a power of two. Proved, and cited rather than reproduced here.
6. $(0,1,2)$ is not vanishing. Proved, by exhibiting its cycle.

Statement 5 is the one that makes the exploration; statements 4 and 6 are what this page can establish on its own, and they are consistent with 5 without being evidence for the half of it that quantifies over every length.

Entries never grow. Let $M={\max }_i{v}_i$. Each $D(v{)}_i=|v_i-v_{i+1}|$ is a distance between two numbers in $[0,M]$, so it lies in $[0,M]$ itself. ∎

Every orbit is eventually periodic. By the above the orbit stays inside the finite set $\{0,\dots ,M{\}}^n$, which has $(M+1{)}^n$ elements. An infinite sequence in a finite set repeats a value, and $D$ is a function of its argument alone, so from the first repeat onwards the sequence is periodic. If the repeated row is $0$ the orbit has vanished; otherwise it cycles. ∎

$(0,1,2)$ cycles, and therefore never vanishes. Two steps give $(0,1,2)\to (1,1,2)\to (0,1,1)$, and then $(0,1,1)\to (1,0,1)\to (1,1,0)\to (0,1,1)$. The fourth of those rows is the first, so the three rows repeat forever, and none of them is $0$. ∎

Why the length matters: the parity argument. Modulo 2, $|a-b|\equiv a+b$, so over $\mathrm{GF}(2)$ the map is linear: $D\equiv I+S$, where $S$ is the cyclic shift $(Sv{)}_i=v_{i+1}$. Hence

Take $n=2^m$ and $k=n$. By Kummer's theorem, $\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ is odd only for $j=0$ and $j=n$ when $n$ is a power of two, so the sum collapses to $I+S^n$. Shifting a ring of $n$ places $n$ times is the identity, so $I+S^n=I+I=0$ over $\mathrm{GF}(2)$: after $n$ steps every entry is even, whatever the ring was. ∎

That is the engine of the full theorem. The remaining move is that $D(2v)=2D(v)$, so a ring all of whose entries are even can be halved without changing the shape of the run; each block of $n$ steps halves the maximum entry, and after at most ${\log }_{2}M$ blocks there is nothing left. This page states that final assembly rather than developing it, and cites the theorem.

What is not proved here. The exhaustive sweep is a proof about its own box and no more. Ten thousand rings of four digits all reaching zero would remain true even if some ring of four five-digit numbers did not, and the reason no such ring exists is the argument above rather than the sweep. Symmetrically, the loops shown for lengths 3, 5, 6 and 7 prove only that some ring of each of those lengths fails. Plenty of rings at those lengths do vanish - any ring of equal numbers vanishes in one step.

What this laboratory computes. Rings of 2 to 12 places, entries from 0 to 9,999, with a ceiling of 200 steps per run. The arithmetic is ordinary exact integer arithmetic, and that is enough forever: entries can never grow, so a run that starts inside the safe range stays inside it. The exhaustive sweeps run every ring in a stated box and stop at 300,000 rings, which is why the by-length view uses entries of only 0 and 1 once the ring gets long.

A finite sweep does not become a theorem by being large. The most seductive thing on this page is that its two strongest statements agree. Every ring of four digits vanishes, and every ring of power-of-two length vanishes. The first was checked and the second was proved, and the checking did not contribute to the proof at all. If you want to feel the difference, raise the entry ceiling: the box grows, the answer does not change, and nothing has been learned about the ring of four entries that happens to be a million.

Where the mathematics is still moving. The two-outcome result and the power-of-two theorem settle the question for rings of non-negative whole numbers, but the same rule can be run on other things: real numbers, integers modulo something, elements of an arbitrary abelian group. Cycle lengths in those settings are studied and are considerably less tidy than the picture here, and this page neither computes nor claims anything about them.

Read this next to Gilbreath's difference field. It is the same operation - absolute differences of neighbours - performed on a line rather than a ring. A line of $n$ numbers has $n-1$ differences, so it narrows by one at every row and cannot help but run out. Closing the line into a circle keeps the width fixed forever, and that single change is what makes recurrence, loops and the whole question of an ending possible at all.