# Tag: games

In preparing for next year’s ‘seminar noncommutative geometry’ I’ve converted about 30 posts to LaTeX, centering loosely around the topics students have asked me to cover : noncommutative geometry, the absolute point (aka the field with one element), and their relation to the Riemann hypothesis.

The idea being to edit these posts thoroughly, add much more detail (and proofs) and also add some extra sections on Borger’s work and Witt rings (and possibly other stuff).

For those of you who prefer to (re)read these posts on paper or on a tablet rather than perusing this blog, you can now download the very first version (minimally edited) of the eBook ‘geometry and the absolute point’. All comments and suggestions are, of course, very welcome. I hope to post a more definite version by mid-september.

I’ve used the thesis-documentclass to keep the same look-and-feel of my other course-notes, but I would appreciate advice about turning LaTeX-files into ‘proper’ eBooks. I am aware of the fact that the memoir-class has an ebook option, and that one can use the geometry-package to control paper-sizes and margins.

Soon, I will be releasing a LaTeX-ed ‘eBook’ containing the Bourbaki-related posts. Later I might also try it on the games- and groups-related posts…

Mathblogging.org is a recent initiative and may well become the default starting place to check on the status of the mathematical blogosphere.

Handy, if you want to (re)populate your RSS-aggregator with interesting mathematical blogs, is their graphical presentation of (nearly) all math-blogs ordered by type : group blogs, individual researchers, teachers and educators, journalistic writers, communities, institutions and microblogging (twitter). Links to the last 7 posts are given so you can easily determine whether that particular blog is of interest to you.

The three people behind the project, Felix Breuer, Frederik von Heymann and Peter Krautzberger, welcome you to send them links to (micro)blogs they’ve missed. Surely, there must be a lot more mathematicians with a twitter-account than the few ones listed so far…

Even more convenient is their list of latest posts from their collection, ordered by date. I’ve put that page in my Bookmarks Bar the moment I discovered it! It would be nice, if they could provide an RSS-feed of this list, so that people could place it in their sidebar, replacing old-fashioned and useless blogrolls. The site does provide two feeds, but they are completely useless as they click through to empty pages…

While we’re on the topic of math-blogging, the results of the ‘What should we write about next?’-poll that ran the previous two days on the entry page. Of all people visiting that page, 2.6% left suggestions.

The vast majority (67%) wants more posts on noncommutative geometry. Most of you are craving for introductions (and motivation) accessible to undergraduates (as ‘it’s hard to find quality, updated information on this’). In particular, you want posts giving applications in mathematics (especially number theory), or explaining relationships between different approaches. One person knew exactly how I should go about to achieve the hoped-for accessibility : “As a rule, I’d take what you think would be just right for undergrads, and then trim it down a little more.”

Others want rather specialized posts, such as on ‘connection and parallel transport in noncommutative geometry’ or on ‘trees (per J-L. Loday, M. Aguiar, Connes/Kreimer renormalization (aka Butcher group)), or something completely other tree-related’.

Fortunately, some of you told me it was fine to write about ‘combinatorial games and cool nim stuff, finite simple groups, mathematical history, number theory, arithmetic geometry’, pushed me to go for ‘anything monstrous and moonshiney’ (as if I would know the secrets of the ‘connection between the Mathieu group M24 and the elliptic genus of K3’…) or wrote that ‘various algebraic geometry related posts are always welcome: posts like Mumford’s treasure map‘.

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?

For the better part of the 30ties, Ernst Witt (1) did hang out with the rest of the ‘Noetherknaben’, the group of young mathematicians around Emmy Noether (3) in Gottingen.

In 1934 Witt became Helmut Hasse‘s assistent in Gottingen, where he qualified as a university lecturer in 1936. By 1938 he has made enough of a name for himself to be offered a lecturer position in Hamburg and soon became an associate professor, the down-graded position held by Emil Artin (2) until he was forced to emigrate in 1937.

A former fellow student of him in Gottingen, Erna Bannow (4), had gone earlier to Hamburg to work with Artin. She continued her studies with Witt and finished her Ph.D. in 1939. In 1940 Erna Bannow and Witt married.

So, life was smiling on Ernst Witt that sunday january 28th 1940, both professionally and personally. There was just one cloud on the horizon, and a rather menacing one. He was called up by the Wehrmacht and knew he had to enter service in february. For all he knew, he was spending the last week-end with his future wife… (later in february 1940, Blaschke helped him to defer his military service by one year).

Still, he desperately wanted to finish his paper before entering the army, so he spend most of that week-end going through the final version and submitted it on monday, as the published paper shows.

In the 70ties, Witt suddenly claimed he did discover the Leech lattice ${\Lambda}$ that sunday. Last time we have seen that the only written evidence for Witt’s claim is one sentence in his 1941-paper Eine Identität zwischen Modulformen zweiten Grades. “Bei dem Versuch, eine Form aus einer solchen Klassen wirklich anzugeben, fand ich mehr als 10 verschiedene Klassen in ${\Gamma_{24}}$.”

But then, why didn’t Witt include more details of this sensational lattice in his paper?

Ina Kersten recalls on page 328 of Witt’s collected papers : “In his colloquium talk “Gitter und Mathieu-Gruppen” in Hamburg on January 27, 1970, Witt said that in 1938, he had found nine lattices in ${\Gamma_{24}}$ and that later on January 28, 1940, while studying the Steiner system ${S(5,8,24)}$, he had found two additional lattices ${M}$ and ${\Lambda}$ in ${\Gamma_{24}}$. He continued saying that he had then given up the tedious investigation of ${\Gamma_{24}}$ because of the surprisingly low contribution

$\displaystyle | Aut(\Lambda) |^{-1} < 10^{-18}$

to the Minkowski density and that he had consented himself with a short note on page 324 in his 1941 paper.”

In the last sentence he refers to the fact that the sum of the inverse orders of the automorphism groups of all even unimodular lattices of a given dimension is a fixed rational number, the Minkowski-Siegel mass constant. In dimension 24 this constant is

$\displaystyle \sum_{L} \frac{1}{| Aut(L) |} = \frac {1027637932586061520960267}{129477933340026851560636148613120000000} \approx 7.937 \times 10^{-15}$

That is, Witt was disappointed by the low contribution of the Leech lattice to the total constant and concluded that there might be thousands of new even 24-dimensional unimodular lattices out there, and dropped the problem.

If true, the story gets even better : not only claims Witt to have found the lattices ${A_1^{24}=M}$ and ${\Lambda}$, but also enough information on the Leech lattice in order to compute the order of its automorphism group ${Aut(\Lambda)}$, aka the Conway group ${Co_0 = .0}$ the dotto-group!

Is this possible? Well fortunately, the difficulties one encounters when trying to compute the order of the automorphism group of the Leech lattice from scratch, is one of the better documented mathematical stories around.

The books From Error-Correcting Codes through Sphere Packings to Simple Groups by Thomas Thompson, Symmetry and the monster by Mark Ronan, and Finding moonshine by Marcus du Sautoy tell the story in minute detail.

It took John Conway 12 hours on a 1968 saturday in Cambridge to compute the order of the dotto group, using the knowledge of Leech and McKay on the properties of the Leech lattice and with considerable help offered by John Thompson via telephone.

But then, John Conway is one of the fastest mathematicians the world has known. The prologue of his book On numbers and games begins with : “Just over a quarter of a century ago, for seven consecutive days I sat down and typed from 8:30 am until midnight, with just an hour for lunch, and ever since have described this book as “having been written in a week”.”

Conway may have written a book in one week, Ernst Witt did complete his entire Ph.D. in just one week! In a letter of August 1933, his sister told her parents : “He did not have a thesis topic until July 1, and the thesis was to be submitted by July 7. He did not want to have a topic assigned to him, and when he finally had the idea, he started working day and night, and eventually managed to finish in time.”

So, if someone might have beaten John Conway in fast-computing the dottos order, it may very well have been Witt. Sadly enough, there is a lot of circumstantial evidence to make Witt’s claim highly unlikely.

For starters, psychology. Would you spend your last week-end together with your wife to be before going to war performing an horrendous calculation?

Secondly, mathematical breakthroughs often arise from newly found insight. At that time, Witt was also working on his paper on root lattices “Spiegelungsgrupen and Aufzähling halbeinfacher Liescher Ringe” which he eventually submitted in january 1941. Contained in that paper is what we know as Witt’s lemma which tells us that for any integral lattice the sublattice generated by vectors of norms 1 and 2 is a direct sum of root lattices.

This leads to the trick of trying to construct unimodular lattices by starting with a direct sum of root lattices and ‘adding glue’. Although this gluing-method was introduced by Kneser as late as 1967, Witt must have been aware of it as his 16-dimensional lattice ${D_{16}^+}$ is constructed this way.

If Witt wanted to construct new 24-dimensional even unimodular lattices in 1940, it would be natural for him to start off with direct sums of root lattices and trying to add vectors to them until he got what he was after. Now, all of the Niemeier-lattices are constructed this way, except for the Leech lattice!

I’m far from an expert on the Niemeier lattices but I would say that Witt definitely knew of the existence of ${D_{24}^+}$, ${E_8^3}$ and ${A_{24}^+}$ and that it is quite likely he also constructed ${(D_{16}E_8)^+, (D_{12}^2)^+, (A_{12}^2)^+, (D_8^3)^+}$ and possibly ${(A_{17}E_7)^+}$ and ${(A_{15}D_9)^+}$. I’d rate it far more likely Witt constructed another two such lattices on sunday january 28th 1940, rather than discovering the Leech lattice.

Finally, wouldn’t it be natural for him to include a remark, in his 1941 paper on root lattices, that not every even unimodular lattices can be obtained from sums of root lattices by adding glue, the Leech lattice being the minimal counter-example?

If it is true he was playing around with the Steiner systems that sunday, it would still be a pretty good story he discovered the lattices ${(A_2^{12})^+}$ and ${(A_1^{24})^+}$, for this would mean he discovered the Golay codes in the process!

Which brings us to our next question : who discovered the Golay code?

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$.”

Here’s a tiny problem illustrating our limited knowledge of finite fields : “Imagine an infinite queue of Knights ${ K_1,K_2,K_3,\ldots }$, waiting to be seated at the unit-circular table. The master of ceremony (that is, you) must give Knights $K_a$ and $K_b$ a place at an odd root of unity, say $\omega_a$ and $\omega_b$, such that the seat at the odd root of unity $\omega_a \times \omega_b$ must be given to the Knight $K_{a \otimes b}$, where $a \otimes b$ is the Nim-multiplication of $a$ and $b$. Which place would you offer to Knight $K_{16}$, or Knight $K_n$, or, if you’re into ordinals, Knight $K_{\omega}$?”

What does this have to do with finite fields? Well, consider the simplest of all finite field $\mathbb{F}_2 = { 0,1 }$ and consider its algebraic closure $\overline{\mathbb{F}_2}$. Last year, we’ve run a series starting here, identifying the field $\overline{\mathbb{F}_2}$, following John H. Conway in ONAG, with the set of all ordinals smaller than $\omega^{\omega^{\omega}}$, given the Nim addition and multiplication. I know that ordinal numbers may be intimidating at first, so let’s just restrict to ordinary natural numbers for now. The Nim-addition of two numbers $n \oplus m$ can be calculated by writing the numbers n and m in binary form and add them without carrying. For example, $9 \oplus 1 = 1001+1 = 1000 = 8$. Nim-multiplication is slightly more complicated and is best expressed using the so-called Fermat-powers $F_n = 2^{2^n}$. We then demand that $F_n \otimes m = F_n \times m$ whenever $m < F_n$ and $F_n \otimes F_n = \frac{3}{2}F_n$. Distributivity wrt. $\oplus$ can then be used to calculate arbitrary Nim-products. For example, $8 \otimes 3 = (4 \otimes 2) \otimes (2 \oplus 1) = (4 \otimes 3) \oplus (4 \otimes 2) = 12 \oplus 8 = 4$. Conway’s remarkable result asserts that the ordinal numbers, equipped with Nim addition and multiplication, form an algebraically closed field of characteristic two. The closure $\overline{\mathbb{F}_2}$ is identified with the subfield of all ordinals smaller than $\omega^{\omega^{\omega}}$. For those of you who don’t feel like going transfinite, the subfield $~(\mathbb{N},\oplus,\otimes)$ is identified with the quadratic closure of $\mathbb{F}_2$.

The connection between $\overline{\mathbb{F}_2}$ and the odd roots of unity has been advocated by Alain Connes in his talk before a general public at the IHES : “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). He describes its content briefly in this YouTube-video

At first it was unclear to me which ‘coupling-problem’ Alain meant, but this has been clarified in his paper together with Caterina Consani Characteristic one, entropy and the absolute point. The non-zero elements of $\overline{\mathbb{F}_2}$ can be identified with the set of all odd roots of unity. For, if x is such a unit, it belongs to a finite subfield of the form $\mathbb{F}_{2^n}$ for some n, and, as the group of units of any finite field is cyclic, x is an element of order $2^n-1$. Hence, $\mathbb{F}_{2^n}- { 0 }$ can be identified with the set of $2^n-1$-roots of unity, with $e^{2 \pi i/n}$ corresponding to a generator of the unit-group. So, all elements of $\overline{\mathbb{F}_2}$ correspond to an odd root of unity. The observation that we get indeed all odd roots of unity may take you a couple of seconds (( If m is odd, then (2,m)=1 and so 2 is a unit in the finite cyclic group $~(\mathbb{Z}/m\mathbb{Z})^*$ whence $2^n = 1 (mod~m)$, so the m-roots of unity lie within those of order $2^n-1$ )).

Assuming we succeed in fixing a one-to-one correspondence between the non-zero elements of $\overline{\mathbb{F}_2}$ and the odd roots of unity $\mu_{odd}$ respecting multiplication, how can we recover the addition on $\overline{\mathbb{F}_2}$? Well, here’s Alain’s coupling function, he ties up an element x of the algebraic closure to the element s(x)=x+1 (and as we are in characteristic two, this is an involution, so also the element tied up to x+1 is s(x+1)=(x+1)+1=x. The clue being that multiplication together with the coupling map s allows us to compute any sum of two elements as $x+y=x \times s(\frac{y}{x}) = x \times (\frac{y}{x}+1)$.
For example, all information about the finite field $\mathbb{F}_{2^4}$ is encoded in this identification with the 15-th roots of unity, together with the pairing s depicted as

Okay, we now have two identifications of the algebraic closure $\overline{\mathbb{F}_2}$ : the smaller ordinals equipped with Nim addition and Nim multiplication and the odd roots of unity with complex-multiplication and the Connes-coupling s. The question we started from asks for a general recipe to identify these two approaches.

To those of you who are convinced that finite fields (LOL, even characteristic two!) are objects far too trivial to bother thinking about : as far as I know, NOBODY knows how to do this explicitly, even restricting the ordinals to merely the natural numbers!

Please feel challenged! To get you started, I’ll show you how to place the first 15 Knights and give you a procedure (though far from explicit) to continue. Here’s the Nim-picture compatible with that above

To verify this, and to illustrate the general strategy, I’d better hand you the Nim-tables of the first 16 numbers. Here they are

It is known that the finite subfields of $~(\mathbb{N},\oplus,\otimes)$ are precisely the sets of numbers smaller than the Fermat-powers $F_n$. So, the first one is all numbers smaller than $F_1=4$ (check!). The smallest generator of the multiplicative group (of order 3) is 2, so we take this to correspond to the unit-root $e^{2 \pi i/3}$. The next subfield are all numbers smaller than $F_2 = 16$ and its multiplicative group has order 15. Now, choose the smallest integer k which generates this group, compatible with the condition that $k^{\otimes 5}=2$. Verify that this number is 4 and that this forces the identification and coupling given above.

The next finite subfield would consist of all natural numbers smaller than $F_3=256$. Hence, in this field we are looking for the smallest number k generating the multiplicative group of order 255 satisfying the extra condition that $k^{\otimes 17}=4$ which would fix an identification at that level. Then, the next level would be all numbers smaller than $F_4=65536$ and again we would like to find the smallest number generating the multiplicative group and such that the appropriate power is equal to the aforementioned k, etc. etc.

Can you give explicit (even inductive) formulae to achieve this? I guess even the problem of placing Knight 16 will give you a couple of hours to think about… (to be continued).

To mark the end of 2009 and 6 years of blogging, two musical compositions with a mathematical touch to them. I wish you all a better 2010!

Remember from last time that we identified Olivier Messiaen as the ‘Monsieur Modulo’ playing the musical organ at the Bourbaki wedding. This was based on the fact that his “modes à transposition limitée” are really about epimorphisms between modulo rings Z/12Z→Z/3Z and Z/12Z→Z/4Z.

However, Messiaen had more serious mathematical tricks up his sleeve. In two of his compositions he did discover (or at least used) one of the smaller sporadic groups, the Mathieu group $M_{12}$ of order 95040 on which we have based a whole series of Mathieu games two and a half years ago.

Messiaen’s ‘Ile de fey 2’ composition for piano (part of Quatre études de rythme (“Four studies in rhythm”), piano (1949–50)) is based on two concurrent permutations. The first is shown below, with the underlying motive rotational permutation shown.

This gives the permutation (1,7,10,2,6,4,5,9,11,12)(3,8). A second concurrent permutation is based on the permutation (1,6,9,2,7,3,5,4,8,10,11) and both of them generate the Mathieu group $M_{12}$. This can be seen by realizing the two permutations as the rotational permutations

and identifying them with the Mongean shuffles generating $M_{12}$. See for example, Dave Benson’s book “Music: A Mathematical Offering”, freely available online.

Clearly, Messiaen doesn’t use all of its 95040 permutations in his piece! Here’s how it sounds. The piece starts 2 minutes into the clip.

The second piece is “Les Yeux dans les Roues” (The Eyes in the Wheels), sixth piece from the “Livre d’Orgue” (1950/51).

According to Hauptwerk, the piece consists of a melody/theme in the pedal, accompanied by two fast-paced homorhythmic lines in the manuals. The pedal presents a sons-durées theme which is repeated six times, in different permutations. Initially it is presented in its natural form. Afterwards, it is presented alternatively picking notes from each end of the original form. Similar transformations are applied each time until the sixth, which is the retrograde of the first. The entire twelve-tone analysis (pitch only, not rhythm) of the pedal is shown below:

That is we get the following five permutations which again generate Mathieu 12 :

• a=(2,3,5,9,8,10,6,11,4,7,12)
• b=(1,2,4,8,9,7,11,3,6,12)(5,10)=e*a
• c=(1,12,11,9,5,4,6,2,10,7)(3,8)=e*d
• d=(1,11,10,8,4,5,3,7,2,9,6)
• e=(1,12)(2,11)(3,10)(4,9)(5,8)(6,7)

Here’s the piece performed on organ :

Considering the permutations $X=d.a^{-1}$ and $Y=(a.d^2.a.d^3)^{-1}$ one obtains canonical generators of $M_{12}$, that is, generators satisfying the defining equations of this sporadic group

$X^2=Y^3=(XY)^{11}=[X,Y]^6=(XYXYXY^{-1})^6=1$

I leave you to work out the corresponding dessin d’enfant tonight after a couple of glasses of champagne! It sure has a nice form. Once again, a better 2010!

Over the week-end I read The artist and the mathematician (subtitle : The story of Nicolas Bourbaki, the genius mathematician who never existed) by Amir D. Aczel.

Whereas the central character of the book should be Bourbaki, it focusses more on two of Bourbaki’s most colorful members, André Weil and Alexander Grothendieck, and the many stories and myths surrounding them.

The opening chapter (‘The Disappearance’) describes the Grothendieck’s early years (based on the excellent paper by Allyn Jackson Comme Appelé du Néant ) and his disappearance in the Pyrenees in the final years of last century. The next chapter (‘An Arrest in Finland’) recount the pre-WW2 years of Weil and the myth of his arrest in Finland and his near escape from execution (based on Weil’s memoires The Apprenticeship of a Mathematician). Chapter seven (‘The Café’) describes the first 10 proto-Bourbaki meetings following closely the study ‘A Parisian Café and Ten Proto-Bourbaki Meetings (1934-1935)‘ by Liliane Beaulieu. Etc. etc.

All the good ‘Bourbaki’-stories get a place in this book, not always historically correct. For example, on page 90 it is suggested that all of the following jokes were pulled at the Besse-conference, July 1935 : the baptizing of Nicolas, the writing of the Comptes-Rendus paper, the invention of the Bourbaki-daughter Betti and the printing of the wedding invitation card. In reality, all of these date from much later, the first two from the autumn of 1935, the final two no sooner than april 1939…

One thing I like about this book is the connection it makes with other disciplines, showing the influence of Bourbaki’s insistence on ‘structuralism’ in fields as different as philosophy, linguistics, anthropology and literary criticism. One example being Weil’s group-theoretic solution to the marriage-rules problem in tribes of Australian aborigines studied by Claude Lévi-Strauss, another the literary group Oulipo copying Bourbaki’s work-method.

Another interesting part is Aczel’s analysis of Bourbaki’s end. In the late 50ties, Grothendieck tried to convince his fellow Bourbakis to redo their work on the foundations of mathematics, changing these from set theory to category theory. He failed as others felt that the foundations had already been laid and there was no going back. Grothendieck left, and Bourbaki would gradually decline following its refusal to accept new methods. In Grothendieck’s own words (in “Promenade” 63, n. 78, as translated by Aczel) :

“Additionally, since the 1950s, the idea of structure has become passé, superseded by the influx of new ‘categorical’ methods in certain of the most dynamical areas of mathematics, such as topology or algebraic geometry. (Thus, the notion of ‘topos’ refuses to enter into the ‘Bourbaki sack’ os structures, decidedly already too full!) In making this decision, in full cognizance, not to engage in this revision, Bourbaki has itself renounced its initial ambition, which has been to furnish both the foundations and the basic language for all of modern mathematics.”

Finally, it is interesting to watch Aczel’s own transformation throughout the book, from slavishly copying the existing Weil-myths and pranks at the beginning of the book, to the following harsh criticism on Weil, towards the end (p. 209) :

“From other information in his autobiography, one gets the distinct impression that Weil was infatuated with the childish pranks of ‘inventing’ a person who never existed, creating for him false papers and a false identity, complete with a daughter, Betti, who even gets married, parents and relatives, and membership in a nonexistent Academy of Sciences of the nonexistent nation of Polvedia (sic).
Weil was so taken with these activities that he even listed, as his only honor by the time of his death ‘Member, Poldevian Academy of Sciences’. It seems that Weil could simply not go beyond these games: he could not grasp the deep significance and power of the organization he helped found. He was too close, and thus unable to see the great achievements Bourbaki was producing and to acknowledge and promote these achievements. Bourbaki changed the way we do mathematics, but Weil really saw only the pranks and the creation of a nonexistent person.”

Judging from my own reluctance to continue with the series on the Bourbaki code, an overdose reading about Weil’s life appears to have this effect on people…

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!

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.