INFINITE DESCENT ON ELLIPTIC CURVES

SAMIR SIKSEK

Dedicated to my Parents

Abstract. We present an algorithm for computing an upper bound for the difference of the logarithmic height and the canonical height on elliptic curves. Moreover a new method for performing the infinite descent on elliptic curves is given, using ideas from the geometry of numbers. These algorithms are practical and are demonstrated by a few examples.

1. Introduction

Recently there has been much interest in the computation of Mordell-Weil groups of elliptic curves, both for specific families of curves (such as in [Brem], [Brem, Ca], [Str, Top]), and in the development of new algorithms for computing the Mordell-Weil group (see for example [Ge, Zi]). Not only is this an interesting problem in itself, but is also an essential ingredient for the popular algorithm for calculating the integral points on elliptic curves using elliptic logarithms (see any of [GPZ], [Smart], [Sm, Ste], [Str, Tz]).

Let E be an elliptic curve defined over a number field K. The computation of the Mordell-Weil group naturally falls into 2 parts:

1. The 2-descent. Here, with some luck, a basis for E(K)/2E(K) is computed.

2. The infinite descent. This is the name given to the process by which given a basis for E(K)/mE(K) for some m ≥ 2, we can obtain a basis for E(K).

Over the rationals, the best (unconditional) algorithm known to me for the 2descent is the one given in [Bi, SwD], and in [Cre] pages 68-76. This has recently been (re-)implemented by J. Cremona as the program mwrank. For most curves of reasonably small discriminant mwrank can calculate E(ℚ)/2E(ℚ) in a very short time. In contrast to this, the method found in the literature for performing the infinite descent usually takes longer, and is often impossible to carry out in practice. Below we explain why this is so, and we present a new more efficient algorithm for carrying out the infinite descent. Our algorithm is practical, and its practicality is demonstrated by a few examples.

The standard method for infinite descent (see [Silv1] pages 739-742, or [Cre] pages 58-61) normally goes via Zagier’s Theorem, and explicit bounds on the difference between the logarithmic and canonical heights of points on elliptic curves defined over number fields (such as Silverman’s given below).

We return to the generality of E being a curve over a number field K.

Date: February 5, 1995.

1991 Mathematics Subject Classification. Primary 11G05; Secondary 11Y16.

Key words and phrases. Elliptic Curves, Diophantine Equations, Computational Number Theory, Mordell-Weil Group.

The author’s research was funded by a studentship from the SERC/EPSRC.

Theorem 1.1. (Zagier) Let B > 0 be such that

S = {P ∈ E(K) : ĥ(P) ≤ B}  (1)

contains a complete set of coset representatives for mE(K) in E(K). Then the set S generates E(K).

Proof. See [Cre] p61 or [Silv1] p740.

Theorem 1.2. ^{1} (Silverman) Let K be a number field and let E/K be given by the Weierstrass equation

E : Y^{2} + a_{1}XY + a_{3}Y = X^{3} + a_{2}X^{2} + a_{4}X + a_{6}  (2)

whose coefficients are in the ring of integers of K. Let Δ be the discriminant of the equation (2) and let j be the j-invariant of E. Further let

b_{2} = a_{1}^{2} + 4a_{2} and 2^{∗} = \{ \begin{matrix}2 & if b_{2} ≠ 0, \\ 1 & if b_{2} = 0. \end{matrix}

Define “height of E” (really of the Weierstrass equation (2)) by

μ(E) = \frac{1}{12}h(Δ) + \frac{1}{12}h_{∞}(j) + \frac{1}{2}h_{∞}(b_{2}/12) + \frac{1}{2} log(2^{∗}),

where, for t ∈ K,

h_{∞}(t) = \frac{1}{[K : ℚ]} ∑_{υ∈M_{K}^{∞}} n_{υ} log(max(1, |t|_{v}))

Then for all P ∈ E(K̄),

h(P) − ĥ(P) ≤ \frac{1}{12}h(j) + 2μ(E) + 1.946.

Proof. See [Silv1].

Having obtained a set of generators for E(K)/mE(K) we can compute all the coset representatives for E(K)/mE(K) and hence their canonical heights. If B is an upper bound for these canonical heights then by Zagier’s Theorem 1.1 we get an upper bound for the canonical heights of all the points of a set S (defined above) which generates E(K). Combining this with Silverman’s result 1.2 we get an upper bound B′ for the logarithmic heights of all the points of S. It follows that the set S can be enumerated, provided of course that this upper bound is not too large.

Unhappily, as indicated above, practical experience suggests that the upper bound B′ involved in this method is often too large. This can be for several reasons:

1. It is possible that the Silverman estimate on the difference between the logarithmic and canonical height is very large.

2. It is possible that the canoncial heights of the generators of E(K)/mE(K) are large.

1Here it is appropriate to make 2 comments:

1. We quoted only one half of Silverman’s Theorem which is given in [Silv2]. Silverman also gives a

lower bound for h − ĥ but this shall not concern us as it is not needed for the infinite descent.

2. Silverman’s bounds for h(P) − ĥ(P) hold for all points P on E defined over any extension of the

ground number field K. Our Theorem 2.1 gives a bound for h(P) − ĥ(P) for all points P ∈ E(K).

Thus a bound derived by our method for points on an elliptic curve over a certain number field will not always hold for points defined over extensions of that field.

3. It is also possible, even though the generators of E(K)/mE(K) have small canonical heights, that some of the coset representatives (particularly if the rank is large) will have large heights.

We stress that the size of the search region for the point of S increases exponentially with B′. To illustrate, if say K = ℚ, and if P = (X, Y) ∈ S then we can write X = x/z^{2} where x and z are in ℤ and satisfy |x| ≤ exp(B′) and |z| ≤ exp(B′/2). It follows that the search region here is roughly proportional to exp(1.5B′). For a number field K of degree n over the rationals, the search region is, very roughly, between exp(1.5nB′) and exp(2nB′) in size. Hence small savings on B′, can translate into big savings in the actual size of the search region.

We will adopt a different approach to the infinite descent:

1. We will give an algorithm which will allow us, in most cases, to calculate a sharper upper bound for the quantity h(P) − ĥ(P).

2. We will show how a basis of a submodule of the torsion-free part of E(K),

having full rank, can be enlarged efficiently to a basis for E(K). The algorithm for infinite descent we will give uses both of these ingredients, and involves searching much smaller regions than the above.

In computing our examples we have found Cremona’s programs ^{2} mwrank, and findinf very useful. findinf is a program for searching for points on a given curve up to a given logarithmic height. In the little programing we needed, we used the popular package Pari/GP (see [Pari]). This has many functions for doing arithmetic on elliptic curves, including elliptic logarithms, and canonical height computations.

2. The bound on the difference h(P) − ĥ(P)

2.1. Preliminaries. Let E be an elliptic curve given by the Weierstrass equation

E : Y^{2} + a_{1}XY + a_{3}Y = X^{3} + a_{2}X^{2} + a_{4}X + a_{6}  (3)

where a_{1}, …, a_{6} are in the ring of integers O_{K} of a number field K. In this section we shall give an algorithm for obtaining an upper bound for the quantity h(P) − ĥ(P). This is based on the traditional method of estimating the difference h(2P) − 4h(P). Generally speaking, when this has been done in the past, it relied on the use of elimination theory, which leads to poor upper bounds. The method we shall give bypasses elimination theory using explicit calculations over some local completions of K.

Apart from Silverman’s Theorem 1.2, there are other results which give bounds on the quantity h(P) − ĥ(P), most notably in [Zimmer] and [Dem]. The reason why we make specific comparisons only with Silverman’s theorem is that this is currently the most widely used and quoted in the literature.

As our method is very different from Silverman’s method for obtaining his estimate 1.2, we have no easy way of deciding a priori which should give the smaller bound. We can only note that, in practice, we have found that our method gives much smaller bounds most of the time, or exceptionally bounds which are slightly better. For example, a straightforward application of Silverman’s Theorem 1.2 for the curve

Y^{2} + Y = X^{3} − 7X + 6

2mwrank and findinf are available by anonymous ftp from euclid.exeter.ac.uk (144.173.8.2) in directory pub/cremona. There are executable binaries for both Sun (sparc) and Silicon Graphics (Irix 4) machines.

gives

h(P) − ĥ(P) ≤ 5.4.

In [BGZ] Buhler, Gross and Zagier derive that

h(P) − ĥ(P) ≤ 0 for all P ∈ E(ℚ),

and we get this also by applying our Theorem 2.1. Needless to say, here our method gave a much better bound than Silverman’s. In contrast to this, for the curve

Y^{2} = X(X^{2} − p^{2})

where p is prime and > 2, Silverman’s theorem gives

h(P) − ĥ(P) ≤ log(p) + 4.505

and our Theorem 2.1 gives

h(P) − ĥ(P) ≤ log(p) + 0.347 for all P ∈ E(ℚ).

Here for small primes p our bound looks much better and for large p it looks roughly the same as Silverman’s. However, even here, the extra work we had to do to get our bound was worthwhile, since to search for all rational points on the curve of canonical height ≤ B, the size of the search region if we apply our bound is roughly

1.682p^{1.5} exp(1.5B),

and if we apply Silverman’s bound it is roughly

860.488p^{1.5} exp(1.5B).

Accordingly, we believe that the small amount of work that goes into obtaining our bound will usually be amply rewarded by the time saved through searching smaller regions.

We employ some standard notation to do with number fields and elliptic curves. Given a number field K we let M_{K} be the set of all valuations on K. We write M_{K}^{0} and M_{K}^{∞} for the sets of non-archimedean and archimedean valuations on K respectively. For an elliptic curve E given by a Weierstrass equation of the form (3) we define some associated constants (see [Silv2] page 46):

\begin{aligned}b_{2} & = & a_{1}^{2} + 4a_{2}, \\ b_{4} & = & 2a_{4} + a_{1}a_{3}, \\ b_{6} & = & a_{3}^{2} + 4a_{6}, \\ b_{8} & = & a_{1}^{2}a_{6} + 4a_{2}a_{6} − a_{1}a_{3}a_{4} + a_{2}a_{3}^{2} − a_{4}^{2}, \\ Δ & = & −b_{2}^{2}b_{8} − 8b_{4}^{3} − 27b_{6}^{2} + 9b_{2}b_{4}b_{6}. \end{aligned}  (4)

Let

\begin{aligned}f(X) & = & 4X^{3} + b_{2}X^{2} + 2b_{4}X + b_{6} \\ g(X) & = & X^{4} − b_{4}X^{2} − 2b_{6}X − b_{8}. \end{aligned}  (5)

It will be seen that the polynomials f, g arise in the duplication formula for a point on the curve E and a little study of these polynomials essentially gives us our required bound for h(P) − ĥ(P).

As usual, we denote the residue field of a completion K_{υ} with respect to a nonarchimedean prime υ by k_{υ}, and we denote the canonical map K_{υ} → k_{υ} ∪ {∞} by x → x̄. We let π be a prime element for υ (i.e. π ∈ K_{υ} such that υ(π) = 1).

Lemma 2.1. Suppose that υ is a non-archimedean valuation on K and P = (x, y) ∈ E(K_{υ}) is such that its reduction P̄ = (x̄, ȳ) ∈ E(k_{υ}) is non-singular. Then

max {|f(x)|_{v}, |g(x)|_{v}} = max {1, |x|_{v}}^{4} .

Proof. If |x|_{v} > 1 then |f(x)|_{v} ≤ |x|_{v}^{3} and |g(x)|_{v} = |x|_{v}^{4} and in this case the conclusion is obvious.

Hence we can suppose that |x|_{v} ≤ 1. Now we are required to prove that

max {|f(x)|_{v}, |g(x)|_{v}} = 1

Hence it is enough to show that when f(x) ≡ 0 (mod π) and g(x) ≡ 0 (mod π) then P̄ is singular on E(k_{υ}).

By a change of variable over K_{υ} which is non-singular modulo π, we may suppose that (x, y) = (0, 0). Now the condition for (0, 0) to be on the Weierstrass equation is that a_{6} = 0. Moreover, since f(0) ≡ g(0) ≡ 0 (mod π) we get that b_{6} ≡ b_{8} ≡ 0 (mod π). Hence from the formulae for b_{6}, b_{8} we get that a_{3} ≡ a_{4} ≡ 0 (mod π). This is a sufficient condition for (0, 0) to be singular on E(k_{υ}).

Here is some more notation which we will find useful:

\begin{aligned}f′(X′) & = & X′^{4}f(\frac{1}{X′}) \\ g′(X′) & = & X′^{4}g(\frac{1}{X′}). \end{aligned}  (6)

Further, for each υ ∈ M_{K}, let

D_{v} = {X ∈ K_{υ} : |X|_{v} ≤ 1 and f(X) ∈ K_{υ}^{2}}

D′_{v} = \{X′ ∈ K_{υ} : |X′|_{v} ≤ 1 and if X′ ≠ 0 then f (\frac{1}{X′} ) ∈ K_{υ}^{2}\}

.

Lemma 2.2. Define constants d_{v}, d′_{v} by 1. d_{v} = inf_{X∈D_{v}} max {|f(X)|_{v}, |g(X)|_{v}},

2. d′_{v} = inf_{X′∈D′_{v}} max {|f′(X′)|_{v}, |g′(X′)|_{v}}. Then, d_{v}, d′_{v} are non-zero.

Proof. We begin by noting that the sets D_{v}, D′_{v}, are compact subsets of K_{υ} (with respect to the υ-adic topology), and hence the infima d_{v}, d′_{v} must be attained. If say d_{v} was zero then there would exist X_{1} ∈ D_{v} such that f(X_{1}) = g(X_{1}) = 0. However, from [Silv3] p347 we have that

Resultant (f, g) = Resultant (f′, g′) = Δ^{2}

where Δ is the discriminant of the elliptic curve E. Accordingly, as this cannot be zero, d_{v} ≠ 0. Similarly d′_{v} ≠ 0.

If E is minimal at some non-archimedean valuation υ then we define

c_{υ} = [E(K_{υ}) : E^{0}(K_{υ})].

i.e. c_{υ} is the Tamagawa index at υ.

Lemma 2.3. For any valuation υ on K, let

ϵ_{υ}^{−1} = inf_{(X,Y)∈E(K_{υ})} \frac{max(|f(X)|_{v}, |g(X)|_{v})}{max(1, |X|_{v})^{4}}  (7)

Then 1. ϵ_{υ} exists. (i.e. the quantity on the right exists and is non-zero). Moreover

ϵ_{υ}^{−1} = min(d_{υ}, d′_{υ}).

2. ϵ_{υ} ≥ 1.

3. If υ is non-archimedean, E is minimal at υ, and the local Tamagawa index c_{υ} = 1, then ϵ_{υ} = 1.

4. If υ is non-archimedean, then ϵ_{υ} = d_{υ}^{−1} where d_{υ} is as defined in Lemma 2.2.

5. If υ is non-archimedean, and

⌊\frac{υ(4Δ)}{2}⌋ = n,

then ϵ_{υ} ≤ |π|_{v}^{−2n} (where ⌊ ⌋ denotes the integer part of a number).

Proof. Suppose (X, Y) ∈ E(K_{υ}). Then by a standard manipulation of the Weierstrass equation (3) we get

(2Y + a_{1}X + a_{3})^{2} = f(X)  (8)

Hence, if |X|_{v} ≤ 1 then X ∈ D_{υ} and

\frac{max(|f(X)|_{v}, |g(X)|_{v})}{max(1, |X|_{v})^{4}} = max(|f(X)|_{v}, |g(X)|_{v}).

If |X|_{v} ≥ 1 then X′ = X^{−1} ∈ D′_{υ} and

\frac{max(|f(X)|_{v}, |g(X)|_{v})}{max(1, |X|_{v})^{4}} = max(|f′(X′)|_{v}, |g′(X′)|_{v}).

Hence it is clear that the quantity on the right of (7) exists and is equal to min(d_{υ}, d′_{υ}), and so is non-zero (by Lemma 2.2). This proves the first part of the above.

For the second part we note that we may take (X, Y) ∈ E(K_{υ}) to be arbitrarily close to 0. Hence X is unbounded with respect to the metric | |_{v} and so

\frac{max(|f(X)|_{v}, |g(X)|_{v})}{max(1, |X|_{v})^{4}}

is arbitarily close to 1. It follows that ϵ_{υ}^{−1} ≤ 1, and hence that ϵ_{υ} ≥ 1, as required for part 2.

Part 3 is clear from Lemma 2.1.

For part 4 we note that if υ is non-archimedean and |X|_{v} > 1 then by the proof of Lemma 2.1,

\frac{max(|f(X)|_{v}, |g(X)|_{v})}{max(1, |X|_{v})^{4}} = 1,

and if |X|_{v} ≤ 1 then

\frac{max(|f(X)|_{v}, |g(X)|_{v})}{max(1, |X|_{v})^{4}} ≤ 1,

so by the definition of ϵ_{υ} we get

ϵ_{υ}^{−1} ≤ inf_{(X,Y)∈E(K_{υ}), |X|_{v}≤1} max(|f(X)|_{v}, |g(X)|_{v})

which immediately gives part 4.

Let us now prove part 5. Let n be as defined in the Lemma. Suppose that

inf_{X∈D_{υ}} max(|f(X)|_{v}, |g(X)|_{v}) ≤ |π|_{v}^{2n+1}

and it is sufficient to derive a contradiction. If this was the case then there would exist (X, Y) ∈ E(K_{υ}), with

f(X) ≡ g(X) ≡ 0 (mod π^{2n+1}).

But from equation (8) we must deduce that f(X) ≡ 0 (mod π^{2n+2}). We now invoke the following identity:

4g(X) = (6X^{2} + b_{2}X + b_{4})^{2} − (8X + b_{2})f(X).  (9)

This is easily verified. It follows that (6X^{2} + b_{2}X + b_{4})^{2} ≡ 0 (mod π^{2n+2}). Finally we use the congruence

[48X^{2} + 8b_{2}X + (−b_{2}^{2} + 32b_{4})](6X^{2} + b_{2}X + b_{4})^{2} ≡ −4Δ (mod f(X)) (10)

in ℤ[X, a_{1}, …, a_{6}]. This is straightforward but rather tedious to verify (it is a slightly more general form of the congruence on page 51 of [Ca1]). We can now conclude that π^{2n+2} divides 4Δ as required.

For a non-archimedean valuation υ, we let (as usual) E^{0}(K_{υ}) be the set of points on E(K_{υ}) with non-singular reduction modulo π. It is useful to define μ_{υ} = μ_{υ}(E) as follows:

1. if υ is archimedean, then μ_{υ} = \frac{1}{3},

2. if υ is non-archimedean and E is not minimal at υ, then μ_{υ} = \frac{1}{3},

3. if υ is non-archimedean and E is minimal at υ, then

μ_{υ} = \{ \begin{matrix}0 & if [E(K_{υ}) : E^{0}(K_{υ})] = 1 \\ 1/4 & if E(K_{υ})/E^{0}(K_{υ}) ≅ ℤ/2ℤ or (ℤ/2ℤ)^{2} \\ (1 − \frac{1}{4^{α}} ) /3 & if E(K_{υ})/E^{0}(K_{υ}) ≅ ℤ/2^{α}ℤ where α ≥ 1 \\ 1/3 & if [E(K_{υ}) : E^{0}(K_{υ})] is not a power of 2. \end{matrix}

Here we recall that for non-archimedean υ at which E is minimal, the group E(K_{υ})/E^{0}(K_{υ}) is either cyclic or is equal to (ℤ/2ℤ)^{2} (see for example Theorem VII.6.1 on page 183 of [Silv2]). Hence the above definition for υ covers all the possible cases.

We are now ready to state our main Theorem on the bound h − ĥ.

Theorem 2.1. Let M_{K} be a complete set of inequivalent valuations on K. For each υ ∈ M_{K}, let n_{υ} = [K_{υ} : ℚ_{υ}]. Define a function

ϵ : M_{K} × E(K) → ℝ_{≥1}  (11)

by

ϵ(υ, P) = \{ \begin{matrix}1 & if υ ∈ M_{K}^{0}, E is minimal at υ, and P ∈ E^{0}(K_{υ}) \\ ϵ_{υ} & otherwise. \end{matrix}  (12)

Then for all P ∈ E(K) we have

\begin{aligned}h(P) − ĥ(P) & ≤ & \frac{1}{[K:ℚ]} (∑_{υ∈M_{K}} μ_{υ}n_{υ} log(ϵ(υ, P))) \\ & ≤ & \frac{1}{[K:ℚ]} (∑_{υ∈M_{K}} μ_{υ}n_{υ} log(ϵ_{υ})) . \end{aligned}  (13)

We note here that if υ is non-archimedean, E is minimal at υ, and the Tamagawa index c_{υ} = 1, then by the definition for μ_{υ} above, and Lemma 2.3 we have that μ_{υ} = log(ϵ(υ, P)) = log(ϵ_{υ}) = 0. Hence only finitely many terms in the above sums are non-zero.

Proof. We begin by noting that for all P ∈ E(K), υ ∈ M_{K},

max(|f(X)|_{v}, |g(X)|_{v}) ≥ ϵ(υ, P)^{−1} max(1, |X|_{v})^{4}  (14)

using the definition of ϵ_{υ} on page 5, and the definition of ϵ(υ, P) above, and Lemma 2.1.

Now if P = (X, Y) ∈ E(K) then by the duplication formula (see [Silv2] p59) the x-coordinate of 2P is g(X)/f(X). Hence using the product definition for naive heights and Lemma 2.1 above we get

\begin{aligned}H_{K}(2P) & = & ∏_{υ∈M_{K}} max \{|f(X)|_{v}, |g(X)|_{v}\}n_{υ} \\ & ≥ & ∏_{υ∈M_{K}} (ϵ(υ, P)^{−1} max \{1, |X|_{v}\}^{4})n_{υ} \\ & = & (∏_{υ∈M_{K}} ϵ(υ, P)^{−n_{υ}}) H_{K}(P)^{4}. \end{aligned}  (15)

Recall that

h(P) = \frac{1}{[K : ℚ]} log(H_{K}(P))

and so

h(2P) − 4h(P) ≥ \frac{1}{[K : ℚ]} ( ∑_{υ∈M_{K}} n_{υ} log(ϵ(υ, P)^{−1})) .

Rearranging, we get

h(P) ≤ \frac{1}{4}h(2P) + \frac{1}{4[K : ℚ]} ( ∑_{υ∈M_{K}} n_{υ} log(ϵ(υ, P))) .

Using

ĥ(P) = lim_{n→∞} 4^{−n}h(2^{n}P)

we get

h(P) ≤ \frac{1}{[K : ℚ]} ( ∑_{υ∈M_{K}} n_{υ} (∑_{n=1}^{∞} \frac{1}{4^{n}} log(ϵ(υ, 2^{n}P)))) + ĥ(P).

However, from the definition of the function ϵ we find that

log(ϵ(υ, 2^{n}P)) = \{ \begin{matrix}0 & υ ∈ M_{K}^{0}, E is minimal at υ, and 2^{n}P ∈ E^{0}(K_{υ}), \\ log(ϵ_{υ}) & otherwise. \end{matrix}

It is now an easy matter to show that for all υ ∈ M_{K},

∑_{n=1}^{∞} \frac{1}{4^{n}} log(ϵ(υ, 2^{n}P)) ≤ μ_{υ} log(ϵ(υ, P))

where μ_{υ}is as defined above. This completes the proof.

It is apparent from our Theorem above that to get an upper bound on h − ĥ, all that remains is to calculate the values ϵ_{υ} at the finitely many valuations for which μ_{υ} is not zero: recall these are the cases when either υ is archimedean (i.e. where K_{υ} = ℝ or ℂ), or where υ is non-archimedean but E is not minimal at υ, or it is minimal but the Tamagawa index c_{υ} ≠ 1.

We give separate algorithms for calculating ϵ_{υ} = min(d_{υ}, d′_{υ})^{−1} for three different cases:

• K_{υ} = ℝ

• K_{υ} = ℂ

• υ is non-archimedean.

2.2. K_{υ} = ℝ. Suppose that K_{υ} = ℝ. Note that there exists σ ∈ Gal(K/ℚ) such that K^{σ} ⊂ ℝ and for all x ∈ K, |x|_{v} = |x^{σ}| where | | is the ordinary absolute value. Hence, by replacing f, g, f′, g′ by f^{σ}, g^{σ}, f′^{σ}, g′^{σ} if necessary,we can assume f, g, f′, g′ are all real polynomials. Now the problem is reduced to finding

d_{v} = inf_{X∈D_{v}} max {|f(X)|_{v}, |g(X)|_{v}} ,

d′_{v} = inf_{X′∈D′_{v}} max {|f′(X′)|_{v}, |g′(X′)|_{v}} ,

where

D_{v} = {X ∈ ℝ : |X| ≤ 1 and f(X) ≥ 0}

and

D′_{v} = \{X′ ∈ ℝ : |X′| ≤ 1 and either X′ = 0 or f(\frac{1}{X′}) ≥ 0\}

are clearly finite unions of intervals. Finally we use the following elementary lemma.

Lemma 2.4. If f, g are continuous real functions and I is an interval then the infimum of the continuous function max {|f(X)|, |g(X)|} over the interval I is attained at one of the following points

(i): an end point of I,

(ii): at one of the roots of f, g, f + g, f − g in the interval I, (iii): at a turning point of one of the functions f, g.

Proof. We simply note that at any point in I not listed in (i) or (ii), the function max {|f(X)|, |g(X)|} is equal to one of ±f, ±g and its infimum must be a local supremum or infimum of f, or g.

Hence, to calculate d_{v}, we write D_{v} as a union of intervals (I) and calculate the infimum of max {|f(X)|, |g(X)|} over each interval separately using the above Lemma, and then d_{v} will be the minimum of these (finitely many) infima. Similarly we calculate d′_{υ}, and then ϵ_{υ} = min(d_{υ}, d′_{υ})^{−1}.

2.3. K_{υ} = ℂ. Suppose that K_{υ} = ℂ. In the same way as the real case, we can if necessary replace f, g, f′, g′ by appropriate conjugates so that

d_{v} = inf_{X∈D_{v}} max {|f(X)|_{v}, |g(X)|_{v}} ,

d′_{v} = inf_{X′∈D′_{v}} max {|f′(X′)|_{v}, |g′(X′)|_{v}} ,

where D_{v} = D′_{v} = D = {z ∈ ℂ : |z| ≤ 1} is the closed unit disc. We make use of the following Lemma.

Lemma 2.5. let f and g be as above. Then the continuous function h : ℂ → ℝ_{>0} defined by

h(z) = max {|f(z)|, |g(z)|}

attains its infimum over D at a point z_{0} satisfying either 1. |z_{0}| = 1 (i.e. it is on the boundary of D), or

2. |f(z_{0})| = |g(z_{0})|.

Proof. For each ρ ∈ ℂ there are, counting multiplicities, 4 solutions to the equation f(X) = ρg(X). In fact by Cardano’s formulae, there exist 4 functions ϕ_{1}, …, ϕ_{4} : ℂ → ℂ such that ϕ_{1}(ρ), …, ϕ_{4}(ρ) are solutions to f(X) = ρg(X).

Let

S = {ρ ∈ ℂ : |ρ| = 1} .

It follows that each ϕ_{i}(S) is a path in ℂ. We note that for all z ∈ ℂ, |f(z)| = |g(z)| if and only if there exist ρ ∈ S such that f(z) = ρg(z) and hence if and only if z ∈ ϕ_{i}(S) for some i.

Now the paths ϕ_{1}(S), …, ϕ_{4}(S) divide the unit disc D into finitely many connected regions U_{1}, …, U_{n}. Consider a region U_{j}; denote the interior of U_{j} by int(U_{j}) and its closure by \overline{U}_{j}. We note that the intersection of int(U_{j}) and ϕ_{i}(S) is empty for i = 1, …, 4. Hence, by the connectedness of U_{j}, we get that either |f| > |g| or |g| > |f| on all of int(U_{j}). Suppose, without loss of generality, that |f| > |g| on all of int(U_{j}). Then h(z) = |f(z)| for all z ∈ \overline{U}_{j}. It is easy to see that f is never zero on \overline{U}_{j}: if f is zero at some point of \overline{U}_{j}, then g is also zero at that point, contradicting Lemma 2.2. Let w(z) = \frac{1}{f(z)}. Then w is holomorphic on int(U_{j}) and continuous on \overline{U}_{j} and so by the Maximum Modulus Theorem of Complex Analysis (see [Pr] p76), it attains its maximum modulus over \overline{U}_{j} on the boundary \overline{U}_{j}\int(U_{j}). Hence h(z) = |f(z)| attains its infimum over \overline{U}_{j} on the boundary \overline{U}_{j}\int(U_{j}). But each of these boundaries is a subset of S ∪ ϕ_{1}(S) ∪ … ∪ ϕ_{4}(S). Since the \overline{U}_{j} cover D we get that h attains its infimum over D on S ∪ ϕ_{1}(S) ∪ … ∪ ϕ_{4}(S). This is the statement of the theorem.

It is plain that the Lemma is true for f′, g′, instead of f, g. Now it is necessary to estimate inf {|f|, |g|} over the boundary S, and over the sections of the paths ϕ_{i}(S). We will use the following naive method. Fix some n ≥ 2 (this should be roughly 1 more than the number of significant digits we want to determine d_{υ} to). Let θ_{j} = 10^{−n}j for j = 1, …, 10^{n}. For each θ_{j} we solve (numerically) the equation

f(X) = e^{2πθ_{j}}g(X),

and let

κ_{j} = min {max(|f(e^{2πθ_{j}})|, |g(e^{2πθ_{j}})|)} ∪ {|f(X)| : X ∈ D and f(X) = e^{2πθ_{j}}g(X)} .

Finally, we take d_{υ} = min(κ_{j}). Similarly, we estimate d′_{υ}, and take ϵ_{υ} = min(d_{υ}, d′_{υ})^{−1}. Of course, this method is crude, and great improvements must be possible, but we will not do this.

2.4. υ is Non-Archimedean. In this section we want to calculate

ϵ_{υ}^{−1} = inf_{(X,Y)∈E(K_{υ})} \frac{max(|f(X)|_{v}, |g(X)|_{v})}{max(1, |X|_{v})^{4}}

for non-archimedean υ. We note by Lemma 2.1, that if the reduction of the curve E(k_{υ}) is non-singular then ϵ_{υ} = 1. Hence, we can assume that E has bad reduction at υ, and calculate the infimum over the points of E(K_{υ}) which have singular reduction modulo υ. To do this we define the following sequence of sets:

We define U_{i} for i = 1, 2, …, to be the set of all X (mod π^{2i}) satisfying

1. f(X) ≡ 0 (mod π^{2i}),

2. g(X) ≡ 0 (mod π^{2i−1}), and

3. there exists X_{0} ∈ K_{υ} such that X ≡ X_{0} (mod π^{2i}) and f(X_{0}) ∈ K_{υ}^{2}.

And we define V_{i} for i = 1, 2, …, to be the set of all X (mod π^{2i}) satisfying 1. f(X) ≡ g(X) ≡ 0 (mod π^{2i}),

2. there exists X_{0} ∈ K_{υ} such that X ≡ X_{0} (mod π^{2i}) and f(X_{0}) ∈ K_{υ}^{2}.

Lemma 2.6. 1. Suppose υ(2) = 0. If i ≥ 1 and U_{i} ≠ ∅, then V_{i} = U_{i} and

π^{2i} | Δ.

2. Suppose υ(2) = e > 0. If U_{i} ≠ ∅ or V_{i} ≠ ∅, then π^{2i} | 4Δ.

Proof. We recall the identity and the congruence we used in the proof of Lemma 2.3 (on page 7)

4g(X) = (6X^{2} + b_{2}X + b_{4})^{2} − (8X + b_{2})f(X).  (16)
[48X^{2} + 8b_{2}X + (−b_{2}^{2} + 32b_{4})](6X^{2} + b_{2}X + b_{4})^{2} ≡ −4Δ (mod f(X)). (17)

It follows from the first that if υ(2) = 0, and X ∈ U_{i}, then

(6X^{2} + b_{2}X + b_{4})^{2} ≡ 0 (mod π^{2i})

and so π^{2i} | g(X) and so X ∈ V_{i}. Further, by the congruence, π^{2i} | Δ, and this completes the proof of the first part. The proof of the second part is similar.

Corollary 2.1. If υ(2) = 0 and U_{1} = ∅ then ϵ_{υ} = 1. If U_{j} ≠ ∅ and U_{j+1} = ∅ then ϵ_{υ} = |π|_{v}^{−2j}.

Hence if υ(2) = 0 then we compute (U_{i}) explicitly for i = 1, 2, … until we reach the empty set. Then the value of ϵ_{υ} is given by the above corollary. Here in calculating the (U_{i}), it is needed to be able to test, given X (mod π^{2i}), if there exists X_{0} ∈ K_{υ} such that X ≡ X_{0} (mod π^{2i}) and f(X_{0}) ∈ K_{υ}^{2}. For this we use a suitable generalization of the algorithm in Lemmas 6 and 7 of [Bi, SwD]. This is given in [Sik].

Corollary 2.2. Suppose υ(2) ≠ 0 1. If U_{1} = ∅ then ϵ_{υ} = 1.

2. If U_{j} ≠ ∅ and V_{j} = ∅ then ϵ_{υ} = |π|_{v}^{−(2j−1)}.

3. If V_{j} ≠ ∅ and U_{j+1} = ∅ then ϵ_{υ} = |π|_{v}^{−2j}.

Hence if υ(2) ≠ 0, then we compute (U_{j}) and (V_{j}) explicitly until one of them is empty. Then we compute ϵ_{υ} from the above corollary.

2.5. The Height Modulo Torsion. As will be seen in the examples, curves where the bound obtained by Theorem 2.1 is small tend to be those where the Tamagawa indices are trivial at the larger primes which divide the discriminant. This is often not the case where the torsion group is non-trivial. However the following Theorem will show us how to exploit the torsion group in order to reduce the bound obtained.

Theorem 2.2. Under the notation and hypotheses of Theorem 2.1, let υ_{1}, …, υ_{n} be the (finitely many) valuations in M_{K} where the quantities μ_{υ} log(ϵ_{υ}) are nonzero. Suppose (for some m ≤ n) that υ_{1}, …, υ_{m} are non-archimedean valuations such that E is minimal at each of them, and there exists a subgroup H ≤ T or(E(K)) such that H surjects onto E(K_{υ_{i}})/E^{0}(K_{υ_{i}}) (via the natural map) for 1 ≤ i ≤ m. Then for each P ∈ E(K), there exists T ∈ H such that

\begin{aligned}h(P + T) − ĥ(P) & ≤ & \frac{1}{[K:ℚ]} (\frac{|H|−1}{|H|}) (∑_{i=1}^{m} μ_{υ}n_{υ} log(ϵ_{υ})) \\ & + & \frac{1}{[K:ℚ]} (∑_{i=m+1}^{n} μ_{υ}n_{υ} log(ϵ_{υ})) . \end{aligned}  (18)

Proof. Let

H = {T_{1}, …, T_{k}} .

Given any P ∈ E(K), and 1 ≤ i ≤ m we must have that exactly one of P + T_{j} has good redution at υ_{i}. Hence, using Theorem 2.1, we get that

\begin{matrix}∑_{j=1}^{k} h(P + T_{j}) − ĥ(P) = ∑_{j=1}^{k} h(P + T_{j}) − ĥ(P + T_{j}) \\ ≤ \frac{1}{[K:ℚ]} (∑_{i=1}^{n} μ_{υ_{i}}n_{υ_{i}} ∑_{j=1}^{k} log(ϵ(υ_{i}, P + T_{j}))) \\ ≤ \frac{k−1}{[K:ℚ]} (∑_{i=1}^{m} μ_{υ_{i}}n_{υ_{i}}ϵ_{υ_{i}}) + \frac{k}{[K:ℚ]} (∑_{i=m+1}^{n} μ_{υ_{i}}n_{υ_{i}}ϵ_{υ_{i}}) \end{matrix}  (19)

Hence, for one of the T_{j} we must have that

k(h(P + T_{j}) − ĥ(P)) ≤ \frac{k − 1}{[K : ℚ]} (∑_{i=1}^{m} μ_{υ_{i}}n_{υ_{i}}ϵ_{υ_{i}}) + \frac{k}{[K : ℚ]} ( ∑_{i=m+1}^{n} μ_{υ_{i}}n_{υ_{i}}ϵ_{υ_{i}})

which gives us the statement of the Theorem.

2.6. Examples.

Example 2.1.

E : Y^{2} = X^{3} − 73705X − 7526231  (20)

We find that the equation is minimal and that its discriminant is

Δ = 1155136043932048 = 2^{4} × 199 × 362793983647

as a product of prime factors. Hence the Tamagawa indices will be 1, except possibly at 2, and so from the definition on page 7, all the μ_{p} = 0 except possibly for p = 2, or p = ∞. Using Pari/GP we find that the Tamagawa index at 2 is 3. Hence μ_{2} = μ_{∞} = \frac{1}{3}. To use Theorem 2.1 it remains to calculate ϵ_{2} and ϵ_{∞}.

We find that

f = 4x^{3} − 294820x − 30104924 = 4(x^{3} − 73705x − 7526231)

and

g = x^{4} + 147410x^{2} + 60209848x + 5432427025.

Now if g ≡ 0 (mod 2) then x is odd. But clearly, if x is odd then |f|_{2} = 1/4, and |g|_{2} ≤ 1/4. Moreover, (−137, −1) ∈ E(ℚ) ⊆ E(ℚ_{2}) and |f(−137)| = |g(−137)| = 1/4. Hence ϵ_{2} = 4.

In computing ϵ_{∞} we find

D_{∞} = ∅

and

D′_{∞} = [−0.007299, −0.005691] ∪ [0, 0.003198].

Using Lemma 2.4 we find ϵ_{∞} = 2.939442. Applying Lemma 2.1 we get

h(P) − ĥ(P) ≤ 0.8215047.  (21)

for all P ∈ E(ℚ).

Here we note that Silverman’s Theorem 1.2 gives a bound

h(P) − ĥ(P) ≤ 13.0242

Example 2.2. We begin with a curve of Mestre (quoted on page 234 of [Silv2])

E : Y^{2} + Y = X^{3} − 6349808647X + 193146346911036  (22)

The discriminant of this curve is

Δ = 60259 × 550469 × 11241887 × 722983930261

as a product of primes. Since it is not divisible by any squares we must have that all constants μ_{p} = 0 for all finite primes p. By definition μ_{∞} = \frac{1}{3} and it remains to determine ϵ_{∞}. Hence we write D_{∞}, and D′_{∞} as unions of intervals as described on page 9 :

D_{∞} = [−1, 1]

and

D′_{∞} = [−1 , −1.08780 × 10^{−5}] ∪ [0 , 2.02512 × 10^{−5}] ∪ [2.35024 × 10^{−5} , 1].

Hence we find that d_{∞} ≈ 4 × 10^{19} and d′_{∞} = 0.1289169. So ϵ_{∞} = 7.75693 and using Theorem 2.1 we get

h(P) − ĥ(P) ≤ μ_{∞} log(ϵ_{∞}) = 0.68286  (23)

for all points P ∈ E(ℚ). We note here that Silverman’s theorem 1.2 gives an upper bound of 21.7782 instead 0.68286.

It is apparent in the last two examples that the reason why the bound for h(P)− ĥ(P) is so small is that all or almost all of the Tamagawa indices were 1. Here is an example where this is not the case:

Example 2.3. We compute the bound for the following curve which is given by Thomas Kretschmer in [Kret] (page 633)

Y^{2} + XY = X^{3} − 5818216808130X + 5401285759982786436  (24)

The model given here is minimal and the discriminant is

Δ = 2^{6} × 3^{8} × 7^{2} × 11^{2} × 29^{2} × 31^{2} × 41^{2} × 47^{2} × 277891391058913

We compute the following table

\begin{matrix}p & c_{p} & μ_{p} & ϵ_{p} \\ 2 & 6 & 1/3 & 2^{6} \\ 3 & 8 & 21/64 & 3^{8} \\ 7 & 2 & 1/4 & 7^{2} \\ 11 & 2 & 1/4 & 11^{2} \\ 29 & 2 & 1/4 & 29^{2} \\ 31 & 2 & 1/4 & 31^{2} \\ 41 & 2 & 1/4 & 41^{2} \\ 47 & 2 & 1/4 & 47^{2} \\ ∞ & - & 1/3 & 518.48024 \end{matrix}

Hence we get

h(P) − ĥ(P) ≤ 15.70819.

In comparison Silverman’s bound is 27.5866.

Here we note that although our bound is much smaller than Silverman’s it is still some what large for the purpose of the infinite descent (see the continuation of this example on page 22). However we note that the reduction of the point of order 2

Q = [1402932, −701466]

is singular at the primes 7, 11, 29, 31, 41, 47. Hence using Theorem 2.2 we get that for all points P ∈ E(ℚ) there is a T ∈ {0, Q} such that

h(P + T) − ĥ(P) ≤ 11.03099

3. The Canonical Height and Results from the Geometry of Numbers

It is worth recalling at the outset of this section, that in the case when the elliptic curve E has rank 1 over the number field K, the infinite descent can be performed in a much easier way than that described in the introduction. This is well known: suppose P ∈ E(K) has infinite order and and let us say that P generates E(K)/2E(K). Then, modulo torsion, P = nQ where n ≥ 1, and Q generates the free part of E(K). Since P generates E(K)/2E(K), n cannot be even and hence n = 1 or n ≥ 3. If n ≥ 3 then

ĥ(Q) ≤ \frac{1}{9}ĥ(P)

and so, if P is not the generator of the free part of E(K), we will find a generator in a much smaller region than that given by Zagier’s Theorem 1.1.

In this section we develop a general technique for the infinite descent which is analougous to the reduction of the bound for the rank 1 case given above. It is here that we shall employ the language of lattices. Following [Ge, Zi] we define Ê(K) = E(K)/T or(E(K)), where T or(E(K)) is the torsion of E(K). Suppose that P_{1}, …, P_{r} generate a sublattice of Ê(K) of full rank (for example P_{1}, …, P_{r} could be a basis of Ê(K)/mÊ(K) for some m ≥ 1). Suppose that this sublattice had index n. If n = 1, then of course, P_{1}, …, P_{r} is a basis for Ê(K), and we can easily recover a basis for E(K). We will define the height pairing matrix of P_{1}, …, P_{r} as follows:

H(P_{1}, …, P_{r}) = (< P_{i}, P_{j} >)_{i,j=1,... ,r}  (25)

where for all P, Q in E(K)

< P, Q >=: \frac{1}{2}(ĥ(P + Q) − ĥ(P) − ĥ(Q))  (26)

Let R(P_{1}, …, P_{r}) be the determinant of the height matrix H(P_{1}, …, P_{r}). If R is the regulator of E(K) it follows that

R = \frac{1}{n^{2}} R(P_{1}, …, P_{r})  (27)

We recall that the regulator is roughly of the same order of magnitude as the product of the canonical heights of some basis for Ê(K) (See, for example, the proof of Manin’s theorem in [Ge, Zi]). Hence if the index n was very large we would expect (by virtue of (27)) there to be points of Ê(K) − {0} of very small canonical height. We make this idea precise. Roughly it tells us that if there are no points of Ê(K) − {0} of height smaller than some lower bound, then we can get an upper bound for the index n and hence reduce the infinite descent to checking the index of P_{1}, …, P_{r} in Ê(K). We make use of the following Lemma from the Geometry of Numbers.

Lemma 3.1. (Hermite, Minkowski and others) Suppose

f(x) = ∑_{i,j=1}^{r} f_{ij}x_{i}x_{j}  (28)

where (f_{ij}) is a symmetric positive definite matrix with determinant

D = det(f_{ij}) > 0.  (29)

Then there exists a positive constant γ_{r} such that

inf_{m≠0 integral} f(m) ≤ γ_{r}D^{\frac{1}{r}}  (30)

Moreover we can take

\begin{matrix}γ_{1}^{1} = 1, & γ_{2}^{2} = \frac{4}{3}, & γ_{3}^{3} = 2, & γ_{4}^{4} = 4, \\ γ_{5}^{5} = 8, & γ_{6}^{6} = \frac{64}{3}, & γ_{7}^{7} = 64, & γ_{8}^{8} = 2^{8} \end{matrix}  (31)

and for r ≥ 9

γ_{r} = (\frac{4}{π} ) Γ (\frac{r}{2} + 1)^{\frac{2}{r}}  (32)

Proof. The Lemma with constant γ_{r} = (\frac{4}{3})^{\frac{(r−1)}{2}} was originally due to Hermite. The formula (30) with γ_{r} given for all r by (32) is the formula for the ‘first Minima’ in Minkowski’s Second Theorem (see [Ca2] p260, and [Sieg] p26 for the formula ). The constants γ_{1}, …, γ_{8} given above are, for 1 ≤ r ≤ 8, the smallest constants which make the Lemma work (See [Ca3] p332).

I’m unaware if the smallest possible values of γ_{r} have been determined for any r ≥ 9.

Lemma 3.2. Let E be an elliptic curve defined over a number field K. Let R be the regulator of E(K). If the rank r is ≥ 1 then there exists a point Q in E(K) of infinite order such that

ĥ(Q) ≤ γ_{r}R^{\frac{1}{r}}  (33)

Proof. Suppose Q_{1}, …, Q_{r} is a basis for Ê(K). If Q = ∑_{i=1}^{r} m_{i}Q_{i} then

ĥ(Q) = ∑_{i,j=1}^{r} m_{i}m_{j} < Q_{i}, Q_{j} > .  (34)

Recall that the height pairing matrix H(Q_{1}, …, Q_{r}) = (< Q_{i}, Q_{j} >) is symmetric positive definite, and its determinant is R, the regulator of E(K). It follows from Lemma (30) that there exist an m ≠ 0 integral such that

ĥ(Q) = ( ∑_{i,j=1}^{r} m_{i}m_{j} < Q_{i}, Q_{j} >) ≤ γ_{r}R^{\frac{1}{r}} .  (35)

Since Q_{1}, …, Q_{r} is a basis for Ê(K) and m ≠ 0, Q must have infinite order, and the Lemma now follows.

We now combine the above with the observation (27) to deduce the following theorem.

Theorem 3.1. Let E be an elliptic curve defined over a number field K. Suppose that E(K) contains no point Q of infinite order with canonical height ĥ(Q) ≤ λ where λ is some positive real number. Suppose that P_{1}, …, P_{r} generate a sublattice of Ê(K) of full rank r ≥ 1. Then the index n of the span of P_{1}, …, P_{r} in Ê(K) satisfies

n ≤ R(P_{1}, …, P_{r})^{\frac{1}{2}} (\frac{γ_{r}}{λ} )^{\frac{r}{2}}  (36)

where R(P_{1}, …, P_{r}) is the determinant of the height pairing matrix and

\begin{matrix}γ_{1}^{1} = 1, & γ_{2}^{2} = \frac{4}{3}, & γ_{3}^{3} = 2, & γ_{4}^{4} = 4, \\ γ_{5}^{5} = 8, & γ_{6}^{6} = \frac{64}{3}, & γ_{7}^{7} = 64, & γ_{8}^{8} = 2^{8} \end{matrix}  (37)

and for r ≥ 9

γ_{r} = (\frac{4}{π} ) Γ (\frac{r}{2} + 1)^{\frac{2}{r}}  (38)

Proof. By Lemma 3.2, if R is the regulator of E(K) then there exists Q in E(K) of infinite order such that

ĥ(Q) ≤ γ_{r}R^{\frac{1}{r}} .

It follows that

λ ≤ γ_{r}R^{\frac{1}{r}} .

But R = \frac{1}{n^{2}} R(P_{1}, …, P_{r}). Hence

λ^{r} ≤ \frac{γ_{r}^{r}R(P_{1}, …, P_{r})}{n^{2}}.

Rearranging, we get the required inequality

n ≤ R(P_{1}, …, P_{r})^{\frac{1}{2}} (\frac{γ_{r}}{λ} )^{\frac{r}{2}} .

4. A Sub-lattice Enlargement Procedure

Suppose we are given P_{1}, …, P_{r} which is a basis for a sublattice of Ê(K) of full rank. By the methods of the previous section, we can establish an upper bound for n, the index of this sublattice in Ê(K). If n < 2, then it is clear that P_{1}, …, P_{r} is a basis for Ê(K) and the infinite descent is finished.

Suppose now that the method of the previous section gave us a bound n ≤ α for some α ≥ 2. Here it is necessary to check, for each prime p ≤ α whether or not the index n is divisible by p. Equivalently, we must determine if there exist a_{1}, …, a_{r} ∈ ℤ, not all divisible by p. such that

∑ a_{i}P_{i} = pQ  (39)

for some Q ∈ Ê(K).

It is clear that in checking this we can assume that |a_{i}| ≤ (p − 1)/2. This leaves us with a finite number of equations of type (39) to solve. We explain how these may be solved later. However, as these equations can be many, it is useful to start with some sieving. In practice, we have found the sieving described below to very effective.

4.1. Sieving. In the notation of above, given a prime p ≤ α, we let P_{r+1}, …, P_{r+s} be a basis for T or(E(K))/pT or(E(K)), where T or(E(K)) is the torsion subgroup of E(K) (and so typically s = 0). We let

V_{p} = {ā ∈ 𝔽_{p}^{r+s} : if a ∈ ℤ^{r+s} and a ≡ ā (mod p) then ∑_{i=1}^{r+s} a_{i}P_{i} ∈ pE(K)}

It is clear the V_{p} is an 𝔽_{p}-linear subspace of 𝔽_{p}^{r+s} and that the index n is divisible by p if and only if V_{p} ≠ {0}.

Suppose that υ ∈ M_{K} is a prime such that:

1. E has good reduction at υ,

2. |E(k_{υ})| is divisible by p but not by p^{2}.

Write |E(k_{υ})| = lp where p does not divide l.

We let π be a uniformizer at υ and compute P′_{i} ≡ lP_{i} (mod π). If P′_{i} ≡ 0 (mod π) for i = 1, …, r + s, then the sieving modulo π will give us nothing and we should start with another υ ∈ M_{K} satisfying the two conditions above. However, suppose, say that P′_{1} is not 0 (mod π). We note that the subgroup lE(k_{υ}) of E(k_{υ}) is cyclic of order p, and contains P′_{1}, …, P′_{r+s}; in particular P′_{1} (mod π) generates lE(k_{υ}). By computing all the multiples of P′_{1} (mod π), we determine m_{i} such that P′_{i} ≡ m_{i}P′_{1} (mod π). Hence, if (ā_{1}, …, ā_{r+s}) ∈ V_{p}, we must have that

∑ m_{i}ā_{i} = 0  (40)

in 𝔽_{p}. This gives us a relation that must be satisfied by the vectors in V_{p}. If we were to compute r + s independent relations by this method, then V_{p} = {0}, and the index would not be divisible by p.

At the very least, our hope is that by sieving modulo a few of these primes π, we have reduced V_{p} to being in a much smaller subspace of 𝔽_{p}^{r+s}, and so we have considerably reduced the number of equations of type (39) to be checked.

Our method of sieving has an obvious gap, which is to find υ ∈ M_{K}, for which |E(k_{υ})| is divisible by p but not p^{2}. At least the second assumption is not always attainable (for example if T or(E(K)) had a subgroup of order p^{2}). So we note that the assumption that p^{2} does not divide |E(k_{υ})| can be easily circumvented after determining the structure of the p-Sylow subgroup of E(k_{υ}), as the reader may readily verify. However, the assumption that p divides |E(k_{υ})| is essential to the idea of the sieving.

If primes υ ∈ M_{K} satisying the conditions above exist, we hope to uncover some by computing sufficiently many |E(k_{υ})|. For K = ℚ there exist efficient methods of computing |E(𝔽_{q})| for primes q, and judging from [Cohen] (pages 396-398), these have become very impressive.

4.2. Solving the Equation P = pQ. If the sieving described above has not been entirely successful in proving that V_{p} = {0}, then it will leave us with a subspace V′_{p} of 𝔽_{p}^{r+s}, containing V_{p} (V′_{p} is simply the set of all solutions to the equations (40)). Here it is useful to take a projective subset of V′_{p}, which we denote by S_{p}; we will let S_{p} be a subset of ℤ^{r+s}\ {0} with the following properties

1. if (b_{1}, …, b_{p}) ∈ S_{p}, then |b_{i}| ≤ (p−1)/2 unless p = 2 in which case b_{i} = 0 or 1,

2. for every (ā_{1}, …, ā_{r+s}) ∈ V_{p}, there exists exactly one (b_{1}, …, b_{p}) ∈ S_{p} such that (ā_{1}, …, ā_{r+s}) ≡ β(b_{1}, …, b_{p}) (mod p) for some β ∈ 𝔽_{p}.

It is clear that all that remains is to check, for all (b_{1}, …, b_{p}) ∈ S_{p}, if

∑_{i=1}^{r+s} b_{i}P_{i} = pQ  (41)

for some Q ∈ E(K).

For each (b_{1}, …, b_{p}) ∈ S_{p}, the equation (41) has exactly p^{2} solutions in E(ℂ), and it is not at all difficult to find these p^{2} possible Q = (x, y) ∈ E(ℂ) with x, y ∈ ℂ computed as accurately as is desired using elliptic logarithms (see [Cohen]). This leaves us with the problem of deciding, given a sufficiently accurate computation of x, y ∈ ℂ, whether or not these are in our number field K. We make use of the following Lemma.

Lemma 4.1. Suppose the elliptic curve E is given by Weierstrass equation (3) with a_{1}, …, a_{6} ∈ O_{K}, and suppose that P = nQ, where P = (x_{1}, y_{1}) and Q = (x_{2}, y_{2}) are in E(K)\ {0}. If υ ∈ M_{K} and υ(x_{2}) < 0 then υ(x_{1}) ≤ υ(x_{2}).

Moreover, if c ∈ O_{K} is such that cx_{1} ∈ O_{K}, then cx_{2} ∈ O_{K}.

Proof. Let E′ be the minimal Weierstrass equation at υ, and let (x′, y′) ∈ E′(K_{υ}) correspond to coordinates (x, y) ∈ E(K_{υ}). Then by [Silv2] p172, there exists u, r, t, s ∈ O_{υ} such that

x = u^{2}x′ + r
y = u^{3}y′ + u^{2}sx′ + t.

If υ(x) < 0 then υ(x′) = υ(x) − 2υ(u), where υ(u) ≥ 0. Hence it is sufficient to assume that υ(x′_{2}) < 0 and show that υ(x′_{1}) ≤ υ(x′_{2}).

Let υ(x′_{2}) = −2m, where m ∈ ℤ (as is well known, υ(x′_{2}) < 0 implies that 3υ(x′_{2}) = 2υ(y′_{2}) and hence that υ(x′_{2}) is even). Then the subset

E′_{m}(K_{υ}) = {(x′, y′) ∈ E′(K_{υ}) : υ(x′) ≤ −2m} ∪ {0}

is a subgroup of E′(K_{υ}) (see for example [Silv2], p187). Hence P′ ∈ E′_{m}(K_{υ}) and υ(x′_{1}) ≤ −2n = υ(x′_{2}).

This concludes the proof of the first part of the Lemma. The second part is now obvious.

Hence given (b_{1}, …, b_{r}) ∈ S_{p}, we calculate P = (x_{1}, y_{1}) = ∑ b_{i}P_{i}, and find c ∈ O_{K} such that cx_{1} ∈ O_{K}. If P = pQ, with Q = (x_{2}, y_{2}) ∈ O_{K}, then cx_{2} ∈ O_{K} by the above Lemma. So if we compute the p^{2} values x_{2} accurately enough ^{3} we can determine if any of the cx_{2} is expressible as a ℤ-linear combination of any ℤ-basis for O_{K}, using an LLL-based algorithm such as the one given on page 100 of [Cohen]. (Of course, if K = ℚ, then we can be much more down to earth. We simply calculate the x_{2}s accurately enough to see if any of cx_{2} is an integer to many decimal places.) If any cx_{2} seems to equal an element a ∈ O_{K}, then we can substitute a/c for x in the equation for E and ask if there is a solution y ∈ K.

If we have found that none of the equations (41) is soluble with Q ∈ E(K), then we have proven that the index is not divisible by p, and we can proceed to the next prime until we reach α, our upper bound for the index. However, if we find that ∑ b_{i}P_{i} = pQ with Q ∈ E(K), then there is a 1 ≤ j ≤ r, such that p does not divide b_{j}. Here we replace P_{j} by Q. The index of the sublattice generated by the new P_{1}, …, P_{r} in Ê(K) is ≤ α/p. In any case, we continue until we get to show that the index is 1.

5. Examples

Example 5.1. Here we return to our Example on page 12

E : Y^{2} = X^{3} − 73705X − 7526231.

We recall that we established

h(P) − ĥ(P) ≤ 0.8215  (42)

for all P ∈ E(ℚ). It is easy to show that this curve has no torsion. Using Cremona’s program mwrank, we found that the 2-part of the Tate-Shafarevich group is trivial, that the rank is 4, and that a basis for E(ℚ)/2E(ℚ) is

P_{1} = (−137, −1), P_{2} = (−157, −419), P_{3} = (−175, −113), P_{4} = (413, −5699);

this the program did in approximately 1.5 minutes.

The determinant of the height pairing matrix of P_{1}, …, P_{4} is 248.987. We search for points of logarithmic height ≤ 5 using Cremona’s program findinf. The search takes a few seconds and turns up only one point: P_{1} = (−137, −1). This has canonical height 4.41996. We note that had there been any point of canonical height ≤ 4.1, then its logarithmic height would have been ≤ 4.1 + 0.8215 < 5 and would have been uncovered by the search. Hence there are no points of canonical height ≤ 4.1. Using Theorem 3.1 we find that the index of the span of P_{1}, …, P_{4} is ≤ 1.88 . Hence we have found the Mordell-Weil group.

Next we compare our method to that outlined in the introduction. We recall that if (X, Y) ∈ E(ℚ), then we can write X = x/z^{2} where x, z ∈ ℤ. Hence to search up to logarithmic height 5, our search region on x, z is

−148 ≤ x ≤ 148, 1 ≤ z ≤ 12.

We note that had we used Zagier’s 1.1 on page 2, we would be required to enumerate all the points on E(ℚ) of canonical height ≤ 13.5831. If we combine this with our estimate (42) above, we must list all points with logarithmic height 14.4046. The corresponding search region is

3Here, if K has a real embedding, then it is useful to replace K with a real conjugate field at the begining of the computation, and so reject all the values of x_{2} which are not real (taking into account that in floating-point arithmetic over ℂ, a real number is one with a very small imaginary part!).

−1802346 ≤ x ≤ 1802346, 1 ≤ z ≤ 1321.

To search this region is possible using a well written program such as findinf mentioned above, but this would take a few hours on a work station.

Moreover we note that if we had to use Silverman’s bound on the difference h(P) − ĥ(P) as well as Zagier’s Lemma we would have to search for all points on E(ℚ) with logarithmic height ≤ 26.6073. Then the search region would be

−359255618029 ≤ x ≤ 359255618029, 1 ≤ z ≤ 599379.

Finally, at the suggestion of Dr Cremona, we compute the following table to give another illustration of how reasonable our bound of 0.8215 is.

\begin{matrix}P & h(P) & ĥ(P) & h(P) − ĥ(P) \\ P_{1} & 4.9199809 & 4.4199587 & 0.50002214 \\ P_{2} & 5.0562458 & 4.4416097 & 0.61463607 \\ P_{3} & 5.1647859 & 4.4605122 & 0.70427372 \\ P_{4} & 6.0234476 & 5.8817481 & 0.14169942 \end{matrix}

Example 5.2. We return here to Mestre’s curve:

E : Y^{2} + Y = X^{3} − 6349808647X + 193146346911036  (43)

We recall that on page 13 we proved that

h(P) − ĥ(P) ≤ 0.682862  (44)

for all points P ∈ E(ℚ). Mestre (see [Mestre]) has shown that this curve has rank at least 12 and has given 12 independent points (Mestre in fact gave a non-minimal model of the curve, and the equation (43) which we will work with is the minimal model). Moreover he has shown that the standard conjectures^{4} imply that the rank is 12. Here we will not take on the task of determining the rank unconditionally ^{5}; we will simply assume that the rank is 12, and obtain a basis from the points given by Mestre. Here is a list of the points that Mestre gave (after applying the change of variable which takes the points onto our minimal model (43)):

\begin{matrix}P_{1} = [49421, 200114], & P_{2} = [49493, 333458], & P_{3} = [49513, 362258], \\ P_{4} = [49632, 502899], & P_{5} = [49667, 538049], & P_{6} = [49797, 654674], \\ P_{7} = [49899, 735713], & P_{8} = [50012, 818375], & P_{9} = [50165, 921837], \\ P_{10} = [50215, 954017], & P_{11} = [50823, 1305633], & P_{12} = [51108, 1454591]. \end{matrix}

Here we proceeded with the sieving first. We used Pari/GP, which calculates |E(𝔽_{q})| for prime q using the Shanks-Mestre algorithm (see [Cohen] page 397). We found that it took roughly 1 second to compute |E(𝔽_{q})| for the first 200 primes q (i.e. for all the primes ≤ 1223). We wrote a program which does the following: for each prime 2 ≤ p ≤ 11 it lists all the primes q ≤ 1223 for which |E(𝔽_{q})| is divisible by p but not p^{2} as recommended by our sieving algorithm on page 17. Next, for each prime q satisfying these conditions, it computes a relation modulo p, which must be satisfied by the vectors in V_{p} as defined on page 17 using the idea described there; if it finds 12 independent relations then the rank of V_{p} is 0 and the index is not divisible by p. For each of the primes p, the program continues computing relations until the rank of the relations is 12 or until there are no more prime q ≤ 1223 satisfying the conditions described. The program took roughly 25 seconds to run and output that for all the primes p ≤ 11 the rank of relations found is 12 except for p = 2 where the rank was 10. We note that there are 47 primes q in the above range satisfying the criterion that 2 divides |E(𝔽_{q})| but 4 does not. Hence it seems very probable that the index is divisible by 2. Calculating the kernel of the relations obtained we get that

4The Birch and Swinnerton-Dyer conjecture, the Taniyama-Weil conjecture, and a suitable Riemann hypothesis.

5Here mwrank would take too long. In the absence of 2-torsion, mwrank uses the algorithm for 2-descent described in [Bi, SwD] and in [Cre] pages 68-76. In this algorithm the size of the search region for the homogeneous spaces is roughly proportional to the square root of the discriminant of the elliptic curve. In cases where the discriminant is very large, such as that for Mestre’s curve above, the algorithm is no longer practical. Unfortunately there does not seem to be any unconditional algorithm suited for determining Mordell-Weil groups of curves of large discriminant and no torsion.

V′_{2} = span {(1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0), (1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1)} (mod 2).

Hence we want to test if any of the 3 points P_{1} + P_{4} + P_{5} + P_{7} + P_{9} + P_{10}, P_{1} + P_{4} + P_{5} + P_{8} + P_{12}, P_{7} + P_{8} + P_{9} + P_{10} + P_{12} is 2-divisible in E(ℚ). Using Pari/GP we calculate the periods of E and the 2-division points ^{6} of the first 2 points. We get for each one a division point which is integral to 50 decimal places. We checked that these give us integral points on the curve. We replace our old P_{7}, and P_{8} with these two new points:

\begin{aligned}P_{7} & = & [38756, −2294721] \\ P_{8} & = & [208314, 88938858], \end{aligned}

thus gaining index 4.

We repeat the sieving for p = 2. This time the rank of relations obtained for p = 2 is 11. We find that if the index is still divisible by 2 then P_{3} + P_{5} + P_{6} + P_{8} + P_{10} + P_{11} + P_{12} must be 2-divisible in E(ℚ). Here none of the 2-division points of this were integral and we used Lemma 4.1 to recover a rational 2-division point. This becomes our new P_{3}:

P_{3} = [\frac{2739835340}{5041}, \frac{141949849330392}{357911}] .

Repeating the sieving described for p = 2 we find that the rank of relations obtained is 12, and hence the index of the span of our new P_{1}, …, P_{12} is not divisible by 2. Moreover, this index is not divisible by any prime 3 ≤ p ≤ 11 since the index of the span of the original points was not.

We return to the sieving again. We calculate |E(𝔽_{q})| for the first 2500 primes q (i.e. all the primes q ≤ 22307), and we extend our range for the prime p to all the primes ≤ 200. It took Pari/GP roughly 25 seconds to compute all the |E(𝔽_{q})| for all the primes q ≤ 22307. Our program this time took about 10 minutes to stop. In each case the rank of relations computed was 12 except for p = 167, 179, 191 where the ranks were respectively 8, 10, 10. Hence if the index of the span of our new P_{1}, …, P_{12} is not 1, then it must be ≥ 167.

The determinant of the height matrix of P_{1}, …, P_{12} is

R(P_{1}, …, P_{12}) = 586593208.77747

6Our use of terminology here is unconventional. Normally the term ‘2-division point’ denotes a point of order 2. Where as we say Q is a 2-division point of P to mean P = 2Q.

and computing γ_{12} we get 3.81181 according to formula (38) . Hence Theorem 3.1 gives us that if there are no rational points on E with canonical height ≤ λ then the index of the span of P_{1}, …, P_{12} in E(ℚ) satisfies:

n ≤ \frac{74295365.4988}{λ^{6}}.

Using this inequality we find that if there where no points of canonical height ≤ 8.73 then the index would be ≤ 166.9 and we would be finished. Using the inequality (44) we see the need to find all points of logarithmic height ≤ 9.41. We used Cremona’s program findinf and found none in that range of canonical height ≤ 8.73 (the program took roughly 5 minutes to list all the points of logarithmic height ≤ 9.41). Hence the points listed below form a basis assuming that the rank (as predicted by the Birch and Swinnerton-Dyer conjecture) is 12:

\begin{matrix}P_{1} = [49421, 200114], & P_{2} = [49493, 333458], & P_{3} = [\frac{2739835340}{5041}, \frac{141949849330392}{357911}] , \\ P_{4} = [49632, 502899], & P_{5} = [49667, 538049], & P_{6} = [49797, 654674], \\ P_{7} = [38756, −2294721], & P_{8} = [208314, 88938858], & P_{9} = [50165, 921837], \\ P_{10} = [50215, 954017], & P_{11} = [50823, 1305633], & P_{12} = [51108, 1454591]. \end{matrix}

Example 5.3. Here we return to the curve

Y^{2} + XY = X^{3} − 5818216808130X + 5401285759982786436  (45)

In [Kret] Kretschmer gave this as a curve of (exact) rank 8 with torsion of order 2, but did not give the points he found on the curve. We used Cremona’s program mwrank and it gave a basis for E(ℚ)/2E(ℚ):

P_{1} = [1410240, −29977314],  P_{2} = [1704648, −661672482],
P_{3} = [1421184, −55353570],  P_{4} = [259761720/125, −189069355038/125],
P_{5} = [4740024, 9180268266],  P_{6} = [975216, 808674546],
P_{7} = [7028688, −17659711842], P_{8} = [3418038804/289, 195936026213238/4913],

Q = [1402932, −701466],

where P_{1}, …, P_{8} are of infinite order and Q is a point of order 2. Here it is easy to show that there are no other torsion points. It remains to complete the infinite descent.

Of course the index of the span of the points above is not divisible by 2 since the points are independent modulo 2E(ℚ). Sieving (as in the above example) with roughly 200 primes (here we excluded all the primes of bad reduction), we were able to show that the index of the span of the given points is not divisible by 5, 7, 11, 13 and detected a possibly 3-divisible linear combination of the points. We found

P_{4} − P_{5} − P_{6} − P_{7} + P_{8} = 3 [−2623596, −1613325930]

and hence replacing P_{8} by

P_{8} = [−2623596, −1613325930]

we reduce the index by a factor of 3. Repeating the sieving we found that the new index is not divisible by 3. Now we continued the sieving using 15000 primes q and our program proved that the index is not divisible by any prime p less than 500 (this took roughly 30 minutes).

The determinant of the height pairing matrix of the new P_{1}, …, P_{8} is 184808.298. Using Theorem 3.1 it is now sufficient to show that there are no points of canonical height ≤ 1.96 whence it would follow that the index is 1. Here we recall that we proved (on page 14) that

h(P) − ĥ(P) ≤ 15.70819.

and so that to check that there are no points of canonical height ≤ 1.96 using this it would necessary to uncover all the points of logarithmic height ≤ 17.67. We expect that this computation would take roughly 10 days. However we also proved that for any point P there is a point T which is either 0 or Q such that

h(P + T) − ĥ(P) ≤ 11.03099  (46)

Now it is sufficient to enumerate all the points of logarithmic height ≤ 13 and check that none have canonical height ≤ 1.96. We did this in roughly 45 minutes using findinf. Hence it follows that

P_{1} = [1410240, −29977314],  P_{2} = [1704648, −661672482],
P_{3} = [1421184, −55353570],  P_{4} = [259761720/125, −189069355038/125],
P_{5} = [4740024, 9180268266],  P_{6} = [975216, 808674546],
P_{7} = [7028688, −17659711842], P_{8} = [−2623596, −1613325930]

Q = [1402932, −701466],

are a basis for E(ℚ).

Finally we would like to point out that we were able to obtain the bound (46) using the fact that the torsion group surjects onto E(ℚ_{p})/E^{0}(ℚ_{p}) for most of the primes where the Tamagawa index is not 1. Since this will not be be the case for most curves we would like to illustrate a third method which can be used to complete the infinite descent when the bound for h(P) − ĥ(P) is too large. We note that for all the non-archimedean primes except 2 and 3, the Tamagawa index is either 1 or 2 (see the table on page 14). In any case, if P ∈ E(ℚ) was of infinite order, and had canonical height ≤ 1.96, then 2P will have canonical height ≤ 7.84 and will have good reduction at all the non-archimedean primes except possibly at 2 or 3. Hence, in the notation of Theorem 2.1 we have

ϵ(p, 2P) = 1

for all primes p ≠ 2, 3, ∞ and

ϵ(p, 2P) ≤ ϵ_{p}

for p = 2, 3, ∞. Using the values of ϵ_{p} given in the table on page 14 for the primes p = 2, 3, ∞ and Theorem 2.1 we get

h(2P) − ĥ(2P) ≤ 6.39956.

Hence to uncover 2P we need to find all points of logarithmic height ≤ 14.24 and this would not take much longer than the search we have already done. Finally we would have to test each point found with canonical height ≤ 7.84 to see if it is twice a point.

6. Concluding Remarks

Regarding the bound for h − ĥ, it would be useful to develop better methods for calculating the constants ϵ_{υ}. Here we suspect that for υ non-archimedean, a case-by-case method (reminiscent of Tate’s algorithm) exists, and would be best for machine implementation of the algorithm.

We would also like to take this opportunity to point out that it would be of great value if the 2-descent algorithm in [Bi, SwD] was improved, or extended to cope with elliptic curves defined over number fields.

Acknowledgment . I am greatly indebted to J. Cremona for suggesting this problem to me and guiding my work on it, and also for his detailed reading of this paper and for making many valuable comments and corrections. I am also grateful to N. Smart for asking questions which stimulated many of the developments in this paper, and to an anonymous referee for pointing out many corrections.

References

[Bi, SwD] B.J. Birch and H.P.F. Swinnerton-Dyer, Notes on Elliptic Curves I, J. Reine Angew.

Math. 212 (1963), 7–25.

[BGZ] J.P. Buhler, B.H. Gross, and D.B. Zagier, On the Conjecture of Birch and Swinnerton-Dyer for an elliptic curve of rank 3, math. Comp. 44 (1985), 473–481.

[Brem] A. Bremner, On the Equation Y^{2} = X(X^{2}+p), in “Number Theory and Applications” (R.A. Mollin, ed.), Kluwer, Dordrecht, 1989, 3–23.

[Brem, Ca] A. Bremner and J.W.S. Cassels, On the Equation Y^{2} = X(X^{2} + p), Math. Comp. 42

(1984), 257–264.

[Ca1] J.W.S. Cassels, Lectures on Elliptic Curves, LMS Student Texts, Cambridge University Press, 1991.

[Ca2] J.W.S. Cassels, Rational Quadratic Forms, LMS Monographs, Academic Press (London), 1978.

[Ca3] J.W.S. Cassels, Introduction to the Geometry of Numbers, Springer-Verlag, 1959.

[Cohen] H. Cohen, A Course in Computational Algebraic Number Theory, GTM 138, Springer-Verlag, 1993.

[Cre] J.E. Cremona, Algorithms for Modular Elliptic Curves, Cambridge University Press, 1992.

[Dem] V. A. Dem’janenko, An estimate of the remainder term in Tate’s formula, Mat. Zametki 3 (1968), 271–278. (Russian)

[Ge, Zi] J. Gebel and H.G. Zimmer, Computing the Mordell-Weil group of an elliptic curve over Q, in “Elliptic Curves and related Topics”, ed. H.Kisilevsky and M. Ram. Murty, CRM Proceedings and Lecture Notes Volume 4, American Mathematical Society 1994.

[GPZ] J. Gebel, A. Pethő, and H.G. Zimmer, Computing integral points on elliptic curves, To Appear Acta. Arith.

[Hus] D. Husemoller, Elliptic Curves, Springer-Verlag, 1987.

[Kret] T.J. Kretschmer, Construction of Elliptic Curves with Large Rank, Math. Comp. 46 (1986), 627–635.

[Mestre] J-F Metre, Construction d’une courbe elliptique de rang ≥ 12, C.R. Acad. Sc. Paris 295 (1982), 643–644.

[Pari] C. Batut, D. Bernardi, H. Cohen, M. Olivier, User’s Guide to PARI-GP (version 1.38.62), 1994.

[Pr] H.A. Priestly, Introduction to Complex Analysis, Oxford University Press, 1985.

[Sieg] C. L. Siegel, Lectures on the Geometry of Numbers, Springer-Verlag, 1988.

[Sik] S. Siksek, Descents on Curves of Genus 1, PhD thesis, Exeter University, 1995.

[Silv1] J.H. Silverman, The Difference between the Weil Height and the Canonical Height on Elliptic Curves, Math. Comp. 55 (1990), 723–743.

[Silv2] J.H. Silverman, The Arithmetic of Elliptic Curves, GTM 106, Springer-Verlag, 1986.

[Silv3] J.H. Silverman, Computing heights on Elliptic Curves, Math. Comp. 51 (1988), 339– 358.

[Smart] N.P. Smart, S-integral points on elliptic curves, Proc. Camb. Phil. Soc. 116 (1994), 391–399.

[Sm, Ste] N.P. Smart and N.M. Stephens, Integral points on Elliptic Curves over Number Fields,

(to appear).

[Str, Top] R.J. Stroeker and J. Top, On the Equation Y^{2} = (X + p)(X^{2} + p^{2}), Rocky Mountain J. Math. (1994).

[Str, Tz] R.J. Stroeker and N. Tzanakis, Solving elliptic diophantine equations by estimating

linear forms in elliptic logarithms, Acta. Arith. 67 (1994), 177–196.

[Zimmer] H. G. Zimmer, On the difference of the Weil Height and the Neron-Tate height, Math. Z. 147 (1976), 35–51.

Department of Mathematics, University of Exeter, Exeter, UK

   E-mail address: SSiksek@maths.exeter.ac.uk