More on Elliptic Divisibility Sequences
October 18th, 2007Last time, I gave some procedures to generate an elliptic divisibility sequence from a point of an elliptic curve, the motivation being that the growth rate of the sequence corresponds to the height of the point- and thus we can compute heights by computing terms of the sequence.
But what about going the other way? Given that we seek points of low height, can we search more intelligently by crafting sequences with a small growth rate, rather than simply mapping from (typically uninteresting) random points to their sequence? The easiest way to achieve this would be to start from the sequence, rather than from the point- but that requires a means to recover the point from the sequence.
Fortunately, Ward’s Memoir1 provides just such a technique, although presented in terms of elliptic functions (the complex analysis way to view elliptic curves). Recall that to define a sequence, we need only specify the second, third and fourth terms h2, h3 and h4. Then the corresponding point is (X,Y) on curve E: Y2=4X3 -g2X -g3, given by the following unpleasant formulae:
However, these needn’t be integral, and it’s preferable to rescale to eliminate that X3 coefficient. Fortunately both of these problems can be solved by clearing denominators, leading to a more pleasant representation of the point and curve. My basic algebra being as rusty as it is, this procedure me a surprisingly long time to figure out in the general case, but I have now added suitable features to my eds SAGE class. For such an object X, a call to X.ward_point() will return a point of an elliptic curve: you can extract the curve from a point P in SAGE by P.curve(). There’s a slight issue in that an EDS may define a singular curve: I’ve caught this exception, and in such a case you’ll get back the integer zero instead. I needed this to prevent large searches over EDS from crashing when such a sequence arose from the parameters, but it’s a bit of an ugly solution.
Given a method to turn sequences into points, the obvious question is whether it acts as the inverse to the creation of sequences from points. The answer turns out to be, almost! Extra scaling factors creep in to the sequence terms each time you loop through a cycle of EDS→point→EDS. The larger the terms, the greater the time/space requirements for manipulation of the sequence; this also has a knock-on effect on the approximate height computed. However, this can be fixed for curves over number fields: considering field elements as polynomials, rescaling each of h2,h3,h4 to have content 1 recovers the original EDS. I offer no mathematical justification for this other than that it works! Thus heights now also includes EDSfromPoint_nf to generate EDS by just such a scaling.
Armed with these techniques, it’s now easy to generate curves of moderately small height that would otherwise be presumably difficult to stumble upon: for instance, with u=1+√2, the curve over the number field Q(u) given by y2=x3 + (-432u-864)*x + (-1728u+6480) has a the point (24-12u,108) of height around 0.0107. This unlikely looking curve arises from the much simpler EDS with defining terms -1,u-1,2u-2, found after a search over sequences from K with small terms that took about an hour. Considering how easily it was found, this compares favourably to the lowest known height over Q of about 0.0045. However, in the context of the Elliptic Lehmer problem heights should be scaled by the degree of the field extension, so to set a record a value of around 0.002 is needed for quadratic extensions such as K. So the search continues…
References
1: Morgan Ward- Memoir on Elliptic Divisibility Sequences (MathSciNet entry)