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 \mathbb{Z}^+={0,1,2,3,\ldots}.

Addition is exclusive-or of the bits of the numbers. Alternatively, the sum of 2^n and 2^m is zero if m=n and 2^m+2^n otherwise. For example, 11+13=6 as can be seen from their bits:

11+13=[1,0,1,1]\oplus[1,1,0,1]=[0,1,1,0]=6.

This means that in this field, n+n=0.

Multiplication is done by considering Fermat powers; numbers of the form 2^{2^n}. The product 2^{2^n}\times 2^{2^m} is defined to be:

2^{2^n}2^{2^m} if m\ne n

3(2^{2^n-1}) if m=n.

So for example, 16\times 16 = 3(2^{4-1})=3(8)=24.

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:

    \[ \begin{array}{c|cc} \times&0&1\\ \hline 0&0&0\\ 1&0&1 \]

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

2.3=2(2+1)=2.2+2=3+2=1

2.4=8, as 2 and 4 are distinct Fermat powers.

3.3=(2+1).(2+1)=2.2+2.1+2.1+1=3+2+2+1=2

3.4=(2+1).4=2.4+4=8+4=12.

The above table can now be extended:

    \[ \begin{array}{c|cccc} \times&0&1&2&3\\ \hline 0&0&0&0&0\\ 1&0&1&2&3\\ 2&0&2&3&1\\ 3&0&3&1&2 \end{array} \]

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:

10.7=(2.4+2)(3+4)=2(4^2)+(2+3.2)4+3.2

=2.6+(2+1)4+1

using the previous table. Continuing:

= 2(4+2)+3.4+1=2^2+2.4+12+1=3+8+12+1=6.

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

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

\(6(16)+4)(12(16)+8)=(6.12)16^2+(6.8+12.4)16+4.8

From the large table above:

\ = 9.24+(7+13)16+11 = 9(16+8)+10.16+11

\ = 9.16+9.8+160+11=144+5+160+11=62.

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 S of ordinals,

\mbox{mex}(S)

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

a+_nb=\mbox{mex}({i+_nb:i<a}\cup{a+_nj:j<b})

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

Multiplication is also defined recursively as

ab=\mbox{mex}({ib+aj+ij:i<a,j<b}).

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

\{i:i< 2^{2^n}\}

for each n.

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

a^{-1}=\mbox{mex}(S)

where S is the smallest set of ordinals satisfying

  1. 0\in S
  2. if 0<i<a and b\in S then [1+(i-a)b]/i \in S 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.
    Thank you for your help!

  2. I simply can’t find the nimbers.py code anywhere on the internet or in the archive. Is there a way you could upload it somewhere?

    (By the way, the 2 posts above are spam.)

Leave a Reply

Your email address will not be published. Required fields are marked *