The period is small and the proof does not say so

A subtraction game is a heap and a list of legal takes. Take 2, 5 or 7 counters from the heap; whoever cannot move loses. It is the smallest interesting impartial game there is, and it is the only family in the subject where eventual periodicity is a theorem rather than a seventy-year-old conjecture.

The theorem is proved by pigeonhole and the proof hands over a bound. For a set whose largest move is m and whose Grundy values never exceed g, a window of m consecutive values determines everything after it, so once a window repeats the whole sequence repeats — and there are at most (g+1)^m windows.

For {2, 5, 7} that bound is 4⁷ = 16,384. The measured period is 22.

The proof, and what it is proving #

The argument is worth having in full, because its weakness is not a flaw in it.

Each Grundy value is a mex over the values at n − s for each move s in the set. So a value depends only on the m values before it, where m is the largest move. A run of m consecutive values is therefore a state, and the sequence is a walk on states with a deterministic next step.

A deterministic walk on finitely many states repeats. That is the whole proof, and it is airtight.

What it cannot do is say when. The number of states is (g+1)^m, which is what the pigeonhole gives, and the argument has no way to know that almost all of those states are unreachable. The bound is a count of everything the sequence could possibly be, and the sequence is one thing.

What the sweep found #

One hundred and twelve subtraction sets — every pair drawn from 1 to 8 and every triple from 1 to 9 — computed to 400 values and searched for a period.

Every one of them is periodic, which is the theorem doing its job. The interesting numbers are the sizes.

The longest period is 22, for {2, 5, 7}, whose largest move is 7. The median period across the sweep is 10. The ratio worth quoting is period against largest move, because that is the quantity a rule of thumb would predict: the worst in the sweep is 3.14, again for {2, 5, 7}.

Two of those rows are what makes a strip a risky instrument rather than a picture. Eighty-four of the 112 sets have a period longer than their own largest move, so the window that certifies a period is nearly always shorter than the pattern it certifies. And seven have a preperiod longer than their period — {3, 5, 9} takes fourteen values to settle into a pattern two long, which is seven repetitions’ worth of irregularity in front of it.

The rule of thumb, and the set that breaks it #

Anybody who has computed a few of these sequences arrives at a working rule: the period is at most about twice the largest move. It is not in the literature as a theorem, it is the kind of thing that gets passed on, and across this sweep it holds 111 times.

{2, 5, 7} breaks it. Its largest move is 7, so 2m + 2 is 16, and its period is 22.

One counterexample in 112 is exactly the density that makes a rule of thumb dangerous. It survives every casual test, it is right often enough to feel like a fact, and the case that breaks it is not exotic — three small numbers, none of them larger than seven.

This is the same shape as the Fibonacci-base rule this site got wrong, which passed 3,572 of 3,600 positions, and the same shape as the width at which a Kōnane row can be cut, where the success rate improves with the parameter and never reaches one. A rule that is right 99% of the time is not a weak theorem. It is not a theorem.

Why the periods stay small #

Nothing above explains why 22 rather than 16,384, and the honest answer is that nobody has a theorem — but the mechanism is visible in the sequences and worth stating as a conjecture rather than a result.

The states the proof counts are windows of m values drawn from {0, …, g}. Almost none of those windows can occur. A window is produced by the mex rule from the window before it, and the mex rule is heavily constrained: a value can only be large if several distinct smaller values are reachable, which needs the window to contain several distinct values in particular places.

So the reachable part of the state space is tiny compared with the whole, and the sequence walks around inside it. Sweeping the sets shows the consequence: the Grundy values of a set of two or three moves never exceed 3 anywhere in this sweep, where the pigeonhole bound assumed they might exceed 3 everywhere at once.

That is a general lesson about pigeonhole bounds. The count is over configurations, and the process visits a subspace. The same gap turns up wherever this site prices a search — the recursion tree against the position graph is exactly the difference between how many routes there could be and how many positions there are, and the ratios there run to millions.

What makes the subtraction case sharper is that the gap is not a saving to be engineered. Nobody is exploiting it; it is simply how the sequences behave, and the bound was never near the truth.

The gap is a reachability ratio, exactly #

The section above calls the small reachable subspace a conjecture. It is not one — it is an identity, and stating it turns the essay’s headline gap from an unexplained discrepancy into a measurement of one specific thing.

The sequence is a deterministic walk on windows: each window determines the next, with no choice anywhere. A deterministic walk on finitely many states runs through some states once and then cycles, so the number of distinct states it ever visits is exactly the preperiod plus the period.

For $\{2, 5, 7\}$ the preperiod is nought and the period is 22. So the walk visits exactly 22 of the 16,384 windows the pigeonhole counts — one window in seven hundred and forty-five, which is the same factor of 745 the essay opens with, arrived at from the other end.

That is worth saying plainly. The proof’s bound and the measured period are not two estimates of one quantity that happen to differ. They are the size of the state space and the size of the orbit, and the ratio between them is not an error in the proof — it is the answer to a different question, which nobody has ever claimed the pigeonhole could answer.

So “why is the period small” and “why are so few windows reachable” are the same question, word for word, and the second is the one with a mechanism attached.

And the answer to it is a different number for every set, which is the half of this a single ratio cannot show.

So the headline gap is mostly a fact about an exponent. The pigeonhole is not loose; it is loose for a large largest move, and the reason that reads as a flaw in the proof is that the sets anybody writes down to illustrate it have largest moves of seven and nine. Take one or two counters and the bound is nine windows against a period of three, which is the sort of agreement a bound is supposed to have. The proof is doing the same thing in both cases; only the exponent has changed.

One constraint that is visible #

Part of that mechanism is visible without any theory, in the positions of the zeros.

A value is nought exactly when the mex has nothing to exclude — when none of the positions reachable from it is worth nought. So $v_n = 0$ precisely when none of $v_{n-2}$, $v_{n-5}$, $v_{n-7}$ is nought, which is a statement with no mex in it at all: no two zeros may be 2, 5 or 7 apart.

Run the sequence out and the zeros land at $0, 1, 4, 10, 13, 14, 22, 23, 26, 32, 35, 36, \ldots$, and no two of those differ by 2, by 5 or by 7. They are, in fact, the greedy such set — take every position that is not excluded by an earlier one — because a position with no nought below it at a legal distance is a nought, with no discretion involved.

That single constraint prunes the window space savagely before anything else is considered. A window of seven values is $4^7$ arrangements only if the noughts inside it may fall anywhere; forbidding two noughts at distance 2, 5 or 7 removes most of the arrangements, and the corresponding constraints on where the ones and twos may sit remove most of what is left. The count of 16,384 assumed all four values could appear in all seven places independently, and they cannot appear independently in any two.

That is not a proof of a small period — the constraints above are necessary and nobody has shown them sufficient, and this site does not claim theorems it has only tested. What it does is locate where the pigeonhole is being generous: not in the pigeonhole, which is exact, but in the assumption that a window is an arbitrary tuple. A window is an arbitrary tuple in the same sense that an English word is an arbitrary string of letters, and the bound is the count of strings.

Eventually, and how eventual #

The theorem says eventually periodic, and the word does real work.

The largest preperiod in the sweep is 21, for {2, 8, 9}, whose period is 11. There are sets whose preperiod is longer than several repetitions of their own period, and a search that stopped early would report a period that is not one.

That is why a period is a proof insists on the window rather than on the repetition. Seeing a pattern repeat twice is evidence; seeing m consecutive values recur is the theorem’s hypothesis, and only the second one settles anything.

Why this family is settled and its cousin is not #

The natural next question is why the same argument does not settle the octal games, which look like the same kind of object.

An octal game allows a move to split a heap into two, and that is the whole difference. A subtraction game’s position is one heap and its value depends on the m values before it. An octal game’s position is a multiset of heaps, and its value depends on the exclusive or of the parts — so the state is not a window of recent values, and there is nothing finite to pigeonhole.

The best-behaved octal game shows how little that buys. Dawson’s chess as the code ·137 is eventually periodic with period 34 from heap 52, with a handful of exceptions before that which never recur — a sequence every bit as settled as {2, 5, 7}'s, and settled by computation rather than by any theorem. Nobody has proved that every finite octal game is eventually periodic and nobody has found one that is not.

So the two families differ in exactly one clause of the rule, and the difference is the difference between a proof and a seventy-year search. The sequence nobody has settled is the essay about the search.

What the small periods are worth #

An honest accounting of what the sweep buys, since it proves nothing new.

It makes the game cheap to play. A period of 22 means every position of every size is settled by 22 numbers and a remainder — Nim is easy in binary, and a subtraction game is easy modulo its period. The proof’s bound of 16,384 would make it cheap too, and by a much less comfortable margin.

It says the bound is not tight and nobody has closed the gap. There is no theorem in the literature giving a small bound on the period of a subtraction game in terms of its moves. The measured periods say such a theorem is plausible; {2, 5, 7} says any simple form of it has to allow more than 2m + 2.

And it is worth remembering what the sequence is for, since the essay has spent its length on the sequence rather than on the game. A heap of twelve under take-2-5-or-7 has a Grundy value; that value names a Nim heap the position is equal to, in the strong sense that the two are interchangeable inside any sum whatever; and the equality is checked rather than claimed, by playing each heap against each Nim heap and comparing the outcome with what the nim-sum predicts. That is what makes a periodic strip a complete description of the game rather than a curiosity about a sequence.

Where the model stops #

112 sets is a sweep, not a family. Every pair up to 8 and every triple up to 9 is a manageable range and it is not the range where anything interesting would hide. A set with four moves, or with moves in the hundreds, could have a period this sweep would never see.

400 values is a horizon. The period search runs over 400 computed values, and a set whose preperiod exceeded that would be reported as unsettled rather than as long — no set here was, and a longer sweep is the only way to know that stays true.

And “the proof gives 16,384” is generous to the proof. The bound counts windows of m values, and it assumes the values are bounded by the observed maximum. A proof with no observation in it cannot even assume that: the Grundy values of a subtraction game are bounded by the size of the set, so the honest a-priori bound is larger still.

All of which places this family at the easy end of a subject whose general problem is PSPACE-complete. The Grundy value of a small subtraction game is one linear pass, and with a period in hand it is a remainder and a lookup — which is the whole practical content of everything above.

Reading the extremes off the strips #

The two ends of the sweep are worth putting side by side, because they fail in opposite directions and a rule of thumb has to survive both.

{2, 5, 7}: period 22, preperiod 0. The sequence is periodic from the first value and the pattern is long. A reader watching the values go by would see no repetition for twenty-two steps and might reasonably conclude there was none.

{2, 8, 9}: period 11, preperiod 21. The sequence has a pattern and does not start using it until the twenty-second value. A reader watching would see several apparent regularities before the real one, and each of them would be wrong.

{3, 5, 9}: period 2, preperiod 14. The eventual behaviour is as simple as it gets — the values alternate — and it takes fourteen values of irregularity to arrive.

No single strip length is adequate to all three. Twenty-four cells is enough to see {3, 5, 9} settle and not enough to see {2, 5, 7} repeat; forty cells shows {2, 8, 9} properly and wastes most of its width on {1, 2}. The figures here are sized per set for that reason, and the practice generalises: a strip whose length was chosen before the sequence was computed is a strip that will eventually lie about one.

What the picture cannot show #

A Grundy strip shows a few dozen values, and every claim in this essay is about a few hundred or a few thousand.

The period is the clearest case. A strip of thirty cells showing a period of 22 shows a little over one repetition, and one repetition is not evidence of anything — the figure’s period was found by searching computed values well beyond the drawing, and the number of values searched is printed on it precisely so a reader does not take the picture as the argument.

The other thing no strip can show is the sweep, and the three tables above are what stands in for it. A figure of 112 strips would be unreadable, so what is drawn is the counts, the extremes and the one red row — which is enough to check every number in the prose and is not enough to see a set behave oddly in the middle of the distribution. A reader who wants the row for {4, 6, 7} is not going to find it here.

The third is the mechanism. Three sections above argue that the reachable window space is small because the mex rule constrains which windows can follow which, and nothing on this page draws a window or a transition between two of them. The reachability ratio is measured; the reason for it is asserted, and the difference is stated rather than hidden.

What a sweep is for #

This essay proves nothing, and it is worth being precise about what it does instead, because the fleet’s habit is to measure claims rather than to repeat them.

It puts a number on a gap. “The proof’s bound is not tight” is a remark. “The proof’s bound is 16,384 and the answer is 22” is a measurement, and it is the difference between suspecting the theorem is weak and knowing by how much.

It finds the counterexample nobody was looking for. The 2m + 2 rule was not under suspicion. It came out of the sweep as one red row among 111 green ones, and a sweep is the only thing that produces that: a person checking sets by hand stops when the rule keeps working.

And it says what a stronger theorem would have to allow. Any bound of the form “period ≤ f(m)” has to satisfy f(7) ≥ 22, which rules out the obvious candidates and is a genuine constraint on anybody trying to prove one.

None of that is a substitute for the theorem, and the essay is not offering one. It is the difference between what is proved and what is true, measured on 112 cases — and measuring that difference is the only way to know which of the two a rule of thumb is closer to.

The convention, named #

Normal play, and one convention about the rules themselves.

A subtraction set is finite and fixed. Every result here depends on there being a largest move, because the largest move is what makes the state finite and the pigeonhole available. An infinite subtraction set — take any prime, take any power of two — is a different object entirely, and eventual periodicity is neither proved nor expected for those.

The second convention is that a player who cannot move loses. Under misère play the sequences above are unchanged and their meaning is not: the values still repeat, and what they say about who wins no longer follows from adding them, because the misère theory needs a quotient rather than a value.