One split is enough

The proof is sixteen cells establishes Lasker’s four-clause formula by induction, and the induction uses almost none of Lasker’s rule. At heaps that are 1, 2 or 0 mod 4 the takes alone produce the right value and the splits are shown only to be harmless. At heaps that are 3 mod 4 one split is needed — splitting off a single counter — and the rest are again only shown to be harmless. So the proof is a claim about which parts of the rule are doing the work, and a claim of that kind can be tested by taking the rest away.

A rule can be larger than what it does #

A rule table and the game it defines are different objects, and the difference is easy to lose. Lasker’s Nim adds to Nim the right to break a heap of $n$ into $a$ and $n-a$ for any $1 \le a \le n/2$. That is $\lfloor n/2 \rfloor$ extra options per heap — two for a heap of five, fifty for a heap of a hundred — and every one of them changes the game tree. A player at a heap of a hundred has fifty more moves than a Nim player, the positions reachable are sums of many heaps rather than single heaps, and the game lasts longer.

What does not follow is that every one of those fifty moves changes a value. The Grundy value is a mex, the least number missing from the option values, and a mex is decided by its gaps. An option whose value is already supplied by some other option contributes nothing, and an option whose value lies above the first gap contributes nothing either. So the question “which splits matter” has a precise form: for each heap, which options must be present for the mex to come out where it does?

The proof answers that for the formula as a whole, and the answer is striking enough to be worth checking head-on rather than inheriting. If it is right, a game with nearly all of Lasker’s splits forbidden is the same game, value for value, and nothing about the rule table would reveal it.

Nine restrictions #

The obvious experiment is to name a restriction, compute the sequence, and compare. Takes are left exactly as Lasker has them — any number of counters from one heap — so the only thing varied is which splits exist.

The first thing the table says is that the restrictions come in exactly two kinds. Five of them — every split, splitting off one counter, splitting off two, splitting off an odd number, and allowing only unequal parts — keep the formula on all 601 heaps. The other four lose it, and all four lose it at the same place: heap 3.

That shared failure point is what the proof predicts. Heap 3 is the first heap that is 3 mod 4 and so the first heap whose value a split decides; its only split is $1 + 2$, worth $1 \oplus 2 = 3$, which fills the gap the takes leave and lifts the value to 4. Any restriction that forbids $1 + 2$ leaves heap 3 at value 3, and every restriction on the failing side of the table does forbid it. Equal halves cannot split an odd heap. Splitting off exactly three counters cannot split a heap of three into two non-empty parts. Splitting only heaps of five or more never touches three at all.

The second thing the table says is that losing the formula at heap 3 is not a local error. Splitting only large heaps keeps 47 of 601 heaps on the formula, not 600. The value at heap 3 is wrong, and heap 3 is an option of every larger heap, so the mex at every larger heap is taken over a different set — and a wrong value propagates upward through every heap that can reach it, which is all of them. A restriction does not damage one clause of the formula. It replaces the sequence.

Every set of sizes #

Nine named restrictions are a sample, and a sample can be arranged to agree with a hypothesis. The honest test is exhaustive over some well-defined family, and a natural one is the split-off sizes: fix a set $S$ of sizes and allow a heap of $n$ to be split into $a$ and $n-a$ whenever one of the two parts has a size in $S$. Taking $S = \{1\}$ is splitting off one counter; $S = \{1, 2, 3, 4, 5, 6\}$ allows every split of every heap up to twelve and most splits beyond.

Sixty-three sets, forty-eight keep the formula and fifteen lose it, and the dividing line is one sentence long: a set keeps Lasker’s formula exactly when it contains 1 or 2. The fifteen that fail are precisely the non-empty subsets of $\{3, 4, 5, 6\}$, and each fails at heap 3. The sweep refuses to report a result if any set breaks that condition in either direction, so the sentence is the sweep rather than a summary of it.

Why 1 or 2, rather than 1 alone, is the arithmetic of the proof run once more. At a heap of $4k+3$ the gap to fill is the value $4k+3$ itself. Splitting off one counter gives $1 \oplus (4k+2)$, and splitting off two gives $2 \oplus (4k+1)$; in both cases the two parts’ values have disjoint binary digits in the last two places and no overlap above, so the nim-sum is their ordinary sum, $4k+3$. The two splits are the same split read from opposite ends of the heap only at heap 3, where $1 + 2$ is both; above that they are different moves that happen to land on the same value for the same reason.

And why the larger sizes never help on their own is heap 3 again. A set drawn from $\{3, 4, 5, 6\}$ offers heap 3 no split at all, so heap 3 is worth 3 rather than 4, and the formula is gone before the larger sizes get a chance to supply anything. The table does not say that a split of size three or more is useless at large heaps — at heaps of the form $2^m - 1$ every split lands on the missing value — only that no set of them can rescue the sequence once heap 3 has gone wrong.

How little of the rule the values use #

The two results together invite a count. At each heap, how many of the splits on offer does the value depend on — meaning how many would have to be removed, at minimum, before the mex changed?

Eight splits needed against two hundred and fifty-six offered, and the share falls as heaps grow: a heap of $n$ offers $n/2$ splits and needs at most one. The rule that turns Nim into Lasker’s Nim is, on this measure, almost entirely idle. Most of what it adds to the game tree is options whose values are already supplied by takes or whose values sit above the first gap; they make the game longer and bushier and leave every Grundy value where it was.

This is a statement about values, not about play, and the distinction matters. A player at a large heap with many splits available has more winning moves when a split happens to reach a zero position, and the sequence of positions a game passes through is completely different in Lasker’s Nim and in the one-split version. What is identical is the value of every single heap, and therefore — by the theorem that a sum is worth the nim-sum of its parts — the outcome of every position made of heaps. The one-split game and the full game are equal as combinatorial games, in the strict sense that either may be substituted for the other in any sum, and they are not the same rule table.

Equal halves are a move to nought #

One restriction on the failing side deserves more than a line, because its failure is total and its explanation is two symbols long.

A split into two equal heaps is a move to $G(a) \oplus G(a)$, which is nought whatever $G(a)$ is. Every non-empty heap already has nought among its option values, because the take that removes the whole heap leaves the empty position. So allowing equal halves adds to every heap an option whose value is already present, and the mex never moves. Nim with equal-halves splitting is Nim, value for value, on all 601 heaps computed — and, by the argument just given, on every heap there is.

The same mechanism is quietly at work on the successful side of the table. “Unequal parts only” keeps the formula for the reason “equal halves only” loses it: removing the equal-halves split removes an option worth nought from heaps that already have nought, which changes nothing, so forbidding it is as idle as allowing it. The restriction splits Lasker’s rule into two halves of which one is always redundant and the other contains the one split that is ever needed.

Withholding the split from small heaps #

A different family of restriction asks where in the range of heap sizes the split has to be available, rather than which sizes of part.

The answer is sharp and slightly counterintuitive. Withholding the split from heaps of one and two changes nothing — a heap of one has no split anyway, and a heap of two has only $1 + 1$, worth nought, which is redundant for the reason equal halves always are. Withholding it from heaps of three changes everything, because that removes the only split heap 3 needs.

The intuition this corrects is that a move like splitting should matter most at large heaps, where it offers the most choice. It is the other way round. Large heaps have so many options that their values are overdetermined; small heaps have few, and the one small heap whose value depends on a split is the heap every larger heap depends on. Lasker’s formula is not held up by the splitting of large heaps at all. It is held up by one split of one heap of three, inherited through every heap above it — and then, at each larger heap of residue 3, by one split of that heap, which is always available because splitting off one counter is always available.

The one split, at a heap of seven #

It is worth looking at a single heap to see the redundancy in the flesh.

A heap of seven is one less than a power of two, and at such heaps every split lands on the missing value. Any one of the three would do, and forbidding any two of them changes nothing. At a heap of eleven, by contrast, three of the five splits land on eleven and two do not, and at a heap of thirty-five only three of seventeen do. Splitting off one counter is always among them, which is why the one-split game works; it is not always alone. What the value needs is that the set of available splits contain at least one of the working ones at every heap of residue 3, and the sweep over split-off sizes shows that 1 or 2 is the only way to guarantee that from the bottom.

What these measurements rest on #

Everything above depends on three conventions, and changing any of them changes the answer.

Normal play. The last player to move wins, which makes every value a mex and every argument above an argument about gaps. Under misère play a redundant option can stop being redundant, because the misère outcome of a position is not determined by the set of its options’ values — which is why misère Nim needs an exception clause that normal Nim does not.

Takes are unrestricted. Every experiment here keeps Lasker’s takes — any number of counters from one heap — and that is what makes the takes cover an initial segment of the values so that only one gap is left for the splits. Restrict the takes as well, and the redundancy analysis has to be redone from scratch, because the gaps multiply.

Equality is about values. The one-split game and Lasker’s game are equal as games, which is a statement about every disjunctive sum. It is not a statement about the number of positions, the length of play, or which moves win from a given position; two equal games can differ in all three.

What the picture cannot show #

The strips show that the values agree. They cannot show that the games play the same, because they do not. In Lasker’s full game a heap of fifteen has seven splits and all seven are moves to a position of value fifteen; in the one-split game it has one. A player looking for a move to a zero position in a sum of heaps will find more of them in the full game, and those extra winning moves are real and invisible in any drawing of Grundy values.

Nor can a finite sweep prove the split-set condition for all sets of sizes. It was checked on the sixty-three subsets of $\{1, \dots, 6\}$ and to heap 400. The half of it that says 1 or 2 is sufficient follows from the proof, which uses only splits of those sizes. The half that says 1 or 2 is necessary follows from heap 3 alone, for any set whatever, since only a part of size 1 or 2 can split a heap of three. So the condition is in fact proved for every set of sizes — but the sweep is what suggested it, and the two sentences of argument came after.

Why the redundancy was invisible #

The surprising part of all this is not that some splits are redundant — almost every rule in this subject has redundant moves — but that the redundancy is so nearly total and so completely hidden. Nobody reading Lasker’s rule would guess that the game is the same with $n/2 - 1$ of the $n/2$ extra options deleted, and nothing in the rule table marks the one that matters.

The wider move is the easier game found the same thing from the opposite direction for Moore’s Nim: adding moves can make a game’s analysis simpler, and here removing almost all of them leaves it unchanged. Both are the mex doing what it always does, which is to ignore everything except the first gap. Nim and the nim-sum is the extreme case, where the takes alone already cover everything and there is no gap for any extra rule to fill, and Kayles is the opposite extreme, where the takes are bounded, the gaps are many, and the splits are load-bearing everywhere. Lasker’s Nim sits between them, with exactly one gap per four heaps.

Still open: where the formula comes from #

The formula has now been proved and its economy measured, and neither says where it comes from. It is a closed form for a game with unbounded takes, which puts it outside the octal family: naming a game with a number allows only finitely many digits, and Lasker’s rule needs infinitely many.

What the family does allow is a bound. Cap the take at $k$ counters and Lasker’s Nim becomes the rule 4.33…3 with $k$ threes — a split digit in front, then $k$ digits each saying “take this many, leaving nothing or one heap”. Each of those games is a finite rule table, and each has a Grundy sequence that is either periodic or not. If they are periodic, and if the periods and the formula agree below the cap, then Lasker’s formula is not an isolated closed form at all but the limit of a family of periodic sequences as the bound goes to infinity — and the whole column of codes with a split digit in front is a family worth surveying for the same reason the sequence nobody has settled surveys the codes without one.