on January 26, 2009 by lieven in games, numbers, Comments (0)

On2 : Conway’s nim-arithmetics

Hello there! If you are new here, you might want to subscribe to the RSS feed for updates on this topic.

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 $\wis{On}_2$ by imposing the ’simplest’ rules which make $\wis{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 $\wis{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 = \wis{mex} \{ \alpha'+\beta,\alpha+ \beta'~|~\alpha' < \alpha, \beta' < \beta \}$

where $\wis{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. , 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 ).

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} + \hdots + 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 = \wis{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 $\wis{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 $\wis{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, ), 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,

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 is the number of primes strictly smaller than (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 \N$ .

Now, $\alpha$ can be written uniquely as $[\omega^t.n_t+\omega^{t-1}.n_{t-1}+\hdots+\omega.n_2 + n_1]$ with t and all n_i natural numbers. Write each n_k in base where is the k+1 -th prime number, that is, we have for $n_0,n_1,\hdots,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 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 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 $\wis{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!

On2 : Conway’s nim-arithmetics

No Comments

Leave a comment

Series of posts

Mathematical Games

Random Posts

Recent Comments

Who's Online

About Me