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 }^{\prime }:{\alpha }^{\prime }<\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 }^{\prime }+\beta$ and $\alpha +{\beta }^{\prime }$ with ${\alpha }^{\prime }<\alpha$ and ${\beta }^{\prime }<\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 }^{\prime }+\beta$ and $\alpha +{\beta }^{\prime }$. In symbols, we define

$\alpha +\beta =\mathbf{mex}{\alpha }^{\prime }+\beta ,\alpha +{\beta }^{\prime }|{\alpha }^{\prime }<\alpha ,{\beta }^{\prime }<\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}+\dots +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 }^{\prime }.\beta +\alpha .{\beta }^{\prime }–{\alpha }^{\prime }.{\beta }^{\prime }$

for all ${\alpha }^{\prime }<\alpha ,{\beta }^{\prime }<\beta$. The rationale behind this being that both $\alpha -{\alpha }^{\prime }$ and $\beta –{\beta }^{\prime }$ 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 }^{\prime }).(\beta -{\beta }^{\prime })>0$. Rewriting this we get $\alpha .\beta >{\alpha }^{\prime }.\beta +\alpha .{\beta }^{\prime }-{\alpha }^{\prime }.{\beta }^{\prime }$ 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,\dots$

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 ${\bar{\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}+\dots +\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,\dots ,n_t$ an expression

$n_k=[\sum _j{p}^j.m(j,k)]$ with $0\le 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^{\prime })>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\le 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\ge 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 }}]={\bar{\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\ge \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\le 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!