Higher Descents on Elliptic Curves

J. E. Cremona

August 1997

1 Introduction

Let E be an elliptic curve defined over ℚ. Our overall goal is to find explicitly the Mordell-Weil group E(ℚ), its rank r and a ℤ-basis. In place of the latter we are often satisfied with a basis for E(ℚ)/mE(ℚ) for some integer m ≥ 2; computing this quotient is usually known as “doing an m-descent” on E.

In this talk we will first give some generalities on descents, before specializing to the well-known case of descent via 2-isogeny. This will be called the first descent. While often conclusive with no further work, there are curves for which this first descent proves inconclusive, in the sense that we obtain homogeneous spaces (defined below) for which we cannot decide whether they have rational points. Higher descents attempt to settle this question, and we will go on to describe in some detail how to carry out a second descent.

Finally we give a numerical example to illustrate the method.

The terminology of descents is by now classical, going back to a series of papers by Cassels (summarized in [3]), and Birch and Swinnerton-Dyer ([1] and [2]). The second descent which we will describe for general curves was used in [2] to study curves of the form y^{2} = x^{3} − Dx. It has been implemented simultaneously (but independently) by the author in C++ as part of his program mwrank, and also by D. Rusin and I. Connell in Maple, as part of Connell’s package apecs.

A longer version of this article is in preparation [6].

2 The First Descent

Since E(ℚ) is a finitely-generated abelian group, we can divide our task into the following subtasks: finding the (finite) torsion subgroup, finding the rank r, usually by finding r independent points in E(ℚ), by finding a basis for E(ℚ)/mE(ℚ) for some integer m ≥ 2, and finally finding a ℤ-basis for E(ℚ) itself. The first of these steps is easy (see [5, Section 3.5]); here we will not be concerned with the last step, and wish to determine E(ℚ)/mE(ℚ) for some m. The only case worked out in detail and implemented in practice for general elliptic curves is the case m = 2. Hence for the purposes of this talk our more modest goal is to compute E(ℚ)/2E(ℚ) explicitly, thus obtaining both the rank r and r independent rational points on E which generate a subgroup of finite index in the Mordell-Weil group E(ℚ). This process is known as “doing a 2-descent”.

2.1 Descent via isogeny

Let φ: E′ ⟶ E be a nonzero isogeny of degree m between two elliptic curves E′ and E, with both curves and the isogeny defined over ℚ. “Doing a φ-descent” on E means determining the quotient E(ℚ)/φ(E′(ℚ)). We have the exact sequence

0 ⟶ E′[φ] ↪ E′ ⟶^{φ} E ⟶ 0,

where E′[φ] denotes the kernel of φ, which is finite of order m. Applying G_{ℚ}- cohomology, where G_{ℚ} = Gal(\overline{ℚ}/ℚ), we obtain the injection

0 ⟶ E(ℚ)/φ(E′(ℚ)) ⟶^{δ} H^{1}(G_{ℚ}, E′[φ]).  (1)

For this to be useful computationally, we must represent elements of the group H^{1}(G_{ℚ}, E′[φ]) in a concrete way, and determine which come from rational points on E. Each element gives rise to a so-called φ-covering of E: this consists of a curve C, isomorphic to E′ over \overline{ℚ} (via θ, say), and a map ξ: C ⟶ E defined over ℚ and of degree m such that the following diagram commutes:

[figure: E′; E; φ; C; θ; ξ]  (2)

For each such φ-covering such that C(ℚ) ≠ ∅, the image of C(ℚ) under ξ is a complete coset of φ(E′(ℚ)) in E(ℚ). So if we can find all such φ-coverings explicitly and determine which have rational points, we will be able to compute the order of E(ℚ)/φ(E′(ℚ)). Repeating the process with the dual isogeny φ′: E ⟶ E′, we can determine the order of E′(ℚ)/φ′(E(ℚ)), and hence determine the rank of E(ℚ). (See [8, Chapter X, Remark 4.7] for details.)

The covering curves C are also known as homogeneous spaces, since they can be given the structure of principal homogeneous spaces for E, via (2). The φ-Selmer group S^{(φ)}(E′/ℚ) is the subgroup of H^{1}(G_{ℚ}, E′[φ]) consisting of elements represented by homogeneous spaces C which have points everywhere locally, i.e. for which C(ℚ_{p}) ≠ ∅ for all primes p (including ℚ_{∞} = ℝ). This group is finite and effectively computable (for suitable φ), and contains E(ℚ)/φ(E′(ℚ)), giving the exact sequence

0 ⟶ E(ℚ)/φ(E′(ℚ)) ↪ S^{(φ)}(E′/ℚ) ⟶ � (E′/ℚ)[φ] ⟶ 0

where � (E′/ℚ) is the Tate-Shafarevich group of E′ over ℚ.

Theoretically, then, it is the possible existence of non-trivial elements of � (E′/ℚ) which provides the obstacle to the φ-descent, since if such elements exist then we will encounter homogeneous spaces which are everywhere locally soluble (ELS) but which contain no global rational point. However, an obstacle which can also arise in practice is that some homogeneous space which does possess rational points may not have any small points (in the sense that the naive or Weil height of the coordinates is small), so that we may be unable to find rational points even when they exist.

Performing a second descent can help circumvent both these obstacles, either by producing large rational points as the images of small points on further curves, which we call descendants of C, or by proving that no such descendants exist. We give some explicit examples of this below, together with an example where we find a further obstacle, this time to the second descent: C may have ELS descendants on none of which are we able to find rational points. In such a case, a third descent would be necessary, but it is not clear how to do this in general.

One can also use φ-coverings to find rational points on E, given explicit equations for C and ξ. Since ξ has degree m ≥ 2, rational points on C will have smaller height than rational points on E itself, and so should be easier to find. It might appear, then, that it would be best to use an isogeny φ of large degree; however, the only isogenies for which a well worked out theory exists (in a form suitable for implementation for general curves) are the multiplication by 2 map (denoted [2]), of degree 4, and 2-isogenies (of degree 2).

Taking φ = [2] is a practical possibility for all curves. In this case, the curves C have equations for the form y^{2} = g(x) where g(x) ∈ ℤ[x] is a polynomial of degree 4. There are efficient procedures for finding all such 2-coverings C, though this is time-consuming when the discriminant Δ of E is large. See [5, Section 3.6] for details of this 2-descent process, which is implemented in our program mrank. A second descent then involves considering 4-coverings. The theory of these is currently under development: see [9] for a recent account, and [4] for a method of determining whether a given 2-descent has descendants.

When E has a rational point of order 2, there is a 2-isogeny defined over ℚ which we may use to do a descent via 2-isogeny. Now the second descent curves are 2-coverings, which we can determine explicitly.

2.2 Descent via 2-isogeny

Let E be an elliptic curve defined over ℚ with a rational point of order 2. Then there is an isogenous curve E′, also defined over ℚ, and dual 2-isogenies φ: E′ ⟶ E and φ′: E ⟶ E′, defined over ℚ, and we can use descent to determine both E(ℚ)/φ(E′(ℚ)) and E′(ℚ)/φ′(E(ℚ)), and hence E(ℚ)/2E(ℚ). Explicitly, we can choose coordinates so that E and E′ have equations of the form

E : y^{2} = x(x^{2} + cx + d)  (3)
E′ : y^{2} = x(x^{2} + c′x + d′)  (4)

where c, d, c′, d′ are integers related by c′ = −2c, d′ = c^{2} − 4d, and dd′ ≠ 0. The kernels of φ and φ′ are generated by the points (0, 0) on E′ and E respectively. The connecting map δ in (1) now maps E(ℚ)/φ(E′(ℚ)) to

H^{1}(G_{ℚ}, E′[φ]) = Hom(G_{ℚ}, {±1}) ≃ ℚ^{∗}/(ℚ^{∗})^{2},

and is given by mapping P = (x, y) ∈ E(ℚ) to x (mod (ℚ^{∗})^{2}) (if x ≠ 0) and (0, 0) to d (mod (ℚ^{∗})^{2}). Moreover, the image is contained in the finite subgroup of ℚ^{∗}/(ℚ^{∗})^{2} generated by the divisors of d. For each factorization d = d_{1}d_{2} with d_{1}, d_{2} ∈ ℤ one has the homogeneous space

C_{d_{1}} : v^{2} = d_{1}u^{4} + cu^{2} + d_{2},  (5)

which is a φ-covering of E with associated map ξ: C_{d_{1}} ⟶ E given by ξ((u, v)) = (d_{1}u^{2}, d_{1}uv).

Hence the algorithm Descent via 2-isogeny may be summarized as follows, given a curve with a rational point of order 2:

1. Transform the equation of the given curve into the form (3), mapping the given point of order 2 to (0, 0);

2. For each square-free divisor d_{1} of d, determine whether C_{d_{1}} has rational points;

3. The points ξ(P) for P ∈ C_{d_{1}} generate E(ℚ)/φ(E′(ℚ));

4. Repeat with E′ to find E′(ℚ)/φ(E(ℚ)), and so determine E(ℚ)/2E(ℚ).

In step 2, we will first determine the subgroup of square-free divisors d_{1} of d such that C_{d_{1}} is ELS (hence determining the Selmer group S^{(φ)}(E′/ℚ)), and then proceed to search for rational points on these C_{d_{1}}, remembering that those which have rational points again form a subgroup. If we fail to find a rational point on some ELS curve C_{d_{1}}, there are two possibilities:

either C_{d_{1}} has rational points, but they are too large to have been found in the search;

or C_{d_{1}} has no rational points.

To distinguish between these, we now carry out the second descent.

3 The Second Descent

3.1 Theoretical background

We continue with the notation of the previous section. Given a φ-covering C of the elliptic curve E as in (2), we attempt to extend it to a 2-covering D so that we have a larger commutative diagram

[figure: D; C; η; E; E′; φ′; E; φ; ξ]  (6)

Both vertical maps are isomorphism defined over \overline{ℚ}; the other maps are all of degree 2 and defined over ℚ. In general there will be several inequivalent ways of doing this for a given C, but the number is finite. We call the homogeneous spaces D descendants of C. If one succeeds in finding a single rational point on just one descendant, then the image of this point under η will give the desired point on C, and hence (via ξ) a rational point on E itself. In principal, finding points on the descendants should be easier than on the first descent curves, since they will have smaller height, approximately by a factor of 2 (see examples in section 4 below).

On the other hand, it may happen that an ELS first descent curve C may have no ELS descendants. In this case, C certainly has no rational points; it represents an element of the Selmer group S^{(φ)}(E′/ℚ) which is not the image of an element of S^{(2)}(E/ℚ), and so represents a non-trivial element of � (E′/ℚ).

The situation is illustrated by the following commutative diagram:

[figure: 0; 0; 0; 0; 0; 0; 0; 0; K; K; δ; S^{(φ′)}(E/ℚ); S^{(2)}(E/ℚ); E′(ℚ)/φ′(E(ℚ)); E(ℚ)/2E(ℚ); φ; δ; S^{(φ)}(E′/ℚ); E(ℚ)/φ(E′(ℚ)); δ; 0; 0; � (E/ℚ)[φ′]; � (E/ℚ)[2]; � (E′/ℚ)[φ]; φ′; 0; 0; 0; 0; φ′]

In this diagram, the group K has order 2, unless d′ is a square in which case it is trivial. The ELS first descent curves C represent elements of S^{(φ)}(E′/ℚ), and their ELS descendants (if they exist) represent their preimages in S^{(2)}(E/ℚ). Of course it is still possible to have descendants which are ELS but with no rational point; this will happen if C represents an element of � (E′/ℚ)[φ] which is the image under φ′ of an element of � (E/ℚ)[2]. So the obstruction has been reduced from the group � (E′/ℚ)[φ] to its subgroup φ′(� (E/ℚ)[2]). If ELS descendants do exist, they form a coset of S^{(φ′)}(E/ℚ)/K in S^{(2)}(E/ℚ), so are parametrized by the first descents on the isogenous curve E′; this will be made explicit below.

This is a sketch of the theory behind the second descent algorithm. Now we explain how to carry out the second descent in practice.

3.2 The second descent in practice

Our starting point is a curve C given by an (affine) equation of the form (5), where d_{1}, c, d_{2} ∈ ℤ, d = d_{1}d_{2} ≠ 0, d′ = c^{2} − 4d ≠ 0, and we desire either to find a rational point on C or show that no such point exists. We may assume that d_{1} is non-square (otherwise C represents the trivial class) so that C has no rational points at infinity, and we seek a rational solution (u, v) to (5). We also assume that C is ELS, so that (5) has real solutions and p-adic solutions for all primes p.

3.2.1 Step 1: solving the conic

Let C_{0} be the curve

C_{0} : Y^{2} = d_{1}X^{2} + cXZ + d_{2}Z^{2},  (7)

which is a conic (curve of genus 0). There is an obvious map C ⟶ C_{0}, and rational points on C correspond to rational points on C_{0} such that X/Z is a square. Since C is ELS, so is C_{0}, and hence by the Hasse principle, C_{0} has a rational point P_{0} = (X_{0} : Y_{0} : Z_{0}) ∈ ℙ^{2}(ℚ). Our first step is to find such a point P_{0}, so we need as a sub-algorithm an efficient way of solving an equation such as (7).

3.2.2 Step 2: parametrizing the conic

Given one solution P_{0} of (7) it is simple to parametrize all solutions:

X = q_{1}(α, β), Y = q_{2}(α, β), Z = q_{3}(α, β)  (8)

where the q_{i} are quadratic polynomials with integer coefficients, which determine a birational map.

θ: ℙ^{1}(ℚ) ⟶ C_{0}(ℚ)
(α : β) ↦ (q_{1}(α, β) : q_{2}(α, β) : q_{3}(α, β)).

It will be important to keep this parametrization as simple as possible; we can arrange that q_{1} and q_{3} have discriminants 16d_{2} and 16d_{1} respectively, with resultant Res_{u}(q_{1}(u, 1), q_{3}(u, 1)) = 16d′, all independent of P_{0}.

3.2.3 Step 3: parametrizing the set of descendants

For θ(α, β) to give a point in C(ℚ) and not just on C_{0}(ℚ), we require

\frac{X}{Z} = \frac{q_{1}(α, β)}{q_{3}(α, β)} = square.

Hence we require a solution in integers α, β, s, t to the equations

\begin{aligned}q_{1}(α, β) & = d_{3}s^{2} & (9) \\ q_{3}(α, β) & = d_{3}t^{2} & (10) \end{aligned}

where d_{3} is a square-free divisor of the resultant 16d′. Each of the finite number of possible d_{3} for which the equations (9), (10) are soluble (separately) will give rise to a descendant curve D. The following steps are now carried out for each such d_{3}.

Note that these d_{3}, which form a group H_{0} modulo squares, are precisely the integers which parametrize the first descent curves C′_{d_{3}} for the curve E′. Assuming that we have already carried out the first descent on E′, we will have already identified a subgroup H_{1} of H_{0} consisting of those d_{3} for which C′_{d_{3}} is ELS (so H_{1} is isomorphic to the Selmer group S^{(φ′)}(E/ℚ)). The set of values of d_{3} which give ELS descendants of our first descent curve C is either empty, or one complete coset of H_{1} in H_{0}. We can use this to make the algorithm more efficient, as in looking for descendants, we do not need to test all d_{3} ∈ H_{0}, but only one in each H_{1}-coset. If none of the cosets gives rise to an ELS descendant (see the later steps for how to determine this) then we will have successfully proved that C(ℚ) = ∅.

Suppose now that there is an ELS descendant D coming from one value of d_{3}. If we find a rational point on D, then we map it to a rational point on C, and again we are successful. If we fail to find a rational point on D, then we loop through the rest of the coset d_{3}H_{1}, construct each of the other ELS descendants, and search for rational points on each until we find one (in which case we can exit from the loop). Finally, if we fail to find rational points on any of the ELS descendants, we admit defeat, and either restart the algorithm with a larger search bound for rational points on the descendants, or attempt a third descent.

We now turn to the construction of the descendant curves themselves, for a fixed value of d_{3} in (9), (10).

3.2.4 Step 4: constructing the descendants

To solve (9), (10) we first verify that each is soluble separately, using the standard criterion of Legendre. If either fails, we continue to the next value of d_{3}. Assuming both are soluble, we find a solution to (9) using the same algorithm as in Step 1, and hence parametrize the solutions:

α = Q_{1}(λ, μ), β = Q_{3}(λ, μ), and s = Q_{2}(λ, μ)  (11)

where the Q_{j} are integer quadratics such that

q_{1}(Q_{1}(λ, μ), Q_{3}(λ, μ)) = d_{3}Q_{2}(λ, μ)^{2}  (12)

identically in λ and μ. Substituting in (10) we obtain the equation

D : g(λ, μ) = d_{3}t^{2}  (13)

where g(λ, μ) is the quartic q_{3}(Q_{1}(λ, μ), Q_{3}(λ, μ)). We check that D is ELS, using the algorithm in [5] or Siksek’s improvement for large primes (see [9]). Now D is the required descendant, which is a 2-covering of E. Equations (11) and (8) give an explicit rational map from a rational point (λ, μ, t) on D via (α, β, s) = (Q_{1}(λ, μ), Q_{3}(λ, μ), Q_{2}(λ, μ)) to (X, Y, Z) = (q_{1}(α, β), q_{3}(α, β)) on C_{0} with X/Z square, and hence to a rational point (u, v) = (\frac{s}{t}, \frac{Y}{d_{3}t^{2}} ) =

(\frac{Q_{2}(λ,μ)}{t}, \frac{q_{2}(Q_{1}(λ,μ),Q_{3}(λ,μ))}{d_{3}t^{2}}) on the first descent curve C.

3.2.5 Step 5: simplifying the descendants

Before we can go about searching for a rational point on the descendant curve D, it is essential to simplify its equation, replacing the quartic g(λ, μ) with an equivalent one (defining the same curve D up to birational isomorphism), since the preceding steps will usually lead to quartics with huge integer coefficients. This simplification is a major part of our algorithm, and is essential for the algorithm to be practical. It takes place in two stages, which we call minimizing and reducing the quartic. The minimization stage replaces g by a projectively equivalent integer quartic g^{∗} whose invariants I^{∗}, J^{∗} are of the form I^{∗} = w^{−4}I(g), J^{∗} = w^{−4}I(g), where w ∈ ℤ is as large as possible. Our algorithm for this, which is in some respects a quartic analogue of Tate’s algorithm for reducing elliptic curves, is based on ideas from Serf’s thesis [7] which in turn follow [1]. Secondly, the reduction stage uses a unimodular transformation to reduce the size of the coefficients of g^{∗} (while keeping I and J unchanged). Here we use a reduction theory for quartics similar to that in [1] (though slightly improved in the case of negative discriminant).

Finally, we use a sieve-assisted search to look for rational points on the transformed equation (13), as described in [5, Section 3.6].

Our algorithms for minimizing and reducing quartics will be described elsewhere. These, and the efficient algorithm for finding a small point on a conic (which we use to solve both (7) and (9)), are the crucial basic number-theoretical algorithms without which the second descent procedure described here could not be made to work effectively in practice.

4 Example

Rusin was interested in the elliptic curve E with standard Weierstrass coefficients [a_{1}, a_{2}, a_{3}, a_{4}, a_{6}] = [0, −1, 0, −1250000000083, −10000000000088]. Using the point (−8, 0) of order 2 this can be put in the form (3) with c = −25 and d = 3^{2} · 5^{3} · 11 · 41 · 271 · 9091. The 128 square-free divisors d_{1} of d give 32 ELS first descent curves C_{d_{1}} (generated by d_{1} = d and d_{1} = −1, 55 = 5 · 11, 451 = 11 · 41 and 11111 = 41 · 271). Here C_{d} comes from the rational 2-torsion point on E and so has a trivial rational point.

A simple search finds the rational point (u, v) = (20, 26565) on C_{−1355}, which maps to the point P_{1} = (−542000, −719911500) on E. There is also a small rational point on C_{4100041}, with u = 3/4, (which we can ignore since 4100041 ≡ −1355d modulo squares), but none on the 28 other non-trivial first descent curves C_{d_{1}}. (In fact we do not search all 28, since we only look at one in each coset of the subgroup which is known to have rational points.) So the φ-Selmer rank of E is 5, of which at least 2 comes from rational points on E.

Similarly, the first descent on E′ shows that its φ′-Selmer rank is 2, generated by d′ and 5, but we do not find rational points except the trivial one on C′_{d′} coming from the rational 2-torsion on E′.

Hence we find from the first descent that the rank is between 1 (= 2 + 1 − 2) and 5 (= 5 + 2 − 2). Rerunning the first descent with higher (reasonable) search bounds does not change this estimate.

When we do the second descent, two things happen: we increase the lower bound, by successfully finding more rational points on certain first descent curves, and we also decrease the upper bound, by successfully proving that certain others have no rational points. Specifically, we find rational points on C_{−55} and on C′_{5}. This shows that the number of first φ-descent curves C_{d_{1}} with rational points is at least 8, and that all 4 first φ′-descent curves have points. Secondly, the remaining 24 curves C_{d_{1}} have no ELS descendants, so do not have rational points. This proves unconditionally that E(ℚ) has rank 3 (as does E′(ℚ)), that the 2-rank of � (E/ℚ) is 0, while the 2-rank of � (E′/ℚ) is exactly 2.

We also obtain three explicit points on E(ℚ) which generate a subgroup of finite index, namely P_{1} = (−542000, −719911500) (as above) and

P_{2} = (\frac{−12123886930631252087108}{111060601^{2}}, \frac{−723566398176234298022167437626250}{111060601^{3}}) ,
P_{3} = (\frac{1651941110876982226534320892}{10864887323^{2}} ,

\frac{66926997509744679365893292879170097213082}{10864887323^{3}}) .

These points have approximate canonical heights 8.9, 46.5 and 61.6 respectively.

The point P_{2} comes from a descendant D of C_{−55}. The parametrization of the associated conic C_{0} is given by

q_{1}(α, β) = 1104305α^{2} + 9953711567910αβ + 22429576515805186725β^{2}
q_{3}(α, β) = 88α^{2} + 793192620αβ + 1787370830745640β^{2}.

Using d_{3} = 13, the first equation we obtain for the descendant D involves a quartic with 60-digit coefficients. Minimizing this removes a factor w = 45382656538986, after which the reduction step produces the more manageable quartic g(λ, μ) = 50125λ^{4} − 1250λ^{3}μ + 950λ^{2}μ^{2} − 124075λμ^{3} + 6235186μ^{4}. Now a small search reveals that g(505, 198) is a square, so we have a rational point on D, which maps to the point

(u, v) = (\frac{14846969850}{111060601}, \frac{886090079459099250015}{111060601^{2}})

on C_{−55}, and finally to P_{2} as above.

Similarly, P_{3} comes from a descendant D′ of C′_{5}, via C′_{5} and E′; the map from D′ to E has degree 8. Here we had to compute 15 descendants before we found one with a rational point.

More examples will appear in [6].

References

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

[2] , Notes on elliptic curves II, J. Reine Angew. Math. 218 (1965), 79–108.

[3] J. W. S. Cassels, Diophantine equations with special reference to elliptic curves, J. London Math. Soc. (2) 41 (1966), 193–291.

[4] , Second descents for elliptic curves, preprint, 1997.

[5] J. E. Cremona, Algorithms for modular elliptic curves, second ed., Cambridge University Press, 1997.

[6] J. E. Cremona and D. Rusin, Higher descents on elliptic curves, In preparation, 1997.

[7] P. Serf, The rank of elliptic curves over real quadratic number fields of class number 1, Ph.D. thesis, Universität des Saarlandes, 1995.

[8] J. H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics 106, Springer-Verlag, 1986.

[9] N. P. Smart, S. Siksek, and J. R. Merriman, Explicit 4-descents on an elliptic curve, Acta Arith. LXXVII.4 (1996), 385–404.