Skip to content →

On2 : transfinite number hacking

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 (ω is the first infinite ordinal number, that is, ω=0,1,2,),

 (ωω13)47=ωω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 F2, 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 F2, the algebraic closure of F2. Naturally, it is the union (or rather, limit) of all finite fields F2n, but, there are too many non-canonical choices to make here.

Recall that F2k is a subfield of F2l 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

F21!F22!F23!

But then, there are several such suitable sequences! Another ambiguity comes from the description of F2n. Clearly it is of the form F2[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 F26!

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

(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 F2 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 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

F2[ωωω]

with the algebraic closure of F2. 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 [ωωω] 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 α 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 α itself as a totally ordered set, namely the set of all strictly smaller ordinal numbers, so e.g. 0=,1=0,2=0,1,).

For two ordinals α and β, the addition [α+β] is the order-type of the totally ordered set αβ (the disjoint union) ordered compatible with the total orders in α and β and such that every element of β is strictly greater than any element from α. Observe that this definition depends on the order of the two factors. For example,[1+ω]=ω as there is an order preserving bijection 0~,0,1,2,0,1,2,3, by 0~0,nn+1. However, ω[ω+1] as there can be no order preserving bijection 0,1,2,0,1,2,,0max 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 [α+β][β+α].

The Cantor-multiplication α.β is the order-type of the product-set α×β ordered via the last differing coordinate. Again, this product has the bad property that it may happen that [α.β][β.α] (for example [2.ω][ω.2]). Finally, the exponential βα is the order type of the set of all maps f : αβ such that f(a)0 for only finitely many aα, 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 γ2, every ordinal number α1 has a unique expression as

α=[γα0.η0+γα1.η1++γαm.ηm]

for some natural number m and such that αα0>α1>>αm0 and all 1ηi<γ. In particular, taking the special cases γ=2 and γ=ω, we have the following two canonical forms for any ordinal number α

[2α0+2α1++2αm]=α=[ωβ0.n0+ωβ1.n1++ωβk.nk]

with m,k,ni natural numbers and αα0>α1>>αm0 and αβ0>β1>>βk0. Both canonical forms will be important when we consider the (better behaved) Conway-arithmetic on On2, next time.

Published in games number theory