The values that keep arriving

An octal game is three digits and a rule: how many counters may be taken, and whether the heap may be emptied, left whole, or split in two. The whole of its theory is one sequence — the Grundy value of a heap of each size — and the whole of the open problem is whether that sequence eventually repeats. Every value in it is a Nim heap in disguise, so the sequence is the game. Every finite subtraction game does, which is a theorem; adding the ability to split a heap in two removes the theorem and nobody has replaced it.

Some do. ·137 settles into a period of 34 from heap 52, and once it has, every heap of every size is answered by a table with 34 entries in it. Most do not, or rather nobody knows: ·007 has been computed to hundreds of millions of heaps and no period has appeared.

There is a way to watch the question that does not involve searching for a period at all.

The alphabet, and why it decides everything #

If a sequence is eventually periodic, the values it uses are the values in the preperiod plus the values in one period, and that is a finite set. The count of distinct values seen so far is therefore a non-decreasing bounded function of how far the search has looked, and it stops rising for good at the end of the first period.

So a rising alphabet is a proof — a short one, and an unconditional one — that no period has started yet. It is weaker than “there is no period”, and it is the strongest statement a finite computation can make.

The two directions are not symmetric. A flat alphabet is not evidence of a period: a sequence can use nine values for ever in an order that never repeats. But a rising one settles the question in one direction, and it settles it without any of the machinery a period search needs.

A solved code shows both halves at once. ·137 is Dawson’s chess doubled, and after heap 52 its sequence is a loop of 34 values drawn from an alphabet of nine — so its curve is flat from very early and stays flat however far the window is widened, which is what naming a game with a number buys once the number is available. The period is the harder half to establish and the alphabet is the half a reader can watch.

What the survey shows #

Six codes. Two have known periods and their alphabets are nine and eight values, flat from early on. Two — ·007 and ·6 — are still climbing at the right-hand edge of the window: 187 distinct values and 162, with largest values of 193 and 168.

The other two are the interesting middle.

·127 uses 22 values in six thousand heaps and picked up its twenty-second late in the window, so it counts as still growing but barely. ·106 uses 24 values, and stopped: its alphabet had reached 24 by the halfway point and did not move again. No period has been found for it, and its alphabet has closed.

That combination is not a contradiction and it is worth stating plainly, because it is exactly the case that separates the diagnostic from the question. A closed alphabet with no period is possible: the sequence has finitely many values and arranges them in an order that has not repeated inside the window. It is the case where this measurement has nothing more to say, and there is one of it in six.

The rare values, measured #

The reason the alphabet matters to the people who work on these problems is a proposal called sparse space, and it is worth measuring rather than describing.

The hope is that the values of an unsettled game split into two groups. A common set, occurring with positive density, containing most of what the sequence does; and a rare set of large values that turn up occasionally and thin out as the heaps grow. If the rare values are sparse enough, a periodicity argument can be run on the common part and the rare ones handled as exceptions — which is how several of the solved octal games were actually solved — including the one Dawson’s chess problem turned out to be.

That is the wrong direction. The rare values are not thinning out over this window; they are taking over. By the last thousand heaps, five heaps in six carry a value outside the twenty-two commonest, and eight of the 187 values appear exactly once in six thousand heaps.

The contrast with a settled code is total. ·137 uses nine values, all of them common by any definition, and the rare share is zero in every block — as it must be, since a periodic sequence’s values all occur with positive density. The same is true of ·127 and ·106, whose alphabets are small enough that the twenty-two commonest are all of them.

What the measurement does and does not license #

Care is needed here, because the measurement is easy to over-read in both directions.

It does not show that sparse space fails. The proposal is about the infinite sequence, and six thousand heaps is not a window in which the asymptotic behaviour of anything is visible. A sequence whose rare share rises to 90% and then falls away to nothing would look exactly like this over these blocks.

It does show that the first six thousand heaps of these two codes give no support to it, which is a different and smaller statement, and one that is worth having written down. The literature on octal games contains a good deal of hope expressed as expectation, and a measurement that runs against the hope over the range anybody can compute is more useful than a repetition of it.

The alphabet is a number, not just a direction #

“No period has started yet” is the weakest thing the measurement supports, and it is leaving a quantity on the table. A rising alphabet gives a lower bound on any period there might be, and the bound is arithmetic.

Suppose the sequence is eventually periodic with preperiod $q$ and period $p$. Then every value that ever occurs occurs somewhere in the first $q + p$ heaps — after that the sequence is repeating, so nothing new can appear. So if a value turns up for the first time at heap $N$, then

$$q + p \;>\; N.$$

Not $q+p \geq$ the alphabet size, which is the weaker reading; $q+p$ exceeds the position of the most recent first appearance, wherever that happens to be.

For ·007 the last new value arrives at heap 5,997, three heaps from the edge of the window. So any period of ·007 has preperiod plus period greater than 5,997 — a hard number, from one pass and a set.

For ·6 it is worse: its most recent new value arrives at heap 6,000, the very last heap computed. The bound is therefore whatever the window is, and it will move every time somebody widens it.

Checked where the answer is known #

A bound is worth what its behaviour on a settled case says, and there is one to hand.

·137 picks up its ninth and last new value at heap 85. So the bound says its preperiod plus period exceeds 85 — that is, is at least 86.

Its preperiod is 52 and its period is 34. Fifty-two plus thirty-four is 86.

The bound is exactly tight, on the one code in the survey where the truth is available to check it against. That is a considerably better recommendation than a bound that merely holds: it says the quantity being measured is not a loose proxy for the period but the period’s own footprint, and that a code which has stopped finding new values has, at that moment, finished laying it down.

What that does to the open cases #

Put the two together and the diagnostic reads differently.

For ·137 the alphabet closed at heap 85 and the period was complete at 86 — the alphabet stopped one heap before the sequence began repeating, which is as early a warning as the quantity can give.

For ·007 the alphabet was still open at 5,997, so if a period exists its preperiod and period together run past six thousand heaps. That is not a proof of anything about the infinite sequence, and it is a much sharper statement than “still climbing”: it converts an impression from a graph into a number that any future computation must respect, and which only grows as the window widens.

And it says exactly what a period search is up against. A search over $n$ heaps must consider candidate periods and candidate starting points, and the alphabet says the pair must sum past 5,997 before there is anything to find. Every candidate below that is ruled out by a set of 187 integers, computed in one pass, with no comparison of windows anywhere.

That is the diagnostic earning its place. It cannot say a period exists and it can say where one cannot be, and where one cannot be is most of the space a period search would otherwise walk.

How large the values get #

The alphabet counts distinct values; the other number worth watching is how big they get, and the two do not have to move together.

·007 reaches a Grundy value of 193 inside six thousand heaps, and ·6 reaches 168. Those are not typographical accidents: a Grundy value of 193 means a heap whose option set covers every value from zero to 192 and misses 193, which requires the option set to be enormous and the values below it to be spread just so — the mex doing something no small option set could do.

By contrast ·137 never exceeds nine, and ·106 never exceeds 23. A settled game’s values stay small because they have to: the period is the whole vocabulary, and a large value inside a short period would have to recur every period for ever, which the recursion below it cannot sustain.

So “large values appear” and “many values appear” are two symptoms of the same condition, and either is enough to say a period has not started. The first is cruder and more visible; the second is what the diagnostic above actually counts.

Why the alphabet is cheap and the period is not #

A period search over $n$ values costs a comparison for every candidate period and every candidate starting point, and the candidate periods are bounded by nothing better than $n$. Worse, a period found has to be certified: a repeat over a window is not a period unless the window is at least as long as the largest move, since the recursion at heap $k$ looks back that far. A period is a proof only when the certificate is checked.

The alphabet costs one set insertion per heap. It answers a weaker question, it answers it in one pass, and it cannot be fooled by a coincidence — two values are the same value or they are not. That is the same virtue an exhaustive census has over a sampled one, at a much lower price.

That is the trade this page is about. Given a game nobody has settled, the alphabet is the first thing to look at, because it either rules out a period having started or it says nothing at all, and both answers arrive immediately.

What a certificate looks like is easiest to see in a game that has one. The subtraction game with moves one, three and four repeats a window of four consecutive values one period later, and four is the largest move, so the recursion at every later heap reads only heaps inside the window and the repetition propagates for ever. Every octal game that has been settled was settled by exhibiting a window like that one.

What a proof would have to do #

It is worth saying what would settle ·007, since the diagnostic above says only what has not happened.

A period is proved by exhibiting a window. Find a stretch of consecutive heaps whose values repeat one period later, make the stretch at least as long as the largest move the code allows, and the recursion is trapped: every heap beyond the window computes its value from heaps inside it, so the repetition propagates for ever. That is the whole argument and it is checkable by a machine.

The difficulty for a splitting game is that the largest move is not bounded. ·007 allows a heap to be split into two of any sizes, so the value at heap $n$ depends on heaps arbitrarily far below it, and there is no window past which the recursion cannot see. The certificate that works for a subtraction game has nothing to attach to.

That is why the sparse-space idea exists. If the values split into a common part with structure and a rare part that is genuinely rare, the splitting moves that reach far down mostly land in the common part, and the argument can be run there. The measurement on this page is a measurement of that “mostly”, and over six thousand heaps it is going the wrong way.

What the solver computed, and how #

Each sequence is generated by the ordinary octal recursion — for each heap, the set of values reachable under the code’s three digits, and the mex of that set — computed to six thousand heaps and cached.

The alphabet curve is a running set: insert each value, record the size at the end of each block. The blocks are twenty-four of 250 heaps, which is enough resolution to see a curve flatten and cheap enough to run on six codes.

The rarity measurement is the one with a methodological trap in it, and the trap is avoided explicitly. The commonest values are identified once, from the whole window, and that fixed set is then applied to each block. Re-identifying the commonest values inside each block would compare different sets of values from block to block and could not report a rise or a fall at all — it would report the same number every time by construction.

The check that could have failed is the flat codes. ·137 and ·17 have known periods, so their alphabets must stop growing and their rare share must be zero; a rising curve for either would mean the sequence generator was wrong rather than that something had been discovered.

The two codes in the middle #

·127 and ·106 are worth a paragraph each, because they are the cases a diagnostic exists to distinguish and a description would run together.

·127 uses 22 values and acquired its last one late in the window, which is the weakest possible form of “still growing”. Its rare share is zero at the cutoff used here, because 22 values are exactly the 22 commonest. A reader would be entitled to call its alphabet closed and wait for more heaps, and the honest report is that the measurement is at its resolution limit.

·106 is the one that says something. Its alphabet reached 24 by heap three thousand and did not move for the next three thousand; its largest value is 23; and no period has been found. So here is a game with a small, apparently closed vocabulary arranging it in an order that has not repeated in six thousand heaps — which is precisely the configuration the diagnostic cannot speak to, and the reason it is offered as a first look rather than as an answer.

Six codes, four verdicts: two settled, two still finding values, one at the resolution limit, one closed and unsettled. That distribution is more informative than any of the individual answers.

It is also a distribution that depends on where the window stops, and the cheapest way to see how much is to run the same measurement over a fifth of it.

So the awkward verdict is a verdict about a window and not about the game. At 1,200 heaps ·106 reads exactly as ·007 does — still climbing, no period — and the two only separate some three hundred heaps later, at heap 1,516. That is the resolution limit stated as a number rather than as a caveat, and it applies to the other five rows as much as to this one: every one of them is a statement about how far somebody looked.

Where the model stops #

Six thousand heaps and six codes. ·007 has been computed vastly further than that by people who work on it, and nothing here is news to them; what is here is the measurement drawn rather than described, on a window a reader could reproduce.

The classification into common and rare uses a fixed cutoff — the twenty-two commonest values — chosen so that the settled codes come out with no rare values at all. That is a defensible choice and it is a choice, and a trend that exists only at the chosen cutoff would be a fact about the choice.

The percentages move a great deal and the smallest rise across the five is 43 percentage points, so the direction is not something a different cutoff would have to be chosen carefully to preserve. What a wider cutoff does is make the first block’s share small — at forty values kept, only 9% of the first thousand heaps carry anything rare — which sharpens the contrast rather than softening it.

And the alphabet diagnostic has the asymmetry named above. It can rule out a period having begun; it can never rule one in, and ·106 is the standing reminder that a closed alphabet and an unsettled sequence are perfectly compatible.

Where the ladder goes next #

The rungs below establish what a Grundy sequence is and which of them have been settled. This rung is a diagnostic for the ones that have not, and a measurement of the hope that is usually attached to them. The rung above is the sparse-space argument itself: what a proof would have to establish about the common values, and whether the common set is closed under the operation such a proof needs.

Two neighbours are worth the trip. The sequence nobody has settled is the history of the open problem, and it is a longer history than most people expect. And a period is a proof is what a positive answer looks like — a window, a certificate, and a check that the recursion cannot see past it.