Four values, and the sequence is settled for ever

A take-away game: a player removes one, three or four counters from the heap, and whoever cannot move loses. The Grundy values run 0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, 2, 3, 2, and onward for ever with period 7.

Establishing that the period holds for ever requires checking four of those numbers.

The claim, and what would normally be needed #

The value of a heap of $n$ is the mex — the least number not present — of the values of the heaps reachable in one move. For this game those are $n-1$, $n-3$ and $n-4$.

The rule is the whole of the arithmetic: the value of a position is the least non-negative integer that is not the value of any option, applied to values already computed. On the smallest interesting subtraction set it can be followed by eye.

The sequence repeats with period 7 is a statement about infinitely many heap sizes. Nothing about computation settles infinitely many cases by inspection, so one of two things must happen: either a proof by some other route, or a finite check with an argument attaching it to all the rest.

The second is what happens here, and the argument is three lines long.

The window, and why its length is the largest move #

Suppose the values are known to repeat with period $p$ across the window of heaps $s, s+1, \ldots, s+m-1$, where $m$ is the largest number of counters a move may take — four, for this game. So $g(k + p) = g(k)$ for each $k$ in that window.

Now take any $n \ge s + m$ and suppose, inductively, that $g(k + p) = g(k)$ for every $k$ below $n$ and at or above $s$. Then

$$g(n + p) = \operatorname{mex}\{\, g(n + p - t) : t \in \{1, 3, 4\} \,\}$$

and every $n + p - t$ on the right is at most $m$ below $n + p$ — which is to say, within the range the induction hypothesis already covers. So each option’s value equals the corresponding option’s value at $n$, the two mex computations are over identical sets, and $g(n + p) = g(n)$.

That is the entire proof. The window has to be $m$ long because a mex looks back exactly $m$ places; a shorter window would leave an option unaccounted for, and the induction would have nothing to stand on.

Which says that the certificate’s length is set by the rule and not by the pattern, and the cheapest way to see that is to change the rule and watch the window change with it while the period does something unrelated.

The check that could have failed #

The generator does not assume the window works. It computes the sequence, finds the period by search, and then verifies each of the $m$ pairs $g(k)$ against $g(k+p)$ — and throws rather than drawing if any pair disagrees.

Then it does something the proof does not need: it computes two thousand values and checks the period holds at every one.

That second step is corroboration rather than evidence, and it is worth having anyway. The proof establishes that the sequence repeats given that the window repeats; the two thousand values test whether the code computing the sequence agrees with the code checking the window. A proof about mathematics does not protect a figure from a bug in its own arithmetic.

Every finite subtraction set has one #

The stronger fact is that this is never a lucky find. Every subtraction game with a finite set is eventually periodic, and the proof is a counting argument rather than a construction.

The value of a heap depends only on the values of the $m$ heaps below it — so the state of the computation is the last $m$ values. Those values are bounded: a mex over at most $m$ options is at most $m$, so each of the last $m$ values is one of $m+1$ possibilities, and there are at most $(m+1)^m$ distinct states.

A computation with finitely many states, stepping deterministically, must revisit a state. From the moment it does, everything afterwards repeats. So a period exists, and the argument even bounds how long it can take to appear.

That bound is enormous and nearly useless in practice — for a set with largest move 6 it allows some 117,000 states before repetition — and the actual periods are tiny. What the argument gives is not the number but the guarantee: searching for a period in a subtraction game is a search for something known to be there.

What the window does not have to contain #

Two things are conspicuously absent from the certificate, and both are worth noticing because they are what makes it small.

The start of the sequence. The window sits at the start of the period, wherever that is, and the values before it play no part in the proof. A game whose values are irregular for fifty heaps and then settle is proved by four values at heap fifty, and the irregular fifty are of no interest to the argument at all. They must be computed to find the period, and they are not part of certifying it.

The rest of the period. For this game the period is 7 and the window is 4, so three of the seven values in a period are never checked against their repeats. They do not need to be: once the induction is running, they are produced by it. The window is a foothold and not a sample.

That second point is the one that surprises people, and it has a clean statement. The certificate’s size is governed by how far back the rule looks, not by how long the pattern is. A game with a long period and small moves has a short certificate; a game with a short period and one enormous move has a long one.

Which also says where the method would break. A rule whose moves are unbounded — take any number of counters at all, as in ordinary Nim — has no finite window, and the mex at heap $n$ depends on everything below it. Nim’s values are settled by a different argument entirely, and the fact that they come out as $g(n) = n$ is not something a periodicity check could ever have established.

What the certificate buys computationally #

Periodicity is not only a satisfying fact; it changes the cost of the game from linear to constant.

Without it, the value of a heap of a billion counters costs a billion steps — every value below it, computed in order. With it, the cost is a division: reduce the index modulo the period, look the answer up in a table of seven numbers, done. The input is a ten-digit number and the work is a handful of operations.

This is exactly the shape of a theorem replacing a search, with one difference worth noticing. The nim-sum was found by insight and proved afterwards. A period is found by search and proved by a check that the search itself can perform. The computation locates its own closed form, and the certificate is small enough to hand over.

That combination is rare enough to be worth naming: a decidable, finite, self-certifying discovery of an infinite regularity.

Where the argument gets much harder #

Move one game family across and the whole neat structure becomes an open problem.

An octal game allows a move to take counters and possibly split the heap into two, which is a richer rule than a subtraction set — and its values are the nim-sum of the parts, so the state of the computation is no longer just the last $m$ values.

Periodicity is still provable when it appears: the Guy–Smith periodicity theorem gives a window which, if it repeats, guarantees repetition for ever. The window is larger than in the subtraction case — it has to reach far enough to cover the splitting moves as well — but it is finite and checkable, so the same style of certificate applies.

What is missing is the guarantee that a period exists at all.

Ninety-eight against four is the price of the splitting move, and it is a price rather than a difficulty: the certificate is longer, and it is still a certificate. What the theorem does not supply is a reason to expect one to exist, and the next game shows what that absence looks like from the outside.

Some octal games fall into a period after a handful of terms. Some fall into one after hundreds of thousands. And for some — ·007 is the standing example — nobody has found a period after computing an extraordinary number of values, and nobody has proved there is none. The question of whether every finite octal game is eventually periodic is open, and has been since Guy and Smith raised it in 1956.

The same shape elsewhere in the subject #

A finite check standing in for an unbounded claim is not peculiar to Grundy sequences, and lining up the other instances makes the pattern easier to recognise.

A value of a game is one. The recursion terminates because play does, so a finite computation settles what would otherwise be a claim about every line, and the outcome classes fall out of the value rather than out of playing.

A misère quotient is one. Under misère play, positions are classified by how they behave in every sum — infinitely many sums — and the quotient is a finite object whose multiplication table settles them all.

A comparison is one. Deciding $G \ge H$ means asking whether $G$ is at least as good as $H$ in every context whatever, and it is settled by solving one game: play the difference and see who wins.

In every case the move is the same: replace a quantification over an infinite family with a computation on a finite object, and prove that the object suffices. That is arguably what mathematics does in general, and it is unusually visible here because in this subject the finite object is drawn — a strip of values, a multiplication table, a difference game — and can be looked at.

What the figure cannot show #

Three limits, and the first is the one this site has recorded before.

Absence of a period is not a result. A strip showing two dozen values and no marked period says only that none was found in the range searched. This site’s generators print how many values were examined for exactly that reason: no period in the 2,000 values computed is a statement a reader can weigh, and no period is not.

A certificate is about one sequence. The window proves this game’s period. It says nothing about the neighbouring game with one more element in its subtraction set, whose values may be completely different — the sequences are not continuous in the rule, and small changes to a code produce unrelated behaviour.

The bound on when a period must appear is not the period. The counting argument allows enormously long pre-periods; the games here settle almost immediately. Nothing observed on small examples licenses any expectation about how soon a period arrives in general, and the octal games are the demonstration.

What a reader can check for themselves #

The nice thing about this particular certificate is that it needs no machine, and following it once makes the argument concrete in a way the prose cannot.

Take the first game’s values: 0, 1, 0, 1, 2, 3, 2, then 0, 1, 0, 1, 2, 3, 2 again. The claim is period 7 from heap 0, and the moves take 1, 3 or 4, so the window is four values wide.

Check them: $g(0)=0$ and $g(7)=0$; $g(1)=1$ and $g(8)=1$; $g(2)=0$ and $g(9)=0$; $g(3)=1$ and $g(10)=1$. Four pairs, all equal, and the sequence is now settled for every heap size there will ever be.

To see why four is the right number, try three. With $g(0), g(1), g(2)$ checked, consider heap 10: its options are heaps 9, 7 and 6, and heap 6 is four back — outside the window, and outside anything the induction has reached. The mex on the two sides might then be taken over different sets, and the argument collapses. The largest move is not a safety margin; it is exactly the reach of the rule.

Anybody who wants a slightly harder exercise can take the second game, subtraction of 2, 5 and 6: period 11, largest move 6, six pairs to check. The values are on the figure above and the arithmetic takes a minute.

Who asked, and what is still open #

Guy and Smith’s 1956 paper introduced octal codes as a compact way of describing this whole family and observed that many of them are eventually periodic. The periodicity theorem that turns an observed repetition into a proof is theirs, and it is the reason searching for periods is a mathematical activity rather than a numerical one.

The open question they raised has outlived them both. Enormous computations have been thrown at ·007 and its relatives — sequences of billions of values, with no period and no proof of aperiodicity — and the honest position is that nobody knows.

It is a good place to end a rung about certificates, because it is the one case in this subject where the certificate exists, is checkable, would settle everything, and cannot be found. A period would be a proof. There may be no period. Nobody can currently tell which.

One more thing the search cannot decide #

There is a fourth possibility beyond periodic, not yet periodic and provably aperiodic, and it deserves a sentence because it is the reason the open question is hard rather than merely unanswered.

A sequence could be eventually periodic with a period so large that no computation will ever reach it. Nothing in mathematics forbids a game whose values settle down after $10^{40}$ terms, and such a game would be indistinguishable, to every search anybody will ever run, from one that never settles at all. The counting argument for subtraction games rules this out for that family by bounding the pre-period; for octal games no such bound is known, which is exactly what makes the question open rather than merely unresolved.

So the honest state of ·007 is a three-way disjunction: it settles somewhere beyond reach, it settles nowhere, or somebody finds the argument that decides which. Fifty years of computation has narrowed only the first branch, and narrowing it further is more computation of the same kind.

The certificate does not need the values to repeat #

The window argument is stated for a sequence that repeats, and it is worth noticing how little of it depends on that.

What the induction actually uses is that the values in the window determine the values one period later, through the mex over a fixed set of offsets. Repetition is one way for that to happen and not the only one. If instead

$$G(n + p) = G(n) + s$$

for a fixed $s$, the same check works with the same window: verify the relation on enough consecutive terms to cover the largest move, and the mex at every later heap is taken over a set that is the earlier set with $s$ added — so the mex itself comes out with $s$ added, and the induction carries.

That is the certificate for arithmetic periodicity, and it is exactly as finite and exactly as checkable as the one this page is about. The values never repeat, the sequence uses infinitely many of them, and the game is completely solved: one period, one constant, and a division.

The consequence is uncomfortable for the search rather than for the theory. A program looking for equality finds nothing in a sequence with a non-zero saltus, however long it runs, and reports the game as unsettled — which is what happened to a whole family, where a saltus turns out to be the ordinary way a hexadecimal game settles and exact repetition the special case. Reading no period found as not solved is therefore an error about the certificate and not about the game.

A certificate is a relation the window can verify, not a picture the eye can recognise, and equality is only the first relation anybody thought to look for.

Where the ladder goes next #

periodicity opens here with the certificate: a finite window, a stated relation, and a proof that the relation continues for ever.

The rung above is what happens when the certificate cannot be found. The sequence nobody has settled takes the Guy and Smith conjecture — that every finite octal game is eventually periodic — and asks what seventy years of arithmetic have actually established about it. The answer is uncomfortable and is the point: the evidence for the conjecture is entirely that nobody has found the counterexample they were looking for. Some codes have settled since 1956 and some have not, and the ones that have not are not converging on anything a reader could report.

That is the same three-way disjunction this page ends on, taken to the family rather than to one code, and it is where the distinction between no period found and no period stops being a caution about wording and becomes the whole content of a research programme.