A function with no formula

The genus is an invariant for misère play that works on the games behaving like Nim and fails on the rest — tame and wild is the classification, and defined up to tameness is the standing caveat attached to every statement about it.

The rule the symbols follow wrote the composition rule out and measured that caveat: over 252 pairs of heaps in nine games, the rule is right on all 238 tame pairs and wrong on all fourteen with a wild heap in them. It closed on what is on the other side:

The rung above is the wild side. Fourteen pairs break the rule and they are in hand, with both symbols and the answer; what a wild symbol does in a sum is a question with data behind it for the first time. The likely answer is that nothing of this shape exists.

Nothing of that shape does exist. But the reason is not the one the sentence expects, and the boundary the rung below reported does not survive two more counters.

The composition is still a function #

File every pair of heaps under the unordered pair of its components’ symbols, and ask whether a file ever holds two different sums. On 405 pairs across 76 files, none does.

That includes the sixteen files with a wild symbol in them, which is the part nobody had checked: the literature asserts the composition for tame positions and says nothing about whether it is even well defined outside them. So the statement the genus symbol of a sum is determined by the genus symbols of its parts holds on this pool with no tameness condition at all — which is a good deal more than the literature’s statement, and considerably more than the rung below’s rule needs.

The base is never the difficulty. The base of a sum is the exclusive-or of the bases on all 405 pairs, wild included, because the base is a normal-play Grundy value and normal play has never heard of tameness. Every failure of every rule below is in the superscript.

The rule, two heaps further #

The rung below asserted two things and one of them has now failed:

• no tame pair breaks the rule — still true, on 370 pairs;
• every pair with a wild component breaks it — false at nine counters, where 34 of 35 break it and one does not.

The exception is Kayles’ heaps of five and nine: symbols $4^{146}$ and $4^{046}$, sum $0^{02}$, which is what the rule gives. Neither heap is fickle so the rule’s second clause does not fire, the bases exclusive-or to nought, and the firm shape it then predicts happens to be right.

That is an accident and it is the point. A rule wrong on fourteen out of fourteen looks like a rule that fails on a class; a rule wrong on 34 out of 35 is a rule that fails on a class and occasionally gets lucky, which is a weaker and more honest statement. The rung below’s boundary was exact on its own pool and the pool stopped one heap short of the exception.

One more thing about the accident is worth recording, because it is a lesson about assertions rather than about games. The rung below’s boundary was written as two assertions in the code — no tame pair may fail, no wild pair may succeed — so that either would stop the build. That is the right way to hold a claim, and it did exactly what it was built to do: raising the sweep from seven counters to nine turned the second assertion red, and the red was the finding.

An assertion that fails when the pool grows is an assertion doing its job. The alternative — a sentence in prose saying the boundary is exact — would have been carried forward unchanged and would now be wrong.

Nothing of that shape works #

Three candidates are available without inventing anything:

• the tame rule — right once, by the accident above;
• the exclusive-or of the tails, digit by digit — the natural generalisation of what the base does, and right on none of the 35;
• inheriting the wild component’s symbol — the reading that a wild part dominates the sum, and right on none.

So a rule of that shape does not exist on the wild side, which is what the rung below predicted. The three candidates are not arbitrary: they are the three things the tame rule’s own parts suggest — keep the rule, generalise the exclusive-or from the base to the tail, or let the wild part decide — and between them they cover what anybody would try first. What it did not predict is that the function does exist: the answers are determined, they are simply not described by anything short of listing them.

That gap — a determined answer with no rule for it — is the exact situation the misère quotient was invented for. Misère quotients do not look for a general invariant at all; they compute the algebra of one game’s own positions, and the reason they are the state of the art is that the general invariant this page is prodding does not exist.

Wildness is not inherited #

Five of the 35 wild pairs have a tame sum, and the count is exact rather than approximate: the sweep computes tameness of the sum directly from its symbol. That is worth stating on its own, because the word wild invites the reading that wildness is a contamination: a wild heap anywhere makes the whole position beyond the theory.

It does not. A wild component plus the right partner is tame, and the resulting position is one the genus handles perfectly well. So tameness is a property of a position rather than of the heaps it contains, and a wild heap is a position that behaves oddly in the company it usually keeps rather than a defect that spreads.

That is the same lesson the fickleness clause teaches one class up: a component’s property need not be a sum’s. Fickleness survives only unanimity — a sum is fickle exactly when every part is — and here wildness fails to survive at all in five cases out of thirty-five.

What the wild answers look like #

The 35 wild sums are not chaos, and it is worth saying what is visible in them even though no rule came out.

Their bases are forced, so every one has the right base. Their superscripts differ from the tame prediction in small, repeated ways — a digit inserted at the front, or the same two digits in the other order — and the same symbols recur across different pairs. Kayles’ nine pairs containing its wild heap of five produce six distinct symbols between them rather than nine, and two of the six turn up twice.

So the wild side is structured and the structure is per-game. That is precisely what would be expected if the right object were a quotient computed for one game rather than an invariant computed for all of them, and it is the strongest hint this page has about where the description would come from.

What this leaves the genus #

Reading the two rungs together gives the honest state of the invariant, and it is a mixed report.

As a function it is better than advertised. The symbols determine the sum’s symbol everywhere in this sweep, tame or wild, which is stronger than the usual statement.

As a calculus it is exactly as good as tameness. The three-line rule is a calculus — it lets a player compose symbols without computing anything — and it works on the tame class and, apart from one accident, nowhere else. A calculus is a way of getting the answer without the search, and on the wild side there is no way but the search.

And the difference between those two sentences is what an invariant is worth. A determined answer nobody can compute cheaply is a table; a rule is a saving. The genus is a rule on the tame games and a table on the wild ones, and the boundary between them is what both rungs have been measuring.

What a table would cost #

If the description of the wild side is a table, it is worth asking how large a table.

Sixteen files carry a wild symbol in this sweep, so sixteen entries cover every wild pair of heaps up to nine counters in nine games. That is small — smaller than the rule it replaces is long — and it is small for a reason worth stating: the wild symbols themselves are few. Nine games to nine counters produce six wild heaps between them, and their symbols repeat.

The catch is the one every table has. It covers the heaps it was built from, and a tenth counter can introduce a wild heap with a symbol nothing in the table has seen. A rule extrapolates and a table does not, which is the whole of what the rung below’s three lines buy on the tame side and the whole of what is missing here.

Who built the genus, and why it stops #

The genus is Grundy and Smith’s, from the 1950s, and it is the first serious attempt at a misère theory — the convention where almost none of the normal-play arithmetic survives: an invariant that reduces to the Grundy value under normal play and carries just enough extra to survive the change of convention. It works, and it works on the games that behave like Nim.

Tameness is not a technicality attached to the theorem; it is the theorem’s subject. A tame position is one whose misère behaviour is Nim’s, and the genus composes for tame positions because Nim’s does. Wild positions were known to break it from the start, and the response for fifty years was to note the boundary and work inside it.

Plambeck’s misère quotients are what came next, and their premise is the opposite one: do not look for an invariant that works for all games, compute the algebra of one game’s positions. This page is a small piece of evidence for why that reframing was necessary — the composition on the wild side is a function with no formula, and a function with no formula is exactly what a quotient computes.

Existence without description, and why it is worse than either alternative #

The result here has three possible shapes and it lands on the least comfortable one. Setting the three out says why.

No function. If two wild heaps with the same genus symbol could have different sums, the genus would simply not be enough information, and the honest response would be to look for a finer invariant. That is a clean failure and there is a standard next move.

A function with a formula. If the pairs composed by a rule, the wild side would be as usable as the tame side and the anchor would end.

A function with no formula. The pair of symbols determines the answer, so the information is there — and nothing short of a lookup table extracts it. That is the outcome, and it is worse than either alternative for a practical reason: there is no next move. A finer invariant is not wanted, because the current one already determines the answer. A rule is not available, because there is none of the shape anybody would write.

What is left is a table, and a table is only as large as the sweep that built it. That is why the cost of building one is worth pricing rather than waving at: the object being asked for is not a theorem with an unknown proof but a finite catalogue with no obvious end, and the question how big does it have to be has no answer until somebody finds a structure it closes under.

Which is exactly the question the rung above takes, and answers in the negative. So this page’s finding is the one that had to be established first — that the wild answers are determined — because a table of undetermined answers would have been a table of nothing.

What this does not say #

Four limits.

Nine games, nine counters. The sweep is 405 pairs and every claim is about them. The function result in particular is the sort that a wider sweep could break with a single pair, and it would be the more interesting outcome — a wild pair whose symbols do not determine the sum would say the invariant is not even a function past tameness.

Three candidate rules is not every rule. Nothing of this shape exists is shorthand for three natural candidates fail. A fourth built from the fickleness structure, or from the wild symbols’ own periods, is untested here.

The tail is truncated. A genus symbol’s superscript is an infinite sequence written to a fixed number of terms — ten here — and two symbols agreeing to ten terms are treated as equal. A longer tail could separate positions this sweep files together, which would break the function result in the direction the previous limit describes.

Wildness here is the site’s own test, which asks whether a symbol is one of Nim’s; the literature’s definition agrees on these games and the two are not checked against each other on anything wider.

And pairs, not boards. Everything here is two heaps. The rung below checked triples for the tame rule and found it holding; nothing checks triples with a wild component, and the accidental success rate could look quite different there.

The convention, named #

Misère play: the player who cannot move loses. Every game here is impartial and given by an octal code, with Nim as the control.

A position’s genus is $g^{g_0g_1g_2\ldots}$: the base $g$ is its normal-play Grundy value, and the superscript records what its misère Grundy value becomes as copies of a two-counter Nim heap are added. A position is tame when its symbol is one of Nim’s own — the firm shape $g^{g,\,g \oplus 2}$ or the two fickle symbols — and wild otherwise.

A pair is wild here when either component is, and the rule is the rung below’s three lines: the base exclusive-ors, the sum is fickle exactly when every part is, and the symbol follows.

A file is the set of pairs sharing an unordered pair of component symbols; a file with two different sums in it would refute the function claim.

The two findings are worth holding together, because they pull in opposite directions. The composition is better behaved than the literature claims — it is a function everywhere here — and less usable, since no rule of the available shape computes it outside the tame class. A function nobody can evaluate cheaply is a table, and a table is what the quotients build.

Where the ladder goes next #

The genus anchor reaches five rungs to here, and this one leaves the wild side in the worst position a measurement can leave anything: a function that exists and has no description.

The rung above asks the two structural questions that would have rescued it, and both come back no. The wild side does not close builds the wild composition table — which needed a wider sweep, because nine counters a heap produces a diagonal rather than a table — and finds that not one of its twelve entries is a symbol any wild heap carries. So the wild symbols are not closed under addition, there is no small algebra hiding in them, and the hope that the table is a misère quotient in disguise has nothing to attach to.

The second finding is stranger and it explains the first. Two wild heaps added together are tame two thirds of the time. Wildness is not preserved by the operation the table is a table of, so the wild side is not a subsystem at all: it is a set of exceptions that mostly leaves itself under addition, which is why a sweep produces a diagonal and why no closed description was ever going to come out.

Read back to this page that reframes what a function with no formula means here. It is not that the wild answers are complicated; it is that the wild heaps do not form a world of their own to be described. The genus is a partial invariant, the partiality is not confined to a recognisable class, and the class it fails on is not stable under the arithmetic the invariant is for.

Two neighbours are worth the trip. Tame and wild is the classification everything here is bounded by. And misère quotients is the exact machinery all of this approximates — one computation per game, no theory across games — and the reason it is a computation is the reason this page’s function has no formula.