Skip to content →

Category: number theory

Aaron Siegel on transfinite number hacking

One of the coolest (pure math) facts in Conway’s book ONAG is the explicit construction of the algebraic closure $\overline{\mathbb{F}_2}$ of the field with two elements as the set of all ordinal numbers smaller than $(\omega^{\omega})^{\omega}$ equipped with nimber addition and multiplication.

Some time ago we did run a couple of posts on this. In transfinite number hacking we recalled Cantor’s ordinal arithmetic and in Conway’s nim arithmetics we showed that Conway’s simplicity rules for addition and multiplication turns the set of all ordinal numbers into a field of characteristic zero : $\mathbb{On}_2$ (pronounced ‘Onto’).

In the post extending Lenstra’s list we gave Hendrik Lenstra’s effective construction of the mystery elements $\alpha_p$ (for prime numbers $p$) needed to do actual calculations in $\mathbb{On}_2$. We used SAGE to check the values for $p \leq 41$ and solved the conjecture left in Lenstra’s paper Nim multiplication that $(\omega^{\omega^{13}})^{43} = \omega^{\omega^7} + 1$ and determined $\alpha_p$ for $p \leq 67$.


Aaron Siegel has now dramatically extended this and calculated the $\alpha_p$ for all primes $p \leq 181$. He mails :

“thinking about the problem I figured it shouldn’t be too hard to write a dedicated program for it. So I threw together some Java code and… pushed the table up to p = 181! You can see the results below. Q(f(p)), excess, and alpha_p are all as defined by Lenstra. The “t(sec)” column is the number of seconds the calculation took, on my 3.4GHz iMac. The most difficult case, by far, was p = 167, which took about five days.

I’m including results for all p < 300, except for p = 191, 229, 263, and 283. p = 263 and 283 are omitted because they involve computations in truly enormous finite fields (exponent 102180 for p = 263, and 237820 for p = 283). I'm confident that if I let my computer grind away at them for long enough, we'd get an answer... but it would take several months of CPU time at least. p = 191 and 229 are more troubling cases. Consider p = 191: it's the first prime p such that p-1 has a factor with excess > 1. (190 = 2 x 5 x 19, and alpha_19 has excess 4.) This seems to have a significant effect on the excess of alpha_191. I’ve tried it for every excess up to m = 274, and for all powers of 2 up to m = 2^32. No luck.”

Aaron is writing a book on combinatorial game theory (to be published in the AMS GSM series, hopefully later this year) and will include details of these computations. For the impatient, here’s his list






Leave a Comment

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

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

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