the Reddit (after)effect

Sunday january 2nd around 18hr NeB-stats went crazy.

Referrals clarified that the post ‘What is the knot associated to a prime?’ was picked up at Reddit/math and remained nr.1 for about a day.

Now, the dust has settled, so let’s learn from the experience.

A Reddit-mention is to a blog what doping is to a sporter.

You get an immediate boost in the most competitive of all blog-stats, the number of unique vistors (blue graph), but is doesn’t result in a long-term effect, and, it may even be harmful to more essential blog-stats, such as the average time visitors spend on your site (yellow graph).

For NeB the unique vistors/day fluctuate normally around 300, but peaked to 1295 and 1733 on the ‘Reddit-days’. In contrast, the avg. time on site is normally around 3 minutes, but dropped the same days to 44 and 30 seconds!

Whereas some of the Reddits spend enough time to read the post and comment on it, the vast majority zap from one link to the next. Having monitored the Reddit/math page for two weeks, I’m convinced that post only made it because it was visually pretty good. The average Reddit/math-er is a viewer more than a reader…

So, should I go for shorter, snappier, more visual posts?

Let’s compare Reddits to those coming from the three sites giving NeB most referrals : Google search, MathOverflow and Wikipedia.

This is the traffic coming from Reddit/math, as always the blue graph are the unique visitors, the yellow graph their average time on site, blue-scales to the left, yellow-scales to the right.

Here’s the same graph for Google search. The unique visitors/day fluctuate around 50 and their average time on site about 2 minutes.

The math-related search terms most used were this month : ‘functor of point approach’, ‘profinite integers’ and ‘bost-connes sytem’.

More rewarding to me are referrals from MathOverflow.

The number of visitors depends on whether the MathO-questions made it to the front-page (for example, the 80 visits on december 15, came from the What are dessins d’enfants?-topic getting an extra comment that very day, and having two references to NeB-posts : The best rejected proposal ever and Klein’s dessins d’enfant and the buckyball), but even older MathO-topics give a few referrals a day, and these people sure take their time reading the posts (+ 5 minutes).

Other MathO-topics giving referrals this month were Most intricate and most beautiful structures in mathematics (linking to Looking for F-un), What should be learned in a first serious schemes course? (linking to Mumford’s treasure map (btw. one of the most visited NeB-posts ever)), How much of scheme theory can you visualize? (linking again to Mumford’s treasure map) and Approaches to Riemann hypothesis using methods outside number theory (linking to the Bost-Connes series).

Finally, there’s Wikipedia

giving 5 to 10 referrals a day, with a pretty good time-on-site average (around 4 minutes, peaking to 12 minutes). It is rewarding to see NeB-posts referred to in as diverse Wikipedia-topics as ‘Fifteen puzzle’, ‘Field with one element’, ‘Evariste Galois’, ‘ADE classification’, ‘Monster group’, ‘Arithmetic topology’, ‘Dessin d’enfant’, ‘Groupoid’, ‘Belyi’s theorem’, ‘Modular group’, ‘Cubic surface’, ‘Esquisse d’un programme’, ‘N-puzzle’, ‘Shabat polynomial’ and ‘Mathieu group’.

What lesson should be learned from all this data? Should I go for shorter, snappier and more visual posts, or should I focus on the small group of visitors taking their time reading through a longer post, and don’t care about the appallingly high bounce rate the others cause?

Langlands versus Connes

This is a belated response to a Math-Overflow exchange between Thomas Riepe and Chandan Singh Dalawat asking for a possible connection between Connes’ noncommutative geometry approach to the Riemann hypothesis and the Langlands program.

Here’s the punchline : a large chunk of the Connes-Marcolli book Noncommutative Geometry, Quantum Fields and Motives can be read as an exploration of the noncommutative boundary to the Langlands program (at least for $GL_1 $ and $GL_2 $ over the rationals $\mathbb{Q} $).

Recall that Langlands for $GL_1 $ over the rationals is the correspondence, given by the Artin reciprocity law, between on the one hand the abelianized absolute Galois group

$Gal(\overline{\mathbb{Q}}/\mathbb{Q})^{ab} = Gal(\mathbb{Q}(\mu_{\infty})/\mathbb{Q}) \simeq \hat{\mathbb{Z}}^* $

and on the other hand the connected components of the idele classes

$\mathbb{A}^{\ast}_{\mathbb{Q}}/\mathbb{Q}^{\ast} = \mathbb{R}^{\ast}_{+} \times \hat{\mathbb{Z}}^{\ast} $

The locally compact Abelian group of idele classes can be viewed as the nice locus of the horrible quotient space of adele classes $\mathbb{A}_{\mathbb{Q}}/\mathbb{Q}^{\ast} $. There is a well-defined map

$\mathbb{A}_{\mathbb{Q}}’/\mathbb{Q}^{\ast} \rightarrow \mathbb{R}_{+} \qquad (x_{\infty},x_2,x_3,\ldots) \mapsto | x_{\infty} | \prod | x_p |_p $

from the subset $\mathbb{A}_{\mathbb{Q}}’ $ consisting of adeles of which almost all terms belong to $\mathbb{Z}_p^{\ast} $. The inverse image of this map over $\mathbb{R}_+^{\ast} $ are precisely the idele classes $\mathbb{A}^{\ast}_{\mathbb{Q}}/\mathbb{Q}^{\ast} $. In this way one can view the adele classes as a closure, or ‘compactification’, of the idele classes.

This is somewhat reminiscent of extending the nice action of the modular group on the upper-half plane to its badly behaved action on the boundary as in the Manin-Marcolli cave post.

The topological properties of the fiber over zero, and indeed of the total space of adele classes, are horrible in the sense that the discrete group $\mathbb{Q}^* $ acts ergodically on it, due to the irrationality of $log(p_1)/log(p_2) $ for primes $p_i $. All this is explained well (in the semi-local case, that is using $\mathbb{A}_Q’ $ above) in the Connes-Marcolli book (section 2.7).

In much the same spirit as non-free actions of reductive groups on algebraic varieties are best handled using stacks, such ergodic actions are best handled by the tools of noncommutative geometry. That is, one tries to get at the geometry of $\mathbb{A}_{\mathbb{Q}}/\mathbb{Q}^{\ast} $ by studying an associated non-commutative algebra, the skew-ring extension of the group-ring of the adeles by the action of $\mathbb{Q}^* $ on it. This algebra is known to be Morita equivalent to the Bost-Connes algebra which is the algebra featuring in Connes’ approach to the Riemann hypothesis.

It shouldn’t thus come as a major surprise that one is able to recover the other side of the Langlands correspondence, that is the Galois group $Gal(\mathbb{Q}(\mu_{\infty})/\mathbb{Q}) $, from the Bost-Connes algebra as the symmetries of certain states.

In a similar vein one can read the Connes-Marcolli $GL_2 $-system (section 3.7 of their book) as an exploration of the noncommutative closure of the Langlands-space $GL_2(\mathbb{A}_{\mathbb{Q}})/GL_2(\mathbb{Q}) $.

At the moment I’m running a master-seminar noncommutative geometry trying to explain this connection in detail. But, we’re still in the early phases, struggling with the topology of ideles and adeles, reciprocity laws, L-functions and the lot. Still, if someone is interested I might attempt to post some lecture notes here.

Seating the first few thousand Knights

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

big Witt vectors for everyone (1/2)

Next time you visit your math-library, please have a look whether these books are still on the shelves : Michiel Hazewinkel‘s Formal groups and applications, William Fulton’s and Serge Lange’s Riemann-Roch algebra and Donald Knutson’s lambda-rings and the representation theory of the symmetric group.

I wouldn’t be surprised if one or more of these books are borrowed out, probably all of them to the same person. I’m afraid I’m that person in Antwerp…

Lately, there’s been a renewed interest in $\lambda $-rings and the endo-functor W assigning to a commutative algebra its ring of big Witt vectors, following Borger’s new proposal for a geometry over the absolute point.

However, as Hendrik Lenstra writes in his 2002 course-notes on the subject Construction of the ring of Witt vectors : “The literature on the functor W is in a somewhat unsatisfactory state: nobody seems to have any interest in Witt vectors beyond applying them for a purpose, and they are often treated in appendices to papers devoting to something else; also, the construction usually depends on a set of implicit or unintelligible formulae. Apparently, anybody who wishes to understand Witt vectors needs to construct them personally. That is what is now happening to myself.”

Before doing a series on Borger’s paper, we’d better run through Lenstra’s elegant construction in a couple of posts. Let A be a commutative ring and consider the multiplicative group of all ‘one-power series’ over it $\Lambda(A)=1+t A[[t]] $. Our aim is to define a commutative ring structure on $\Lambda(A) $ taking as its ADDITION the MULTIPLICATION of power series.

That is, if $u(t),v(t) \in \Lambda(A) $, then we define our addition $u(t) \oplus v(t) = u(t) \times v(t) $. This may be slightly confusing as the ZERO-element in $\Lambda(A),\oplus $ will then turn be the constant power series 1…

We are now going to define a multiplication $\otimes $ on $\Lambda(A) $ which is distributively with respect to $\oplus $ and turns $\Lambda(A) $ into a commutative ring with ONE-element the series $~(1-t)^{-1}=1+t+t^2+t^3+\ldots $.

We will do this inductively, so consider $\Lambda_n(A) $ the (classes of) one-power series truncated at term n, that is, the kernel of the natural augmentation map between the multiplicative group-units $~A[t]/(t^{n+1})^* \rightarrow A^* $.
Again, taking multiplication in $A[t]/(t^{n+1}) $ as a new addition rule $\oplus $, we see that $~(\Lambda_n(A),\oplus) $ is an Abelian group, whence a $\mathbb{Z} $-module.

For all elements $a \in A $ we have a scaling operator $\phi_a $ (sending $t \rightarrow at $) which is an A-ring endomorphism of $A[t]/(t^{n+1}) $, in particular multiplicative wrt. $\times $. But then, $\phi_a $ is an additive endomorphism of $~(\Lambda_n(A),\oplus) $, so is an element of the endomorphism-RING $End_{\mathbb{Z}}(\Lambda_n(A)) $. Because composition (being the multiplication in this endomorphism ring) of scaling operators is clearly commutative ($\phi_a \circ \phi_b = \phi_{ab} $) we can define a commutative RING $E $ being the subring of $End_{\mathbb{Z}}(\Lambda_n(A)) $ generated by the operators $\phi_a $.

The action turns $~(\Lambda_n(A),\oplus) $ into an E-module and we define an E-module morphism $E \rightarrow \Lambda_n(A) $ by $\phi_a \mapsto \phi_a((1-t)^{-1}) = (1-at)^{-a} $.

All of this looks pretty harmless, but the upshot is that we have now equipped the image of this E-module morphism, say $L_n(A) $ (which is the additive subgroup of $~(\Lambda_n(A),\oplus) $ generated by the elements $~(1-at)^{-1} $) with a commutative multiplication $\otimes $ induced by the rule $~(1-at)^{-1} \otimes (1-bt)^{-1} = (1-abt)^{-1} $.

Explicitly, $L_n(A) $ is the set of one-truncated polynomials $u(t) $ with coefficients in $A $ such that one can find elements $a_1,\ldots,a_k \in A $ such that $u(t) \equiv (1-a_1t)^{-1} \times \ldots \times (1-a_k)^{-1}~mod~t^{n+1} $. We multiply $u(t) $ with another such truncated one-polynomial $v(t) $ (taking elements $b_1,b_2,\ldots,b_l \in A $) via

$u(t) \otimes v(t) = ((1-a_1t)^{-1} \oplus \ldots \oplus (1-a_k)^{-1}) \otimes ((1-b_1t)^{-1} \oplus \ldots \oplus (1-b_l)^{-1}) $

and using distributivity and the multiplication rule this gives the element $\prod_{i,j} (1-a_ib_jt)^{-1}~mod~t^{n+1} \in L_n(A) $.
Being a ring-qutient of $E $ we have that $~(L_n(A),\oplus,\otimes) $ is a commutative ring, and, from the construction it is clear that $L_n $ behaves functorially.

For rings $A $ such that $L_n(A)=\Lambda_n(A) $ we are done, but in general $L_n(A) $ may be strictly smaller. The idea is to use functoriality and do the relevant calculations in a larger ring $A \subset B $ where we can multiply the two truncated one-polynomials and observe that the resulting truncated polynomial still has all its coefficients in $A $.

Here’s how we would do this over $\mathbb{Z} $ : take two irreducible one-polynomials u(t) and v(t) of degrees r resp. s smaller or equal to n. Then over the complex numbers we have
$u(t)=(1-\alpha_1t) \ldots (1-\alpha_rt) $ and $v(t)=(1-\beta_1) \ldots (1-\beta_st) $. Then, over the field $K=\mathbb{Q}(\alpha_1,\ldots,\alpha_r,\beta_1,\ldots,\beta_s) $ we have that $u(t),v(t) \in L_n(K) $ and hence we can compute their product $u(t) \otimes v(t) $ as before to be $\prod_{i,j}(1-\alpha_i\beta_jt)^{-1}~mod~t^{n+1} $. But then, all coefficients of this truncated K-polynomial are invariant under all permutations of the roots $\alpha_i $ and the roots $\beta_j $ and so is invariant under all elements of the Galois group. But then, these coefficients are algebraic numbers in $\mathbb{Q} $ whence integers. That is, $u(t) \otimes v(t) \in \Lambda_n(\mathbb{Z}) $. It should already be clear from this that the rings $\Lambda_n(\mathbb{Z}) $ contain a lot of arithmetic information!

For a general commutative ring $A $ we will copy this argument by considering a free overring $A^{(\infty)} $ (with 1 as one of the base elements) by formally adjoining roots. At level 1, consider $M_0 $ to be the set of all non-constant one-polynomials over $A $ and consider the ring

$A^{(1)} = \bigotimes_{f \in M_0} A[X]/(f) = A[X_f, f \in M_0]/(f(X_f) , f \in M_0) $

The idea being that every one-polynomial $f \in M_0 $ now has one root, namely $\alpha_f = \overline{X_f} $ in $A^{(1)} $. Further, $A^{(1)} $ is a free A-module with basis elements all $\alpha_f^i $ with $0 \leq i < deg(f) $.

Good! We now have at least one root, but we can continue this process. At level 2, $M_1 $ will be the set of all non-constant one-polynomials over $A^{(1)} $ and we use them to construct the free overring $A^{(2)} $ (which now has the property that every $f \in M_0 $ has at least two roots in $A^{(2)} $). And, again, we repeat this process and obtain in succession the rings $A^{(3)},A^{(4)},\ldots $. Finally, we define $A^{(\infty)} = \underset{\rightarrow}{lim}~A^{(i)} $ having the property that every one-polynomial over A splits entirely in linear factors over $A^{(\infty)} $.

But then, for all $u(t),v(t) \in \Lambda_n(A) $ we can compute $u(t) \otimes v(t) \in \Lambda_n(A^{(\infty)}) $. Remains to show that the resulting truncated one-polynomial has all its entries in A. The ring $A^{(\infty)} \otimes_A A^{(\infty)} $ contains two copies of $A^{(\infty)} $ namely $A^{(\infty)} \otimes 1 $ and $1 \otimes A^{(\infty)} $ and the intersection of these two rings in exactly $A $ (here we use the freeness property and the additional fact that 1 is one of the base elements). But then, by functoriality of $L_n $, the element
$u(t) \otimes v(t) \in L_n(A^{(\infty)} \otimes_A A^{(\infty)}) $ lies in the intersection $\Lambda_n(A^{(\infty)} \otimes 1) \cap \Lambda_n(1 \otimes A^{(\infty)})=\Lambda_n(A) $. Done!

Hence, we have endo-functors $\Lambda_n $ in the category of all commutative rings, for every number n. Reviewing the construction of $L_n $ one observes that there are natural transformations $L_{n+1} \rightarrow L_n $ and therefore also natural transformations $\Lambda_{n+1} \rightarrow \Lambda_n $. Taking the inverse limits $\Lambda(A) = \underset{\leftarrow}{lim} \Lambda_n(A) $ we therefore have the ‘one-power series’ endo-functor
$\Lambda~:~\mathbf{comm} \rightarrow \mathbf{comm} $
which is ‘almost’ the functor W of big Witt vectors. Next time we’ll take you through the identification using ‘ghost variables’ and how the functor $\Lambda $ can be used to define the category of $\lambda $-rings.

The odd knights of the round table

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).

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 ($\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.