EXPLICIT 4-DESCENTS ON AN ELLIPTIC CURVE

J.R. MERRIMAN, S. SIKSEK, AND N.P. SMART

Abstract. It is shown that the obvious method of descending from an element of the 2-Selmer group of an elliptic curve, E, will indeed give elements of order 1, 2 or 4 in the Weil-Chatelet group of E. Explicit algorithms for such a method are given.

1. Introduction

We wish to investigate how to find generators of an elliptic curve, E(ℚ), modulo 2E(ℚ) defined over ℚ. As is usual we can reduce this to the study of certain homogenous spaces

y^{2} = f(x, 1),  (1)

where f(X, Z) is a binary quartic form (or quartic for short) with integer coefficients. One wishes to know whether equation (1) has a ℚ-rational point and if so to exhibit one. One can often show that equation (1) has no ℚrational points by local methods. However, even if (1) is everywhere locally soluble, it does not follow necessarily that a ℚ-rational point exists; this failure of the “Hasse principle” is well known and gives rise to an element of the Tate-Shafarevich group.

Further, it is not necessarily the case that a rational point on equation (1) will have“small” coordinates. Hence searching for a rational point (even when one is known to exist) may be futile. This is important in some conditional algorithms, eg [13], for determining generators of E when one computes, for instance, the rank of the curve by assuming the conjectures of Birch and Swinnerton-Dyer. In such methods one then just needs to search for enough points with the correct regulator. One has a bound on the search region on the elliptic curve, but this can often be too large for practical use, especially if the curve has a generator with a large height. To get around this problem one could perform a 2-descent and then search in a bounded region on the descendents, this should be easier as this new region should be smaller. If however the search region is still too large performing a further descent and obtaining a 4-descent will again reduce the search region, hopefully to something more manageable.

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

Key words and phrases. Elliptic Curves, Computational Number Theory.

Interest in practical algorithms to find the generators of the Mordell-Weil group has grown in recent years due to the need to find the generators to compute all the integral points using elliptic logarithms. This is the most efficient way known to compute integral points, see [23], [12], [21] and [22].

In this paper we give an explicit method, suitable for machine calculation, to deal with such troublesome homogenous spaces by considering further descents on equation (1). This has been done before in the literature, see [2] and [16], for special types of elliptic curves. However we could find no general account which was of use for systematic machine computations. We explain an explicit method for performing such further descents and we show this is equivalent to constructing elements of order dividing 4 in the Tate-Shafarevich group of the elliptic curve. Our method resembles that in [3] and [4]. The associated problem of finding generators of the Mordell-Weil group given generators of E/mE we shall not discuss here. However a very efficient solution to this problem has recently been given by Siksek, [18].

This work grew out of the PhD thesis of the second author, [17]. However it was not until John Cremona pointed out to us the link to us between classical invariant theory and 2-descents that we could see how to put everything together. We would like to thank John Cremona and Nelson Stephens for their help and encouragement in the course of our work. We also would like to thank EPSRC who funded the research contained in this paper.

2. Background

Before we proceed to 4-descents we recap on the method of 2-descent. Let E be an elliptic curve over ℚ given by

Y^{2} = X^{3} + IX + J.

Now consider the set of all binary quartics with rational coefficients with the standard invariants I and J;

f = ax^{4} + bx^{3}z + cx^{2}z^{2} + dxz^{3} + ez^{4}

We only consider such quartics up to the relation of equivalence: f and g are equivalent if

g(x, z) = u^{2}f(αx + βz, γx + δz),

for u, α, β, γ, δ ∈ ℚ, with u ≠ 0. It is well known, see [1], that such quartics represent elements of the 2-Selmer group. They can be efficiently computed by the methods in [1] and [11].

As the curves D_{2} : y^{2} = f(x, z) are elements of the 2-Selmer group there is a map ϕ_{2} : D_{2} → E defined over ℚ which commutes with the birational map from D_{2} to its jacobian (which is E) and the multiplication by 2 map on E, i.e. We have the commutative diagram:

\begin{matrix}E & \underrightarrow{[2]} & E \\ ↕ & ϕ_{2}↗ \\ D_{2} \end{matrix}

Given a rational point on D_{2} and ϕ_{2} we can compute its image on E. This is what one does in the standard method of 2-descent on an elliptic curve. By [10], one can take ϕ_{2} to be the following map derived from the syzygy between the covariants of f. Let H(x, z) denote the hessian determinant of f(x, z) and T (x, z) denote the Jacobian determinant of f(x, z) and H(x, z). Then we have

ϕ_{2}(x, y) = (−H(x, 1)/4y^{2}, 3T (x, 1)/32y^{3}) .

Such curves y^{2} = f(x, 1) correspond to elements of order dividing 2 in the Weil-Chatelet group of E. Now by [5], elements of order dividing 4 in W C(E) correspond to curves D_{4} whose jacobian is E and for which there is a map ϕ_{4} defined over ℚ such that the following diagram is commutative:

E \underrightarrow{[2]} E \underrightarrow{[2]} E
↕  ↕ ϕ_{2}↗
D_{4} \underrightarrow{ϕ_{4}} D_{2}

Of course we are only interested in finding D_{4}’s which cover a D_{2} which is locally soluble everywhere. This could be for one of two reasons:

• To show that D_{2} has no rational solutions and hence is an element of order 2 in the Tate-Shafarevich group of E.

• To produce a point on D_{2} and hence via ϕ_{2} produce a point on E. This last reason is useful as the heights of rational points on D_{4} should be much smaller than the height of equivalent points on D_{2} and hence we expect them to be easier to find. In addition we will only be interested in D_{2}’s which do not possess an obvious rational point. Hence we assume that either f(x, z) is irreducible or that it is a product of two irreducible quadratic factors.

3. The Intersection of Two Quadric Surfaces

An element of order 4 in the Tate-Shafarevich group, III, of an elliptic curve will be represented by a principal homogeneous space H of period 4 and, by a well established result due to Lang and Tate (see for example [20][Exercise 10.11]), the index of this homogeneous space is also 4. This means that the minimum degree of a divisor on the curve, rational over ℚ, is 4. We must therefore discuss the properties of curves of genus 1 with this property. Fortunately there is an excellent exposition in [26][Chapter 2 Appendix II], although we will need to supplement this with some more detailed algebraic information. For convenience, we briefly summarise the geometry.

Suppose our divisor is Z_{0}, then since H is a curve of genus 1, the linear system |Z_{0}| is very ample and by Riemann-Roch has dimension 3. The image of H under the associated (bi-)rational mapping is therefore a nonsingular quartic curve in ℙ^{3}. The projective coordinates x_{1}, x_{2}, x_{3}, x_{4} cut out a basis for this linear system and, further, since the linear system |2Z_{0}| has dimension 7 but contains the divisors corresponding to the 10 quadratic monomials x_{i}x_{j}, it is clear that H is contained in the intersection of two quadrics. Since H has genus 1 it is in fact a complete intersection of any pair of quadrics containing it. For convenience we will fix a pair, say Q_{1}(x) and Q_{2}(x) which we identify with their corresponding quadratic forms

Q_{1}(x) = x^{t}Ax, Q_{2}(x) = x^{t}Bx

where x = (x_{1} : x_{2} : x_{3} : x_{4})^{t}. Hence H is given by the simultaneous equations Q_{1}(x) = Q_{2}(x) = 0.

For any curve X one can construct a family of varieties Pic^{n}(X) parametrising divisor classes of degree n on X. Thus, J = Pic^{0}(X) is just the Jacobian variety of X. Each Pic^{n}(X) for n ≥ 1 is a principal homogeneous space for J and our next construction amounts to a birational identification of the curve Pic^{2}(H) for our curve of genus 1, H. We consider the pencil of quadrics Q_{λ}(x) = λ_{1}Q_{1}(x) + λ_{2}Q_{2}(x), for λ = (λ_{1} : λ_{2}) ∈ ℙ^{1}, which contain H and let

F (λ) = F (λ_{1}, λ_{2}) = det(λ_{1}A + λ_{2}B),

a homogeneous quartic polynomial in λ_{1}, λ_{2}. This defines a curve of genus 1 which is the double covering of ℙ^{1} ramified at the 4 points corresponding to the zeros of F. The coefficients of F (λ_{1}, λ_{2}) are the basic invariants of Q_{1}(x) and Q_{2}(x) (see below) and we denote by D_{2} the curve Y^{2} = F (λ_{1}, 1). Using the notation of [26][Appendix III] we can construct a rational mapping (defined over ℚ)

ω : H × H → D_{2}

by the recipe: if P_{1}, P_{2} denote points of H there is a unique point λ = (λ_{1} : λ_{2}) ∈ ℙ^{1} such that the line P_{1}P_{2} (tangent if P_{1} = P_{2}) lies in the quadric Q_{λ}. As explained in [26][Appendix III], F (λ_{1}, λ_{2}) is a square and hence we obtain a point, ω(P_{1}, P_{2}), on the double cover. This construction yields a rational mapping with the properties

ω(P_{1}, P_{2}) = ω(P′_{1}, P′_{2}) ⇔ P_{1} + P_{2} ∼ P′_{1} + P′_{2}

and therefore induces a birational mapping of Pic^{2}(H) with D_{2}. When we fix a point on H, say, P_{0} the mapping P ↦ ω(P, P_{0}) induces a birational map between D_{2} ×_{ℚ}ℚ(P_{0}) and H ×_{ℚ}ℚ(P_{0}) and both are identified with the elliptic curve which is their Jacobian over ℚ(P_{0}), i.e. J ×_{ℚ} ℚ(P_{0}). Were H to have a ℚ-rational divisor of degree 2 then Pic^{2}(H) ≃ Pic^{0}(H) and H would correspond to a 2-covering of J and so correspond to an element of order dividing 2 in III.

We now assume that a point P_{0} on H has been fixed and assume we are working over a field of definition for H and P_{0}. Then H itself has the structure of an elliptic curve isomorphic to that of its Jacobian.

Geometrically the group law is given as follows: P_{1}, P_{2}, P_{3} have the properties

P_{1} + P_{2} + P_{3} = 0 ⇔ P_{0}, P_{1}, P_{2}, P_{3} are coplanar.

Further −P_{1} is the residual intersection of the plane through P_{1} containing the tangent line to H at P_{0}. ¿From this description it is then clear that points of order 2 on H are those points at which the tangent line to H is coplanar with the tangent line at P_{0}. If P_{1} denotes such a point, a simple geometrical argument shows that the unique quadric in the pencil Q_{λ} which contains the line P_{0}P_{1} must be a cone and this is precisely the condition that F (λ) = 0, i.e. ω(P_{1}, P_{0}) is a ramification point of the double covering D_{2} → ℙ^{1}.

We now turn our attention to the invariant theory our pair of quadric surfaces in ℙ^{3}. Much of what follows will be found in Todd, [25][Chapter 7], but using a different notation. As above let

Q_{1}(x) = x^{t}Ax , Q_{2}(x) = x^{t}Bx,

where A and B are two symmetric 4 × 4 matrices, denote our two quadric surfaces with transversal intersection. We then define the basic invariants, σ_{0}, …, σ_{4}, of Q_{1}(x) and Q_{2}(x) by the equation

det(t_{1}A + t_{2}B) = t_{1}^{4}σ_{0} + t_{1}^{3}t_{2}σ_{1} + t_{1}^{2}t_{2}^{2}σ_{2} + t_{1}t_{2}^{3}σ_{3} + t_{2}^{4}σ_{4}.

To determine the fundamental covariants we first set A′ = adj(A), B′ = adj(B) and then define d_{1} and d_{2} to be the two symmetric matrices determined by

adj(t_{1}A′ + t_{2}B′) = t_{1}^{3}σ_{0}^{2}A + t_{1}^{2}t_{2}σ_{0}d_{1} + t_{1}t_{2}^{2}σ_{4}d_{2} + t_{2}^{3}σ_{4}^{2}B.

We then define two more quadratic forms

F_{1}(x) = x^{t}d_{1}x , F_{2}(x) = x^{t}d_{2}x.

The five fundamental covariants of Q_{1}(x) and Q_{2}(x) are then given by Q_{1}(x), Q_{2}(x), F_{1}(x), F_{2}(x) and the jacobian:

G(x) = \frac{1}{16} \frac{∂(Q_{1}, Q_{2}, F_{1}, F_{2})}{∂(x_{1}, x_{2}, x_{3}, x_{4})}.

Lemma 1. The invariants σ_{i} and the covariants F_{1}(x), F_{2}(x) are of weight two, the covariants Q_{1}(x) and Q_{2}(x) are of weight zero, whilst the covariant G(x) is of weight 5.

Proof. Let x = T y denote a change of variable. Putting U^{t} = adj(T) we have

adj(U^{t}) = adj((det T)T^{−1}) = (det T)^{2}T.

Let A^{∗} = T^{t}AT, A′^{∗} = U^{t}A′U etc then we have • The invariants σ_{i} have weight two because

det(t_{1}A^{∗} + t_{2}B^{∗}) = (det T)^{2} det(t_{1}A + t_{2}B).

• The covariants Q_{1}(x) and Q_{2}(x) have weight zero because

Q_{1}^{∗}(y) = y^{t}A^{∗}y = y^{t}T^{t}AT y = x^{t}Ax = Q_{1}(x).

• The covariants F_{1}(x) and F_{2}(x) are of weight two because

adj(t_{1}A′^{∗} + t_{2}B′^{∗}) = (det T)^{4}adj(t_{1}A′ + t_{2}B′)

and so σ_{0}^{∗}d_{1}^{∗} = (det T)^{4}σ_{0}T^{t}d_{1}T. Hence d_{1}^{∗} = (det T)^{2}T^{t}d_{1}T. Similarly for d_{2}.

• The fact that the covariant G(x) has weight 5 then follows from the definition by applying the rule for computing the partial derivatives of a composition of functions.

One then finds that the syzygy given by Figure 1 holds. This was derived by applying the above weight considerations to the two quadrics

Q_{1}(x) = μ_{1}x_{1}^{2} + μ_{2}x_{2}^{2} + μ_{3}x_{3}^{2} + μ_{4}x_{4}^{2} , Q_{2}(x) = λ_{1}x_{1}^{2} + λ_{2}x_{2}^{2} + λ_{3}x_{3}^{2} + λ_{4}x_{4}^{2}.

By a linear change of variable defined over ℂ one can always put our two quadrics in this form as we have assumed that they are transversal. As it is a formal identity holding for these two quadrics it must then hold in general.

When x is a point on our intersection of two quadrics the syzygy of Figure 1 reduces to

G^{2} = σ_{0}F_{1}^{4} − F_{1}^{3}F_{2}σ_{1} + F_{1}^{2}F_{2}^{2}σ_{2} − F_{1}F_{2}^{3}σ_{3} + F_{2}^{4}σ_{4}

So we have a map from H onto a curve of the form

D_{2} : y^{2} = σ_{0}x^{4} + σ_{1}x^{3} + σ_{2}x^{2} + σ_{3}x + σ_{4}

F_{2}^{2}Q_{1}Q_{2}σ_{1}σ_{3}^{2} − 2F_{2}^{2}Q_{1}Q_{2}σ_{1}σ_{2}σ_{4} + F_{2}^{3}Q_{2}σ_{1}σ_{4} − 2σ_{0}^{2}F_{1}^{2}Q_{2}^{2}σ_{4} − 3σ_{0}^{2}Q_{1}^{2}Q_{2}^{2}σ_{3}^{2}σ_{4} − 3σ_{0}F_{1}^{2}F_{2}Q_{2}σ_{3} − F_{2}^{3}Q_{1}σ_{3}^{2} + σ_{0}F_{1}Q_{1}^{2}Q_{2}σ_{1}σ_{3}σ_{4} − σ_{0}F_{1}^{2}Q_{2}^{2}σ_{2}^{2} + 3σ_{0}^{2}Q_{1}^{2}Q_{2}^{2}σ_{2}σ_{4}^{2} + 2F_{2}^{3}Q_{1}σ_{2}σ_{4} − 2σ_{0}F_{1}^{2}Q_{1}Q_{2}σ_{2}σ_{3} + F_{1}^{2}F_{2}Q_{2}σ_{1}σ_{2} − F_{2}^{4}σ_{4} − σ_{0}Q_{1}^{2}Q_{2}^{2}σ_{2}^{3}σ_{4} + 4σ_{0}F_{1}^{2}F_{2}Q_{1}σ_{4} − F_{1}^{2}F_{2}Q_{1}σ_{1}σ_{3} + 2σ_{0}^{2}F_{1}Q_{2}^{3}σ_{2}σ_{4} − σ_{0}F_{1}^{2}Q_{1}Q_{2}σ_{1}σ_{4} + 2σ_{0}F_{1}^{2}Q_{2}^{2}σ_{1}σ_{3} − σ_{0}^{2}F_{1}Q_{2}^{3}σ_{3}^{2} + 3σ_{0}Q_{1}^{2}Q_{2}^{2}σ_{1}σ_{2}σ_{3}σ_{4} + 2σ_{0}F_{1}^{3}Q_{2}σ_{2} − σ_{0}F_{2}Q_{1}^{2}Q_{2}σ_{2}σ_{3}σ_{4} + 3σ_{0}^{2}Q_{1}^{3}Q_{2}σ_{3}σ_{4}^{2} − F_{1}^{3}Q_{2}σ_{1}^{2} + σ_{0}F_{1}^{3}Q_{1}σ_{3} + 5σ_{0}F_{2}Q_{1}^{2}Q_{2}σ_{1}σ_{4}^{2} + 4σ_{0}F_{1}F_{2}^{2}Q_{2}σ_{4} + F_{1}^{3}F_{2}σ_{1} − σ_{0}F_{1}^{4} + F_{2}Q_{1}^{2}Q_{2}σ_{1}σ_{2}^{2}σ_{4} + σ_{0}F_{1}F_{2}Q_{2}^{2}σ_{2}σ_{3} − F_{1}F_{2}^{2}Q_{2}σ_{1}σ_{3} − 3σ_{0}Q_{1}^{2}Q_{2}^{2}σ_{1}^{2}σ_{4}^{2} − 3σ_{0}F_{1}F_{2}Q_{2}^{2}σ_{1}σ_{4} − 3σ_{0}Q_{1}^{3}Q_{2}σ_{1}σ_{2}σ_{4}^{2} − 4σ_{0}^{2}F_{1}Q_{1}^{2}Q_{2}σ_{4}^{2} + F_{1}F_{2}^{2}Q_{1}σ_{2}σ_{3} + 2σ_{0}F_{1}Q_{1}^{2}Q_{2}σ_{2}^{2}σ_{4} − σ_{0}F_{2}^{2}Q_{2}^{2}σ_{2}σ_{4} + σ_{0}^{2}F_{2}Q_{2}^{3}σ_{3}σ_{4} + F_{1}^{2}Q_{1}Q_{2}σ_{1}^{2}σ_{3} − 3F_{1}F_{2}^{2}Q_{1}σ_{1}σ_{4} − 4σ_{0}^{2}F_{2}Q_{1}Q_{2}^{2}σ_{4}^{2} + F_{1}F_{2}^{3}σ_{3} − 2F_{2}Q_{1}^{2}Q_{2}σ_{1}^{2}σ_{3}σ_{4} − σ_{0}F_{2}Q_{1}Q_{2}^{2}σ_{2}σ_{3}^{2} − F_{1}Q_{1}^{2}Q_{2}σ_{1}^{2}σ_{2}σ_{4} + 2σ_{0}F_{2}Q_{1}Q_{2}^{2}σ_{2}^{2}σ_{4} − 2σ_{0}F_{2}^{2}Q_{1}^{2}σ_{4}^{2} − F_{2}^{2}Q_{1}^{2}σ_{2}^{2}σ_{4} + 3σ_{0}F_{1}F_{2}Q_{1}Q_{2}σ_{3}^{2} + σ_{0}F_{2}Q_{1}Q_{2}^{2}σ_{1}σ_{3}σ_{4} − σ_{0}F_{2}^{2}Q_{1}Q_{2}σ_{3}σ_{4} − 4σ_{0}F_{1}F_{2}Q_{1}Q_{2}σ_{2}σ_{4} + 2F_{2}^{2}Q_{1}^{2}σ_{1}σ_{3}σ_{4} − σ_{0}F_{1}^{2}Q_{1}^{2}σ_{2}σ_{4} + Q_{1}^{3}Q_{2}σ_{1}^{3}σ_{4}^{2} − σ_{0}^{2}Q_{1}^{4}σ_{4}^{3} − σ_{0}^{3}Q_{2}^{4}σ_{4}^{2} − F_{1}F_{2}Q_{1}Q_{2}σ_{1}σ_{2}σ_{3} + 5σ_{0}^{2}F_{1}Q_{1}Q_{2}^{2}σ_{3}σ_{4} + σ_{0}F_{1}Q_{1}Q_{2}^{2}σ_{2}^{2}σ_{3} + σ_{0}F_{1}Q_{1}^{3}σ_{1}σ_{4}^{2} + 3F_{1}F_{2}Q_{1}Q_{2}σ_{1}^{2}σ_{4} + 2σ_{0}F_{2}Q_{1}^{3}σ_{2}σ_{4}^{2} − 2σ_{0}F_{1}Q_{1}Q_{2}^{2}σ_{1}σ_{3}^{2} − σ_{0}F_{1}Q_{1}Q_{2}^{2}σ_{1}σ_{2}σ_{4} − 3σ_{0}^{2}Q_{1}Q_{2}^{3}σ_{2}σ_{3}σ_{4} − 3σ_{0}F_{1}F_{2}Q_{1}^{2}σ_{3}σ_{4} + σ_{0}^{2}Q_{1}Q_{2}^{3}σ_{3}^{3} − F_{1}^{2}F_{2}^{2}σ_{2} + F_{1}F_{2}Q_{1}^{2}σ_{1}σ_{2}σ_{4} − F_{2}Q_{1}^{3}σ_{1}^{2}σ_{4}^{2} + 3σ_{0}^{2}Q_{1}Q_{2}^{3}σ_{1}σ_{4}^{2} + G^{2} = 0

Figure 1. The Syzygy

given by

ψ : \begin{matrix}H & ⟶ & D_{2} \\ x & ⟶ & (−F_{1}(x)/F_{2}(x), G(x)/F_{2}(x)^{2}) \end{matrix}

Now if D_{2} was a two-covering of an elliptic curve E, then the map above would correspond to a map ϕ_{4}, i.e. an extension of the two-covering to a four-covering, if we could show the following...

• The map ψ above has degree 4.

• Let P_{0} denote a point on D_{2} with zero y-coordinate, and let P_{1}, …, P_{4} denote the pre-images of P_{0} under ψ. If we choose P_{1} as a zero of the group law on H then P_{2}, P_{3}, P_{4} are the points of order two.

In other words if we consider D_{2} as an elliptic curve with base point P_{0} then the following diagram is commutative.

(D_{2}, P_{0}) \underrightarrow{[2]} (D_{2}, P_{0})
↕  ψ↗
H

The fact that ψ is a degree 4 map can be seen by considering a point (x, y, z) on D_{2}. Then the point x lies on the three quadric surfaces

Q_{1}(x) = Q_{2}(x) = zF_{1}(x) + xF_{2}(x) = 0.

By Bezout’s Theorem these intersect in eight points and the imposition of the condition G(x) = y determines a subset of four points.

Now the condition that the images of the four points P_{1}, …, P_{4} have zero y coordinate means that G(x) = 0. But this means that the four points lie on the union of four planes in ℙ^{3} (to see this consider Todd, [25][Page 249]). However as the images of the four points are equal the ratio of F_{1}(x) and F_{2}(x) is constant and so the four points all lie on the same plane. Now consider a plane which contains the tangent at P_{1} and which also passes through P_{i}, for 2 ≤ i ≤ 3. Then, if P_{i} is not a point of order two, such a plane intersects H in one other (distinct) point, (see our discussion on the group law above). But then it would be a plane which contained P_{1}, …, P_{4} and the tangent line at P_{1} which is impossible. Hence P_{i} is a point of order two.

4. The Descent Construction

We wish to parametrise the solutions to equation (1) over ℚ. By a change of variable we can assume our homogenous space is of the form

C : aY^{2} = G(X, Z),  (2)

where G(X, Z) is a binary quartic form with ℤ coefficients, with G(1, 0) = 1 and a ∈ ℚ^{∗} is the coefficient of x^{4} in f(x, z). We wish to determine (X, Z) up to multiplication by an element of ℚ^{∗} and so we can assume that (X, Z) ∈ ℤ^{2} \ {(0, 0)} and (X, Z) are coprime. Let A = ℚ[Θ] denote the algebra

ℚ[X]/(G(X, 1)) = L_{1} ⊕ … ⊕ L_{t},

where the L_{i} are number fields such that L_{i} = ℚ(θ_{i}) and G(θ_{i}, 1) = 0 and no two distinct pairs θ_{i}, θ_{j} are conjugate. We can hence assume, as G(X, Z) is irreducible or a product of two irreducible quadratic factors, that t = 1 or 2. Put (X −θ_{i}Z)O_{L_{i}} = 𝔞_{i}𝔟_{i}^{2}, where 𝔞_{i} is square free and ∏_{i=1}^{t} N_{L_{i}/ℚ}(𝔞_{i}) ∈ aℚ^{∗}^{2}.

Lemma 2. If 𝔭 is a prime ideal of L_{i} and 𝔭|𝔞_{i} then either 𝔭|a, or 𝔭|Δ(G), where Δ(G) is the discriminant of G(X, Z)

Proof. Suppose 𝔭 is a prime ideal of L_{i} such that 𝔭|𝔞 but 𝔭 does not divide a or Δ(G). Let L^{gal} denote the minimal galois closure of L_{1} ∪ … ∪ L_{t}. As 𝔭 does not divide Δ(G) we see that 𝔭 does not ramify in L^{gal}. Let 𝔮 denote a prime ideal of L^{gal} which divides 𝔭 then

ord_{𝔮}(X − θ_{i}Z) = ord_{𝔭}(X − θ_{i}Z) ≡ 1 (mod 2),

as 𝔞_{i} is square free. But

ord_{𝔮} (∏_{i=1}^{t} N_{L_{i}/ℚ}(X − θ_{i}Z)) = ord_{𝔮}G(X, Z) = ord_{𝔮}(aY^{2}) ≡ 0 (mod 2),

as 𝔮 does not divide a.

So there is a θ with G(θ, 1) = 0 such that θ ≠ θ_{i} and 𝔮|(X − θY). Then we find that 𝔮 divides (θ − θ_{i})X and (θ − θ_{i})Z. But as 𝔮 does not divide θ − θ_{i} we find that 𝔮|(X, Z). But this is true for all prime ideals 𝔮 of L^{gal} which divide which divide 𝔭, hence 𝔭|(X, Z). But this means that 𝔭 is the trivial ideal.

Let S_{i} denote the set of prime ideals in L_{i} which divide a or Δ(G). We let L_{i}(S_{i}, 2) denote the set of elements of L_{i} modulo squares such that if we add a square root of an element of L_{i}(S_{i}, 2) to L_{i} we obtain an extension unramified away from S_{i}. This finite set can be determined by the methods in [19]. Using the above Lemma we can then write

X − θ_{i}Z = ϵ_{i}γ_{i}^{2},  (3)

where ϵ_{i} ∈ L_{i}(S_{i}, 2) and γ_{i} ∈ L_{i}^{∗}. For each tuple (ϵ_{1}, …, ϵ_{t}) we reject those for which

∏_{i=1}^{t} N_{L_{i}/ℚ}(ϵ_{i}) ∉ aℚ^{∗}^{2}.

We can obviously assume that (ϵ_{1}, …, ϵ_{t}) is determined modulo an element of ℚ^{∗}. We have then a map

μ : \begin{matrix}C & ⟶ & A^{∗}/ℚ^{∗}A^{∗}^{2} \\ (X, Y, 1) & ⟶ & X − ΘZ (mod ℚ^{∗}A^{∗}^{2}) \end{matrix}

which should be familiar as the usual map one uses to perform 2-descents on a curve of the form (1), when f(x, z) is monic (see [6]).

We finally obtain a finite set of equations of the form (3), from each one of these sets of equations we shall derive the descendents. We now look at the two various cases corresponding to the factorization of G(X, Z). In all cases we obtain a new “homogenous space” as an intersection of two quadrics.

4.1. G(X, Z) is irreducible. For convenience we make the change of variable such that the coefficient of X^{3}Z in G(X, Z) is zero. We have the equation

X − θZ = ϵ(x_{1} + x_{2}θ + x_{3}θ^{2} + x_{4}θ^{3})^{2}

from which we obtain (on equating coefficients of θ^{j}) the four equations:

X = Q_{3}(x) , Z = Q_{4}(x) , 0 = Q_{1}(x) , 0 = Q_{2}(x),

Where Q_{i}(x) is a quadratic form in four variables. The last two equations give us our two quadrics.

Given the above change of variable, one can easily check that if F_{1}(x) and F_{2}(x) denote the corresponding covariants of Q_{1}(x) and Q_{2}(x) then a point x such that Q_{1}(x) = Q_{2}(x) = 0 satisfies the identities:

Q_{3}(x) ≡ F_{1}(x) , Q_{4}(x) ≡ −F_{2}(x).

And in addition

det(Q_{1}(x)t_{1} + Q_{2}(x)t_{2}) = aG(t_{1}, t_{2}).

Hence in this case the above construction does indeed give rise to a 4-descent extending the 2-descent (1).

4.2. G(X, Z) is a product of two irreducible quadratics. Here we find the equations

X − θ_{1}Z = ϵ_{1}(x_{1} + θ_{1}x_{2})^{2},
X − θ_{2}Z = ϵ_{2}(x_{3} + θ_{2}x_{4})^{2}.

Again equating coefficients of θ_{1} we find the X (resp. Z) in terms of two different quadratic forms. Then equating coefficients of θ_{2} we find two quadrics Q_{1}(x) and Q_{2}(x) which must be equal to zero. Again we find

det(Q_{1}(x)t_{1} + Q_{2}(x)t_{2}) = aG(t_{1}, t_{2}).

But this time for a point x satisfying Q_{1}(x) = Q_{2}(x) = 0 we find that

X(x) ≡ c_{1}F_{1}(x) + c_{2}F_{2}(x) , Z(x) ≡ c_{3}F_{1}(x) + c_{4}F_{2}(x)

for some constants c_{i} depending only on the coefficients of G(t_{1}, t_{2}). However we then notice that

G(c_{1}F_{1}(x) + c_{2}F_{2}(x), c_{3}F_{1}(x) + c_{4}F_{2}(x)) = G(F_{1}(x), −F_{2}(x))/δ^{2}

where δ is also some constant depending only on the coefficients of G(t_{1}, t_{2}). Hence in this case we also find that the above construction does produce a 4-descent extending the 2-descent (1).

We now discard every four descent which is not locally soluble everywhere. To do this we need to test whether the intersection of two quadrics is soluble in every completion of ℚ. However we note the following result which can often speed up this search, given that the methods below for local-solubility are quite cumbersome. We shall denote by A_{p} the obvious localisation of the algebra A.

Lemma 3. Suppose we know that equation (2) has three solutions over ℚ_{p}, say P_{1}, P_{2} and P_{3}. (This may be because we know that some element in L_{1}(S_{1}, 2) × … × L_{t}(S_{t}, 2) gives rise to an intersection of two quadrics that we know to be soluble in ℚ_{p} by the methods below). Suppose the curve

Y = b_{2}X^{2} + b_{1}XZ + b_{0}Z^{2}

intersects (2) at the three points P_{1}, P_{2}, P_{3}. Then the fourth point of intersection, P_{4}, is also defined over ℚ_{p} and we have

∏_{i=1}^{4} μ(P_{i}) ≡ 1 (mod A_{p}^{∗}/Q_{p}^{∗}A_{p}^{∗}^{2}).

Proof. That P_{4} is also defined over ℚ_{p} is obvious. For the other part we set X = Θ in both sides of the identity

a(b_{2}X^{2} + b_{1}X + b_{0})^{2} − G(X, 1) = l(X − x(P_{1})) … (X − x(P_{4}))

5. Local Solubility Of An Intersection Of Two Quadrics

We first consider the non-archimedean case, then we shall go onto the archimedean case.

5.1. The Non-Archimedean Case. We let v denote the non-archimedean valuation of ℚ we shall be considering, p the corresponding prime number and ℙ_{p} = {(x : y) : x, y ∈ ℤ_{p} and min(v(x), v(y)) = 0}.

Let A, B be 4×4 symmetric matrices with entries in ℚ such that det(XA− Y B) has distinct roots. We shall give an algorithm for determining the solubility of

H : \{ \begin{matrix}x^{t}Ax = 0 \\ x^{t}Bx = 0 \end{matrix}

over ℚ_{p}. We can assume without loss of generality that A and B have entries in ℤ and hence that ∂(A, B) (the discriminant of det(XA − Y B)) is in ℤ.

The algorithm we will give, relies on searching for points on H modulo p and then attempting to lift the points found to points modulo powers of p until it is certain that they will lift to points defined over ℤ_{p}^{4}. We need two pieces of information:

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

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

Theorem 4. Suppose A, B are 4 × 4 symmetric matrices with entries in ℤ_{p} such that ∂(A, B) ≠ 0. We have

1. If v(2∂(A, B)) = 0 then H has a non-trivial solution over ℤ_{p}.

2. Suppose that there exists x_{0} ∈ ℤ_{p}^{4}\pℤ_{p}^{4} such that

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

and there is no pair (λ : μ) ∈ ℙ_{p} such that 2(λAx_{0} − μBx_{0}) ≡ 0 (mod p^{δ+1}). Then there exists x ∈ ℤ_{p}^{4} such that x ≡ x_{0} (mod p^{δ+1}) and x is a non-trivial point on H.

Proof. For the first part it is sufficient to note that if v(2∂(A, B)) = 0 then x^{t}\overline{A}x ≡ x^{t}\overline{B}x ≡ 0 (mod p) has genus 1 and it follows then that there is a non-trivial solution to H. The second part is a special case of Theorem 5.21 on page 64 of [14].

Thus it is clear that to test local solubility at the non-archimedean places, it is sufficient to check solubility over ℚ_{p} only for those p for which v(2∂(A, B)) ≠ 0. For any such p, we can do this using the above Theorem in a standard way, c.f. the book [11] where a similar algorithm is given for the case y^{2} = f(x, 1) That such a process terminates is guaranteed by the following Lemma.

Lemma 5. Suppose that there exists x_{1} ∈ ℤ_{p}^{4} such that

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

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

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

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

Then we have that v(∂(C, D)) = v(∂(A, B)). Now note that

C ≡ ( \begin{matrix}0 & 0 \\ 0 & C_{1} \end{matrix} ) (mod p^{γ})

where C_{1} is a 3 × 3 matrix with entries in ℤ_{p}. Also

D ≡ ( \begin{matrix}0 & v^{t} \\ v & D_{1} \end{matrix} ) (mod p^{γ})

where D_{1} is a 3 × 3 matrix with entries in ℤ_{p}, and v ∈ ℤ_{p}^{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 p^{γ}. By considering the formula for the discriminant of G in terms of its coefficients, we see that p^{γ}|∂(C, D). This completes the proof.

5.2. The Archimedean Case. Let A, B be n × n symmetric matrices with entries in ℤ. Suppose further that F (X, Y) = det(XA − Y B) is nonzero and does not have any repeated roots. We want to determine the local solubility of

H : \{ \begin{matrix}x^{t}Ax = 0 \\ x^{t}Bx = 0 \end{matrix}

over ℝ. 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 polynomial of degree n with distinct roots.

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

Lemma 6. (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 [24].

We are now ready for a simplification:

Lemma 7. Suppose that F (λ) = det(A − λB) has a non-real root. Then H has a non-trivial solution over ℝ.

Proof. This is standard, see for example [15][p 263-264].

By Lemma 7, 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 8. 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 ℝ^{n} such that

(A − λ_{i}B)x_{i} = 0.  (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} )  (5)

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

Proof. This is straightforward.

Lemma 9. Under the hypotheses and notation of Lemma 8, H has a nontrivial 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, 8.

¿From this we can then deduce.

Lemma 10. Under the hypotheses and notation of Lemma 8, H 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 H has no non-trivial real solution. By Lemma 10 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)

as in Lemma 8. Recall that the αs and βs 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 11. Under the notation and hypotheses of Lemma 8, H 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 10.

This allows us to test for the real solubility of H.

6. A Special Case

In this section we consider the problem of determining the local solubility at non-archimedean primes of an intersection of two quadric surfaces. As before we assume that these two surfaces are given by two symmetric 4 × 4 matrices, A and B. Using the method of the previous section can be very inefficient in terms of computing time. However in this section we show how one can find a faster method in the case where det(AX + BY) has a linear factor over ℚ_{p}. We shall assume for convenience that p ≠ 2. So for the rest of this section we assume that det(AX + BY) has a linear factor over ℚ_{p}. Now by a linear change of variable, defined over ℚ_{p}, and taking appropriate linear combinations of Q_{1}(x) and Q_{2}(x), we can assume that Q_{1}(x) = x^{t}Ax contains no x_{4} terms and Q_{2}(x) = x^{t}Bx contains only one term involving x_{4} and this is of the form x_{4}^{2}.

In this situation Q_{1}(x) determines a curve of genus zero. By another change of variable defined over ℚ_{p}we may assume that Q_{1}(x) is of the form

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

with a, b, c ∈ ℤ_{p}, and v(a) = v(b) = 0 and v(c) = 0 or 1. If v(c) = 1, then −ab^{−1} must be a square in ℤ_{p}, otherwise (7) does not have a solution over ℚ_{p} and we may stop. So if α^{2} = −ab^{−1} then (1 , α , 0) is a non-trivial solution to (7), and we are finished. If v(c) = 0, then heuristically, for 50% of pairs (x, y), −c^{−1}(ax^{2} + by^{2}) is a square in ℤ_{p}. Thus we expect to find a solution to ℚ_{1}(x) = 0 in O(1) steps, if Q_{1}(x) is soluble. If Q_{1}(x) is not soluble then certainly its intersection with Q_{2}(x) = 0 will not be either.

Given one solution to Q_{1}(x) = 0 we can parametrise all others in the form

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

where q_{i}(X_{1}, X_{2}) are binary quadratic forms which can be explicitly determined. Suppose that z_{i} = αq_{i}(X_{1}, X_{2}) for some α ∈ ℚ_{p}^{∗}. Substituting this into z^{t}Bz = 0 we obtain an equation of the form x_{4}^{2} = g(X_{1}, X_{2}), where g(X_{1}, X_{2}) is a binary quartic form with coefficients in ℤ_{p}.

So we are reduced to finding whether

Y^{2} = g(X)

has any solutions in ℚ_{p} (including any at infinity) where g(X) ∈ ℤ_{p}[X] is of degree 4 and has non-zero discriminant. First we note that this curve has a pair of points at infinity if and only if the leading coefficient of g is square in ℤ_{p}.

There are standard algorithms to solve this problem in the literature, see for instance [11] and [1]. However these methods have polynomial time complexity in p. In this section we give an algorithm with probablistic polynomial time complexity in log p based on root extraction in finite fields. The method is deterministic polynomial time in log p assuming the Generalised Riemann Hypothesis, [9][pages 31-34 and 37].

If f is a polynomial in ℤ_{p}[X], we write \overline{f} for the image of f under the map ℤ_{p}[X] → 𝔽_{p}[X] induced by the natural map ℤ_{p} → 𝔽_{p}. 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. We shall make repeated use of the following Lemma.

Lemma 12. Suppose the curve

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

is given with f(X) ∈ ℤ_{p}[X], a ∈ ℤ_{p}. Let x_{1}, y_{1} ∈ ℤ_{p} such that ay_{1}^{2} ≡ f(x_{1}) (mod p). Then there exists x, y ∈ ℤ_{p} with x ≡ x_{1}, y ≡ y_{1} (mod p), such that ay^{2} = f(x) except possibly when ay_{1} ≡ f′(x_{1}) ≡ 0 (mod p).

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 p), and to the polynomial

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

in the case ay_{1} ≢ 0 (mod p).

Corollary 1. Suppose f(X) ∈ ℤ_{p}[X] such that \overline{f} ≢ 0 (mod p), and deg \overline{f} ≤ 4. Then pY^{2} = f(X) has a solution in ℚ_{p} if \overline{f} has a root defined over 𝔽_{p} which is not a repeated root.

Using the above Lemma, and its corollary, we shall give an algorithm to determine in probabilistic polynomial time whether

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

has a solution in ℚ_{p}. Before giving the complete algorithm we deduce two Lemma’s from Lemma 12.

Lemma 13. Suppose that f(X) ∈ ℤ_{p}[X] such that deg f = 4 and deg \overline{f} = 3 or 4. Suppose \overline{f}(X) has no repeated factors. Then equation (10) has solutions over ℚ_{p}.

Proof. Under the hypotheses of the Lemma, the equation Y^{2} = \overline{f}(X) is a curve of genus 1 defined over 𝔽_{p}. It follows (see [8][page 119]) that it has at least one point defined over 𝔽_{p}. Again, since \overline{f} does not have repeated factors, we can use Lemma 12, with a = 1, to show that this solution lifts to one defined over ℚ_{p}.

Lemma 14. Suppose f(X) ∈ ℤ_{p}[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 equation (10) has solutions in ℚ_{p}.

Proof. The curve Y^{2} = \overline{h}(X) has genus 0, and hence has p+1 points defined over 𝔽_{p}. 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 p ≥ 5 then Y^{2} = \overline{h}(X) has at least one point (x_{1}, y_{1}) ∈ 𝔽_{p}^{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 12. For the case p = 3 the Lemma can be established by a lengthy but straightforward case-by-case check which we omit.

The following corollary easily follows from the above Lemmas.

Corollary 2. Suppose \overline{f} ≢ 0. If equation (10) has no points over ℚ_{p} then \overline{f} ≡ α\overline{g}^{2} where \overline{g}(X) ∈ 𝔽_{p}[X] and α ∈ 𝔽_{p}^{∗}\𝔽_{p}^{∗}^{2}.

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

Using these results the following algorithm is immediate.

Algorithm 1. Testing

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

for solubility over ℚ_{p}, where f(X) ∈ ℤ_{p}[X], deg f = 4, and the discriminant of f is non-zero.

Step I

• If \overline{f} ≡ 0 (mod p), then go to Step II.

• Check if \overline{f} = \overline{a} \overline{g}^{2} for some \overline{g} ∈ 𝔽_{p}[X], and \overline{a} ∈ 𝔽_{p}. If this is not the case, or if \overline{a} ∈ 𝔽_{p}^{∗}^{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} ∉ 𝔽_{p}^{∗}^{2}. So any solution (X_{0}, Y_{0}) ∈ ℤ_{p}^{2} to (11) must satisfy Y_{0} ≡ 0 and \overline{g}(X_{0}) ≡ 0. Now \overline{g} has at most two solutions \overline{ϵ_{1}}, \overline{ϵ_{2}} (mod p); if \overline{g} has no solutions in 𝔽_{p} then (11) has no solutions in ℤ_{p} and we can stop.

• Hence

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

where Y_{1}, X_{1} ∈ ℤ_{p}. Choose a ∈ ℤ_{p} and g ∈ ℤ_{p}[X] such that the images of a and g under ℤ_{p} → 𝔽_{p} are \overline{a} and \overline{g}. Then f = ag^{2} + ph where h has coefficients in ℤ_{p}. Since p^{2}|Y_{0}^{2} = f(X_{0}) and p|g(X_{0}), we get that p|h(X_{0}). Hence if neither of ϵ_{1} and ϵ_{2} is a root of \overline{h} then (11) is not soluble and we can stop.

• If say ϵ_{i} is a root of \overline{h} then p divides the trailing coefficient of h(pX+ϵ_{i}). So we will get at most 2 equations of the form

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

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

Step II

• Here f is divisible by p. If f is divisible by p^{2} then we can replace f by \frac{1}{p^{2}} f and go to Step I.

• So suppose that f_{1} = \frac{1}{p}f ≢ 0 (mod p). We see that we want to deter-

mine if

pY_{1}^{2} = f_{1}(X)

has solutions in ℤ_{p}. If f_{1} has no roots in 𝔽_{p} then (11) is not soluble and we can stop.

• If f_{1} has a root which is not a repeated root then (11) 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}{p}f_{1}(pX_{1} + ϵ_{i})

is soluble, and \frac{1}{p}f_{1}(pX_{1} + ϵ_{i}) ∈ ℤ_{p}[X]. So we use Step I again.

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

Proof. It is clear that after r steps, we may write down a Z ∈ ℤ_{p}, such that f(Z) ≡ 0 (mod p^{2(r+1)}). By [7][page 52], f has a root in ℤ_{p}. This immediately implies that (11) has a solution defined over ℚ_{p}.

7. Examples

We give an example which shows how you can prove the 2-primary part of the Tate-Shafarevich group is a given number. We look at the curve

Y^{2} + Y = X^{3} − X^{2} − 929X − 10595

This has conductor 571, and conjectured rank equal to 0 with no two torsion. The Birch-Swinnerton-Dyer conjectures imply that the Tate-Shafarevich group has order 4.

Applying mwrank we find that the three rogue homogenous spaces in the 2-Selmer group are given by

Y^{2} = −229X^{4} − 135X^{3} − 238X^{2} − 84X − 8,
Y^{2} = −108X^{4} − 4X^{3} − 76X^{2} − 112X − 31,
Y^{2} = −4X^{4} + 4X^{3} + 92X^{2} − 104X − 727.

Note if you start with an elliptic curve with no two-torsion then the first descents will always involve irreducible quartics.

The first of these is isomorphic to

−229y^{2} = x^{4} − 135x^{3}z + 54502x^{2}z^{2} − 4405044xz^{3} + 96071912z^{4}.

Working in the field ℚ(θ), where θ^{4} − 2θ^{3} + 2θ^{2} − 4θ − 1 = 0, we find that there are 8 possible descendents. All of these are however insoluble over ℚ_{571}.

Similarly the second equation is isomorphic to

−3y^{2} = x^{4} − 4x^{3} + 8208x^{2} − 1306368x + 39051072.

Working in the field Q(ϕ) where ϕ^{4} − 2ϕ^{2} − 2ϕ − 3 = 0, we find that there are at most 8 descendents. Again we find that they are all insoluble over ℚ_{571}.

The last equation is isomorphic to

−y^{2} = x^{4} + 4x^{3} − 368x^{2} − 1664x + 46528,

and working in the relevant quartic number field we immediately see (by the norm condition) that this has no descendents and hence has no rational points. Hence the Tate-Shafarevich group has 2 primary part of order 4.

References

[1] B.J. Birch and H.P.F. Swinnerton-Dyer. Notes on elliptic curves. I. J. Reine Angew. Math., Vol 212 , pp 7–25, 1963.

[2] B.J. Birch and H.P.F. Swinnerton-Dyer. Notes on elliptic curves. II. J. Reine Angew. Math., Vol 218 , pp 79–108, 1965.

[3] A. Bremner. On the equation y^{2} = x(x^{2} + p). In Number Theory and Applications, Ed. R.A. Mollin, pages 3–23. Kluwer, Dordrecht, 1989.

[4] A. Bremner and J.W.S. Cassels. On the equation y^{2} = x(x^{2} + p). Math. Comp., Vol 42 , pp 257–264, 1984.

[5] J.W.S. Cassels. Diophantine equations with special reference to elliptic curves. J. of LMS, Vol 41 , pp 193–291, 1966.

[6] J.W.S. Cassels. The Mordell-Weil group of curves of genus 2. In Arithmetic and Geometry Papers Dedicated to I.R.Shafarevich on the Occasion of his Sixtieth Birthday, Vol. 1, pages 29–60. Birkha̋user, 1983.

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

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

[9] H. Cohen. A Course In Computational Algebraic Number Theory. Springer-Verlag, Berlin, 1993.

[10] I. Connell. Addendum to a paper of Harada and Lang. J. of Algebra, Vol 145 , pp 463–467, 1992.

[11] J.E. Cremona. Algorithms For Modular Elliptic Curves. Cambridge University Press, 1992.

[12] J. Gebel, A. Pethő, and H.G. Zimmer. Computing integral points on elliptic curves. Acta. Arith., Vol 68 , pp 171–192, 1994.

[13] J. Gebel and H.G. Zimmer. Computing the Mordell-Weil group of an elliptic curve over ℚ. In Elliptic Curves and Related Topics, Ed. H. Kisilevsky and M. Ram. Murty. CRM Proceedings and Lecture Notes Volume 4, AMS ., 1994.

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

[15] W.H. Greub. Linear Algebra. Springer-Verlag, 1967.

[16] M.J. Razar. A relation between the two component of the Tate-S̆afarevič group and L(1) for certain elliptic curves. Am. J. of Math, Vol 96 , pp 127–144, 1974.

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

[18] S. Siksek. Infinite descent on elliptic curves. To Appear Rocky Mountain Journal, 1996.

[19] S. Siksek and N.P. Smart. On the complexity of computing the 2-Selmer group of an elliptic curve. Preprint, 1995.

[20] J.H. Silverman. The Arithmetic Of Elliptic Curves. Springer-Verlag, 1986.

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

[22] N.P. Smart and N.M. Stephens. Integral points on elliptic curves over number fields. To Appear Proc. Camb. Phil. Soc., 1996.

[23] R.J. Stroeker and N. Tzanakis. Solving elliptic diophantine equations by estimating linear forms in elliptic logarithms. Acta. Arith., Vol 67 , pp 177–196, 1994.

[24] H.P.F. Swinnerton-Dyer. Rational zeros of two quadratic forms. Acta. Arith., Vol 6 , 1964.

[25] J.A. Todd. Projective and Analytical Geometry. Pitman, 1947.

[26] A. Weil. Number Theory. An approach through history. Birkhauser, 1984.

Institute Of Maths and Stats., University of Kent at Canterbury, Canterbury, Kent, England.

  E-mail address: J.R.Merriman@ukc.ac.uk , S.Siksek@ukc.ac.uk , N.P.Smart@ukc.ac.uk