Skip to content →

Category: games

How to play Nimbers?

Nimbers is a 2-person game, winnable only if you understand the arithmetic of the finite fields $\mathbb{F}_{2^{2^n}} $ associated to Fermat 2-powers.

It is played on a rectangular array (say a portion of a Go-board, for practical purposes) having a finite number of stones at distinct intersections. Here’s a typical position

The players alternate making a move, which is either

  • removing one stone, or
  • moving a stone to a spot on the same row (resp. the same column) strictly to the left (resp. strictly lower), and if there’s already a stone on this spot, both stones are removed, or
  • adding stones to the empty corners of a rectangle having as its top-right hand corner a chosen stone and removing stones at the occupied corners

Here we illustrate two possible moves from the above position, in the first we add two new stones and remove 2 existing stones, in the second we add three new stones and remove only the top right-hand stone.

As always, the last player able to move wins the game!

Note that Nimbers is equivalent to Lenstra’s ‘turning corners’-game (as introduced in his paper Nim-multiplication or mentioned in Winning Ways Chapter 14, page 473).

If all stones are placed on the left-most column (or on the bottom row) one quickly realizes that this game reduces to classical Nim with Nim-heap sizes corresponding to the stones (for example, the left-most stone corresponds to a heap of size 3).

Nim-addition $n \oplus m $ is defined inductively by

$n \oplus m = mex(n’ \oplus m,n \oplus m’) $

where $n’ $ is any element of ${ 0,1,\ldots,n-1 } $ and $m’ $ any element of ${ 0,1,\ldots,m-1 } $ and where ‘mex’ stands for Minimal EXcluded number, that is the smallest natural number which isn’t included in the set. Alternatively, one can compute $n \oplus m $ buy writing $n $ and $m $ in binary and add these binary numbers without carrying-over. It is well known that a winning strategy for Nim tries to shorten one Nim-heap such that the Nim-addition of the heap-sizes equals zero.

This allows us to play Nimber-endgames, that is, when all the stones have been moved to the left-column or the bottom row.

To evaluate general Nimber-positions it is best to add another row and column, the coordinate axes of the array

and so our stones lie at positions (1,3), (4,7), (6,4), (10,3) and (14,8). In this way all legal moves follow the rectangle-rule when we allow rectangles to contain corners on the added coordinate axes. For example, removing a stone is achieved by taking a rectangle with two sides on the added axes, and, moving a stone to the left (or the bottom) is done by taking a rectangle with one side at the x-axes (resp. the y-axes)

However, the added stones on the coordinate axes are considered dead and may be removed from the game. This observation allows us to compute the Grundy number of a stone at position (m,n) to be

$G(m,n)=mex(G(m’,n’) \oplus G(m’,n) \oplus G(m,n’)~:~0 \leq m’ < m, 0 \leq n’ < n) $

and so by induction these Grundy numbers are equal to the Nim-multiplication $G(m,n) = m \otimes n $ where

$m \otimes n = mex(m’ \otimes n’ \oplus m’ \otimes n \oplus m \otimes n’~:~0 \leq m’ < m, 0 \leq n’ < n) $

Thus, we can evaluate any Nimbers-position with stone-coordinates smaller than $2^{2^n} $ by calculating in a finite field using the identification (as for example in the odd Knights of the round table-post) $\mathbb{F}_{2^{2^n}} = \{ 0,1,2,\ldots,2^{2^n}-1 \} $

For example, when all stones lie in a 15×15 grid (as in the example above), all calculations can be performed using

Here, we’ve identified the non-zero elements of $\mathbb{F}_{16} $ with 15-th roots of unity, allowing us to multiply, and we’ve paired up couples $(n,n \oplus 1) $ allowing u to reduce nim-addition to nim-multiplication via

$n \oplus m = (n \otimes \frac{1}{m}) \otimes (m \oplus 1) $

In particular, the stone at position (14,8) is equivalent to a Nim-heap of size $14 \otimes 8=10 $. The nim-value of the original position is equal to 8

Suppose your opponent lets you add one extra stone along the diagonal if you allow her to start the game, where would you have to place it and be certain you will win the game?

One Comment

Seating the first few thousand Knights

The Knight-seating problems asks for a consistent placing of n-th Knight at an odd root of unity, compatible with the two different realizations of the algebraic closure of the field with two elements.
The first identifies the multiplicative group of its non-zero elements with the group of all odd complex roots of unity, under complex multiplication. The second uses Conway’s ‘simplicity rules’ to define an addition and multiplication on the set of all ordinal numbers.

The odd Knights of the round table-problem asks for a specific one-to-one correspondence between two realizations of ‘the’ algebraic closure $\overline{\mathbb{F}_2} $ of the field of two elements.

The first identifies the multiplicative group of its non-zero elements with the group of all odd complex roots of unity, under complex multiplication. The addition on $\overline{\mathbb{F}_2} $ is then recovered by inducing an involution on the odd roots, pairing the one corresponding to x to the one corresponding to x+1.

The second uses Conway’s ‘simplicity rules’ to define an addition and multiplication on the set of all ordinal numbers. Conway proves in ONAG that this becomes an algebraically closed field of characteristic two and that $\overline{\mathbb{F}_2} $ is the subfield of all ordinals smaller than $\omega^{\omega^{\omega}} $. The finite ordinals (the natural numbers) form the quadratic closure of $\mathbb{F}_2 $.

On the natural numbers the Conway-addition is binary addition without carrying and Conway-multiplication is defined by the properties that two different Fermat-powers $N=2^{2^i} $ multiply as they do in the natural numbers, and, Fermat-powers square to its sesquimultiple, that is $N^2=\frac{3}{2}N $. Moreover, all natural numbers smaller than $N=2^{2^{i}} $ form a finite field $\mathbb{F}_{2^{2^i}} $. Using distributivity, one can write down a multiplication table for all 2-powers.



The Knight-seating problems asks for a consistent placing of n-th Knight $K_n $ at an odd root of unity, compatible with the two different realizations of $\overline{\mathbb{F}_2} $. Last time, we were able to place the first 15 Knights as below, and asked where you would seat $K_{16} $



$K_4 $ was placed at $e^{2\pi i/15} $ as 4 was the smallest number generating the ‘Fermat’-field $\mathbb{F}_{2^{2^2}} $ (with multiplicative group of order 15) subject to the compatibility relation with the generator 2 of the smaller Fermat-field $\mathbb{F}_2 $ (with group of order 15) that $4^5=2 $.

To include the next Fermat-field $\mathbb{F}_{2^{2^3}} $ (with multiplicative group of order 255) consistently, we need to find the smallest number n generating the multiplicative group and satisfying the compatibility condition $n^{17}=4 $. Let’s first concentrate on finding the smallest generator : as 2 is a generator for 1st Fermat-field $\mathbb{F}_{2^{2^1}} $ and 4 a generator for the 2-nd Fermat-field $\mathbb{F}_{2^{2^2}} $ a natural conjecture might be that 16 is a generator for the 3-rd Fermat-field $\mathbb{F}_{2^{2^3}} $ and, more generally, that $2^{2^i} $ would be a generator for the next field $\mathbb{F}_{2^{2^{i+1}}} $.

However, an “exercise” in the 1978-paper by Hendrik Lenstra Nim multiplication asks : “Prove that $2^{2^i} $ is a primitive root in the field $\mathbb{F}_{2^{2^{i+1}}} $ if and only if i=0 or 1.”

I’ve struggled with several of the ‘exercises’ in Lenstra’s paper to the extend I feared Alzheimer was setting in, only to find out, after taking pen and paper and spending a considerable amount of time calculating, that they are indeed merely exercises, when looked at properly… (Spoiler-warning : stop reading now if you want to go through this exercise yourself).

In the picture above I’ve added in red the number $x(x+1)=x^2+1 $ to each of the involutions. Clearly, for each pair these numbers are all distinct and we see that for the indicated pairing they make up all numbers strictly less than 8.

By Conway’s simplicity rules (or by checking) the pair (16,17) gives the number 8. In other words, the equation
$x^2+x+8 $ is an irreducible polynomial over $\mathbb{F}_{16} $ having as its roots in $\mathbb{F}_{256} $ the numbers 16 and 17. But then, 16 and 17 are conjugated under the Galois-involution (the Frobenius $y \mapsto y^{16} $). That is, we have $16^{16}=17 $ and $17^{16}=16 $ and hence $16^{17}=8 $. Now, use the multiplication table in $\mathbb{F}_{16} $ given in the previous post (or compute!) to see that 8 is of order 5 (and NOT a generator). As a consequence, the multiplicative order of 16 is 5×17=85 and so 16 cannot be a generator in $\mathbb{F}_{256} $.
For general i one uses the fact that $2^{2^i} $ and $2^{2^i}+1 $ are the roots of the polynomial $x^2+x+\prod_{j<i} 2^{2^j} $ over $\mathbb{F}_{2^{2^i}} $ and argues as before.

Right, but then what is the minimal generator satisfying $n^{17}=4 $? By computing we see that the pairings of all numbers in the range 16…31 give us all numbers in the range 8…15 and by the above argument this implies that the 17-th powers of all numbers smaller than 32 must be different from 4. But then, the smallest candidate is 32 and one verifies that indeed $32^{17}=4 $ (use the multiplication table given before).

Hence, we must place Knight $K_{32} $ at root $e^{2 \pi i/255} $ and place the other Knights prior to the 256-th at the corresponding power of 32. I forgot the argument I used to find-by-hand the requested place for Knight 16, but one can verify that $32^{171}=16 $ so we seat $K_{16} $ at root $e^{342 \pi i/255} $.

But what about Knight $K_{256} $? Well, by this time I was quite good at squaring and binary representations of integers, but also rather tired, and decided to leave that task to the computer.

If we denote Nim-addition and multiplication by $\oplus $ and $\otimes $, then Conway’s simplicity results in ONAG establish a field-isomorphism between $~(\mathbb{N},\oplus,\otimes) $ and the field $\mathbb{F}_2(x_0,x_1,x_2,\ldots ) $ where the $x_i $ satisfy the Artin-Schreier equations

$x_i^2+x_i+\prod_{j < i} x_j = 0 $

and the i-th Fermat-field $\mathbb{F}_{2^{2^i}} $ corresponds to $\mathbb{F}_2(x_0,x_1,\ldots,x_{i-1}) $. The correspondence between numbers and elements from these fields is given by taking $x_i \mapsto 2^{2^i} $. But then, wecan write every 2-power as a product of the $x_i $ and use the binary representation of numbers to perform all Nim-calculations with numbers in these fields.

Therefore, a quick and dirty way (and by no means the most efficient) to do Nim-calculations in the next Fermat-field consisting of all numbers smaller than 65536, is to use sage and set up the field $\mathbb{F}_2(x_0,x_1,x_2,x_3) $ by

R.< x,y,z,t > =GF(2)[]
S.< a,b,c,d >=R.quotient((x^2+x+1,y^2+y+x,z^2+z+x*y,t^2+t+x*y*z))

To find the smallest number generating the multiplicative group and satisfying the additional compatibility condition $n^{257}=32 $ we have to find the smallest binary number $i_1i_2 \ldots i_{16} $ (larger than 255) satisfying

(i1*a*b*c*t+i2*b*c*t+i3*a*c*t+i4*c*t+i5*a*b*t+i6*b*t+
i7*a*t+i8*t+i9*a*b*c+i10*b*c+i11*a*c+i12*c+i13*a*b+
i14*b+i15*a+i16)^257=a*c

It takes a 2.4GHz 2Gb-RAM MacBook not that long to decide that the requested generator is 1051 (killing another optimistic conjecture that these generators might be 2-powers). So, we seat Knight
$K_{1051} $ at root $e^{2 \pi i/65535} $ and can then arrange seatings for all Knight queued up until we reach the 65536-th! In particular, the first Knight we couldn’t place before, that is Knight $K_{256} $, will be seated at root $e^{65826 \pi i/65535} $.

If you’re lucky enough to own a computer with more RAM, or have the patience to make the search more efficient and get the seating arrangement for the next Fermat-field, please drop a comment.

I’ll leave you with another Lenstra-exercise which shouldn’t be too difficult for you to solve now : “Prove that $x^3=2^{2^i} $ has three solutions in $\mathbb{N} $ for each $i \geq 2 $.”

2 Comments

can -oids save group-theory 101?

Two questions from my last group-theory 101 exam:

(a) : What are the Jordan-Holder components of the Abelian group $\mathbb{Z}/20 \mathbb{Z} $?

(b) : Determine the number of order 7 elements in a simple group of order 168.

Give these to any group of working mathematicians, and, I guess all of them will solve (a), whereas the number of correct solutions to (b) will be (substantially) smaller.

Guess what? All(!) my students solved (b) correctly, whereas almost none of them had anything sensible to say about (a). A partial explanation is that they had more drill-exercises applying the Sylow-theorems than ones concerning the Jordan-Holder theorem.

A more fundamental explanation is that (b) has to do with sub-structures whereas (a) concerns quotients. Over the years I’ve tried numerous methods to convey the quotient-idea : putting things in bags, dividing a big group-table into smaller squares, additional lessons on relations, counting modulo numbers … No method appears to have an effect, lasting until the examination.

At the moment I’m seriously considering to rewrite the entire course, ditching quotients and using them only in disguise via groupoids. Before you start bombarding me with comments, I’m well aware of the problems inherent in this approach.

Before you do groupoids, students have to know some basic category theory. But that’s ok with me. Since last year it has been decided that I should sacrifice the first three weeks of the course telling students the basics of sets, maps and relations. After this, the formal definition of a category will appear more natural to them than the definition of a group, not? Besides, most puzzle-problems I use to introduce groups are actually examples of groupoids…

But then, what are the main theorems on finite groupoids? Well, I can see the groupoid cardinality result, giving you in one stroke Lagrange’s theorem as well as the orbit-counting method. From this one can then prove the remaining classical group-results such as Cauchy and the Sylows, but perhaps there are more elegant approaches?

Have you seen a first-year group-theory course starting off with groupoids? Do you know an elegant way to prove a classical group-result using groupoids?

2 Comments

On2 : extending Lenstra’s list

We have seen that John Conway defined a nim-addition and nim-multiplication on the ordinal numbers in such a way that the subfield $[\omega^{\omega^{\omega}}] \simeq \overline{\mathbb{F}}_2 $ is the algebraic closure of the field on two elements. We’ve also seen how to do actual calculations in that field provided we can determine the mystery elements $\alpha_p $, which are the smallest ordinals not being a p-th power of ordinals lesser than $[\omega^{\omega^{k-1}}] $ if $p $ is the $k+1 $-th prime number.

Hendrik Lenstra came up with an effective method to compute these elements $\alpha_p $ requiring a few computations in certain finite fields. I’ll give a rundown of his method and refer to his 1977-paper “On the algebraic closure of two” for full details.

For any ordinal $\alpha < \omega^{\omega^{\omega}} $ define its degree $d(\alpha) $ to be the degree of minimal polynomial for $\alpha $ over $\mathbb{F}_2 = [2] $ and for each prime number $p $ let $f(p) $ be the smallest number $h $ such that $p $ is a divisor of $2^h-1 $ (clearly $f(p) $ is a divisor of $p-1 $).

In the previous post we have already defined ordinals $\kappa_{p^k}=[\omega^{\omega^{k-1}.p^{n-1}}] $ for prime-power indices, but we now need to extend this definition to allow for all indices. So. let $h $ be a natural number, $p $ the smallest prime number dividing $h $ and $q $ the highest power of $p $ dividing $h $. Let $g=[h/q] $, then Lenstra defines

$\kappa_h = \begin{cases} \kappa_q~\text{if q divides}~d(\kappa_q)~\text{ and} \\ \kappa_g + \kappa_q = [\kappa_g + \kappa_q]~\text{otherwise} \end{cases} $

With these notations, the main result asserts the existence of natural numbers $m,m’ $ such that

$\alpha_p = [\kappa_{f(p)} + m] = [\kappa_{f(p)}] + m’ $

Now, assume by induction that we have already determined the mystery numbers $\alpha_r $ for all odd primes $r < p $, then by teh argument of last time we can effectively compute in the field $[\kappa_p] $. In particular, we can compute for every element its multiplicative order $ord(\beta) $ and therefore also its degree $d(\beta) $ which has to be the smallest number $h $ such that $ord(\beta) $ divides $[2^h-1] $.

Then, by the main result we only have to determine the smallest number m such that $\beta = [\kappa_{f(p)} +m] $ is not a p-th power in $\kappa_p $ which is equivalent to the condition that

$\beta^{(2^{d(\beta)}-1)/p} \not= 1 $ if $p $ divides $[2^{d(\beta)}-1] $

All these conditions can be verified within suitable finite fields and hence are effective. In this manner, Lenstra could extend Conway’s calculations (probably using a home-made finite field program running on a slow 1977 machine) :

[tex]\begin{array}{c|c|c} p & f(p) & \alpha_p \\ \hline 3 & 2 & [2] \\ 5 & 4 & [4] \\ 7 & 3 & [\omega]+1 \\ 11 & 10 & [\omega^{\omega}]+1 \\ 13 & 12 & [\omega]+4 \\ 17 & 8 & [16] \\ 19 & 18 & [\omega^3]+4 \\ 23 & 11 & [\omega^{\omega^3}]+1 \\ 29 & 28 & [\omega^{\omega^2}]+4 \\ 31 & 5 & [\omega^{\omega}]+1 \\ 37 & 36 & [\omega^3]+4 \\ 41 & 20 & [\omega^{\omega}]+1 \\ 43 & 14 & [\omega^{\omega^2}]+ 1 \end{array}[/tex]

Right, so let’s try the case $p=47 $. To begin, $f(47)=23 $ whence we have to determine the smallest field containg $\kappa_{23} $. By induction (Lenstra’s tabel) we know already that

$\kappa_{23}^{23} = \kappa_{11} + 1 = [\omega^{\omega^3}]+1 $ and $\kappa_{11}^{11} = \kappa_5 + 1 = [\omega^{\omega}]+1 $ and $\kappa_5^5=[4] $

Because the smallest field containg $4 $ is $[16]=\mathbb{F}_{2^4} $ we have that $\mathbb{F}_2(4,\kappa_5,\kappa_{11}) \simeq \mathbb{F}_{2^{220}} $. We can construct this finite field, together with a generator $a $ of its multiplicative group in Sage via


sage: f1.< a >=GF(2^220)

In this field we have to pinpoint the elements $4,\kappa_5 $ and $\kappa_{11} $. As $4 $ has order $15 $ in $\mathbb{F}_{2^4} $ we know that $\kappa_5 $ has order $75 $. Hence we can take $\kappa_5 = a^{(2^{220}-1)/75} $ and then $4=\kappa_5^5 $.

If we denote $\kappa_5 $ by x5 we can obtain $\kappa_{11} $ as x11 by the following sage-commands


sage: c=x5+1

sage: x11=c.nth_root(11)

It takes about 7 minutes to find x11 on a 2.4 GHz MacBook. Next, we have to set up the field extension determined by $\kappa_{23} $ (which we will call x in sage). This is done as follows


sage: p1.=PolynomialRing(f1)

sage: f=x^23-x11-1

sage: F2=f1.extension(f,'u')

The MacBook needed 8 minutes to set up this field which is isomorphic to $\mathbb{F}_{2^{5060}} $. The relevant number is therefore $n=\frac{2^{5060}-1}{47} $ which is the gruesome

34648162040462867047623719793206539850507437636617898959901744136581<br/>
259144476645069239839415478030722644334257066691823210120548345667203443<br/>
317743531975748823386990680394012962375061822291120459167399032726669613
<br/>
442804392429947890878007964213600720766879334103454250982141991553270171

938532417844211304203805934829097913753132491802446697429102630902307815

301045433019807776921086247690468136447620036910689177286910624860871748

150613285530830034500671245400628768674394130880959338197158054296625733

206509650361461537510912269982522844517989399782602216622257291361930850

885916974186835958466930689748400561295128553674118498999873244045842040

080195019701984054428846798610542372150816780493166669821114184374697446

637066566831036116390063418916814141753876530004881539570659100352197393

997895251223633176404672792711603439161147155163219282934597310848529360

118189507461132290706604796116111868096099527077437183219418195396666836

014856037176421475300935193266597196833361131333604528218621261753883518

667866835204501888103795022437662796445008236823338104580840186181111557

498232520943552183185687638366809541685702608288630073248626226874916669

186372183233071573318563658579214650042598011275864591248749957431967297

975078011358342282941831582626985121760847852546207377440873367589369439

085660784239080183415569559585998884824991911321095149718147110882474280

968166266224151511519773175933506503369761671964823112231808283557885030

984081329986188655169245595411930535264918359325712373064120338963742590

76555755141425

Remains ‘only’ to take x,x+1,etc. to the n-th power and verify which is the first to be unequal to 1. For this it is best to implement the usual powering trick (via digital expression of the exponent) in the field F2, something like


sage: def power(e,n):
...: le=n.bits()
...: v=n.digits()
...: mn=F2(e)
...: out=F2(1)
...: i=0
...: while i< le :
...: if v[i]==1 : out=F2(out_mn)
...: m=F2(mn_mn)
...: mn=F2(m)
...: i=i+1
...: return(out)
...:

then it takes about 20 seconds to verify that power(x,n)=1 but that power(x+1,n) is NOT! That is, we just checked that $\alpha_{47}=\kappa_{11}+1 $.

It turns out that 47 is the hardest nut to crack, the following primes are easier. Here’s the data (if I didn’t make mistakes…)

[tex]\begin{array}{c|c|c} p & f(p) & \alpha_p \\ \hline 47 & 23 & [\omega^{\omega^{7}}]+1 \\ 53 & 52 & [\omega^{\omega^4}]+1 \\ 59 & 58 & [\omega^{\omega^8}]+1 \\ 61 & 60 & [\omega^{\omega}]+[\omega] \\ 67 & 66 & [\omega^{\omega^3}]+[\omega] \end{array}[/tex]

It seems that Magma is substantially better at finite field arithmetic, so if you are lucky enough to have it you’ll have no problem finding $\alpha_p $ for all primes less than 100 by the end of the day. If you do, please drop a comment with the results…

Leave a Comment

On2 : Conway’s nim-arithmetics

Last time we did recall Cantor’s addition and multiplication on ordinal numbers. Note that we can identify an ordinal number $\alpha $ with (the order type of) the set of all strictly smaller ordinals, that is, $\alpha = { \alpha’~:~\alpha’ < \alpha } $. Given two ordinals $\alpha $ and $\beta $ we will denote their Cantor-sums and products as $[ \alpha + \beta] $ and $[\alpha . \beta] $.

The reason for these square brackets is that John Conway constructed a well behaved nim-addition and nim-multiplication on all ordinals $\mathbf{On}_2 $ by imposing the ‘simplest’ rules which make $\mathbf{On}_2 $ into a field. By this we mean that, in order to define the addition $\alpha + \beta $ we must have constructed before all sums $\alpha’ + \beta $ and $\alpha + \beta’ $ with $\alpha’ < \alpha $ and $\beta’ < \beta $. If + is going to be a well-defined addition on $\mathbf{On}_2 $ clearly $\alpha + \beta $ cannot be equal to one of these previously constructed sums and the ‘simplicity rule’ asserts that we should take $\alpha+\beta $ the least ordinal different from all these sums $\alpha’+\beta $ and $\alpha+\beta’ $. In symbols, we define

$\alpha+ \beta = \mathbf{mex} { \alpha’+\beta,\alpha+ \beta’~|~\alpha’ < \alpha, \beta’ < \beta } $

where $\mathbf{mex} $ stands for ‘minimal excluded value’. If you’d ever played the game of Nim you will recognize this as the Nim-addition, at least when $\alpha $ and $\beta $ are finite ordinals (that is, natural numbers) (to nim-add two numbers n and m write them out in binary digits and add without carrying). Alternatively, the nim-sum n+m can be found applying the following two rules :

  • the nim-sum of a number of distinct 2-powers is their ordinary sum (e.g. $8+4+1=13 $, and,
  • the nim-sum of two equal numbers is 0.

So, all we have to do is to write numbers n and m as sums of two powers, scratch equal terms and add normally. For example, $13+7=(8+4+1)+(4+2+1)=8+2=10 $ (of course this is just digital sum without carry in disguise).

Here’s the beginning of the nim-addition table on ordinals. For example, to define $13+7 $ we have to look at all values in the first 7 entries of the row of 13 (that is, ${ 13,12,15,14,9,8,11 } $) and the first 13 entries in the column of 7 (that is, ${ 7,6,5,4,3,2,1,0,15,14,13,12,11 } $) and find the first number not included in these two sets (which is indeed $10 $).

In fact, the above two rules allow us to compute the nim-sum of any two ordinals. Recall from last time that every ordinal can be written uniquely as as a finite sum of (ordinal) 2-powers :
$\alpha = [2^{\alpha_0} + 2^{\alpha_1} + \ldots + 2^{\alpha_k}] $, so to determine the nim-sum $\alpha+\beta $ we write both ordinals as sums of ordinal 2-powers, delete powers appearing twice and take the Cantor ordinal sum of the remaining sum.

Nim-multiplication of ordinals is a bit more complicated. Here’s the definition as a minimal excluded value

$\alpha.\beta = \mathbf{mex} { \alpha’.\beta + \alpha.\beta’ – \alpha’.\beta’ } $

for all $\alpha’ < \alpha, \beta’ < \beta $. The rationale behind this being that both $\alpha-\alpha’ $ and $\beta – \beta’ $ are non-zero elements, so if $\mathbf{On}_2 $ is going to be a field under nim-multiplication, their product should be non-zero (and hence strictly greater than 0), that is, $~(\alpha-\alpha’).(\beta-\beta’) > 0 $. Rewriting this we get $\alpha.\beta > \alpha’.\beta+\alpha.\beta’-\alpha’.\beta’ $ and again the ‘simplicity rule’ asserts that $\alpha.\beta $ should be the least ordinal satisfying all these inequalities, leading to the $\mathbf{mex} $-definition above. The table gives the beginning of the nim-multiplication table for ordinals. For finite ordinals n and m there is a simple 2 line procedure to compute their nim-product, similar to the addition-rules mentioned before :

  • the nim-product of a number of distinct Fermat 2-powers (that is, numbers of the form $2^{2^n} $) is their ordinary product (for example, $16.4.2=128 $), and,
  • the square of a Fermat 2-power is its sesquimultiple (that is, the number obtained by multiplying with $1\frac{1}{2} $ in the ordinary sense). That is, $2^2=3,4^2=6,16^2=24,… $

Using these rules, associativity and distributivity and our addition rules it is now easy to work out the nim-multiplication $n.m $ : write out n and m as sums of (multiplications by 2-powers) of Fermat 2-powers and apply the rules. Here’s an example

$5.9=(4+1).(4.2+1)=4^2.2+4.2+4+1=6.2+8+4+1=(4+2).2+13=4.2+2^2+13=8+3+13=6 $

Clearly, we’d love to have a similar procedure to calculate the nim-product $\alpha.\beta $ of arbitrary ordinals, or at least those smaller than $\omega^{\omega^{\omega}} $ (recall that Conway proved that this ordinal is isomorphic to the algebraic closure $\overline{\mathbb{F}}_2 $ of the field of two elements). From now on we restrict to such ‘small’ ordinals and we introduce the following special elements :

$\kappa_{2^n} = [2^{2^{n-1}}] $ (these are the Fermat 2-powers) and for all primes $p > 2 $ we define
$\kappa_{p^n} = [\omega^{\omega^{k-1}.p^{n-1}}] $ where $k $ is the number of primes strictly smaller than $p $ (that is, for p=3 we have k=1, for p=5, k=2 etc.).

Again by associativity and distributivity we will be able to multiply two ordinals $< \omega^{\omega^{\omega}} $ if we know how to multiply a product

$[\omega^{\alpha}.2^{n_0}].[\omega^{\beta}.2^{m_0}] $ with $\alpha,\beta < [\omega^{\omega}] $ and $n_0,m_0 \in \mathbb{N} $.

Now, $\alpha $ can be written uniquely as $[\omega^t.n_t+\omega^{t-1}.n_{t-1}+\ldots+\omega.n_2 + n_1] $ with t and all $n_i $ natural numbers. Write each $n_k $ in base $p $ where $p $ is the $k+1 $-th prime number, that is, we have for $n_0,n_1,\ldots,n_t $ an expression

$n_k=[\sum_j p^j.m(j,k)] $ with $0 \leq m(j,k) < p $

The point of all this is that any of the special elements we want to multiply can be written as a unique expression as a decreasing product

$[\omega^{\alpha}.2^{n_0}] = [ \prod_q \kappa_q^m(q) ] $

where $q $ runs over all prime powers. The crucial fact now is that for this decreasing product we have a rule similar to addition of 2-powers, that is Conway-products coincide with the Cantor-products

$[ \prod_q \kappa_q^m(q) ] = \prod_q \kappa_q^m(q) $

But then, using associativity and commutativity of the Conway-product we can ‘nearly’ describe all products $[\omega^{\alpha}.2^{n_0}].[\omega^{\beta}.2^{m_0}] $. The remaining problem being that it may happen that for some q we will end up with an exponent $m(q)+m(q’)>p $. But this can be solved if we know how to take p-powers. The rules for this are as follows

$~(\kappa_{2^n})^2 = \kappa_{2^n} + \prod_{1 \leq i < n} \kappa_{2^i} $, for 2-powers, and,

$~(\kappa_{p^n})^p = \kappa_{p^{n-1}} $ for a prime $p > 2 $ and for $n \geq 2 $, and finally

$~(\kappa_p)^p = \alpha_p $ for a prime $p > 2 $, where $\alpha_p $ is the smallest ordinal $< \kappa_p $ which cannot be written as a p-power $\beta^p $ with $\beta < \kappa_p $. Summarizing : if we will be able to find these mysterious elements $\alpha_p $ for all prime numbers p, we are able to multiply in $[\omega^{\omega^{\omega}}]=\overline{\mathbb{F}}_2 $.

Let us determine the first one. We have that $\kappa_3 = \omega $ so we are looking for the smallest natural number $n < \omega $ which cannot be written in num-multiplication as $n=m^3 $ for $m < \omega $ (that is, also $m $ a natural number). Clearly $1=1^3 $ but what about 2? Can 2 be a third root of a natural number wrt. nim-multiplication? From the tabel above we see that 2 has order 3 whence its cube root must be an element of order 9. Now, the only finite ordinals that are subfields of $\mathbf{On}_2 $ are precisely the Fermat 2-powers, so if there is a finite cube root of 2, it must be contained in one of the finite fields $[2^{2^n}] $ (of which the mutiplicative group has order $2^{2^n}-1 $ and one easily shows that 9 cannot be a divisor of any of the numbers $2^{2^n}-1 $, that is, 2 doesn’t have a finte 3-th root in nim! Phrased differently, we found our first mystery number $\alpha_3 = 2 $. That is, we have the marvelous identity in nim-arithmetic

$\omega^3 = 2 $

Okay, so what is $\alpha_5 $? Well, we have $\kappa_5 = [\omega^{\omega}] $ and we have to look for the smallest ordinal which cannot be written as a 5-th root. By inspection of the finite nim-table we see that 1,2 and 3 have 5-th roots in $\omega $ but 4 does not! The reason being that 4 has order 15 (check in the finite field [16]) and 25 cannot divide any number of the form $2^{2^n}-1 $. That is, $\alpha_5=4 $ giving another crazy nim-identity

$~(\omega^{\omega})^5 = 4 $

And, surprises continue to pop up… Conway showed that $\alpha_7 = \omega+1 $ giving the nim-identity $~(\omega^{\omega^2})^7 = \omega+1 $. The proof of this already uses some clever finite field arguments. Because 7 doesn’t divide any number $2^{2^n}-1 $, none of the finite subfields $[2^{2^n}] $ contains a 7-th root of unity, so the 7-power map is injective whence surjective, so all finite ordinal have finite 7-th roots! That is, $\alpha_7 \geq \omega $. Because $\omega $ lies in a cubic extension of the finite field [4], the field generated by $\omega $ has 64 elements and so its multiplicative group is cyclic of order 63 and as $\omega $ has order 9, it must be a 7-th power in this field. But, as the only 7th powers in that field are precisely the powers of $\omega $ and by inspection $\omega+1 $ is not a 7-th power in that field (and hence also not in any field extension obtained by adjoining square, cube and fifth roots) so $\alpha_7=\omega +1 $.

Conway did stop at $\alpha_7 $ but I’ve always been intrigued by that one line in ONAG p.61 : “Hendrik Lenstra has computed $\alpha_p $ for $p \leq 43 $”. Next time we will see how Lenstra managed to do this and we will use sage to extend his list a bit further, including the first open case : $\alpha_{47}= \omega^{\omega^7}+1 $.

For an enjoyable video on all of this, see Conway’s MSRI lecture on Infinite Games. The nim-arithmetic part is towards the end of the lecture but watching the whole video is a genuine treat!

Leave a Comment