Category: number theory

Quiver Grassmannians and $\mathbb{F}_1$-geometry

Published May 9, 2012 by lievenlb

Reineke’s observation that any projective variety can be realized as a quiver Grassmannian is bad news: we will have to look at special representations and/or dimension vectors if we want the Grassmannian to have desirable properties. Some people still see a silver lining: it can be used to define a larger class of geometric objects over the elusive field with one element $\mathbb{F}_1$.

In a comment to the previous post Markus Reineke recalls motivating discussions with Javier Lopez Pena and Oliver Lorscheid (the guys responsable for the map of $\mathbb{F}_1$-land above) and asks about potential connections with $\mathbb{F}_1$-geometry. In this post I will ellaborate on Javier’s response.

The Kapranov-Smirnov $\mathbb{F}_1$-floklore tells us that an $n$-dimensional vectorspace over $\mathbb{F}_1$ is a pointed set $V^{\bullet}$ consisting of $n+1$ points, the distinguished point playing the role of the zero-vector. Linear maps $V^{\bullet} \rightarrow W^{\bullet}$ between $\mathbb{F}_1$-spaces are then just maps of pointed sets (sending the distinguished element of $V^{\bullet}$ to that of $W^{\bullet}$). As an example, the base-change group $GL_n(\mathbb{F}_1)$ of an $n$-dimensional $\mathbb{F}_1$-space $V^{\bullet}$ is isomorphic to the symmetric group $S_n$.

This allows us to make sense of quiver-representations over $\mathbb{F}_1$. To each vertex we associate a pointed set and to each arrow a map of pointed sets between the vertex-pointed sets. The dimension-vector $\alpha$ of quiver-representation is defined as before and two representations with the same dimension-vector are isomorphic is they lie in the same orbit under the action of the product of the symmetric groups determined by the components of $\alpha$. All this (and a bit more) has been worked out by Matt Szczesny in the paper Representations of quivers over $\mathbb{F}_1$.

Oliver Lorscheid developed his own approach to $\mathbb{F}_1$ based on the notion of blueprints (see also part 2 and a paper with Javier).

Roughly speaking a blueprint $B = A // \mathcal{R}$ is a commutative monoid $A$ together with an equivalence relation $\mathcal{R}$ on the monoid semiring $\mathbb{N}[A]$ compatible with addition and multiplication. Any commutative ring $R$ is a blueprint by taking $A$ the multiplicative monoid of $R$ and $\mathcal{R}(\sum_i a_i,\sum_j b_j)$ if and only if the elements $\sum_i a_i$ and $\sum_j b_j$ in $R$ are equal.

One can extend the usual notions of prime ideals, Zariski topology and structure sheaf from commutative rings to blueprints and hence define a notion of “blue schemes” which are then taken to be the schemes over $\mathbb{F}_1$.

What’s the connection with Reineke’s result? Well, for quiver-representations $V$ defined over $\mathbb{F}_1$ they can show that the corresponding quiver Grassmannians $Gr(V,\alpha)$ are blue projective varieties and hence are geometric objects defined over $\mathbb{F}_1$.

For us, old-fashioned representation theorists, a complex quiver-representation $V$ is defined over $\mathbb{F}_1$ if and only if there is an isomorphic representation $V’$ with the property that all its arrow-matrices have at most one $1$ in every column, and zeroes elsewhere.

Remember from last time that Reineke’s representation consisted of two parts : the Veronese-part encoding the $d$-uple embedding $\mathbb{P}^n \rightarrow \mathbb{P}^M$ and a linear part describing the subvariety $X \rightarrow \mathbb{P}^n$ as the intersection of the image of $\mathbb{P}^n$ in $\mathbb{P}^M$ with a finite number of hyper-planes in $\mathbb{P}^M$.

We have seen that the Veronese-part is always defined over $\mathbb{F}_1$, compatible with the fact that all approaches to $\mathbb{F}_1$-geometry allow for projective spaces and $d$-uple embeddings. The linear part does not have to be defined over $\mathbb{F}_1$ in general, but we can look at the varieties we get when we force the linear-part matrices to be of the correct form.

For example, by modifying the map $h$ of last time to $h=x_0+x_7+x_9$ we get that the quiver-representation

is defined over $\mathbb{F}_1$ and hence that Reineke’s associated quiver Grassmannian, which is the smooth plane elliptic curve $\mathbb{V}(x^3+y^2z+z^3)$, is a blue variety. This in sharp contrast with other approaches to $\mathbb{F}_1$-geometry which do not allow elliptic curves!

Oliver will give a talk at the 6th European Congress of Mathematics in the mini-symposium Absolute Arithmetic and $\mathbb{F}_1$-Geometry. Judging from his abstract,he will also mention quiver Grassmannians.

Leave a Comment

Seating the first few billion Knights

Published December 30, 2010 by lievenlb

The odd Knight of the round table problem asks for a consistent placement of the n-th Knight in the row 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’ in ONAG to define an addition and multiplication on the set of all ordinal numbers.

Here’s the seating arrangement for the first 15 knights. Conway proved that all finite ordinals smaller than $2^{2^i} $ form a subfield of $\overline{\mathbb{F}}_2 $. The first non-trivial one being $\{ 0,1,2,3 \} $ with smallest multiplicative generator $2 $, whence we place Knight 2 at $e^{2 i \pi/3} $ and as $2^2=3 $ we know where to place the third Knight.

The next subfield is made of the numbers $\{ 0,1,2,\ldots,13,14,15 \} $ and its non-zero numbers form a cyclic group of order 15. Hence we need to find the smallest generator of this group satisfying the additional property of being compatible with the earlier seating, that is, its fifth power must equal to 2. Checking the multiplication table reproduced here one verifies that the wanted generator is 4 and so we place Knight 4 at $e^{\frac{2 \pi i}{15}} $ and as all the ordinals smaller than 16 are powers of 4 this tells us where to place the Knights until we get to the 15th in the row.

In february we were able to seat the first few thousand Knights by showing by hand that 32 is the smallest ordinal such that its 15-th power is equal to 4 and using SAGE that 1051 is the smallest ordinal whose 257-th power equals 32. These calculations enabled us to seat the Knights until we get to the 65536-th in the row.

Today I managed to show that 1361923 is the smallest ordinal such that its 65537-th power equals 1051. You can verify this statement in SAGE using the method explained in the february post

sage: R.< x,y,z,t,u >=GF(2)[]

sage: S.< a,b,c,d,e > =
R.quotient((x^2+x+1,y^2+y+x,z^2+z+x*y,t^2+t+x*y*z,u^2+u+x*y*z*t))

sage: (c*e+b*e+a*b*c*d+b*c*d+a*b*d+a+1)^65537
c^2 + b*d + a + 1

(It takes a bit longer to check minimality of 1361923). That is, we have to seat Knight 1361923 at $e^{\frac{2 \pi i}{4294967295}} $ and because all the numbers smaller than 4294967296 are powers of 1361923 we have seating arrangements for the first 4294967295 Knights!

I did try the same method in february but ran into time- and memory-problems on my 2.4Ghz 2Gb MacBook. Today I upgraded from Sage 3.3 to Sage 4.6 and this version is a lot faster (using the 64-bit architecture) and also appears to be much better at memory-management. Thank you, Sage-community!

Wishing you all a lot of mathematical (and other) fun in the prime-number year 2011.

atb :: lieven.

One Comment

Langlands versus Connes

Published October 26, 2010 by lievenlb

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.

6 Comments

Lambda-rings for formula-phobics

Published February 5, 2010 by lievenlb

In 1956, Alexander Grothendieck (middle) introduced $\lambda $-rings in an algebraic-geometric context to be commutative rings A equipped with a bunch of operations $\lambda^i $ (for all numbers $i \in \mathbb{N}_+ $) satisfying a list of rather obscure identities. From the easier ones, such as

$\lambda^0(x)=1, \lambda^1(x)=x, \lambda^n(x+y) = \sum_i \lambda^i(x) \lambda^{n-i}(y) $

to those expressing $\lambda^n(x.y) $ and $\lambda^m(\lambda^n(x)) $ via specific universal polynomials. An attempt to capture the essence of $\lambda $-rings without formulas?

Lenstra’s elegant construction of the 1-power series rings $~(\Lambda(A),\oplus,\otimes) $ requires only one identity to remember

$~(1-at)^{-1} \otimes (1-bt)^{-1} = (1-abt)^{-1} $.

Still, one can use it to show the existence of ringmorphisms $\gamma_n~:~\Lambda(A) \rightarrow A $, for all numbers $n \in \mathbb{N}_+ $. Consider the formal ‘logarithmic derivative’

$\gamma = \frac{t u(t)’}{u(t)} = \sum_{i=1}^\infty \gamma_i(u(t))t^i~:~\Lambda(A) \rightarrow A[[t]] $

where $u(t)’ $ is the usual formal derivative of a power series. As this derivative satisfies the chain rule, we have

$\gamma(u(t) \oplus v(t)) = \frac{t (u(t)v(t))’}{u(t)v(t)} = \frac{t(u(t)’v(t)+u(t)v(t)’}{u(t)v(t))} = \frac{tu(t)’}{u(t)} + \frac{tv(t)’}{v(t)} = \gamma(u(t)) + \gamma(v(t)) $

and so all the maps $\gamma_n~:~\Lambda(A) \rightarrow A $ are additive. To show that they are also multiplicative, it suffices by functoriality to verify this on the special 1-series $~(1-at)^{-1} $ for all $a \in A $. But,

$\gamma((1-at)^{-1}) = \frac{t \frac{a}{(1-at)^2}}{(1-at)} = \frac{at}{(1-at)} = at + a^2t^2 + a^3t^3+\ldots $

That is, $\gamma_n((1-at)^{-1}) = a^n $ and Lenstra’s identity implies that $\gamma_n $ is indeed multiplicative! A first attempt :

hassle-free definition 1 : a commutative ring $A $ is a $\lambda $-ring if and only if there is a ringmorphism $s_A~:~A \rightarrow \Lambda(A) $ splitting $\gamma_1 $, that is, such that $\gamma_1 \circ s_A = id_A $.

In particular, a $\lambda $-ring comes equipped with a multiplicative set of ring-endomorphisms $s_n = \gamma_n \circ s_A~:~A \rightarrow A $ satisfying $s_m \circ s_m = s_{mn} $. One can then define a $\lambda $-ringmorphism to be a ringmorphism commuting with these endo-morphisms.

The motivation being that $\lambda $-rings are known to form a subcategory of commutative rings for which the 1-power series functor is the right adjoint to the functor forgetting the $\lambda $-structure. In particular, if $A $ is a $\lambda $-ring, we have a ringmorphism $A \rightarrow \Lambda(A) $ corresponding to the identity morphism.

But then, what is the connection to the usual one involving all the operations $\lambda^i $? Well, one ought to recover those from $s_A(a) = (1-\lambda^1(a)t+\lambda^2(a)t^2-\lambda^3(a)t^3+…)^{-1} $.

For $s_A $ to be a ringmorphism will require identities among the $\lambda^i $. I hope an expert will correct me on this one, but I’d guess we won’t yet obtain all identities required. By the very definition of an adjoint we must have that $s_A $ is a morphism of $\lambda $-rings, and, this would require defining a $\lambda $-ring structure on $\Lambda(A) $, that is a ringmorphism $s_{AH}~:~\Lambda(A) \rightarrow \Lambda(\Lambda(A)) $, the so called Artin-Hasse exponential, to which I’d like to return later.

For now, we can define a multiplicative set of ring-endomorphisms $f_n~:~\Lambda(A) \rightarrow \Lambda(A) $ from requiring that $f_n((1-at)^{-1}) = (1-a^nt)^{-1} $ for all $a \in A $. Another try?

hassle-free definition 2 : $A $ is a $\lambda $-ring if and only if there is splitting $s_A $ to $\gamma_1 $ satisfying the compatibility relations $f_n \circ s_A = s_A \circ s_n $.

But even then, checking that a map $s_A~:~A \rightarrow \Lambda(A) $ is a ringmorphism is as hard as verifying the lists of identities among the $\lambda^i $. Fortunately, we get such a ringmorphism for free in the important case when A is of ‘characteristic zero’, that is, has no additive torsion. Then, a ringmorphism $A \rightarrow \Lambda(A) $ exists whenever we have a multiplicative set of ring endomorphisms $F_n~:~A \rightarrow A $ for all $n \in \mathbb{N}_+ $ such that for every prime number $p $ the morphism $F_p $ is a lift of the Frobenius, that is, $F_p(a) \in a^p + pA $.

Perhaps this captures the essence of $\lambda $-rings best (without the risk of getting an headache) : in characteristic zero, they are the (commutative) rings having a multiplicative set of endomorphisms, generated by lifts of the Frobenius maps.

2 Comments

Seating the first few thousand Knights

Published February 3, 2010 by lievenlb

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

2 Comments

Conway’s big picture

Published May 2, 2009 by lievenlb

Conway and Norton showed that there are exactly 171 moonshine functions and associated two arithmetic subgroups to them. We want a tool to describe these and here’s where Conway’s big picture comes in very handy. All moonshine groups are arithmetic groups, that is, they are commensurable with the modular group. Conway’s idea is to view several of these groups as point- or set-wise stabilizer subgroups of finite sets of (projective) commensurable 2-dimensional lattices.

Expanding (and partially explaining) the original moonshine observation of McKay and Thompson, John Conway and Simon Norton formulated monstrous moonshine :

To every cyclic subgroup $\langle m \rangle $ of the Monster $\mathbb{M} $ is associated a function

$f_m(\tau)=\frac{1}{q}+a_1q+a_2q^2+\ldots $ with $q=e^{2 \pi i \tau} $ and all coefficients $a_i \in \mathbb{Z} $ are characters at $m $ of a representation of $\mathbb{M} $. These representations are the homogeneous components of the so called Moonshine module.

Each $f_m $ is a principal modulus for a certain genus zero congruence group commensurable with the modular group $\Gamma = PSL_2(\mathbb{Z}) $. These groups are called the moonshine groups.

Conway and Norton showed that there are exactly 171 different functions $f_m $ and associated two arithmetic subgroups $F(m) \subset E(m) \subset PSL_2(\mathbb{R}) $ to them (in most cases, but not all, these two groups coincide).

Whereas there is an extensive literature on subgroups of the modular group (see for instance the series of posts starting here), most moonshine groups are not contained in the modular group. So, we need a tool to describe them and here’s where Conway’s big picture comes in very handy.

All moonshine groups are arithmetic groups, that is, they are subgroups $G $ of $PSL_2(\mathbb{R}) $ which are commensurable with the modular group $\Gamma = PSL_2(\mathbb{Z}) $ meaning that the intersection $G \cap \Gamma $ is of finite index in both $G $ and in $\Gamma $. Conway’s idea is to view several of these groups as point- or set-wise stabilizer subgroups of finite sets of (projective) commensurable 2-dimensional lattices.

Start with a fixed two dimensional lattice $L_1 = \mathbb{Z} e_1 + \mathbb{Z} e_2 = \langle e_1,e_2 \rangle $ and we want to name all lattices of the form $L = \langle v_1= a e_1+ b e_2, v_2 = c e_1 + d e_2 \rangle $ that are commensurable to $L_1 $. Again this means that the intersection $L \cap L_1 $ is of finite index in both lattices. From this it follows immediately that all coefficients $a,b,c,d $ are rational numbers.

It simplifies matters enormously if we do not look at lattices individually but rather at projective equivalence classes, that is $~L=\langle v_1, v_2 \rangle \sim L’ = \langle v’_1,v’_2 \rangle $ if there is a rational number $\lambda \in \mathbb{Q} $ such that $~\lambda v_1 = v’_1, \lambda v_2=v’_2 $. Further, we are of course allowed to choose a different ‘basis’ for our lattices, that is, $~L = \langle v_1,v_2 \rangle = \langle w_1,w_2 \rangle $ whenever $~(w_1,w_2) = (v_1,v_2).\gamma $ for some $\gamma \in PSL_2(\mathbb{Z}) $.
Using both operations we can get any lattice in a specific form. For example,

$\langle \frac{1}{2}e_1+3e_2,e_1-\frac{1}{3}e_2 \overset{(1)}{=} \langle 3 e_1+18e_2,6e_1-2e_2 \rangle \overset{(2)}{=} \langle 3 e_1+18 e_2,38 e_2 \rangle \overset{(3)}{=} \langle \frac{3}{38}e_1+\frac{9}{19}e_2,e_2 \rangle $

Here, identities (1) and (3) follow from projective equivalence and identity (2) from a base-change. In general, any lattice $L $ commensurable to the standard lattice $L_1 $ can be rewritten uniquely as $L = \langle Me_1 + \frac{g}{h} e_2,e_2 \rangle $ where $M $ a positive rational number and with $0 \leq \frac{g}{h} < 1 $.

Another major feature is that one can define a symmetric hyper-distance between (equivalence classes of) such lattices. Take $L=\langle Me_1 + \frac{g}{h} e_2,e_2 \rangle $ and $L’=\langle N e_1 + \frac{i}{j} e_2,e_2 \rangle $ and consider the matrix

$D_{LL’} = \begin{bmatrix} M & \frac{g}{h} \\ 0 & 1 \end{bmatrix} \begin{bmatrix} N & \frac{i}{j} \\ 0 & 1 \end{bmatrix}^{-1} $ and let $\alpha $ be the smallest positive rational number such that all entries of the matrix $\alpha.D_{LL’} $ are integers, then

$\delta(L,L’) = det(\alpha.D_{LL’}) \in \mathbb{N} $ defines a symmetric hyperdistance which depends only of the equivalence classes of lattices (hyperdistance because the log of it behaves like an ordinary distance).

Conway’s big picture is the graph obtained by taking as its vertices the equivalence classes of lattices commensurable with $L_1 $ and with edges connecting any two lattices separated by a prime number hyperdistance. Here’s part of the 2-picture, that is, only depicting the edges of hyperdistance 2.

The 2-picture is an infinite 3-valent tree as there are precisely 3 classes of lattices at hyperdistance 2 from any lattice $L = \langle v_1,v_2 \rangle $ namely (the equivalence classes of) $\langle \frac{1}{2}v_1,v_2 \rangle~,~\langle v_1, \frac{1}{2} v_2 \rangle $ and $\langle \frac{1}{2}(v_1+v_2),v_2 \rangle $.

Similarly, for any prime hyperdistance p, the p-picture is an infinite p+1-valent tree and the big picture is the product over all these prime trees. That is, two lattices at square-free hyperdistance $N=p_1p_2\ldots p_k $ are two corners of a k-cell in the big picture!
(Astute readers of this blog (if such people exist…) may observe that Conway’s big picture did already appear here prominently, though in disguise. More on this another time).

The big picture presents a simple way to look at arithmetic groups and makes many facts about them visually immediate. For example, the point-stabilizer subgroup of $L_1 $ clearly is the modular group $PSL_2(\mathbb{Z}) $. The point-stabilizer of any other lattice is a certain conjugate of the modular group inside $PSL_2(\mathbb{R}) $. For example, the stabilizer subgroup of the lattice $L_N = \langle Ne_1,e_2 \rangle $ (at hyperdistance N from $L_1 $) is the subgroup

${ \begin{bmatrix} a & \frac{b}{N} \\ Nc & d \end{bmatrix}~|~\begin{bmatrix} a & b \\ c & d \end{bmatrix} \in PSL_2(\mathbb{Z})~} $

Now the intersection of these two groups is the modular subgroup $\Gamma_0(N) $ (consisting of those modular group element whose lower left-hand entry is divisible by N). That is, the proper way to look at this arithmetic group is as the joint stabilizer of the two lattices $L_1,L_N $. The picture makes it trivial to compute the index of this subgroup.

Consider the ball $B(L_1,N) $ with center $L_1 $ and hyper-radius N (on the left, the ball with hyper-radius 4). Then, it is easy to show that the modular group acts transitively on the boundary lattices (including the lattice $L_N $), whence the index $[ \Gamma : \Gamma_0(N)] $ is just the number of these boundary lattices. For N=4 the picture shows that there are exactly 6 of them. In general, it follows from our knowledge of all the p-trees the number of all lattices at hyperdistance N from $L_1 $ is equal to $N \prod_{p | N}(1+ \frac{1}{p}) $, in accordance with the well-known index formula for these modular subgroups!

But, there are many other applications of the big picture giving a simple interpretation for the Hecke operators, an elegant proof of the Atkin-Lehner theorem on the normalizer of $\Gamma_0(N) $ (the whimsical source of appearances of the number 24) and of Helling’s theorem characterizing maximal arithmetical groups inside $PSL_2(\mathbb{C}) $ as conjugates of the normalizers of $\Gamma_0(N) $ for square-free N.
J.H. Conway’s paper “Understanding groups like $\Gamma_0(N) $” containing all this material is a must-read! Unfortunately, I do not know of an online version.

Leave a Comment

On2 : extending Lenstra’s list

Published January 27, 2009 by lievenlb

We have seen that John Conway defined a nim-addition and nim-multiplication on the ordinal numbers in such a way that the subfield $[\omega^{\omega^{\omega}}] \simeq \overline{\mathbb{F}}_2 $ is the algebraic closure of the field on two elements. We’ve also seen how to do actual calculations in that field provided we can determine the mystery elements $\alpha_p $, which are the smallest ordinals not being a p-th power of ordinals lesser than $[\omega^{\omega^{k-1}}] $ if $p $ is the $k+1 $-th prime number.

Hendrik Lenstra came up with an effective method to compute these elements $\alpha_p $ requiring a few computations in certain finite fields. I’ll give a rundown of his method and refer to his 1977-paper “On the algebraic closure of two” for full details.

For any ordinal $\alpha < \omega^{\omega^{\omega}} $ define its degree $d(\alpha) $ to be the degree of minimal polynomial for $\alpha $ over $\mathbb{F}_2 = [2] $ and for each prime number $p $ let $f(p) $ be the smallest number $h $ such that $p $ is a divisor of $2^h-1 $ (clearly $f(p) $ is a divisor of $p-1 $).

In the previous post we have already defined ordinals $\kappa_{p^k}=[\omega^{\omega^{k-1}.p^{n-1}}] $ for prime-power indices, but we now need to extend this definition to allow for all indices. So. let $h $ be a natural number, $p $ the smallest prime number dividing $h $ and $q $ the highest power of $p $ dividing $h $. Let $g=[h/q] $, then Lenstra defines

$\kappa_h = \begin{cases} \kappa_q~\text{if q divides}~d(\kappa_q)~\text{ and} \\ \kappa_g + \kappa_q = [\kappa_g + \kappa_q]~\text{otherwise} \end{cases} $

With these notations, the main result asserts the existence of natural numbers $m,m’ $ such that

$\alpha_p = [\kappa_{f(p)} + m] = [\kappa_{f(p)}] + m’ $

Now, assume by induction that we have already determined the mystery numbers $\alpha_r $ for all odd primes $r < p $, then by teh argument of last time we can effectively compute in the field $[\kappa_p] $. In particular, we can compute for every element its multiplicative order $ord(\beta) $ and therefore also its degree $d(\beta) $ which has to be the smallest number $h $ such that $ord(\beta) $ divides $[2^h-1] $.

Then, by the main result we only have to determine the smallest number m such that $\beta = [\kappa_{f(p)} +m] $ is not a p-th power in $\kappa_p $ which is equivalent to the condition that

$\beta^{(2^{d(\beta)}-1)/p} \not= 1 $ if $p $ divides $[2^{d(\beta)}-1] $

All these conditions can be verified within suitable finite fields and hence are effective. In this manner, Lenstra could extend Conway’s calculations (probably using a home-made finite field program running on a slow 1977 machine) :

[tex]\begin{array}{c|c|c} p & f(p) & \alpha_p \\ \hline 3 & 2 & [2] \\ 5 & 4 & [4] \\ 7 & 3 & [\omega]+1 \\ 11 & 10 & [\omega^{\omega}]+1 \\ 13 & 12 & [\omega]+4 \\ 17 & 8 & [16] \\ 19 & 18 & [\omega^3]+4 \\ 23 & 11 & [\omega^{\omega^3}]+1 \\ 29 & 28 & [\omega^{\omega^2}]+4 \\ 31 & 5 & [\omega^{\omega}]+1 \\ 37 & 36 & [\omega^3]+4 \\ 41 & 20 & [\omega^{\omega}]+1 \\ 43 & 14 & [\omega^{\omega^2}]+ 1 \end{array}[/tex]

Right, so let’s try the case $p=47 $. To begin, $f(47)=23 $ whence we have to determine the smallest field containg $\kappa_{23} $. By induction (Lenstra’s tabel) we know already that

$\kappa_{23}^{23} = \kappa_{11} + 1 = [\omega^{\omega^3}]+1 $ and $\kappa_{11}^{11} = \kappa_5 + 1 = [\omega^{\omega}]+1 $ and $\kappa_5^5=[4] $

Because the smallest field containg $4 $ is $[16]=\mathbb{F}_{2^4} $ we have that $\mathbb{F}_2(4,\kappa_5,\kappa_{11}) \simeq \mathbb{F}_{2^{220}} $. We can construct this finite field, together with a generator $a $ of its multiplicative group in Sage via

sage: f1.< a >=GF(2^220)

In this field we have to pinpoint the elements $4,\kappa_5 $ and $\kappa_{11} $. As $4 $ has order $15 $ in $\mathbb{F}_{2^4} $ we know that $\kappa_5 $ has order $75 $. Hence we can take $\kappa_5 = a^{(2^{220}-1)/75} $ and then $4=\kappa_5^5 $.

If we denote $\kappa_5 $ by x5 we can obtain $\kappa_{11} $ as x11 by the following sage-commands

sage: c=x5+1

sage: x11=c.nth_root(11)

It takes about 7 minutes to find x11 on a 2.4 GHz MacBook. Next, we have to set up the field extension determined by $\kappa_{23} $ (which we will call x in sage). This is done as follows

sage: p1.=PolynomialRing(f1)


sage: f=x^23-x11-1

sage: F2=f1.extension(f,'u')

The MacBook needed 8 minutes to set up this field which is isomorphic to $\mathbb{F}_{2^{5060}} $. The relevant number is therefore $n=\frac{2^{5060}-1}{47} $ which is the gruesome

34648162040462867047623719793206539850507437636617898959901744136581<br/>
259144476645069239839415478030722644334257066691823210120548345667203443<br/>
317743531975748823386990680394012962375061822291120459167399032726669613
<br/>
442804392429947890878007964213600720766879334103454250982141991553270171

938532417844211304203805934829097913753132491802446697429102630902307815

301045433019807776921086247690468136447620036910689177286910624860871748

150613285530830034500671245400628768674394130880959338197158054296625733

206509650361461537510912269982522844517989399782602216622257291361930850

885916974186835958466930689748400561295128553674118498999873244045842040

080195019701984054428846798610542372150816780493166669821114184374697446

637066566831036116390063418916814141753876530004881539570659100352197393

997895251223633176404672792711603439161147155163219282934597310848529360

118189507461132290706604796116111868096099527077437183219418195396666836

014856037176421475300935193266597196833361131333604528218621261753883518

667866835204501888103795022437662796445008236823338104580840186181111557

498232520943552183185687638366809541685702608288630073248626226874916669

186372183233071573318563658579214650042598011275864591248749957431967297

975078011358342282941831582626985121760847852546207377440873367589369439

085660784239080183415569559585998884824991911321095149718147110882474280

968166266224151511519773175933506503369761671964823112231808283557885030

984081329986188655169245595411930535264918359325712373064120338963742590

76555755141425

Remains ‘only’ to take x,x+1,etc. to the n-th power and verify which is the first to be unequal to 1. For this it is best to implement the usual powering trick (via digital expression of the exponent) in the field F2, something like

sage: def power(e,n): ...: le=n.bits() ...: v=n.digits() ...: mn=F2(e) ...: out=F2(1) ...: i=0 ...: while i< le : ...: if v[i]==1 : out=F2(out_mn) ...: m=F2(mn_mn) ...: mn=F2(m) ...: i=i+1 ...: return(out) ...:

then it takes about 20 seconds to verify that power(x,n)=1 but that power(x+1,n) is NOT! That is, we just checked that $\alpha_{47}=\kappa_{11}+1 $.

It turns out that 47 is the hardest nut to crack, the following primes are easier. Here’s the data (if I didn’t make mistakes…)

[tex]\begin{array}{c|c|c} p & f(p) & \alpha_p \\ \hline 47 & 23 & [\omega^{\omega^{7}}]+1 \\ 53 & 52 & [\omega^{\omega^4}]+1 \\ 59 & 58 & [\omega^{\omega^8}]+1 \\ 61 & 60 & [\omega^{\omega}]+[\omega] \\ 67 & 66 & [\omega^{\omega^3}]+[\omega] \end{array}[/tex]

It seems that Magma is substantially better at finite field arithmetic, so if you are lucky enough to have it you’ll have no problem finding $\alpha_p $ for all primes less than 100 by the end of the day. If you do, please drop a comment with the results…

Leave a Comment

On2 : Conway’s nim-arithmetics

Published January 26, 2009 by lievenlb

Last time we did recall Cantor’s addition and multiplication on ordinal numbers. Note that we can identify an ordinal number $\alpha $ with (the order type of) the set of all strictly smaller ordinals, that is, $\alpha = { \alpha’~:~\alpha’ < \alpha } $. Given two ordinals $\alpha $ and $\beta $ we will denote their Cantor-sums and products as $[ \alpha + \beta] $ and $[\alpha . \beta] $.

The reason for these square brackets is that John Conway constructed a well behaved nim-addition and nim-multiplication on all ordinals $\mathbf{On}_2 $ by imposing the ‘simplest’ rules which make $\mathbf{On}_2 $ into a field. By this we mean that, in order to define the addition $\alpha + \beta $ we must have constructed before all sums $\alpha’ + \beta $ and $\alpha + \beta’ $ with $\alpha’ < \alpha $ and $\beta’ < \beta $. If + is going to be a well-defined addition on $\mathbf{On}_2 $ clearly $\alpha + \beta $ cannot be equal to one of these previously constructed sums and the ‘simplicity rule’ asserts that we should take $\alpha+\beta $ the least ordinal different from all these sums $\alpha’+\beta $ and $\alpha+\beta’ $. In symbols, we define

$\alpha+ \beta = \mathbf{mex} { \alpha’+\beta,\alpha+ \beta’~|~\alpha’ < \alpha, \beta’ < \beta } $

where $\mathbf{mex} $ stands for ‘minimal excluded value’. If you’d ever played the game of Nim you will recognize this as the Nim-addition, at least when $\alpha $ and $\beta $ are finite ordinals (that is, natural numbers) (to nim-add two numbers n and m write them out in binary digits and add without carrying). Alternatively, the nim-sum n+m can be found applying the following two rules :

the nim-sum of a number of distinct 2-powers is their ordinary sum (e.g. $8+4+1=13 $, and,
the nim-sum of two equal numbers is 0.

So, all we have to do is to write numbers n and m as sums of two powers, scratch equal terms and add normally. For example, $13+7=(8+4+1)+(4+2+1)=8+2=10 $ (of course this is just digital sum without carry in disguise).

Here’s the beginning of the nim-addition table on ordinals. For example, to define $13+7 $ we have to look at all values in the first 7 entries of the row of 13 (that is, ${ 13,12,15,14,9,8,11 } $) and the first 13 entries in the column of 7 (that is, ${ 7,6,5,4,3,2,1,0,15,14,13,12,11 } $) and find the first number not included in these two sets (which is indeed $10 $).

In fact, the above two rules allow us to compute the nim-sum of any two ordinals. Recall from last time that every ordinal can be written uniquely as as a finite sum of (ordinal) 2-powers :
$\alpha = [2^{\alpha_0} + 2^{\alpha_1} + \ldots + 2^{\alpha_k}] $, so to determine the nim-sum $\alpha+\beta $ we write both ordinals as sums of ordinal 2-powers, delete powers appearing twice and take the Cantor ordinal sum of the remaining sum.

Nim-multiplication of ordinals is a bit more complicated. Here’s the definition as a minimal excluded value

$\alpha.\beta = \mathbf{mex} { \alpha’.\beta + \alpha.\beta’ – \alpha’.\beta’ } $

for all $\alpha’ < \alpha, \beta’ < \beta $. The rationale behind this being that both $\alpha-\alpha’ $ and $\beta – \beta’ $ are non-zero elements, so if $\mathbf{On}_2 $ is going to be a field under nim-multiplication, their product should be non-zero (and hence strictly greater than 0), that is, $~(\alpha-\alpha’).(\beta-\beta’) > 0 $. Rewriting this we get $\alpha.\beta > \alpha’.\beta+\alpha.\beta’-\alpha’.\beta’ $ and again the ‘simplicity rule’ asserts that $\alpha.\beta $ should be the least ordinal satisfying all these inequalities, leading to the $\mathbf{mex} $-definition above. The table gives the beginning of the nim-multiplication table for ordinals. For finite ordinals n and m there is a simple 2 line procedure to compute their nim-product, similar to the addition-rules mentioned before :

the nim-product of a number of distinct Fermat 2-powers (that is, numbers of the form $2^{2^n} $) is their ordinary product (for example, $16.4.2=128 $), and,
the square of a Fermat 2-power is its sesquimultiple (that is, the number obtained by multiplying with $1\frac{1}{2} $ in the ordinary sense). That is, $2^2=3,4^2=6,16^2=24,… $

Using these rules, associativity and distributivity and our addition rules it is now easy to work out the nim-multiplication $n.m $ : write out n and m as sums of (multiplications by 2-powers) of Fermat 2-powers and apply the rules. Here’s an example

$5.9=(4+1).(4.2+1)=4^2.2+4.2+4+1=6.2+8+4+1=(4+2).2+13=4.2+2^2+13=8+3+13=6 $

Clearly, we’d love to have a similar procedure to calculate the nim-product $\alpha.\beta $ of arbitrary ordinals, or at least those smaller than $\omega^{\omega^{\omega}} $ (recall that Conway proved that this ordinal is isomorphic to the algebraic closure $\overline{\mathbb{F}}_2 $ of the field of two elements). From now on we restrict to such ‘small’ ordinals and we introduce the following special elements :

$\kappa_{2^n} = [2^{2^{n-1}}] $ (these are the Fermat 2-powers) and for all primes $p > 2 $ we define
$\kappa_{p^n} = [\omega^{\omega^{k-1}.p^{n-1}}] $ where $k $ is the number of primes strictly smaller than $p $ (that is, for p=3 we have k=1, for p=5, k=2 etc.).

Again by associativity and distributivity we will be able to multiply two ordinals $< \omega^{\omega^{\omega}} $ if we know how to multiply a product

$[\omega^{\alpha}.2^{n_0}].[\omega^{\beta}.2^{m_0}] $ with $\alpha,\beta < [\omega^{\omega}] $ and $n_0,m_0 \in \mathbb{N} $.

Now, $\alpha $ can be written uniquely as $[\omega^t.n_t+\omega^{t-1}.n_{t-1}+\ldots+\omega.n_2 + n_1] $ with t and all $n_i $ natural numbers. Write each $n_k $ in base $p $ where $p $ is the $k+1 $-th prime number, that is, we have for $n_0,n_1,\ldots,n_t $ an expression

$n_k=[\sum_j p^j.m(j,k)] $ with $0 \leq m(j,k) < p $

The point of all this is that any of the special elements we want to multiply can be written as a unique expression as a decreasing product

$[\omega^{\alpha}.2^{n_0}] = [ \prod_q \kappa_q^m(q) ] $

where $q $ runs over all prime powers. The crucial fact now is that for this decreasing product we have a rule similar to addition of 2-powers, that is Conway-products coincide with the Cantor-products

$[ \prod_q \kappa_q^m(q) ] = \prod_q \kappa_q^m(q) $

But then, using associativity and commutativity of the Conway-product we can ‘nearly’ describe all products $[\omega^{\alpha}.2^{n_0}].[\omega^{\beta}.2^{m_0}] $. The remaining problem being that it may happen that for some q we will end up with an exponent $m(q)+m(q’)>p $. But this can be solved if we know how to take p-powers. The rules for this are as follows

$~(\kappa_{2^n})^2 = \kappa_{2^n} + \prod_{1 \leq i < n} \kappa_{2^i} $, for 2-powers, and,

$~(\kappa_{p^n})^p = \kappa_{p^{n-1}} $ for a prime $p > 2 $ and for $n \geq 2 $, and finally

$~(\kappa_p)^p = \alpha_p $ for a prime $p > 2 $, where $\alpha_p $ is the smallest ordinal $< \kappa_p $ which cannot be written as a p-power $\beta^p $ with $\beta < \kappa_p $. Summarizing : if we will be able to find these mysterious elements $\alpha_p $ for all prime numbers p, we are able to multiply in $[\omega^{\omega^{\omega}}]=\overline{\mathbb{F}}_2 $.

Let us determine the first one. We have that $\kappa_3 = \omega $ so we are looking for the smallest natural number $n < \omega $ which cannot be written in num-multiplication as $n=m^3 $ for $m < \omega $ (that is, also $m $ a natural number). Clearly $1=1^3 $ but what about 2? Can 2 be a third root of a natural number wrt. nim-multiplication? From the tabel above we see that 2 has order 3 whence its cube root must be an element of order 9. Now, the only finite ordinals that are subfields of $\mathbf{On}_2 $ are precisely the Fermat 2-powers, so if there is a finite cube root of 2, it must be contained in one of the finite fields $[2^{2^n}] $ (of which the mutiplicative group has order $2^{2^n}-1 $ and one easily shows that 9 cannot be a divisor of any of the numbers $2^{2^n}-1 $, that is, 2 doesn’t have a finte 3-th root in nim! Phrased differently, we found our first mystery number $\alpha_3 = 2 $. That is, we have the marvelous identity in nim-arithmetic

$\omega^3 = 2 $

Okay, so what is $\alpha_5 $? Well, we have $\kappa_5 = [\omega^{\omega}] $ and we have to look for the smallest ordinal which cannot be written as a 5-th root. By inspection of the finite nim-table we see that 1,2 and 3 have 5-th roots in $\omega $ but 4 does not! The reason being that 4 has order 15 (check in the finite field [16]) and 25 cannot divide any number of the form $2^{2^n}-1 $. That is, $\alpha_5=4 $ giving another crazy nim-identity

$~(\omega^{\omega})^5 = 4 $

And, surprises continue to pop up… Conway showed that $\alpha_7 = \omega+1 $ giving the nim-identity $~(\omega^{\omega^2})^7 = \omega+1 $. The proof of this already uses some clever finite field arguments. Because 7 doesn’t divide any number $2^{2^n}-1 $, none of the finite subfields $[2^{2^n}] $ contains a 7-th root of unity, so the 7-power map is injective whence surjective, so all finite ordinal have finite 7-th roots! That is, $\alpha_7 \geq \omega $. Because $\omega $ lies in a cubic extension of the finite field [4], the field generated by $\omega $ has 64 elements and so its multiplicative group is cyclic of order 63 and as $\omega $ has order 9, it must be a 7-th power in this field. But, as the only 7th powers in that field are precisely the powers of $\omega $ and by inspection $\omega+1 $ is not a 7-th power in that field (and hence also not in any field extension obtained by adjoining square, cube and fifth roots) so $\alpha_7=\omega +1 $.

Conway did stop at $\alpha_7 $ but I’ve always been intrigued by that one line in ONAG p.61 : “Hendrik Lenstra has computed $\alpha_p $ for $p \leq 43 $”. Next time we will see how Lenstra managed to do this and we will use sage to extend his list a bit further, including the first open case : $\alpha_{47}= \omega^{\omega^7}+1 $.

For an enjoyable video on all of this, see Conway’s MSRI lecture on Infinite Games. The nim-arithmetic part is towards the end of the lecture but watching the whole video is a genuine treat!

Leave a Comment

On2 : transfinite number hacking

Published January 8, 2009 by lievenlb

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

One Comment

Mazur’s knotty dictionary

Published December 27, 2008 by lievenlb

In the previous posts, we have depicted the ‘arithmetic line’, that is the prime numbers, as a ‘line’ and individual primes as ‘points’.

However, sometime in the roaring 60-ties, Barry Mazur launched the crazy idea of viewing the affine spectrum of the integers, $\mathbf{spec}(\mathbb{Z}) $, as a 3-dimensional manifold and prime numbers themselves as knots in this 3-manifold…

After a long silence, this idea was taken up recently by Mikhail Kapranov and Alexander Reznikov (1960-2003) in a talk at the MPI-Bonn in august 1996. Pieter Moree tells the story in his recollections about Alexander (Sacha) Reznikov in Sipping Tea with Sacha : “Sasha’s paper is closely related to his paper where the analogy of covers of three-manifolds and class field theory plays a big role (an analogy that was apparently first noticed by B. Mazur). Sasha and Mikhail Kapranov (at the time also at the institute) were both very interested in this analogy. Eventually, in August 1996, Kapranov and Reznikov both lectured on this (and I explained in about 10 minutes my contribution to Reznikov’s proof). I was pleased to learn some time ago that this lecture series even made it into the literature, see Morishita’s ‘On certain analogies between knots and primes’ J. reine angew. Math 550 (2002) 141-167.”

Here’s a part of what is now called the Kapranov-Reznikov-Mazur dictionary :

What is the rationale behind this dictionary? Well, it all has to do with trying to make sense of the (algebraic) fundamental group $\pi_1^{alg}(X) $ of a general scheme $X $. Recall that for a manifold $M $ there are two different ways to define its fundamental group $\pi_1(M) $ : either as the closed loops in a given basepoint upto homotopy or as the automorphism group of the universal cover $\tilde{M} $ of $M $.

For an arbitrary scheme the first definition doesn’t make sense but we can use the second one as we have a good notion of a (finite) cover : an etale morphism $Y \rightarrow X $ of the scheme $X $. As they form an inverse system, we can take their finite automorphism groups $Aut_X(Y) $ and take their projective limit along the system and call this the algebraic fundamental group $\pi^{alg}_1(X) $.

Hendrik Lenstra has written beautiful course notes on ‘Galois theory for schemes’ on all of this starting from scratch. Besides, there are also two video-lectures available on this at the MSRI-website : Etale fundamental groups 1 by H.W. Lenstra and Etale fundamental groups 2 by F. Pop.

But, what is the connection with the ‘usual’ fundamental group in case both of them can be defined? Well, by construction the algebraic fundamental group is always a profinite group and in the case of manifolds it coincides with the profinite completion of the standard fundamental group, that is,
$\pi^{alg}_1(M) \simeq \widehat{\pi_1(M)} $ (recall that the cofinite completion is the projective limit of all finite group quotients).

Right, so all we have to do to find a topological equivalent of an algebraic scheme is to compute its algebraic fundamental group and find an existing topological space of which the profinite completion of its standard fundamental group coincides with our algebraic fundamental group. An example : a prime number $p $ (as a ‘point’ in $\mathbf{spec}(\mathbb{Z}) $) is the closed subscheme $\mathbf{spec}(\mathbb{F}_p) $ corresponding to the finite field $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z} $. For any affine scheme of a field $K $, the algebraic fundamental group coincides with the absolute Galois group $Gal(\overline{K}/K) $. In the case of $\mathbb{F}_p $ we all know that this abslute Galois group is isomorphic with the profinite integers $\hat{\mathbb{Z}} $. Now, what is the first topological space coming to mind having the integers as its fundamental group? Right, the circle $S^1 $. Hence, in arithmetic topology we view prime numbers as topological circles, that is, as knots in some bigger space.

But then, what is this bigger space? That is, what is the topological equivalent of $\mathbf{spec}(\mathbb{Z}) $? For this we have to go back to Mazur’s original paper Notes on etale cohomology of number fields in which he gives an Artin-Verdier type duality theorem for the affine spectrum $X=\mathbf{spec}(D) $ of the ring of integers $D $ in a number field. More precisely, there is a non-degenerate pairing $H^r_{et}(X,F) \times Ext^{3-r}_X(F, \mathbb{G}_m) \rightarrow H^3_{et}(X,F) \simeq \mathbb{Q}/\mathbb{Z} $ for any constructible abelian sheaf $F $. This may not tell you much, but it is a ‘sort of’ Poincare-duality result one would have for a compact three dimensional manifold.

Ok, so in particular $\mathbf{spec}(\mathbb{Z}) $ should be thought of as a 3-dimensional compact manifold, but which one? For this we have to compute the algebraic fundamental group. Fortunately, this group is trivial as there are no (non-split) etale covers of $\mathbf{spec}(\mathbb{Z}) $, so the corresponding 3-manifold should be simple connected… but wenow know that this has to imply that the manifold must be $S^3 $, the 3-sphere! Summarizing : in arithmetic topology, prime numbers are knots in the 3-sphere!

More generally (by the same arguments) the affine spectrum $\mathbf{spec}(D) $ of a ring of integers can be thought of as corresponding to a closed oriented 3-dimensional manifold $M $ (which is a cover of $S^3 $) and a prime ideal $\mathfrak{p} \triangleleft D $ corresponds to a knot in $M $.

But then, what is an ideal $\mathfrak{a} \triangleleft D $? Well, we have unique factorization of ideals in $D $, that is, $\mathfrak{a} = \mathfrak{p}_1^{n_1} \ldots \mathfrak{p}_k^{n_k} $ and therefore $\mathfrak{a} $ corresponds to a link in $M $ of which the constituent knots are the ones corresponding to the prime ideals $\mathfrak{p}_i $.

And we can go on like this. What should be an element $w \in D $? Well, it will be an embedded surface $S \rightarrow M $, possibly with a boundary, the boundary being the link corresponding to the ideal $\mathfrak{a} = Dw $ and Seifert’s algorithm tells us how we can produce surfaces having any prescribed link as its boundary. But then, in particular, a unit $w \in D^* $ should correspond to a closed surface in $M $.

And all these analogies carry much further : for example the class group of the ring of integers $Cl(D) $ then corresponds to the torsion part $H_1(M,\mathbb{Z})_{tor} $ because principal ideals $Dw $ are trivial in the class group, just as boundaries of surfaces $\partial S $ vanish in $H_1(M,\mathbb{Z}) $. Similarly, one may identify the unit group $D^* $ with $H_2(M,\mathbb{Z}) $… and so on, and on, and on…

More links to papers on arithmetic topology can be found in John Baez’ week 257 or via here.

Leave a Comment