The nimbers multiply

Adding nimbers is exclusive-or, and the reason is a theorem: the value of two impartial games side by side is the exclusive-or of their values. That is Sprague and Grundy’s result, and it is what makes a Grundy value worth computing.

Multiplying them is stranger, less well known, and is where the game theory turned into algebra.

$$a \otimes b = \operatorname{mex}\{\, (a' \otimes b) \oplus (a \otimes b') \oplus (a' \otimes b') : a' < a,\ b' < b \,\}$$

That is the same manoeuvre as the mex rule itself — take the least value the answer is not forced to avoid — applied to a product rather than to a move.

What the definition is saying #

The exclusion set looks arbitrary and is not. Read it as three requirements that a product must satisfy, combined.

If $a' < a$ and $b' < b$, then in a well-behaved multiplication $(a - a') \otimes (b - b')$ is non-zero — the product of two non-zero things. Expanding that, and remembering that subtraction and addition are both exclusive-or here:

$$(a \otimes b) \oplus (a' \otimes b) \oplus (a \otimes b') \oplus (a' \otimes b') \ne 0$$

which rearranges to say that $a \otimes b$ must not equal $(a' \otimes b) \oplus (a \otimes b') \oplus (a' \otimes b')$.

So each pair $(a', b')$ excludes exactly one candidate value, and the definition takes the least value not excluded. The multiplication is the smallest one consistent with having no zero divisors, which is a much less arbitrary description than the formula suggests.

The results, checked #

Conway’s theorem is that the nimbers below $2^{2^k}$ form a field for every $k$ — so below 2, below 4, below 16, below 256, and so on up.

Every axiom is checked here over the table rather than cited. Closure, commutativity, associativity, distributivity over exclusive-or, and an inverse for every non-zero element: 16 × 16 for the first two, 16³ for the associativity and distributivity checks, and a search for an inverse of each of the fifteen non-zero values.

The inverses are worth reading, because they are not what anybody would guess: $2^{-1} = 3$, $3^{-1} = 2$, $4^{-1} = 15$, $5^{-1} = 12$, $6^{-1} = 9$, $7^{-1} = 11$, $8^{-1} = 10$, $13^{-1} = 14$. Nothing about the binary representations predicts them, and the pairing is not by any visible rule — 2 and 3 swap, 13 and 14 swap, and 4 goes all the way to 15.

And the check can fail. The nimbers below eight are not closed under the same multiplication — 8 is not of the form $2^{2^k}$ — so a figure drawn at that size would show products falling outside the table. The generator reports this, which is what stops the field claim from being a size chosen to make the claim true.

The operation the multiplication distributes over is the nim-sum — exclusive-or, which comes out of the games directly, because it is what putting two positions side by side does to their values. The multiplication does not come from anywhere in the games, and that asymmetry is the subject of a later section.

Why the Fermat powers, and not the other sizes #

The theorem’s shape — a field below $2^{2^k}$ and nowhere in between — is stated above and is worth an argument, because a reader meeting it will assume the sizes are an artefact of the proof rather than a fact about the multiplication.

The closure failure is the tell, and it can be checked by hand at the smallest place it happens. $2 \otimes 4$ is $8$. Both factors are below eight; the product is not. So the nimbers below eight are not closed, and no amount of care with the other axioms rescues them.

The multiplication insists on building outward at particular moments. Below 2 the only element is $1$ and the field is trivial. Below 4 the elements are $\{0,1,2,3\}$ and everything stays inside. Extend to $\{0,\ldots,7\}$ and the products immediately leave; extend all the way to 16 and they stay in again. The stable sizes are $2, 4, 16, 256, 65536, \ldots$ — squarings of the previous one — and nothing between two stable sizes is stable.

That is the same pattern finite fields of characteristic two have anywhere: a field of order $2^n$ contains one of order $2^m$ exactly when $m$ divides $n$, so the chain of fields each containing the last has orders that repeatedly square. The nimbers are not being awkward; they are being a tower of finite fields, and the tower has the shape towers of that kind always have.

The nesting is visible in the one table, because each stable size is a corner of the next.

Which is why the refusal is the right check #

That makes the generator’s refusal at eight more than a safety rail. It is the one place a reader can watch the theorem being about the sizes rather than about the arithmetic.

A generator that drew the eight-element table would have to do one of two things: report products lying outside its own range, or quietly enlarge the range to fit them — and the second is the dangerous one, because a table silently drawn at sixteen with a caption saying eight is a picture of a true claim about the wrong object.

The refusal is what makes “below sixteen” a measurement rather than a choice. Sixteen is not the largest size a laptop can check; it is the largest of the stable sizes small enough to print, and the generator will confirm the axioms at 4 and at 16 and refuse at every size between them. A reader who suspects the essay of picking a size that flatters the claim can ask for another one and be told no.

Two properties that follow immediately #

Once the field is established, two facts drop out that are worth having, because they are the ones a reader will want to use.

Every element is its own additive inverse. $a \oplus a = 0$, always, which is what characteristic two means. So there is no subtraction distinct from addition, and no signs.

Squaring is not a bijection onto the squares in the usual sense, because in characteristic two the map $a \mapsto a \otimes a$ is a field automorphism — the Frobenius map — and it is therefore a bijection of the whole field. Every element has exactly one square root, which is emphatically not true of the real numbers and is one of the reasons finite fields of characteristic two are pleasant to compute in.

The second is visible in the table, and it is worth looking at rather than taking on trust, because “every element has exactly one square root” is a sentence about the real numbers being false.

There is no figure of the table at eight, and the reason is worth recording: the generator refuses to draw one. It checks the field axioms before drawing and throws when they fail, so asking it for the nimbers below eight produces an error rather than a picture — the nimbers below 8 are not a field — closure under multiplication.

That refusal is the same machinery that makes the tables above worth believing. A generator that would happily draw a non-field with the caption “and every axiom checked” is a generator whose captions mean nothing.

The surprise: the multiplication is not a game operation #

This is the part that is genuinely odd and is usually passed over.

Nim-addition means something about games. $a \oplus b$ is the value of the position consisting of a heap worth $a$ beside a heap worth $b$. The operation is defined by the game and the arithmetic follows.

Nim-multiplication is not defined by one. It comes from an algebraic requirement — no zero divisors, least value consistent — and nothing about a disjunctive sum, or any other way of putting two positions side by side, produces it.

So at this rung the field structure is a fact about the values with no known counterpart among the positions those values came from. That is unusual: almost everything else in this subject earns its place by corresponding to something a player could do.

It does not stay that way. The rung above this one exhibits a construction on positions whose value is exactly $a \otimes b$ — two coin-turning games laid across each other on a grid, with a move turning a rectangle — and the correspondence is checked cell by cell. So the operation defined here for algebraic reasons turns out to be what a two-dimensional turning game computes, and the two derivations share no step.

What survives of the oddity is narrower and still worth having. The multiplication is not a general operation on impartial games: there is no way to take two arbitrary impartial positions and combine them so that their Grundy values multiply. It is a construction available on one family, and the family had to be built for it. Addition needs no such arrangement — any two positions whatever, side by side.

Working one entry out by hand #

The definition is easier to trust after one product has been computed from it, so here is $2 \otimes 2$.

The exclusions come from pairs $(a', b')$ with $a' < 2$ and $b' < 2$, so $a', b' \in \{0, 1\}$. For each, the excluded value is $(a' \otimes 2) \oplus (2 \otimes b') \oplus (a' \otimes b')$.

• $(0,0)$: $0 \oplus 0 \oplus 0 = 0$.
• $(0,1)$: $0 \oplus 2 \oplus 0 = 2$.
• $(1,0)$: $2 \oplus 0 \oplus 0 = 2$.
• $(1,1)$: $2 \oplus 2 \oplus 1 = 1$.

Excluded: $\{0, 1, 2\}$. The least value not excluded is 3, so $2 \otimes 2 = 3$.

The same derivation, drawn on the table it is an entry of, shows where the four exclusions come from — every one of them is a product already in the table, which is what makes the recursion terminate.

A larger entry makes the same point at a size nobody would work by hand. $4 \otimes 4$ has sixteen smaller pairs behind it, which between them exclude 0, 1, 2, 3, 4, 5, 8, 11, 12 and 14 — ten values, with gaps — and the least survivor is 6. The gaps matter: the exclusions are not an initial segment, so the mex is not simply one more than the largest thing ruled out.

That is the entry in the table, and it is worth noting how unlike ordinary squaring it is: $2 \otimes 2 = 3$, and $2 \otimes 3 = 1$, so 2 and 3 are inverses of each other and 2 is not its own square root of anything familiar.

What it is good for #

The multiplication has uses, and they are outside game theory.

The nimbers below $2^{2^k}$ form the field $\mathrm{GF}(2^{2^k})$ — a finite field of characteristic two — and nim-arithmetic is one concrete realisation of those fields with an unusually simple description. Addition is exclusive-or, which is free on any computer, and multiplication has a recursive rule that is fast enough to be practical.

Inside game theory it turns up in Turning Turtles-style coin games and in the analysis of games played on grids, where the value of a position factorises into a product of the values of its coordinates — a genuine game-theoretic use, and a narrow one.

Why the sizes are $2^{2^k}$ and not anything else #

The tower of exponents looks arbitrary and has a clean reason, which is worth stating because it also explains the failure at 8.

The construction has a property: the least value that is not in any smaller field, and that is not a root of anything the smaller field can express, becomes a new element with new behaviour. Each time that happens, the field doubles in exponent — from $2^1$ to $2^2$ to $2^4$ to $2^8$ — and the sizes are $2, 4, 16, 256, 65536, \ldots$

Eight is not on that list. The nimbers below 8 contain 4, which generates elements outside the range, so the set is not closed and the axioms have nothing to hold on.

The figure checks that failure rather than assuming it, and the check is the reason the field claim above means anything: a table drawn at a size chosen because it works, with no acknowledgement that other sizes do not, would be an assertion dressed as a computation.

Where the values themselves come from #

It is worth reconnecting to the games, because after a page of algebra the origin of these numbers is easy to lose.

A nimber is not a symbol somebody chose. ∗5 is the value of a Nim heap of five counters, and equally the value of every impartial position that behaves like one — a row of coins, a green Hackenbush graph, a subtraction game heap. The mex rule computes which.

So the field constructed above is a field whose elements are answers to games. That is the fact that makes it more than a curiosity about finite fields, and it is also the fact that makes the missing game-interpretation of the multiplication conspicuous.

Where the model stops #

The table is computed at one size. Everything asserted here is checked over the nimbers below sixteen, and the general theorem for every $k$ is stated rather than checked — the next size up is 256, whose associativity check is $256^3$ products and whose table would not fit on a page.

And the field is characteristic two, so all the intuitions carried from ordinary arithmetic about signs and ordering are absent. Every element is its own negative, because $a \oplus a = 0$. There is no ordering at all: the nimbers are pairwise confused, so “bigger” is meaningless and the numerals are indices.

What the picture cannot show #

The table is a grid of numbers and the numbers look like sizes. They are not.

∗5 is not larger than ∗3. In the ordering the theory actually has, the two are confused — neither above, below, nor equal — and the only reason 5 is written after 3 is that the mex produced them in that order. Every figure of this kind invites the reader to see a magnitude, and there is none to see.

Why this belongs in the impartial field rather than in a footnote #

There is a case for treating nim-multiplication as an aside — it has no game interpretation, it is used rarely, and the impartial theory is complete without it.

The case against, and the reason it has an essay here, is that it settles what kind of object a Grundy value is.

Before it, a Grundy value is a label: an index into the Nim heaps, which happens to add by exclusive-or because the games do. After it, the values are a field, with a structure that has nothing to do with the games and that the games did not put there.

That is a meaningful change in status. A label that turns out to carry an algebraic structure of its own is evidence that the label was the right one — the same kind of evidence as two people independently reaching the mex, and arriving from an entirely different direction.

Who found it, and when #

Conway, in On Numbers and Games, 1976. The construction extends past the finite nimbers to the ordinals, where the same rules make the ordinals below $\omega^{\omega^\omega}$ into an algebraically closed field of characteristic two — a sentence that is entirely serious and is very far from any game anybody plays.

What the recursion costs #

The definition is recursive in both arguments, and the cost is worth a note because it is not the cost the formula suggests.

Computing $a \otimes b$ from scratch requires every product $a' \otimes b'$ with $a' < a$ and $b' < b$, plus $a' \otimes b$ and $a \otimes b'$ — so a naive implementation is exponential and unusable past single digits.

Memoised, it is quadratic in the size of the table and completely routine: the 16 × 16 table here is built in a few milliseconds, and the axiom checks — which are cubic, since associativity and distributivity quantify over triples — dominate it.

That is the memoisation argument once more, in a setting with no game in it at all. The same manoeuvre that turns an impossible search into a table turns an impossible definition into an implementation, and it is the same manoeuvre for the same reason: the recursion revisits its own subproblems.

A closing comparison #

Nim-addition and nim-multiplication make an instructive pair, and the difference between them is the reason only one of them is famous.

Addition was discovered. It was found in the games — Bouton’s criterion is an addition rule before anybody called it one — and its properties were then noticed.

Multiplication was constructed. It was defined by writing down what a well-behaved product would have to avoid and taking the least value consistent with that, and nothing in any game suggested it.

Both are correct, both are useful, and only the first is about games. That is a fair summary of where the impartial theory sits: an object that came out of play, which turned out to have a life of its own once somebody asked algebraic questions of it.

What is checked here, and what is not #

Stated plainly, so the claims on this page can be separated by strength.

Checked, exhaustively, over the range drawn: the multiplication table for the nimbers below 16; commutativity and closure over all 256 pairs; associativity and distributivity over all 4,096 triples; an inverse for each of the fifteen non-zero elements; and the failure of closure below 8.

Stated on the theory’s authority: that the same holds at every $2^{2^k}$; that the construction extends to the ordinals; that squaring is an automorphism.

The division matters because the second list contains everything that makes the result sound impressive, and the first contains everything this site is answerable for.

Where the multiplication computes something #

The field structure above is established on its own terms, and a reader is entitled to ask what it is for.

Where the ladder goes next #

The rungs below this one are Nim itself and the theorem that makes every impartial game a Nim heap. This rung is the algebra the values turn out to carry on their own account. The direction onward is the boundary: where one number per position stops being enough, which is where this entire structure runs out.