Two people, four years apart, one theorem

The central theorem of impartial game theory was proved twice, by two people who had not heard of each other, four years apart.

Roland Sprague published in 1935, in Japan, in the Tôhoku Mathematical Journal. Patrick Michael Grundy published in 1939, in England, in the Proceedings of the Cambridge Philosophical Society. Neither cites the other. Neither knew.

The usual reading of a simultaneous discovery is that the time was ripe. This one has a sharper explanation available, and it is checkable: there was nothing else to find.

What the theorem says #

Every impartial position — one where both players have exactly the same moves available — behaves in every respect like a single Nim heap of some size. That size is the position’s Grundy value, and it is computed by one rule:

$$g(P) = \operatorname{mex}\{\, g(Q) : Q \text{ an option of } P \,\}$$

where mex is the minimum excluded value: the least non-negative integer not in the set.

“Behaves like a Nim heap in every respect” is doing a great deal of work in that sentence, and it is worth unpacking, because it is much stronger than “has the same outcome”.

Equivalent does not mean has the same winner. It means substitutable: the position may be exchanged for its Nim heap inside any sum whatever, alongside any other games, without changing any outcome anywhere. The theorem’s own essay plays that claim out rather than restating it — every heap of the subtraction game taking one, three or four counters against every Nim heap up to twelve, a hundred and sixty-nine sums, each decided by a search that has never heard of a Grundy value, and every verdict the one the nim-sum predicts.

Three requirements, and what survives them #

Suppose the task is to attach a number to every impartial position, with the number computed from the numbers of the options. Three things are wanted.

One. A position with no moves gets 0. It has to: the empty set has mex 0, and any rule disagreeing here is disagreeing about a game with nothing in it.

Two. The number is 0 exactly when the position is a loss for the player to move. This is the point of the number. A value that does not decide the outcome is decorative.

Three. Values add by nim-addition across a disjunctive sum. Two positions side by side, each a game, and the value of the pair is the exclusive-or of the two values.

The third requirement is not obvious and is the whole theorem. But the second alone is already close to fatal for the alternatives, and it is the one the figure above tests, because it is the requirement anybody would write down first.

Five things it could have been #

The candidates in the hero figure are not straw men. Each is the first or second thing a person actually reaches for.

The number of options. A position with no moves gets 0, which satisfies requirement one immediately, and “more moves is better” is the intuition every board-game player has. It fails at the third heap of the subtraction game: a heap of 2 has one option and gets value 1, and a heap of 2 is a loss for whoever moves.

One more than the smallest option. A refinement — it grows with the game and bottoms out correctly. Same failure, same heap.

One more than the largest option. The height of the position, which is the natural thing to want if the number is meant to measure how much game is left. Also fails at heap 2.

The nim-sum of the options. This one is interesting because it is almost right, and it is wrong in a way that is instructive: nim-addition is exactly the correct operation for combining separate games, and it is exactly the wrong operation for combining the options of one game. It fails at heap 1.

The parity of the number of options. Whoever moves last is a parity question, so a parity answer ought to be close. It is not.

The mex survives, and it survives because of a property the others lack. The mex is the least value the position is not forced to avoid. Every option’s value is excluded — because a position and its option must not be equal, or a player could move without changing anything — and the mex takes the smallest number that survives the exclusions. Any rule that skips a smaller available number is claiming an equivalence the game does not support; any rule that lands on an excluded number is claiming a move changes nothing.

That is not a proof of uniqueness and is not offered as one. It is an explanation of why two people looking hard at the same requirement arrived at the same place.

The three requirements do not quite pin it down #

The section above says the mex survives the requirements and the alternatives do not, and that is true. It stops short of saying the requirements force the mex, and the gap is worth opening, because what sits in it is the reason the numeral is an index rather than a size.

Suppose $f$ assigns a non-negative integer to every impartial position and satisfies the three demands. Requirement three makes $f$ nim-additive, so from $P + \operatorname{Nim}(g(P))$ being a second-player win — which is the cancellation the theorem proves — requirement two gives $f(P) = f(\operatorname{Nim}(g(P)))$. Everything about $f$ is therefore decided by what it does to Nim heaps.

Write $\varphi(n) = f(\operatorname{Nim} n)$. The same two requirements make $\varphi$ additive, $\varphi(m \oplus n) = \varphi(m) \oplus \varphi(n)$, and injective, since a heap sent to nought would be a first-player win with value nought. A nimber is a string of binary digits added without carrying, so an additive injective map on nimbers is exactly an invertible linear substitution on those digits — and there are a great many of them.

So the requirements determine the value up to a relabelling of the nimbers and no further. Swap the two lowest bits and a Nim heap of one is worth 2 and a heap of two is worth 1; every sum still comes out right, every second-player win still gets nought, and nothing in requirements one to three can tell the difference. Shift every bit up instead and no position is worth 1 at all.

That is a claim about maps rather than about games, so it can be run on a game and watched not failing.

What the mex adds, and what neither requirement asks for, is that a Nim heap of $n$ be worth $n$. That is a normalisation rather than a theorem — a choice of which of the relabellings to call the value, made so that the answer for Nim reads back as Nim.

Which is the precise sense in which two people found the same thing. They found the same structure, forced; the shared numeral is a convention they also both happened to make, because it is the one that makes the theorem’s own example come out unchanged.

Why requirement three is the one that is hard to have #

Requirement two — value zero exactly when the mover loses — kills the alternatives, and it is not the requirement that makes the theorem remarkable. Requirement three is.

To see why, notice how much it is asking. It says that a game made of several independent parts has a value obtained by an operation on the parts’ values, and that the operation is the same one every time. Nothing about the definition of a game suggests this should be possible. Most quantities attached to a compound object do not compose: the outcome class does not — two first-player wins can add to a first-player win or to a second-player win — and neither does the temperature, and neither does the length.

Most quantities attached to a compound object simply do not compose. Two first-player wins can add to a first-player win or to a second-player win, so the outcome class settles nothing about a sum; the same is true of the temperature and of the length. A requirement of that shape is not a formality to be waved through.

So it is worth putting to the six candidates, and the single-heap test never does, because five of them are dead before it comes up. Run each rule a second time on positions of two heaps — the same recursion over the same options, with the options of a pair being a move in one heap or the other — and compare its answer there with the exclusive or of its answers on the two heaps alone.

So neither requirement singles the mex out on its own. Requirement two kills the counting rules and leaves the nim-sum and the parity standing on requirement three; requirement three leaves the counting rules standing and kills the other two on requirement two. The mex is what survives the pair, and the striking thing is still what it always was: a rule arrived at by asking for outcomes turns out to satisfy a demand about sums that nothing in its definition mentions.

That is worth stating plainly because it is what a good definition looks like from the inside: pinned down by one demand, and then unreasonably obliging about a second.

What Grundy added that Sprague did not, and the reverse #

The two papers are not identical, and the differences are informative about what each was trying to do.

Sprague’s is about games: he takes the disjunctive sum seriously as the object of study and proves the equivalence to Nim heaps as a structural result. Grundy’s is about graphs: his formulation is in terms of a function on a directed graph, defined by the mex condition, and the game reading is one application of it.

Grundy’s version is the one that generalised, and the reason is that it is stated about the shape rather than about the subject. What Grundy defines is now called the Grundy function of a directed acyclic graph, and it turns up in places with no game anywhere near them.

Sprague’s version is the one that was needed, though, because the game reading is what makes the sum theorem meaningful. A labelling of a graph has no reason to be interesting; a value that survives addition does.

The surprise: the theorem is a statement about substitution #

Here is the part that is routinely under-stated, and it is the reason the theorem is powerful rather than merely tidy.

The Grundy value does not summarise a position. It replaces it.

Take any impartial position with value 5. Anywhere it appears, in any sum, alongside any other games, it may be swapped for a Nim heap of five counters and no outcome anywhere changes. Not the winner of the sum, not the set of winning moves in the other components, nothing.

A sum with several components is therefore read one component at a time, and that is the entire practical content of the result.

This is what makes the theorem a reduction rather than a solution. Bouton solved Nim. Sprague and Grundy solved every impartial game at once, conditional on being able to compute the values — and the conditional is where the modern subject lives, because computing them is often exactly as hard as playing.

The proof, in the shape it is actually used #

The theorem is proved by showing that a position and its Nim heap cancel — that $P + \text{Nim}(g(P))$ is a loss for whoever moves — which is the standard way of showing two games are equal on this site and everywhere else.

The strategy that wins that sum is worth describing because it is the argument’s whole content and takes three lines. Whoever is not to move maintains one invariant: the two components’ values are equal after each of their own moves. If the opponent changes one component’s value, restore equality in the other; if the opponent moves within a component without changing its value — which is possible, since the mex only excludes option values, it does not forbid an option from having some other value — then answer inside the same component to change it back.

The argument needs exactly two facts about the mex and no others. Every value below it is present among the options, so whatever reduction the opponent asks for in the heap is available in the game. The mex itself is absent from the options, so the opponent cannot move to a position of equal value and force a repetition. Both come straight from the definition, and neither is available from any of the five alternatives — which is the second, independent reason the mex is not a lucky choice.

Where the model stops, and it stops abruptly #

The theorem’s hypothesis is one word: impartial. Both players must have the same moves from every position.

Remove it and the theorem is not weakened, it is destroyed. A partizan position does not have a Grundy value that is merely harder to compute; it has none, and there is no number that behaves as one.

Where the impartial theory stops runs the comparison that shows it: three partizan positions against every nimber, no cell reading “=”, and most cells reading confused — which is worse than inequality, because a position confused with a nimber is neither above nor below it and no ordering could rescue the substitution either.

That collapse is the subject of that essay and it is why Conway’s theory exists. The interesting historical point is the length of the gap: Sprague and Grundy are 1935 and 1939, and the partizan theory is the early 1970s. Thirty-odd years in which the answer for half the subject was complete and the other half had nothing.

What the picture cannot show #

The strips and tables in this essay all show values as numbers, and that is a small lie of omission that matters when the sum theorem is used.

A Grundy value is a nimber, not an integer. It is written 5 here for brevity and ∗5 elsewhere on this site, and the two behave completely differently: integers add by carrying and nimbers add by exclusive-or, so 3 and 5 make 8 as integers and ∗6 as nimbers. Every figure showing a row of small numbers invites the wrong arithmetic, and no arrangement of the figure fixes it.

The consequence is that a value of 5 is not “bigger” than a value of 3 in any useful sense. Nimbers are not ordered — each is confused with every other — and the numeral is an index rather than a size.

Who found it, and what happened next #

Sprague was a number theorist. Grundy was a statistician who died in 1959, at forty-one, and whose name is on this theorem and on very little else.

Sprague’s 1935 paper was followed by a second in 1937 extending the treatment, so he did return to it; Grundy’s was written while he was a student and he did not build on it either. The theorem now carrying both names carried neither for decades — it circulated as folklore among people who worked on Nim-like puzzles, and was rediscovered a third time in the 1950s by people who then found the earlier papers.

Neither result attracted much attention at the time. The theorem’s fame is largely retrospective, dating from Winning Ways and Conway’s On Numbers and Games in the 1970s, which put it in a frame where its limitations were as visible as its strength — impartial games are one class, and the general theory is bigger.

What is worth taking from the independence is not that the time was ripe but that the requirement was tight. Two people were asked, in effect, the same constrained question, and there was one answer available. That is a fact about the mathematics rather than about the decade, and it is checkable in the way the hero figure checks it: by enumerating what else the answer might have been and watching each candidate fail. The decade explanation, by contrast, is not checkable at all, which is a reason to prefer the other one when both are available.

Independent discovery, and what it is worth as evidence #

It is tempting to treat two independent proofs as confirmation, and it is worth being careful about what they confirm.

They do not confirm that the theorem is true; a proof does that, and one is enough. What they are evidence about is that the theorem is findable — that the path to it is short from more than one starting point, and that the requirements leading to it are natural enough to be arrived at twice.

That is a claim about the shape of the subject rather than about the result, and this site has a way of testing claims of that shape: enumerate the alternatives and see how many survive. The answer here is one of six, and the five that die do so at small heaps, within a few values of the start.

How small is a measurement rather than an impression, and it is a measurement over a population rather than over the two games this essay happens to draw.

A heap of sixteen is a bad afternoon and a heap of four is a first attempt. So a person working by hand on a game of this kind runs into the failure almost immediately, and is pushed toward the mex by the same pressure from whichever direction they came.

Compare the case where independence would have been surprising: Wythoff’s cold positions involve the golden ratio, which nothing in the rules of the game suggests, and nobody found those twice.

A footnote on the name #

The theorem is called Sprague–Grundy with an en dash, which is the punctuation for two people, rather than Sprague-Grundy with a hyphen, which would be one person with a double-barrelled name. This site’s concept index carries the distinction deliberately: the label for the slug is set by hand for exactly this reason.

It is a small thing and it is the kind of small thing this field is about. The punctuation records that the result was found twice.

Where the ladder goes next #

This anchor’s earlier rungs establish the theorem and its use; this one asks why it took the shape it did. The rung after is where it stops, which is the boundary that made a second, larger theory necessary — and which is also where the number gives way to a value that can say how much is at stake rather than only who wins.