A parity with a first exception

The game that is a number system sets up Sylver Coinage and then admits what everybody who writes about it has to admit: nobody knows who wins. Two players name positive integers; a number may not be named if it is a sum of copies of numbers already named; whoever is forced to name 1 loses. After two coprime numbers are down, the position is finite and can be solved outright, and that essay solves every such opening in range. The opening position itself is not finite, and the status of the single move 16 has carried a prize on it for decades.

That is the honest state of the game and it is not the whole of what can be said. A position of Sylver Coinage is a numerical semigroup — the set of numbers already reachable — and the numbers still unnameable are its gaps. So the positions are a well-studied family of objects that come in a natural order: by genus, the number of gaps. Genus 1 is one position, genus 2 is two, genus 15 is 2,857. Each genus is finite, so each genus can be solved completely.

Solve all of them and something falls out that the opening position gives no sign of.

Odd rows: 25 per cent, 50, 38.5, 28.8, 27.4, 26.2, 21.5. Even rows: nought, nought, nought, 1.5, 5.4, 7.8, 4.8.

Fifteen rows, and the thinnest odd row is more than twice the thickest even one. The count of numbers a player cannot name is a quantity nobody chooses and nobody controls, and its parity is very nearly the whole game.

What the census is a census of #

Before anything is read off that table it is worth being clear what is in it and how confident the counting is.

The rows are the numerical semigroups: 1, 1, 2, 4, 7, 12, 23, 39, 67, 118, 204, 343, 592, 1001, 1693, 2857. Those numbers are known independently of anything on this site — they are counted in the literature on numerical semigroups, they grow roughly like the Fibonacci numbers, and getting them right is a non-trivial thing to do. The enumeration here builds each semigroup exactly once by a standard tree, and the counts are checked against the known ones row by row. A miscounted row does not produce a slightly wrong share; it produces a wrong denominator and a wrong set of positions, and the check is the first thing that fires.

The outcomes come from a recursion on the semigroups themselves rather than on lists of named numbers, which makes it an independent implementation of the game from the one the game that is a number system uses. Both say the same thing about the positions both can reach. The base is a single position and it is worth stating because everything rests on it: genus 1 is the semigroup with 1 as its only gap, its only legal move is to name 1, and naming 1 loses. The mover loses. If that came out the other way, every row beneath it would invert.

The upper limit is genus 15, which is 2,857 positions and about seven thousand in total. That is not a limitation of patience; it is where a boolean-per-semigroup recursion stops being instant. Genus 20 is 37,396 positions and would take an afternoon.

Why genus is the right clock #

One thing the table deliberately does not do is order the positions by anything except genus. There are other natural orderings — by the smallest nameable number, by the largest unnameable one, by how many generators the semigroup needs — and each would produce a different-looking census of the same objects. Genus is the right one here for a reason that is about the game rather than about the semigroups: it is the only one of those quantities that a move is guaranteed to change. Naming a number always removes at least one gap. It need not change the multiplicity, it need not change the number of generators, and it can leave the Frobenius number where it was. So genus is the game’s own clock, and sorting by it is sorting by how far the position is from the end.

That also settles a question the phrase “solved completely” might otherwise leave open. The recursion terminates because genus strictly decreases, and it stays inside the table because a move never raises it. Each row can be computed from the rows beneath it and nothing else, which is why a census by genus is a solution and a census by multiplicity would not be.

Where the parity comes from #

A tendency this strong has a mechanism, and the mechanism is one line.

Name the largest gap — the Frobenius number — and exactly one number leaves the gap set: that one. Every other gap is smaller, so naming the largest cannot have made any of them reachable, because the only new sums are the Frobenius number itself and things larger than it, all of which were already nameable. The genus falls by one and by no more.

That move exists in every position with a gap above 1. So every position has a move to the rung directly beneath it, and a game in which naming the Frobenius number were the only move would be exactly the game of removing one counter from a pile: odd loses, even wins, no exceptions. The parity in the census is that game showing through.

What breaks it is that the other moves exist. Naming a smaller gap can close several at once — name a small number and everything reachable from it closes too — so there are moves that jump two or three rungs down, and those are what a player uses to get out of a bad parity. The census is the record of how often that escape is available.

The lemma is checked on every one of the 6,962 positions in range rather than argued for and left. It is the sort of claim that is obviously true once stated and obviously true in a way that would survive an off-by-one in the code; so the figure computes the drop for each position’s Frobenius number and refuses to draw if a single one of them is not exactly one.

Those two are the parity in its purest form. Genus 1 has no choices. Genus 3 has three moves and all of them are bad. What the census asks is how long that keeps happening.

It is worth working the genus-3 position through, because it is the smallest place where the parity has to be earned rather than forced. Its gaps are 1, 2 and 3. Naming 1 loses on the spot. Naming 2 closes 2 and, with 2 nameable, closes nothing else below 4 — but 3 remains a gap, so the result is genus 1, the position the opponent then loses from. Wait: it is the opponent’s move from genus 1, and genus 1 is a loss for whoever must move. So naming 2 hands the opponent a loss and the mover wins.

That is the wrong answer, and following it through is the point. Naming 2 from gaps {1, 2, 3} does not leave gaps {1, 3}: with 2 nameable, 4 is a sum of two 2s and was already nameable, but 3 is not reachable from 2 alone, so the gaps are {1, 3} and the genus is 2, not 1. Genus 2 is a position the mover wins. Naming 3 similarly leaves gaps {1, 2} — genus 2 again, another win for the opponent. So all three moves lose and the position is a loss for the mover, and the parity holds because the two available non-losing moves each drop the genus by exactly one, into a row that is entirely wins.

The near-miss above is the kind of arithmetic slip the assertions in these figures exist to catch, and it is why the drop is computed for every position rather than reasoned about for one.

Reading the table the other way #

There is a second thing in the census that has nothing to do with parity, and it is easy to walk past.

The odd rows are not near 100 per cent. Genus 5 is the highest at exactly half, and after that they fall steadily. So even in the parity’s favoured rows, most positions are wins for the mover — the parity is a statement about a minority being unusually large, not about the odd rows being losses.

That matters for what the rule is good for. A player who knew only the parity of the genus would be right about a genus-15 position 78.5 per cent of the time by guessing “the mover wins” — and would be right 78.5 per cent of the time by guessing that at genus 14 as well, where the true figure is 95.2. The parity is a real signal about the population and a poor guide to any particular position, which is the ordinary situation with a statistic and an unusual one for a combinatorial game, where the quantities are normally exact or absent.

The first exception #

Genus 2, 4 and 6 hold nothing at all: 2 positions, 7 positions, 23 positions, and on every one of the thirty-two the player to move wins. Then the rule breaks.

One position, at genus 8, out of sixty-seven. Its gaps are 1, 2, 3, 5, 6, 7, 10 and 11 — so 4, 8, 9 and everything from 12 upwards can be named, and the position is the semigroup generated by 4, 9, 14 and 15.

Nothing about the strip announces itself. It is a perfectly ordinary numerical semigroup with multiplicity 4 and Frobenius number 11; there are several others of genus 8 that look very much like it and are wins for the mover. What makes it a loss is that every one of its eight moves — and there are eight, one for each gap — reaches a position from which the opponent wins, and there is no way to state which of those eight closures is doing the work, because they all are.

That is the shape of the whole subject in one position. The finite answer exists, it is a boolean, and it has no shorter description than the search that produced it.

The obvious follow-up is whether the exception is nearly a win — whether it is a loss by a narrow margin that some small change would flip. That question has no content here and it is worth saying why. In a scoring game a position can be lost by one point, and a near-miss is a real thing to measure; comparison is a search is about the machinery for asking how close two positions are. In an impartial game under normal play there is no margin. A position is a loss because every move goes to a win, and it would be a win if any single one of the eight went to a loss. There is no eighth-of-a-loss and nothing to be narrow about.

What can be measured instead is how alone it is, and the answer is: completely, at its own genus, and not for long. Sixty-six other positions of genus 8, all wins. Then genus 10 arrives with eleven.

Wearing away from both ends #

Having a first exception is one thing. What happens after it is the more interesting measurement, and it is the one that decides whether the parity is a rule with a footnote or something looser.

Both ends give way at once. The odd rows fall — 50 per cent at genus 5, 38.5, 28.8, 27.4, 26.2, 21.5 at genus 15 — a decline that is not flattening out. The even rows climb: nought, nought, nought, then one position, then eleven, then forty-six, then eighty-one.

Neither movement is fast, and neither shows any sign of stopping. At genus 15 the two are still comfortably apart, and the figure asserts that they are: it refuses to draw if the thinnest odd row ever falls below the thickest even one. That assertion has not fired, and it is the kind of assertion that would fire on the first row where the story stopped being true rather than after somebody noticed.

What the figure cannot say is whether they meet. Two sequences, one falling and one rising, over seven terms each: that is not enough to extrapolate from and it is not honest to try. A period is a proof is about the one situation in this subject where a finite computation settles an infinite question, and it settles it by exhibiting a period that a lemma then shows must persist. Nothing like that is available here. There is no lemma saying the parity persists and no lemma saying it fails, and computing to genus 20 would move the last row of the table without changing what the table can be asked.

What this is worth knowing #

The value of the census is not that it solves Sylver Coinage, because it does not and cannot: every position in it has finite genus, and the opening position has infinite genus, so nothing here touches the question with the prize on it. What it does is change the shape of what is unknown.

Before the census, the natural picture of the game is a fog with a few solved islands in it — the game that is a number system solves the two-generator openings, and around them nothing. After it, the finite part of the game has a visible structure: a parity that very nearly decides everything, produced by a move that is always available, eroded by moves that are sometimes available, with the erosion measured. That is a considerably more useful thing to be uncertain about.

It also places the game precisely against its neighbours. Where the impartial theory stops collects games the general theory does not settle, and they fail in different ways. Some have Grundy values that resist a formula; some have no useful sum structure at all. Sylver Coinage is neither: every finite position has a Grundy value, the recursion computes it without difficulty, and the difficulty is entirely that the positions anybody cares about are not finite. It is a game where a bound instead of an answer is not even available, because the quantity that would be bounded is a single bit.

And the parity itself is worth carrying as an example of a particular kind of near-theorem. It is not a heuristic somebody noticed; it has a proof of the mechanism — the Frobenius move always steps one — and the proof is exact and checked on every position. What it does not have is a proof that the mechanism dominates, and it manifestly does not dominate everywhere, because there are 139 positions in range where it fails. A rule with a mechanism and no proof of sufficiency, wearing away steadily as the objects get larger, is a common shape in this subject and it is easy to mistake for either of the two things it is not: a theorem, or a coincidence.

There is a narrower lesson about the shape of the computation, and it is the one worth taking to another game. The parity here comes from a move that is always available and always small. That is a structure worth looking for anywhere the positions have a natural size: if some move always reduces the size by exactly one, the game inherits a parity, and the interesting question becomes how often the larger moves let a player escape it. Nim and the nim-sum is the extreme case where the escape is always available and the parity is entirely gone; one part that never ends is the other extreme, where the size does not decrease at all. Sylver Coinage sits between them and the census is a measurement of exactly where.

The last thing the table does is make the next question askable. Sylver Coinage’s finite positions are the numerical semigroups, and numerical semigroups are studied for reasons that have nothing to do with games — their counts by genus, the shape of their gap sets, which of them are symmetric. Every one of those properties can now be asked against the outcome column. Whether any of them predicts it is a question this census makes precise and does not answer, which is the right place for a rung to stop.