The rule the symbols follow

The genus of a sum established that the symbols compose — that the genus of a sum is determined by the genera of its parts — and closed by naming what it had not done:

The composition is a function and this essay does not write it down; producing the rule with its cases, and checking it against the 405 pairs rather than deriving it, is a concrete piece of work with a definite finish.

Here is the function. It is three lines, it has no table in it, and the surprise is in the second line.

The rule #

A tame position’s genus symbol takes one of two shapes. It is firm when the symbol is g with superscript g, g ⊕ 2 — the ordinary shape, the one a Nim heap of g counters has. It is fickle when it is one of the two symbols only a position of single counters reaches: 0¹²⁰ and 1⁰³¹.

Then:

• the base of the sum is the exclusive-or of the bases;
• the sum is fickle exactly when every component is fickle, and firm otherwise;
• the symbol follows, because firm and fickle each determine the superscript from the base.

The first line is Sprague–Grundy and is a control: the base of a genus is the normal-play Grundy value, and normal-play Grundy values exclusive-or by the theorem. A run in which they did not would mean the machinery was broken rather than the rule.

The third line is bookkeeping. Once the base and the class are known the symbol is written out with no further computation.

The content is the second line, and it is not what a reader would guess. Fickleness is a property that survives only unanimity: one component with two counters in it makes the whole sum firm, however many all-ones components stand beside it.

Two hundred and thirty-eight of 252 #

The rule is checked on every unordered pair of heaps of one to seven counters, in nine games: Nim as the control, then Dawson’s Kayles, Kayles itself, and six other octal codes.

It is right on 238 of the 252 pairs.

Fourteen pairs break it. Every one of the fourteen contains a wild heap, and every pair containing a wild heap is one of the fourteen. Both directions are asserted: a tame pair the rule missed, or a wild pair it happened to get right, would stop the build, because either would blur the boundary the page is about.

Seven of the nine games have no wild heap at all up to seven counters, and the rule is exact on all 196 of their pairs. Kayles goes wild at five and ·6 at seven, and each contributes seven failures — the pairs that include the wild heap.

Exactly as good as tameness #

That is the finding and it is worth saying why it is the right kind of finding rather than a disappointment.

The genus is defined as an invariant of tame play. Its whole content is that a tame position may be replaced, in any misère sum, by the Nim position with the same symbol — which is what what a tame heap may be replaced by establishes and what makes the symbol worth carrying. A wild position has a symbol and the symbol does not stand for a Nim position, so there is no reason for it to compose like one.

So a composition rule that worked on wild positions would be surprising, and a rule that failed on some tame ones would be wrong. The genus is an approximation to the quotient and an approximation is entitled to a domain; what it is not entitled to is a domain nobody has drawn. What the sweep finds is neither: the rule holds exactly on the class it is for.

A boundary that arrives as two counts rather than as a caveat is worth more than a caveat. The usual statement is the genus composes for tame games, which is a sentence with an escape clause in it; fourteen and fourteen is the same sentence with the escape clause measured.

The second line is Nim’s misère rule #

The clause that carries the content has a familiar reading, and putting the two side by side is the best argument for the rule being right rather than fitted.

Under the misère convention, Nim is played as under normal play until every heap holds a single counter, and then the winner is decided by the parity of the number of heaps. That is the patch, and it is a clause about heaps of one.

In the genus’s vocabulary, a Nim heap of one counter is fickle and every larger heap is firm. The rule’s second line says the sum is fickle only when every component is — which is to say, only when every heap holds a single counter.

The misère patch and the composition rule are the same sentence in two notations. The patch says the ending only matters when every heap is a single counter; the rule says fickleness survives only unanimity. One is stated about play and the other about symbols, and there is nothing between them.

A rule for pairs is a rule for pairs, so it is worth asking whether it survives a third component. It does, where tameness does.

Over triples of heaps of at most six counters: Nim, 56 of 56; Dawson’s Kayles, 56 of 56; Kayles, 38 of 56. The eighteen Kayles failures are the triples containing its wild heap of five.

The second line makes triples the interesting case, because every component is fickle is a condition that gets harder to satisfy as components are added. On a triple of Nim heaps, the sum is fickle only if all three heaps hold one counter — a single position out of the fifty-six — and it is firm on the other fifty-five.

That is the same behaviour Nim’s patch has and it is not obvious in advance. A rule of the shape fickle when an odd number of components are fickle would have been just as natural to write down and it is wrong on the first triple it meets. That rule and the right one agree on every pair — one fickle component out of two is odd, two is even — so pairs alone cannot separate them, and the triples can. A rule tested only on pairs would have been under-determined, which is the reason the triples are on the page rather than in a footnote.

Why the rule was worth deriving rather than quoting #

The composition is in the literature, and this site’s habit is to reproduce a rule from the data rather than to quote one. That habit costs time now and then and it earns something here.

Deriving it means starting from the symbols the recursion produces and looking for the function. The base column answers itself — exclusive-or, on all 252 pairs, before any thought about misère play. The superscript column does not: the obvious first guess, that the superscripts exclusive-or termwise like the bases, is wrong on all 252, because the sequences have different periods and the stars a genus symbol is defined against are shared between the components rather than added to each separately.

What survives once that guess is dead is the two-class reading, and the two-class reading is only available because the symbols were classified first — tame and wild put every heap into firm, fickle or wild, and the rule is a statement about those three words.

So the derivation had a prerequisite and the prerequisite was a classification, which is the ordinary shape of this kind of work: a rule about symbols needs the symbols sorted into kinds, and quoting the rule would have hidden that the sorting is where the content is.

What a rule of this shape can and cannot be #

Before the failures, it is worth being exact about the form of the claim, because the form is what the rungs above go on to attack.

The rule takes two genus symbols and returns one. That is a very strong demand and it is worth separating into two demands that usually travel together. The first is that the pair of symbols determines the answer — that two heaps carrying the same symbol are interchangeable for this purpose, so the function exists. The second is that the function has a formula: a short rule, of the kind written above, that computes the answer rather than looking it up.

Those are different claims and they can come apart in either direction. A function can exist with no formula, which is the ordinary situation for an arbitrary map between finite sets and is not usually what happens to a mathematical object anybody has named. A formula can also appear to work while the function underneath does not exist, if the pool never happens to contain two heaps with the same symbol and different answers — which is a failure a census catches only by being wide enough.

The rule above is being asserted in both senses at once, and the 238 of 252 is evidence for both together. Reading the count as evidence for the formula alone is the mistake to avoid: a formula wrong on fourteen pairs is a formula with fourteen exceptions, and a function wrong on fourteen pairs is not a function at all.

The distinction decides what the fourteen are worth. If the pair of symbols determines the sum even where the formula fails, the fourteen are a gap in a description and there is something to describe. If it does not, the genus is simply not enough information and no amount of describing will help. Nothing on this page separates those, and the separation is the first thing the rung above has to do.

What the rule does not reach #

Three limits, and the first is the one the fourteen are about.

Wild positions. The rule is exact on tame pairs and wrong on every pair with a wild component in it. What a wild symbol composes with is not a question this page answers, and it is not clear it has an answer of this shape — a wild position’s symbol is a partial invariant and there is no Nim position it stands for, so the argument the rule rests on is unavailable.

Two games and their heaps, not their positions. Everything here is a sum of single heaps of octal games. A position of an octal game is a multiset of heaps and its genus is the composition of the heaps’ genera, which is what the rule computes — so the restriction is less severe than it sounds, and it is still a restriction: no partizan position appears, and there is no partizan genus for one to have.

Seven counters. Every symbol is computed to a tail of ten stars and every heap runs to seven, which is where two of the nine games have gone wild and seven have not. A game that goes wild at nine would be counted here as wholly tame, and the rule’s 94.4 per cent would be a different number on a sweep one heap deeper — larger or smaller depending on which games the extra heap makes wild.

And the composition is a rule for the symbol, not for the winner. A genus symbol carries the misère outcome in its first superscript digit, so a rule for the symbol gives a rule for the outcome — of a sum of tame components. It gives nothing about a sum with a wild component in it, which is precisely the case a solver meets once the game is one of the many that go wild.

What fickleness is #

The word carries the rule and it is worth unpacking, because “fickle” is a name rather than a description and the name is doing no work for a reader.

A position’s genus records what happens to its misère Grundy value as copies of ∗2 are added beside it. For most positions that sequence settles at once into the alternation g, g ⊕ 2, g, g ⊕ 2, … — adding a star two flips one bit and adding another flips it back. Those are the firm positions, and firm is the ordinary case.

For two positions it does not. 0¹²⁰ runs 1, 2, 0, 2, 0, … and 1⁰³¹ runs 0, 3, 1, 3, 1, …: a first entry out of step, and then the alternation. That first entry is the misère outcome of the position alone, with no stars beside it, and it is out of step precisely because the misère convention and the normal-play convention disagree there.

So fickleness is the mark of a position whose ending is exposed. A position with a heap of two or more has a move that leaves the ending untouched — take one counter and the position is still one somebody can move in — and a position of single counters does not. Adding a star two beside it hides the ending, which is why the sequence settles from the second entry on.

That reading makes the second line of the rule inevitable rather than empirical. A sum’s ending is exposed only if every component’s is, because a single component with a spare move keeps the ending covered. And the sum is fickle exactly when every component is is that sentence written in the notation.

The rule against the quotient #

It is worth pricing the rule against the machinery it approximates, since the quotient is the exact object and the genus is the approximation.

The quotient of a game is a monoid: every position maps to an element, elements multiply, and the outcome is read off. It is exact, it is what the modern misère theory computes, and it is expensive — a quotient is found by a closure computation over positions and it can be infinite.

The genus is one symbol per position and a three-line composition. It is cheap, and it is right exactly as far as tameness goes.

So the trade is the ordinary one and the sweep prices it. Seven of the nine games here are tame to seven counters and the genus handles them completely; two are not, and on those the genus handles the pairs without the wild heap and nothing else. A solver would use the genus first and fall back, and this page says how often the fallback fires.

The convention, named #

Misère play: the player who moves last loses. A genus symbol is the normal-play Grundy value followed by the sequence of misère Grundy values of the position plus 0, 1, 2, … copies of ∗2, truncated at the point the sequence becomes periodic with period two.

Tame means the symbol is one a Nim position has — g with superscript g, g ⊕ 2 for any g, together with 0¹²⁰ and 1⁰³¹. Everything else is wild. Every symbol in the sweep is computed by the recursion rather than looked up, and the sums are computed the same way and compared against the rule rather than produced by it.

Where the ladder goes next #

The genus anchor has four rungs to here: what the genus is, what a tame heap may be replaced by, that the symbols compose, and now the function that composes them.

The rung above takes the fourteen wild pairs and finds that they were never a boundary. A function with no formula widens the sweep two heaps and the composition rule goes from wrong on all fourteen wild pairs to wrong on 34 of 35 and right on one — Kayles’ five and nine, which is a coincidence rather than a class. So the tidy split this page ends on was a split of the pool.

What survives the widening is stronger and stranger than the split was. The pair of symbols still determines the sum on the wild side — two wild heaps with the same pair of genus symbols give the same answer — and no rule of the shape this page’s three lines have describes what that answer is. A function exists and has no formula, which is a different situation from a partial invariant and a much more uncomfortable one.

The wild side does not close then asks the two structural questions that would have made the wild table tractable, and both come back no. The twelve entries of the wild composition table are not symbols any wild heap carries, so the wild symbols are not closed under addition and there is no small algebra to find. And two wild heaps added together are tame two thirds of the time, so wildness is not even preserved — which is why a sweep of nine counters a heap produces a diagonal rather than a table, and why the object this ladder has been reaching for may not be an object at all.

Two neighbours are worth the trip. Tame and wild is the classification the whole page is bounded by, and the fourteen failures are its boundary measured rather than described. And misère quotients is the exact machinery this approximates, and reading the two together shows what three lines buy and what they cost.