William suggested that I wrote a paragraph or two describing what
would be involved for the S-integral points implementation. I have
not done so yet, but this email might contain enough to get someone
started, I spent some time yesterday looking up the literature on
this, and there is quite a lot of it.
Here are the basic parameters: A field K, which can be Q to start
with; a set of primes of K, which can be empty to start with; an
elliptic curve E defined over K, for which a basis for the
Mordell-Weil group is known. The output is the finite set of points
of E(K) which are S-integral (meaning that the coordinates are
S-integers, i.e. are integral at all primes not in S). It's an old
result that this is a finite set.
Classical Diophantine methods can be applied in which case you don't
need the MW basis since you don't use the elliptic curve structure at
all. The bounds then come from bounds on linear forms in logarithms
from analytic number theory. They are exponential and not of much
practical use, I think (though I am not an expert in that, and indeed
one of John Coates's first papers in number theory was an effective
form of this result).
The new methods come from using linear forms in elliptic logarithms,
with bounds proved by Sinou David in the 1990s. There are several
papers which make this more or less explicit (try typing "S-integral
points" into Google to save me listing them all.
The simplest case is K=Q and S={}. Here I would strongly recommend
the section in Henri Cohen's new book (volume 2, last section of last
chapter) where he gives every last detail and a worked example. Then
go on to general S, still with K=Q. I believe this is covered in
Nigel Smart's book on Diophantine Equation solving (I even asked Nigel
earlier this evening, and he seemed to think it did). There are also
some tricks which give better bounds for curves of small rank. For
general number fields there is the paper of Stephens and Smart, but it
leaves out some details; and various papers by Petho, Zimmer,
Herrmann et al. Herrmann is the person who wrote the Magma
implementation (for K=Q only). He also implemented the general case
in Simath, and he might be willing to donate his code. He once told
me that he intended to port it to Magma, but I think he no longer
works in research.
A very rough sketch of the method is that you first get from the
elliptic log bounds a bound K on the coefficients of an S-integral
point P when expressed as a sum P = \sum_{i=1}^{r}n_i P_i where the
P_i are the generators, so that for P S-integral then max|n_i| <= K.
Typically that K is huge. But then an LLL trick (due to de Weger)
enables you to go from a lager bound to a much smaller one. Then you
repeat this (it's magic) until you get no further improvement. With
luck you are then down to something like K=10 which leaves you only
21^r points to look at. [I have ignored torsion here for simplicity.]
Anyway, step 1 is to implement the easiest case from Cohen's book,
which should not be too hard, and we can develop things from there!
John
On 21/11/2007, William Stein <[EMAIL PROTECTED]> wrote:
>
> On Nov 21, 2007 8:11 AM, sms <[EMAIL PROTECTED]> wrote:
> > thanks for inviting me to become a member here!
>
> Welcome to sage-devel!
>
> >
> > David: I am working in Algebraic Geometry (algebraic cycles and K-
> > theory) mainly but teach almost entirely number theory and hence
> > essentially only give away thesis topics in number theory. By the way
> > I got into all this after writing
> > a little python package for symbian series 60 phones (google for
> > python math lab) which two of my students help
> > developing meanwhile.
>
> That's pretty cool. Could you change the title of the link to Sage on the
> "python math lab" webpage from
> " SAGE: System for Arithmetic Geometry Experimentation, a CAS
> developed by William Stein et.al."
> to
> " SAGE: Open Source Mathematical Software, a Python-based CAS
> developed by William Stein et al."
>
> Thanks.
>
> > To involve them into developing parts SAGE
> > is an experiment though, hence it would be good to let them work on
> > less time-critical things and be patient. It might even be better to
> > give away such task in seminars where they usually work only for a few
> > weeks on a subject.
>
> I like that idea.
>
> > John's suggestion (S-integral points) seems very interesting and if I
> > may I would like to suggest it to a student. Also Edwards coordinates
> > seem to be a nice option. Otherwise I will follow William and suggest
> > that they choose their own topic and go ahead and compare with MAGMA.
> > At the end we can see whether there is a contribution.
>
> Sounds good. Regarding S-integral points, it would be best to break the
> project up into several subtasks (I'm not sure what the subtasks are).
>
> -- William
>
> >
>
--
John Cremona
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
