The genus of a sum

The genus is a misère bookkeeping device with an ambitious purpose. Tame and wild introduces it: a symbol like $2^{20}$, carrying a heap’s normal-play Grundy value as its base and a sequence of misère values as its superscript, computed by adding stars to the position and re-running the recursion.

The purpose is substitution. Carry one symbol per heap and never look at the heap again — which is only legitimate if the symbols compose, and the symbols compose is a claim about a function nobody here had tested.

The test, and why it has to cross games #

Inside a single game the claim is nearly untestable, and that is the trap.

Take Kayles on its own. Nine heaps produce nine symbols, most of them distinct, so the forty-five pairs fall into forty-five files with one member each — and a file with one member cannot disagree with itself. The claim passes and nothing has been tested.

So the sweep runs nine games at once: Nim, five octal games including Kayles and Dawson’s chess, and three more chosen for having short rule tables. Nine games times forty-five pairs is 405, and the same pair of symbols now occurs repeatedly, in different games, with different heaps behind it. That is exactly the situation the claim says is safe, and it is the only situation in which it can fail.

Four hundred and five pairs fall into seventy-nine files. Not one file holds two answers.

Which half of the symbol does the work #

A genus symbol has two parts and the obvious question is whether both are needed.

Filed by the bases alone — the normal-play Grundy values, ignoring the superscripts — the 405 pairs fall into fifty files, and twelve of them hold more than one answer. The file for base one plus base one holds three: $0^{120}$, $0^{02}$ and $0^{20}$. Three different misère behaviours from two heaps that agree on everything normal play can see.

Filed by the superscripts alone, there are seventy-four files and four of them split, the worst holding two answers.

Filed by the whole symbols, seventy-nine files and none splits.

So the two halves are both load-bearing, and neither is close to sufficient. That is the precise form of the warning tame and wild issues — not by exclusive or on the base alone — and here it is a count rather than a caution.

What a genus symbol actually holds #

The notation is compact and worth unpacking once, because everything above turns on there being two halves rather than one.

Write $g^{g_0 g_1 g_2 \dots}$. The base $g$ is the ordinary Grundy value of the position under normal play. The superscript entries are the misère Grundy values of the position with stars added: $g_0$ is the misère Grundy value of the position itself, $g_1$ of the position plus a star, $g_2$ of the position plus two stars, and so on. The sequence settles — it is eventually constant for every symbol in the sweep — so the notation writes the settled tail once.

A Nim heap of size $n$ has genus $n^{n'}$ where $n'$ is $n$ with a twist at the small end, and the classification tame means having the symbol of some Nim heap. So the symbol is doing two jobs at once: recording what normal play says, and recording how the position responds to being padded with stars, which is a proxy for how it responds to being put in company.

Padding with stars is not an arbitrary choice of company. A star is the smallest position with a move in it, so a position plus $k$ stars is that position given $k$ units of pure tempo — and misère play is a subject about tempo, since the whole difference from normal play is who is left holding the last move.

The file that holds three answers #

The clearest failure of the bases-only reading deserves its own look.

Every pair of heaps whose bases are both one is filed together: 1 and 1, in whichever games. The sums have three different genera between them — $0^{120}$, $0^{02}$ and $0^{20}$.

All three sums have base nought, as exclusive or requires. All three are second-player wins under normal play, for the same reason. And under misère play they behave in three different ways, distinguished by what happens when stars are added — which is to say, by how they behave in company.

So two positions can agree on everything normal play can measure and still differ misère, and a solver carrying only Grundy values has thrown away exactly the information the misère convention needs. That is the whole reason the genus has a superscript, stated as a count of files rather than as a principle.

What the base does #

The base of a sum is the exclusive or of the bases, on all 405 pairs, with no exceptions.

That is not a discovery. The base of a genus symbol is the normal-play Grundy value, normal-play Grundy values add by exclusive or, and nothing about the misère convention touches the normal-play recursion. So the first half of the symbol composes by the rule everybody already knows, and the whole of the difficulty is in the second half.

And what it does not #

The superscript is the exclusive or of the superscripts in three of the 405 pairs.

Three. A rule that agrees with the data less than one per cent of the time is not a rule that has been slightly misstated; it is the wrong shape of rule entirely. The superscript is a sequence of misère Grundy values of the position with stars added, and adding stars to a sum is not the same as adding stars to each part — the star can be answered in either component, which is precisely the sort of interaction exclusive or is blind to.

So the composition is a function of the two symbols and it is not digitwise. It is a table, or a rule with cases, and the sweep establishes that such a table exists rather than exhibiting it.

Tameness survives addition #

A heap is tame when its genus is the genus of some Nim heap, which is what makes the substitution useful: a tame heap can be replaced, in any misère sum, by the Nim position with its symbol. What a tame heap may be replaced by is that rung.

Of the 405 pairs, 352 are pairs of tame heaps, and all 352 have tame sums. Not one exception.

That is the property the classification needs to be a property of a game rather than of each position separately. A game all of whose heaps are tame is a game whose every position is tame, so the whole of it can be analysed as Nim under the misère convention — and the single wild heap that ruins the analysis ruins it because a sum containing it need not be tame, not because the heap itself is unusual.

Six wild heaps in eighty-one #

The population the last two sections rest on is small enough to name in full.

Eighty-one single heaps were computed — nine games, nine heaps each — and six of them are wild. Kayles has two, at heaps five and nine. Dawson’s chess has one, at heap nine. The code $\cdot 6$ has one at heap seven, $\cdot 36$ has one at heap eight, and $\cdot 127$ has one at heap nine.

Nim, $\cdot 07$, $\cdot 007$ and $\cdot 31$ have none at all: every heap of those four is tame, all the way to nine, so their misère analysis within this range is Nim’s misère analysis with a substitution.

Six wild heaps in eighty-one is seven per cent, and it is worth noticing where they sit. Not one is below heap five, and three of the six are at heap nine, which is the largest computed. Wildness arrives late, which is exactly what makes it dangerous: a game examined at small heaps looks tame, the substitution looks sound, and the first counterexample is out past where anybody checked.

That is the same shape as the periodicity situation and it has the same remedy. A window of computation settles nothing unless something says how far the window has to reach, and for wildness there is no such theorem here.

Two wild heaps that add to a tame sum #

Forty-six of the 405 pairs are mixed — one tame heap and one wild — and only two of those forty-six come out tame. So a wild heap almost always makes the sum wild, which is what a reader expects and what makes wildness feel like a contaminant.

Seven of the 405 are pairs of two wild heaps. All seven come out tame.

That is a genuine surprise and it is worth being careful about what it does and does not show. It does not show that wildness cancels in general: seven pairs is a small number, and the wild heaps in this sweep are six positions from five games — Kayles at heaps five and nine, Dawson’s chess at nine, $\cdot 6$ at seven, $\cdot 36$ at eight and $\cdot 127$ at nine — so the seven pairs are drawn from a very small population. What it does show is that wild is not a stain that spreads — a sum of two positions the Nim analysis cannot handle can be a position it handles perfectly.

The mechanism is not mysterious once stated. A wild heap has a genus that no Nim heap has; two of them can have genera whose combination is a genus some Nim heap does have, in the same way that two irrational numbers can sum to an integer. The sum is tame because its symbol is a Nim symbol, and nothing requires its parts to have been.

Seven pairs is a number small enough that the honest thing to do is widen the window and look again, and the sweep is cheap enough to run two heaps further.

So the seven-for-seven is a small-sample effect and the finding underneath it is not: a sum of two wild heaps is usually tame and is not always tame, which is a weaker and more useful statement than the one nine heaps supported. The claim that survives the widening unchanged is the one the whole classification rests on — the pair of symbols determines the answer, on 594 pairs as on 405.

The claim, restated as what a solver may do #

Putting the counts together gives the licence the genus was invented to give, with its conditions attached.

A solver may carry one symbol per heap. The sum’s symbol is a function of the symbols, so the heaps themselves need never be revisited — 405 pairs, seventy-nine files, no file with two answers.

It may not compute that symbol digitwise. The base is an exclusive or and the superscript is not, so the composition needs a table or a rule with cases, and a solver that reached for exclusive or on both halves would be wrong on 402 of the 405.

It may treat a board of tame heaps as Nim. Tameness is closed under addition on all 352 tame pairs, so a game whose heaps are all tame has a complete misère analysis by substitution.

And it may not assume wildness is fatal. Two wild heaps came out tame seven times in seven at nine counters and nineteen times in twenty-two at eleven, so a sum containing wild parts is usually tame and still has to be computed rather than written off.

The four together are what the classification is worth, and none of them is obvious from the definition.

What the whole thing is for #

The genus exists to make a misère analysis look like a normal-play one, and the sweep says how far that succeeds.

It succeeds completely on the arithmetic: symbols compose, so a board of heaps can be reduced to a symbol per heap and then to one symbol, and no heap needs to be looked at twice. It succeeds completely on tameness, which is closed under addition. And it fails, in the sense that matters, on the wild positions — where the symbol is not a Nim symbol, the substitution is unavailable, and the analysis has to fall back on something else.

That something else is the misère quotient, which is a much heavier object: instead of one symbol per heap it computes the whole monoid of positions-up-to-indistinguishability for that particular game. The quotient is exact where the genus is not, and it is expensive in a way the genus is not.

So the genus is the cheap tool, and this rung is a measurement of how much of the job the cheap tool does.

Determining and describing are two properties #

The genus is called a partial invariant, and the phrase runs together two claims that this anchor spends three rungs separating. It is worth having them apart before the rungs above are read.

Determining is the claim that two positions with the same symbol are interchangeable for the purpose in hand — that the symbol is enough information, so a function of it exists. That is a statement about the invariant’s resolution.

Describing is the claim that the function has a short rule. That is a statement about the invariant’s arithmetic, and it is a different and stronger thing.

An invariant can determine without describing, which is the situation the wild side turns out to be in: the pair of symbols fixes the answer, and no rule of the expected shape computes it. It can also describe without determining, which is the failure a small pool hides — a rule that works on every pair tested because the pool never contains two positions with one symbol and two answers.

A census supports the two claims with different evidence and a count does not distinguish them. Right on 238 of 252 is consistent with a rule that describes a real function and with a rule that happens to fit a pool where the function does not exist, and telling them apart means looking for pairs that share a symbol rather than for pairs the rule gets wrong.

That is the check to run before widening anything. If two positions with the same symbol have different sums, no rule can work and the invariant needs refining. If they never do, the function exists and the search is for a formula — and those two situations call for completely different work.

What the sweep cannot say #

Heaps up to nine, in nine games, with superscripts computed to six terms. Every one of those is a limit and each could hide something.

Nine heaps is small. Kayles’ normal-play sequence is periodic only from heap seventy-one, so the first nine heaps of any octal game are its least representative ones, and a splitting file might well appear further out. Two heaps further out it does not — 594 pairs, 124 files, none of them holding two answers — and two heaps is not far. What the widening does change is the population the wild counts are drawn from: thirteen wild heaps instead of six, from six games instead of five, with $\cdot 07$ going wild at ten after nine tame heaps.

Six terms of superscript is a truncation. The superscript is an infinite sequence and it is settled — eventually constant — for every symbol here, but eventually is doing work and a symbol whose superscript settles later than six would be recorded wrongly.

And nine games is a sample, chosen for short rule tables rather than for variety of behaviour. The claim tested is the one the literature makes, and this sweep is evidence for it rather than a proof of it; the composition rule itself — the table that says which symbol two symbols produce — is not exhibited here at all, only shown to exist over this pool.

The convention this is entirely about #

Misère play: the player who cannot move wins. Every number above changes if that clause is reversed, and most of the apparatus disappears — under normal play the genus is redundant, because the base is the whole answer and the superscript never has to be consulted.

That is worth stating as the reason the object exists. The genus is a normal-play Grundy value with a misère correction stapled to it, and the sweep above is the measurement of how much correction is needed: the base composes for free, the correction does not compose digitwise, and the pair composes as a function.

Where the ladder goes next #

The genus anchor has three rungs to here, and the three above take the composition question from a rule to a function to something that is neither.

The rule the symbols follow states the composition explicitly and scores it: 238 of 252 pairs, with the failures exactly the wild ones, which looks like a rule with a clean boundary. A function with no formula widens the sweep two heaps and the boundary evaporates — the rule is wrong on 34 of 35 wild pairs and right on one, which is a coincidence rather than a class.

What survives is stranger than the rule was. The pair of symbols still determines the sum on the wild side — two wild heaps with the same pair give the same answer — and no rule of that shape describes what the answer is. A function exists and has no formula, which leaves a table as the only object available.

The wild side does not close then asks the two structural questions that would have made such a table finite and useful, and both come back no. Not one of the twelve entries is a symbol 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 preserved either — which is why a wider sweep produces a diagonal rather than a table.

So the anchor ends with the genus doing exactly what a partial invariant does: it determines the answer everywhere and describes it only on the half that was easy.