Skip to content →

neverendingbooks Posts

On2 : Conway’s nim-arithmetics

Published January 26, 2009 by lievenlb

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

On2 : transfinite number hacking

Published January 8, 2009 by lievenlb

In ONAG, John Conway proves that the symmetric version of his recursive definition of addition and multiplcation on the surreal numbers make the class On of all Cantor’s ordinal numbers into an algebraically closed Field of characteristic two : On2 (pronounced ‘Onto’), and, in particular, he identifies a subfield
with the algebraic closure of the field of two elements. What makes all of this somewhat confusing is that Cantor had already defined a (badly behaving) addition, multiplication and exponentiation on ordinal numbers.

Over the last week I’ve been playing a bit with sage to prove a few exotic identities involving ordinal numbers. Here’s one of them ($\omega $ is the first infinite ordinal number, that is, $\omega={ 0,1,2,\ldots } $),

$~(\omega^{\omega^{13}})^{47} = \omega^{\omega^7} + 1 $

answering a question in Hendrik Lenstra’s paper Nim multiplication.

However, it will take us a couple of posts before we get there. Let’s begin by trying to explain what brought this on. On september 24th 2008 there was a meeting, intended for a general public, called a la rencontre des dechiffeurs, celebrating the 50th birthday of the IHES.

One of the speakers was Alain Connes and the official title of his talk was “L’ange de la géométrie, le diable de l’algèbre et le corps à un élément” (the angel of geometry, the devil of algebra and the field with one element). Instead, he talked about a seemingly trivial problem : what is the algebraic closure of $\mathbb{F}_2 $, the field with two elements? My only information about the actual content of the talk comes from the following YouTube-blurb

Alain argues that we do not have a satisfactory description of $\overline{\mathbb{F}}_2 $, the algebraic closure of $\mathbb{F}_2 $. Naturally, it is the union (or rather, limit) of all finite fields $\mathbb{F}_{2^n} $, but, there are too many non-canonical choices to make here.

Recall that $\mathbb{F}_{2^k} $ is a subfield of $\mathbb{F}_{2^l} $ if and only if $k $ is a divisor of $l $ and so we would have to take the direct limit over the integers with respect to the divisibility relation… Of course, we can replace this by an increasing sequence of a selection of cofinal fields such as

$\mathbb{F}_{2^{1!}} \subset \mathbb{F}_{2^{2!}} \subset \mathbb{F}_{2^{3!}} \subset \ldots $

But then, there are several such suitable sequences! Another ambiguity comes from the description of $\mathbb{F}_{2^n} $. Clearly it is of the form $\mathbb{F}_2[x]/(f(x)) $ where $f(x) $ is a monic irreducible polynomial of degree $n $, but again, there are several such polynomials. An attempt to make a canonical choice of polynomial is to take the ‘first’ suitable one with respect to some natural ordering on the polynomials. This leads to the so called Conway polynomials.

Conway polynomials for the prime $2 $ have only been determined up to degree 400-something, so in the increasing sequence above we would already be stuck at the sixth term $\mathbb{F}_{2^{6!}} $…

So, what Alain Connes sets as a problem is to find another, more canonical, description of $\overline{\mathbb{F}}_2 $. The problem is not without real-life interest as most finite fields appearing in cryptography or coding theory are subfields of $\overline{\mathbb{F}}_2 $.

(My guess is that Alain originally wanted to talk about the action of the Galois group on the roots of unity, which would be the corresponding problem over the field with one element and would explain the title of the talk, but decided against it. If anyone knows what ‘coupling-problem’ he is referring to, please drop a comment.)

Surely, Connes is aware of the fact that there exists a nice canonical recursive construction of $\overline{\mathbb{F}}_2 $ due to John Conway, using Georg Cantor’s ordinal numbers.

In fact, in chapter 6 of his book On Numbers And Games, John Conway proves that the symmetric version of his recursive definition of addition and multiplcation on the surreal numbers make the class $\mathbf{On} $ of all Cantor’s ordinal numbers into an algebraically closed Field of characteristic two : $\mathbf{On}_2 $ (pronounced ‘Onto’), and, in particular, he identifies a subfield

$\overline{\mathbb{F}}_2 \simeq [ \omega^{\omega^{\omega}} ] $

with the algebraic closure of $\mathbb{F}_2 $. What makes all of this somewhat confusing is that Cantor had already defined a (badly behaving) addition, multiplication and exponentiation on ordinal numbers. To distinguish between the Cantor/Conway arithmetics, Conway (and later Lenstra) adopt the convention that any expression between square brackets refers to Cantor-arithmetic and un-squared ones to Conway’s. So, in the description of the algebraic closure just given $[ \omega^{\omega^{\omega}} ] $ is the ordinal defined by Cantor-exponentiation, whereas the exotic identity we started out with refers to Conway’s arithmetic on ordinal numbers.

Let’s recall briefly Cantor’s ordinal arithmetic. An ordinal number $\alpha $ is the order-type of a totally ordered set, that is, if there is an order preserving bijection between two totally ordered sets then they have the same ordinal number (or you might view $\alpha $ itself as a totally ordered set, namely the set of all strictly smaller ordinal numbers, so e.g. $0= \emptyset,1= { 0 },2={ 0,1 },\ldots $).

For two ordinals $\alpha $ and $\beta $, the addition $[\alpha + \beta ] $ is the order-type of the totally ordered set $\alpha \sqcup \beta $ (the disjoint union) ordered compatible with the total orders in $\alpha $ and $\beta $ and such that every element of $\beta $ is strictly greater than any element from $\alpha $. Observe that this definition depends on the order of the two factors. For example,$ [1 + \omega] = \omega $ as there is an order preserving bijection ${ \tilde{0},0,1,2,\ldots } \rightarrow { 0,1,2,3,\ldots } $ by $\tilde{0} \mapsto 0,n \mapsto n+1 $. However, $\omega \not= [\omega + 1] $ as there can be no order preserving bijection ${ 0,1,2,\ldots } \rightarrow { 0,1,2,\ldots,0_{max} } $ as the first set has no maximal element whereas the second one does. So, Cantor’s addition has the bad property that it may be that $[\alpha + \beta] \not= [\beta + \alpha] $.

The Cantor-multiplication $ \alpha . \beta $ is the order-type of the product-set $\alpha \times \beta $ ordered via the last differing coordinate. Again, this product has the bad property that it may happen that $[\alpha . \beta] \not= [\beta . \alpha] $ (for example $[2 . \omega ] \not=[ \omega . 2 ] $). Finally, the exponential $\beta^{\alpha} $ is the order type of the set of all maps $f~:~\alpha \rightarrow \beta $ such that $f(a) \not=0 $ for only finitely many $a \in \alpha $, and ordered via the last differing function-value.

Cantor’s arithmetic allows normal-forms for ordinal numbers. More precisely, with respect to any ordinal number $\gamma \geq 2 $, every ordinal number $\alpha \geq 1 $ has a unique expression as

$\alpha = [ \gamma^{\alpha_0}.\eta_0 + \gamma^{\alpha_1}.\eta_1 + \ldots + \gamma^{\alpha_m}.\eta_m] $

for some natural number $m $ and such that $\alpha \geq \alpha_0 > \alpha_1 > \ldots > \alpha_m \geq 0 $ and all $1 \leq \eta_i < \gamma $. In particular, taking the special cases $\gamma = 2 $ and $\gamma = \omega $, we have the following two canonical forms for any ordinal number $\alpha $

$[ 2^{\alpha_0} + 2^{\alpha_1} + \ldots + 2^{\alpha_m}] = \alpha = [ \omega^{\beta_0}.n_0 + \omega^{\beta_1}.n_1 + \ldots + \omega^{\beta_k}.n_k] $

with $m,k,n_i $ natural numbers and $\alpha \geq \alpha_0 > \alpha_1 > \ldots > \alpha_m \geq 0 $ and $\alpha \geq \beta_0 > \beta_1 > \ldots > \beta_k \geq 0 $. Both canonical forms will be important when we consider the (better behaved) Conway-arithmetic on $\mathbf{On}_2 $, next time.

One Comment

best of 2008 (2) : big theorems

Published January 3, 2009 by lievenlb

Charles Siegel of Rigorous Trivialities ran a great series on big theorems.

The series started january 10th 2008 with a post on Bezout’s theorem, followed by posts on Chow’s lemma, Serre duality, Riemann-Roch, Bertini, Nakayama’s lemma, Groebner bases, Hurwitz to end just before christmas with a post on Kontsevich’s formula.

Also at other blogs, 2008 was the year of series of long posts containing substantial pure mathematics.

Out of many, just two examples : Chris Schommer-Pries ran a three part series on TQFTs via planar algebras starting here, at the secret blogging seminar.
And, Peter Woit of Not Even Wrong has an ungoing series of posts called Notes on BRST, starting here. At the moment he is at episode nine.

It suffices to have a quick look at the length of any of these posts, to see that a great deal of work was put into these series (and numerous similar ones, elsewhere). Is this amount of time well spend? Or, should we focus on shorter, easier digestible math-posts?

What got me thinking was this merciless comment Charles got after a great series of posts leading up to Kontsevich’s formula :

“Perhaps you should make a New Years commitment to not be so obscurantist, like John Armstrong, and instead promote the public understanding of math!”

Well, if this doesn’t put you off blogging for a while, what will?

So, are we really writing the wrong sort of posts? Do math-blog readers only want short, flashy, easy reading posts these days? Or, is anyone out there taking notice of the hard work it takes to write such a technical post, let alone a series of them?

At first I was rather pessimistic about the probable answer to all these questions, but, fortunately we have Google Analytics to quantify things a bit.

Clearly I can only rely on the statistics for my own site, so I’ll treat the case of a recent post here : Mumford’s treasure map which tried to explain the notion of a generic point and how one might depict an affine scheme.

Here’s some of the Google Analytics data :



The yellow function gives the number of pageviews for that post, the value ranges between 0 and 600 (the number to the right of the picture). In total this post was viewed 2470 times, up till now.

The blue function tells the average time a visitor spend reading that post, the numbers range between 0 and 8 minutes (the times to the left of the picture). On average the time-on-page was 2.24 minutes, so in all people spend well over 92 hours reading this one post! This seems like a good return for the time it took me to write it…

Some other things can be learned from this data. Whereas the number of page-views has two peaks early on (one the day it was posted, the second one when Peter Woit linked to it) and is now steadily decreasing, the time-on-page for the later visitors is substantially longer than the early readers.

Some of this may be explained (see comment below) by returning visits. Here is a more detailed picture (orange = new visits, green=returning visits, blue=’total’ whatever this means).



All in all good news : there is indeed a market for longer technical math-posts and people (eventually) take time to read the post in detail.

6 Comments