Wednesday, December 17, 2008

Hermite forms and torsion points

I spent most of the day polishing off a paper called Heuristically Fast Computation of Hermite Normal Forms of Random Integer Matrices with Clement Pernet and Robert Bradshaw. It's about a very fast algorithm Clement and I came up with (building on lots of existing work!) to compute Hermite forms. Some interesting things happened -- first, of course, we didn't completely finish the paper today. Second, Robert nailed down a very serious but "silly" efficiency bug in our current Sage implementation that Craig Citro had introduced, which made it VASTLY slower than it should be (I had stupidly positively reviewed that patch, too). Third, as with writing any paper, we had to carefully prove several key points in the algorithm that we had brushed aside before, and some of these were quite surprising to me. For example, in computing the Hermite form of a square nonsingular matrix with determinant d, one should in fact work modulo d, not 2*d as we had done before (we had blindly followed what Allan Steel says he does in Magma, which is actually overkill). We're running a bunch of benchmarks of Sage versus Magma on one of my new Sun 24-core 128GB RAM boxes, which is very fun. If our paper is sufficiently well written, Allan will referee it and the next version of Magma will be at least as fast as our implementation, since we explain all of our tricks.

I also talked with Ralph Greenberg for a while today about the field Q(E[ell^n]) where E is an elliptic curve over Q, and we assume that the ell-adic representation is surjective. We used group and Galois theory to compute all the abelian quotients of the Galois group G of Q(E[ell^n]). One deduces that the only abelian quotient is (Z/ell*Z)^*, hence the maximal abelian subfield of Q(E[ell^n]) is Q(zeta_ell). This can be used along with the Chebotarev density theory to prove that if P is a point on E(Q) of infinite order and m is an integer divisible only by primes such that the ell-adic representation is surjective, then there are infinitely many primes p such that the reduction of P modulo p has order divisible by m. And that's interesting, since it's a step in a paper I'm writing about a generalization of the Gross-Zagier formula to higher rank. There are other ways to prove the above reduction statement, I think in more generality, which I thought through last night. But I was just very curious about the structure of G, which is why Ralph and I talked it through. The basic idea for understanding it is to use a few tricks, including that PSL_2 is simple, that there is always a square root of the matrix -1 in SL_2(F_ell), and that the kernel of reduction from SL_2(Z/ell^nZ) to SL_2(F_{ell}) is isomorphic to trace zero matrices with the conjugation action, hence a simple representation.