A paper has recently appeared which shows how EDSs can be used to search for small height points in connection with the elliptic Lehmer problem. So we start by recalling the statement of this problem. For an excellent introduction to elliptic curves, consult Joe Silverman's two books The Arithmetic of Elliptic Curves and Advanced Topics in the Arithmetic of Elliptic Curves.
Let E denote an elliptic curve defined over an algebraic number field K. As usual, we denote the addition on the group E(K) of K-rational points of E by + and the group identity as O. Then O is the point at infinity on the projective curve. There is a function h called the global canonical height which satisfies the properties:
(1) for all P,Q in E(K), h(P+Q)+h(P-Q)=2h(P)+2h(Q),
(2) h(Q)=0 if and only if Q is a torsion point.
Property (1) is called the parallelogram law. This height function is the analogue of the usual height of an algebraic number, which we will review later. In particular, problems such as the Lehmer problem are thought to have analogues. Although refinements of the basic problem exist, we can state the elliptic Lehmer problem as the following. Let d denote the degree of the field K. Then there is a constant c>0 which does not depend on E,K or Q such that
h(Q) > c/d provided Q is not a torsion point.
Before we give some examples, it will help to agree some notation. An elliptic curve is given by a Weierstrass equation,
y2 + a1xy + a3y = x3 + a2x2 + a4x + a6.
This equation is usually codified in terms of the coefficients as a vector [a1,a2,a3,a4,a5]. A (non-identity) point is usually written [x,y]. In the pari-GP calculator, this is the way to enter curves and points.
Suppose K=Q the field of rationals and Q lies in E(Q). The elliptic Lehmer problem implies that the global heights of all non-torsion rational points are uniformly bounded below. What are the smallest values currently known? The following were extracted by Noam Elkies from tables of elliptic curves made by John Cremona and they show how small the height can be.
1.E is [0,0,0,-412,3316], Q=[-18,70] has h(Q)=.00563..
2.E is [0,1,1,-310,3364], Q=[-19,-53] has h(Q)=.00670..
3.E is [1,0,0,-1415,20617], Q=[-26,213] has h(Q)=.00926..
The Elliptic Divisibility Sequence generated by 1. is
0,1,140, -1372000, -268912000000,1844736320000000000,...
It is sequence A058939 in The On-Line Encyclopedia of Integer Sequences maintained by Neil Sloane. Recently, Elkies has posted a list with some even smaller heights.
Silverman has a fast algorithm for computing heights of rational points on elliptic curves. There are no versions of Silverman's algorithm currently implemented over general number fields but some special calculations have been made. Let K=Q(i) where i=sqrt(-1). Here the elliptic Lehmer problem implies a bound for 2h(Q) so we give some examples of this value which we obtained from Cremona.
1.E is [0,1-i,i,-i,0], Q=[0,0] and 2h(Q)=.023..
2.E is [1,1+i,i,0,0], Q=[-1,1] and 2h(Q)=.0175..
In the paper referred to above, it was argued that EDSs provide a natural way of searching for small height points. The paper contains the following examples.
1.The field is Q(w) where w is a non-trivial cube root of 1. The curve E is [0,0,0,-243,3726+10368w] and the point is [3-12w,-108w2]. The global height is .01032.. Although the curve might look a bit complicated, it actually arose from a simple EDS: The first 5 terms are 0,1,1+w,1+w,1+w,..
2.The field is Q(u) where u=(1+sqrt(5))/2. The curve is [0,0,0,-2214+1215u,40878-23328u] and the point is [3-9u,108-108u]. The global height is .00971.. Again, this comes from a simple sequence which begins 0,1,1-u,-2+u,5-3u,..
So far, nobody has found a value of dh(Q) below the smallest value known in the rational case.
Morgan Ward gives formulae for converting an EDS to a point on an elliptic curve. They can be found in his paper 'Memoir on elliptic divisibility sequences' Amer. J. Math. 70 (1948), 31-74. This paper is a must-read if you plan to find out more about EDSs. You can view these formulae by following this link.
Let a denote an algebraic number and say it generates the number field K. The so called projective height is the quantity
h(a) = Sv log max{1,|a|v},
where the sum runs over all the valuations of K. Notice that Kronecker's Theorem implies h(a)=0 if and only if a is a root of unity - in other words, a torsion point of the multiplicative group K*. The clasical Lehmer problem asks whether the non-zero values of the height are uniformly bounded below by
h(a) > c/d.
For more information about Lehmer's problem, consult the book .
1.If K is totally real then the non-zero heights are bounded below by log((1+sqrt(5))/2). So a stronger form of the Lehmer problem is true for totally real numbers, where the lower bound is even independent of the degree.
2.Suppose a is non-reciprocal then we can take c to be the log of the root of x3-x-1 outside the unit circle. To say a is non-reciprocal means that the set of conjugates of a is different from the set of conjugates of 1/a.
3.No smaller positive value of c has been found than that coming from the 10th degree polynomial
x10+x9-x7-x6-x5-x4-x3+x+1.
The roots of this polynomial are reciprocal. The minimal polynomial of a reciprocal algebraic number is symmetric in the sense that its sequence of coefficients reads the same backwards and forwards.
Perhaps it is possible to prove special cases of the elliptic Lehmer problem.
Using the projective height, we can write down Tate's formula for the global height h(Q) of a point Q. It is
h(Q) = lim 4-n1/2 h(x(2nQ)).
It is known that the global height of a K-rational point on an elliptic curve is invariant under isomorphism. This is helpful in cutting down the searching. It means we only need to look for integral points for example.
A group of us have recently started to search using elliptic divisibilty sequences. Every integral point on an elliptic curve gives rise to an EDS. Given the equation of the curve as above, suppose each a[i] in OK, the ring of integers of K. Define
b2 = a12+4a2,
b4 = 2a4+a1a3,
b6 = a32+4a6,
b8 = a12a6+4a2a6-a1a3a4+a2a32-a42.
Define a sequence of polynomials in OK[x,y] as follows: F[0]=0, F[1]=1, and
F[2] = 2y+a1x+a3,
F[3] = 3x4+b2x3+3b4x2+3b6x+b8,
F[4] = F[2](2x6+b2x5+5b4x4+10b6x3+ 10b8x2+(b2b8-b4b6)x+b4b8-b62).
These polynomials are called division polynomials. For more information about these, and about elliptic curves in general, consult Silverman's books. Now define inductively
F[2n+1] = F[n+2]F[n]3-F[n-1]F[n+1]3 and
F[2n]F[2] = F[n](F[n+2]F[n-1]2-F[n-2]F[n+1]2)
If the point [x,y] is a non-identity element of E(K) then we obtain a sequence of numbers u[n] = F[n]. If the point started as an integral point then all the numbers u[n] will be integral and they form an EDS.
If D denotes the discriminant of the curve than we have shown that we can get at the height using quite simple formula. Let N denote the field norm from K to Q. Let T denote the set of primes which divide N(D). Let e[n]=|N(u[n])| and f[n] = the T-free part of e[n].
Then the global height is
1/d lim 1/n2 log f[n],
where d denotes the degree of K over Q. For a proof, see the paper. The method will not give very high accuracy but it does give accuracy to 4 or 5 sig figs even for n=100. It is also easy to implement because it only requires polynomial arithmetic, such as is available in pari-gp.