# Conway’s “Nimbers”

While hunting about for some material on finite fields, I came across Conway’s “Nim Field”, or the field of “nimbers”, which was entirely new to me. Conway is well known for the extraordinary inventiveness and the sheer enthusiastic wit of his mathematics, and nimbers are a brilliant example of that. The definition is given in his work On Numbers and Games, in which nimbers are shown to be important for combinatorial game theory. My interest is not in their use, but in the wonderful delight of their construction. A nice account is given here.

The elements of the nim field include the non-negative integers .

Addition is exclusive-or of the bits of the numbers. Alternatively, the sum of and is zero if and otherwise. For example, as can be seen from their bits:

.

This means that in this field, .

Multiplication is done by considering Fermat powers; numbers of the form . The product is defined to be:

if

if .

So for example, .

To perform multiplication, write up a table of small values, and use that table to extend to higher values. Consider all numbers up to the first Fermat power 2. From the definition, the following table can be produced:

This can be continued out to the next Fermat power 4. Using the above table:

, as 2 and 4 are distinct Fermat powers.

.

The above table can now be extended:

Using the same approach, a multiplication table up to the next Fermat power 16 can be constructed (which we’ll display in ASCII to save space):

 x | 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
---------------------------------------------------
0 | 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
1 | 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
2 | 0  2  3  1  8 10 11  9 12 14 15 13  4  6  7  5
3 | 0  3  1  2 12 15 13 14  4  7  5  6  8 11  9 10
4 | 0  4  8 12  6  2 14 10 11 15  3  7 13  9  5  1
5 | 0  5 10 15  2  7  8 13  3  6  9 12  1  4 11 14
6 | 0  6 11 13 14  8  5  3  7  1 12 10  9 15  2  4
7 | 0  7  9 14 10 13  3  4 15  8  6  1  5  2 12 11
8 | 0  8 12  4 11  3  7 15 13  5  1  9  6 14 10  2
9 | 0  9 14  7 15  6  1  8  5 12 11  2 10  3  4 13
10 | 0 10 15  5  3  9 12  6  1 11 14  4  2  8 13  7
11 | 0 11 13  6  7 12 10  1  9  2  4 15 14  5  3  8
12 | 0 12  4  8 13  1  9  5  6 10  2 14 11  7 15  3
13 | 0 13  6 11  9  4 15  2 14  3  8  5  7 10  1 12
14 | 0 14  7  9  5 11  2 12 10  4 13  3 15  1  8  6
15 | 0 15  5 10  1 14  4 11  2 13  7  8  3 12  6  9

For example:

using the previous table. Continuing:

.

And this table can now be used to compute higher products.

For another example, consider . Using the largest Fermat power less than 200, which is 16, write this as

From the large table above:

The quite remarkable thing is that the non-negative integers with these two operations forms a field! By definition of addition, it is of characteristic two.

Alternative definitions of the operations can be defined in terms of ordinals and the mex function, where given a set of ordinals,

is defined to be the smallest ordinal not in . Then addition can be defined recursively as

where we use the notation to indicate that all additions are “nim” additions and not arithmetic addition.

Multiplication is also defined recursively as

.

where all operations on the right are “nim” operations.

These two definitions mean that the definition can be extended to include the entire class of ordinals, and not just the finite ordinals – the integers. In fact the integers form a proper subfield of the nim-field, as do all finite subsets of the form

for each .

Using the mex definitions means that inversion can be algorithmically defined:

where is the smallest set of ordinals satisfying

1. if and then where all operations are understood to be “nim” operations.

Nimbers in Sage

Happily, the nim-field has been implemented in Sage, the python file can be downloaded from here.

Here’s how it can be used:

sage: load nimbers.py
sage: from nimbers import NimberField
sage: N = NimberField()
sage: N(100)*N(200)
62
sage: 1/N(100)
57


## 4 thoughts on “Conway’s “Nimbers””

1. I maintain listening to your news speak about getting free on the web grant applications so I’ve been
looking around for the most effective site to obtain one.