Tag: simples

On2 : Conway’s nim-arithmetics

Published January 26, 2009 by lieven

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!

Comments closed

Andre Weil on the Riemann hypothesis

Published October 15, 2008 by lieven

Don’t be fooled by introductory remarks to the effect that ‘the field with one element was conceived by Jacques Tits half a century ago, etc. etc.’

While this is a historic fact, and, Jacques Tits cannot be given enough credit for bringing a touch of surrealism into mathematics, but this is not the main drive for people getting into F_un, today.

There is a much deeper and older motivation behind most papers published recently on $\mathbb{F}_1 $. Few of the authors will be willing to let you in on the secret, though, because if they did, it would sound much too presumptuous…

So, let’s have it out into the open : F_un mathematics’ goal is no less than proving the Riemann Hypothesis.

And even then, authors hide behind a smoke screen. The ‘official’ explanation being “we would like to copy Weil’s proof of the Riemann hypothesis in the case of function fields of curves over finite fields, by considering spec(Z) as a ‘curve’ over an algebra ‘dessous’ Z namely $\mathbb{F}_1 $”. Alas, at this moment, none of the geometric approaches over the field with one element can make this stick.

Believe me for once, the main Jugendtraum of most authors is to get a grip on cyclotomy over $\mathbb{F}_1 $. It is no accident that Connes makes a dramatic pauze in his YouTubeVideo to let the viewer see this equation on the backboard

$\mathbb{F}_{1^n} \otimes_{\mathbb{F}_1} \mathbb{Z} = \mathbb{Z}[x]/(x^n-1) $

But, what is the basis of all this childlike enthusiasm? A somewhat concealed clue is given in the introduction of the Kapranov-Smirnov paper. They write :

“In [?] the affine line over $\mathbb{F}_1 $ was considered; it consists formally of 0 and all the roots of unity. Put slightly differently, this leads to the consideration of “algebraic extensions” of $\mathbb{F}_1 $. By analogy with genuine finite fields we would like to think that there is exactly one such extension of any given degree n, denote it by $\mathbb{F}_{1^n} $.

Of course, $\mathbb{F}_{1^n} $ does not exist in a rigorous sense, but we can think if a scheme $X $ contains n-th roots of unity, then it is defined over $\mathbb{F}_{1^n} $, so that there is a morphism

$p_X~:~X \rightarrow spec(\mathbb{F}_{1^n} $

The point of view that adjoining roots of unity is analogous to the extension of the base field goes back, at least to Weil (Lettre a Artin, Ouvres, vol 1) and Iwasawa…“

Okay, so rush down to your library, pick out the first of three volumes of Andre Weil’s collected works, look up his letter to Emil Artin written on July 10th 1942 (19 printed pages!), and head for the final section. Weil writes :

“Our proof of the Riemann hypothesis (in the function field case, red.) depended upon the extension of the function-fields by roots of unity, i.e. by constants; the way in which the Galois group of such extensions operates on the classes of divisors in the original field and its extensions gives a linear operator, the characteristic roots (i.e. the eigenvalues) of which are the roots of the zeta-function.

On a number field, the nearest we can get to this is by adjunction of $l^n $-th roots of unity, $l $ being fixed; the Galois group of this infinite extension is cyclic, and defines a linear operator on the projective limit of the (absolute) class groups of those successive finite extensions; this should have something to do with the roots of the zeta-function of the field. However, our extensions are ramified (but only at a finite number of places, viz. the prime divisors of $l $). Thus a preliminary study of similar problems in function-fields might enable one to guess what will happen in number-fields.”

A few years later, in 1947, he makes this a bit more explicit in his marvelous essay “L’avenir des mathematiques” (The future of mathematics). Weil is still in shell-shock after the events of the second WW, and writes in beautiful archaic French sentences lasting forever :

“L’hypothèse de Riemann, après qu’on eu perdu l’espoir de la démontrer par les méthodes de la théorie des fonctions, nous apparaît aujourd’hui sous un jour nouveau, qui la montre inséparable de la conjecture d’Artin sur les fonctions L, ces deux problèmes étant deux aspects d’une même question arithmético-algébrique, où l’étude simultanée de toutes les extensions cyclotomiques d’un corps de nombres donné jouera sans doute le rôle décisif.

L’arithmétique gausienne gravitait autour de la loi de réciprocité quadratique; nous savons maintenant que celle-ci n’est qu’un premier example, ou pour mieux dire le paradigme, des lois dites “du corps de classe”, qui gouvernent les extensions abéliennes des corps de nobres algébriques; nous savons formuler ces lois de manière à leur donner l’aspect d’un ensemble cohérent; mais, si plaisante à l’œil que soit cette façade, nous ne savons si elle ne masque pas des symmétries plus cachées.

Les automorphismes induits sur les groupes de classes par les automorphismes du corps, les propriétés des restes de normes dans les cas non cycliques, le passage à la limite (inductive ou projective) quand on remplace le corps de base par des extensions, par example cyclotomiques, de degré indéfiniment croissant, sont autant de questions sur lesquelles notre ignorance est à peu près complète, et dont l’étude contient peut-être la clef de l’hypothese de Riemann; étroitement liée à celles-ci est l’étude du conducteur d’Artin, et en particulier, dans le cas local, la recherche de la représentation dont la trace s’exprime au moyen des caractères simples avec des coefficients égaux aux exposants de leurs conducteurs.

Ce sont là quelques-unes des directions qu’on peut et qu’on doit songer à suivre afin de pénétrer dans le mystère des extensions non abéliennes; il n’est pas impossible que nous touchions là à des principes d’une fécondité extraordinaire, et que le premier pas décisif une fois fait dans cette voie doive nous ouvrir l’accès à de vastes domaines dont nous soupçonnons à peine l’existence; car jusqu’ici, pour amples que soient nos généralisations des résultats de Gauss, on ne peut dire que nus les ayons vraiment dépassés.”

Arnold’s trinities version 2.0

Published June 20, 2008 by lieven

Arnold has written a follow-up to the paper mentioned last time called “Polymathematics : is mathematics a single science or a set of arts?” (or here for a (huge) PDF-conversion).

On page 8 of that paper is a nice summary of his 25 trinities :

I learned of this newer paper from a comment by Frederic Chapoton who maintains a nice webpage dedicated to trinities.

In his list there is one trinity on sporadic groups :

where $F_{24} $ is the Fischer simple group of order $2^{21}.3^{16}.5^2.7^3.11.13.17.23.29 = 1255205709190661721292800 $, which is the third largest sporadic group (the two larger ones being the Baby Monster and the Monster itself).

I don’t know what the rationale is behind this trinity. But I’d like to recall the (Baby)Monster history as a warning against the trinity-reflex. Sometimes, there is just no way to extend a would be trinity.

The story comes from Mark Ronan’s book Symmetry and the Monster on page 178.

Let’s remind ourselves how we got here. A few years earlier, Fischer has created his ‘transposition’ groups Fi22, Fi23, and Fi24. He had called them M(22), M(23), and M(24), because they were related to Mathieu’s groups M22,M23, and M24, and since he used Fi22 to create his new group of mirror symmetries, he tentatively called it $M^{22} $.
It seemed to appear as a cross-section in something even bigger, and as this larger group was clearly associated with Fi24, he labeled it $M^{24} $. Was there something in between that could be called $M^{23} $?
Fischer visited Cambridge to talk on his new work, and Conway named these three potential groups the Baby Monster, the Middle Monster, and the Super Monster. When it became clear that the Middle Monster didn’t exist, Conway settled on the names Baby Monster and Monster, and this became the standard terminology.

Marcus du Sautoy’s account in Finding Moonshine is slightly different. He tells on page 322 that the Super Monster didn’t exist. Anyone knowing the factual story?

Some mathematical trickery later revealed that the Super Monster was going to be impossible to build: there were certain features that contradicted each other. It was just a mirage, which vanished under closer scrutiny. But the other two were still looking robust. The Middle Monster was rechristened simply the Monster.

And, the inclusion diagram of the sporadic simples tells yet another story.

Anyhow, this inclusion diagram is helpful in seeing the three generations of the Happy Family (as well as the Pariahs) of the sporadic groups, terminology invented by Robert Griess in his 100+p Inventiones paper on the construction of the Monster (which he liked to call, for obvious reasons, the Friendly Giant denoted by FG).
The happy family appears in Table 1.1. of the introduction.

It was this picture that made me propose the trinity on the left below in the previous post. I now like to add another trinity on the right, and, the connection between the two is clear.

Here $Golay $ denotes the extended binary Golay code of which the Mathieu group $M_{24} $ is the automorphism group. $Leech $ is of course the 24-dimensional Leech lattice of which the automorphism group is a double cover of the Conway group $Co_1 $. $Griess $ is the Griess algebra which is a nonassociative 196884-dimensional algebra of which the automorphism group is the Monster.

I am aware of a construction of the Leech lattice involving the quaternions (the icosian construction of chapter 8, section 2.2 of SPLAG). Does anyone know of a construction of the Griess algebra involving octonions???