The Southwestern Center for Arithmetical Algebraic Geometry

Arizona Winter School 1999
Cremona's Project Description

Let me tell you more about what I expect us to be doing during the Winter School. I am still not entirely sure what will or will not work out: one reason for me choosing conics (genus 0 curves) as a topic for you is that we want to actually implement at least one (preferably two) methods of solving them in at least one (preferably at least two) systems / packages. The complete solution will be split up into various stages. For simplicity we will take the input equation to be ax2+by2+cz2 with a>0, b>0, c<0.

  1. Check whether a solution exists. This does require factoring a, b, c, and while we are doing this we can reduce to the case where they are squarefree and pairwise coprime. Output of this stage will include explicit soluions to the three congruences x2=-ab (mod c) etc.
  2. Finding one solution. Either some version of a reduction (recursive) procedure (where some "small" cases will need special treatment), or a 3D lattice reduction method.
  3. Finding a small solution given any solution. This should not be necessary after a 3D lattice method, but will be after a reduction method. Here we can use Mordell's method, as in my preprint, or a better (faster) method I have not yet written up but can explain.
  4. Finding an optimal parametrization of the solutions by quadratics, as in my preprint. (My new method for (3) requires doing this first as it works by reducing positive definite quadratics).

Along the way, you will learn about many algorithms of widespread use, including lattice reduction in 2 and 3 dimensions, reduction of positive definite binary quadratic forms, modular square roots, etc. I have no idea how much of this any of you know already, either as theory or algorithmically. Not all, I hope! We will NOT need to know anything about factoring algorithms, as all the systems we may use can do this efficiently (but not efficiently that it will not be important to eliminate all unnecessary factorization from our implementation).

There are several ways in which we can implement these things, using various pieces of software. I will give an overview of these in some of my talks, for the benefit of all participants, but you are the ones who will learn at least one in quite a lot of detail. You will get some choice in which one you end up using. Originally I though of having you in two pairs working together. Now there are 5 of you we either have someone on their own (perhaps one of you has quite a lot of previous computing experience) or split as 2+3. The possible systems are:

  1. Maple. This has a built-in command for solving our equation, but it is very inefficient for large problems and gives huge solutions even for moderate problems. So here you would end up with a better procedure in Maple than the built-in one -- which (maybe after some more work after the School) might be good enough to offer to Waterloo Maple Software to include in their next release! I do have such a Maple programme already, some or all of which could be pirated in emergency.
  2. PARI/GP. This is an enormously useful (and free) package for doing many kinds of computational number theory, so is well worth getting to know in any case. PARI has a high-level programming / calculator interface (GP) which is not hard to learn, which we would use rather than programming in C (which is also possible with PARI). Advantages are many built-in functions, such as lattice reduction and modular square roots.
  3. LiDIA/LC. LiDIA is a C++ library for number theory, which I have used extensively as almost all my programs are rwitten in it. You should probably only opt for this if you have done some programming before, in C or C++ (or Pascal, but then you will have more to learn). It would be fine to have a pair of which only one had such experience, as then the other would learn. Also, some experience with general unix programming tools would be an advantage, but is not absolutely necessary provided that you know the basics of editing files as you can learn how to run compilers, or we can set things up so that that side is fairly automatic (using "make"). An alternative here is to use the interactive interface to LiDIA called LC, which works like an interactive version of C augmented by all the special functions of LiDIA.

That's probably enough choice. I will mention other packages in my talks (Magma, Mathematica, Kant/Kash, ...), but they are either not installed and/or I have little or no experience with them, so it would be better for you not to use them (this time) or you will get no help! The ones I have mentioned are all installed on a machine at UA which we will all have access to, and I will ask Doug Ulmer to set you up accounts there so that you can start to try things out before the School starts. There is good online help for all of these, as well as some documentation which you can read in html or ps format.

If any of you particularly wanted to it might be possible as an alternative to solving conics to implement a 2-descent via 2-isogeny for elliptic curves over Q, as described in my book (was that on the reading list?) There are many details here which would probably be too hard to implement in the limited time we have, including careful book-keeping of data, and solving equations of the form y2=quartic. But a rather basic version may be possible. A full 2-descent algorithm would (in my humble opinion) be much too big a project to hope to get very far with in five days.