The proof is sixteen cells

Splitting is a move ends with a formula and an apology. Lasker’s Nim — Nim with the extra option of breaking a heap in two without taking anything — has Grundy values given by four clauses, one for each residue of the heap modulo four: a heap of 1 or 2 mod 4 is worth itself, a heap of 3 mod 4 is worth one more, a heap of 0 mod 4 is worth one less. The formula was checked against the mex recursion on every heap to two thousand, and it was sketched rather than proved. Two thousand agreements are evidence. They are not a reason.

The reason turns out to be small enough to draw whole.

What a proof of this formula has to do #

The Grundy value of a heap is the least non-negative integer that is not the value of one of its options. In Lasker’s Nim a heap of $n$ has two kinds of option. Taking any number of counters leaves a single smaller heap, so the takes contribute the values of heaps $0, 1, \dots, n-1$. Splitting into $a$ and $n - a$, with both parts non-empty, leaves a sum of two heaps, and the nim-sum is what a sum is worth, so each split contributes $G(a) \oplus G(n-a)$.

A proof by induction therefore has one job per heap. Assume the formula for every heap smaller than $n$. Work out which values the takes reach. Work out which values the splits reach. Show that the least value neither reaches is the one the formula names. That is the whole of it, and the difficulty is entirely in the second step: there are $\lfloor n/2 \rfloor$ splits of a heap of $n$, their values are exclusive-ors of formula values, and exclusive-or has no respect for ordinary arithmetic. The value of a split can be almost anything below $2n$.

The trick is not to ask what a split’s value is. It is to ask what that value is mod 4, which turns out to be a question with a four-by-four answer.

Exclusive-or does not carry #

Exclusive-or has no carry. Each binary digit of $x \oplus y$ is the exclusive-or of the corresponding digits of $x$ and $y$ and nothing else, so the last two bits of a nim-sum are the nim-sum of the last two bits. In residues, $(x \oplus y) \bmod 4 = (x \bmod 4) \oplus (y \bmod 4)$.

Ordinary addition respects every modulus — the residue of a sum mod 3 or mod 5 is fixed by the residues of its terms — and that is exactly what exclusive-or does not do. Three and five are worth $3 \oplus 5 = 6$, and knowing only that they are both 0 and 2 mod 3 says nothing about 6 mod 3 in general: $0 \oplus 2$ and $3 \oplus 5$ have the same residues term by term and different residues as nim-sums. The moduli exclusive-or respects are the powers of two and no others, because a power of two is a set of low binary digits and exclusive-or treats the digits one column at a time. So a residue argument for a game whose values combine by nim-sum has to be made mod 2, 4, 8 and so on, and the four clauses of Lasker’s formula are what that argument looks like at the first power of two large enough to hold them.

The second ingredient is a fact about the formula itself, and it is the one to look at before trusting anything else.

Read the four clauses modulo four and they say that a value’s residue is a function of its heap’s residue alone. A heap of $4k+1$ is worth $4k+1$, residue 1. A heap of $4k+2$ is worth $4k+2$, residue 2. A heap of $4k+3$ is worth $4k+4$, residue 0. A heap of $4k$ is worth $4k-1$, residue 3. So below any $n$ where the formula has already been established, the residue of $G(m)$ can be read off $m \bmod 4$ without knowing $m$.

Put the two facts together and the residue of a split’s value is fixed by the residues of its two parts. That is the table at the top. Its sixteen cells are computed here not by the argument but from the sequence itself, over every split of every heap to four hundred, and each cell is checked to have received one residue and only one — which is the experimental form of the claim that the table is a function at all. It is; and since the table is symmetric and its diagonal is all noughts ($x \oplus x = 0$), only six of its cells carry information.

Reading one anti-diagonal at a time #

A split of a heap of residue $r$ has parts whose residues add to $r$ mod 4. So the splits of a heap of $4k+1$ come only from the pairs of residues $(0, 1)$ and $(2, 3)$; the splits of $4k+3$ come only from $(0, 3)$ and $(1, 2)$; and so on. In the table these are anti-diagonals — the cells running from top right to bottom left along which the row and column residues sum to a constant.

The last column is the proof, and it is worth reading slowly because it is not the obvious thing to have checked.

A heap of $4k+1$ has value residue 1, and its splits can only produce residue 2. A heap of $4k+2$ has value residue 2, and its splits produce 0 or 1. A heap of $4k$ has value residue 3, and its splits produce 0 or 1. A heap of $4k+3$ has value residue 0, and its splits produce 3. In no class can a split reach its own heap’s residue, and that is what stops splitting from ever being a move to a position of equal value — the one thing the mex rule forbids an option to be.

That already explains three of the four clauses. It does not yet explain why the fourth clause adds one, and for that the takes have to be counted.

The induction step, drawn #

The takes from a heap of $n$ reach every smaller heap, so by the formula below $n$ they reach every value in the set $\{G(0), \dots, G(n-1)\}$. The formula is a permutation that swaps each pair $4j-1, 4j$ and fixes everything else, so on any initial segment it is almost the identity. The takes from $n$ reach every value below $n$ except when the top of the segment has just cut a swapped pair in half.

Do the cases.

A heap of $4k+1$: the takes reach $G(0), \dots, G(4k)$, which is exactly $\{0, \dots, 4k\}$ because the last pair $4k-1, 4k$ is complete. The least missing value is $4k+1$. Its residue is 1, and the anti-diagonal says no split of a $4k+1$ heap reaches residue 1. So the mex is $4k+1$, and the first clause holds.

A heap of $4k+2$: the takes reach $\{0, \dots, 4k+1\}$. The least missing value is $4k+2$, residue 2, which no split of a $4k+2$ heap can reach. The mex is $4k+2$.

A heap of $4k+4$, the fourth clause: the takes reach $G(0)$ through $G(4k+3) = 4k+4$, and $4k+3$ itself is missing, because the value $4k+3$ belongs to the heap $4k+4$ that is being computed. The least missing value is $4k+3$, residue 3. A heap that is 0 mod 4 splits only into residues 0 and 1. So the gap stays open and the mex is $4k+3$ — one less than the heap.

A heap of $4k+3$ is the case where the splits matter. The takes reach $\{0, \dots, 4k+2\}$, the least missing value is $4k+3$, and its residue is 3 — which is precisely the residue this class of heap can split into. So a split may fill the gap. If one does, the mex moves past $4k+3$ to the next missing value; the takes cannot supply $4k+4$ (it is not the value of any smaller heap), and $4k+4$ has residue 0, which no split of a 3 mod 4 heap reaches. So the mex is $4k+4$, one more than the heap — provided some split really does land on $4k+3$ exactly, and not merely on something else with residue 3.

The one split the proof has to name #

Residues show that a split of $4k+3$ can land on $4k+3$. They do not show that one does, because a residue argument cannot tell $4k+3$ from $4k+7$ or from $3$. The proof needs one explicit split, and the obvious candidate works for every $k$.

Split off a single counter: $4k+3 = 1 + (4k+2)$. By the formula below $n$, $G(1) = 1$ and $G(4k+2) = 4k+2$. Their nim-sum is $1 \oplus (4k+2)$. The number $4k+2$ ends in binary $\ldots 10$, so exclusive-or with 1 sets its last bit and changes nothing else: $1 \oplus (4k+2) = 4k+3$. That is the value the takes left missing, delivered by the smallest split there is.

That closes the induction. The base cases are heaps 0, 1 and 2, which have values 0, 1 and 2 by direct inspection — a heap of one has only the move to nought, a heap of two has the moves to one and nought and the split into two heaps of one, worth $1 \oplus 1 = 0$. From there every heap is covered by one of the four cases above, and each case used only the formula for smaller heaps, the no-carry property of exclusive-or, and the single split $1 + (4k+2)$ at heaps of residue 3.

It is worth stating plainly what kind of argument this is, because it is not the kind a period is a proof describes. There, a finite window of a subtraction game’s sequence settles everything after it, because the game has bounded moves and the recursion can only look back a fixed distance. Lasker’s Nim looks back the whole way: every heap has every smaller heap as an option and every split as well, so no window of any size is sufficient on its own. What makes the infinite induction go through is not a bound on the moves but a bound on the information the moves can carry — the two low bits — which is a different finiteness hiding in the same place.

How many splits land where they need to #

The proof names one split and needs only one. Counting all of them is worth doing, partly because the count is unexpectedly regular and partly because it answers a question the proof raises and cannot settle: is the working split rare or common?

The first column is solid, as the proof says it must be. So is the second — splitting off two counters also works at every such heap, since $2 \oplus (4k+1) = 4k+3$ for the same no-carry reason. Beyond those two the pattern depends on the heap’s binary expansion, and the count is exact: for a heap of $n = 4k+3$ the number of splits landing on $n$ is $2^{b+1} - 1$, where $b$ is the number of ones in $k$ written in binary. At $k = 0, 1, 3, 7$ — heaps 3, 7, 15 and 31, each one less than a power of two — $k$ is all ones, the count equals the number of splits, and every split of the heap works. At $k = 8$, heap 35, $k$ is a single one followed by zeros and only three of seventeen splits work.

The count is checked against that formula on every row drawn, to heap 47, and it is offered as a measured regularity rather than a theorem — nothing here proves it for every $k$. The shape of a reason is visible, though. A split $a + (n-a)$ lands on $n$ exactly when the formula values of its two parts exclusive-or to $n$, and since the formula only ever disturbs the last two bits, that is almost a question about whether the two parts’ binary digits avoid colliding. Where $k$ has a one, the two parts have a choice of which of them carries it; where $k$ has a nought, they have none. A count that doubles with every one in $k$ is what that picture predicts.

None of this is needed for the proof. It is included because it corrects an impression the proof gives, which is that one special split is doing heroic work at every heap of residue 3. At heaps of the form $2^m - 1$ nothing is special at all: every split of the heap reaches the missing value, and the smallest split is merely the one easiest to write down. What is special is the residue class. At heaps of residue 1, 2 and 0 no split can ever do the work, whatever $k$ is, and the anti-diagonal table says so without looking at any heap.

The convention the result depends on #

Two conventions are carried silently by every line above, and the formula depends on both.

The first is normal play: the player who cannot move loses, which is what makes the empty heap worth nought and every value a mex. Under misère play the same rule table is a different game and none of the residue arithmetic applies, because the terminal position is no longer the zero of the value system.

The second is that a split must leave two non-empty heaps. Allow a split into $n$ and $0$ and it is a move that does nothing, which under normal play is a pass and changes the game entirely. Allow a split into three heaps and the options gain three-way nim-sums, which the residue table handles just as well — the no-carry property does not care how many terms there are — but the anti-diagonals change, because the part residues now add in threes. Whether the formula survives is a separate question with a separate table, and nothing here settles it.

What the table cannot show #

The table proves the formula. It does not explain why the formula exists in the first place — why a rule about splitting heaps should produce a sequence whose residues repeat at all. The proof assumes the residue pattern below $n$ and delivers it at $n$, which is how induction works, but the pattern had to be found in the sequence before it could be assumed. A reader handed a different take-and-break rule has no way to know in advance whether some modulus will make its table a function; for most rules none does, and the sequence nobody has settled is the survey of how rarely a short description exists.

Nor does a residue table say anything useful about Kayles, which is the natural comparison from the essay that introduced Lasker’s game. Kayles is eventually periodic with period twelve, so its values are in the end a function of the heap mod 12 — but only from heap 71, with fourteen exceptions below that, and its values stay small and do not track the heap at all. The argument here works because Lasker’s Nim allows taking any number of counters, which makes the takes alone cover almost the whole initial segment of values and leaves the splits a single gap to fill. Bound the take and the takes cover only a few values, the gaps multiply, and a residue table has nothing to say about which of them a split fills.

The surprising connection #

The formula is a statement about the residues mod 4 of a game whose rules mention no residues at all, and the reason it can be proved by a table of residues is a fact about binary arithmetic that has nothing to do with games: exclusive-or does not carry. That is the same fact that makes Nim’s own solution a column-by-column parity check, and the same fact behind the tartan theorem for products of coin games. Here it shows up as permission to throw away every bit of every value except the last two, and still know exactly which move is illegal for the mex.

Put another way: the proof never computes a single Grundy value. It computes sixteen residues, reads four anti-diagonals, and names one split. Everything the two thousand agreements were evidence for follows from those three steps, and Sprague–Grundy supplies the only ingredient not visible in the pictures — that a split, being a sum, is worth the nim-sum of its parts at all.

Still open: which of the splits the formula actually needs #

The proof uses one split at one residue class and none anywhere else. That suggests something stronger than the proof states, which is that most of Lasker’s extra rule is idle — that a heap of $n$ offers $\lfloor n/2 \rfloor$ splits and the values would be the same if nearly all of them were forbidden. The residue argument is silent on this, because forbidding splits removes options and can only lower a mex; whether it does lower one depends on whether the removed splits were the ones filling a gap.

The measurement that settles it is direct. Allow only the split that takes one counter off, and compute the sequence. Allow only equal halves, or only heaps above some size, or any set of split sizes at all, and compare each against the four clauses. If the proof’s economy is real, a single kind of split should reproduce every heap — and if the formula survives some restrictions and not others, the dividing line should be statable in one sentence. Take one, three or four is the precedent for a rule set whose answer is decided by a small subset of its moves, and Grundy sequences the reminder that the answer to a question like this is usually found by computing rather than by argument.