What mathematical objects do computers really know? (Part I)

In this first post, I am coming back to the first of the two papers already mentioned in my (second) first post, which is joint work with F. Jouve and D. Zywina, and titled “An explicit integral polynomial whose splitting field has Galois group W(E8)“.

The paper’s avowed purpose is very straightforward to state: we give an explicit polynomial (call it P), monic and with integral coefficients (in fact, palindromic), of degree 240, with the stated property in the title. Here’s a PDF file containing it (if you print this file and stitch the pages together, any resemblance of the resulting outline shape with a surfboard, when viewed from afar, is entirely coincidental).

In fact, I am not going to spend much time discussing the mathematical arguments in the paper. Rather, since the proof that P does indeed have the stated properties depends on computer help, I’m going to describe how this comes about, and more importantly explain why I believe we do have a proof of our statement, which is a valid mathematical proof of it (except maybe for the most paranoid among mathematicians). Note that I’m essentially a full-blooded mathématicien platonicien, and so it is a fairly serious matter to me to be sure that there is no cheating.

Of course, there has been a lot of discussion of the use of computers in mathematical proofs, involving much more important results, but as is often the case, things can become a lot sharper in one’s mind when dealing with a specific problem, and for me this was the first time the question really arose.

[Just a few words on the mathematical background: the result is a particular case of the “explicit” Inverse Galois Problem, and the explicitness is indeed what is of interest; it has been known for a long time (though a formal statement is not easy to find) that infinitely many integral polynomials exist with splitting field the group W=W(E8), and in particular Shioda described a way to find, in principle, all such polynomials. Várilly-Alvarado and Zywina have managed to create concrete examples from Shioda’s method, but the coefficients of the ones they obtained are huge. Ours can be seen as rather reasonable in a way (the largest coefficients have about 100 decimal digits). Our construction is based on completely different ideas, where the origin of the “low complexity” is pretty clear: the principle is that, given a “generic” matrix in some (algebraic) matrix group G, with rational coefficients, the Weyl group of G is typically going to be the Galois group of the splitting field of the characteristic polynomial of this matrix. Although we haven’t found formal statements of this type, it’s actually unlikely that this is very new. For instance, for GL(n), where the Weyl group is the symmetric group on n letters, this principle is more or less obvious (but not necessarily easy to prove!). We apply this to the exceptional group of type E8 (which can be seen in a natural way as a subgroup of GL(248)), and to get a sufficiently generic element, we follow the idea of random walks: we take some elements in E8(Q), multiply them, and manage to check that the resulting matrix works. We multiply very simple matrices (analogues of the elementary matrices in GL(n), as I’ll describe a bit in more detail in the second part), and few (in fact, 16) of them, so the resulting matrix has small coefficients, which explains the low complexity of our polynomial.]

To describe how our result depends on computer help, recall first that the Galois group (say G) of P can be seen in a natural way as a group of permutations of its 240 roots. Similarly, it turns out that W can be seen as a permutation group of 240 objects, which may be interpreted either as the vectors of minimal (non-zero) length in the lattice (which is often also denoted E8, though here this would only create confusion) of which it is the automorphism group, or as the so-called roots of the exceptional group E8 with respect to a chosen maximal torus (and you may find confusing this use of the same word “root” for two apparently very different things, but in fact it is precisely because of the link with zeros of characteristic polynomials that the terminology was introduced in Lie theory…)

So, roughly, we must check that the Galois group (say G) of P is (1) not smaller than W; (2) not bigger than W. Both facts require some computer help, but in very different ways. I’ll discuss (1) now, and (2), which is more significant, in another post.

For (1), the Magma mathematical software is used as some kind of database holding extensive information about W, and able to perform computations in it. Since W has order about 700,000,000, some mechanical help may seem indispensible, but in fact there is some chance that a pure thought proof of this first part could exist. And even if some computations are needed, one shouldn’t think it is impossible to get one’s hand (usefully) dirty with W: Élie Cartan, in 1896, computed its Jordan-Hölder series (there is a normal subgroup of index 2, and the quotient has a normal subgroup of order 2, with quotient simple, in fact isomorphic to an orthogonal group of dimension 8 over the field with 2 elements), and it’s safe to assume that he couldn’t just use his laptop for this purpose.

We get information on the “size” of G by looking at the factorization pattern of P modulo primes: it is a standard, and very useful, fact of algebraic number theory that if P has no repeated root modulo a prime p, and factors as a product of n1 distinct linear factors, n2 distinct irreducible quadratic factors, and so on, then as a subgroup of the permutation group of the roots, G contains a permutation which is product of n1 1-cycles, n2 (disjoint) 2-cycles, and so on.

Now, the computer knows about all (conjugacy classes of proper) maximal subgroups of W, and for each of them (say H), knows the cycle types of all conjugacy classes of elements of H. If by reduction modulo primes we find cycle types which do not all occur in such a maximal subgroup, then it is not possible that G be isomorphic to a subgroup of W. This is what happens when reducing modulo 7 and 11 (no more!). Note that here it is assumed implicitly that the cycle types which arise from reduction of P correspond to cycle types of element of W; this is not obvious a priori, and is in fact linked with the second part of the proof, and so I’m leaving some explanation for the second post. (For some context: there are only 112 conjugacy classes in W; they can be described in an abstract way which makes them manageable, as done by Carter for all Weyl groups).

At first, this fact looked just like a lucky coincidence, highly dependent on being able to list the data mentioned above (maximal subgroups and their conjugacy classes). However, a closer look shows that we got (by luck, maybe) some not so random conjugacy classes. The first one is the square of the so-called Coxeter class c. Now, the latter is very canonical (it can be defined for all finite reflection groups, at least, and for the symmetric group on n letters, for instance, it is the class of the n-cycles), and it has many interesting properties.

The second conjugacy class is less remarkable, but is in fact the biggest in W (which certainly explains why it comes out so easily!), and the only property we need is that it is an odd permutation (any other odd permutation would do). Now, of course, the other class c2 is an even permutation, and so what we actually need about W is the following:

Fact of life: Let G be a proper subgroup of W, the Weyl group of E8, containing an element in the conjugacy class c2. Then G is contained in the kernel of the signature homomorphism.

(Note that the signature can be defined on W without referring to the embedding in the permutation group of 240 objects).

This statement (to me) seems reasonable enough that a direct proof could well exist (it does seem somewhat surprising, on the other hand). And, in a way, such a proof already exists: using the Jordan-Hölder series of W, one can check this using the printed Atlas of Finite Groups, and hence depend only on standard mathematical arguments and published literature, which is at least the usual standard of mathematical proof. But maybe there could be an argument even more conceptual.
Now, with this done, let’s wait until the next post to discuss the second part of the proof…

On Murphy’s law…

Welcome to the second version of my first blog. The first version turned out to be quite ephemeral since the ETH blog database failed on Friday in some way, leading to its utter destruction. Hopefully this one will last longer, and at least I will try to backup more carefully (by chance, I didn’t lose anything, but that’s only because I had an open window with all the content at work…)

Anyway, here’s what I said in the first post of the first blog:
Before writing a “real” post, I will just point out my home page at ETH, and in particular the list of papers and preprints, where I have recently added two articles, which I will probably describe later on:

(1) An explicit integral polynomial whose splitting field has Galois group W(E8), (joint work with F. Jouve and D. Zywina) which does pretty much what the title says…

(2) The large sieve, monodromy and zeta functions of algebraic curves, II: independence of the zeros, where the issue of relations between zeros of L-functions is investigated in the case of finite fields, with the help of sieve methods and the Riemann Hypothesis of Deligne.