The picture Bouton's proof leaves behind

Bouton’s 1901 argument is two closure properties of one set, and the set is the positions whose heaps exclusive-or to nothing.

(a) No move from that set stays inside it. (b) From any position outside it, some move enters it.

Together those say the set is exactly the losing positions, and the proof is four lines. The step from that to the 1935 theorem is one substitution — heap sizes become Grundy values — and this essay takes the argument across rather than the criterion.

The same two sentences, with a variable #

Replace the set whose heaps exclusive-or to nothing by the set of positions of Grundy value $v$ and the two properties read:

(a) No move from a position of value $v$ leads to a position of value $v$. (b) From any position of value greater than $v$, some move leads to a position of value $v$.

Those two sentences together are the mex rule. The least value not among a position’s options is the position’s own value, which is exactly (a) — its own value is absent — and exactly (b) — every smaller value is present.

So the Sprague–Grundy theorem is not a different kind of argument from Bouton’s. It is Bouton’s argument with a variable where his nought was, and the numbers that make it work are the ones the substitution supplies. Over five games and heaps to twenty-four, no move stays inside a class and no class above a value fails to reach it — not once.

Why the generalisation is the argument rather than a new one #

It is worth being exact about how little has to be added, because the usual account of the Sprague–Grundy theorem makes it sound like a different enterprise.

Bouton’s proof of (a) is one line: a move changes one heap, and changing one term of an exclusive-or that is nought cannot leave it nought. His proof of (b) is the construction everybody meets — look at the leading bit of the exclusive-or, find a heap with that bit set, and reduce it to match.

The generalised (a) is the mex rule’s own statement that a position’s value is not among its options’. The generalised (b) is the other half: every value below is among them. Neither needs a construction, because the mex rule is the construction — it defines the value so that both hold.

So the theorem’s proof is shorter than Bouton’s, not longer. What it needs that Bouton did not have is not an argument but the definition the argument is about, and a definition is exactly the kind of thing that does not look like a discovery until afterwards.

What the argument does not say, and everybody hears #

There is a third sentence nobody writes down and every reader of the proof supplies.

Bouton’s argument is about moving towards nought. A position with a non-zero exclusive-or has a move to a zero one; a zero one has no move to another zero one; so play descends. In Nim that picture is exactly right, and it is right in a stronger sense than the argument needs: every move in Nim lowers the Grundy value, because a Nim heap’s value is its size and a move makes a heap smaller.

The theorem does not say that. The mex rule guarantees every value below is reachable and says nothing whatever about above.

Ninety-nine of 444 chances here are taken. In the subtraction game $\{1, 2, 3\}$, 33 of 39 positions that could reach a higher value do; in $\{1, 2\}$, 23 of 26. And in Nim, none of 300.

What a climb looks like #

A single climb is easy to hold. Take the subtraction game $\{1, 2\}$, whose values run 0, 1, 2, 0, 1, 2, 0 and so on with period three. A heap of three has value nought. Its options are heaps of two and one, whose values are two and one.

So from a position of value nought, a player can move to a position of value two. The value went up, by two, in a game where every move removes counters and every position gets strictly smaller.

That is not an anomaly of a small heap. It happens at every multiple of three in that game, and the same shape appears in every game here whose sequence is not the identity. What it destroys is the intuition that a Grundy value is a measure of how much is left: the value is a label chosen by the mex rule, and the mex rule looks only downwards.

What a value is not #

The climbs settle a question that gets asked of Grundy values constantly and is rarely answered plainly: what does the number mean?

It does not mean how far from the end. A heap of three in $\{1, 2\}$ has value nought and a heap of two has value two, and the heap of three is further from the end.

It does not mean how good for the mover. Value nought is a loss and everything else is a win, so the number’s being large says nothing beyond its not being nought.

It does not mean how much is at stake, which is the temperature’s job in the partizan theory and has no counterpart here.

What it means is exactly one thing: the size of the Nim heap this position can be exchanged for. That is the whole content of the theorem and the whole content of the number, and the reason the value can climb is that the exchange rate has no reason to be monotone in anything a player can see.

Why the extra property is invisible from inside Nim #

This is the fourth time the same shape has turned up here and it is worth naming it once properly.

Nim has a property the theorem does not require — the values descend — and in Nim that property is free, because the value is the size and the size goes down. A person proving the theorem about Nim would have no way to tell which of the two facts their proof was using, because the two coincide on every position they could look at.

The consequences ran through the whole decade after 1901. The criterion transplants and is wrong; the method is complete and proves nothing; the missing ingredient is a substitution that is invisible in Nim. And now the argument’s own imagery is a fact about Nim rather than about the subject.

Everything Bouton had was correct and everything he could see was the special case. That is the honest summary of the sequence, and it is a much narrower criticism than it did not generalise — nothing in the 1901 paper is wrong, and nothing in it points anywhere.

The two properties are not symmetric, and that is the content #

One more thing about the pair of sentences deserves saying, because a reader meeting them together will take them for two halves of a symmetry and they are not.

Property (a) is a prohibition and it is cheap: no move stays in a class. Property (b) is an existence claim and it is the whole theorem: from above, the class can be reached.

Bouton’s own proof shows the asymmetry plainly. His (a) is one sentence about the exclusive-or; his (b) is a construction that names a heap and a number to reduce it to. And the transplant of his criterion to a subtraction game breaks exactly (b) and never (a) — taking moves away cannot create a move that stays in a class, and it can very easily destroy the move that reaches one.

That is why the generalised pair is a theorem rather than a definition dressed up. The mex rule makes both true by construction for a single heap; carrying them to a position of several heaps at once is what needs the exclusive-or, and the exclusive-or is Bouton’s.

Half of the generalised argument is free, half of it is the theorem, and the free half is the half Bouton proved in a line.

What closure buys that a criterion does not #

The two essays above this one both carry the 1901 paper across to 1935, and they carry different things. It is worth saying which is worth more.

The substitution carries the criterion: a test on a position, which a player can apply. It is the half a reader wants and it is the half that needs a table of Grundy values before it says anything.

The closure carries the argument: a pair of sentences about sets, which nobody applies to anything. It is the half that explains why the criterion is true, and it needs no table at all — the mex rule makes both sentences true by definition and the exclusive-or carries them to several heaps.

So the argument generalises more cleanly than the criterion does, which is the reverse of how the decade after 1901 seems to have been spent. Wythoff and Moore both produced criteria; neither produced an argument with a variable in it. Each of their criteria is exact on its own game and fails elsewhere, which is what a criterion does when it is carried without its argument.

A criterion travels badly and an argument travels well, and the object that was missing for thirty-four years was the definition that would have let the argument be stated at all.

There is nothing further to ask #

Six essays: the criterion and where it fails, the two solutions published beside it, how far a description of its kind reaches, the other half of the paper, the substitution that was missing, and the argument carried across.

What is left to ask about Bouton’s argument is what it does leave behind, and the answer is that it leaves behind the theorem — carried over one sentence at a time by the two essays above. Nothing further can be asked of the 1901 paper that is not a question about 1935, and 1935 is a different subject.

So there is nothing further to ask, at six.

What six essays of transplanting established #

The sequence closes here, so it is worth setting out what the six measurements add up to, since none of them is the sentence a reader would have expected at the start.

The 1901 criterion is exact on Nim and wrong elsewhere, and its errors are one-sided — sound and incomplete, which is a useful thing to be and not a theory.

The two solutions published beside it fail differently, two by being wrong and one by having no form for the question, and only the last kind of failure decides anything.

The method behind the criterion is complete and proves nothing: every impartial game has a set of losing positions, so exhibiting one is no achievement; what made 1901 a theorem is that the set had a short description, and seven of fifty-six subtraction games have one.

The misère half of the same paper is the harder result and goes nowhere worse, because the clause it adds is a fact about one game’s endgame and has no direction.

The step to 1935 is one substitution, invisible in Nim because a Nim heap’s value is its size.

And the argument carries across whole, with the picture it leaves behind — the values descending — turning out to be the last of the special case rather than part of the theorem.

What runs through all six is a single shape. Everything in the 1901 paper is correct, and every part of it that looks general is general only about Nim. That is a narrower and more interesting claim than a paper failing to generalise, and it took six transplants to state.

Why the sweep stops at subtraction games #

Normal play throughout, and Grundy values computed by the mex rule over each game’s own moves.

Three conventions of the sweep.

Subtraction games and Nim, not octal games. A take-and-break move splits a heap in two, so its options are positions rather than heaps and their values are exclusive-ors. Closure still holds there — it is the theorem — but stating it over single heaps would be stating it about the wrong objects.

A climb is counted per value rather than per move. For each value $v$ and each heap $n$ with a smaller value, the question is whether some option of $n$ has value $v$. Counting individual moves would weight a heap with many options more heavily and would measure branching rather than direction.

And heaps run to twenty-four. Far enough for every game here to have settled into its period several times over, which is why the count at thirty-two moves every number and no verdict.

A climb is not a blunder #

Five games. The closure properties are a theorem and do not need a sweep; what the sweep is for is the third sentence, and Nim alone never climbs is a statement about the five games here.

A climb is not a bad move. A position whose value rises is not a mistake — the winner’s move is always to a position of value nought, and what the counts measure is what is available, not what is played. A picture in which the values descend is wrong about the game tree and right about the winning line.

And the count says nothing about how far they climb. A move from nought to two and a move from nought to seven are one climb each here, and the distribution of climb sizes is not measured.

The one place the imagery does hold #

It would be wrong to leave the descending picture as simply false, because there is a place it is exactly right and it is the place a player is standing.

A winning player moves to a position of value nought, every time. From nought their opponent must move to something non-zero, and the winner returns it to nought. So along the winning line the value alternates between nought and something, and the something gets no chance to grow: the line visits nought at every second position and ends at nought.

What climbs is everything off that line. A losing player, or a careless one, can send the value up and often can send it up a long way — and the count above is over all the moves there are rather than over the moves a winner makes.

So the picture describes the play and not the game. That is a distinction worth drawing generally: an argument about a winning strategy tours a very thin part of the position graph, and any imagery it leaves behind is imagery about that part. Bouton’s descending values are the winning line’s values, and the winning line is where nothing surprising ever happens by construction.

Still open: whether anything else never climbs #

Nim is the one game in range whose values never rise, and its Grundy sequence is the identity. Those two facts are obviously related and the relation is not established here.

The conjecture is short: a game climbs nowhere exactly when its Grundy sequence is non-decreasing, since a move makes a heap smaller and a non-decreasing sequence then cannot raise the value. Nim’s sequence is strictly increasing, so it qualifies; every other sequence here goes down somewhere and climbs somewhere.

What would make it a measurement rather than an observation is a game whose sequence is non-decreasing without being the identity — a sequence that repeats a value and never falls. Whether any subtraction game has one is a question about the mex rule that the fifty-six-game sweep three essays below could answer with one extra column, and it would say whether never climbing is a property of Nim or of a family Nim happens to be in.