A repetition is a guess

A period is a proof when it has been checked through a window. Guy and Smith’s theorem for octal games says that if a game’s Grundy values repeat with period p from heap s onward, all the way to heap 2s + 2p + t — t being the number of digits in the game’s code, the most counters one move removes — then they repeat with that period for ever. A finite computation settles a claim about every heap there will ever be. It is one of the cleanest arguments in the subject, and the reason a search for periods is mathematics rather than numerology.

The theorem says nothing about a repetition that has not reached its window. And that is the state every sweep of octal games is in for most of its run: values computed to some depth, a pattern spotted, a period reported. The sequence nobody has settled is about the codes where no window ever closes. This essay is about the far more numerous codes where one does — and about what a reader would have believed on the way there, if the reader had believed what the values seemed to say.

The answer is measurable on every short code there is, because for the ones that settle the truth is known. Read each one heap by heap, report at every depth the pattern a sweep would report, and compare. The reports are wrong thousands of times. None of the wrong ones ever survives to its own window. And the right one usually arrives long before the window does, which is a different kind of problem: a correct belief that nothing yet entitles anybody to hold.

Reading the way a sweep reads #

A reading needs a rule, and the rule here is the plainest one, the one a period search uses: at depth d, with the values of heaps 1 to d − 1 in hand, take the earliest heap s and then the shortest period p such that every value from heap s on equals the value p heaps later, and the repeated stretch covers at least two full periods. Two periods is the least a pattern can show and still be a pattern. Heap 0 is left out, for a reason the last section comes to.

Every octal code of one, two and three digits was read this way — 511 codes, the digits running from 0 to 7 with the last one not 0. For each, the sequence was computed to 2,400 heaps and the reading taken at every depth until that code’s own certificate window closed. A code counts as settled when the reading at 2,400 heaps passes the window test inside that range, which makes its period a theorem rather than an observation. 291 codes are settled that way. The other 220 are not: 178 of them have a largest value still rising at 2,400 heaps, the games whose values grow and which no pure period can describe, and 42 have bounded values that have not repeated in a way the window can certify. Those 42 include the codes the subject has been waiting on for seventy years, and they are set aside here, because a reading of a sequence nobody has settled cannot be scored.

How often the first reading is wrong #

On 134 of the 291 settled codes, the first pattern the reading finds is the period, and it never changes. Those are the easy ones — short periods starting early, like Nim’s relatives, whose values are periodic almost from the first heap.

The rest are not easy. Nineteen change their reading once, and the count climbs from there: seventy change it between five and a hundred times, and eleven change it more than a hundred and fifty times. Across the 291 codes the reading reports a period that turns out to be false 4,684 times. Most of those are a cheap kind of mistake: 4,540 are a period of 1, reported because two neighbouring values happen to be equal and two equal values are, by the letter of the rule, two full periods. A sweep that wanted a longer stretch before believing would never make them.

The other 144 are not cheap. Sixty-eight have period 2, twenty-three period 4, sixteen period 5, and twenty-seven period 20. Those last belong to ·45 and its relatives, codes whose true period is 20 and starts at heap 498: on the way there the reading picks up period 20 several times from an earlier start, holds it for dozens of heaps, and loses it again. Dawson’s own game, ·137 — the chess problem that turned out to be an octal game — changes its reading 32 times before settling on period 34 from heap 52 at depth 120, and its certificate closes at depth 175.

Where the false readings come from #

The false readings are not spread evenly over the codes, and where they cluster says what fools a reader. The single strongest predictor is whether the true period starts at once. Of the 149 settled codes periodic from heap 1, 103 are read right from the first reading. Of the 142 whose period starts later — the codes with a pre-period, a stretch of values at the start that repeat nothing — only 31 are. A pre-period is where false readings live: 3,183 of the 4,684 start before the true period does, inside the stretch of values the period will never revisit, and they are local regularities in that stretch, read as if they were the pattern.

What they have in common with the truth is also telling. Leave aside the period-1 readings, which are only two equal values. Of the 144 longer false readings, 42 have exactly the right period and the wrong start, as ·226’s does, and 65 have a period that divides the true one — a period of 2 or 4 or 5 inside a true period of 20, say, the reading catching a fragment of the pattern and taking it for the whole. Only 37 have a period unrelated to the one that is proved. So a false reading is rarely a different pattern. It is usually the right pattern seen too early, or a part of it seen too soon, and the error is in where or how much, not in what.

That is the same lesson two counters and one displaced term drew among the hexadecimal games, where a family key read from a code’s first sixty values was a key on its pre-period rather than its period, and that the quantity that carried nothing stated as a caution: a sequence read to a fixed depth looks periodic from wherever it happens to have settled, and nothing in a finite stretch says this stretch is too early. The window is the only thing that does.

A false reading never gets there #

The theorem has a sharp consequence for the false readings, and it can be checked rather than merely believed. A reading of period p from heap s carries its own certificate requirement — the window 2s + 2p + t. If a reading ever lasted that long, the theorem would make it true. So no false reading can reach its own window, and how close each comes is the right measure of how convincing it was.

None does. The most convincing false readings get three quarters of the way: a period of 8 from heap 4 in ·176, and a period of 5 from heap 7 in ·226 and three of its neighbours, each holding to depth 20 of a window that needed 27. Most break near half way, and that is structural rather than lucky. A period starting near the beginning of the sequence needs only about two periods’ worth of values to be reported, and its window needs about twice that, so a reading that is reported at all is already about half way to its own proof. The distance from half way to the whole way is where the theorem does its work.

·226 is worth looking at whole, because its false reading is the most instructive kind. From heap 7 the values run 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3 — period 5, plainly, over more than two and a half periods. Heap 20 is worth 0. Then from heap 21 the same five values resume, 5, 1, 2, 3, 4, 5, 1, and this time they never stop. The false reading had the period exactly right and the start wrong. A single displaced value at heap 20 separates them, and no count of repetitions, however generous, could have told the reader at depth 20 which of the two situations it was in: the values seen were the values of a period-5 sequence either way. Only the window distinguishes them, by demanding the pattern hold until heap 27, by which time heap 20 has broken it.

No number of repeats is the right number #

The obvious repair to a reader fooled by two equal neighbours is to ask for more: believe a period only after three full repetitions, or four, or five. On these codes that works, after a fashion.

Demanding three repetitions still believes 668 false readings; four believes nine; five believes three, all of them runs of five equal values in ·154; six believes none. So a reader who waited for six full repetitions would never have been fooled on any of the 291 settled codes. That is a fact about 291 sequences. It is not a rule, because nothing about it carries to the next code: the false readings that survive five repetitions are runs of one repeated value, and a code whose values repeat a single number six times before changing would fool it, and nothing in the octal rule forbids one.

The theorem asks a different question. It does not count repetitions; it asks whether the pattern has held past twice its own start. For a period that starts early that is barely more than two repetitions — 2.1 on the most favourable code — and for one that starts late it is many: the median code needs 3.5, and ·45, whose period of 20 starts at heap 498, needs 27. The right number of repetitions depends on where the period starts, because what can go wrong is not that the period is miscounted but that something before the start is still reaching forward. A splitting move from a heap of size n reaches back to values below n/2, so a value far down the sequence can be disturbed by values near the start until the pattern has run twice as far as the start itself. A fixed count of repeats cannot know that. The window is built from it.

There is a cost to the window’s caution, and it is large. On every one of the 291 settled codes the reading is right before the window closes — usually by a few heaps, the median gap is four, but on ·45 and its relatives by five hundred. From depth 538 a reader of ·45 has the right answer and no right to it. That is the honest position of every period search that has not yet reached its window — the gap a strategy is not a certificate draws between knowing an answer and being able to show it — and what the arithmetic cost in 1956 priced from the other side: the work of proving a period is the work of computing to the window, and it can be far more than the work of finding it.

The window’s fine print #

The one choice in the reading rule that has not been justified is leaving heap 0 out. It matters, and it turns up the only place in the survey where the window itself can be fooled.

·4 is the game in which a move takes one counter and must leave two non-empty heaps. Heaps of 0, 1 and 2 have no move at all and are worth 0. Read from heap 0, those three values are a period of 1 from heap 0, and its window, 2·0 + 2·1 + 1, is three heaps: the reading has reached its own certificate. Then heap 3 is worth 1, because its one move leaves two heaps of one, a position worth 0, and the reading is false.

Allowing readings to start at heap 0 and rerunning the whole survey, this is the only false reading of all of them that reaches its window — which shows why the window is stated from heap 1 rather than a flaw in the theorem. The argument behind the window takes a heap well past the window, looks at a move from it, and shifts one of the heaps the move leaves down by a period, where the values are already known to repeat. A move that splits must leave two non-empty heaps, so heap 0 can never be one of the parts, and a pattern that includes heap 0 cannot be shifted onto one. From heap 1 on, the shifting argument always has somewhere to land, and in the survey none of the 4,684 false readings reaches its window.

The reading rule, and the certificate it is scored against #

Codes are written with a leading point, the k-th digit describing what may be done by removing k counters: 1 if the whole heap may go, 2 if one heap may be left, 4 if two non-empty heaps may be left, added together. Grundy values are computed by the mex rule from heap 0 to 2,400. A reading at depth d is the earliest start s ≥ 1 and then the smallest p such that values s to d − 1 repeat with period p and d − s ≥ 2p. A code is settled when the reading at 2,400 heaps satisfies 2s + 2p + t ≤ 2,400, which by the theorem makes it the period. A reading is false when it differs from the settled period in start or period, and it breaks at the first depth at which it no longer holds; how far it got is the last depth it held divided by its own window. “Right from” is the depth after which the reading never changes again. Codes whose largest value over heaps 1,600 to 2,400 exceeds that over heaps 800 to 1,600 are counted as growing; the split is a description, not a proof that they grow for ever.

Where three digits stop #

Every count here is for codes of at most three digits; longer codes have longer windows, and the false readings of a four-digit code could behave differently, though nothing here suggests how. The reading rule is one rule, the plainest; a cleverer reader — one that preferred longer periods, or discounted runs of a single value — would make fewer mistakes, and the six-repetition result says a reader can be tuned to make none on these codes, which is exactly why tuning on them proves nothing. The 220 codes without a certified period are outside the measurement, and they include every code a reader would most like to know about. And the survey can only show that no false reading reached its window among the codes it read. That none ever can, from heap 1 on, is the theorem, and the count is consistent with it rather than evidence for it.

Still open: the false readings of a game that grows #

The 178 codes whose values grow are read here as having no period, and that is correct and unhelpful: many of them are arithmetically periodic, their values repeating with period p plus a fixed increase each time, and there is a window theorem for that pattern too. Read the way this essay reads the pure periods, they would produce false arithmetic readings — a saltus that looks settled and is not — and the question is whether those break as early, relative to their own windows, as the pure ones do here, or whether a growing sequence can hold a false increase for longer. Three bits of rule found that the splitting bit separates the codes that settle from the ones that do not; whether it also separates the codes whose false readings are long-lived from the ones whose readings are honest early is the same question asked one level down.