The table closes, until heaps of four

What a component would have to carry grouped single components — Nim heaps, Kayles rows, heaps of Dawson’s chess — by whether any small company tells them apart with a held pass on the board. The pass is one token, usable once by either player, and never as the move that ends the game. The grouping found more classes than any pair of numbers per component could name, and it closed by asking whether the classes form an algebra: whether the class of a sum is a function of the classes of its parts, as a misère quotient’s classes combine.

That question has a sharper form than the one it was asked in, and the sharper form is the one misère theory settled decades ago. Fix a pool of components. Let a position be any finite sum of them, together with everything those sums can move to. Call two positions indistinguishable when adding the same position to each never changes who wins. If two positions agree beside every position of the pool, they agree beside every sum of two, so adding anything to both keeps them indistinguishable. The classes always combine. There is always an algebra — a commutative monoid, with the empty board as its identity — and the only question is how big it is. A misère quotient of a tame game is small and finite; the misère quotients of some wild games are infinite. So the real question for the held pass is which of those it resembles.

How a table is computed without an infinite universe #

The positions of a pool are infinitely many — any number of heaps of each size — so the table cannot be computed outright. It is computed on a box. A box of size $B$ holds every position with at most $B$ components of each size, and every such position is tested beside every other position of the same box: two positions share a class when all those tests agree. As $B$ grows, positions that looked alike may be split by a newly admitted company, and the count of classes can only rise. When the count stops rising across several boxes, the table is finite as far as the box can see. It is the method what misère play costs and two heaps of testing are enough use for misère quotients, and the same caution they give applies. That is evidence and not proof, and every count below should be read that way. A class split only by some company outside every box tried is invisible here.

The same computation serves all three conventions: normal play, where the player unable to move loses; misère play, where that player wins; and the held pass, which is normal play with the token on the board. Under the held pass the player to move wins if some move leaves a loss, or if the board is not empty and its nim-sum is nought. Spending the pass then hands the opponent a normal-play loss. Every outcome the box needs is solved from those rules, and on 270 positions of three pools the solver agrees with the recursion the essay below this one used.

Heaps of one: four classes where misère needs two #

The smallest pool shows the whole shape. A position is some number of heaps of one, and the pass sits beside them.

Normal play loses at every even count, misère play at every odd one, and each leaves two classes: the table is a group of order two, one generator whose square is the identity. The held pass loses at the empty board and at every odd count from three. The empty board is lost because the pass may not be the last move and nothing else is left. One heap is won by taking it — leaving the empty board with the pass unspendable. Two heaps are won by spending the pass, leaving the opponent two heaps of one in plain Nim. Three heaps are lost: taking one leaves two, which the opponent wins by passing, and passing leaves three heaps of one in plain Nim, which the opponent wins by taking one. From there the outcomes alternate.

So the held pass leaves four classes: no heaps, one heap, an even count from two and an odd count from three. Adding a heap walks them in order and then swings between the last two for ever. Written as a table it is the monoid generated by one element $a$ with $a^4 = a^2$. The first two classes are a tail, positions too small for the pass to behave as it does on a crowded board; the last two are a cycle, and the cycle is exactly normal play’s group of order two. Misère play on the same pool has no tail at all. Its whole table is the cycle.

Six pools that close #

The next pools admit larger components, and the counts keep that shape.

Nim heaps up to two leave eleven classes under the held pass, against six for misère play and four for normal play. Heaps up to three leave fourteen, against six and four. Kayles rows up to four leave eleven, Dawson heaps up to five eleven, and Kayles rows up to five nineteen, against twelve under misère and eight under normal play. Each of those counts is the same at every box tried — boxes of four, five and six for the Nim and Kayles pools, three to five for Dawson’s chess. On every one of them the held pass needs about twice as many classes as misère play and between two and four times as many as normal play. That fits what the pass has shown from the start: a pass is not a move showed the ending clause is the whole difficulty, and a clause about the end of the game is a clause about the whole board.

Two things in that column are worth pointing at. The first is that the Kayles and Dawson pools, whose components were split in the essay below this one by companies no pair of numbers could anticipate, still close. Needing more than two numbers per component is not the same as needing infinitely many classes. The second is the row that does not close.

Heaps of four, and a table that never stops #

Admit Nim heaps of four and the count does not settle.

Boxes of two to seven find 31, 43, 55, 71, 87 and 102 classes, gaining twelve to sixteen with each step. Beside them, heaps up to three under the held pass are at fourteen from a box of three onward, and heaps up to four under misère play are at ten in every box. The contrast is exact: the same pool under the other difficult convention closes at once, and the smaller pool under the same convention closes at once. Only the combination of heaps of four with the held pass keeps finding new classes.

A count that keeps growing in a box is not yet a proof that the table is infinite. A slow table can take a long time to close, and a box can split positions that some larger computation would show were never really different. What turns the growth into an argument is finding why it grows, and here the reason is visible in a single plane of the box.

One line of losses #

Take only heaps of two and heaps of four, with the pass on the board, and mark the positions the player to move loses.

The losses in that plane are few and regular. There is the empty board. There are heaps of four on their own, lost at seven, thirteen, nineteen and twenty-five — a period of six that begins at seven, the kind of eventually periodic sequence a period is a proof is about. And there is one line: three heaps of two alone, five beside two fours, seven beside four, and so on — $2k + 3$ heaps of two beside $2k$ heaps of four, at every $k$ the box reaches, out to twenty-seven twos beside twenty-four fours.

A line of slope one is what makes a table infinite, and the reason is one step long. Two counts of twos — say $m$ and $m + 2$ — have the same nim-sum, so no normal-play question tells them apart. But $m$ twos meet their loss beside $m - 3$ fours and $m + 2$ twos meet theirs beside $m - 1$, and so a company of $m - 3$ fours makes one position a loss and leaves the other a win. For odd counts the line does this directly; for even counts the same job is done by fours with a single heap of one beside them, as the next figure shows. Every count of twos is split from every other count of the same parity by some number of fours. The classes of $m$ heaps of two, for $m = 0, 1, 2, \ldots$, are all different, and a finite table would have to repeat one of them.

The table of lightest separating companies is the same fact read sideways. Two twos against four are split by a single heap of one, and three against five by nothing at all, since three twos lose and five twos win. From four twos on, the lightest company is a run of fours, with a heap of one added when the count of twos is even: two fours beside four or five twos, four beside six or seven, six beside eight. Each pair needs a company two heaps heavier than the pair before it, and there is no pair a lighter company reaches. That is what the growth in the box was measuring. Each larger box admits one more run of fours and splits one more pair of counts of twos.

One point on the line, played #

A line of losses is a strong claim, and the way to trust it is to watch one point on it defend itself.

Five twos and two fours have nim-sum two, so spending the pass would hand the opponent a normal-play win; the player to move has to touch a heap. Removing a two leaves four twos and two fours, nim-sum nought, and the opponent spends the pass. Cutting a two to one is answered by removing another two. And every cut of a four — to nothing, one, two or three — is answered by cutting the other four to three minus that. The two fours behave as a pair whose cuts cancel: after both, the fours have become a one and a two, or a three and nothing, and the nim-sum of that pair is three either way. That is why the loss moves along the line two twos at a time for every two fours. Each pair of fours is a store of replies, and the twos are left for the pass to settle.

The reply table is exhaustive for this position and says nothing about the line in general. Nothing here proves that $2k + 3$ twos beside $2k$ fours is a loss for every $k$; it is a loss at thirteen values of $k$, and the fours-pair mechanism is the natural route to a proof by induction. It would need a description of the losses off this plane as well, because the replies above pass through positions with heaps of one and three. Until that proof exists, the table’s being infinite is observed, not established.

Why a Kayles row of five is not a heap of four #

The obvious guess is that the table breaks because a Grundy value of four arrives. It does not. A Kayles row of five is worth $\ast 4$ exactly as a Nim heap of four is, and Kayles rows up to five close at nineteen classes, the same at boxes of three and four. Every impartial game is a Nim heap for every question normal play can ask. Under the held pass the two are different objects, in the way what a component would have to carry found Nim 1 and Kayles 8 to be.

The difference is visible in the replies. The line depends on a heap of four whose four cuts pair with another heap’s four cuts: nothing, one, two or three against three, two, one or nothing. A Nim heap of four can move to every smaller heap, so it has all four. A Kayles row of five moves to rows of four and three and to pairs of rows, whose values are a different set, and whatever the rows’ replies do instead, they do not lay down a line: the table closes. The line is a fact about Nim heaps of four, not about the value four.

The normal-play group at the bottom of every table #

Every finite commutative table has a kernel: the part every position falls into once enough is added to it, which is always a group. For misère quotients the kernel is well understood, and it is the most revealing thing to compute here.

On all four pools whose product table fits in the box, the held-pass kernel has exactly as many elements as the normal-play group, and every element is its own inverse. The misère kernel is the same size. So under either convention a crowded board is described by its nim-sum and nothing else, and the extra classes all live in the tail — in positions small enough for the end of the game to be in sight.

The two kernels differ in one entry, and it is the surprising connection. Misère play’s crowded loss sits at nim-sum nought, which is Bouton’s rule for misère Nim once some heap is larger than one. (Among heaps of one alone it sits at one, which is Bouton’s exception.) The held pass’s crowded loss sits at nim-sum one, on every pool. That is exactly where a pass is not a move put the loss for a pass that may end the game: there the pass is a Nim heap of one, and a position plus a heap of one is lost when its own nim-sum is one. On a crowded board the clause forbidding the pass as the last move never gets a chance to matter, because the game is nowhere near its end, and the held pass is a heap of one. The whole difference between the two passes lives in the tail of the table, and the tail is where the eleven, fourteen and nineteen classes come from.

The convention the tables depend on #

Everything above is normal play with one shared pass, which either player may spend once, at any turn at which some component is not empty. A position’s class is taken relative to its own pool — indistinguishability beside positions of that pool and nothing else — which is the convention of what survives misère play and of equal in this company. A class can be split by a component from outside the pool, and none of these tables says anything about sums mixing a pool with something else. The counts are for the boxes named in each figure, and the misère and normal-play columns are computed by the same box method, not quoted from the literature. That the normal-play column comes out as the group of nim-values, and the misère column for Nim heaps as the six-element table known for heaps up to three, is a check on the method rather than a finding.

What a box of multiplicities cannot see #

A box is finite, and three consequences follow. A table called closed here is closed on the boxes tried: a class split only by very large companies would be missed, and the Dawson pool’s table does not even fit its own products inside the largest box. A table called growing here is growing on the boxes tried, and the argument that it grows for ever rests on a line of losses observed at thirteen points and not proved. And the pools are chosen, not surveyed. Nim heaps up to four break; whether heaps up to five break faster, whether Dawson or Kayles pools break at some larger size, and whether a pool of mixed rulesets breaks sooner than its parts, are not measured. The kernel finding is stated on four pools whose products all fit, and it is stated as what those four show.

Still open: a proof of the line, and where between three and four #

Two questions follow and they pull in different directions.

The first is a proof. The reply table shows the mechanism — pairs of fours whose cuts cancel, and twos settled by the pass — and an induction on $k$ would need to know every loss the replies pass through, which lie off the plane of twos and fours. If the losses near the line have a description as clean as the line itself, the held pass on Nim heaps up to four has an infinite quotient by proof rather than by box, and it joins the wild misère games as a convention whose algebra is genuinely unbounded.

The second is the boundary. Heaps up to three close at fourteen and heaps up to four do not, and the pair of fours is the culprit. Kayles rows up to five close with a component worth $\ast 4$. The question is which property of a component pool decides which side it falls on, and the smallest test is a pool that contains heaps of four and nothing that pairs them: heaps of one, two and four without three. That pool is still generated by the same moves, since a four can be cut to three, so the test needs a ruleset built to omit the move. Whether a pool that cannot answer x with three minus x closes is the measurement that would say whether the pairing is the whole story.