Category: Computers

A while back I mentioned the usefulness of version control software in my work (see also the current discussion at the Secret Blogging Seminar). Now here is a True Life example of what it can do: Vijay Patankar wrote to me today, pointing out that in my paper Weil numbers generated by other Weil numbers and torsion fields of abelian varieties, I claim (misquoting slightly for typographical reasons):

Remark 3.9. In [K1], the question of the “splitting behaviour” of a simple abelian variety A/Q at all primes is also raised: is it true that the reduction modulo p of A remains simple for almost all p? In fact, the “horizontal” statements of Chavdarov can already deal with this. For instance, this property holds if A/Q has the property that the Galois group of the field Q(A[n]) generated by the points of n-torsion of A is equal to Sp(2g,Z/nZ) for any sufficiently large prime n.

Here, the citation [K1] refers to my earlier paper Some Local-Global Applications of Kummer Theory, but as he pointed out, the question is not mentioned anywhere there… So where did it go?

I have no memory at all of what happened, but thanks to SVN’s history facility, I have been able to reconstitute the outline of this nanoscopic academic drama: first, in late 2001, I added a remark about this problem in the final section, among other questions suggested by the paper:


r416 | emmanuel | 2001-09-13 08:52:44 +0200 (Thu, 13 Sep 2001) | 3 lines
416 emmanuel \item Given an abelian variety $A/k$ over un number field, how does
416 emmanuel its decomposition in simple factors relate to that of its reductions
416 emmanuel in general? In particular, assuming $A$ to be $k$-simple, is the set
416 emmanuel of primes $\ideal{p}$ with $A_{\ideal{p}}$ reducible finite, or of
416 emmanuel density $0$?

Here, the first line is an excerpt from the log file which records the history of every file under version control (it is produced by the svn log command); the number 416 is the “revision number” which identifies at what point in time the changes corresponding to this “commit” were made.

The next lines (which, in fact, come chronologically first in the unraveling of the mystery, as they tell which revision number to look at to find the exact date) are obtained by the svn blame command: for each line of a file, this indicates (1) at which revision the line was added (or last changed); (2) who did the change.

Then, in late 2002, just before sending the corrected version to the publisher, I commented out this question:

r1831 | emmanuel | 2002-11-14 21:16:41 +0100 (Thu, 14 Nov 2002) | 2 lines
1831 emmanuel %\item Given an abelian variety $A/k$ over un number field, how does
1831 emmanuel % its decomposition in simple factors relate to that of its reductions
1831 emmanuel % in general? In particular, assuming $A$ to be $k$-simple, is the set
1831 emmanuel % of primes $\ideal{p}$ with $A_{\ideal{p}}$ reducible finite, or of
1831 emmanuel % density $0$?


I still don’t know why I ended up doing this; indeed, two years later, I was convinced I had not done so, when I wrote the excerpt above from my other paper (the date can again be determined using SVN). In passing, this confirms the principle (which I try to adhere to usually) that one should always give a complete detailed reference to any outside work – even if it’s your own.  If I had taken the trouble of trying to locate the page or section number for this question, I would have realized it was missing…

Finally, if the question seems of interest, this paper of Murty and Patankar develops it further.

When writing my papers (and for many other things), I have been using some kind of version control software since about 1999. Among other things, what version control does is to allow you to preserve as many intermediate versions of your work as you want; any time I reach a point that I may want to preserve, a suitable command indicates that the current state of things must be remembered. Later on, it is also easy to recover those intermediate stages, and/or to compare one of them to the current state of the work (or indeed to compare two of the previous stages directly). In particular, it is useful to tag a paper as soon as it is submitted for publication. Then, even if I make changes or corrections while waiting for the refereeing process to slowly snail itself to send a report back, it remains very easy to look back (one, two, three or four years later) to check what was the exact text I had sent to the journal.

Version control is of course also particularly useful when collaborating because no amount of mistyping can lead to a situation where local changes by me erase a brilliant ten page development by a co-author (well, not really, since it is a theorem that for any computer there is a finite combination of letters which, typed properly, will erase everything on it…). It was particularly useful when I was translating into English a friend’s book on methods of mathematics for physicists. We both had the software configured so that any changes could be communicated to the other by asking the software for what had changed between our local copy and the reference version it controls. Since there were around a hundred source files for this book, including copies of the French original and of the (sometimes partially translated) English versions, plus figures, control files, etc, this was really convenient.

It is unfortunately not so trivial to set up version control, which is more commonly used by computer scientists for their projects (source code replacing LaTeX files). It should be fairly easy for a university to offer this as a service to its faculty (ETH, for instance, has something like this for software — anyone can register a software project at origo.ethz.ch and this platform provides all that is needed, including version control, bug tracker, forums for interaction with users, access control for closed-source projects, wiki,…) but it doesn’t seem to be common for more academic work. (It could of course be a good project to adapt the system to this type of situation).

After moving to ETH, the setup I had been using in Bordeaux for about 8 years was not easily reproducible, and it took me a while here in Zürich to arrive at a smooth operation. (It’s still not quite as nice as before, but it’s getting there). I use the svn software for version control (with Linux), mostly for historical reasons (I know there are many other options). For local work on a single computer, the setup would be quite simple, but part of the point of this exercise is that I can keep multiple copies of my (past and present) work on different computers, and continue writing any paper on any of them, submitting the changes to a central server from which they can be recovered on all the others (this is useful also for backup, and during travels; if I make changes on some important files on my laptop during a conference or a visit to wonders of the earth, I can usually expect to be able to save it to the central server when I have internet access, and thus avoid losing too much if the laptop is destroyed or stolen — which has happened to me once…).

The main configuration issue is to have this server accessible from other computers in a semi-permanent manner. My setup in Bordeaux did not translate well to Zürich (partly for reasons of complexity and having forgotten part of the operating procedure…) However, the following works fine for the moment: I use a VPN connection to ETH to connect to the internet, which provides an IP address visible from the outside, even from behind a router/firewall. Then dyndns allows me to keep a permanent URL to access the server (which runs on an Apache web server with the required SVN module to permit access, and fortunately I just had to copy the old configuration file to make this work…)

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(E₈)“.

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(E₈), 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 E₈ (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 E₈(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 E₈, though here this would only create confusion) of which it is the automorphism group, or as the so-called roots of the exceptional group E₈ 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 n₁ distinct linear factors, n₂ 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 n₁ 1-cycles, n₂ (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 c² 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 E₈, containing an element in the conjugacy class c². 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…