Computational Projects: Part 1

I made a diagram that illustrates most of the algorithms I wish Sage had to support my current mathematical research program. I am focusing most of my Sage development effort on ensuring that these get implemented as soon as possible.  I will not depend on anybody else to help me with any of this, though if people would like to help in various ways that would be greatly appreciated. Over half of these are in the closed commercial Magma software already, which makes it much easier for me to implement them in Sage.

Research Versus the Goals of the Sage Project

A concern I have is that there might be disagreement in the Sage community about some of the design decisions that are necessary to support the implementation of my planned algorithms.  For example, improving number field arithmetic to be dramatically faster requires making some sacrifices so that the implementation takes one week instead of two months (e.g., fundamentally depending on FLINT for basic arithmetic, which at least one Sage developer will be quite unhappy about).  Even though I'm the leader of the Sage project, I won't just add code to Sage that a lot of people don't like.   However, implementing everything planned here is a lot of work, and given the time and resources I have available, it will be impossible to fully document and test everything up to the standard necessary for inclusion in Sage.  If this gets to be a nontrivial problem, I will maintain my own alternative ``fork'' of Sage, which I'll distribute separately.  It will have `bleeding edge'' code that I'm developing, and I'll make full source releases available on a separate website, but I will not have to worry about constantly updating packages (like Maxima and Scipy) that are irrelevant to my research. The architecture of Sage makes creating such a fork easy, and of course I know how to manage this.  In a few years, once I've built everything and complete the research I plan to do with it, I can spend the time merging back the good parts into mainline Sage.  I know that several other Sage developers (e.g., Nick Alexander, David Roe, etc.) do something similar, since their personal research is so important to them, and getting code into Sage is overly difficult.   It is very important that I acknowledge this tension, because currently the demands of "publishing" code in Sage -- and indeed of maintaining Sage as a general purpose system -- are so tough that they make genuine development of Sage as a research tool too difficult.  Solution: create something that isn't Sage.

The Diagram

Here is the diagram.  It is a tiny picture, but if you click on it you should get a bigger PDF that you can zoom into (if you are using Linux, download this PNG instead). 

I will spend the rest of this post discussing the first few algorithms at the top of the diagram, and my motivation for implementing them. Future posts will address the rest of the algorithms.

Number Fields
The top of the diagram lists number fields, and the two projects involve greatly speeding up basic arithmetic in Sage with elements of number fields. This is important to my research, since I intend to do explicit comptutations with elliptic curves and modular forms over number fields, including making large tables, hence fast arithmetic is important. Arithmetic in some cases in Sage is ridiculously slow, especially for relative fields. Fixing this involves switching from using NTL for all number field arithmetic to using FLINT (via Sebastian Pancratz's new rational polynomials) for absolue fields and Singular for relative extensions. I spent some time on this project and the results are at Trac 9541, but the code there should not be used as is. Instead, I'll finish this project by extracting out the best ideas from those patches, and adding more. The main idea for relative number fields is to create a C interface (written in Cython!) to Singular for computing with transcendence degree 1 function fields over the rational numbers. The other lesson I learned when working on Trac 9541 is that it is orders of magnitude easier to delete all code related to using NTL for number fields instead of trying to simultaneously support several different models for numbers fields.

Function Fields

Continuing clockwise, the next cluster of algorithms involves function fields of transcedence degree 1 over the prime subfield, i.e., function fields of algebraic curves. Function fields are important for my research because an application of explicit Riemann-Roch spaces and divisor reduction is a key step in completing a paper on torsion points on elliptic curves over quartic fields that I'm writing with Kamienny and Stoll. Function field arithmetic, rings, ideals, polynomial factorization, norm, traces, ``Poppov reduction'', etc., are the subject of Trac 9054, which should be relatively easy to finish. The next step is to implement Florian Hesse's algorithm for Riemann-Roch spaces, by following the description in Florian's papers and talks on the topic. Next, I'll have to implement divisor reduction and computation of maximal orders (normalization of curves).  I suspect that Chris Hall will help. Parallel to this, it is also a good idea to use the same code as in the number field case to make basic arithmetic in certain function fields much faster than the generic code of Trac 9054.

Elliptic Curves over Function Fields

I am also interested in code for computing with elliptic curves that are defined over function fields (usually over finite fields). This is related to work of Chris Hall, Sal Baig, and others at recent Sage

Days on function fields. This code will make it easier to computationally explore function field analogues of new ideas related to the Gross-Zagier formula and the BSD conjecture. The main goals  are to implement algorithms for computing every quantity appearing in the Birch and Swinnerton-Dyer conjecture, including torsion, Tamagawa numbers, L-functions, Mordell-Weil groups (2-descent), and regulators. Also, I need to implement code for doing computations with Drinfeld modules, since Drinfled modules provide the analogue of modular curves and Heegner points in the function field setting.

Kolyvagin's Conjecture: a status report

During the Summer of 2009, I read some papers of Cornut, Vatsal, and Jetchev-Kane that were motivated by Mazur's conjecture about Heegner points. Meanwhile, I was thinking about Kolyvagin's conjecture on nontriviality of his Euler system of Heegner points. This is a conjecture about any elliptic curve E over Q along with any prime p and a fixed choice of quadratic imaginary field K that satisfies the Heegner hypothesis (e.g., each prime dividing the conductor of E splits in K). The conjecture is simply that one of Kolyvagin's cohomology classes in H^1(K, E[p^n]) is nonzero, for some n. When E has analytic rank 1 over K this conjecture holds for the class tau_1 for n sufficiently large, by the Gross-Zagier formula.

Three years ago, I wrote a paper with Dimitar Jetchev and Kristen Lauter where we gave *numerical evidence* that Kolyvagin's conjecture holds for the curve 389a with p=3, K=Q(sqrt(-7)), n=1, and tau_5!=0. But we didn't *prove* that tau_5 is nonzero. Moreover, our numerical approach was so inefficient that we couldn't have done many more examples. Nonetheless, this was good news - at least there was evidence thst Kolyvagin's construction doesn't completely degenerate for curves of rank > 1.

Last summer, when reading Cornut, Jetchev-Kane, etc., I figured out how to make some of what they do explicit and machine computable, and I implemented code. This was several weeks of focused programming work in Sage, starting from scratch, partly because I refuse to used the closed Magma math software system (which had maybe half of what I would have needed).

Anyway, running all this code for a week on my (big NSF funded!) cluster, and also Jon Hanke's at Univ of Georgia resulted in provable verification of Kolyvagin's conjecture for around 100 triples (E,K,p) with E of rank 2, and K of class number 1. I am right now working on polishing the write up of this for publication (I plan to submit the paper sometime in the next month).

At a Sage Days we had out on Lopez in late summer 2009, Jared Weinstein got interested in this project, and with some input from Karl Rubin about how to apply Kolyvagin systems, we figured out how to compute the distribution of Kolyvagin classes which massively clarified the numerical data I had obtained. He also found a completely different *conditional* algorithm to compute Kolyvagin classes: when I implemented it the results exactly matched what I got with my algorithm the previous month: nice.

In December 2009, at another Sage Days at the Clay Math Institute in Cambridge, MA, Jennifer Balakrishnan became interested in the project and ran my code (with some modifications) to verify Kolyvagin's conjecture for the rank 3 curve 5077a and p=3. The relevant quadratic imaginary field K had larger class number so we had to improve the theory a bit. The computer calculations also took many hours. Meanwhile, Jared Weinstein came up with some preliminary rank 3 analogues of his results from the previous summer, which gave Jen and me confidence that our rank 3 verification of Kolyvagin's conjecture was correct. We also plan to write a paper about this soon, but still haven't really done much (Jen has though, actually).

During the next few months (early 2010) Jared worked on refining and generalizing his density arguments, with some input from me. I also finally read the Mazur-Rubin book on Kolyvagin systems.

In June at Sage Days 22 at MSRI Jared ran a very coherent 2 week minicourse on Kolyvagin and had several students do projects making explicit subtle cases of explicit computation with Kolyvagin's Euler system when p=3. They were forced to use Magma, since they had to adapt some general 3-descent code, and there is only one implementation of 3-descent in the world: Michael Stoll's in Magma. (My student Robert Miller started along the path to a free open implementation last year, but we decided he should finish his thesis first. That said, it will be a great contribution to math when somebody finally implements a free 3-descent.) Anyway, I think their Magma computation with a modified 3-descent led to some great new data related to Kolyvagin's Euler system, I think when Sha(E/K)[3] is nontrivial.

There are a few other related directions that I haven't mentioned above. First it is possible to use similar techniques to verify the natural analogue of Kolyvagin's conjecture for modular abelian varieties of larger rank and I have done this for a few examples. It would also be interested to extend the Stein-Weinstein density business to this case. There is probably an analogue of everything for modular motives (in the sense of Scholl) and maybe Kimberly Hopkins would have some interest in this.

Another interesting direction to pursue is totally real fields. Around 2001, Zhang generalized some of the Gross-Zagier formula and also some of Kolyvagin's Euler system to this setting.  A natural Ph.D. (?) project is to generalize enough to state an analogue of Kolyvagin's conjecture, then verify the conjecture in at least one case of a curve of rank 2. This will inevitably involve Hilbert modular forms, and certain explicit computation with quaternion algebras over a totally real field. Currently all existing code in this direction is in Magma, so step 1 is to understand enough of the recent work of Voight and Dembelle to implement open source code in Sage (it appears neither Dembelle or Voight have any plans to do this, unfortunately). But for this project doing only one single verification of Kolyvagin means that one doesn't have to write very general code, so this should be much easier than a general implementation (which would likely take at least a year fulltime work). Probably my Ph.D. student Aly Deines will take on this project.

I will close this blog post with some remarks about the whole point of this line of investigation. In first learned about Kolyvagin's conjecture from Christophe Cornut back in 2001 when we were both B.P. Assistant Professors at Harvard together. At the time, I think Christophe was perhaps trying to prove the conjecture, maybe using similar tools (e.g. Ratner's theorem) to what he used to prove Mazur's conjecture on nontriviality of Heegner points. I only wondered about verifying the conjecture in a few cases later in 2007, since I started wondering about BSD for rank 2 curves, and it is natural to wonder whether or not Kolyvagin's approach just falls apart for rank 2 or not. (Answer: it doesn't!) Anyway, I stumbled on a way of checking the conjecture computationally in specific cases, and this has led to some potentially interesting questions and results that explain the computations. Also, one gets a new algorithm to compute something about Selmer groups, which applies in some cases where p-adic techniques don't, e.g. additive primes.

I personally do not think anything mentioned above will prove Kolyvagin's conjecture in general. I.e. the above techniques are very unlikely to say anything much about the question that Cornut was attacking back in 2001. I published in IMRN a (fairly naive and formal!) conjectural analogue of the Gross-Zagier formula for arbitrary rank. This is in a totally diffent direction to the work of Zhang, Yang, etc. generalizing Gross-Zagier.  A "suitably form" of this conjectural formula does imply Kolyvagin's conjecture (and the full Birch and Swinnerton-Dyer rank conjecture). I personally think the most likely way in which Kolyvagin's conjecture will be proved is that somebody will prove something nontrivial toward the above mentioned generalization of Gross-Zagier.