Closing the wild side

A genus symbol records how a heap behaves under misère play — its Grundy value and a tail saying what happens when nim-heaps of various sizes are added. Tame and wild splits the heaps into the ones whose symbol follows the pattern nim-heaps follow and the ones whose symbol does not, and the tame half is closed under addition: a sum of tame heaps is tame.

The wild side does not close measured the other half and found that it is not: the twenty-two wild symbols in the sweep produce twelve further symbols when added, none of which is one of the twenty-two. That page closed by naming the object and offering two answers:

the obvious object is the set reached by closing the twenty-two of them under addition — is it finite, and if so how large? … If the closure is finite it is a monoid after all, just not the one the rung below guessed; if it is not, the wild side has no algebra at any size.

The answer is neither, and it is more useful than either.

First, that there is a closure to compute #

Closing a set under an operation presumes there is one. Adding two heaps and reading the symbol of the sum is an operation on heaps; whether it descends to an operation on symbols is a separate question, and if two pairs of heaps with the same pair of symbols gave sums with different symbols there would be nothing to close.

They do not. Twenty-two pairs of wild symbols occur in the table and none of them has more than one answer. Twelve of the twenty-two occur more than once — the commonest fourteen times — and every occurrence gives the same symbol.

So the rung below’s question is well posed, which was not obvious and is not a formality: much of what makes misère play difficult is precisely that a heap’s symbol does not determine its behaviour in a sum, and here, on this table, it does.

It is worth being careful about what that establishes. Single-valuedness on the pairs that occur is not the same as the symbol determining the sum in general — a pair occurring once is single-valued for free, and the content is in the twelve pairs that occur repeatedly. Those are the ones that could have disagreed and do not. So the statement is: within this sweep, no two pairs of wild heaps with matching symbols give sums with different symbols.

The genus was designed to have that property and it is known not to have it everywhere; what this table shows is that the failures are not here. That is why the rung below could build the table at all.

What the closure reaches #

The sweep runs to heaps of ten and to sums of four, and both bounds are set by what a misère game tree costs rather than chosen. A genus symbol is computed by walking the whole tree of a position under both ending conventions, and the tree of four heaps of ten is the largest the build affords; the enumeration over combinations of wild heaps is on top of that.

Six games in the genus pool have a wild heap of at most ten. Close each one’s wild symbols under addition — take sums of two, three and four wild heaps and collect every symbol that appears — and five of the six stop producing new ones.

·07, Dawson’s chess, ·6 and ·36 reach everything they are going to at three heaps, with closures of two symbols each. Kayles reaches everything at four, with a closure of five. ·127 is still producing new symbols when the sweep stops, and its closure is at least eight.

That is a graded answer and the grading is not by symbol. It is by game.

The closures are also small in absolute terms, and their smallness is the part worth carrying. Two symbols is a closure with almost nothing in it: one wild symbol, its double, and that is the whole algebra. Five, for Kayles, is a set a reader can hold in mind. Nothing here needs a table of twenty-two anything — the twenty-two wild symbols of the rung below are twenty-two symbols spread across six unrelated games, and no game contributes more than a handful.

Why that is the useful answer #

The two answers the rung below set out were both about the wild symbols as a set: either they close or they do not. What the measurement says is that the question does not have a symbol-level answer, because the closure of a game’s wild symbols is a fact about that game’s move rule.

That should have been expected in hindsight and was not. A genus symbol is a summary of a heap in one game; two games can produce heaps with the same symbol and quite different sets of reachable sums, because the sums available depend on which heap sizes the game has. So the wild symbols of the pool is not a set that adds — it is six sets that each add among themselves.

Read that way the finding is a positive one. On most of these games the wild side does have an algebra, and it is small: a handful of symbols, closed after three or four heaps. What the genus cannot do is give one algebra covering them all, which is a weaker failure than having none.

The distinction matters for what anybody should do next. A universal algebra of wild symbols would be a theorem about misère play; six small per-game algebras are six facts, and facts of that shape are what the subject already collects. So this page does not open a route the genus had been blocking — it says the route was never there, and explains why the blockage looked like one.

There is also a warning in it about how the twenty-two were counted. Pooling the wild symbols of six games into one set of twenty-two is what makes the wild symbols are not closed true, and the pooling is the reason. Each game’s own symbols very nearly are closed; adding a symbol from another game to one of them is not an operation anybody can perform, since the two heaps are in different games.

The level-by-level view shows the shape of it. The additions fall at every step on every game, never rising — checked rather than described, since a game whose additions rose would be one whose closure is not being approached at all. Four games run out at the third heap, Kayles at the fourth, and ·127 is still adding one when the sweep stops.

The one that does not close #

·127 deserves its own paragraph because it is the only evidence in either direction about what an unbounded closure would look like.

It begins with two wild symbols, adds three at two heaps, two at three, one at four. That is falling, and it is falling towards something. Whether the something is nought — a closure of eight or nine, reached at five or six heaps — or a slow unbounded growth is exactly what the sweep cannot see, because sums of five wild heaps are beyond it.

The honest reading is that ·127 looks like the others, only slower. Every game that closed did so after its additions had fallen to one, and ·127 is at one. But looks like is not a measurement, and the previous rung on this anchor is a standing reminder that a pattern in a genus table can stop without warning.

It is also the game with the most wild material to work with, which cuts both ways. More wild heaps means more pairs, more triples and more chances for a new symbol, so a slower closure is what a larger starting set would produce whether or not the closure is finite. Distinguishing large and finite from infinite needs the level where the additions reach nought, and that level is one further out than the sweep goes.

What this does to the quotient #

The reason any of this matters is that misère quotients exist because the genus does not do what a general invariant would. A quotient is built per game, by hand or by search, and it is the subject’s answer to the genus’s failure.

This page sharpens what the failure is. It is not that the wild symbols have no algebra — five of six games’ do. It is that the algebra is per game, which is precisely the property a quotient has and an invariant does not. So the genus’s wild half and the misère quotient are closer objects than the anchor has been treating them as: both are per-game algebras of the same rough size, and the difference is that a quotient is designed to be one and the genus’s closure turns out to be one by accident.

That suggests a comparison nobody has made, and it is cheap: for a game whose wild closure is small, is the closure related to the misère quotient — a sub-object, a quotient of it, an unrelated thing of similar size? Kayles has a closure of five symbols and a known quotient, and the two can be put side by side.

There is a reason to expect them to be related and a reason to expect them not to be. A quotient identifies two positions when no third position tells them apart, and a genus symbol identifies two heaps when a particular family of third positions — the nim-heaps — does not tell them apart. So the genus is a quotient by a smaller test set, and a quotient by a smaller test set is coarser: the genus should identify more than the misère quotient does, and its closure should be a quotient of the quotient. Against that, the genus’s tail is a finite truncation, so it also identifies things the full test would separate for a reason that has nothing to do with the game.

What a tame heap may be replaced by is where this anchor established that a genus symbol licenses a substitution, which is the same statement in the language a quotient uses, and it is the page the comparison would start from.

What a closure of two looks like #

Four of the six games have a closure of exactly two symbols, and it is worth writing one out, because two is small enough that the algebra can be stated rather than described.

·36 has one wild heap of ten or fewer — heap eight — and its symbol is $3^{1431}$. Add two of those heaps and the sum’s symbol is $0^{120}$, which is tame and is the symbol nought has. Three copies give $3^{1431}$ again, four give $0^{120}$, five give $3^{1431}$.

So the closure is two elements with the multiplication of a group of order two: the wild symbol is its own inverse, and an odd pile is wild while an even pile is not. That is exactly the structure two heaps of Nim have, and it is why the closure is small — the wild symbol is behaving, in sums with itself, like a single star.

Three of the other four two-element closures have the same shape, and Kayles’s closure of five is the only one in the pool with any room in it. So the honest summary of what closing the wild side reaches is: on five games out of six, almost nothing — a couple of symbols alternating with parity — and the interest is entirely in the two exceptions.

What it is not doing is behaving like a star in sums with anything else, which is what wildness means and what the rung two below established. So the small closure is not evidence of tameness; it is evidence that wildness is a statement about a heap’s interaction with the tame world, and says nothing about how the heap interacts with itself.

What is measured #

Heaps to ten and sums to four. The sweep enumerates every combination of wild heaps up to four at a time, which is the size the misère game trees allow. Sums of five would settle ·127 and are out of reach.

Six games, not the whole genus pool. Three of the nine codes in the pool have no wild heap at all in range, so they contribute nothing to close.

And the closures are of symbols, not of heaps. Two different sums can give the same symbol and are one element of the closure; the closure being small does not mean the reachable positions are few. That is the same distinction the genus rests on throughout — a symbol is a summary — and it is why a small closure is a statement about the invariant rather than about the game.

The tail is truncated at six. A genus symbol’s superscript is an infinite sequence and every table on this anchor computes a prefix of it; six is what the rest of the site uses and is enough for every symbol here to have settled. Two symbols agreeing to six places and differing at the seventh would be counted as one throughout, which would make every closure here a lower bound rather than a count. Nothing in range does that, and the check is the same one the rung that built the table ran.

What closure at three means and does not mean #

Closing at three is a smaller claim than it sounds and a more useful one than the alternatives the rung below offered.

It does not say the wild symbols form an algebra. It says that for five of the six games, the set reached by adding wild symbols to each other stops growing after three rounds — the closure is finite and can be written out. A finite closure is enough to compute with and is not enough to explain: the table it produces has no shorter description than itself, which is exactly the situation the genus was introduced to escape.

The sixth game is the one that keeps the result honest. A single game whose closure does not stop at three means the number three is a fact about five games rather than about wildness, and any rule quoting it would be quoting a coincidence.

Where the ladder goes next #

The genus anchor has seven rungs: what the genus is, what a tame heap may be replaced by, that the symbols compose, the function that composes them, that no rule of that shape reaches the wild side, what the wild table looks like, and now what closing it reaches.

What the closure is for is the arithmetic, which is where the genus was going all along: the genus of a sum is the composition rule this anchor started from, and what misère play costs is the price of not having it.

The rung above is the comparison with the quotient. This page ends with two objects of the same size and the same per-game character — a game’s wild closure and its misère quotient — and no account of how they are related. Kayles is the natural case: a closure of five symbols against a quotient the literature has, and the question is whether the symbols are functions on the quotient’s elements, which is checkable directly.

Two neighbours are worth the trip. Tame and wild is where the tame half is shown closed, and it is the contrast that makes this page’s five-of-six an interesting number rather than an obvious one. And a function with no formula is the other place on this site where an invariant turned out to be per-game rather than universal, and the two failures have the same shape.