No number bounds it

A game ends when every line of play reaches a position with no moves, and the way to prove that is to exhibit a termination measure: a quantity every legal move strictly lowers, in an order with no infinite descending chain. Which games end at which level sorted this collection’s games by the order their measures live in. Nim, Cutcake and Toads and Frogs have measures in the natural numbers. The hydra needs the ordinals below $\varepsilon_0$, and nothing smaller will do. Sylver Coinage went in the middle, on the strength of a well-quasi-ordering argument, and the placement came with a warning attached: an argument of that kind is a ceiling, not a floor. A cleverer measure could put the game lower — into the naturals, even — and the essay named the obvious candidate. Pair the count of numbers still nameable with the number of distinct prime factors the named numbers share, which falls to one exactly when the gaps become finite, and check whether the combination descends.

It does not. But the question has a complete answer, and the answer is more exact than a level. The game tree of Sylver Coinage is $\omega^2$ tall. No measure into anything shorter exists, the candidate fails for a reason that can be read off a single move, and a two-line repair of it produces a measure that is not merely correct but tight: it is the height of every position.

The rules, and the convention the count depends on #

Two players name positive integers in turn. A number may not be named if it is a sum of numbers already named, repeats allowed. The numbers reachable as such sums form a numerical semigroup once the named numbers have no common factor, and the numbers still nameable are its gaps; the game that is a number system sets all of that out. Whoever names 1 loses.

That last clause needs a convention, and every count below depends on it. Here the game is played as normal play on the gaps above 1: a player whose only nameable number is 1 has lost, and naming 1 is not counted as a move. So a play is a sequence of legal namings of numbers other than 1, and the length of a position is the longest play available from it. With 2 and 3 named, nothing but 1 is left, and the length is nought.

The height of a position generalises length to positions whose plays have no longest member. It is defined by the recursion every value in this collection uses: a position with no moves has height nought, and any other has as its height the least ordinal larger than the heights of all its options. When the lengths from a position are bounded, the height is the largest of them. When they are not, the height is infinite, and the ordinals say how.

The height is the thing a termination measure is trying to be. Every move lowers the height, by construction, so the height is itself a measure; and any measure at all must assign each position something at least as large as its height, because a descending sequence of measure values can be followed one move at a time. So the smallest order a measure can live in is fixed by the tallest position, and asking for a game’s level is asking for its height.

Every length is available from {2} #

Start with the case that settles the naturals, because it takes two moves.

Suppose the first move is 2. Every even number is now a sum of twos, so the second player must name an odd number, and any odd number above 1 is legal. Naming 2k + 1 makes every larger odd number reachable too — it is 2k + 1 plus some twos — so what remains nameable is exactly the odd numbers below it: 1, 3, 5, up to 2k − 1. There are k of them.

The figure’s third column is searched rather than argued, and the search agrees with a simple observation: a player who wants the game to last can always name the largest remaining gap, which removes that gap and no other, so k − 1 more moves are available before only 1 is left. The play from {2} can therefore last one move, or two, or ten, or a thousand, at the discretion of whoever makes the second move.

That is the end of any measure in the natural numbers. A measure m would give {2} some value m({2}) = N, every move would lower it by at least one, and so no play from {2} could last more than N moves. The second player names 2N + 3 and the play lasts N + 1. There is no N.

It is worth being clear about what kind of fact this is. It is not that Sylver Coinage is long. Nim with a googol counters is longer than any Sylver Coinage game anybody will play, and its measure is a natural number because the googol is known before the first move. The obstruction here is that the length is decided during the game, by a player, from a position where nothing about it is yet fixed — which is exactly the property two ways to end with no bound found in Sylver Coinage and not in Nim, stated now as a proof that no bound exists rather than as the absence of one.

So the game is not at the bottom of the scale. The question left is where in the middle it sits.

The candidate rises on {4} + 6 #

The proposed measure had two parts. While the named numbers share a factor, infinitely many numbers remain nameable and the gap count is useless, so it needs a second quantity that decreases during that stretch: the number of distinct primes dividing every named number. That is one prime for {4}, and two for {6}, and it reaches nought exactly when the gaps become finite.

The natural way to combine the two is lexicographically — compare the prime counts first, and the gap counts only when the prime counts are equal — which is the same trick that makes a pair of natural numbers well-ordered. For the gap count to mean anything while a factor is shared, it has to be taken in the scaled game: with gcd d, divide everything named by d and count the gaps of the semigroup that results. That count is finite, because the scaled numbers have no common factor.

The first row is the whole failure in one move. With 4 named, the gcd is 4, which has one prime; the scaled semigroup is generated by 1 and has no gaps. The pair is (1, 0). Now name 6. The gcd drops to 2 — still one prime — and the scaled semigroup is generated by 2 and 3, with one gap. The pair is (1, 1). It went up.

The rest of the table is the same event at different scales. From {16}, naming 18 drops the gcd from 16 to 2, which is one prime before and after, and the scaled semigroup generated by 8 and 9 has 28 gaps; the pair rises by 28 on one move. From {8, 12}, naming 10 lowers the gcd from 4 to 2 and the gaps from one to four. And on ten moves the pair stays exactly level — {4} + 2, {9} + 3, {12} + 6 — because the gcd fell to a divisor with the same primes and the scaled semigroup is everything in both positions.

What every one of the 54 has in common is stated in the figure’s second footer and checked on all of them: the gcd fell to a proper divisor with the same set of primes. From 4 to 2, 8 to 4, 9 to 3, 12 to 6. The move made real progress — the numbers that could still be named went from the odd ones and the twos-but-not-fours to only the odd ones — and the measure could not register it, because it counts each prime once, and a prime counted once cannot record that it has lost a copy of itself.

One level for every prime factor #

The repair is in that diagnosis. Count the prime factors of the gcd with their repeats — two for 4, three for 8, two for 9, four for 16 — and write Ω(d) for the count. The candidate becomes the pair

(Ω(gcd), gaps of the semigroup scaled by the gcd),

compared lexicographically, and it falls on every move by an argument two lines long.

A move either names a multiple of the current gcd d or it does not. If it does, the gcd stays d, and the move named d times a gap of the scaled semigroup — it has to have been a gap, or the number was not nameable — so the scaled semigroup has at least one gap fewer and the second coordinate falls while the first stands still. If it does not, the new gcd is a common divisor of d and the new number, so it divides d and is not d: a proper divisor, which has at least one prime factor fewer, counted with repeats. The first coordinate falls and the second can do whatever it likes.

The chain figure is the argument drawn as a path. The gcd can fall only to a proper divisor, so it can fall at most as many times as a chain of divisors can be long, and the longest chain from d drops one prime at a time: Ω(d) steps. The distinct-prime count agrees with Ω only on a gcd with no repeated prime. Thirty, whose primes are 2, 3 and 5, is such a number, and on it the two counts walk down together; on 16 the distinct-prime count is one at every stage and sees none of the four steps.

The check is worth having for the reason which games end at which level gave for its own: a measure stated wrongly looks like a measure until somebody tries every move. The candidate above was exactly such a quantity. Plausible, falling on 42,465 of 42,519 moves, and wrong.

The pair is the height #

So Sylver Coinage has a measure into pairs of natural numbers ordered lexicographically, which is the ordinal $\omega^2$: the pairs (0, n) come first, then (1, n), then (2, n), each block a copy of the naturals and the blocks themselves indexed by the naturals. That puts a ceiling of $\omega^2$ on the game’s height. The claim of this essay’s title is that the ceiling is attained, and it is attained in the strongest sense available: the measure equals the height of every position.

Take the finite part first. When the gcd is 1, the pair is (0, g), where g is the number of gaps, and the height is the longest play. The two agree, less one for the gap that is 1 itself.

The right-hand column is the reason. The largest gap F plus any positive element of the semigroup is larger than F, so it was reachable already, and naming F makes nothing new reachable except F itself. A player trying to prolong the game can always spend exactly one gap; a player trying to shorten it can spend several at once. So the longest play from a position with gcd 1 is its gap count less the gap at 1, and the height of such a position is the finite number the pair’s second coordinate records.

Now a position with gcd d larger than 1, and scaled gaps g. Its options are of two kinds. Naming a multiple of d stays at the same level with fewer scaled gaps. Naming anything else falls to a divisor of d — and here is the point — it can fall to a position as tall as the mover likes below that level. Divide one prime p out of d, and name (d/p) times some large number y coprime to p. The new gcd is d/p, and the scaled semigroup now contains p and y, whose gaps number at least (p − 1)(y − 1)/2 by Sylvester’s count; with y large that is as many gaps as anybody wants. The play from {2} in the second figure is the smallest instance: d = 2, p = 2, and the options reach every finite height.

So by induction on the level, a position with gcd d has height exactly

ω · Ω(d) + g,

where g is the gaps of the scaled semigroup, less one when d is 1. The options that drop a level reach every height below ω · Ω(d) and none at or above it; the options that stay at the level reach ω · Ω(d) + (g − 1) and nothing higher. The least ordinal above all of those is the formula. With 4 and 10 named, for instance, the gcd is 2 and the scaled semigroup is generated by 2 and 5, with gaps 1 and 3; the height is ω + 2. The even numbers still nameable are 2 and 6, the longest way to stay at gcd 2 is to name 6 and then 2, and after that every move is odd and the game is finite with no bound on how long.

The empty position is the top. Its options are {n} for every n from 2 upward, of height ω · Ω(n), and Ω(n) is unbounded — Ω(2^k) is k. The least ordinal above ω · k for every k is $\omega^2$. The game is $\omega^2$ tall, the measure lives in $\omega^2$, and no measure into any shorter order exists, because the empty position would need a value above every ω · k.

What each opening leaves #

The formula reads most strikingly on the first move, because the first move chooses the level and nothing else.

An opening n leaves a position of height ω · Ω(n): the primes at ω, 4 and 6 and 9 and 10 at ω·2, 8 and 12 and 18 and 20 at ω·3, 16 and 24 at ω·4. The primes are exactly the lowest openings, and every prime from 5 up is a proved winning opening — Hutchings’s theorem, whose proof is a strategy-stealing argument that names no reply. And 16 is both the tallest opening below 25 and the smallest opening nobody has solved.

That second coincidence is worth stating and then setting down. The known losing openings — 1, 2, 3, 4, 6, 8, 9 and 12 — are the small numbers of the form $2^a 3^b$, and such numbers have more prime factors than their size would suggest, so they sit high on this scale for their magnitude. But 2 and 3 are primes at the bottom level and lose, and 24 is as tall as 16 and says nothing. The height of an opening measures how many times the players can reset the length of the game, which is a fact about the tree’s shape; the outcome is a fact about which branches win. Nothing in the formula links them, and it would be a mistake to read the colours as a map of who wins.

Where the proof strength sits #

The level which games end at which level could exhibit for Sylver Coinage was a well-quasi-ordering argument, Dickson’s lemma, and it said so honestly: an upper bound. The exact answer is lower than the general lemma needs and higher than the naturals, and it is worth placing precisely.

A measure into $\omega^2$ is a double induction: an induction on one natural number, inside which each step is itself an induction on another. It is the pattern that proves the Ackermann function is total, and it is well inside ordinary arithmetic — Peano arithmetic proves each ordinal below $\varepsilon_0$ well-founded, one at a time, and $\omega^2$ is very far below that. So Sylver Coinage sits at a definite, low place in the middle of the scale: strictly above Nim, which needs one induction, and immeasurably below the hydra, which needs all of them.

The middle of the scale, in other words, was not one level but a whole region, and Sylver Coinage is at its second floor. The hydra’s $\varepsilon_0$ is the limit of ω, $\omega^{\omega}$, $\omega^{\omega^{\omega}}$ and on up, and $\omega^2$ is the second step of that climb.

There is one more thing the formula says that the placement by Dickson’s lemma could not. The measure is computable from the position in a moment: a gcd, a factorisation, and a gap count of a semigroup with no common factor. So the conditional promise the earlier essay described — no bound now, a bound once the numbers are coprime — has a sharper form. Before the numbers are coprime, a solver cannot bound the length, but it can say exactly how many times the players can still choose it: Ω(d) times. That is how many more moves can each reset the remaining length to an arbitrary finite number, and after the last of them the gap count is a hard bound.

What the height cannot show #

Four things the height is not, each of which it would be easy to read into the pictures above.

It is not how long a game takes. The height of {2} is ω and every play from it is finite; ω is the statement that there is no longest one, not that some play is infinite. No Sylver Coinage game is infinite. The empty position’s $\omega^2$ says the same thing twice over: the first move chooses how many resets remain, and each reset chooses a length.

It is not who wins. A position of height nought is lost for the player to move and a position of height one is won, but past that the height is a fact about the longest line and the outcome a fact about the best one, and the two part company immediately. {2, 5}, of height one, and {2, 7}, of height two, are both won for the player to move — the second by naming 3, which leaves only 1 and ends the game one move short of its longest play — while {4, 5, 11}, of height four, is lost.

The sweep is bounded and the argument is not. The 42,519 moves checked are those among numbers up to 20; the two-line argument covers every move of every position, and the checking is there because an argument stated slightly wrongly is common and a measure checked slightly wrongly is how the candidate survived long enough to be proposed.

And the height is a property of the game with 1 excluded. Under the other reading of the rule — naming 1 is a move, the last one — every finite part rises by one and nothing else changes; the $\omega^2$ does not move.

Still open: whether the finite part decides anything #

The formula has a finite part and an infinite part, and one of them has been seen before. When the gcd is 1, the height is the gap count less one, and a parity with a first exception found that the parity of the gap count very nearly decides who wins: the first three rows with an even number of gaps hold no position lost for the player to move, and the odd rows hold both kinds. The height explains why that parity is the natural first guess. If every play ran to the longest length the tree allows, the winner would be read off the parity of the height, and the census would be exact. It is not exact because a player can shorten the game — name a number that closes several gaps at once — and every move closes the largest gap is the class of positions where every move does exactly that, which is why the parity survives there.

That suggests the next measurement, at the first infinite level. A position with a prime gcd has height ω + g. Its moves either stay at the level, spending one scaled gap or several, or drop to the finite game with a length the mover chooses. Whether the parity of g nearly decides those positions as the gap parity nearly decides the finite ones — or whether the freedom to choose a length below erases the pattern entirely — is a question the formula makes askable, and one a search over positions with bounded moves could begin to answer, with the caution that at a level with infinitely many moves the bound is where the answer could hide. It ends, and nothing says when is the hydra’s version of the same distance between knowing a game ends and knowing how, and the condition the recursion rests on is why any of it matters: every value in this collection is computed by a recursion that stops because some measure is descending, and for Sylver Coinage that measure can now be written down.