numbers

Lambda-rings for formula-phobics

Feb 5th

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),\boxplus,\boxtimes)$ requires only one identity to remember

$~(1-at)^{-1} \boxtimes (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 \Lambda(A)$

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

$\gamma(u(t) \boxplus 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+\hdots$

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

Print Friendly

fun, Grothendieck, lambda rings, Lenstra, numbers

big Witt vectors for everyone (1/2)

Feb 2nd

Posted by lievenlb in geometry

2 comments

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

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

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

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

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

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

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

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

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

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

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

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

$u(t) \boxtimes v(t) = ((1-a_1t)^{-1} \boxplus \hdots \boxplus (1-a_k)^{-1}) \boxtimes ((1-b_1t)^{-1} \boxplus \hdots \boxplus (1-b_l)^{-1})$

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

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

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

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

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

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

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

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

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

Print Friendly

fun, Galois, geometry, google, Grothendieck, groups, lambda rings, Lenstra, numbers, Riemann, Witt

The odd knights of the round table

Jan 28th

Posted by lievenlb in games

No comments

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

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

The connection between $\overline{\mathbb{F}_2}$ and the odd roots of unity has been advocated by Alain Connes in his talk before a general public at the IHES : “L’ange de la géométrie, le diable de l’algèbre et le corps à un élément” (the angel of geometry, the devil of algebra and the field with one element). He describes its content briefly in this YouTube-video

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

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

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

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

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

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

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

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

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

If m is odd, then (2,m)=1 and so 2 is a unit in the finite cyclic group $~(\mathbb{Z}/m\mathbb{Z})^*$ whence , so the m-roots of unity lie within those of order [↩]

Print Friendly

arxiv, Connes, Conway, fun, Galois, games, geometry, ONAG, ordinals, simples

On2 : extending Lenstra’s list

Jan 27th

Posted by lievenlb in games

No comments

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 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 let f(p) be the smallest number such that 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 be a natural number, the smallest prime number dividing and the highest power of dividing . 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 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 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) :

$\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}$

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 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 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 has order in $\mathbb{F}_{2^4}$ we know that $\kappa_5$ has order . 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
259144476645069239839415478030722644334257066691823210120548345667203443
317743531975748823386990680394012962375061822291120459167399032726669613
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(outmn) ...: m=F2(mnmn) ...: 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…)

$\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}$

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…

Print Friendly

Conway, mac

On2 : Conway’s nim-arithmetics

Jan 26th

Posted by lievenlb in games

No comments

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 $\wis{On}_2$ by imposing the ‘simplest’ rules which make $\wis{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 $\wis{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 = \wis{mex} \{ \alpha'+\beta,\alpha+ \beta'~|~\alpha' < \alpha, \beta' < \beta \}$

where $\wis{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. , 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 ).

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} + \hdots + 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 = \wis{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 $\wis{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 $\wis{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, ), 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,

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 is the number of primes strictly smaller than (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 \N$ .

Now, $\alpha$ can be written uniquely as $[\omega^t.n_t+\omega^{t-1}.n_{t-1}+\hdots+\omega.n_2 + n_1]$ with t and all n_i natural numbers. Write each n_k in base where is the k+1 -th prime number, that is, we have for $n_0,n_1,\hdots,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 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 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 $\wis{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!

Print Friendly

Conway, games, simples

numbers

Lambda-rings for formula-phobics

big Witt vectors for everyone (1/2)

The odd knights of the round table

On2 : extending Lenstra’s list

On2 : Conway’s nim-arithmetics

My latest tweets

Blogroll

Series of posts

Who's Online

About Me

numbers

Lambda-rings for formula-phobics

big Witt vectors for everyone (1/2)

The odd knights of the round table

On2 : extending Lenstra’s list

On2 : Conway’s nim-arithmetics

My latest tweets

User Login

Blogroll

Series of posts

Who's Online

About Me