The formula is a limit

Lasker’s Nim has a closed form, and one split is enough showed how little of its rule the closed form uses. Neither says where the game sits among other games. It is not an octal game: naming a game with a number gives one digit to each number of counters that may be removed, and Lasker allows any number, which would take infinitely many digits. So the formula has been treated as a curiosity standing outside the family whose Grundy sequences are the subject’s main body of data — a game with a formula, beside a family of games with periods.

That separation does not survive putting a bound on the take.

Lasker’s Nim with a cap on the take #

Allow a player to split any heap into two non-empty heaps, or to take between one and $k$ counters from a heap, leaving nothing or leaving the rest as one heap. For each finite $k$ this is an ordinary take-and-break rule with a finite description. In the notation, a digit before the point says what may be done while removing nothing — the digit 4 means “leave two heaps”, which is the split — and the digits after it say what may be done while removing one, two, three counters: the digit 3 means “leave nothing or leave one heap”. So the capped game is written 4.33…3, with $k$ threes. Lasker’s Nim is what this becomes as $k$ grows without bound.

Each capped game is a finite rule table, so its Grundy sequence can be computed and searched for a period like any other. The strips above are that computation for the first eight caps, and they say something definite. Every one of them is periodic almost from the start — from heap one when $k$ is even, from heap $k+1$ when $k$ is odd, with no long irregular opening — and each follows Lasker’s formula up to about heap $k$ before the cap starts to bite and the sequence wraps round.

The wrap is visible in the strips as a nought reappearing. With the take capped at $k$, a heap of $k + 1$ cannot be removed in one move, and once heaps are large enough that no take empties them, the value can drop back towards small numbers; the pattern then repeats. Lasker’s own sequence never wraps, because a heap of any size can be removed whole.

Three regularities, and what they say #

The table has three columns worth reading as claims.

The period is $k+1$ rounded up to an even number. Two, four, four, six, six, eight, eight — the capped games come in pairs with the same period. The rounding up is the split at work: without the split, the capped take is the subtraction game $\{1, \dots, k\}$, a game whose Grundy value is simply the heap mod $k+1$, period $k + 1$ exactly. Adding a free split changes the period only when $k+1$ is odd, and then only by one.

The agreement with Lasker’s formula grows with the cap. At $k = 1$ the capped game follows the formula through heap 2; at $k = 10$, through heap 10. In between it advances two heaps for every two steps of $k$. The formula is therefore the pointwise limit of the capped sequences: fix any heap $n$, and every capped game with a large enough cap gives heap $n$ its Lasker value. That is a precise sense in which Lasker’s Nim is “the capped games with the cap removed”, and it is the sense in which the formula belongs to the family.

The largest value is $k+1$. The capped sequences stay small, as every periodic sequence must, and the bound is exactly one more than the cap. Lasker’s sequence is unbounded, and it gets that way by being the limit of sequences whose bounds climb one at a time.

What makes this more than a reformulation is the comparison with the octal codes in the last column. The capped take without a split is a sawtooth — $0, 1, \dots, k, 0, 1, \dots$ — and its limit as $k$ grows is plain Nim, $G(n) = n$. The capped take with a split has period nearly the same length, and its limit is Lasker’s formula. So the four-clause formula is to the split column what the identity is to the column without it: the unbounded end of a sequence of periodic games, reached one digit at a time.

Where the cap bites, worked by hand #

The smallest capped game with something to show is 4.33 — split freely, or take one or two counters. Its first few values can be done in a line each, and doing them shows exactly where the cap and the formula part company.

Heap 0 has no move and is worth nought. Heap 1 can only be taken whole, which reaches nought, so it is worth 1. Heap 2 can be taken whole, reduced to one, or split into $1 + 1$, worth $1 \oplus 1 = 0$; its options are worth 0 and 1, and it is worth 2. So far the capped game and Lasker’s agree, because nothing yet exceeds the cap.

Heap 3 is where they part. Under Lasker’s rule a heap of three can be removed whole, which reaches nought; together with the takes to heaps 2 and 1 and the split $1 + 2$, worth $1 \oplus 2 = 3$, its options are worth 0, 1, 2 and 3, and it is worth 4. Under the cap of two, the move to nought is gone. The options are the takes to heaps 2 and 1, worth 2 and 1, and the split, worth 3. Nought is missing, so the heap is worth nought. One missing option at one heap, and the value falls from four to nothing.

Heap 4 then agrees again by accident: its options are the takes to heaps 3 and 2, worth 0 and 2, and the splits $1 + 3$ and $2 + 2$, worth $1 \oplus 0 = 1$ and $0$; the mex is 3, which happens to be Lasker’s value. Heap 5 has takes worth 3 and 0 and splits worth $1 \oplus 3 = 2$ and $2 \oplus 0 = 2$, so it is worth 1, and from there the sequence is 1, 2, 0, 3 over and over. The period of four is visible after five heaps, and the reason it closes is that the values below the cap never grow past three, so every heap’s options are drawn from the same four numbers.

This is the general mechanism, and it explains both regularities in the table. A capped heap larger than $k$ has lost its move to nought, and nought is the one value Lasker’s recursion always has available; with it gone, the mex drops to something small, and once every value is small the sequence has finitely many states to cycle through. And the cap only bites at the first heap that needed the move to nought to reach its Lasker value — which is why agreement lasts roughly $k$ heaps and not exactly $k$: at an odd cap the first heap beyond it happens to have nought available through a split, and the departure comes one heap later.

The surprising member of the column #

With a split digit in front, the capped Lasker games are a handful of codes among many. The natural next step is to fill in the neighbourhood: every two-digit code with a free split in front, 4.$d_1 d_2$, beside the same code without it, 0.$d_1 d_2$. And the first thing that neighbourhood contains is an old acquaintance.

The rule 4.4 allows two things: split a heap into two non-empty heaps, or remove one counter and split what is left into two non-empty heaps. Kayles allows two things: knock down one pin, or two adjacent pins, from a row, which leaves nothing, one row or two rows. These look unrelated. They are the same game.

Read a heap of $m$ counters as a row of $m - 1$ pins. Splitting the heap into $a$ and $b$ with $a + b = m$ gives two heaps that stand for rows of $a - 1$ and $b - 1$ pins, which together hold $m - 2$ pins — one fewer than the row of $m - 1$, with the missing pin between them. Since $a$ and $b$ are at least one, the rows can be empty, and every position of the knocked-down pin is available. That is Kayles’ first move. Removing one counter and splitting the rest into $a + b = m - 1$ gives rows of $a - 1$ and $b - 1$ pins, holding $m - 3$ — two fewer, adjacent, which is Kayles’ second move. A heap of one counter stands for a row of no pins and has no move in either game.

So the rule 4.4 on a heap of $n+1$ is Kayles on a row of $n$, move for move, and its Grundy sequence is Kayles’ shifted by one place. Kayles is usually written ·77 — take one or two, leaving nothing, one heap or two — and the identity says it has a second name in the column with a split digit in front. The same holds for 4.40 through 4.43 and, as the survey shows next, for 4.60 through 4.63, whose extra digits turn out to add only moves already present.

Sixty-four codes, with a split and without #

Every two-digit code, then, computed both ways to two thousand heaps and searched for a period.

“Settle” here means something weaker than it does for the ordinary octal games, and the difference has to be said. For a finite octal code there is a theorem: once a sequence has repeated through a window a fixed multiple of its period past its start, it repeats for ever. Nothing like that has been established for codes with a split digit, because the split looks back at every smaller heap however far away, and the usual argument needs moves that look back a bounded distance. So a period in the right-hand grid is a period observed through at least three repetitions and two hundred heaps beyond its start — strong evidence, and not a proof.

With that said, the comparison is striking. The split digit leaves the rows of the grid recognisable and changes a great deal within them. Most codes with a free split settle immediately, from heap one, with periods of one, two, three or four. The row for $d_1 = 4$ settles either way but not to the same thing: without the split its first four codes have period 34, the period of Dawson’s Kayles, and with it they have period twelve from heap 72, because with the split in front they are Kayles. The row for $d_1 = 6$ settles at period twelve from heap 72 only with the split, for the same reason — with it, those codes become Kayles too. And a scattering of codes that had no period in range without the split acquire one with it.

What the split settles, and what it unsettles #

The changes can be listed, and the list is short enough to read whole.

Thirteen codes are settled by the split and four are unsettled by it. That is the same direction Lasker’s own game pointed in when it was first set beside Nim: adding a move that removes nothing tends to make a sequence simpler rather than harder. Here it is measured over a family rather than claimed about one game, and the ratio of thirteen to four says the tendency is real and not universal.

The four codes the split unsettles are ·44 through ·47, and they are informative. Without the split they already have long pre-periods — period 24 from heap 143, period 20 from heap 498 — so they are codes that settle late, near the edge of what two thousand heaps can see. With the split in front their values grow into the hundreds and no period appears in range. A move that removes nothing gives every heap an option worth the nim-sum of two smaller heaps, and for most codes that fills gaps and steadies the sequence; for these it seems to feed values that keep arriving. “Seems” is the honest word, because a code with no period in two thousand heaps may simply have a long one.

The four codes unsettled either way are ·64 through ·67. They share their sequence with each other in both grids, since their second digit’s extra moves are dominated by what the first digit already allows, and they are unresolved in both.

Why a limit is the right description #

It would be possible to read all this as a set of coincidences — a formula here, a Kayles identity there, a count of thirteen to four. The capped games argue for a different reading, which is that Lasker’s formula is a property of a family and not of one game.

Every capped game is periodic, with a period that grows linearly in the cap, and each agrees with the formula on an initial stretch that also grows linearly. The formula is the union of those initial stretches. The same shape appears without the split — the subtraction games $\{1, \dots, k\}$ are periodic and converge to Nim — and nobody finds Nim’s closed form surprising for that reason, because $G(n) = n$ is so simple that its status as a limit is never noticed. Lasker’s formula is the version of the same fact in the column with a split in front, and the four clauses are what a sawtooth looks like after every fourth pair of values has been exchanged by the split.

That also says why no finite code is Lasker’s Nim. A finite code has a largest removal, and a largest removal is a cap. The formula lives exactly at the point the family cannot reach.

The convention the survey depends on #

The column is built on three choices, each of which could have been made differently.

The digit before the point is restricted to 4 — split into two heaps, removing nothing. A digit of 8 would allow splitting into three heaps at no cost, and the hexadecimal family shows that three-way splitting brings sequences that climb by a constant, which the two-way column never showed within its range.

The codes are two digits after the point. The capped Lasker games need $k$ digits, so only the first two of them sit inside the grid; the rest of the family is reached by the separate sweep over $k$.

Periodicity is observed, not proved, for the reason given above. Every “settles” and “unsettles” in this essay is relative to a range of two thousand heaps, and a count of thirteen against four could move if the range were widened — most likely by some of the question marks acquiring long periods, which would add to the settled side.

What the grids cannot show #

A grid of periods is a summary of sixty-four sequences, and it discards everything about them except whether they repeat and how often. It cannot show that 4.12 has period seven from heap six and 0.12 has period four, or why; it cannot show that two codes in the same cell with the same period have entirely different values; and it cannot show that a question mark is a code whose values grow rather than one with a period too long to see. The strips and the Kayles identity are there because a grid of numbers cannot tell a reader that two rows are the same game.

Nor does anything here say what property of a rule table predicts a closed form. The capped games are periodic, their limit has a formula, and the survey counts which neighbours settle — but a formula, a period and a failure to settle are three different outcomes and the digits do not visibly sort codes into them. Three bits of rule measured how much description a code’s sequence needs across the ordinary octal family and found no digit-level predictor; the column with a split in front offers no reason to expect one either.

Still open: whether the cap is the only road to the formula #

The capped games reach Lasker’s formula by relaxing one bound. Other families reach unbounded games too — cap the size of heap that may be split, or the number of heaps a split may produce, or allow the take only in amounts from some infinite set — and each gives its own sequence of finite codes with its own limit. Whether those limits also have closed forms, and whether a limit of periodic games always does, is a question about the family rather than about Lasker, and it is the natural question for the column once its first member has been placed in it.

A narrower question is sitting in the grid already. The Kayles identity says that 4.4 is ·77 in disguise, one counter over. It would be worth knowing how many of the other right-hand cells are ordinary octal games in disguise — shifted, or relabelled, or with dominated moves removed — because every such identity moves a code from the unexplored column into the explored family, and the heap is not the position is a reminder that the same game can wear very different rule tables.