Descents on Curves of Genus 1

Samir Siksek

Submitted by Samir Siksek to the University of Exeter as a thesis for the degree of Doctor of Philosophy in the Faculty of Science July 1995

This thesis is available for Library use on the understanding that it is copyright material and that no quotation from the thesis may be published without proper acknowledgement.

I certify that all the material in this thesis which is not my own work has been clearly identified and that no material is included for which a degree has previously been conferred upon me.

Samir Siksek

Abstract. In this thesis we improve on various methods connected with computing the Mordell-Weil group of an elliptic curve. Our work falls into several parts:

1. We give a new upper bound for the difference of the logarithmic and canonical heights of points on elliptic curves.

2. We give a new method for performing the infinite descent on an elliptic curve. This is essentially a lattice enlargement algorithm.

3. We show how to compute the 2-Selmer group of an elliptic curve defined over the rationals by a method which has complexity

L_{D}(0.5, c_{1}) = (e^{(log D)^{0.5}(log log D)^{0.5}})^{c_{1}+o(1)},

where D = |Δ| the absolute value of the discriminant of the elliptic curve, and c_{1} is a positive constant. This part is based on joint work with N. Smart.

4. We give a recipe for ‘higher descents’ on homogeneous spaces arising from the 2-descent. This is useful in dealing with homogeneous spaces which are everywhere locally soluble but for which a search for points does not reveal any global points.

5. We give algorithms for checking our homogeneous spaces for solubility over completions of number fields.

Acknowledgements

I am grateful to my supervisor John Cremona for his help and encouragement and for suggesting the topic of the thesis to me. I would also like to thank EPSRC for their financial support, Robin Chapman for putting up with my questions, Ray Miller and Jeremy Bygott for help with L^{A}TEX.

Finally I would like to thank my family for their patience and support.

Contents

1 Introduction 6

1.1 The Mordell-Weil Theorem . . . . . . . . . . . . . . . . . . . . . 7 1.1.1 The Weak Mordell-Weil Theorem . . . . . . . . . . . . . . 7 1.1.2 The Infinite Descent . . . . . . . . . . . . . . . . . . . . . 9

1.2 Outline of the Usual Method of Computing the Mordell-Weil Group 11 1.2.1 Computing the Torsion Subgroup of E(K) . . . . . . . . 11 1.2.2 Computing the 2-Selmer Group of E . . . . . . . . . . . . 12 1.2.3 Computing E(K)/2E(K) . . . . . . . . . . . . . . . . . . 13 1.2.4 The Infinite Descent: Computing E(K) from E(K)/2E(K) 14

1.3 Applications of Computing the Mordell-Weil Group . . . . . . . 15

1.3.1 Describing Rational Solutions to Elliptic Diophantine Equa-

tions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3.2 Integral Points on Elliptic Diophantine Equations. . . . . 16 1.3.3 Rational Points on Certain Curves of Genus > 1. . . . . . 17 1.3.4 Rational Points on Certain Surfaces. . . . . . . . . . . . . 18

1.4 Computer Packages . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.4.1 mwrank and findinf . . . . . . . . . . . . . . . . . . . . . 19 1.4.2 Pari/GP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2 The Infinite Descent 21

2.1 The bound on the difference h(P) − ĥ(P) . . . . . . . . . . . . . 21 2.1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.2 υ is Real . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.1.3 υ is Complex . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.1.4 υ is Non-Archimedean . . . . . . . . . . . . . . . . . . . . 33 2.1.5 The Height Modulo Torsion . . . . . . . . . . . . . . . . . 34 2.1.6 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.2 The Canonical Height and Results from the Geometry of Numbers 38 2.3 A Sub-lattice Enlargement Procedure . . . . . . . . . . . . . . . 42

2.3.1 Sieving . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.3.2 Solving the Equation P = pQ . . . . . . . . . . . . . . . . 44

2.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3 Computing the 2-Selmer Group of an Elliptic Curve 54 3.1 The Method of Brumer and Kramer . . . . . . . . . . . . . . . . 55 3.2 Finding K(R, 2) . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.3 Computing The 2-Selmer Group . . . . . . . . . . . . . . . . . . 60

4 Descents on the Intersections of 2 Quadrics 63 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.2 The Homogeneous Spaces for the 2-Descent . . . . . . . . . . . . 65 4.3 ‘Coprimality’ in number fields . . . . . . . . . . . . . . . . . . . . 66 4.4 Diagonalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.5 Parametrization of the Singular Combinations . . . . . . . . . . . 69 4.6 Descents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

4.6.1 F has at least 2 roots defined over K . . . . . . . . . . . 71 4.6.2 F is the Product of 2 Irreducible Quadratic Factors … 73 4.6.3 F has exactly one root defined over K . . . . . . . . . . . 75

4.7 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.8 Local to Global- A Counter Example . . . . . . . . . . . . . . . . 81

5 Local Solubility I: Over Non-Archimedean Completions 86 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.2 Algorithm I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.3 Algorithm II: F has a rational root over O_{υ} . . . . . . . . . . . . 90

5.3.1 Parametrizing the Singular Combination . . . . . . . . . . 90 5.3.2 Local Solubility Testing for Y^{2} = g(X) . . . . . . . . . . . 91

6 Local Solubility II: Over Archimedean Completions 96 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.2 Reducing to Totally Real F (λ) . . . . . . . . . . . . . . . . . . . 97 6.3 Results on the Totally Real Case . . . . . . . . . . . . . . . . . . 98 6.4 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 6.5 A Special Case for Two Quadrics in Four Variables . . . . . . . . 100

A Hensel Lifting for Y^{2} = g(X) 102

B The Geometry of the Intersection of two Quadrics 104 B.0.1 The Combinant . . . . . . . . . . . . . . . . . . . . . . . . 107

Chapter 1

Introduction

In this thesis we improve on various methods connected with computing the Mordell-Weil group of an elliptic curve. This is a deep and non-trivial problem with many interesting applications to diophantine equations. For reasons which will be made clear, it is not within the present “state-of-the-art” to be able to determine the Mordell-Weil group of every elliptic curve, even in theory. However we genuinely believe that the existing methods together with those developed in this thesis will eventually make it practical to compute the Mordell-Weil group of most elliptic curves defined over the rationals with a reasonably small discriminant.

We start by sketching the proof of the Mordell-Weil theorem. We assume that the reader is familiar with the basic theory of elliptic curves. Excellent references on the theory of elliptic curves are [Si2] and [Ca1]. For the basic algorithms concerning computing the Mordell-Weil group over the rationals see [Cre].

1.1 The Mordell-Weil Theorem

Let K be a number field. We shall normally take our elliptic curve defined over K to be in standard Weierstrass form:

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

where a_{1}, …, a_{6} are in the ring of integers O_{K} of K.

Theorem 1.1.1 E(K) is finitely generated.

This was proved by Mordell for elliptic curves defined over the rationals, and later extended by Weil to elliptic curves (as well as higher-dimensional abelian varieties) defined over arbitrary number fields. We shall sketch the basic idea of the proof, which falls in to 2 parts: the first is called the weak Mordell-Weil theorem, where one proves that E(K)/2E(K) is finite, and the second is called the infinite descent, where it is shown that this implies that E(K) is finitely generated.

1.1.1 The Weak Mordell-Weil Theorem

By a standard change of variable we may suppose that

E : Y^{2} = X^{3} + AX + B,  (1.2)

where A, B ∈ O_{K}. We let f(X) = X^{3} + AX + B, and let L be the K-algebra defined by

L = K[X]/(f(X)).

Then L is the sum of as many fields as f(X) has irreducible factors in K[X]. We let Θ be the image of X under the natural map

K[X] → L.

It turns out that we have a group homomorphism (see [Ca1] page 66 or [Ca6] page 31)

α : E(K) → L^{∗}/L^{∗}^{2}  (1.3)

given explicitly by ^{1}

P = (x, y) → (x − Θ)L^{∗}^{2}.  (1.4)

This homomorphism has kernel 2E(K). Moreover its image is some finite subgroup of L^{∗}/L^{∗}^{2}. Hence it will follow that the group E(K)/2E(K) is finite. This is the first step in the proof of the Mordell-Weil Theorem.

For the ‘generic’ case where f(X) is irreducible over K, and hence L is a field, we shall be more explicit about the image of α. It can be shown that the image of α is contained in the group

L(R, 2) = {β ∈ L^{∗}/L^{∗}^{2} : Norm_{L/K}(β) ∈ K^{∗}^{2} and ord_{℘}(β) ≡ 0 (mod 2) if ℘ ∉ R}.

(1.5)

where R is the set of all primes in L which are either infinite or divide the discriminant Δ of the elliptic curve.

It will be seen that to determine E(K)/2E(K) it is sufficient to determine for each s ∈ L(R, 2) whether or not it is in the image of the map α and if it is to give a P ∈ E(K) satisfying α(P) = s.

Hence given s ∈ L(R, 2) we must determine if it is possible to have

(x − Θ) = sϵ^{2}  (1.6)

for some x ∈ K and ϵ ∈ L^{∗}, and if so determine the x (and ϵ) explicitly. Now any such ϵ can be written in the form

ϵ = u_{1} + u_{2}Θ + u_{3}Θ^{2}

where u_{1}, u_{2}, u_{3} ∈ K. Substituting in equation (1.6) and comparing coefficients of 1, Θ, Θ^{2} we get

Q_{1}(u_{1}, u_{2}, u_{3}) = x  (1.7)
Q_{2}(u_{1}, u_{2}, u_{3}) = −1  (1.8)
Q_{3}(u_{1}, u_{2}, u_{3}) = 0,  (1.9)

1The definition must be adjusted appropriately to give the correct image of the points of order 2, if there are any. See [Ca1] page 67.

where Q_{1}, Q_{2}, Q_{3} are ternary homogeneous quadratic forms.

Here we would solve our problem for the particular s if and only if we can find a simultaneous solution to the last two equations above. We will call the simultaneous pair of equations ^{2}

\begin{matrix}Q_{2}(u_{1}, u_{2}, u_{3}) = −u_{4}^{2} \\ Q_{3}(u_{1}, u_{2}, u_{3}) = 0 \end{matrix} \}  (1.10)

a homogeneous space (see [Si2] page 287). It is convenient to point out here that it is not always possible to determine if our homogeneous space (1.10) has solutions over K (these would be termed global solutions). However, in principle, there is no problem in checking if our homogeneous space has solutions over every local completion of K, and this is plainly a necessary condition for it to have global solutions. When (1.10) has solutions over every local completion of K, we will say that it is everywhere locally soluble. It turns out the set of all s ∈ L(R, 2) for which the corresponding homogeneous space 1.10 is everywhere locally soluble forms a subgroup of L(R, 2). This is termed the 2-Selmer group. We note here for later reference that if we determine which of the pairs of equations (1.10) have rational solutions, and for each of these find a point on it, then we will be able to recover a complete set of coset representatives of E(K)/2E(K).

At any rate, for the proof of the Weak Mordell-Weil Theorem it suffices to note that L(R, 2) is finite, and hence that E(K)/2E(K) is finite.

1.1.2 The Infinite Descent

We assume that the reader is familiar with the basic theory of heights in projective space and on elliptic curves (see [Si2] page 205-220).

Recall, that if M_{K} is a complete set of inequivalent valuations on K, then we define the naive height of a point P = (X, Y) ∈ E(K) by

H(P) = ( ∏_{υ∈M_{K}} max \{1, |X|_{v}\}^{n_{v}})^{\frac{1}{[K:ℚ]}}  (1.11)

2Note that we will prefer to write these in homogeneous form.

where n_{v} = [K_{v} : ℚ_{v}].

We define the logarithmic height of the point P by h(P) = log H(P), and finally the canonical height of the point P by

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

It turns out that for any constant C, the points for which H(P) ≤ C are at most finitely many, and these may be effectively enumerated. To complete the proof of the Mordell-Weil Theorem we use the fact that E(K)/2E(K) is finite to show that there is a C such that the points for which H(P) ≤ C generate E(K). The first step here is to use the following theorem of Zagier.

Theorem 1.1.2 (Zagier) Let B_{1} > 0 be such that

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

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

Proof. See [Cre] p61 or [Si1] p740. □ Now it remains to show that if B_{1} is given by the above Theorem, then we can obtain a C such that the region H(P) ≤ C contains all the points for which ĥ(P) ≤ B_{1}. This is possible at once since the difference h(P) − ĥ(P) is absolutely bounded for any elliptic curve E. For example, Silverman has shown the following.

Theorem 1.1.3 (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}  (1.14)

whose coefficients are in the ring of integers of K. Let Δ be the discriminant of the equation (1.14) 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 (1.14)) by

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

where ^{3}, 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 [Si1]. □ If we let B_{2} be the bound for h(P) − ĥ(P) in Silverman’s Theorem above, then we see E(K) is generated by the points satisfying H(P) ≤ C where C = exp(B_{1}+B_{2}). This completes the (sketched) proof of the Mordell-Weil Theorem.

1.2 Outline of the Usual Method of Computing

the Mordell-Weil Group

The classical method of computing the Mordell-Weil group of an elliptic curve E over a number field K is via several distinct steps. We outline these below and explain if and why the method involved in each step is in need of improvement. Further we will summarize the contribution we have made towards making each step practical.

1.2.1 Computing the Torsion Subgroup of E(K)

This step is completely trivial for elliptic curves over ℚ (see [Cre] page 52). We will not consider the problem of computing the torsion subgroup for an elliptic curve defined over a number field.

3M_{K}^{∞} is the set of archimedean valuations on K.

1.2.2 Computing the 2-Selmer Group of E

The best method for computing the 2-Selmer group for elliptic curves defined over ℚ and of small discriminants is using the algorithm of Birch and Swinnerton-Dyer (see [Bi, SwD]). Indeed Cremona’s program mwrank (see page 19), which is an implementation of algorithm of Birch and Swinnerton-Dyer, computes 2-Selmer groups of elliptic curves of discriminants of size 10^{15} in a few minutes. In this algorithm the elements of the 2-Selmer group are represented by curves of the form

y^{2} = g(x)

where g(x) is a quartic polynomial with integral coefficients. Birch and Swinnerton-Dyer showed that for each element of 2-Selmer we can choose a representative as above where the coefficients of g(x) lie in a certain region and have given invariants. Hence the algorithm involves searching this region for the polynomials with the given invariants. It turns out that the size of this region is at least O(|Δ|^{\frac{1}{2}} ) where Δ is the discriminant of the elliptic curve E (See [Bi, SwD] page 11). This is in fact the obstruction to using the method for elliptic curves of large discriminant.

There is a much older method of determining the 2-Selmer group. Birch and Swinnerton-Dyer comment on this:

“It is possible to find the elements of G [the 2-Selmer group] by the classical process of descent; and for hand calculation this is probably the easiest way. However for any given curve … one needs to know the structure of the appropriate algebraic number field, and it is not convenient to investigate this by means of an automatic computer. We have therefore used a different procedure … ”. ([Bi, SwD] page 8).

Of course the situation concerning algorithms for computing the structure of algebraic number fields is now very different from that of the time Birch and Swinnerton-Dyer devised their algorithm ([Bi, SwD] appeared in 1963). There are now ‘subexponential’ algorithms for computing the class groups and fundamental units of algebraic number fields (see for example Chapters 5 and 6 of [Cohen] for a description of some of these). This strongly suggests that the descent via algebraic number fields deserves to be examined again. Indeed we show in Chapter 3, which is based on joint work with N. Smart, that this approach can be refined so that its complexity is

L_{D}(0.5, c_{1}) = (e^{(log D)^{0.5}(log log D)^{0.5}})^{c_{1}+o(1)},

where D = |Δ|, and c_{1} is a positive constant. This is better than the complexity of the method of Birch and Swinnerton-Dyer.

The only implementation of these ‘subexponential’ algorithms for computing the class groups and fundamental units that is available to us is part of the package Pari/GP (see page 19). According to the manual ([Pari] page 46) these programs are “completely experimental”, and we have found that they perform rather badly for cubic number fields of large discriminants. It is for this reason that no example is given for computing the 2-Selmer group using the method of Chapter 3. However it is hoped that improved implementations for computing the class group and fundamental units will make this method completely practical in the future.

1.2.3 Computing E(K)/2E(K)

Once we have computed the 2-Selmer group we hope to find enough points on E(K) to show that the map from E(K)/2E(K) to the 2-Selmer group is a surjection. Equivalently we wish to show that every homogeneous space corresponding to an element of the 2-Selmer group has point defined over K on it. This is not always possible because of the failure of the local-to-global principle for curves of genus 1. This leads us to the concept of ‘higher descent ’ discussed in Chapter 4 where we give a method often successful in resolving the problem of which homogeneous spaces have K-rational points. It should be noted that these methods do not always meet with success.

Both the computation of the 2-Selmer group and the method of ‘higher descent’ require algorithms for testing certain homogeneous spaces for local solubility. We give these in Chapters 5 and 6.

1.2.4 The Infinite Descent: Computing E(K) from E(K)/2E(K)

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.2) 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.1.3) 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, 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 canonical heights of the generators of E(K)/mE(K) are large .

3. It is also possible that 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 regions for the points of S increase 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 in to big savings in the actual size of the search region.

In Chapter 2 we will adopt a different approach to the infinite descent:

1. We will give an algorithm which will allow us, in most cases, to calulate 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.

1.3 Applications of Computing the Mordell-Weil

Group

As noted already, we will be concerned with the problem of determining a basis for the Mordell-Weil group of an elliptic curve. We hope to convince the reader that this is an interesting and engaging problem in itself. It is however appropriate to describe some of the applications of computing the Mordell-Weil group of an elliptic curve ^{4}:

1.3.1 Describing Rational Solutions to Elliptic Diophantine Equations.

Many diophantine problems are equivalent to computing the Mordell-Weil group of an elliptic curve, or showing that an elliptic curve has rank at least 1. This includes many geometrical problems. A well-known example is the so called ‘congruent number problem’ (see [Kob]): An integer n is said to be a ‘congruent number’ if it is the area of some right-angled triangle with rational sides. It turns out that n is congruent if and only if the elliptic curve

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

4It should be noted that what is presented here is necessarily a random sample, and that some parts are perhaps out of date. This is because of the vastness of the topic and the modest knowledge of the author. Nice references here are [Guy], [Mord].

has rank at least 1, and that to find a particular right-angled triangle with area n it necessary to find a point of infinite order on this curve. This can be a highly non-trivial problem. For example, as a corollary to the calculations in Section (4.7) it turns out that the simplest right-angled triangle having area 2833 has base and perpendicular

\frac{5334745291350384}{709516254613385}, \frac{2010059549319719705}{2667372645675192},

and has hypotenuse

\frac{1426240910614742861472434930476897}{1892544249217657898838245644920}.

1.3.2 Integral Points on Elliptic Diophantine Equations.

Many diophantine problems are equivalent to computing all the integral points on a model of an elliptic curve. For elliptic curves in standard minimal Weierstrass form there is now a practical algorithm for performing this using elliptic logarithms (see [GPZ], [Smart], [Str, Tz], and for a generalization to number fields [Sm, Ste]). These algorithms require the computation of the Mordell-Weil group beforehand. This method has been extended (see [Tz]) to finding the integral points on elliptic curves of the form

Y^{2} = f(X)

where f(X) ∈ ℤ[X] is a quartic polynomial. ^{5}

As an example, we mention Ljunggren’s infamous equation (see [Mord] page 271)

Y^{2} = 2X^{4} − 1.

Ljunggren had shown that the only integral solutions of this are (±1, ±1) and (±13, ±239). However his method was exceedingly complicated, especially for such an innocuous looking equation, and Mordell had wished if only a simpler proof could be found. It is striking to note that this can now be resolved by a couple of computer programs. Letting y = 2XY and x = 2X^{2} we find that

5See [Str, We] for an example which arises from the theory of Radon Transforms.

E : y^{2} = x(x^{2} − 2).  (1.15)

Using mwrank (see page 19) we find that the Mordell-Weil group of this elliptic curve is ⟨(0, 0)⟩ ⨁ ⟨(−1, 1)⟩. We thank N. Smart for computing the integral points on this equation using his own implementation of the elliptic logarithm method mentioned above. After a minute or so the program output that the only integral points on E are

(0, 0), (−1, ±1), (2, ±2), (338, ±6214).

It easily follows that the only integral solutions to Ljunggren’s equation are the ones he gave.

1.3.3 Rational Points on Certain Curves of Genus > 1.

Given a curve of genus > 1, we can occasionally cover an elliptic curve by this curve, and then use the Mordell-Weil group of the elliptic curve to obtain information about its rational points. We give one example of a method essentially due to Dem’Janenko (see [Ca5]). Suppose we wanted to determine the rational points on

X^{4} + Y^{4} = 2Z^{4}.  (1.16)

If (X, Y, Z) is a non-trivial solutions of the equation (1.16) then we may assume that X, Y, Z are coprime integers. It easily follows that

P_{1} = (\frac{2Z^{2}}{X^{2}} , \frac{2Y^{2}Z}{X^{3}} ) , P_{2} = (\frac{2Z^{2}}{Y^{2}} , \frac{2X^{2}Z}{Y^{3}} ) ,

are rational points on the elliptic curve (1.15). We note that the naive heights of P_{1}, and P_{2} are equal: it is clear that 2Z^{2} > X^{2}, Y^{2}. Hence it follows that the difference between their canonical heights is bounded. Using Silverman’s estimates for the difference between the logarithmic and canonical heights we get

|ĥ(P_{1}) − ĥ(P_{2})| ≤ 9.6988.

We recall that the Mordell-Weil group of (1.15) is

⟨(0, 0)⟩ ⨁ ⟨(−1, 1)⟩

where (0, 0) is a point of order 2 and (−1, 1) is of infinite order. Write

P_{i} = m_{i}(−1, 1) + n_{i}(0, 0)

where m_{i} ∈ ℤ and n_{i} ∈ {0, 1} (i = 1, 2). It follows that

|m_{1}^{2} − m_{2}^{2}| ≤ \frac{9.6988}{ĥ((−1, 1))} = 15.93.

From this we deduce that either m_{1} = m_{2} or |m_{1}|+|m_{2}| ≤ 15. It is now a simple matter to check that the only (non-trivial) solutions to (1.16) are (±1, ±1, ±1).

1.3.4 Rational Points on Certain Surfaces.

It is possible to describe certain surfaces by a parametric family of elliptic curves. In this case one can obtain information about the rational points on the surface by studying the Mordell-Weil groups of these elliptic curves. For example, in [SwD2], Swinnerton-Dyer uses this idea to show that the rational points on the variety

X^{4} + Y^{4} = Z^{4} + W^{4}

are dense (with respect to the Euclidean topology).

An impressive recent success for this method is the counterexample by N. D. Elkies (see [Elkies]) to a conjecture of Euler that there are no solutions in positive integers to

A^{4} + B^{4} + C^{4} = D^{4}.  (1.17)

Elkies parametrized this as a pencil of curves of genus 1. By finding the simplest curve in the pencil which is everywhere locally soluble and checking that it has a solution, he found a solution ^{6} to Euler’s (1.17):

2682440^{4} + 15365639^{4} + 18796760^{4} = 20615673^{4} .

He also showed that the rational points are dense in the real locus of

r^{4} + s^{4} + t^{4} = 1.

1.4 Computer Packages

In preparing the examples in this thesis, we have found it useful to use some computer packages and programs which we list below.

1.4.1 mwrank and findinf

These are programs written by J. Cremona for elliptic curves defined over ℚ. mwrank is an implementaion of the Birch and Swinnerton-Dyer method of 2descent ([Bi, SwD] and [Cre] pages 68-76). It also attempts an infinite descent via the traditional method explained on page 9.

The 2-descent step is remarkably successful for curves of small discriminant^{7}. The infinite descent is not so successful for reasons explained on page 14.

findinf is a program for searching for points up to a given logarithmic height on an elliptic curve using a quadratic sieve method.

1.4.2 Pari/GP

We have found this package very useful for number-theoretic computations. It has many functions for doing arithmetic on elliptic curves, including elliptic logarithms, and canonical height computations. Moreover it provides tools for dealing with modular arithmetic, algebraic numbers, p-adic numbers.

6Clearly this solution could not be easily found by a naive computer search. The smallest solution

95800^{4} + 217519^{4} + 414560^{4} = 422481^{4} was later found by Roger Frye - using Elkies’ ideas- in a search which took 100 hours of computer time.

7Though of course there is no guarantee of finding rational points on all the everywhere locally soluble homogeneous spaces.

All the programming we did was done using this package.

The Infinite Descent

The contents of this chapter have been accepted for publication by the Rocky Mountain Journal of Mathematics.

2.1 The bound on the difference h(P) − ĥ(P)

2.1.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}  (2.1)

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.1.3, there are other results which give bounds on the quantity h(P) − ĥ(P), most notably in [Zim] 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.1.3), 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.1.3 for the curve

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

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.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.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 (2.1) we define some associated constants (see [Si2] 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}  (2.2)

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}  (2.3)

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 an 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.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 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}  (2.4)

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

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.1.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 infimums 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 [Si3] 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.1.3 Let, for any valuation υ on K,

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

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.1.2).

5. If υ is non-archimedean, and

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

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

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

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

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 (2.5) exists and is equal to min(d_{υ}, d′_{υ}), and so is non-zero (by Lemma (2.1.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 arbitrarily 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.1).

For part 4 we note that if υ is non-archimedean and |X|_{v} > 1 then by the proof of Lemma (2.1.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 were the case then there would exist (X, Y) ∈ E(K_{υ}), with

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

But from equation (2.6) 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).  (2.7)

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

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

in ℤ[X, a_{1}, …, a_{6}]. This is straight forward but rather tedious to verify ( it is a slightly more general form of the congruence in 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 subgroup 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 [Si2]). 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.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}  (2.9)

by

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

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}  (2.11)

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.1.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}  (2.12)

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

Now if P = (X, Y) ∈ E(K) then by the duplication formula (see [Si2] p59) the x-coordinate of 2P is g(X)/f(X). Hence using the product definition for naive heights and Lemma (2.1.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}  (2.13)

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: to 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.1.2 υ is Real

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.1.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.1.3 υ is Complex

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.1.5 let f and g be as above. Then the continuous function k : ℂ → ℝ_{>0} defined by

k(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 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 k(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.1.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 k(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 k 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) inside the unit disc D. 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.1.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.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.1.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.1.3) (on page 27)

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

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.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 the algorithm given in the Appendix A can be used.

Corollary 2.1.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.1.5 The Height Modulo Torsion

As will be seen in the examples, curves where the bound obtained by Theorem (2.1.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.1.2 Under the notation and hypotheses of Theorem (2.1.1), let υ_{1}, …, υ_{n} be the (finitely many) valuations in M_{K} where the quantities μ_{υ} log(ϵ_{υ}) are non-zero. 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 ≤ Tor(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}  (2.16)

Proof. Let

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

Given any P ∈ E(K), and 1 ≤ i ≤ m we must have at least one of P + T_{j} has good reduction at υ_{i}. Hence, using Theorem (2.1.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}  (2.17)

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.1.6 Examples

Example 2.1.1

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

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 27, 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.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.1.4) we find ϵ_{∞} = 2.939442. Applying Lemma (2.1.1) we get

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

for all P ∈ E(ℚ).

Here we note that Silverman’s Theorem (1.1.3) gives a bound

h(P) − ĥ(P) ≤ 13.0242

Example 2.1.2 We begin with a curve of Mestre (quoted on page 234 of [Si2])

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

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 30 :

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.1) we get

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

for all points P ∈ E(ℚ). We note here that Silverman’s theorem (1.1.3) 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.1.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  (2.22)

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 somewhat large for the purpose of the infinite descent (see the continuation of this example on page 51). 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.1.2) we get that for all points P ∈ E(ℚ) there is a T ∈ {0, Q} such that

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

2.2 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.2).

In this section we develop a general technique for the infinite descent which is analogous to the reduction of the bound for the rank 1 case given above. The inspiration for much of this comes from Manin’s Theorem (see [Ge, Zi]). There it is shown, using the Geometry of Numbers, how an upper bound for the regulator gives an upper bound for heights of generators of a sublattice of full rank. Below, we shall use the Geometry of numbers to show how given a basis for a sublattice of full rank, and a little extra information, we get an upper bound on the index.

We shall employ the language of lattices. Following [Ge, Zi] we define Ê(K) = E(K)/Tor(E(K)), where Tor(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}  (2.23)

where for all P, Q in E(K)

⟨P, Q⟩ =: \frac{1}{2}(ĥ(P + Q) − ĥ(P) − ĥ(Q))  (2.24)

Let R(P_{1}, …, P_{r}) be the determinant of the height pairing 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})  (2.25)

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 (2.25)) 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 2.2.1 (Hermite, Minkowski and others) Suppose

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

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

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

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

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

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}  (2.29)

and for r ≥ 9

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

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

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

Lemma 2.2.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}}  (2.31)

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} > .  (2.32)

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 (2.28) 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}} .  (2.33)

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 (2.25) to deduce the following theorem.

Theorem 2.2.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}}  (2.34)

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}  (2.35)

and for r ≥ 9

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

Proof. By Lemma (2.2.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}} .

□

2.3 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  (2.37)

for some Q ∈ Ê(K).

It is clear that in checking this we can assume that |a_{i}| ≤ p/2. This leaves us with a finite number of equations of type (2.37) 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 be very effective.

2.3.1 Sieving

In the notation of above, given a prime p ≤ α, we let P_{r+1}, …, P_{r+s} be a basis for Tor(E(K))/pTor(E(K)), where Tor(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}^{0} 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 2 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 the multiples of P′_{i} (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  (2.38)

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 prime π, 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 (2.37) 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 Tor(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} satisfying the conditions above exist, we hope to uncover some by computing sufficiently many |E(k_{υ})|. If K = ℚ, then there exist efficient methods of computing |E(𝔽_{q})| for primes q, and judging from [Cohen] (pages 396-398), these have become very impressive.

2.3.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 (2.38)). 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_{r+s}) ∈ 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}\ {0}, there exists exactly one (b_{1}, …, b_{r+s}) ∈ S_{p} such that (ā_{1}, …, ā_{r+s}) ≡ β(b_{1}, …, b_{r+s}) (mod p) for some β ∈ 𝔽_{p}.

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

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

for some Q ∈ E(K).

For each (b_{1}, …, b_{r+s}) ∈ S_{p}, the equation (2.39) 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 2.3.1 Suppose the elliptic curve E is given by Weierstrass equation (2.1) 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 on E(K)\ {0}. If υ ∈ M_{K}^{0} 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 [Si2] 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 [Si2], p187). Hence P′ ∈ E′_{m}(K_{υ}) and υ(x′_{1}) ≤ −2m = υ(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}) ∈ S_{p}, we calculate P = (x_{1}, y_{1}) = ∑ b_{i}P_{i}, and find a 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 ^{1} 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 (2.39) 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.

2.4 Examples

Example 2.4.1 Here we return to our Example on page 35

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

We recall that we established

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

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.

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

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 (2.2.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.2) on page 10, we would be required to enumerate all the points on E(ℚ) of canonical height ≤ 13.5831. If we combine this with our estimate (2.40) above, we must list all points with logarithmic height 14.4046. The corresponding search region is

−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 effective our bound (2.40) 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 2.4.2 We return here to Mestre’s curve:

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

We recall that on page 36 we proved that

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

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 nonminimal model of the curve, and the equation (2.41) which we will work with is the minimal model). Moreover he has shown that the standard conjectures ^{2} imply that the rank is 12. Here we will not take on the task of determining the rank unconditionally ^{3}; 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 (2.41)):

\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}

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

3Here 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.

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 43. 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 43 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

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 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 were integral and we used Lemma (2.3.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 get 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

and computing γ_{12} we get 3.81181 according to formula (2.36) . Hence Theorem (2.2.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 were no points of canonical height ≤ 8.73 then the index would be ≤ 166.9 and we would be finished. Using the inequality (2.42) we see that we 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

\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 2.4.3 Here we return to the curve

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

In [Kret] Kretchmer 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 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 (2.2.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 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 be 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  (2.44)

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],

is a basis for E(ℚ).

Finally we would like to point out that we were able to obtain the bound (2.44) 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 (2.1.3)). 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.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 (2.1.3) for the primes p = 2, 3, ∞ and Theorem (2.1.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.

Computing the 2-Selmer

Group of an Elliptic Curve

When trying to compute the Mordell-Weil group of an elliptic curve one normally first computes the 2-Selmer group. This is a group which contains a subgroup isomorphic to E(ℚ)/2E(ℚ). Whilst computing the 2-Selmer group is certainly an effective procedure there is no known effective procedure for computing the subgroup isomorphic to E(ℚ)/2E(ℚ). However all is not lost as at least the 2-Selmer group gives one an upper bound on the rank of the elliptic curve. We set

L_{D}(α, β) = (e^{(log D)^{α}(log log D)^{1−α}})^{β+o(1)}.

This is a function which interpolates between polynomial time, α = 0, and exponential time, α = 1. In this chapter we show the complexity of computing the 2-Selmer group is O(L_{D}(0.5, c_{1})) where D denotes the absolute discriminant of the elliptic curve.

Let E be our elliptic curve given by

E : Y^{2} = X^{3} + AX + B.

We shall assume that the elliptic curve has no points of order 2 defined over ℚ. This is certainly the most difficult case for finding the 2-Selmer group. The modern method of computing the 2-Selmer group in this case goes back to the paper of Birch and Swinnerton-Dyer, [Bi, SwD]. In their method a search is carried out for the quartics which represent the homogeneous spaces given their invariants. As we noted in the Introduction (page 12), this method is certainly fast for small values of D, however it is not hard to see that its complexity is at least O(\sqrt{|D|}), [Bi, SwD][Page 11]. In the present chapter we shall show how the “old-fashioned” technique which is the basis for Weil’s proof of the Mordell-Weil Theorem combined with a method derived from a paper of Brumer and Kramer, [Brum, Kra], will determine the 2-Selmer group in our stated time. Our complexity is therefore much better than the Birch and Swinnerton-Dyer algorithm.

As we have pointed out already, this chapter is based on joint work with Dr N. Smart.

We let S denote the set of primes dividing 2D, we note that this has cardinality O(log D). Let K denote the number field generated by θ where θ^{3} + Aθ + B = 0. We will let R denote the set of primes of K lying above those in S as well as the infinite primes. As usual we let K(R, 2) denote the group of all elements of K^{∗}/K^{∗}^{2} such that by adjoining a square root of an element of K(R, 2) to K one obtains an extension of K unramified outside R. Equivalently we have

K(R, 2) = {α ∈ K^{∗}/K^{∗}^{2} : ord_{℘}(α) ≡ 0 (mod 2) if ℘ ∉ R.}.  (3.1)

One can show (see for example Exercise 10.9 on page 320 of [Si2]), that K(R, 2) contains the 2-Selmer group. We first find K(R, 2) and then reduce it to the 2-Selmer group.

3.1 The Method of Brumer and Kramer

For each prime p ∈ S ∪ {∞} we define

K_{p} = ℚ_{p}[T]/(f(T)) = ℚ_{p}(t)

where (f(T)) is the ideal in ℚ_{p}[T] generated by f(T) = T^{3} + AT + B, and t = T + (f(T)). Just as in the classical case of the 2-descent over ℚ we have an embedding

E(ℚ_{p})/2E(ℚ_{p}) → K_{p}^{∗}/K_{p}^{∗}^{2}  (3.2)

with the usual definition of K_{p}^{∗}/K_{p}^{∗}^{2}. Here, for each prime p we have the following diagram

\begin{aligned}0 & ⟶ & E(ℚ)/2E(ℚ) & ⟶^{X−t} & K(R, 2) \\ & & ↓ & & ↓ \\ 0 & ⟶ & E(ℚ_{p})/2E(ℚ_{p}) & ⟶^{X−t} & K_{p}^{∗}/K_{p}^{∗}^{2}. \end{aligned}  (3.3)

We denote the natural map from K(R, 2) to K_{p}^{∗}/K_{p}^{∗}^{2} by σ.

For each prime p ∈ S ∪ {∞} we let U_{p} be the image of E(ℚ_{p})/2E(ℚ_{p}) in K_{p}^{∗}/K_{p}^{∗}^{2} under the mapping (3.2). In [Brum, Kra] Brumer and Kramer showed that the Selmer group is the maximal subgroup of K(R, 2) whose image under the natural map σ is contained in U_{p} for all primes p ∈ S ∪ {∞}. Ostensibly, to use this method for the computation of the 2-Selmer group, one must first calculate E(ℚ_{p})/2E(ℚ_{p}) for each prime p ∈ S ∪ {∞}. However, we have found this mildly troublesome, and indeed what is really needed is to compute the images U_{p}. We note that the size of K_{p}^{∗}/K_{p}^{∗}^{2} is bounded for all primes p and all (cubic) polynomials f.

To determine U_{p} it is sufficient to take each element of K_{p}^{∗}/K_{p}^{∗}^{2} which has norm in ℚ_{p}^{∗}^{2} and determine whether or not it is in U_{p}. As in the classical case (see page 65) this leads to a homogeneous space as the intersection of 2 quadric surfaces, and here all that is required is to check their solubility over the local field ℚ_{p}. This can be done by the polynomial time algorithm given in Chapters 5 and 6 ^{1}; these algorithms are non-constructive (they do not give points on the homogeneous space but simply determine whether or not they have a point defined over ℚ_{p}, which is all that is needed here).

1It is to be noted here that any homogeneous spaces (over ℚ_{p}) arising here will be the intersection of 2 quadric surfaces, one of which is singular. Hence if p ≠ 2, ∞ then we can use our polynomial time algorithm in Section 5.3

3.2 Finding K(R, 2)

It will be seen later that determining K(R, 2) is useful for our higher descents which we describe in the next chapter. But there K will not necessarily be a cubic field. We should also point out that the above method of Brumer and Kramer has been applied to computing the Mordell-Weil group of Jacobians of hyperelliptic curves of higher genus by Schaefer [Scha], where again the field K is not necessarily cubic. Hence for the purpose of this section we will assume that K is a general number field with absolute discriminant D, and R is a finite set of valuations on K which includes all those at infinity. It should be noted however, that some of the complexity analysis is valid only for the case where |R| = O(log(D)). We shall assume that we are given an integral basis for the maximal order of K and generators for the unit and class groups. To determine this information will take time O(L_{D}(0.5, c_{2})) as computing a basis for the maximal order can be done in time O(L_{D}(1/3, c_{3})), [Bu, Len], and computing the unit and class groups can be done in time O(L_{D}(0.5, c_{2})), [Buch] assuming GRH and a certain conjecture about the number of reduced smooth ideals of a number field. The class group Cl_{K} is then presented as a set of ideals 𝔠_{1}, …, 𝔠_{g} and integers s_{i} with s_{i−1}|s_{i}, such that, if for an ideal 𝔞 we denote by \overline{𝔞} the image of 𝔞 in the class group, we have

Cl_{K} ≅ ⟨\overline{𝔠_{1}}⟩ × … × ⟨\overline{𝔠_{g}}⟩ ,

with ⟨\overline{𝔠_{i}}⟩ ≅ ℤ/s_{i}ℤ. We denote by η_{1}, …, η_{r} a set of r fundamental units for K. Given an ideal of K then using the basis of the relation lattice which was used in computing the class group one can determine whether the ideal is principal and if so compute a generator in time O(L_{D}(0.5, c_{4})) (see [Buch]). We note that in general one cannot write down the elements we require in polynomial time when we express them in standard representation so throughout we assume all elements are in a compact representation, see [Thiel]. We now give the algorithm to compute K(R, 2) as a product of cyclic groups of order 2. Let the finite prime ideals in R be denoted ℘_{1}, …, ℘_{t}.

Suppose α ∈ K(R, 2). Then by the definition (3.1) above (α) = 𝔞𝔟^{2} where 𝔞|(2D). Let F be the group of fractional ideals. We have a homomorphism

ϕ : K(R, 2) → F/F^{2}

given by α → (α)F^{2}. Clearly the image of ϕ is contained in the group

H_{1} = ⟨℘_{1}F^{2}⟩ × … × ⟨℘_{n}F^{2}⟩ .

Let

H_{2} = {𝔡F^{2} ∈ H_{1} : 𝔡F^{2} = (γ)F^{2} for some γ ∈ K^{∗}} .

Clearly Im(ϕ) = H_{2}. We want to show how to calculate H_{2} and then how to refine it to obtain K(R, 2) as a product of cyclic groups of order 2. We assume that for each ℘_{i} that we can write

\overline{℘_{j}} = ∏_{i=1}^{g} \overline{𝔠_{i}}^{b_{ij}};

this can be done by the method in [Buch] in time O(L_{D}(0.5, c_{4})). Suppose 𝔡F^{2} ∈ H_{2}, then we can take 𝔡 = ∏_{j=1}^{n} ℘_{j}^{a_{j}}. Hence

\overline{𝔡} = ∏_{i=1}^{g} \overline{𝔠_{i}}^{e_{i}},

where e_{i} = ∑_{j=1}^{n} a_{j}b_{ij}. Suppose that s_{1}, …, s_{k} are odd, and s_{k+1}, …, s_{g} are even. Then 𝔡F^{2} lies in H_{2} if and only if ∑_{j=1}^{n} a_{j}b_{ij} ≡ 0 (mod 2) for i = k + 1, …, g.

By a computing an 𝔽_{2}-basis for the subspace of the vectors (a_{1}, …, a_{n}) in 𝔽_{2}^{n} which satisfy the congruences above, we get a basis for H_{2}. Further we may replace the representative of each element of this basis by one which is a principal ideal as follows: Suppose 𝔡 is such a representative which we want to replace by a principal ideal. By construction of this basis we know 𝔡 as a product of the ℘_{i} and hence we can write \overline{𝔡} = ∏ \overline{𝔠_{i}}^{u_{i}} where u_{k+1}, …, u_{g} are even. Now since s_{1}, …, s_{k} are odd we can find t_{1}, …, t_{k} such that u_{i} + 2t_{i} ≡ 0 (mod s_{i}) for i = 1, …, k. We take t_{j} = −u_{j}/2 for j = k + 1, …, g. Hence we have that

𝔡 ∏_{i=1}^{g} 𝔠_{i}^{2t_{i}} = (α)

for some α ∈ K^{∗}. This α can be computed in time O(L_{D}(0.5, c_{4})) as we stated above. Hence we can write

H_{2} = ⟨(α_{1})F^{2}⟩ × … × ⟨(α_{n})F^{2}⟩

for some α_{1}, …, α_{n} ∈ K^{∗}.

Lemma 3.2.1 Let 𝔟_{1}, …, 𝔟_{l} be an 𝔽_{2}-basis for Cl[2]. Write 𝔟_{i}^{2} = (β_{i}). Then

α_{1}K^{∗}^{2}, …, α_{n}K^{∗}^{2}, β_{1}K^{∗}^{2}, …, β_{l}K^{∗}^{2}, η_{1}K^{∗}^{2}, …, η_{r}K^{∗}^{2}, η_{r+1}K^{∗}^{2} (3.4)

is a basis for K(R, 2), where η_{1}, …, η_{r} is a system of fundamental units for K, and we take η_{r+1} a generator for the roots of unity.

Proof. It is clear that the elements of the list above generate K(R, 2). What remains is to show that these are independent. Suppose that

∏_{i=1}^{n} α_{i}^{a_{i}} ∏_{i=1}^{l} β_{i}^{b_{i}} ∏_{i=1}^{r+1} η_{i}^{c_{i}} ∈ K^{∗}^{2}

where the a’s, b’s, c’s, are in {0, 1}. Then ∏((α_{i})F^{2})^{a_{i}} = (1)F^{2} which implies that a_{i} = 0 for i = 1, …, n. Hence we can now assume that

∏_{i=1}^{l} β_{i}^{b_{i}} ∏_{i=1}^{r+1} η_{i}^{c_{i}} ∈ K^{∗}^{2}.

Hence ∏ 𝔟_{i}^{2b_{i}} = (ϵ)^{2} where ϵ ∈ K^{∗}, i.e. ∏ 𝔟_{i}^{b_{i}} = (ϵ), so b_{i} = 0. The result now follows. □

Lemma 3.2.2 The complexity of finding K(R, 2) as a product of cyclic groups of order 2 is given by O(L_{D}(0.5, c_{1})).

Proof. We note that the number of ideals ℘_{i} dividing (2D) is O([K : ℚ] log D). The number of elements in a basis of Cl[2] is O(log(h_{K})) = O(log(D)). Hence the number of ideals that we need to check to be principal is a polynomial function in log D. As we stated earlier for each ideal this can be done in time O(L_{D}(0.5, c_{4})) by an algorithm which will also produce a generator of any principal ideal found. The desired complexity then follows. □

3.3 Computing The 2-Selmer Group

We return now to the special case where K is a cubic field arising from our elliptic curve E. For each element of K(R, 2) we eliminate those elements which do not lie in the image of σ in diagram (3.3) for all p ∈ S ∪ {∞}. Suppose we know that the Selmer group is a subgroup of some group

⟨k_{1}⟩ × … × ⟨k_{v}⟩ ≤ K(R, 2)

where the ⟨k_{i}⟩ are cyclic groups of order 2 (it is understood that the k_{i} are in fact k_{i}K^{∗}^{2}). Consider any prime p ∈ S ∪{∞}; recall that we denoted the image of the map

E(ℚ_{p})/2E(ℚ_{p}) → K_{p}^{∗}/K_{p}^{∗}^{2}  (3.5)

by U_{p}. To determine the Selmer group we want to determine the maximal subgroup of ⟨k_{1}⟩ × … × ⟨k_{v}⟩ whose image under σ is in U_{p} for all primes p; obviously we need only consider those primes which divide 2D and the infinite prime. This idea we find explained in [Brum, Kra] or [Scha] as we have already stated.

Lemma 3.3.1 The image of an element of K(R, 2) under σ can be checked to lie in U_{p} in polynomial time.

Proof. Suppose X^{3} + AX + B has three roots in ℚ_{p} and p > 2; then

U_{p} ≤ ℚ_{p}^{∗}/ℚ_{p}^{∗}^{2} × ℚ_{p}^{∗}/ℚ_{p}^{∗}^{2} × ℚ_{p}^{∗}/ℚ_{p}^{∗}^{2}.

There are at most four elements of ℚ_{p}^{∗}/ℚ_{p}^{∗}^{2} and |U_{p}| has order O(1).

We therefore have O(1) tests to perform as to whether an element of ℚ_{p} is a p-adic square. This can certainly be done in polynomial time. The other cases are similar. □

For i = 1, …, v, we define the subgroup S_{i} of ⟨k_{1}⟩ × … × ⟨k_{i}⟩ to be the maximal subgroup of ⟨k_{1}⟩ × … × ⟨k_{i}⟩ whose image under σ is in U_{p}. We let

b_{1}, …, b_{j_{i}} ∈ ⟨k_{1}⟩ × … × ⟨k_{i}⟩

be such that

H_{i} := ⟨b_{1}S_{i}⟩ × … × ⟨b_{j_{i}}S_{i}⟩ = (⟨k_{1}⟩ × … × ⟨k_{i}⟩) /S_{i}.

Notice that |H_{i}| = O(1). This is because |E(ℚ_{p})/2E(ℚ_{p})| = O(1). Hence if there were too many b_{j} then there would exist a relation of the form

σ(b_{1}^{s_{1}}) … σ(b_{j_{i}}^{s_{j_{i}}}) = identity of K_{p}^{∗}/K_{p}^{∗}^{2}

where the s_{j} ∈ {0, 1} and not all s_{j} = 0. But certainly the identity is in the image of the map (3.2). Hence b_{1}^{s_{1}} … b_{j_{i}}^{s_{j_{i}}} is in S_{i} giving a contradiction. Hence as we claimed |H_{i}| = O(1).

Now we determine the S_{i} and H_{i} recursively. To determine S_{1} simply check if the image of k_{1} is in U_{p}. If it is then S_{1} ≅ ⟨k_{1}⟩ and H_{1} ≅ {S_{1}}. If it is not then S_{1} ≅ {identity}, and H_{1} ≅ ⟨k_{1}S_{1}⟩.

Suppose we have determined S_{i} and the H_{i}. To determine S_{i+1} and H_{i+1} we check if

σ(b_{1}^{s_{1}}) … σ(b_{j_{i}}^{s_{j_{i}}})σ(k_{i+1})  (3.6)

is in U_{p} for any s_{j} = 0 or 1. If none of these are in U_{p} then S_{i+1} = S_{i}, and

H_{i+1} = ⟨b_{1}S_{i+1}⟩ × … × ⟨b_{j_{i}}S_{i+1}⟩ × ⟨k_{i+1}S_{i+1}⟩ .

If, on the other hand, the expression (3.6) is in U_{p} for some choice of s_{j} = 0 or 1 (there can be at most one such choice), then

S_{i+1} ≅ S_{i} × ⟨b_{1}^{s_{1}} … b_{j_{i}}^{s_{j_{i}}} k_{i+1}⟩

and

H_{i+1} ≅ ⟨b_{1}S_{i+1}⟩ × … × ⟨b_{j_{i}}S_{i+1}⟩ .

The number of choices of b_{j} that we have is O(1) as |H_{i}| = O(1). Hence we can determine S_{k} as a product of cyclic groups all of order 2. The time to do this is then polynomial in log D via Lemma 3.3.1

Now to determine the Selmer group, we start with K(R, 2) expressed as a product of cyclic groups. For our primes p_{1}, …, p_{r} dividing 2D we start with p_{1} and we determine as above the maximal subgroup V_{p_{1}} ≤ K(R, 2) whose image under σ = σ_{p_{1}} which is contained in U_{p_{1}}. Our construction will give us V_{p_{1}} as a product of cyclic groups of order 2. This will certainly contain the Selmer group. We now discard K(R, 2) and find the maximal subgroup of V_{p_{1}} whose image under σ_{p_{2}} is contained in U_{p_{2}}. Doing this recursively we arrive at the Selmer group as soon as we have carried out the above construction for all of p_{1}, …, p_{r} and also the infinite prime.

If we have K(R, 2) as a product of cyclic groups of order 2 then we will find the Selmer group in polynomial time. Hence the total complexity is given by the complexity of finding K(R, 2).

Descents on the

Intersections of 2 Quadrics

4.1 Introduction

Let us briefly review the progress made so far with the problem of computing the Mordell-Weil group of an elliptic curve. We have shown, jointly with N. Smart, how the 2-Selmer group may be computed efficiently (at least in theory) for an elliptic curve defined over ℚ. We have also given practical methods for performing the infinite descent. We want to show how to determine the coset representatives for E(ℚ)/2E(ℚ) once we have computed the Selmer group. Equivalently, we want to determine which of the homogeneous spaces representing the 2-Selmer group has a rational point on it. This is an unsolved problem, and one which we have failed to solve.

Hopefully, a computer search will find rational points on all of the homogeneous spaces representing the 2-Selmer group and this would give us the coset representatives for E(ℚ)/2E(ℚ). Occasionally we will not be able to find rational points on some of the homogeneous spaces representing the 2-Selmer group. Here we have two possibilities:

1. The homogeneous space, though everywhere locally soluble, has no global points. Unfortunately, there is no local-to-global principle for curves of genus 1 (see, say [Ca1] pages 85-88).

2. The homogeneous space, has global (i.e. rational) points but these are too large to be found by a naive computer search.

Here, in order to try to find out if the homogeneous space has points on it we will use what is referred to as ‘higher descents’. It is appropriate here to explain what is meant by a descent (Compare this to [Ca4] p205): Given a homogeneous space D we construct other curves D_{1}, …, D_{n} and rational maps (which are also defined over ℚ) ϕ_{i} : D_{i} → D (of degree > 1) such that for all P ∈ D(ℚ) there would exist Q ∈ D_{i}(ℚ) for some i such that ϕ_{i}(Q) = P. We will sometimes refer to D as the ‘parent’, and the D_{i} as the ‘descendants’. ^{1}

Of course, if we discover that none of the D_{i} is everywhere locally soluble, then D cannot have a rational point and we would be finished. If a search reveals a rational point Q on one of the D_{i} then ϕ_{i}(Q) is a rational point on D and we are finished.

Our hope is that the method of constructing the curves D_{i} and the maps ϕ_{i} will be recursive. Since deg(ϕ_{i}) > 1, we expect that if there is a rational point P on D(ℚ) and if P = ϕ_{i}(Q), Q ∈ D_{i}(ℚ), then the (logarithmic) height of Q will be smaller than that of P and hence it will be easier to find a rational point on D_{i}.

Repeating this process, and rejecting at each stage the D_{i} which are not everywhere locally soluble, we hope to finally arrive at some curve D_{i} which has a small rational point or prove that D does not have a rational point.

The basic idea behind such methods is known and has been used to treat particular families of elliptic curves (see for example [Brem, Ca], [Brem], [Str, Top]). However, our exposition will be in a more general setting, allowing the methods to be better understood and applied. Moreover, we will give new faster algorithms for testing the curves D_{i} for local solubility.

1In the descents which we will study in this chapter, our descendant curves D_{i}, will always be intersections of two quadric surfaces in ℙ^{3}. Our D will always be a curve genus 1, and it follows from Theorem B.0.3 that the intersection of the 2 quadric surfaces is in fact transverse, and that D_{i} is a curve of genus 1.

It should be clear that there is no guarantee for such a method to succeed in deciding whether a particular homogeneous space D has a rational point or not (see [Brem, Bue] and our Chapter (4.8)). But such methods are often effective, and at the very least we hope to have minimized the possibility of failure.

In theory, it happens to be no extra trouble for us to consider these descents over a general number field K, and we will do this. However, we will always assume that we can determine the class group and fundamental units of the number fields we use.

4.2 The Homogeneous Spaces for the 2-Descent

Suppose E is an elliptic curve defined over the number field K and given by the equation

y^{2} = f(x)  (4.1)

where f(x) = x^{3} + Ax + B is a polynomial over K with no repeated roots. Let L be the algebra

L = K[T]/(f(T)),

and let Θ be the image of T under the natural homomorphism

K[T] → L.

We recall that we have an group homomorphism (see [Ca1] page 66 or [Ca6] page 31)

α : E(K) → L^{∗}/L^{∗}^{2}  (4.2)

given explicitly by

P = (x, y) → (x − Θ)L^{∗}^{2}.  (4.3)

This homomorphism has as its kernel 2E(K). Moreover, the image of this homomorphism is contained in the 2-Selmer group which we regard as a (finite) subgroup of L^{∗}/L^{∗}^{2}. We assume that we have already determined the 2-Selmer group which we will denote by S. For each element of S we would like to know if this element can be expressed as α(P) for some P ∈ E(K). If s_{1}, …, s_{n} are the elements of S which can be so expressed, and if say s_{i}L^{∗}^{2} = α(P_{i}) where the P_{i} ∈ E(K) then P_{1}, …, P_{n} is a complete set of coset representatives for E(K)/2E(K).

Hence we would like to know, for each s ∈ S if it is possible for us to have

(x − Θ) = sϵ^{2}  (4.4)

for some x ∈ K and ϵ ∈ L, and if so determine the x (and ϵ) explicitly. Now any such ϵ can be written in the form

ϵ = u_{1} + u_{2}Θ + u_{3}Θ^{2}

where u_{1}, u_{2}, u_{3} ∈ K. Substituting in equation (4.4) and comparing coefficients of 1, Θ, Θ^{2} we get

\begin{matrix}Q_{1}(u_{1}, u_{2}, u_{3}) = x \\ Q_{2}(u_{1}, u_{2}, u_{3}) = −1 \\ Q_{3}(u_{1}, u_{2}, u_{3}) = 0. \end{matrix} \}  (4.5)

Here we would solve our problem for the particular s if and only if we can find a simultaneous solution to the last two equations above. Thus our ‘homogeneous space’ is an intersection of 2 quadric surfaces in four (homogeneous) variables:

\begin{matrix}Q_{2}(u_{1}, u_{2}, u_{3}) = −u_{4}^{2} \\ Q_{3}(u_{1}, u_{2}, u_{3}) = 0. \end{matrix} \}  (4.6)

This will be a curve of genus 1 and the intersection of the 2 quadric surfaces in (4.6) is a transverse intersection by Theorem B.0.3. It is on this curve that we look for a solution, and it is this curve which is the starting point for our higher descents. We note for future reference that that the second of these quadrics is singular.

4.3 ‘Coprimality’ in number fields

When dealing with homogeneous equations over the rationals (in say n variables), one often make the simplifying assumption that all the solutions are given by integer n-tuples which are not all divisible by a common prime factor. Of course, this useful device does not extend without modification to homogeneous equations defined over number fields, due to the failure of unique factorization over number fields in general. Our purpose here is to show how this method may be modified as follows: instead of insisting that there be no common prime ideal factors at all, we demand that there are no common prime ideal factors from outside a certain finite pre-determined set.

Theorem 4.3.1 Let 𝔞_{1}, …, 𝔞_{k} be a set of ideals whose image in the ideal class group of K generates the ideal class group, and let S = {℘_{1}, …, ℘_{m}} be the set of prime ideals which divide any of the 𝔞_{i}. If (a_{1}, …, a_{n}) ∈ K^{n}\0 then there exists u ∈ K^{∗} such that (ua_{1}, …, ua_{n}) ∈ O_{K}^{n}\0 and if ℘ is a prime ideal dividing all the ua_{i} then ℘ ∈ S.

Proof. It is obvious that the images of the ℘_{i} in the ideal class group also generate the ideal class group. By scaling, we may assume that (a_{1}, …, a_{n}) ∈ O_{K}^{n}\0. Suppose we are given ℘, a prime ideal which divides all of the a_{i} but is not contained in S. Let

r = min_{i=1,...,n} {ord_{℘}(a_{i})} ≥ 1.

Then there exists non-negative integers α_{1}, …, α_{m} such that

(∏_{j=1}^{m} ℘_{j}^{α_{j}} ) ℘^{r} = (b)

for some b ∈ O_{K}. Also, clearly, there exist β_{1}, …, β_{m} such that β_{j} ≥ α_{j} for j = 1, …, m and

∏_{j=1}^{m} ℘_{j}^{β_{j}} = (c).

Hence the n-tuple (\frac{a_{1}c}{b}, …, \frac{a_{n}c}{b}) is proportional to (a_{1}, …, a_{n}) and is not divisible by ℘. Furthermore, if ℘′ is a prime ideal not in S ∪ {℘} then clearly

min_{i=1,...,n} \{ord_{℘′}(\frac{a_{i}c}{b})\} = min_{i=1,...,n} \{ord_{℘′}(a_{i})\} .

Proceeding recursively in this fashion, it follows that there is a vector in O_{K}^{n} which is proportional to our original (a_{1}, …, a_{n}) and which is not divisible by any common prime ideal which is not in S. □

It is clear that our set S depends on our choice of generators for the ideal class group and so is not unique. However, we will still find it convenient to think of it as fixed at the outset and will denote it by S_{K}. If (a_{1}, …, a_{n}) ∈ O_{K}^{n} we will say that a_{1}, …, a_{n} are coprime outside S_{K} if no prime ideal ℘ in S_{K} divides all of the a_{i}.

4.4 Diagonalization

For this section we will assume that A, B are n×n matrices with coefficients in our number field K. We write \overline{K} for the algebraic closure over K. The following is a trivial modification of a standard result for Hermitian matrices.

Lemma 4.4.1 Suppose x_{1}, x_{2} ∈ \overline{K}^{n} which satisfy

(A − λ_{1}B)x_{1} = (A − λ_{2}B)x_{2} = 0

for λ_{1}, λ_{2} ∈ \overline{K}. If λ_{1} ≠ λ_{2} then

x_{1}^{t}Ax_{2} = x_{1}^{t}Bx_{2} = 0.

Proof. Note that Ax_{2} = λ_{2}Bx_{2} and x_{1}^{t}A = λ_{1}x_{1}^{t}B. Hence

λ_{1}x_{1}^{t}Bx_{2} = x_{1}^{t}Ax_{2} = λ_{2}x_{1}^{t}Bx_{2}.

If λ_{1} ≠ λ_{2} then the result follows. □

Theorem 4.4.1 Suppose that A and B are n × n symmetric matrices defined over a number field K such that

F (X, Y) = det(XA − Y B)

has distinct roots over K.

If F (X, Y) factorizes as

F (X, Y) = F_{1}(X, Y) … F_{r}(X, Y)

where F_{1}, …, F_{r} are homogeneous and irreducible over K, then there exists a non-singular matrix P ∈ GL(K, n) such that

P^{t}AP = ( \begin{matrix}A_{1} \\ & . & . & . \\ & & & & A_{r} \end{matrix} ) , P^{t}BP = ( \begin{matrix}B_{1} \\ & . & . & . \\ & & & & B_{r} \end{matrix} )  (4.7)

where A_{i} and B_{i} are symmetric matrices of size deg(F_{i}), and

det(XA_{i} − Y B_{i}) = c_{i}F_{i}(X, Y)

with c_{i} ∈ K satisfying ∏ c_{i} = 1.

Proof. By replacing A by A + ϵB for some ϵ ∈ K, we may assume that det(A) ≠ 0. Suppose λ_{j} is a root of F_{j}(X, 1). Then there exists v_{j} ∈ \overline{K}^{n} such that (A − λ_{j}B)v_{j} = 0. Let v_{j}^{(i)} (i = 1, …, deg(F_{j})) be the conjugates of v_{j}. Using Lemma 5.8.1, page 40 of [Si2] we know that there are w_{j}^{(i)} ∈ K^{n} (i = 1, …, deg(F_{j})) which span the same \overline{K}-linear subspace of \overline{K}^{n} as the v_{j}^{(i)}. Now let P be the matrix with columns

w_{1}^{(1)}, …, w_{1}^{(deg(F_{1}))}, …, w_{r}^{(1)}, …, w_{r}^{(deg(F_{r}))}.

It is easy to see, using Lemma 4.4.1 that P is the matrix required by the Theorem. □

4.5 Parametrization of the Singular Combina-

tions

As is noted before our intersections of pairs of quadric surfaces, will be curves of genus 1, must be a transverse intersections, and the singular combinations of the corresponding pencils will all have rank=3. Hence a singular combination is a curve of genus 0. Now since we would have checked our intersection of 2 quadrics for everywhere local solubility we know that this singular combination is everywhere locally soluble ^{2}. Hence this singular combination must have a global solution and if we were to find one such solution then all others will be given parametrically. It is this parametrization which will enable us to perform our descents in Section 4.6.

Of course, after a non-singular change of variable, we may take our singular combination to be of the form

aX^{2} + bY^{2} + cZ^{2} = 0  (4.8)

where a, b, c ∈ O_{K}\{0}. In [Sieg2] Siegel gives a region for the triple (X, Y, Z) which is guaranteed to contain a solution. We omit giving this because of its complexity. If K = ℚ then we have the following Theorem of Holzer

Theorem 4.5.1 The solvable equation ax^{2}+by^{2}+cz^{2} = 0 taken in its canonical form with a > 0, b > 0, c < 0 has a non-trivial solution with

|x| ≤ |bc|^{\frac{1}{2}} , |y| ≤ |ca|^{\frac{1}{2}} , |z| ≤ |ab|^{\frac{1}{2}} .

Proof. See [Holzer], or [Mord] page 47. □

Once we have one non-trivial solution of the Equation (4.8) we can parametrize all others as is well-known.

Theorem 4.5.2 Suppose x_{0}, y_{0}, z_{0} ∈ K is a non-trivial solution of equation (4.8) then there exist binary quadratic forms q_{1}, q_{2}, q_{3} defined over K such that x, y, z ∈ K is a solution if and only if it is a K-rational multiple of q_{1}(u, v), q_{2}(u, v), q_{3}(u, v) for some u, v ∈ K.

2Here the assumption that the intersection is transverse is critical. For in this case our equations can be taken of the form

q_{1}(x_{1}, x_{2}, x_{3}) = 0, q_{2}(x_{1}, x_{2}, x_{3}) = x_{4}^{2}, and if this has a non-trivial solution over any (say local) field then not all of x_{1}, x_{2}, x_{3} will be zero, and hence q_{1}(x_{1}, x_{2}, x_{3}) = 0 has a non-trivial solution. This of course is not the case for the rational curve

x^{2} + y^{2} + z^{2} = 0, x^{2} + 2y^{2} = zw which has the solution (0, 0, 0, 1), the singular combination x^{2} + y^{2} + z^{2} = 0 has no non-trivial solutions over either of ℝ, or ℚ_{2}.

Proof. See [Mord] page 48 which gives q_{1}, q_{2}, q_{3} explicitly in terms of a, b, c and x_{0}, y_{0}, z_{0}. □ It follows from the above that one can always constructively obtain a parametric solution to any singular combination of an everywhere locally soluble transverse intersection of 2 quadric surfaces in 4 variables.

4.6 Descents

We will explain 3 methods of ‘descent’ on the (transverse) intersection of 2 quadrics

\begin{matrix}x^{t}Ax = 0 \\ x^{t}Bx = 0 \end{matrix} \}  (4.9)

Write F (X, Y) = det(XA−Y B). Each method will require that F splits over K in a certain way. Since we are performing the descents to determine if the homogeneous space (4.9) has rational points, we will assume that (4.9) is everywhere locally soluble.

4.6.1 F has at least 2 roots defined over K

Suppose F has at least 2 roots defined over K. By Theorem (4.4.1) we know that by performing a simultaneous change of variable we can take

A = ( \begin{matrix}\begin{aligned}a_{1} \\ & a_{2} \end{aligned} & 0 \\ 0 & A_{1} \end{matrix} )

and

B = ( \begin{matrix}\begin{aligned}b_{1} \\ & b_{2} \end{aligned} & 0 \\ 0 & B_{1} \end{matrix} ) .

By again taking suitable linear combinations we can assume that in the above a_{1} = 1, a_{2} = 0, b_{1} = 0, b_{2} = 1. Hence our original equations will have become of the form

\begin{matrix}x_{1}^{2} = Q_{1}(x_{3}, x_{4}), \\ x_{2}^{2} = Q_{2}(x_{3}, x_{4}) \end{matrix} \}  (4.10)

where Q_{1}, Q_{2} are quadratic forms with coefficients in K. Since our original pair was everywhere locally soluble, both x_{1}^{2} = Q_{1}(x_{3}, x_{4}), and x_{2}^{2} = Q_{2}(x_{3}, x_{4}) are everywhere locally soluble, and hence have parametric solutions of the form

\begin{matrix}x_{1} : x_{3} : x_{4} = p_{1}(u_{1}, u_{2}) : p_{3}(u_{1}, u_{2}) : p_{4}(u_{1}, u_{4}) \\ x_{2} : x_{3} : x_{4} = q_{2}(v_{1}, v_{2}) : q_{3}(v_{1}, v_{2}) : q_{4}(v_{1}, v_{2}) \end{matrix} \}  (4.11)

where the p_{i} and the q_{i} are binary quadratic forms with coefficients in K.

We construct a set S_{K} of prime ideals as in Section 4.3. Clearly we may assume that the p_{i}, q_{j} have coefficients in O_{K}. Moreover we may assume that the pairs u_{1}, u_{2} and v_{1}, v_{2} are defined over O_{K}, and that each pair is not divisible by any prime ideal not in S_{K}. Now, we will have a solution to the pair (4.10) if we can find α ∈ K^{∗} such that

\begin{matrix}p_{3}(u_{1}, u_{2}) = αq_{3}(v_{1}, v_{2}) \\ p_{4}(u_{1}, u_{2}) = αq_{4}(v_{1}, v_{2}) \end{matrix} \}  (4.12)

has a solution. We note that if ℘ is an ideal such that ord_{℘}(α) > 0 then either ℘ ∈ S_{K} or ℘ divides the resultant of p_{3}, p_{4}, which is necessarily non-zero ^{3}. Similarly if ord_{℘}(α) < 0 then ℘ is either in S_{K} or ℘ divides the resultant of q_{3}, q_{4}. Now dropping our requirement that v_{1}, v_{2} are in O_{K}, we see that α matters only up to squares in K^{∗}. Hence we may, by the method used for determining K(R, 2) in Chapter 3, determine all possible α modulo K^{∗}^{2}. Doing this we will have finitely many curves (4.12) defined over K. The process of deriving these curves from our original curve (4.9) is a ‘descent’ according to the paradigm of our introduction to this chapter (page 64). The explicit maps from the ‘descendants’ (4.12) to the ‘parent’ (4.10) are given explicitly by (4.11).

3Suppose that the resultant of p_{3}, p_{4} is 0. Then p_{3}, p_{4} (when regarded as homogeneous polynomials) have a common factor. Since p_{1}, p_{3}, p_{4} satisfies p_{1}^{2} = Q_{1}(p_{3}, p_{4}), this common factor must divide p_{1}. If this common factor is quadratic, then there is precisely one solution to x_{1}^{2} = Q_{1}(x_{3}, x_{4}) in ℙ^{2}, and this is impossible. Hence p_{i}(u_{1}, u_{2}) = l(u_{1}, u_{2})m_{i}(u_{1}, u_{2}), where

4.6.2 F is the Product of 2 Irreducible Quadratic Factors

Suppose F (X, Y) = det(XA−Y B) is the product of 2 irreducible factors defined over K. Then, by Theorem 4.4.1, after a non-singular change of variable defined over K we can assume

A = ( \begin{matrix}A_{1} & 0 \\ 0 & A_{2} \end{matrix} )

and

B = ( \begin{matrix}B_{1} & 0 \\ 0 & B_{2} \end{matrix} )

where A_{1}, A_{2}, B_{1}, B_{2} are 2 × 2 matrices over K and

det(XA − Y B) = det(XA_{1} − Y B_{1}) det(XA_{2} − Y B_{2}).

Hence det(XA_{1} − Y B_{1}) and det(XA_{2} − Y B_{2}) are irreducible. Hence we may re-write our original equations 4.9 in the form

\begin{matrix}y^{t}A_{1}y = −z^{t}A_{2}z \\ y^{t}B_{1}y = −z^{t}B_{2}z \end{matrix} \}  (4.13)

where

y = ( \begin{matrix}y_{1} \\ y_{2} \end{matrix} ) , z = ( \begin{matrix}z_{1} \\ z_{2} \end{matrix} ) .

l, m_{1}, m_{3}, m_{4} are linear, and m_{3}, m_{4} are linearly independent. By a non-singular change of variable, we can assume that m_{2}(u_{1}, u_{2}) = u_{1}, m_{3}(u_{1}, u_{2}) = u_{2}. Hence m_{1}(u_{1}, u_{2})^{2} = Q_{1}(u_{1}, u_{2}). So Q_{1} is a square polynomial, and it follows that x_{1}^{2} − Q_{1}(x_{3}, x_{4}) has rank=2, contradicting our assumption that (4.9) is a transverse intersection of quadric surfaces.

Let λ be a root of det(A_{2} − Y B_{2}), so λ is defined over a quadratic extension of K. Then A_{2} − λB_{2} has rank=1. So there exists δ ∈ K(λ) such that

y^{t}(A_{1} − λB_{1})y = δζ^{2}.  (4.14)

Since our original pair of equations (4.9) was soluble over all localizations of K, it follows that this equation regarded as curve of genus 0 over K(λ) must have solutions over all localizations of K(λ). By the results of Section 4.5 there exists binary quadratic forms q_{1}, q_{2}, q_{3} defined over K(λ) such that the triple y_{1}, y_{2}, ζ is a solution to (4.14) over K(λ) if and only if

y_{1} : y_{2} : ζ = q_{1}(ψ_{1}, ψ_{2}) : q_{2}(ψ_{1}, ψ_{2}) : q_{3}(ψ_{1}, ψ_{2}).  (4.15)

By comparing the coefficients of 1, λ in (4.14), we see that there exists a solution to (4.13) defined over K if and only if there exists y_{1}, y_{2} ∈ K and α ∈ K(λ)^{∗}, ψ_{1}, ψ_{2} ∈ K(λ) (not both zero) such that

\begin{matrix}y_{1} = αq_{1}(ψ_{1}, ψ_{2}) \\ y_{2} = αq_{2}(ψ_{1}, ψ_{2}). \end{matrix}  (4.16)

Suppose for the moment that we have a fixed α. Now ψ_{1} = β_{1} + λβ_{2}, and ψ_{2} = β_{3} + λβ_{4} for some β_{1}, …, β_{4} ∈ K, and not all zero. Then expanding αq_{1}(ψ_{1}, ψ_{2}) and αq_{2}(ψ_{1}, ψ_{2}) and comparing the coefficients of λ in (4.16) we get a pair of homogeneous quadratic equations in 4 variables (defined over K) which we want to solve:

\begin{matrix}Q_{1}(β_{1}, …, β_{4}) = 0 \\ Q_{2}(β_{1}, …, β_{4}) = 0. \end{matrix}

Now this pair depends on the choice of α and we need to show that α can be taken from a finite set whose elements can be effectively enumerated. This is what we shall do. We note that we may assume the following

1. By scaling we can assume that A_{1}, A_{2}, B_{1}, B_{2} all have entries in O_{K}.

2. If y_{1}, y_{2}, z_{1}, z_{2} is a solution to (4.13) then we may assume that they are in O_{K} and that the 4-tuple (y_{1}, y_{2}, z_{1}, z_{2}) is not divisible by any prime ideal not in S_{K}.

3. q_{1}, q_{2} are defined over O_{K(λ)}, and ψ_{1}, ψ_{2} are in O_{K(λ)} and are not both divisible by any prime ideal not in S_{K(λ)}.

Now if ℘ is a prime ideal of K(λ) such that ord_{℘}(α) ≤ −1 then it is easy to see from (4.16) and the above assumptions that either ℘ divides the resultant of q_{1}, q_{2} or ℘ is in S_{K(λ)}. Moreover if ℘ is a prime ideal of K(λ) such that ord_{℘}(α) ≥ 1 then ℘ will divide both y_{1}, y_{2} and hence ℘ will divide one of the ideals in {℘′O_{K(λ)} : ℘′ ∈ S_{K}}. Hence it is clear that ord_{℘}(α) = 0 for all prime ideal ℘ not in some finite set, and that this set can be determined. We now drop our requirement that ψ_{1}, ψ_{2} are in O_{K(λ)}, and so we see from (4.16) that α matters only up to squares in K(λ)^{∗}. By the methods of Chapter 3 we may determine all possible α modulo K(λ)^{∗}^{2}. This shows that the α may be taken from a finite set which can be enumerated.

4.6.3 F has exactly one root defined over K

Suppose F (X, Y) = det(XA − Y B) has exactly one rational root. By a nonsingular change of coordinates (defined over K) and then taking appropriate linear combinations, we may assume that

A = ( A_{1}  0_{0  0} )

B = ( B_{1}  0_{0  1} ) ,

where A_{1}, B_{1} are 3 × 3 matrices over K and det(XA_{1} − Y B_{1}) is irreducible. Hence we may rewrite our original equations (4.9) in the form

\begin{matrix}z^{t}A_{1}z & = & 0 \\ z^{t}B_{1}z & = & y^{2} \end{matrix} \}  (4.17)

where z = ( \begin{matrix}z_{1} \\ z_{2} \\ z_{3} \end{matrix} ). As usual we parametrize the solutions to z^{t}A_{1}z = 0 by

z_{1} : z_{2} : z_{3} = q_{1}(X_{1}, X_{2}) : q_{2}(X_{1}, X_{2}) : q_{3}(X_{1}, X_{2}),  (4.18)

Suppose that z_{i} = αq_{i}(X_{1}, X_{2}) for some α ∈ K^{∗}. Substituting this into z^{t}B_{1}z = y^{2} we see that

G(X_{1}, X_{2}) = Y^{2}  (4.19)

where Y = α^{−1}y and G is a binary quartic form with coefficients in K. It is easy to see that (4.17) has a solution defined over K if and only if (4.19) has a solution defined over K. Hence if G has a root defined over K, (4.17) has a solution defined over K.

Lemma 4.6.1 IF G has no roots defined over K then it is irreducible (i.e. it is not a product of 2 irreducible quadratic factors).

Proof. Suppose G is a product of two irreducible quadratic factors. Let L′ be the splitting field of G. Let λ be a root of the irreducible cubic polynomial det(B_{1} − XA_{1}). Now [K(λ) : K] = 3 and [L′ : L] = 2 or 4, and so λ ∉ L′.

Now z^{t}(B_{1} − λA_{1})z has rank = 2 and so

z^{t}(B_{1} − λA_{1})z = βm(z_{1}, z_{2}, z_{3})^{2} + γn(z_{1}, z_{2}, z_{3})^{2}

where β, γ ∈ K(λ)^{∗} and m, n are linear forms with coefficients in K(λ). Let L′′ = L′(\sqrt{−β/γ}). Clearly λ ∉ L′′, since again [L′′ : K] is a power of 2.

Then

z^{t}(B_{1} − λA_{1})z = M(z_{1}, z_{2}, z_{3})N(z_{1}, z_{2}, z_{3})  (4.20)

where M, N are linear forms with coefficients in L′′(λ). But if we let z_{i} = q_{i}(X_{1}, X_{2}) then z^{t}B_{1}z = G(X_{1}, X_{2}) and z^{t}A_{1}z = 0. Hence

G(X_{1}, X_{2}) = M(q_{1}, q_{2}, q_{3})N(q_{1}, q_{2}, q_{3}),

where M(q_{1}, q_{2}, q_{3}) and N(q_{1}, q_{2}, q_{3}) will be quadratic factors of G(X_{1}, X_{2}). But the roots of G are contained in L′ and hence in L′′. So there is some δ ∈ L′′(λ)\ {0} such that δM(q_{1}, q_{2}, q_{3}) and δ^{−1}N(q_{1}, q_{2}, q_{3}) are in L′′[X_{1}, X_{2}]. Write

δM(z_{1}, z_{2}, z_{3}) = M_{1}(z_{1}, z_{2}, z_{3}) + λM_{2}(z_{1}, z_{2}, z_{3}) + λ^{2}M_{3}(z_{1}, z_{2}, z_{3})

where M_{1}, M_{2}, M_{3} are linear forms with coefficients in L′′. Hence M_{2}(q_{1}, q_{2}, q_{3}) is (identically) zero, and so (since q_{1} : q_{2} : q_{3} is a parametrization of the zeros of z^{t}A_{1}z,) the (projective) variety M_{2}(z_{1}, z_{2}, z_{3}) = 0 contains the locus of zeros of the non-singular conic z^{t}A_{1}z = 0. It follows that M_{2}(z_{1}, z_{2}, z_{3}) is (identically) zero. Similarly M_{3} = 0 and hence δM(z_{1}, z_{2}, z_{3}) has coefficients in L′′. This is also true for δ^{−1}N(z_{1}, z_{2}, z_{3}) by the same argument. Hence by (4.20) it follows the coefficients of z^{t}(B_{1} − λA_{1})z are in L′′, which contradicts λ ∉ L′′. This completes the proof ^{4}. □ We have already stated that if G has a root in K then (4.19) and hence (4.17) has a point defined over K. Hence we will assume that G has no roots over K, and by the above Lemma it will follow that G is irreducible. We now return to the descents. Rewrite the equation (4.19) in the form

aY^{2} = F (X_{1}, X_{2})  (4.21)

where a ∈ O_{K} and F is irreducible monic of degree 4 with coefficients in O_{K} ^{5}. Let Θ be a root of F (X_{1}, 1) and let L = K(Θ). It is clear that if (X_{1}, X_{2}, Y) is a solution to (4.21) then we can assume that X_{1}, X_{2} are coprime outside a certain predetermined set of prime ideals S_{K}.

Lemma 4.6.2 If (X_{1}, X_{2}, Y) is a solution to the equation (4.21) and X_{1}, X_{2} are coprime outside S_{K}, then we can write

(X_{1} − ΘX_{2})O_{L} = 𝔞𝔟^{2}  (4.22)

where 𝔞, 𝔟 are ideals of L, and 1. 𝔞 is square-free,

4In essence we have shown that det(B_{1} − XA_{1}) is the resolvent cubic of G.

5Clearly by multiplying the equation (4.19) by a suitable element in O_{K}^{2} we can assume that G has coefficients in O_{K}. Now if a is the leading coefficient of G(X_{1}, X_{2}), then we simply multiply (4.19) by a^{3}, replace Y by a^{−2}Y, and X_{1} by a^{−1}X_{1}.

2. Norm_{L/K}(𝔞) ∈ aK^{∗}^{2},

3. If ℘ is a prime ideal of L and ℘|𝔞 then either

(a) ℘|a, or

(b) ℘|Δ(F), where Δ(F) is the discriminant of F, or (c) ℘|𝔮O_{L} where 𝔮 ∈ S_{K}.

Proof. It is clear that we can write (X_{1} − ΘX_{2})O_{L} in the form (4.22), where 𝔞 satisfies conditions 1 and 2 of the Lemma. Suppose ℘ is a prime ideal of L, such that ℘|𝔞, and ℘ does not divide a, Δ(F). Let L′ be the splitting field of F over K, so that L′ ⊇ L ⊇ K. Since ℘ does not divide Δ(F) we see that ℘ does not ramify over L′. Hence if 𝔮|℘O_{L′}, where 𝔮 is a prime ideal of L′, then

ord_{𝔮}(X_{1} − ΘX_{2})O_{L′} = ord_{℘}(X_{1} − ΘX_{2})O_{L}

which is odd. But

ord_{𝔮} ∏_{i=1}^{4}(X_{1} − Θ_{i}X_{2}) = ord_{𝔮}F (X_{1}, X_{2}) = ord_{𝔮}aY^{2}

is even, since 𝔮 does not divide a. So 𝔮|(X_{1} − Θ′X_{2})O′_{L} where Θ′ is a root of F (X_{1}, 1) which does not equal Θ. Hence 𝔮|(Θ − Θ′)X_{1} and 𝔮|(Θ − Θ′)X_{2}. But 𝔮 does not divide (Θ − Θ′) since otherwise 𝔮|Δ(F) which would imply ℘|Δ(F). Hence 𝔮|X_{1}, X_{2}. Since this is true for all ideals 𝔮 of L′ dividing ℘O_{L′}, it follows that ℘|X_{1}, X_{2}. Hence the conclusion follows. □ Suppose that (X_{1}, X_{2}, Y) is a solution to (4.21), and X_{1}, X_{2} are coprime outside S_{K}. We will write

X_{1} − ΘX_{2} = ϵγ^{2}  (4.23)

where ϵ, γ ∈ L^{∗}. As usual, our ϵ matters only up to squares in L^{∗}. From the above Lemma, we see that our ϵ is supported, modulo square ideals, by the (finitely many) prime ideals specified in condition 3 of the Lemma. Hence, by the method in Chapter 3, we can list a complete set of representatives of L^{∗} modulo L^{∗}^{2} which are supported by these prime ideals. Of these, we keep only those whose Norm is in aK^{∗}^{2}; these will be our required ϵs. For any fixed ϵ, if we write γ = ∑_{i=1}^{4} v_{i}Θ^{(i−1)}, v_{i} ∈ K^{∗} and compare coefficients of 1, …, Θ^{3} in (4.23), we will get

\begin{matrix}Q_{1}(v_{1}, …, v_{4}) & = & X_{1} \\ Q_{2}(v_{1}, …, v_{4}) & = & X_{2} \\ Q_{3}(v_{1}, …, v_{4}) & = & 0 \\ Q_{4}(v_{1}, …, v_{4}) & = & 0 \end{matrix} \}  (4.24)

where the Q_{i} are quadratic forms with coefficients in K. Now

\begin{matrix}Q_{3}(v_{1}, …, v_{4}) & = & 0 \\ Q_{4}(v_{1}, …, v_{4}) & = & 0 \end{matrix} \}  (4.25)

defines an intersection of 2 quadrics as is required.

4.7 Examples

We have applied the method of the previous section to obtain generators on the congruent number curve

E : Y^{2} = X(X^{2} − p^{2})  (4.26)

for primes

p = 257, 313, 353, 1201, 1217, 1249, 1321, 2113, 2273, 2777, 2833, 2953.

these primes are all congruent to 1 (mod 8), and it is easy to show that the 2-Selmer rank will always be 2 (see below). In [Serf], all the integers n ≤ 3000 for which the rank of Y^{2} = X(X^{2} − n^{2}) is 2 are predicted. For most of these, Mordell-Weil generators were found in [Ge, Zi]. However some values were omitted (presumably because the generators were too large for the method). The primes above are all the primes p ≡ 1 (mod 8) for which generators are not given in [Ge, Zi]. We shall omit most of the details, as they are quite tedious.

As usual, we have a map

E(ℚ) → ℚ^{∗}/ℚ^{∗}^{2} × ℚ^{∗}/ℚ^{∗}^{2} × ℚ^{∗}/ℚ^{∗}^{2}

given by ^{6}

(X, Y) → [Xℚ^{∗}^{2}, (X − p)ℚ^{∗}^{2}, (X + p)ℚ^{∗}^{2}].

It is not hard to show that the 2-Selmer group, regarded as a subgroup of ℚ^{∗}/ℚ^{∗}^{2} × ℚ^{∗}/ℚ^{∗}^{2} × ℚ^{∗}/ℚ^{∗}^{2} is generated by [p, 1, p], [p, 2p, 2], and the images of the points of order 2. Hence if we can find points on the homogeneous spaces corresponding to these 2 elements of the 2-Selmer group, we will be able to write down generators for E(ℚ)/2E(ℚ).

1. The homogeneous space corresponding to [p, 1, p] is

\begin{matrix}U^{2} − V^{2} & = & pA^{2} \\ U^{2} + V^{2} & = & B^{2} \end{matrix} \}

A rational point on this homogeneous space gives a corresponding rational point on E: (pU^{2}/V^{2}, p^{2}ABU/V^{3}). After 2 descents starting from this homogeneous space we arrived at the equation

e_{1}^{4} + 8e_{1}^{3}f_{1} + 12e_{1}^{2}f_{1}^{2} + 16e_{1}f_{1}^{3} + 4f_{1}^{4} = pg_{1}^{2}.  (4.27)

A rational point on this gives P_{1} on E with X-coordinate

X = p (\frac{e_{1}^{4} + 4e_{1}^{3}f_{1} + 4e_{1}^{2}f_{1}^{2} + 8e_{1}f_{1}^{3} + 4f_{1}^{4}}{4e_{1}f_{1}(e_{1}^{2} + 2e_{1}f_{1} + 2f_{1}^{2})} )^{2} .

After a small search for points on (4.27) we have found a point for each p in our list and computed the corresponding generator P_{1} on E. The information is contained in the table below.

2. Similarly, after 2 descents on the homogeneous space corresponding to [p, 2p, 2] we arrive at

e_{2}^{4} − 8e_{2}^{3}f_{2} + 18e_{2}^{2}f_{2}^{2} + 8e_{2}f_{2}^{3} + f_{2}^{4} = pg_{2}^{2}.  (4.28)

which gives generator P_{2} on E with X-coordinate

X = p (\frac{e_{1}^{4} − 4e_{1}^{3}f_{1} + 10e_{1}^{2}f_{1}^{2} + 4e_{1}f_{1}^{3} + f_{1}^{4}}{e_{1}^{4} − 4e_{1}^{3}f_{1} − 6e_{1}^{2}f_{1}^{2} + 4e_{1}f_{1}^{3} + f_{1}^{4}} )^{2} .

6For (X,Y) a point of order 2 the definition must be adjusted as on page 67 of [Ca1]

Again, after a short search for points on (4.28), we found a point with small coordinates for each p in our list.

\begin{matrix}p & e_{1} & f_{1} & ĥ(P_{1}) & e_{2} & f_{2} & ĥ(P_{2}) & R(P_{1}, P_{2}) \\ 257 & 1 & 2 & 10.243 & 13 & 2 & 19.340 & 168.055 \\ 253 & 121 & 4 & 38.629 & 34 & 23 & 30.979 & 177.561 \\ 313 & 194 & 3 & 39.493 & −18 & 103 & 35.825 & 193.933 \\ 1201 & 151 & 6 & 40.455 & −56 & 57 & 36.927 & 247.108 \\ 1217 & −29 & 4 & 25.829 & 8 & 1 & 15.628 & 316.657 \\ 1249 & 27 & 52 & 36.378 & 206 & 45 & 41.421 & 443.022 \\ 1321 & 11 & 3 & 21.274 & 9 & 2 & 16.394 & 285.289 \\ 2113 & −1 & 6 & 16.437 & −24 & 31 & 30.879 & 490.464 \\ 2273 & 8 & 1 & 14.848 & 1346 & 751 & 59.533 & 785.932 \\ 2777 & 22 & 73 & 35.506 & 11 & 2 & 17.919 & 621.627 \\ 2833 & 164 & 3 & 38.172 & −117 & 82 & 41.802 & 1147.840 \\ 2953 & 537 & 29 & 50.718 & −261 & 184 & 48.236 & 848.351 \end{matrix}

It should be clear from the height of the points listed that not all could be found by a naive computer search for points ^{7} on E.

4.8 Local to Global- A Counter Example

As we saw, given an intersection of two quadrics which defines a curve of genus 1, if there exist a singular combination of the quadrics which defined over the ground number field, then it is possible to perform a descent arriving at other curves of genus 1. It was therefore clear a priori, that it is unreasonable that a local-to-global principle should exist for such curves. This is because, even though the original curve is everywhere locally soluble, it is possible that none of its descendents are. This leaves us with the following question: Given an intersection of two quadrics

7Experience with findinf shows that it is not very feasible to search for points whose logarithmic height is much greater that 15.

\begin{matrix}x^{t}Ax = 0 \\ x^{t}Bx = 0 \end{matrix} \}  (4.29)

where A, B, are symmetric 4 × 4 matrices with entries over a number field K, and suppose that F (X, Y) = det(XA − Y B) is irreducible over K, and that the pair (4.29) is everywhere locally soluble. Is it the case that the pair must have a non-trivial solution defined over K? Infact, in the literature of Curves of Genus 1 I know of no counterexamples to local-to-global principle which cannot be demonstrated by constructing a complete covering of rational ^{8} descendents of the original curve, and showing that these are all insoluble on local grounds. Here we are faced with the task of constructing such a counterexample with no obvious method of constructing a covering of rational descendants. However there are well-known counterexamples where (by an argument due to Lind, see [Ca4] page 284) it is possible to show that there are no global points, without constructing any coverings , even though in such cases it was always easy to disprove global solubility by constructing a complete set of rational coverings.

In our counterexample to the question posed we will mimic Lind’s argument for disproving global solubility, and use our results from Chapters 5, and 6 to prove everywhere local solubility.

Example 4.8.1

\begin{matrix}−2x^{2} + 34x(z + w) + y^{2} − 17z^{2} & = & 0 \\ −17x^{2} + 3y^{2} + 4yz + w^{2} & = & 0 \end{matrix} \}  (4.30)

Here, the relevant det(XA − Y B) is irreducible, as required by our question. We will show that (4.30) is everywhere locally soluble but has no non-trivial rational points.

Let us prove first that the pair (4.30) have no common solutions over ℚ. Suppose that a non-trivial rational solution (x, y, z, w) exists. We may suppose that x, y, z, w are integers and that they have no common divisor.

8Here, by rational, we mean defined over the ground field.

It is easy to see that x ≠ 0. If 17|x then by the first equation y^{2} − 17z^{2} ≡ 0 (mod 17^{2}) (since 17^{2}|x^{2} and 17^{2}|34x). It would follow that 17|y and 17|z. From the second equation we get that 17|w. This contradiction shows that 17 does not divide x.

Suppose p is an odd prime dividing x. Reducing the first equation of (4.30) modulo p , we get that y^{2} ≡ 17z^{2} (mod p). It is straightforward to see that if p|y or p|z then p|x, y, z, w, giving us a contradiction. Hence we deduce that 17 is a quadratic residue modulo p. By the Law of Quadratic Reciprocity it follows that p is a quadratic residue modulo 17. This is true of all odd primes that divide x. But −1, and 2 are quadratic residues modulo 17. Hence we can write

x ≡ x_{1}^{2} (mod 17).

Similarly to the above, it is easy to show that 17 does not divide y, and that there exists y_{1} such that

y ≡ y_{1}^{2} (mod 17).

Since 17 does not divide x, y we get that 17 does not divide x_{1}, y_{1} either. Now reduce the first equation of (4.30) modulo 17. It follows that

−2x^{2} + y^{2} ≡ 0 (mod 17)

and so

2x_{1}^{4} ≡ y_{1}^{4} (mod 17).

But 2 is not a quartic residue modulo 17. This gives us a contradiction. Hence no rational solution to the pair (4.30) exists.

Let us now prove that the pair (4.30) has solutions everywhere locally. We can write (4.30) in the form of (4.29) where

A = ( \begin{matrix}−2 & 0 & 17 & 17 \\ 0 & 1 & 0 & 0 \\ 17 & 0 & −17 & 0 \\ 17 & 0 & 0 & 0 \end{matrix} )

and

B = ( \begin{matrix}−17 & 0 & 0 & 0 \\ 0 & 3 & 2 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} )

Let F (λ, μ) = det(λA − μB). The discriminant of F is

−11 327 320 899 466 789 632 139.

The prime factorization of this is

17^{3} × 2 305 581 294 416 199 803.

We denote the second prime by p_{1}. It follows from our Theorem 5.2.1 that to prove everywhere local solubility it sufficient to prove that the pair (4.30) has solutions over ℝ, ℚ_{2}, ℚ_{17}, ℚ_{p_{1}}.

1. Over ℝ. Here we note that the roots of F (1, μ) are roughly 0.34, 13.29, −0.38 ± 3.79i. Hence F is not totally real and so we must have solubility in ℝ by Lemma (6.2.2) on page 97.

2. Over ℚ_{2}. We recall that any 2-adic number which is congruent to 1 modulo 8 is a 2-adic square. Hence 17 is a 2-adic square. Moreover, it is easy to show that the (two) 2-adic square-roots of 17 are congruent to 1, −1 modulo 8 respectively. Let α ∈ ℚ_{2} satisfying α^{2} = 17 and α ≡ 1 (mod 8). Then −3α^{2} − 4α ≡ 1 (mod 8). Hence there exists β ∈ ℚ_{2} satisfying

β^{2} = −3α^{2} − 4α.

It follows that (0, α, 1, β) is a 2-adic solution to the pair (4.30).

3. Over ℚ_{17}. Here it is sufficient to observe that (1, 6, 4, 0) (mod 17) is a non-singular point on the reduction of the pair (4.30) modulo 17, and hence by Theorem (5.2.1) it must lift to a non-trivial solution on ℚ_{17}.

4. Over ℚ_{p_{1}} Here F (λ, μ) has only one double root modulo p_{1}. This is

1 : 393 077 095 592 234 641.

Write this as 1 : μ_{1}. Then A + μ_{1}B (mod p_{1}) is, up to scalar multiples, the only linear combination of A, B (mod p_{1}) which might have rank ≤ 2. Using Pari/GP, we find that its rank = 3. This means that every non-trivial linear combination of A, B (mod p_{1}) has rank ≥ 3. It is now easy to use the proof of Lemma B.0.4 to construct a non-singular point on the pair (4.30) modulo p_{1}, and hence this must have a non-trivial point defined over ℚ_{p_{1}}.

Local Solubility I: Over

Non-Archimedean

Completions

5.1 Introduction

Let K be a number field, and let A, B be 4×4 symmetric matrices with entries in K such that det(XA−Y B) has distinct roots (i.e. the combinant^{1} ∂(A, B) ≠ 0). Our goal in this chapter is to give algorithms for determining the solubility of

\begin{matrix}x^{t}Ax = 0 \\ x^{t}Bx = 0 \end{matrix} \}  (5.1)

over the non-archimedean completions of K. Our notation for this chapter is as follows:

K a number field

M_{K}^{0} a full set of inequivalent non-archimedean valuations on K O the set of integers of K υ a non-archimedean valuation on K O_{υ} := {x ∈ K_{υ} : υ(x) ≥ 0} π a prime element for υ (i.e. π ∈ K_{υ} such that υ(π) = 1) k_{υ} residue field associated with K_{υ} q the number of elements in k_{υ} ℙ_{π} := {(x, y) : x, y ∈ O_{υ} and min(υ(x), υ(y)) = 0}

1See page 107.

Further, when working with a fixed valuation υ, we let O_{υ} → k_{υ} be the natural map sending x ∈ O_{υ} to \overline{x} ∈ k_{υ}. Similarly, given vectors v and matrices C defined over O_{υ}, we denote by \overline{v} and \overline{C} to be their reductions in the obvious way.

We can assume without loss of generality that A and B have entries in O and hence that ∂(A, B) is in O.

The first algorithm we will give, relies on searching for points on

\begin{matrix}x^{t}Ax ≡ 0 \\ x^{t}Bx ≡ 0 \end{matrix} \} mod(π)  (5.2)

for πs corresponding to a finite pre-determined set of υs, and then attempting to lift the points found to points modulo powers of π until it is certain that they will lift to points defined over O_{υ}^{4}. We need two pieces of information:

1. For which of the infinitely many υ ∈ M_{K}^{0} is it necessary to do this?

2. Modulo which power of the corresponding π is it sufficient to find a solution, to be sure that this solution will lift?

The second algorithm we give assumes that A, B have a singular combination defined over O_{υ}.

5.2 Algorithm I

Theorem 5.2.1 Suppose A, B are 4 × 4 symmetric matrices with entries in Oυ such that ∂(A, B) ≠ 0. We have 1. If υ(2∂(A, B)) = 0 then

\begin{matrix}x^{t}Ax = 0 \\ x^{t}Bx = 0 \end{matrix} \}  (5.3)

has a non-trivial solution over Oυ.

2. Suppose that there exists x_{0} ∈ O_{υ}^{4}\πO_{υ}^{4} such that

x_{0}^{t}Ax_{0} ≡ x_{0}^{t}Bx_{0} ≡ 0 (mod π^{2δ+1})

and there is no pair (λ, μ) ∈ ℙ_{π} such that 2(λAx_{0}−μBx_{0}) ≡ 0 (mod π^{δ+1}). Then there exists x ∈ O_{υ}^{4} such that x ≡ x_{0} (mod π^{δ+1}) and x is a nontrivial solution to the pair of equations (5.3).

Proof. For the first part it is sufficient to note that if υ(2∂(A, B)) = 0 then x^{t}\overline{A}x ≡ x^{t}\overline{B}x ≡ 0 (mod π) has genus 1 by Theorem B.0.2; it follows then from [Ca4] page 205 that there is a non-trivial solution to (5.3). The second part is a special case of Theorem 5.21 on page 64 of [Gre]. □ Thus it is clear that to test local solubility at the archimedean places, it sufficient to check solubility over K_{v} only for those υ ∈ M_{K}^{0} for which υ(2∂(A, B)) ≠ 0. For any such υ, we can do this using the following algorithm.

Algorithm 5.2.1 We write down a complete set of coset representatives of O_{υ}^{4}/πO_{υ}^{4}. For any of these (other than the one contained in πO_{υ}^{4}) we check if it gives a solution to x^{t}Ax ≡ x^{t}Bx ≡ 0 (mod π). If there are none which give a solution to this, then (5.3) has no solution over K_{v} and we can stop. If there are some, and for one of them we can establish that it lifts to a point on (5.3) by the above Theorem then we can stop. If not then we will be left with x_{1}, …, x_{n} satisfying x^{t}Ax ≡ x^{t}Bx ≡ 0 (mod π) and for each there exists (λ, μ) ∈ ℙ_{π} such that 2(λAx − μBx) ≡ 0 (mod π).

Suppose now that after r steps we are left with a set of x_{1}, …, x_{n} (not necessarily the same x_{i} as before) satisfying x^{t}Ax ≡ x^{t}Bx ≡ 0 (mod π^{2r+1}) and for each there exists (λ, μ) ∈ ℙ_{π} such that 2(λAx − μBx) ≡ 0 (mod π^{r+1}). Then for each i = 1, …, n, we write a complete set of representatives of O_{υ}/π^{2r+3}O_{υ} which are congruent to x_{i} modulo π^{2r+1}. If none of these are on x^{t}Ax ≡ x^{t}Bx ≡ 0 (mod π^{2r+3}) then we go to the next i (if there are none for all the is then 5.3 has no solutions and we can stop). If there are some on x^{t}Ax ≡ x^{t}Bx ≡ 0 (mod π^{2r+3}), which using the above Theorem will lift to points on (5.3) then we can stop. So we may suppose that pooling our xs that we get for each i we end up with a new list x_{1}, …, x_{n} all satisfying x^{t}Ax ≡ x^{t}Bx ≡ 0 (mod π^{2r+3}) and for each there exists a pair (λ, μ) ∈ ℙ_{π} such that 2(λAx − μBx) ≡ 0 (mod π^{r+2}). The following Lemma shows that we must eventually stop.

Lemma 5.2.1 Suppose that there exists x_{1} ∈ O_{υ}^{4} such that

x_{1}Ax_{1} ≡ x_{1}Bx_{1} ≡ 0 (mod π^{α})

and there exists (λ : μ) ∈ ℙ_{π} such that (λAx_{1} − μBx_{1}) ≡ 0 (mod π^{β}), then min(α, β) ≤ υ(∂(A, B)).

Proof. Let γ = min(α, β). Choose x_{2}, x_{3}, x_{4} ∈ O_{υ}^{4} such that x_{1}, x_{2}, x_{3}, x_{4} are linearly independent modulo π. Let T be the 4 × 4 matrix with columns x_{1}, x_{2}, x_{3}, x_{4}. Further, choose (λ′ : μ′) ∈ ℙ_{π} such that λμ′−λ′μ ≢ 0 (mod π). Write

C = T^{t}(λA − μB)T, D = T^{t}(λ′A − μ′B)T.

Then by Theorem B.0.4 we have that υ(∂(C, D)) = υ(∂(A, B)). Now note that

C ≡ ( 0 C_{1}^{0  0}  ) (mod π^{γ})

where C_{1} is a 3 × 3 matrix with entries in O_{υ}. Also

D ≡ ( v D_{1}^{0  v^{t}}  ) (mod π^{γ})

where D_{1} is a 3 × 3 matrix with entries in O_{υ}, and v ∈ O_{υ}^{3}. It is now easily seen that the coefficients of X^{4} and X^{3}Y in G(X, Y) = det(XC − Y D) are congruent to 0 modulo π^{γ}. By considering the formula for the discriminant of G in terms of its coefficients, we see that π^{γ}|∂(C, D). This completes the proof.

□

5.3 Algorithm II: F has a rational root over O_{υ}

If F (X, Y) = det(XA − Y B) has a root defined over O_{υ}, then by parametrizing a singular combination of our equation

\begin{matrix}x^{t}Ax = 0 \\ x^{t}Bx = 0 \end{matrix} \}  (5.4)

we can reduce the testing of solubility of (5.4) over K_{v}, to the problem of testing solubility over K_{v} of an equation of the form

Y^{2} = g(X),  (5.5)

where g(X) ∈ K_{v}[X] has degree 4 and no repeated roots. In our algorithm here, instead of Hensel’s Lemma we intend to use techniques such as finding the roots of polynomials over finite fields, which will give us an overall polynomial time complexity ^{2}. We shall restrict ourselves to the case where υ(2) = 0, or equivalently where the residue field has odd characteristic.

5.3.1 Parametrizing the Singular Combination

As in the case over a number field (see page 76), to get to an equation of the form (5.5), it sufficient to find a single non-trivial solution of the singular combination. By a change of variable defined over K_{v} we may assume that our singular combination is of the form

aX^{2} + bY^{2} + cZ^{2} = 0  (5.6)

2The polynomials we wish to solve all have degree at most 4, and hence are soluble. Hence computing the roots is reduced to extracting pure roots of elements of finite fields. This problem is soluble in probablistic polynomial time, or alternatively in deterministic polynomial time assuming the Generalized Riemann Hypothesis (see [Cohen] pages 31-34 and page 37).

where a, b, c ∈ O_{υ}, and υ(a) = υ(b) = 0 and υ(c) = 0 or 1. If υ(c) = 1, then −ab^{−1} must be a square in O_{υ}, otherwise (5.4) does not have a solution over K_{v} and we may stop. So if α^{2} = −ab^{−1} then (1 , α , 0) is a non-trivial solution to (5.6), and we are finished. If υ(c) = 0, then heuristically, for 50% of pairs (x, y), −c^{−1}(ax^{2} + by^{2}) is a square in O_{υ}. Thus we assume that we can arrive at a solution in O(1) steps.

5.3.2 Local Solubility Testing for Y^{2} = g(X)

We recall that g ∈ O_{υ}[X] has degree 4, and non-zero discriminant, and that the characterstic of the residue field k_{v} is odd. We write q for the number of elements in the residue field k_{v}. When considering solutions to

Y^{2} = g(X)

we shall include those at infinity; thus this curve has a pair of points at infinity if and only if the leading coefficient of g is square in O_{υ}. If f is a polynomial in O_{υ}[X], we write \overline{f} for the image of f under the map O_{υ}[X] → k_{v}[X] induced by the natural map O_{υ} → k_{v}. If deg f = 4 but deg \overline{f} ≤ 3 we shall say that \overline{f} has a root at infinity; if deg \overline{f} ≤ 2 we shall say that \overline{f} has a multiple root at infinity. These conventions should be borne in mind in what follows.

Lemma 5.3.1 Suppose the curve

C : aY^{2} = f(X)  (5.7)

is given with f(X) ∈ O_{υ}[X], a ∈ O_{υ}. Let x_{1}, y_{1} ∈ O_{υ} such that

ay_{1}^{2} ≡ f(x_{1}) (mod π).

Then there exists x, y ∈ O_{υ} with x ≡ x_{1}, y ≡ y_{1} (mod π), such that

ay^{2} = f(x)

except possibly when

ay_{1} ≡ f′(x_{1}) ≡ 0 (mod π).

Proof. The conclusion follows by applying Hensel’s Lemma to the polynomial

G_{1}(X) = f(X) − ay_{1}^{2}

in the case f′(x_{1}) ≢ 0 (mod π), and to the polynomial

G_{2}(Y) = aY^{2} − f(x_{1})

in the case ay_{1} ≢ 0 (mod π). A suitable version of Hensel’s Lemma is given on page 49 of [Ca7]. □

Lemma 5.3.2 Suppose that f(X) ∈ O_{υ}[X] such that deg f = 4 and deg \overline{f} = 3 or 4. Suppose \overline{f}(X) has no repeated factors. Then the equation

Y^{2} = f(X)

has solutions over K_{v}. ^{3}

Proof. Under the hypotheses of the Lemma, the equation

Y^{2} = \overline{f}(X)

is a curve of genus 1 defined over k_{v}. It follows (see [Ca1] page 119) that it has at least one point defined over k_{v}. Again, since \overline{f} does not have repeated factors, we can use Lemma 5.3.1 to show that this solution lifts to one defined over K_{v}. □

Lemma 5.3.3 Suppose f(X) ∈ O_{υ}[X] such that 1 ≤ deg \overline{f} ≤ 4. Suppose that \overline{f} = \overline{g}^{2}\overline{h} where deg \overline{g} ≥ 0, deg \overline{h} ≥ 1 and \overline{h} is a square-free polynomial. Then the equation

Y^{2} = f(X)

has solutions in K_{v}.

3There is nothing new here: see [Ca4] page 205 (where the term elliptic curve really means a curve of genus 1).

Proof. The curve Y^{2} = \overline{h}(X) has genus 0, and hence has q + 1 points defined over k_{v}. Of these at most 2 are at infinity. Further, there is at most 1 root of g. If this root is x_{0} say, then there are at most 2 points on Y^{2} = \overline{h}(X) whose x-coordinate is x_{0}. Hence if q ≥ 5 then Y^{2} = \overline{h}(X) has at least one point (x_{1}, y_{1}) ∈ k_{v}^{2} with x_{1} ≢ x_{0}. Then the point (x_{1}, y_{1}\overline{g}(x_{1})) lifts to a point on Y^{2} = f(X) by Lemma 5.3.1. For the case q = 3 the Lemma can be established by a lengthy but straightforward case-by-case check which we omit. □ The following theorems follow easily from the above Lemmas.

Theorem 5.3.1 Suppose \overline{f} ≢ 0. If

Y^{2} = f(X)  (5.8)

has no points over K_{v} then

\overline{f} ≡ α\overline{g}^{2}

where \overline{g}(X) ∈ k_{v}[X] and α ∈ k_{v}^{∗}\k_{v}^{∗}^{2}.

Proof. The only case that remains to be checked is that if \overline{f} ≢ 0 and \overline{f} ≡ \overline{g}^{2} then ( 5.8) has a solution over K_{v}. For this it is sufficient to choose any x_{0} such that g(x_{0}) ≢ 0 (mod π), and then note that (x_{0}, g(x_{0})) lifts by Lemma 5.3.1. □

Theorem 5.3.2 Suppose f(X) ∈ O_{υ}[X] such that \overline{f} ≢ 0 (mod π), and deg \overline{f} ≤ 4. Then

πY^{2} = f(X)

has a solution in K_{v} if \overline{f} has a root defined k_{v} which is not a repeated root.

Algorithm 5.3.1 Testing

Y^{2} = f(X)  (5.9)

for solubility over K_{v}, where f(X) ∈ O_{υ}[X], deg f = 4, and the discriminant of f is non-zero.

Step I If \overline{f} ≡ 0 (mod π), then go to Step II. Now suppose \overline{f} ≢ 0. Check if \overline{f} = \overline{a}\overline{g}^{2} for some \overline{g} ∈ k_{v}[X], and \overline{a} ∈ k_{v}. If this is not the case, or if \overline{a} ∈ k_{v}^{∗}^{2} then we have local solubility by the above theorems and we can stop. Hence we can assume that \overline{f} = \overline{a}\overline{g}^{2}, and \overline{a} ∉ k_{v}^{∗}^{2}. So any solution (X_{0}, Y_{0}) ∈ O_{υ}^{2} to (5.9) must satisfy Y_{0} ≡ 0 and \overline{g}(X_{0}) ≡ 0. Now \overline{g} has at most two solutions \overline{ϵ_{1}}, \overline{ϵ_{2}} (mod π); if \overline{g} has no solutions in k_{v} then (5.9) has no solutions in O_{υ} and we can stop. Hence

Y_{0} = πY_{1} and X_{0} = πX_{1} + ϵ_{i}

where Y_{1}, X_{1} ∈ O_{υ}. Choose a ∈ O_{υ} and g ∈ O_{υ}[X] such that the images of a and g under O_{υ} → k_{v} are \overline{a} and \overline{g}. Then f = ag^{2}+πh where h has coefficients in O_{υ}. Since π^{2}|Y_{0}^{2} = f(X_{0}) and π|g(X_{0}), we get that π|h(X_{0}). Hence if neither of ϵ_{1} and ϵ_{2} is a root of \overline{h} then (5.9) is not soluble and we can stop. If say ϵ_{i} is a root of \overline{h} then π divides the trailing coefficient of h(πX + ϵ_{i}). So we will get at most 2 equations of the form

Y^{2} = f_{i}(X)

where f_{i}(X) = \frac{1}{π^{2}} f(πX + ϵ_{i}) ∈ O_{υ}[X]. It is now necessary and sufficient that one of these should have solutions in O_{υ}, and we use Step I again with f_{i} instead of f.

Step II Here f is divisible by π. If f is divisible by π^{2} then we can replace f by \frac{1}{π^{2}} f and go to Step I. So suppose that f_{1} = \frac{1}{π} f ≢ 0 (mod π). We see that we want to determine if

πY_{1}^{2} = f_{1}(X)

has solutions in O_{υ}. If f_{1} has no roots in k_{v} then (5.9) is not soluble and we can stop. If f_{1} has a root which is not a repeated root then (5.9) is soluble and we can stop. Suppose that f_{1} has repeated roots ϵ_{i} where i = 1, or i = 1, 2. Then it is necessary and sufficient to determine if either of

Y_{1}^{2} = \frac{1}{π} f_{1}(πX_{1} + ϵ_{i})

is soluble, and \frac{1}{π} f_{1}(πX_{1} + ϵ_{i}) ∈ O_{υ}[X]. So we use Step I again.

Lemma 5.3.4 Suppose r = υ(∂g) where ∂g is the discriminant of g. In the above algorithm, if we are still undecided after r+1 steps, then the equation (5.9) has a solution defined over K_{v} and we can stop.

Proof. It is clear that after r steps, we may write down a Z ∈ O_{υ}, such that f(Z) ≡ π^{2(r+1)}. By [Ca7] page 52, f has a root in O_{υ}. This immediately implies that (5.9) has a solution defined over K_{v}. □

Local Solubility II: Over

Archimedean Completions

6.1 Introduction

Let K be a number field, and A, B be n × n symmetric matrices with entries in O_{K}, the ring of integers of K. Suppose further that F (X, Y) = det(XA − Y B) is non-zero and does not have any repeated roots. We want to determine the local solubility of

\begin{matrix}x^{t}Ax = 0 \\ x^{t}Bx = 0 \end{matrix} \}  (6.1)

over all completions of K isomorphic to ℝ. If σ_{1}, …, σ_{n} : K ↪ ℝ are the real embeddings of K, then this is equivalent to determining if, for each i,

\begin{matrix}x^{t}A^{σ_{i}}x = 0 \\ x^{t}B^{σ_{i}}x = 0 \end{matrix} \}  (6.2)

has a non-trivial solution over ℝ.

Without loss of generality, we will assume for the rest of this chapter that σK = K ⊆ ℝ, and hence that A, B are n × n real matrices.

Further, as det(XA − Y B) is non-zero, by taking appropriate linear combinations of A and B (if necessary), we can assume that det A and det B are non-zero. Hence F (λ) = det(A − λB) is a real polynomial of degree n with distinct roots.

6.2 Reducing to Totally Real F (λ)

The following lemma of Swinnerton-Dyer allows us to get a better grip on the problem.

Lemma 6.2.1 (Swinnerton-Dyer) Let f, g be homogeneous real quadratic forms; the manifold f = g = 0 contains non-zero real points if and only if the quadratic form λf − μg is not definite for all real λ, μ.

Proof. This is part of Lemma 1 of [SwD1]. □ We are now ready for a simplification:

Lemma 6.2.2 Suppose that F (λ) = det(A − λB) has a non-real root. Then

\begin{matrix}x^{t}Ax = 0 \\ x^{t}Bx = 0 \end{matrix} \}  (6.3)

has a non-trivial solution over ℝ.

Proof. Recall first our assumption above that det A and det B are non-zero.

Suppose for a contradiction that the pair of equations (6.3) has no non-trivial real solutions. By Lemma (6.2.1) above, there exists a real linear combination of A and B which is a positive definite matrix. Without loss of generality, we may suppose that this is B, and that det A ≠ 0. From Linear Algebra we know that there exists a non-singular real matrix P such that P^{t}BP = I, the identity n×n matrix. Note that P^{t}AP is a real symmetric matrix, and hence must have only real eigenvalues. Hence the solutions to det((P^{t}AP) − λI), or equivalently those of det(A − λB) are all real. This gives our desired contradiction. □

6.3 Results on the Totally Real Case

By Lemma (6.2.2), we may restrict our attention to the case where F (X, Y) = det(XA − Y B) has n real roots. Hence by the next Lemma, the two matrices A, B are simultaneously diagonalizable over ℝ. Naturally, it is much easier to ask if there is a definite linear combination of two matrices when they are diagonal.

Lemma 6.3.1 Suppose that det A, det B are non-zero, and that det(A−Y B) is a polynomial of degree n, which has n real roots λ_{1}, …, λ_{n} say. Let x_{1}, …, x_{n} be non-trivial vectors in ℝ^{⋉} such that

(A − λ_{i}B)x_{i} = 0.  (6.4)

Let P = (x_{1}, …, x_{n}), the n × n matrix with the x_{i} as its columns. Then P ∈ GL_{n}(ℝ) and

P^{t}AP = ( \begin{matrix}α_{1} \\ & . & . & . \\ & & & & α_{n} \end{matrix} ) , P^{t}BP = ( \begin{matrix}β_{1} \\ & . & . & . \\ & & & & β_{n} \end{matrix} )  (6.5)

where α_{i} = λ_{i}x_{i}^{t}Bx_{i} , β_{i} = x_{i}^{t}Bx_{i} .

Proof. This is straightforward (cf Lemma 4.4.1 and Theorem 4.4.1). □

Lemma 6.3.2 Under the hypotheses and notation of Lemma (6.3.1), the pair of equations

\begin{matrix}x^{t}Ax = 0 \\ x^{t}Bx = 0 \end{matrix} \}  (6.6)

has a non-trivial real solution if and only if there do not exist real λ^{∗}, μ^{∗} (not both zero) such that the real numbers μ^{∗}α_{i} − λ^{∗}β_{i} all have the same sign.

Proof. This is immediate from Lemmas (6.2.1), (6.3.1). □

Lemma 6.3.3 Under the hypotheses and notation of Lemma (6.3.1), the pair of equations

\begin{matrix}x^{t}Ax = 0 \\ x^{t}Bx = 0 \end{matrix} \}  (6.7)

has no non-trivial real solution if and only if there exists λ_{j}, one of the roots of F (λ) = det(A − λB), such that A − λ_{j}B is semi-definite.

Proof. Suppose first that the pair of equations (6.7) has no non-trivial real solution. By Lemma (6.3.3) above, there exist real λ^{∗}, μ^{∗} such that μ^{∗}α_{i} − λ^{∗}β_{i} all have the same sign. If μ^{∗} = 0 then we can replace it by a very small non-zero real number and still have that μ^{∗}α_{i} − λ^{∗}β_{i} all have the same sign. Hence, we will assume that μ ≠ 0. By dividing by μ^{∗}, we see that there is a real λ^{∗∗} such that α_{i} − λ^{∗∗}β_{i} all have the same sign. Let λ_{j} be the root of F (λ) which is closest to λ^{∗∗}.We note that as we vary λ along the real line, none of the α_{i} −λβ_{i} change sign until we cross a root of ∏(α_{i} − λβ_{i}) = F (λ). Since λ_{j} is the closest root of F (λ) to λ^{∗∗}, it follows that α_{i} − λ_{j}β_{i} i ≠ j all have the same sign and that, of course, α_{j} − λ_{j}β_{j} = 0. Hence A − λ_{j}B is semi-definite, as required.

Conversely, suppose that A−λ_{j}B is semi-definite, where λ_{j} is a root of F (λ). Write

A = ( \begin{matrix}α_{1} \\ & . & . & . \\ & & & & α_{n} \end{matrix} ) , B = ( \begin{matrix}β_{1} \\ & . & . & . \\ & & & & β_{n} \end{matrix} )  (6.8)

as in Lemma (6.3.1). Recall that the alphas and betas are all non-zero, since by assumption det A, det B ≠ 0. A − λ_{j}B is semi-definite and so all the α_{i} − λ_{j}β_{i} are all of the same sign except α_{j} − λ_{j}β_{j} = 0. Note α_{j} − (λ_{j} + ϵ)β_{j} = −ϵβ_{j}; hence, since β_{j} ≠ 0, by choosing ϵ small enough and with appropriate sign, we will have that α_{i} − (λ_{j} + ϵ)β_{i} are all of the same sign. Hence A − (λ_{j} + ϵ)B is definite and the lemma follows. □

Theorem 6.3.1 Under the notation and hypotheses of Lemma (6.3.1),the pair of equations

\begin{matrix}x^{t}Ax = 0 \\ x^{t}Bx = 0 \end{matrix} \}  (6.9)

has a non-trivial solution in ℝ if and only if, for each λ_{j}, the real numbers α_{i} − λ_{j}β_{i} (i ≠ j) do not all have the same sign.

Proof. Immediate from Lemma (6.3.3). □

6.4 The Algorithm

We can now present our algorithm for determining the solubility of the pair

\begin{matrix}x^{t}Ax = 0 \\ x^{t}Bx = 0 \end{matrix} \}  (6.10)

over ℝ, under the assumption that det(XA − Y B) is non-zero, and has distinct roots.

Algorithm 6.4.1 Since det(XA − Y B) is non-zero, we can choose K-linear combinations of A and B which are non-singular and hence assume that det(A) and det(B) are non-zero. Now check if all the roots of det(A − λB) are real. If there is a non-real root then the pair (6.10) has a non-trivial solution over ℝ and we can stop. Otherwise let λ_{1}, …, λ_{n} be the roots of F (λ) = det(A − λB) and let x_{i} ∈ K(λ_{i})^{n} −{0} be solutions to (A−λ_{i}B)x_{i} = 0 (this is simply solving linear equations). Define β_{i} = x_{i}^{t}Bx_{i} and α_{i} = λ_{i}x_{i}^{t}Bx_{i}. It is clear that the λ_{i}, β_{i} and α_{i} can be calculated to arbitrary accuracy in ℝ. Check if, for each 1 ≤ j ≤ n, the numbers α_{i} − λ_{j}β_{i} (1 ≤ i ≤ n, i ≠ j) do not all have the same sign. These are non-zero, and so it is easy to determine their signs. If for some j, α_{i} − λ_{j}β_{i} i ≠ j have the same sign then (6.10) has only the trivial solution. Otherwise, it has a non-trivial solution.

6.5 A Special Case for Two Quadrics in Four

Variables

We record in passing the following theorem, which says that if n = 4, K = ℚ and F (X, Y) = det(XA−Y B) has 4 distinct roots, all in ℚ, then solubility over ℝ is guaranteed once solubility over ℚ_{p} has been checked for all (finite) primes p.

Theorem 6.5.1 Suppose that A, B are symmetric 4 × 4 matrices with rational entries such that F (X, Y) = det(XA − Y B) can be factorized completely over ℚ. Then, if

\begin{matrix}x^{t}Ax = 0 \\ x^{t}Bx = 0 \end{matrix} \}  (6.11)

has non-trivial solutions in ℚ_{p} for all finite primes p, it has a non-trivial solution in ℝ.

Proof. Suppose (6.11) has non-trivial solutions in ℚ_{p} for all finite primes p, and it has no non-trivial solution in ℝ. As before, we may assume that A and B are non-singular. Hence by Lemma (6.3.3), there exists λ_{j}, a root of det(A − λB) such that A − λ_{j}B is semi-definite. Now after a simultaneous diagonalization over ℚ (see Theorem 4.4.1), we can assume that

\begin{matrix}x^{t}Ax & = & α_{1}x_{1}^{2} & + & α_{2}x_{2}^{2} & + & α_{3}x_{3}^{2} & + & α_{4}x_{4}^{2} \\ x^{t}(A − λ_{j}B)x & = & γ_{1}x_{1}^{2} & + & γ_{2}x_{2}^{2} & + & γ_{3}x_{3}^{2} \end{matrix} \}  (6.12)

where γ_{1}, γ_{2}, γ_{3} have the same sign. Recall that this has non-trivial solutions over ℚ_{p}, for all finite primes p. We will show that the second equation, as an equation in 3 variables, has a non-trivial solutions over all completions ℚ_{p} (p ≠ ∞). If (x_{1}, x_{2}, x_{3}, x_{4}) ∈ ℚ_{p}^{4}−{0} and solves the pair (6.12) then we cannot have x_{1} = x_{2} = x_{3} = 0. For otherwise α_{4}x_{4}^{2} = 0 in ℚ_{p} and so either α_{4} = 0 or x_{4} = 0. Hence either det(A) = 0 or (x_{1}, x_{2}, x_{3}, x_{4}) = 0. This contradiction shows that the equation

γ_{1}x_{1}^{2} + γ_{2}x_{2}^{2} + γ_{3}x_{3}^{2} = 0  (6.13)

is solvable at all the finite primes. By the well known lemma below, this must also have a solution in the reals. This contradicts the fact that γ_{1}, γ_{2}, γ_{3} share the same sign, and so we are finished. □

Lemma 6.5.1 for any conic over ℚ, the number of primes p (including ∞) for which there is not a point over ℚ_{p} is even.

Proof. See [Ca2] page 46. □

Appendix A

Hensel Lifting for Y^{2} = g(X)

Let K be a field complete with respect to a non-archimedean valuation υ, such that the corresponding residue field is finite. Let O be the ring of valuation integers, and let π be a uniformizer for υ. Suppose g(X) is a non-zero polynomial with coefficients in O, and has non-zero discriminant. In this Appendix we consider the following problem: Given x_{0} ∈ O and ϵ ≥ 0, does there exist x ∈ O such that g(x) is a square in O and υ(x − x_{0}) ≥ ϵ ?

The question arises from our method of computing the non-archimedean contribution to the upper bound for h − ĥ in Chapter 2. This question is considered in [Bi, SwD] and [Cre] for the case where K = ℚ_{p} for some prime p, and g is a polynomial of degree 4, though the details for our general case are not any more difficult. The following Lemma, is a direct generalization of Lemmas 6 and 7 of [Bi, SwD], and the details of their proof carry over without any changes, and thus a proof is omitted.

Lemma A.0.2 Suppose υ(2) = e ≥ 0. Suppose that x_{0} ∈ O, and let

υ(g(x_{0})) = λ, υ(g′(x_{0})) = μ.

Then there exists x ∈ O, with g(x) a square in O, and υ(x − x_{0}) ≥ ϵ if

1. g(x_{0}) is a square in O, or 2. λ − μ ≥ ϵ > μ, or

3. λ is even, and there exists i such that 1 ≤ i ≤ 2e, λ = μ + ϵ − i, ϵ > μ, and π^{−λ}g(x_{0}) ≡ 1 (mod π^{i}).

There may exist x ∈ O, with g(x) a square in O, and υ(x − x_{0}) ≥ ϵ if

1. μ ≥ ϵ and λ ≥ 2ϵ, or

2. μ ≥ ϵ and λ = 2ϵ − 2i where 1 ≤ i ≤ e.

There does not exist x ∈ O, with g(x) a square in O, and υ(x − x_{0}) ≥ ϵ in any other case.

Now suppose that x_{0} ∈ O, and that we want to know if there exists x ∈ O such that g(x) is a square in O and υ(x−x_{0})ϵ. If we use the above Lemma we will be able to decide this question unless μ_{0} ≥ ϵ, and λ_{0} ≥ 2ϵ−2e, where λ_{0} = υ(g(x_{0})), and μ = υ(g′(x_{0})). Suppose that this is the case. Let α_{1}, …, α_{q} be a complete set of coset representatives for O/πO. Now it is sufficient to determine, if for some j, there exists x ∈ O such that g(x) is a square in O and υ(x − x_{1}) ≥ ϵ + 1 where x_{1} = x_{0} + α_{j}π^{ϵ}. For any fixed j, we use the above Lemma. If we are still undecided, then μ_{1} ≥ ϵ + 1, and λ_{1} ≥ 2(ϵ + 1) − 2e, where λ_{1} = υ(g(x_{1})) and μ_{1} = υ(g′(x_{1})). Continuing recursively in the obvious manner, if our question remains undecided forever, then we will have constructed a sequence (x_{k}) ∈ O (k = 0, 1, …) such that υ(g(x_{k})) ≥ ϵ+k, and υ(g′(x_{k})) ≥ 2(ϵ+k)−2e. Since K is complete, and the discriminant of g is non-zero, we arrive at a contradiction.

Appendix B

The Geometry of the

Intersection of two Quadrics

Suppose A and B are linearly independent 4 × 4 matrices with entries in a ground field K, which has characteristic ≠ 2. We shall say that two distinct quadric surfaces (in ℙ^{3})

H_{1} : x^{t}Ax = 0

and

H_{2} : x^{t}Bx = 0

intersect transversely if F (X, Y) = det(XA − Y B) is non-zero and has distinct roots. We assume throughout that our ground field K has characteristic ≠ 2.

Theorem B.0.2 The intersection of the 2 distinct quadric surfaces H_{1}, and H_{2} is an (irreducible) curve of genus 1 if and only if it is transverse. Moreover, if the intersection is not transverse, then it has a (Zariski) component which is a curve of genus 0.

Proof. Suppose that H_{1}, and H_{2} intersect transversely. Then by Proposition 22.38 on page 304 of [Harris], the intersection

\begin{matrix}x^{t}Ax = 0 \\ x^{t}Bx = 0 \end{matrix} \}  (B.1)

is a curve of genus 1. The rest of the theorem follows from the two Lemmas below. □

Lemma B.0.3 If det(XA − Y B) = 0 identically, then (B.1) must have a Zariski component which is a curve of genus 0.

Proof. Let y be transcendental over K. Now det(A − yB) = 0 and so there exists a vector v(y) ∈ K[y]^{4}\{0} such that

(A − yB)v(y) = 0.

Moreover, we may assume that the elements of v(y) are coprime as polynomials in y. Now let y_{1}, y_{2} be independent transcendental elements over K. By the usual argument (cf. Lemma 4.4.1) y_{1} ≠ y_{2} implies that

v(y_{1})^{t}Av(y_{2}) = v(y_{1})^{t}Bv(y_{2}) = 0.

Now substitute y_{1} = y_{2} = y in the above. So we have

v(y)^{t}Av(y) = v(y)^{t}Bv(y) = 0.

If v(y) is a non-constant vector then the conclusion follows. Suppose that v(y) = v ∈ K^{4}\{0}. So (A − yB)v = 0, which implies that Av = Bv = 0. In this case it is easy to show now that the intersection H_{1} ∩ H_{2} is a collection of straight lines (in ℙ^{3}). □

Lemma B.0.4 Suppose det(XA−Y B) ≠ 0 but it has a multiple root. Then (B.1) has a component which is a curve of genus 0.

Proof. Without loss of generality we may assume that Y^{2} divides det(XA − Y B). Clearly the rank of A is at most 3. If A has rank 1 or 2, then let L(x_{1}, …, x_{4}) be a linear form dividing x^{t}Ax. Then the intersection of L(x_{1}, …, x_{4}) = 0 and x^{t}Bx = 0 is either a pair of lines or a plane conic. In either case the conclusion of the lemma follows.

Hence suppose that the rank of A is 3. By a non-singular change of variable we may assume that

A = ( A_{1}  0_{0  0} ) .

Write

x^{t}Bx = q(x_{1}, x_{2}, x_{3}) + x_{4}l(x_{1}, x_{2}, x_{3}) + bx_{4}^{2}

where q is quadratic, l is linear and b is constant. It follows that the coefficient of X^{3}Y in det(XA − Y B) is b det(A_{1}). Since Y^{2}| det(XA − Y B) we have that b = 0. So (B.1) is birational to the conic

(x_{1}, x_{2}, x_{3})A_{1}(x_{1}, x_{2}, x_{3})^{t} = 0

via the map

x_{4} = \frac{−q(x_{1}, x_{2}, x_{3})}{l(x_{1}, x_{2}, x_{3})}.

□

This completes the proof.

Theorem B.0.3 Suppose that the characteristic of K is 0. Suppose that C is a curve of genus 1, and D is the intersection of 2 distinct quadric surfaces H_{1} and H_{2} (in ℙ^{3}) as above. If there is a non-constant morphism ϕ : D → C then the intersection is transverse and D is a curve of genus 1.

Proof. If the intersection is not transverse, then D contains a component D_{1} which is a curve of genus 0. Restricting ϕ to D_{1} we see that we have a nonconstant morphism from a curve of genus 0 into a curve of genus 1. This is impossible (see exercise 2.8 on page 43 of [Si2]). □

B.0.1 The Combinant

Define ∂(A, B) = disc(det(XA − Y B)). We need(ed) the following theorem. Theorem B.0.4 If a, b, c, d are elements of K and P is a 4 × 4 matrix then write C = P^{t}(aA − bB)P and D = P^{t}(cA − dB)P. We have

∂(C, D) = (ad − bc)^{12}(det(P))^{12}∂(A, B).

Proof. See [Bi, Le, Mu] page 112. □

Bibliography

[Bi, SwD] B.J. Birch and H.P.F. Swinnerton-Dyer, Notes on Elliptic Curves I, J. Reine Angew. Math. 212 (1963), 7-25.

[Bi, Le, Mu] B.J. Birch, D.J. Lewis, T. G. Murphy, Simultaneous Quadratic Forms, Am .J. Math. 84 (1962), 110-112.

[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, Bue] A. Bremner and D. Buell, Three Points of Great Height on Elliptic Curves, Math.Comp. 61 (1993), 111-115.

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

[Brum, Kra] A. Brumer and K. Kramer, The Rank of Elliptic Curves, Duke Math. J., 44 (1977), 715–743.

[Buch] J. Buchmann, A Subexponential Algorithm for the Determination of Class Groups and Regulators of Algebraic Number Fields, Séminaire de théorie des nombres, Paris (1988-1989), 28–41.

[Bu, Len] J. Buchmann and H.W. Lenstra Jnr, Approximating Rings of Integers in Number Fields, To Appear.

[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.

[Ca4] J.W.S. Cassels, Survey Article: Diophantine Equations with Special Reference to Elliptic Curves, J.L.M.S. 41 (1966), 193-291.

[Ca5] J.W.S. Cassels, On a theorem of Dem’Janenko, J. London Math. Soc. 43 (Part I) (1968), 67-70.

[Ca6] J.W.S. Cassels, The Mordell-Weil Group of Curves of Genus 2, .

[Ca7] J.W.S. Cassels, Local Fields, LMS Student Texts, Cambridge University Press, 1986.

[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)

[Elkies] N. D. Elkies, On A^{4} + B^{4} + C^{4} = D^{4}, Math. Comp. 51 (1988), 825-835.

[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.

[Gre] M. J. Greenberg, Lectures on Forms in Many Variable, W. A. Benjamin, 1969.

[Guy] R. K. Guy, Unsolved Problems in Number Theory, Springer-Verlag, 1981.

[Harris] J. Harris, Algebraic Geometry, GTM 133, Springer-Verlag, 1992.

[Hart] R. Hartshorne, Algebraic Geometry, GTM 52, Springer-Verlag, 1977.

[Holzer] L. Holzer, Minimal solutions of diophantine equations, Can. J. Math. 11 (1950), 238-244.

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

[Kob] N. Koblitz, Introduction to Elliptic Curves and Modular Forms, GTM 97, Springer-Verlag, 1984.

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

[Mazur] B. Mazur, On the Passage from Local to Global in Number Theory, Bulletin (new series) of the AMS 29 (1993), 14-50.

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

[Mord] L. J. Mordell, Diophantine Equations, Academic Press, 1969.

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

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

[Scha] E.F. Schaefer, 2-descent on the Jacobians of Hyperelliptic Curves, To Appear: Journal of Number Theory.

[Serf] P. Serf, Congruent Numbers and Elliptic Curves, in “Computational Number Theory”, ed. A. Pethő, M. Pohst, H. Williams, H.Zimmer , Walter de Gruyter, 1991.

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

[Sieg2] C. L. Siegel, Normen Algebraischer Zahlen, Nachr. Akad. Wiss Gottingen, Math.-Phys. Kl.

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

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

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

[Sik] S. Siksek, Infinite Descents on Elliptic Curves, to appear in Rocky Mountain Journal.

[Si, Sm] S. Siksek and N. P. Smart, On the Complexity of Computing the 2-Selmer Group of and Elliptic Curve, submitted to the Journal of Number Theory.

[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, We] R.J. Stroeker and B. M. M. de Weger, On a quartic diophantine equation, Report 9371/B, Econometric Institute, Erasmus University Rotterdam, 1993.

[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.

[SwD1] H. P. F. Swinnerton-Dyer, Rational Zeros of two Quadratic Forms, Acta. Arith. 9 (1964)

[SwD2] H. P. F. Swinnerton-Dyer, A^{4} +B^{4} = C^{4} +D^{4} revisited, J. London Math. Soc. 43 (Part I) (1968), 149-151.

[Thiel] C. Thiel, Under the assumption of the Generalized Riemann Hypothesis verifying the class number belongs to N P ∩ co–N P, In ANTS-1 : Algorithmic Number Theory, Eds L.M. Adleman and M-D. Huang, Springer-Verlag (Berlin), Lecture Notes In Computer Science No. 877, (1994),234–247.

[Trop] A.M. Tropper, Linear Algebra, Van Nostrand Reinhold, 1969.

[Tz] N. Tzanakis, to appear.

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