A set with a short description

The rung two below sets out Bouton’s argument as two closure properties and calls the second one the half that does the work. That is right about the proof and it hides something about the method, and the something is worth a rung.

The method proves nothing #

Strip Bouton’s argument to its shape and it is this:

Exhibit a set S of positions such that (a) no move from a position in S lands in S, and (b) from every position outside S, some move lands in S. Then S is exactly the set of losing positions.

The conclusion follows in three lines. A player handed a position outside S moves into it; the opponent, by (a), must move back out; the game shrinks; so play ends, and it ends on the opponent.

Now notice what the method requires. It requires a set with those two properties — and every impartial game has one. Take S to be the losing positions themselves. Property (a) holds because a move from a loss must be to a win; property (b) holds because a win is a position with a move to a loss; and both are the definitions rather than facts about any particular game.

So the method never fails and never says anything. Handed any game whatever, it certifies a set that was already the answer.

What made 1901 a theorem is not the argument. It is that Bouton’s set had a description shorter than the game.

What his description was #

Bouton’s set is the positions whose heap sizes exclusive-or to nothing, and the description is a sentence about binary columns: read the heaps down the page and count the marks in each column.

The thing worth noticing about that sentence is its length. It does not grow with the game. A reader can carry it, apply it to a position with three heaps or thirty, and never consult a table. Set that beside the alternative description — here is the list of losing positions — which for a game with heaps up to n has about n² entries and grows for ever.

That is the whole of what a closed form buys, and Nim is easy is the same observation priced in computation rather than in characters. The criterion is linear in the digits where the game is exponential in the counters.

So the question worth asking of the method is not whether it works — it always works — but how often a set of that kind has a description of that kind.

Why “short” is the right axis and not “clever” #

There is a temptation to say that Bouton found a clever description and that cleverness is what the method needs. It is worth resisting, because cleverness is not a property with a measurement attached and length is.

A description of a set of positions is a finite object. It can be counted in characters, and the count either grows with the size of the game or does not. That is the whole distinction, and the two sides of it behave completely differently:

A description whose length is fixed answers a question about any position, at any size, from a sentence a reader already has. Bouton’s is eleven words.

A description whose length grows is a lookup, and a lookup needs whatever it is looking up to be somewhere. That is not a failure — a table with a modulus in front of it is a complete solution — but it is a different kind of object, and the difference decides whether anybody can carry it.

So the question this rung asks has a clean form: for how many games is the losing set describable by a sentence of fixed length? Not elegantly, not cleverly, not in closed form in whatever sense a reader supplies to that phrase — describably, in a bounded number of characters, and the sweep counts.

When a column criterion can exist at all #

The question has an exact answer and it is a question about the Grundy sequence rather than about the proof.

A column criterion works when the exclusive-or of the values reduces to a count of marks in the columns of the sizes. That requires the value of a heap to be a function of a fixed set of its bits — because only then does reading the size’s binary digits amount to reading the value’s.

So three tests, in increasing generosity, and each is a property of the sequence:

Literal. The value is the heap size with some bits masked off: g(n) = n & m for a fixed mask m. That is Bouton’s criterion exactly, with the bits the game ignores dropped, and it is the strongest of the three.

Low bits. The value is any function of the low k bits, which is the same as the sequence being periodic with a period that is a power of two, from the start. A column criterion exists here too — read the low k columns, combine them by whatever the function is — though the combining rule is no longer a parity.

Periodic. The sequence repeats at all, which is the weakest thing that gives a finite description of any kind. Not a column criterion, but a table with a modulus in front of it.

The counts #

Sweep every subtraction set of up to four numbers drawn from one to six — fifty-six games — and compute each Grundy sequence to a heap of ninety-six.

All fifty-six are periodic. Every subtraction game is, and the reason is short: the value of a heap depends on a fixed window of values below it, so once a window repeats the sequence repeats for ever. That is the periodicity argument in its easy form, and it is why subtraction games are the tractable corner of the take-and-break family — though the period being small is not something the proof says, which is a separate finding one anchor over.

Nineteen have values that are a function of their low bits.

Seven have Bouton’s own description. They are {1}, {1, 3}, {1, 5}, {1, 2, 3}, {1, 3, 5}, {1, 2, 3, 5} and {1, 2, 3, 6}.

Seven of fifty-six. That is the reach of the method as Bouton stated it, over a family of games chosen for being the easiest ones there are.

What the seven have in common #

The list is short enough to read and the pattern in it is worth naming, because it says what a Bouton-describable game looks like from the outside.

Every one of the seven contains 1. That is not decoration: a subtraction game without 1 has g(1) = 0, so the value is not the size with bits dropped at the very first heap, and the description fails immediately.

Beyond that they are the sets whose Grundy sequence is n mod 2ᵏ for some k, which is to say the sets that behave like a truncation. {1, 2, 3} gives 0, 1, 2, 3, 0, 1, 2, 3 — the size’s low two bits — and {1} gives 0, 1, 0, 1, which is its low one bit.

The condition is that the game’s period is a power of two and the values run in order within it. That is a strong and arbitrary-looking requirement, and the fifty-six games in the sweep satisfy it seven times.

The gap between having a description and having Bouton’s #

The last figure makes a distinction the counts hide, and it matters.

{1, 2, 3} has a column criterion — its values are the low two bits, so those two columns exclusive-or to nothing is exactly right. What it does not have is Bouton’s, which reads every column, and reading extra columns can only refuse positions the true test would accept.

That is the rung two below’s finding restated as a claim about descriptions. Bouton’s criterion is not the wrong kind of description for that game; it is the right kind with the wrong parameter, and the repair is to drop the bits the game does not use.

So the literal count of seven is a count of games where Bouton’s mask is the right mask, and the count of nineteen is a count of games where some mask is. The second is the honest measure of how far his method reaches, and it is a third of the family rather than an eighth.

Which leaves thirty-seven games — two thirds — where no column criterion of any kind exists, and where the losing positions have a finite description only in the sense that a table with a modulus is one.

What a table with a modulus is, as a description #

It is worth being fair to the thirty-seven, because “no column criterion” sounds like “no answer” and is not.

A periodic sequence gives a complete solution: compute the period once, and every future question about a heap of any size is a division and a lookup. That is the same purchase the octal certificate makes one anchor over, and it is a real one.

What it does not give is a portable description. A column criterion fits in a sentence and travels with a reader; a table of forty numbers does not, and a reader who wants to know whether a heap of a hundred is losing must consult something. That is the difference between a rule a bar-room Nim player can carry and a rule that needs a reference.

And the difference is the whole of why Nim is the famous one. How a position is written down is where the same distinction is priced in the complexity field’s currency, and it reaches the same place from the other side. Not because it is the deepest game in the family — it is the shallowest — but because its answer compresses into a sentence about columns, and a sentence about columns is a thing a person can be shown once and use for ever.

Why the octal family is worse #

Subtraction games are the family where every game is periodic, and that is the reason to sweep them: the weakest of the three tests passes everywhere, so the counts are measuring the two stronger ones cleanly.

Take the splitting move away from that guarantee and the bottom falls out. In an octal game a move may cut a heap in two, so a value depends on exclusive-ors of pairs from anywhere below it, and periodicity stops being automatic — seventeen of sixty-four one- and two-digit codes have no period found at a heap of a thousand, and the conjecture that one must eventually exist is seventy years old.

For those seventeen there is no description at all: no column criterion, no table, no modulus, nothing finite that answers a question about an arbitrary heap. The method still applies — the set of losing positions exists, it has both closure properties, and the argument certifies it — and the certificate is a set nobody can write down.

That is the sharpest statement of what the method is worth. Bouton’s argument proves a theorem about every take-and-break game there is, and for seventeen of the sixty-four simplest ones the theorem it proves is unusable.

What the seven look like as a family #

The seven sets are not a random seventh of the family and reading them as a family is worth a paragraph.

Sorted, they are {1}, {1, 3}, {1, 5}, {1, 2, 3}, {1, 3, 5}, {1, 2, 3, 5} and {1, 2, 3, 6}. Two shapes account for all of them.

The odd sets. {1}, {1, 3}, {1, 5} and {1, 3, 5} all consist of odd numbers, and a game where every move takes an odd number has values that alternate with the heap’s parity — the size’s lowest bit, and nothing else. Four of the seven are this.

The consecutive-from-one sets. {1, 2, 3} gives values 0, 1, 2, 3 repeating, which is the low two bits; and {1, 2, 3, 5} and {1, 2, 3, 6} behave the same way in range, because the extra element is large enough not to disturb the pattern at the heaps checked.

So the description Bouton’s method produces exists for the games whose values are a truncation of the heap size, and a truncation is what a game gets when its moves are either all odd or a consecutive run from one. Neither of those is a property anybody would have set out to characterise, and both are properties a person can check by eye.

That is the honest shape of the finding. The reach of the method is not a subtle class; it is two small families of very simple games, and Nim’s own position in it is the degenerate case where the mask is every bit and the truncation is the identity.

What the picture cannot show #

The family is subtraction sets of small numbers. Fifty-six games, sets of at most four numbers from one to six, chosen because the sweep is exhaustive over them and because they are where a column criterion has its best chance. A wider family would have a smaller share, not a larger one.

And the literal test searches sixty-four masks. A mask outside that range would be a mask reading bits above the sixth, which no game in the family uses; the search is exhaustive for the family and not for all masks.

Nor does the sweep ask about multi-heap criteria that are not column criteria. A game might have a short description of its losing positions that reads the heap sizes some other way entirely — a sum, a comparison, a Beatty pair as Wythoff’s game has — and this measurement would file it under no column criterion along with the games that have nothing. The counts are about descriptions of Bouton’s kind, which is the kind the method produces.

The convention, named #

Normal play: the player who cannot move loses. Every sequence, every mask and every count above is computed under it.

The convention is where the method’s base case comes from, and it is worth seeing that the closure argument depends on it in one place only. Property (a) and property (b) mention no convention at all; what they establish is that S is closed under the play and reachable from outside it. The step that turns those into S is the losing positions is the observation that the empty position is in S and the mover there has lost — which is the convention, used once, at the very bottom.

Invert it and the argument survives with S adjusted: misère Nim’s losing set satisfies the same two properties, with the clause about heaps of size one bolted on. What it does not survive is being asked about anything else, which is the rung above.

The surprise: the method is complete and therefore worthless #

The natural reading of a closure argument is that it is a proof technique — something that works on some games and not others, and finding out which is the interesting part.

It is the opposite. The method works on every game, always, with no exceptions and no conditions, because the set it asks for is a set every game has. A technique with a hundred per cent success rate is a technique that has not been asked anything, and that is exactly the situation: exhibit a set with these properties is answered by the losing positions, and the answer is the question.

So the work is not in the argument, and the rung two below’s framing — which half of Bouton’s proof survives a transplant — is a question about his criterion rather than about his method. The method transplants perfectly. The description does not.

The general shape is that a proof technique with no failure mode is a technique doing no work, and the thing to measure is not whether it applies but what it costs to apply. Here that cost is the length of the description, and the measurement is: seven games in fifty-six get a sentence, nineteen get a short rule, thirty-seven get a table, and in the wider family some get nothing at all.

That is a better account of what 1901 achieved than he found a clever argument. The argument is not clever and did not need to be. He found a set with a short description, in a game where one existed, and the reason the paper is famous is that most games do not have one.

Where the ladder goes next #

bouton has three rungs: the criterion, the two solutions beside it, and how far a description of its kind reaches.

The rung above is the other half of the same paper. Bouton solved misère Nim as well, in a single sentence — play the ordinary criterion until the move would leave every heap at one, and then leave an odd number of them — and it is the only misère result in the subject that fits on a line. Transplanted exactly as the normal one is, it fails differently: the normal criterion errs in one direction and this one errs in both, and the clause responsible is the one about heaps of size one.