The game that is a number system

Two players take turns naming positive integers. The only rule about what may be named is that a number cannot be named if it is a sum of numbers already named, repetitions allowed. Whoever names 1 loses.

No board, no pieces, no position to draw. And yet every position of this game is a well-studied object with a literature of its own, the reason the game ends is a theorem published in 1884, and the answer to the second move of the game is unknown and carries a prize.

It is the only game in this field that was invented by a mathematician rather than found among people playing it, and it is in this field anyway — for a reason that turns out to be the reverse of every other essay here, and that the last third of this one is about.

The position is a semigroup #

Once some numbers have been named, the numbers that are out of play are exactly the sums of them. That set — closed under addition, containing zero — is a numerical semigroup, and it is the object the whole of this essay is about.

Its complement in the positive integers is the set of gaps, and the gaps are the legal moves.

That largest gap has a name: the Frobenius number, the largest amount that cannot be made from coins of the given denominations. Sylvester wrote about it in 1884 and gave a formula for two coprime denominations, and the formula has nothing to do with games.

Why the game ends #

Every game on this site needs a reason to stop, and this one’s reason is the strangest on the site.

Once two coprime numbers have been named, only finitely many integers remain unrepresentable. That is not obvious and it is the content of the Frobenius result: past a certain point every integer is a sum, so past that point there is nothing left to name. Each move consumes one gap; the gaps are finite; so play ends.

Compare with the games this site usually studies, where termination is trivial — a subtraction game ends because heaps shrink, Nim ends because counters leave. Sylver Coinage has no decreasing quantity of that kind: the numbers named can be as large as anybody likes and there is no bound on them in the rules. What decreases is the genus of the semigroup, and knowing that it decreases requires a theorem in number theory.

That is worth sitting with. The termination clause that Bouton could take for granted in Nim, and that Zermelo’s theorem requires as a hypothesis, is here a nontrivial result imported from another subject.

What this site can settle #

From a position with two coprime numbers named, the game is an ordinary finite impartial game under normal play and can be solved exhaustively. That is done here.

The reason the site settles only one is not modesty. After a single number n is named, the position has infinitely many moves: every integer that is not a multiple of n remains nameable, and there are infinitely many of those. No search reaches an opening, and no search ever will.

From the second move on it is different. Two coprime numbers leave finitely many gaps, and the whole game tree from there is finite.

The second move, solved #

So the honest boundary of this site’s own knowledge is exactly one move in.

Every position of the form “5 and 7 have been named” and its relatives can be solved completely: the gaps of ⟨5, 7⟩ are 1, 2, 3, 4, 6, 8, 9, 11, 13, 16, 18 and 23, of which eleven are legal moves, and the player to move wins by naming 8. That is a complete answer to a specific position, obtained by search, and it is the kind of thing this site is for.

Run it over every coprime pair up to twelve and a pattern appears that is more striking than the individual answers: almost every such position is a win for the player to move, and almost always by exactly one reply. The exception is ⟨2, 3⟩, whose only gap is 1 — so the player to move must name 1 and loses.

One winning reply out of a dozen legal moves is a needle, and it is the same shape Chomp’s openings have. A game with almost no P-positions is a game where a player who does not know the answer will not stumble into it.

The needle is also, in this game, unpredictable, and the sweep says how badly. Over the thirty-four coprime pairs up to twelve, thirty-three are a win for the player to move and twenty-nine of those have exactly one winning reply. The replies themselves run from 2 to 49 and bear no visible relation to the denominations: from ⟨5, 7⟩ the reply is 8, from ⟨5, 8⟩ it is 7, from ⟨5, 11⟩ it is 4, and from ⟨5, 12⟩ it is 33.

Two of those replies are worth drawing, because they are the case a player would never try.

That is the opposite of the heuristic the last section of this essay ends on, and it is not an accident of six gaps. The same thing happens at more than twice the size, where there are fifteen legal moves to choose from instead of five.

Four of the thirty-three winning pairs behave that way — ⟨2, 5⟩, ⟨4, 5⟩, ⟨5, 6⟩ and ⟨5, 9⟩ — and ten of them win with a reply of 3 or less instead. Both extremes occur and nothing separates them, which is the computational fingerprint of a game whose losing positions have no known characterisation.

That unpredictability is worth contrasting with the games this site normally solves. Nim’s winning move is a function of the position computable in a line; a subtraction game’s is a lookup in a table with a proved period. Here the answer to each position is a fact rather than an instance of a rule, and a table of facts is what “solved” means for this game at every size anybody has reached.

Grundy values, and why they do not help #

Sylver Coinage is impartial — both players may name the same numbers — so every finite position of it has a Grundy value, and the value of a sum of positions would be the nim-sum of theirs.

That sentence is true and almost useless here, for a reason worth being precise about: there are no sums. The game is played on one position and never decomposes. There is no board to fall apart into regions and no arithmetic to do across parts, so the single most powerful tool in the impartial theory has nothing to attach to.

What the Sprague-Grundy theorem normally buys is that every impartial position collapses to a single Nim heap and that heaps add, and the second half is the half that does the work: it is what lets a board fall into regions and a value be assembled from theirs. Here the first half holds and the second is vacuous.

So what remains is the outcome class, and the outcome class of a finite Sylver position is exactly what the search above computes. An impartial game can occupy only two of the four normal-play outcome classes anyway — a position worth a nimber is P when the nimber is zero and N otherwise, and neither of the two partizan classes is reachable — so for a game that never decomposes, that one bit is the whole of what a value can say. Knowing the Grundy value rather than merely the outcome would matter if the game ever appeared as a component of something larger, and it never does.

That is a real limitation on what the theory offers this particular game, and it explains why the literature on Sylver Coinage is number-theoretic rather than game-theoretic. The interesting structure is in the semigroups, not in the arithmetic of values.

What is known about the openings #

The literature’s answers are worth stating precisely, because the shape of what is known is the essay’s point.

Losing openings. 1, 2, 3, 4, 6, 8, 9 and 12 lose, with complete second-player strategies known. Those are the small numbers of the form 2^a·3^b — the 3-smooth numbers — and the pattern is unmistakable.

Winning openings. Hutchings’s theorem: every prime of 5 or more wins as a first move. Those are the only winning openings anybody has proved.

And then it stops. The next 3-smooth number is 16. The pattern predicts it loses. Nobody has shown that it does, Conway offered a thousand dollars for the answer in 2017, and it remains open.

How much the two results actually cover #

The table above reads as a solid block of answers ending at 16, and that is a fact about where the table was cut. Counting what the two quoted results reach gives a very different picture of the frontier.

The losing openings are the 3-smooth numbers — those of the form $2^a 3^b$ — and there are few of them: 20 below a hundred, 40 below a thousand, 67 below ten thousand. They thin out logarithmically, because a 3-smooth number is a choice of two exponents and the exponents are bounded by a logarithm.

The winning openings are the primes from five up, and primes thin out too, at density $1/\ln n$.

Put the two together and the fraction of openings either result speaks about falls:

Both families have density zero in the integers, so the covered fraction goes to nothing. Whatever is known about Sylver Coinage openings is known about a vanishing proportion of them.

Which moves the frontier down to ten #

That also relocates the boundary, and the relocation is worth being exact about.

The smallest integers neither result reaches are $10, 14, 15, 20, 21, 22, 25, 26, \ldots$ — the composites with a prime factor of five or more. Ten is smaller than sixteen, and the two theorems quoted on this page say nothing whatever about it: it is not 3-smooth, so the losing pattern does not claim it, and it is not prime, so Hutchings’s theorem does not either.

This site is not claiming that the opening 10 is open. It is claiming something narrower and checkable: that the two results this essay states leave it untouched, and that a reader taking the table as a solid block up to 16 has read the shape of the knowledge wrongly. Sixteen is famous because it is the smallest 3-smooth number the pattern predicts and nobody has proved — it is a gap in a conjecture — and the gaps in the coverage start six numbers earlier and never close again.

So the frontier is not a line with answers behind it. It is a sparse set of answers scattered through a sea of silence, and the sea gets deeper: at ten thousand, seven openings in eight are not addressed by either theorem, and no search will ever address one, because an opening leaves infinitely many moves.

That is a considerably stranger position for a game to be in than “unsolved past a certain size”. Most of this site’s open problems are frontiers made of computation, and the next section says so. This one is a frontier made of arithmetic: the answers that exist are indexed by number-theoretic properties, and every integer without one of those properties is simply not in anybody’s account of the game.

The frontier is a strange shape #

Most unsolved problems on this site are unsolved because a search runs out. The octal game ·007 has been computed to enormous lengths and no period has appeared; Sprouts from three spots defeats this site’s own machinery at a million positions. Those are frontiers made of computation.

This one is not. Sixteen is not hard because sixteen is large. It is hard because the position after naming it has infinitely many moves, so there is no search to run out — the first move of the game is already past the edge of what any exhaustive method touches, and it has been since the game was invented.

A frontier made of computation looks quite different, and a subtraction game is the model of it: a Grundy sequence computed to two thousand terms, a period found in it, and a certificate that the period is real because the recursion cannot see past the window that proves it. Every step of that is a thing a machine does more of when given more time. Sylver Coinage offers no step of that kind, because its positions have unbounded branching from the first move onward — there is no sequence to extend and no window to certify.

That distinction matters for what “unsolved” means. A game with a finite branching factor is unsolved so far; a game whose second position has infinite branching is unsolved in a way that more computing will not touch.

How large a finite position gets #

The positions this site can settle are finite, and it is worth seeing how quickly finite stops meaning small.

Sylvester’s formula says the genus of ⟨a, b⟩ is (a−1)(b−1)/2, so the number of moves available grows quadratically in the denominations — and every one of those moves leads to a position with its own tree. The search is finite and it is not small, which is the ordinary state of affairs and the reason the pair table stops at twelve.

What the formula also says is that small denominations end the game fast. Two and three leave one gap. Three and five leave four. The way to make a Sylver Coinage position last is to name large coprime numbers, and the way to end it is to name small ones — which makes naming 2 or 3 a move that hurries toward the terminal position, and is the beginning of an explanation for why the small 3-smooth numbers lose.

The surprise: a game that is a piece of number theory #

Here is the thing worth carrying away, and it goes in the direction opposite to the rest of this field.

Everywhere else in out in the world, the theory is turned on an object that existed first: a game people played, a rule in a rule book, an ending from a manual. Here it is the other way round. The game came first — Conway invented it — and the object it turns out to be about is one number theory had been studying for a century.

A position is a numerical semigroup. A move adds a generator. The game ends because of the Frobenius bound. The losing positions are semigroups with a property nobody has characterised, and characterising them is a question about semigroups rather than about play.

So this essay is in the applied field for the opposite reason to its neighbours: not because the theory was applied to something, but because a game turned out to be a question in somebody else’s subject, and that subject’s answers are the ones that settled it.

The two directions are worth naming together. A game can receive an existing theory, as Bridg-It receives matroid theory and is solved by it. Or a game can be a question in one, as this is. Both are applications and only the first is what the word usually means.

What the picture cannot show #

The strips above stop just past the Frobenius number, and stopping there is a claim rather than a convenience.

Everything beyond the last gap is representable, so there is nothing to draw — but the picture cannot show why that is guaranteed rather than merely observed. The reason is the stopping rule inside the sieve: it halts after seeing a run of consecutive representable numbers as long as the smallest generator, because from there every larger number is reachable by adding that generator to one of them. That is the proof of finiteness, and it is a property of the algorithm rather than of the picture.

The second thing not shown is the game tree. Every figure here is one position; the game from ⟨5, 7⟩ has a tree with eleven branches at the root and a different semigroup at every node, and the semigroups are what changes rather than any picture. This is the one game on the site with no position to draw at all, and the strips are a representation of the state rather than of the play.

The convention, named #

Naming 1 loses, and that is normal play in disguise.

Since 1 is always nameable until somebody names it, no player is ever without a move — so the game never reaches the “player unable to move” state directly. What happens instead is that a player is left with 1 as their only option, and naming it loses. That is exactly the normal-play convention applied to the gaps above 1: the loser is the player who cannot move among those, and the rule about 1 is the encoding.

The recursion here treats it that way, which is why the same code that solves subtraction games solves this. It is worth noticing because the alternative reading — that this is a misère game, since naming a number loses — is wrong and would attach the whole misère apparatus to a game that does not need it.

Where the ladder goes next #

sylver opens here, and the rung above it is the one somebody will be paid for.

Short of that, there is a rung this site could reach: the structure of the losing positions. Every P-position found by the search above is a numerical semigroup, and asking which semigroups they are is a question with a finite answer for each genus and no known pattern across genera. That is a search this machinery could run and a table nobody here has drawn.