\usepackagecolor\usepackage[matrix]xy\usepackageskak\usepackagecolor\usepackage[matrix]xy\usepackageskak Skip to content →

Category: featured

On2 : Conway’s nim-arithmetics

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

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

α+β=mexα+β,α+β | α<α,β<β

where 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 α and β 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 :
α=[2α0+2α1++2αk], so to determine the nim-sum α+β 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

α.β=mexα.β+α.βα.β

for all α<α,β<β. The rationale behind this being that both αα and ββ are non-zero elements, so if On2 is going to be a field under nim-multiplication, their product should be non-zero (and hence strictly greater than 0), that is,  (αα).(ββ)>0. Rewriting this we get α.β>α.β+α.βα.β and again the ‘simplicity rule’ asserts that α.β should be the least ordinal satisfying all these inequalities, leading to the 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 22n) 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 112 in the ordinary sense). That is, 22=3,42=6,162=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)=42.2+4.2+4+1=6.2+8+4+1=(4+2).2+13=4.2+22+13=8+3+13=6

Clearly, we’d love to have a similar procedure to calculate the nim-product α.β of arbitrary ordinals, or at least those smaller than ωωω (recall that Conway proved that this ordinal is isomorphic to the algebraic closure ¯F2 of the field of two elements). From now on we restrict to such ‘small’ ordinals and we introduce the following special elements :

κ2n=[22n1] (these are the Fermat 2-powers) and for all primes p>2 we define
κpn=[ωωk1.pn1] 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 <ωωω if we know how to multiply a product

[ωα.2n0].[ωβ.2m0] with α,β<[ωω] and n0,m0N.

Now, α can be written uniquely as [ωt.nt+ωt1.nt1++ω.n2+n1] with t and all ni natural numbers. Write each nk in base p where p is the k+1-th prime number, that is, we have for n0,n1,,nt an expression

nk=[jpj.m(j,k)] with 0m(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

[ωα.2n0]=[qκmq(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

[qκmq(q)]=qκmq(q)

But then, using associativity and commutativity of the Conway-product we can ‘nearly’ describe all products [ωα.2n0].[ωβ.2m0]. 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

 (κ2n)2=κ2n+1i<nκ2i, for 2-powers, and,

 (κpn)p=κpn1 for a prime p>2 and for n2, and finally

 (κp)p=αp for a prime p>2, where αp is the smallest ordinal <κp which cannot be written as a p-power βp with β<κp. Summarizing : if we will be able to find these mysterious elements αp for all prime numbers p, we are able to multiply in [ωωω]=¯F2.

Let us determine the first one. We have that κ3=ω so we are looking for the smallest natural number n<ω which cannot be written in num-multiplication as n=m3 for m<ω (that is, also m a natural number). Clearly 1=13 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 On2 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 [22n] (of which the mutiplicative group has order 22n1 and one easily shows that 9 cannot be a divisor of any of the numbers 22n1, that is, 2 doesn’t have a finte 3-th root in nim! Phrased differently, we found our first mystery number α3=2. That is, we have the marvelous identity in nim-arithmetic

ω3=2

Okay, so what is α5? Well, we have κ5=[ωω] 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 ω 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 22n1. That is, α5=4 giving another crazy nim-identity

 (ωω)5=4

And, surprises continue to pop up… Conway showed that α7=ω+1 giving the nim-identity  (ωω2)7=ω+1. The proof of this already uses some clever finite field arguments. Because 7 doesn’t divide any number 22n1, none of the finite subfields [22n] 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, α7ω. Because ω lies in a cubic extension of the finite field [4], the field generated by ω has 64 elements and so its multiplicative group is cyclic of order 63 and as ω 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 ω and by inspection ω+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 α7=ω+1.

Conway did stop at α7 but I’ve always been intrigued by that one line in ONAG p.61 : “Hendrik Lenstra has computed αp for p43”. 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 : α47=ωω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

Mumford’s treasure map


David Mumford did receive earlier this year the 2007 AMS Leroy P. Steele Prize for Mathematical Exposition. The jury honors Mumford for “his beautiful expository accounts of a host of aspects of algebraic geometry”. Not surprisingly, the first work they mention are his mimeographed notes of the first 3 chapters of a course in algebraic geometry, usually called “Mumford’s red book” because the notes were wrapped in a red cover. In 1988, the notes were reprinted by Springer-Verlag. Unfortnately, the only red they preserved was in the title.

The AMS describes the importance of the red book as follows. “This is one of the few books that attempt to convey in pictures some of the highly abstract notions that arise in the field of algebraic geometry. In his response upon receiving the prize, Mumford recalled that some of his drawings from The Red Book were included in a collection called Five Centuries of French Mathematics. This seemed fitting, he noted: “After all, it was the French who started impressionist painting and isn’t this just an impressionist scheme for rendering geometry?””

These days it is perfectly possible to get a good grasp on difficult concepts from algebraic geometry by reading blogs, watching YouTube or plugging in equations to sophisticated math-programs. In the early seventies though, if you wanted to know what Grothendieck’s scheme-revolution was all about you had no choice but to wade through the EGA’s and SGA’s and they were notorious for being extremely user-unfriendly regarding illustrations…

So the few depictions of schemes available, drawn by people sufficiently fluent in Grothendieck’s new geometric language had no less than treasure-map-cult-status and were studied in minute detail. Mumford’s red book was a gold mine for such treasure maps. Here’s my favorite one, scanned from the original mimeographed notes (it looks somewhat tidier in the Springer-version)



It is the first depiction of spec(Z[x]), the affine scheme of the ring Z[x] of all integral polynomials. Mumford calls it the”arithmetic surface” as the picture resembles the one he made before of the affine scheme spec(C[x,y]) corresponding to the two-dimensional complex affine space A2C. Mumford adds that the arithmetic surface is ‘the first example which has a real mixing of arithmetic and geometric properties’.

Let’s have a closer look at the treasure map. It introduces some new signs which must have looked exotic at the time, but have since become standard tools to depict algebraic schemes.

For starters, recall that the underlying topological space of spec(Z[x]) is the set of all prime ideals of the integral polynomial ring Z[x], so the map tries to list them all as well as their inclusions/intersections.

The doodle in the right upper corner depicts the ‘generic point’ of the scheme. That is, the geometric object corresponding to the prime ideal  (0) (note that Z[x] is an integral domain). Because the zero ideal is contained in any other prime ideal, the algebraic/geometric mantra (“inclusions reverse when shifting between algebra and geometry”) asserts that the gemetric object corresponding to  (0) should contain all other geometric objects of the arithmetic plane, so it is just the whole plane! Clearly, it is rather senseless to depict this fact by coloring the whole plane black as then we wouldn’t be able to see the finer objects. Mumford’s solution to this is to draw a hairy ball, which in this case, is sufficiently thick to include fragments going in every possible direction. In general, one should read these doodles as saying that the geometric object represented by this doodle contains all other objects seen elsewhere in the picture if the hairy-ball-doodle includes stuff pointing in the direction of the smaller object. So, in the case of the object corresponding to  (0), the doodle has pointers going everywhere, saying that the geometric object contains all other objects depicted.

Let’s move over to the doodles in the lower right-hand corner. They represent the geometric object corresponding to principal prime ideals of the form  (p(x)), where p(x) in an irreducible polynomial over the integers, that is, a polynomial which we cannot write as the product of two smaller integral polynomials. The objects corresponding to such prime ideals should be thought of as ‘horizontal’ curves in the plane.

The doodles depicted correspond to the prime ideal  (x), containing all polynomials divisible by x so when we divide it out we get, as expected, a domain Z[x]/(x)Z, and the one corresponding to the ideal  (x2+1), containing all polynomials divisible by x2+1, which can be proved to be a prime ideals of Z[x] by observing that after factoring out we get Z[x]/(x2+1)Z[i], the domain of all Gaussian integers Z[i]. The corresponding doodles (the ‘generic points’ of the curvy-objects) have a predominant horizontal component as they have the express the fact that they depict horizontal curves in the plane. It is no coincidence that the doodle of  (x2+1) is somewhat bulkier than the one of  (x) as the later one must only depict the fact that all points lying on the straight line to its left belong to it, whereas the former one must claim inclusion of all points lying on the ‘quadric’ it determines.

Apart from these ‘horizontal’ curves, there are also ‘vertical’ lines corresponding to the principal prime ideals  (p), containing the polynomials, all of which coefficients are divisible by the prime number p. These are indeed prime ideals of Z[x], because their quotients are
Z[x]/(p)(Z/pZ)[x] are domains, being the ring of polynomials over the finite field Z/pZ=Fp. The doodles corresponding to these prime ideals have a predominant vertical component (depicting the ‘vertical’ lines) and have a uniform thickness for all prime numbers p as each of them only has to claim ownership of the points lying on the vertical line under them.

Right! So far we managed to depict the zero prime ideal (the whole plane) and the principal prime ideals of Z[x] (the horizontal curves and the vertical lines). Remains to depict the maximal ideals. These are all known to be of the form
m=(p,f(x))
where p is a prime number and f(x) is an irreducible integral polynomial, which remains irreducible when reduced modulo p (that is, if we reduce all coefficients of the integral polynomial f(x) modulo p we obtain an irreducible polynomial in  Fp[x]). By the algebra/geometry mantra mentioned before, the geometric object corresponding to such a maximal ideal can be seen as the ‘intersection’ of an horizontal curve (the object corresponding to the principal prime ideal  (f(x))) and a vertical line (corresponding to the prime ideal  (p)). Because maximal ideals do not contain any other prime ideals, there is no reason to have a doodle associated to m and we can just depict it by a “point” in the plane, more precisely the intersection-point of the horizontal curve with the vertical line determined by m=(p,f(x)). Still, Mumford’s treasure map doesn’t treat all “points” equally. For example, the point corresponding to the maximal ideal m1=(3,x+2) is depicted by a solid dot ., whereas the point corresponding to the maximal ideal m2=(3,x2+1) is represented by a fatter point . The distinction between the two ‘points’ becomes evident when we look at the corresponding quotients (which we know have to be fields). We have

Z[x]/m1=Z[x]/(3,x+2)=(Z/3Z)[x]/(x+2)=Z/3Z=F3 whereas Z[x]/m2=Z[x]/(3,x2+1)=Z/3Z[x]/(x2+1)=F3[x]/(x2+1)=F32

because the polynomial x2+1 remains irreducible over F3, the quotient F3[x]/(x2+1) is no longer the prime-field F3 but a quadratic field extension of it, that is, the finite field consisting of 9 elements F32. That is, we represent the ‘points’ lying on the vertical line corresponding to the principal prime ideal  (p) by a solid dot . when their quotient (aka residue field is the prime field  Fp, by a bigger point when its residue field is the finite field  Fp2, by an even fatter point when its residue field is  Fp3 and so on, and on. The larger the residue field, the ‘fatter’ the corresponding point.

In fact, the ‘fat-point’ signs in Mumford’s treasure map are an attempt to depict the fact that an affine scheme contains a lot more information than just the set of all prime ideals. In fact, an affine scheme determines (and is determined by) a “functor of points”. That is, to every field (or even every commutative ring) the affine scheme assigns the set of its ‘points’ defined over that field (or ring). For example, the  Fp-points of spec(Z[x]) are the solid . points on the vertical line  (p), the  Fp2-points of spec(Z[x]) are the solid . points and the slightly bigger points on that vertical line, and so on.

This concludes our first attempt to decypher Mumford’s drawing, but if we delve a bit deeper, we are bound to find even more treasures… (to be continued).

5 Comments

Connes-Consani for undergraduates (3)

A quick recap of last time. We are trying to make sense of affine varieties over the elusive field with one element F1, which by Grothendieck’s scheme-philosophy should determine a functor

nano(N) : abeliansetsAN(A)

from finite Abelian groups to sets, typically giving pretty small sets N(A). Using the F_un mantra that Z should be an algebra over F1 any F1-variety determines an integral scheme by extension of scalars, as well as a complex variety (by extending further to C). We have already connected the complex variety with the original functor into a gadget that is a couple  (nano(N),maxi(R)) where R is the coordinate ring of a complex affine variety XR having the property that every element of N(A) can be realized as a CA-point of XR. Ringtheoretically this simply means that to every element xN(A) there is an algebra map Nx : RCA.

Today we will determine which gadgets determine an integral scheme, and do so uniquely, and call them the sought for affine schemes over F1.

Let’s begin with our example : nano(N)=G_m being the forgetful functor, that is N(A)=A for every finite Abelian group, then the complex algebra R=C[x,x1] partners up to form a gadget because to every element aN(A)=A there is a natural algebra map Na : C[x,x1]CA defined by sending xea. Clearly, there is an obvious integral form of this complex algebra, namely Z[x,x1] but we have already seen that this algebra represents the mini-functor

min(Z[x,x1]) : abeliansetsA(ZA)

and that the group of units (ZA) of the integral group ring ZA usually is a lot bigger than N(A)=A. So, perhaps there is another less obvious Z-algebra S doing a much better job at approximating N? That is, if we can formulate this more precisely…

In general, every Z-algebra S defines a gadget gadget(S)=(mini(S),maxi(SZC)) with the obvious (that is, extension of scalars) evaluation map

mini(S)(A)=HomZalg(S,ZA)HomCalg(SZC,CA)=maxi(SZC)(A)

Right, so how might one express the fact that the integral affine scheme XT with integral algebra T is the ‘best’ integral approximation of a gadget  (nano(N),maxi(R)). Well, to begin its representing functor should at least contain the information given by N, that is, nano(N) is a sub-functor of mini(T) (meaning that for every finite Abelian group A we have a natural inclusion N(A)HomZalg(T,ZA)). As to the “best”-part, we must express that all other candidates factor through T. That is, suppose we have an integral algebra S and a morphism of gadgets (as defined last time)

f : (nano(N),maxi(R))gadget(S)=(mini(S),maxi(SZC))

then there ought to be Z-algebra morphism TS such that the above map f factors through an induced gadget-map gadget(T)gadget(S).

Fine, but is this definition good enough in our trivial example? In other words, is the “obvious” integral ring Z[x,x1] the best integral choice for approximating the forgetful functor N=G_m? Well, take any finitely generated integral algebra S, then saying that there is a morphism of gadgets from  (G_m,maxi(C[x,x1]) to gadget(S) means that there is a C-algebra map ψ : SZCC[x,x1] such that for every finite Abelian group A we have a commuting diagram

\xymatrix{A \ar[rr] \ar[d]_e & & Hom_{\mathbb{Z}-alg}(S, \mathbb{Z} A) \ar[d] \\ 
Hom_{\mathbb{C}-alg}(\mathbb{C}[x,x^{-1}],\mathbb{C} A) \ar[rr]^{- \circ \psi} & & Hom_{\mathbb{C}-alg}(S \otimes_{\mathbb{Z}} \mathbb{C}, \mathbb{C} A)}

Here, e is the natural evaluation map defined before sending a group-element aA to the algebra map defined by xea and the vertical map on the right-hand side is extensions by scalars. From this data we must be able to show that the image of the algebra map

\xymatrix{S \ar[r]^{i} & S \otimes_{\mathbb{Z}} \mathbb{C} \ar[r]^{\psi} & \mathbb{C}[x,x^{-1}]}

is contained in the integral subalgebra Z[x,x1]. So, take any generator z of S then its image ψ(z)C[x,x1] is a Laurent polynomial of degree say d (that is, ψ(z)=cdxd+c1x1+c0+c1x++cdxd with all coefficients a priori in C and we need to talk them into Z).

Now comes the basic trick : take a cyclic group A=CN of order N>d, then the above commuting diagram applied to the generator of CN (the evaluation of which is the natural projection map π : C[x.x1]C[x,x1]/(xN1)=CCN) gives us the commuting diagram

\xymatrix{S \ar[r] \ar[d] & S \otimes_{\mathbb{Z}} \mathbb{C} \ar[r]^{\psi} & \mathbb{C}[x,x^{-1}] \ar[d]^{\pi} \\ 
\mathbb{Z} C_n = \frac{\mathbb{Z}[x,x^{-1}]}{(x^N-1)} \ar[rr]^j & & \frac{\mathbb{C}[x,x^{-1}]}{(x^N-1)}}

where the horizontal map j is the natural inclusion map. Tracing zS along the diagram we see that indeed all coefficients of ψ(z) have to be integers! Applying the same argument to the other generators of S (possibly for varying values of N) we see that , indeed, ψ(S)Z[x,x1] and hence that Z[x,x1] is the best integral approximation for G_m.

That is, we have our first example of an affine variety over the field with one element F1 :  (G_m,maxi(C[x,x1])gadget(Z[x,x1]).

What makes this example work is that the infinite group Z (of which the complex group-algebra is the algebra C[x,x1]) has enough finite Abelian group-quotients. In other words, F1 doesn’t see Z but rather its profinite completion \hat{\mathbb{Z}} = \underset{\leftarrow} \mathbb{Z}/N\mathbb{Z}… (to be continued when we’ll consider noncommutative F1-schemes)

In general, an affine F1-scheme is a gadget with morphism of gadgets
 (nano(N),maxi(R))gadget(S) provided that the integral algebra S is the best integral approximation in the sense made explicit before. This rounds up our first attempt to understand the Connes-Consani approach to define geometry over F1 apart from one important omission : we have only considered functors to sets, whereas it is crucial in the Connes-Consani paper to consider more generally functors to graded sets. In the final part of this series we’ll explain what that’s all about.

Leave a Comment