Modulo Errors

As I continue to try and get a grasp of heights on elliptic curves, I’ve been looking into the various techniques available for computing them. Since the literal definition as a limit is unworkable, it is common to follow the approach of Silverman and consider the archimedean and nonarchimedean heights in turn. This isn’t too difficult to implement (it’s given in Cremona’s book as well as Silverman’s paper¹), but requires a switching process to avoid certain technical wrinkles. An unpublished paper by my supervisor gives a variation on the theme which avoids the switching; I managed to get both working - and agreeing - in Maple fairly easily.

However, there is a radically different approach possible using Elliptic Divisibility Sequences. These a priori needn’t have anything to do with elliptic curves: they’re simply a type of sequence governed by a not-too-unpleasant rule for iteration: plenty of information on them is available from Graham Everest’s homepage. What’s remarkable, however, is that given an elliptic curve a sequence can be defined which allows you to recover the height of points on that curve. There are numerous advantages to this: it doesn’t matter whether you’re working over the rationals or some other number field; you needn’t have a minimal equation for the curve; and computation is essentially mechanical, as the algebraic geometry is hidden from view. For instance, to follow Silverman’s approach (or variations) it is necessary to factorise the discrinant of the curve to establish primes of bad reduction- this may take up the lions’ share of computation time, but isn’t needed when working via EDS.

There are however sacrifices to be made regarding efficiency or accuracy. Searching for points of very small height clearly only requires a few decimal places of accuracy to indicate whether you’re on the right track; but working purely from the definition of an EDS even this can be cripplingly slow to obtain. Thus, guided by Rachel Shipsey’s PhD thesis², I’ve been trying to create a useful implementation in Maple. The fruits of my labour can be obtained here; they’re still not perfect, as a couple of the examples given by Everest and Ward still cause things to grind to a halt.

Nonetheless, they chew through the others quite happily, and are a lot simpler to use than they were to write! To get started, simply run eds_init with three arguments- the second, third and fourth terms of your sequence. Terms 0 and 1 are assumed to be 0 and 1, for a ‘proper’ EDS. Then, a call to termk(n) will give you the nth term of the sequence. You’ll find that globally there’s a vector h storing all known terms, and another h_known indicating just which those are: typically (and preferably) not all of them, since with Shipsey’s techniques determining the six neighbours of a term h_n allows for a jump to the terms h_2n (or h_2n+1) and its neighbours. In this way, a double and add approach can be employed to obtain a desired term efficiently. There’s still room for improvement here, since this is only the case k=1 from Shipsey’s algorithm: knowing larger factors k allows yet greater jumps through the sequence (to h_2kn from h_k and h_n etc). I’m also tempted to try coding them in PARI instead; I think Maple is stumbling more on performing calculations such as finding norms and gcds than determining the terms themselves, and PARI may be better suited to these.

To get an estimate of the height (as described by Everest and Ward³) , use height_everest(n,d,acc,x,y): n is term of the sequence you wish to work with (the higher the better but slower); d should be the degree of the field etension over the rationals; acc is the level of accuracy (in decimal places) passed to Maple’s eval function during the approximation of the logarithm; whilst x and y are the coordinates of the point of interest.

References

1: Silverman- Computing heights on elliptic curves. (MathSciNet entry)

2: Shipsey- Elliptic Divisibility Sequences (Download)

3: Everest, Ward- The canonical height of an algebraic point on an elliptic curve. (MathSciNet entry) (Download [PS])

This entry was posted on Friday, December 15th, 2006 at 4:35 pm and is filed under Algebraic Geometry, Maple, Number Theory, PhD.