COMPUTING THE RANK OF ELLIPTIC CURVES OVER

REAL QUADRATIC NUMBER FIELDS OF CLASS NUMBER 1

J.E. Cremona and P. Serf

20 May 1996

Abstract. In this paper we describe an algorithm for computing the rank of an elliptic curve defined over a real quadratic field of class number one. In the case where the curve has no 2-torsion, this algorithm extends the one described by Birch and Swinnerton-Dyer for curves over ℚ in [1]. Several worked examples are included.

1. Introduction

The method of 2-descent has been used for many years in the study of the arithmetic of elliptic curves, from both the theoretical and the computational points of view. For elliptic curves defined over the rational numbers ℚ, an explicit algorithm for carrying out a general 2-descent was presented by Birch and Swinnerton-Dyer in [1]. A simpler algorithm, using 2-descent via 2-isogeny, can be applied when the curve has non-trivial 2-torsion; this is described in [10], [6], or [9]. Both algorithms have also been described in the book [2], and have been implemented by the first author. (The corresponding program mwrank can be obtained free via anonymous ftp from //euclid.exeter.ac.uk/pub/cremona.)

The aim of the present paper is to describe how to apply both 2-descent via 2-isogeny and general 2-descent over real quadratic number fields of class number 1. The algorithms have been implemented by the second author (see [8]). (The corresponding program rankrqnf1 can be obtained free via anonymous ftp from //ftp.math.uni-sb.de/pub/simath/pascale-serf.) We will give examples for both 2descent via 2-isogeny and general 2-descent over quadratic number fields, and in the case of 2-descent via 2-isogeny, we will in addition show how to construct Tate-Shafarevich groups with large 2-torsion.

For the computations over ℚ (see end of Section 2), we used the program mwrank, and also the computer algebra system simath. This system is mainly designed for algebraic number theory, with an emphasis on elliptic curves and function fields over finite fields. It has been developed since 1985 in the research group of Prof. H.G. Zimmer in Saarbrücken. (For non-commercial applications, simath is available free via anonymous ftp from //ftp.math.uni-sb.de/pub/simath.)

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 11G05, 11Y16, 11Y50, 14G25, 14H52, 14Q05.

Key words and phrases. elliptic curves, Mordell-Weil, real quadratic fields.

The second author was supported in part by DFG grant 513 009 738 3.

An independent implementation of 2-descent via 2-isogeny for number fields of arbitrary degree and class number is currently being developed by D. Simon in Bordeaux, as part of the PARI system.

Much of the work carried out here also applies to the case of imaginary quadratic fields; the main difference is that in order to obtain bounds for the search region (see Subsection 3.1) it is necessary to do more work. This is currently in progress.

We would like to thank Prof. H.G. Zimmer for his support, and Prof. D. Zagier for some helpful suggestions.

2. 2-descent via 2-isogeny

If an elliptic curve E has a rational point of order 2 over a number field K of class number 1, we can use 2-descent via 2-isogeny to determine rk(E/K). This algorithm goes back to Tate and is described in some detail in [10], [6], and [9].

We may assume that E is given in the form

E : y^{2} = x^{3} + cx^{2} + dx

with c, d ∈ 𝔒(K), the ring of integers of K, so that (0, 0) is the point of order 2. The main idea of 2-descent via 2-isogeny is to split up the multiplication by 2 on E into a 2-isogeny ϕ and its dual isogeny ϕ′:

E(K) ⟶^{ϕ} ; ⟵_{ϕ′}E′(K) with ϕ′ ∘ ϕ = [2]_{E(K)}, ϕ ∘ ϕ′ = [2]_{E′(K)},

where E′ is the 2-isogenous curve given by

E′ : y^{2} = x^{3} + c′x^{2} + d′x with c′ = −2c, d′ = c^{2} − 4d,

and ϕ and ϕ′ are as follows:

ϕ : E(K) ⟶E′(K)
O ↦ O
(0, 0) ↦ O
(x_{0}, y_{0}) ↦ (\frac{y_{0}^{2}}{x_{0}^{2}} , \frac{y_{0}(x_{0}^{2}−d)}{x_{0}^{2}})  ∀(x_{0}, y_{0}) ≠ O, (0, 0),
ϕ′ : E′(K) ⟶E(K)
O ↦ O
(0, 0) ↦ O
(x′_{0}, y′_{0}) ↦ (\frac{y′_{0}^{2}}{4x′_{0}^{2}} , \frac{y′_{0}(x′_{0}^{2}−d′)}{8x′_{0}^{2}}) ∀ (x′_{0}, y′_{0}) ≠ O, (0, 0).

Then the following formula holds for rk(E/K):

2^{rk(E/K)} = \frac{#α(E(K)) · #α′(E′(K))}{4}

or equivalently

(∗)  rk(E/K) = log_{2} #α(E(K)) + log_{2} #α′(E′(K)) − 2

with the group homomorphisms

α : E(K) ⟶ K^{∗}/K^{∗}^{2}
O  ↦ 1 mod K^{∗}^{2}
(0, 0) ↦ d mod K^{∗}^{2}
(x_{0}, y_{0}) ↦ x_{0} mod K^{∗}^{2} ∀ (x_{0}, y_{0}) ≠ O, (0, 0)

and

α′ : E′(K) ⟶ K^{∗}/K^{∗}^{2}
O  ↦ 1 mod K^{∗}^{2}
(0, 0) ↦ d′ mod K^{∗}^{2}
(x′_{0}, y′_{0}) ↦ x′_{0} mod K^{∗}^{2} ∀ (x′_{0}, y′_{0}) ≠ O, (0, 0).

The images of α and α′ are in fact finite. For d ∈ 𝔒(K), let K(d, 2) denote a set of elements d_{1} of K^{∗}, in distinct classes modulo K^{∗}^{2}, such that ord_{P}(d_{1}) is even for all prime ideals P of 𝔒(K) which divide d. Clearly this set is finite; since we are assuming that K has class number 1, it is easy to see that we may take the representatives d_{1} to be all the square-free divisors of d in 𝔒(K), multiplied by a set of representatives of units modulo squares. Then the cardinalities of the images of α and α′ satisfy

#α(E(K)) = #\{d_{1} ∈ K(d, 2); y^{2} = d_{1}x^{4} + cx^{2} + \frac{d}{d_{1}} has a point over K\},
#α′(E′(K)) = #\{d′_{1} ∈ K(d′, 2); y^{2} = d′_{1}x^{4} + c′x^{2} + \frac{d′}{d′_{1}} has a point over K\}.

(When we say that an equation “has a point over” K, we mean that the associated nonsingular projective curve has a point defined over K. Similarly with K replaced by an extension field.)

Let us in addition characterize the Selmer and Tate-Shafarevich groups for the ϕ- and ϕ′-descent:

#S^{(ϕ)}(E/K) = #\{d′_{1} ∈ K(d′, 2); y^{2} = d′_{1}x^{4} + c′x^{2} + \frac{d′}{d′_{1}} has a point

over all completions K_{P} of K}

#� (E/K)[ϕ] = #(S^{(ϕ)}(E/K)) / #(E′(K)/ϕ(E(K)))
#E′(K)/ϕ(E(K)) = #α′(E′(K))

where the second equality can be deduced from the exact sequence

0 ↪ E′(K)/ϕ(E(K)) ⟶ S^{(ϕ)}(E/K) ⟶ � (E/K)[ϕ] ⟶ 0.

Analogously,

#S^{(ϕ′)}(E′/K) = #\{d_{1} ∈ K(d, 2); y^{2} = d_{1}x^{4} + cx^{2} + \frac{d}{d_{1}} has a point

over all completions K_{P} of K}

#� (E′/K)[ϕ′] = #(S^{(ϕ′)}(E′/K)) / #(E(K)/ϕ′(E′(K)))
#E(K)/ϕ′(E′(K)) = #α(E(K))

from the corresponding sequence

0 ↪ E(K)/ϕ′(E′(K)) ⟶ S^{(ϕ′)}(E′/K) ⟶ � (E′/K)[ϕ′] ⟶ 0.

The 2-torsion of � (E/K) is bounded by

#� (E/K)[ϕ] ≤ #� (E/K)[2] ≤ #� (E/K)[ϕ] · #� (E′/K)[ϕ′],

so that

#� (E′/K)[ϕ′] = 1 ⟹ #� (E/K)[2] = #� (E/K)[ϕ],

and analogously we have for the 2-torsion of � (E′/K)

#� (E′/K)[ϕ′] ≤ #� (E′/K)[2] ≤ #� (E′/K)[ϕ′] · #� (E/K)[ϕ],

so that

#� (E/K)[ϕ] = 1 ⟹ #� (E′/K)[2] = #� (E′/K)[ϕ′].

If we assume that � (E/K) and � (E′/K) are finite, then we know that they must have a quadratic structure, i.e. #� (E/K)[2] and #� (E′/K)[2] must be even powers of 2.

Let us now return to the computation of rk(E/K). From (∗) and the characterization of #α(E(K)) and #α′(E′(K)), we can proceed as follows:

• First we determine all square-free divisors d_{1} of d and d′_{1} of d′, and hence the finite sets K(d, 2) and K(d′, 2).

• Then we check whether the corresponding quartic equations (or for short “quartics”) y^{2} = d_{1}x^{4} + cx^{2} + d/d_{1} and y^{2} = d′_{1}x^{4} + c′x^{2} + d′/d′_{1} have a point over all completions K_{P} of K. (We can restrict to considering the finite primes of K dividing 2dd′ and the infinite primes. See Subsection 3.7 for how to decide local solubility.)

• Finally we search for global points on all everywhere locally soluble quartics, count how many globally soluble quartics there are, and derive the rank.

Remark. The main problem with this procedure is that there exists no algorithm for deciding whether an everywhere locally soluble quartic has a global solution. All we can do is try to find one. But if we are not successful, we do not know whether the quartic does not have a global solution (which means that � (E/K)[ϕ] or � (E′/K)[ϕ′] are non-trivial), or whether we have not searched long enough. The only satisfactory way of deciding this is to carry out so-called “higher descents”; but we do not consider these further here.

Table 1 contains two curves of rank 4 and 7 over K = ℚ(\sqrt{5}) and two curves of rank 5 and 6 over K = ℚ(\sqrt{6}). In all cases we found global points on all everywhere locally soluble quartics, i.e. � (E/K)[ϕ] and � (E′/K)[ϕ′], hence � (E/K)[2] and � (E′/K)[2] too, are trivial. It is easy to derive points on E from the global points on the quartics: if (x_{0}, y_{0}) is a global point on y^{2} = d_{1}x^{4} + cx^{2} + d/d_{1}, then (d_{1}x_{0}^{2}, d_{1}x_{0}y_{0}) is a point on E; and if (x′_{0}, y′_{0}) is a global point on y^{2} = d′_{1}x^{4} +c′x^{2} + d′/d′_{1}, then the point (d′_{1}x′_{0}^{2}, d′_{1}x′_{0}y′_{0}) on E′ can be transferred to E by using the isogeny ϕ′. For all curves we list the rank r and r linearly independent points. The examples are taken from [5], where H. Graf determined lower bounds on the rank of elliptic curves over quadratic number fields. We ran them on an SGI Challenge.

Notation. If K = ℚ(\sqrt{D}) where D > 0 is square-free, we use the standard integral basis 1, ω with ω = \sqrt{D} if D ≡ 2, 3 (mod 4) or ω = (1 + \sqrt{D})/2 if D ≡ 1 (mod 4). Elements x ∈ K are represented as ordered pairs (α_{x}, β_{x}) where x = α_{x} + β_{x}ω, with α_{x}, β_{x} ∈ ℚ, and α_{x}, β_{x} ∈ ℤ when x ∈ 𝔒(K).

As an application of our program, we will now construct Tate-Shafarevich groups with large 2-torsion over real quadratic number fields.

In [7], K. Kramer considered the following family of elliptic curves over ℚ:

E_{m} : y^{2} + xy = x^{3} − 16mx^{2} − 8mx − m with m ∈ ℕ.

E_{m} has a point of order 2, namely (−\frac{1}{4}, \frac{1}{8}). Kramer showed how to choose m so that #� (E_{m}/ℚ)[2] ≥ 2^{2n} for a given n ∈ ℕ. We found out that #� (E_{m}/ℚ)[2] is actually much greater in most cases. Therefore we proceeded as follows:

We first determined all m ∈ {1, …, 1000} such that

rk(E_{m}/ℚ) = 0  and  16 | #� (E_{m}/ℚ).

For these computations we used the simath functions ecrrank and ecrordtsg (these both depend on the Birch and Swinnerton-Dyer conjecture). We restricted to those m with rk(E_{m}/ℚ) = 0 because computing the elliptic regulator, which is necessary for determining #� (E_{m}/ℚ), is trivial in those cases.

Then we used the program mwrank to compute #� (E_{m}/ℚ)[2], assuming that rk(E_{m}(ℚ)) = 0. We obtained the following results:

150 cases where  #� (E_{m}/ℚ)[2] = 4,
244 cases where  #� (E_{m}/ℚ)[2] = 16,
and 7 cases where  #� (E_{m}/ℚ)[2] = 64.

For the seven m with #� (E_{m}/ℚ)[2] = 64, namely

m = 290, 420, 494, 654, 884, 966, and 990,

we investigated what happens when we pass from ℚ to each of the first ten real quadratic number fields of class number 1, i.e. to ℚ(\sqrt{D}) for

D = 2, 3, 5, 6, 7, 11, 13, 14, 17, and 19.

Determining the rank of E_{m} over ℚ(\sqrt{D}) is easy:

rk(E_{m}/ℚ(\sqrt{D})) = rk(E_{m}/ℚ) + rk(E_{m,D}/ℚ),

where E_{m,D} is the D-twist of E_{m}. We used the simath function ecrrank for these computations.

6 J.E. CREMONA AND P. SERF

Table 1

K  c  d  rank  linearly independent points time
ℚ(\sqrt{5}) (661, 453) (−24244, 84854)  4 #1 x = (−166, 18)  106 s

y = (4020, −728)

#2 x = (−76, −722)

y = (−3610, 8132)

#3 x = (−220, 462)

y = (8646, 9724)

#4 x = (5328, −3528)

y = (−485088, 293508)

ℚ(\sqrt{5}) (684, 297) (38874, 15048) 7 #1 x = (48060, −29538) 75 s

y = (−12406932, 7661178)

#2 x = (1350, −1080)

y = (−76176, 41022)

#3 x = (−24, 72)

y = (1104, 1836)

#4 x = (582, −162)

y = (−13656, 16548)

#5 x = (−60, −186)

y = (−3816, −3234)

#6 x = \frac{1}{25}(−4818, −3762)

y = \frac{1}{125}(−456060, −532092)

#7 x = (32, −96)

y = (−1216, 2504)

ℚ(\sqrt{6}) (711, 227) (−183540, −72105) 5 #1 x = \frac{1}{25}(−4377, −2328) 236 s

y = \frac{1}{125}(1027122, 443133)

#2 x = \frac{1}{25}(−813, 168)

y = \frac{1}{125}(−202584, −43401)

#3 x = \frac{1}{2}(10925, 4370)

y = \frac{1}{4}(2377280, 967955)

#4 x = \frac{1}{2}(−513, −152)

y = \frac{1}{4}(−37734, −13851)

#5 x = (2356, 969)

y = (181754, 74366)

ℚ(\sqrt{6}) (119, 59) (−1786893, −595631) 6 #1 x = (−289, 98)  240 s

y = (−8449, −1705)

#2 x = (5165, 1489)

y = (438263, 156786)

#3 x = \frac{1}{3}(506, −598)

y = \frac{1}{9}(−110538, −72887)

#4 x = (−205, −326)

y = (−26231, −9753)

#5 x = \frac{1}{4}(7163, 3306)

y = \frac{1}{8}(898681, 341069)

#6 x = \frac{1}{50}(6299409, 2572474)

y = \frac{1}{500}(31643083896,12918941431)

ELLIPTIC CURVES OVER REAL QUADRATIC FIELDS 7

Now, when applying 2-descent via 2-isogeny to E_{m} over K = ℚ(\sqrt{D}), we knew in advance the value of rk(E_{m}/K) to be obtained. In all cases we had

#S^{(ϕ′)}(E′_{m}/K) = 1

and

#E_{m}(K)/ϕ′(E′_{m}(K)) = #α(E_{m}(K)) = 1,

hence

#� (E′_{m}/K)[ϕ′] = 1.

Therefore #� (E_{m}/K)[2] = #� (E_{m}/K)[ϕ] = #(S^{(ϕ)}(E_{m}/K)) / #(E′_{m}(K)/ϕ(E_{m}(K))) with

#E′_{m}(K)/ϕ(E_{m}(K)) = #α′(E′_{m}(K))

and

rk(E_{m}/K) = log_{2} #α′(E′_{m}(K)) − 2,

i.e.

#α′(E′_{m}(K)) = 2^{rk(E_{m}/K)+2}.

We obtained the following values for #� (E_{m}/ℚ(\sqrt{D}))[2].

Table 2 \begin{aligned}& D & 2 & 3 & 5 & 6 & 7 & 11 & 13 & 14 & 17 & 19 \\ m \\ 290 & & 256 & 64 & 256 & 256 & 256 & 256 & 1024 & 256 & 256 & 1024 \\ 420 & & 256 & 1024 & 256 & 256 & 256 & 256 & 256 & 1024 & 1024 & 256 \\ 494 & & 256 & 64 & 256 & 256 & 1024 & 256 & 256 & 1024 & 1024 & 1024 \\ 654 & & 256 & 1024 & 256 & 256 & 64 & 256 & 256 & 64 & 256 & 256 \\ 884 & & 1024 & 256 & 256 & 256 & 256 & 256 & 1024 & 256 & 256 & 1024 \\ 966 & & 1024 & 256 & 256 & 256 & 256 & 256 & 1024 & 256 & 256 & 256 \\ 990 & & 1024 & 256 & 256 & 256 & 256 & 256 & 64 & 64 & 64 & 1024 \end{aligned}

Here there are

7 cases where  #� (E_{m}/ℚ(\sqrt{D}))[2] = 64,
46 cases where  #� (E_{m}/ℚ(\sqrt{D}))[2] = 256,
and 17 cases where  #� (E_{m}/ℚ(\sqrt{D}))[2] = 1024.

3. General 2-descent

General 2-descent can (in principle) be applied to an arbitrary elliptic curve E over a number field K, whether E(K)[2] is trivial or non-trivial. For K = ℚ, Birch and Swinnerton-Dyer described in detail in [1] how to proceed.

The main principle of general 2-descent is to not consider the elliptic curve E itself, but 2-coverings (or principal homogeneous spaces) of E. These are represented (provided they are everywhere locally trivial, see the remark below) by quartic equations of the form

y^{2} = g(x) = ax^{4} + bx^{3} + cx^{2} + dx + e with a, b, c, d, e ∈ K,

whose invariants

I(g) = 12ae − 3bd + c^{2} and J(g) = 72ace − 27ad^{2} − 27b^{2}e + 9bcd − 2c^{3}

differ from the invariants c_{4}(E) and 2c_{6}(E) by a 4th and a 6th power, i.e.

I(g) = λ^{4} c_{4}(E) and J(g) = λ^{6} 2c_{6}(E)

for some λ ∈ K^{∗}. Two homogeneous spaces y^{2} = g_{1}(x) and y^{2} = g_{2}(x) are called equivalent if

g_{2}(x) = μ^{2}(γx + δ)^{4}g_{1} (\frac{αx + β}{γx + δ} )

for some α, β, γ, δ ∈ K with αδ−βγ ≠ 0 and some μ ∈ K^{∗}. The set of all equivalence classes of 2-coverings forms an elementary abelian 2-group, say G, with

G ≅ H^{1}(Gal(\overline{K}/K), E(\overline{K})[2]),

where \overline{K} denotes the algebraic closure of K and Gal(\overline{K}/K) the absolute Galois group of \overline{K}/K. The trivial class in G consists of those quartics y^{2} = g(x) such that g(x) has a root in K; they are elliptic curves which are isomorphic to E over K.

Remark. Not all 2-coverings of E may be represented by quartics. However, this is certainly possible for those which have points everywhere locally (that is, in all completions of K) by [1], Lemma 1. These are the only 2-coverings which will concern us here.

We are interested in two subgroups of G: the subgroup G of all equivalence classes of 2-coverings which have a point everywhere locally (i.e. over all completions K_{P} of K), and the subgroup G′ of all equivalence classes of 2-coverings which have a global point. G has the following properties:

#G < ∞, G ≅ S^{(2)}(E/K), #G = 2^{k} for some k ∈ ℕ.

For G′ we have

G′ ≤ G, G′ ≅ E(K)/2E(K), #G′ = 2^{k′} for some k′ ∈ ℕ, k′ ≤ k.

Applying the Mordell-Weil theorem, i.e. using E(K) ≅ E_{tors}(K) × ℤ^{r} with r = rk(E/K), we have #E(K)/2E(K) = 2^{t+r} with 2^{t} = #E(K)[2]. This yields

r = k′ − t.

So in order to compute rk(E/K), all we have to do is to determine the number 2^{k} of all everywhere locally soluble quartics (up to equivalence) and, among these, the number 2^{k′} of all globally soluble quartics.

Exactly as in the case of 2-descent via 2-isogeny, there is a major problem: How to decide whether a quartic with points everywhere locally has a global point? If we do not find such a point, it may be either because there is none, or because we have not searched long enough.

Quartics which are everywhere locally but not globally soluble come from elements of order 2 in the Tate-Shafarevich group; more precisely, the exact sequence

0 ↪ E(K)/2E(K) ⟶ S^{(2)}(E/K) ⟶ � (E/K)[2] ⟶ 0

implies

#� (E/K)[2] = #(S^{(2)}(E/K)) / #(E(K)/2E(K)) = 2^{k−k′},

so that

k′ < k ⟺ � (E/K)[2] is non-trivial.

We have seen that we must determine all everywhere locally soluble quartics (at least one from each equivalence class) whose invariants I and J satisfy

I = λ^{4} c_{4}(E) and J = λ^{6} 2c_{6}(E)

for some λ ∈ K^{∗}. We can of course not consider all such pairs of invariants; we must restrict to finitely many and reasonably many. We will see in Section 4 that we have to deal with at most four (I, J) pairs if K is a quadratic number field.

Let us now confine ourselves to one fixed pair (I, J). We will explain in detail how to find all quartics belonging to this pair.

It should be mentioned that we may assume the coefficients a, b, c, d, e of the quartics to be integral, as denominators in the right-hand side of y^{2} = ax^{4} + bx^{3} + cx^{2} + dx + e can always be absorbed into y. Then I and J are also integral.

We must determine

(1) a search region for a,

(2) for each a, a search region for b,

(3) for each pair (a, b), a search region for c,

(4) for each triple (a, b, c), the coefficients d and e such that I(a, b, c, d, e) = I

and J(a, b, c, d, e) = J, and check whether the quartic y^{2} = ax^{4} + bx^{3} + cx^{2} + dx + e is

(5) a trivial quartic,

(6) equivalent to a quartic previously obtained,

(7) everywhere locally soluble,

(8) globally soluble.

Finally we will derive

(9) points on the elliptic curve from the global points on the quartics. The nine steps in this procedure are described in more detail in the nine subsections 3.1–3.9.

3.0 The different types of quartics.

Over K = ℚ, Birch and Swinnerton-Dyer had to consider three different types of quartics:

type 1: quartics with no real roots;
type 2: quartics with four real roots;
type 3: quartics with two real roots.

From the equality

4I^{3} − J^{2} = 27 · disc(g)

for I = I(g) and J = J(g), we can deduce that

if 4I^{3} − J^{2} > 0, only type 1 and type 2 quartics are possible;
if 4I^{3} − J^{2} < 0, only type 3 quartics are possible.

Moreover, in the case of positive discriminant, one can show that the classes of globally soluble quartics of type 2 (including the trivial class) form a subgroup of the group G′, of index 1 or 2. This is because the type 1 quartics map to points on the identity component of E(ℝ): there will be globally soluble quartics of type 1 if and only if there are rational points on the other component of E(ℝ). One can use this fact to speed up the algorithm, since it follows that if there are any globally soluble quartics of type 1, the number of them is equal to the number of type 2, so the search for type 1 quartics may be curtailed as soon as one is found.

Let us now come to the case K = ℚ(\sqrt{D}), D > 0. Let σ_{1} and σ_{2} with σ_{1}(\sqrt{D}) = \sqrt{D} and σ_{2}(\sqrt{D}) = −\sqrt{D} be the two embeddings of K into ℝ. For each quartic g(x) = ax^{4} + bx^{3} + cx^{2} + dx + e with a, b, c, d, e ∈ K, we consider the two real embeddings g_{σ_{1}}(x) = σ_{1}(a)x^{4} + σ_{1}(b)x^{3} + σ_{1}(c)x^{2} + σ_{1}(d)x + σ_{1}(e) and g_{σ_{2}}(x) = σ_{2}(a)x^{4} + σ_{2}(b)x^{3} + σ_{2}(c)x^{2} + σ_{2}(d)x + σ_{2}(e). As the signs of the discriminants of g_{σ_{1}} and g_{σ_{2}} are independent of each other, the types of g_{σ_{1}} and g_{σ_{2}} (the “σ_{1}-type” and “σ_{2}-type” of g) are also independent of each other. Hence the following type combinations (t_{σ_{1}}, t_{σ_{2}}) are possible:

if σ_{1}(4I^{3} − J^{2}) > 0 and σ_{2}(4I^{3} − J^{2}) > 0: (t_{σ_{1}}, t_{σ_{2}}) ∈ {(1, 1), (1, 2), (2, 1), (2, 2)};
if σ_{1}(4I^{3} − J^{2}) > 0 and σ_{2}(4I^{3} − J^{2}) < 0: (t_{σ_{1}}, t_{σ_{2}}) ∈ {(1, 3), (2, 3)};
if σ_{1}(4I^{3} − J^{2}) < 0 and σ_{2}(4I^{3} − J^{2}) > 0: (t_{σ_{1}}, t_{σ_{2}}) ∈ {(3, 1), (3, 2)};
if σ_{1}(4I^{3} − J^{2}) < 0 and σ_{2}(4I^{3} − J^{2}) < 0: (t_{σ_{1}}, t_{σ_{2}}) ∈ {(3, 3)}.

As over ℚ, we may use the group structure to reduce the running time of the algorithm, since (for example) the number of globally soluble quartics of type (3, 1) is either 0 or equal to the number of type (3, 2); similarly in other cases. However, we have not yet implemented this idea.

3.1 A search region for a.

In order to bound the leading coefficient a for K = ℚ, Birch and Swinnerton-Dyer introduced the notion of a reduced quartic. They associate to each quartic a positive definite quadratic form, covariant under real transformations, and they call the quartic reduced if the quadratic form is. Since every positive definite quadratic form is SL(2, ℤ)-equivalent to a reduced quadratic form, every quartic is SL(2, ℤ)- equivalent to a reduced quartic. For a reduced quadratic form, the root with positive imaginary part lies in the usual fundamental domain for the action of SL(2, ℤ) on the complex upper half plane H, which implies that its imaginary part is at least \sqrt{3}/2. From this lower bound Birch and Swinnerton-Dyer derived real bounds for the leading coefficient a of reduced quartics. The relevant a are the integers between the lower and the upper bound.

Thus the crucial fact in step (1) is the following result:

∀z ∈ H ∃ M ∈ SL(2, ℤ) with Im(M(z)) ≥ \frac{\sqrt{3}}{2}.

Let us now come to a real quadratic number field K = ℚ(\sqrt{D}), D > 0. For each quartic over 𝔒(K), we consider its two real embeddings. The action of SL(2, ℤ) on H is replaced by the action of SL(2, 𝔒(K)) on H × H:

M(z_{1}, z_{2}) = (σ_{1}(M)(z_{1}), σ_{2}(M)(z_{2})) ∀M ∈ SL(2, 𝔒(K)), (z_{1}, z_{2}) ∈ H × H.

The product of the two imaginary parts can be bounded below as follows:

Theorem. Assume K = ℚ(\sqrt{D}), D > 0, and h(K) = 1. There exists δ_{0} = δ_{0}(D) ∈ ℝ_{>0} such that

∀(z_{1}, z_{2}) ∈ H^{2} ∃M ∈ SL(2, 𝔒(K)) with Im(σ_{1}(M)(z_{1})) · Im(σ_{2}(M)(z_{2})) ≥ δ_{0},

namely

δ_{0} = \frac{π^{2}}{2^{4}} \frac{1}{disc(K/ℚ)}.

Applying this result leads to bounds on the norm of a, so that we only have to determine all a whose norm lies between these bounds (see [8] for the details).

Proof. The first part of the proof is a simplification of a similar proof in [4] for arbitrary totally real number fields: For some fixed z = (z_{1}, z_{2}) ∈ H^{2} we set

Λ = 𝔒(K)·z+𝔒(K) = {(σ_{1}(a)·z_{1}+σ_{1}(b), σ_{2}(a)·z_{2}+σ_{2}(b)) | a, b ∈ 𝔒(K)} ⊂ ℂ^{2}

and for arbitrary L ∈ ℝ_{>0}

V_{L} = {u = (u_{1}, u_{2}) ∈ ℂ^{2}; |u_{j}|^{2} ≤ L · Im(z_{j}) for j = 1, 2}.

A well-known lemma by Minkowski says that if the volume of V_{L} is greater than or equal to 2^{4} times the volume of a fundamental parallelogram for Λ, which is the case for L ≥ \frac{2^{2}}{π} \sqrt{disc(K/ℚ)}, then there exists a non-zero element of Λ lying in V_{L}, i.e. there are c, d ∈ 𝔒(K), not both zero, satisfying

|σ_{j}(c) · z_{j} + σ_{j}(d)|^{2} ≤ L · Im(z_{j}) for j = 1, 2.

Let e = gcd(c, d), hence 1 = gcd(c′, d′) for c′ = \frac{c}{e} and d′ = \frac{d}{e}, so that there exist

a′, b′ ∈ 𝔒(K) with 1 = a′d′ − b′c′. Then we have, for the matrix M = ( \begin{matrix}a′ & b′ \\ c′ & d′ \end{matrix} ),

Im(σ_{j}(M)(z_{j})) ≥ L^{−1} · |σ_{j}(e)|^{2}.

If we now try to bound the imaginary parts simultaneously, which is done in [4], some power of σ_{1}(ε_{0}) comes in, where ε_{0} is the fundamental unit of K. But this can be avoided by bounding the product of the imaginary parts:

Im(σ_{1}(M)(z_{1})) · Im(σ_{2}(M)(z_{2})) ≥ L^{−2} · | norm_{K/ℚ}(e)|^{2} ≥ L^{−2}.

For L = \frac{2^{2}}{π} \sqrt{disc(K/ℚ)} we obtain the desired result. □

3.2 For each a, a search region for b.

For all B ∈ 𝔒(K), the quartic g^{∗}(x) = g(x + B) has integral coefficients and the same invariants as g. Its first two coefficients are

a^{∗} = a and b^{∗} = b + 4Ba,

so that

b^{∗} ≡ b (mod 4a).

Hence we may assume b lies in a complete set of representatives modulo 4a. For K = ℚ we can choose the symmetric set

{b ∈ ℤ : −2|a| < b ≤ 2|a|}.

Let us now come to the case K = ℚ(\sqrt{D}), D > 0. Any κ ∈ 𝔒(K) can be written as κ = (α_{κ}, β_{κ}) with α_{κ}, β_{κ} ∈ ℤ, its representation with respect to the integral basis. For a = (α_{a}, β_{a}), the set

{(α_{b}, β_{b}) ∈ ℤ^{2} | −2γ_{a}N′ < α_{b} ≤ 2γ_{a}N′ and − 2γ_{a} < β_{b} ≤ 2γ_{a}}

with γ_{a} = gcd(α_{a}, β_{a}) ∈ ℕ and N′ = | norm_{K/ℚ}(a′)| for a = γ_{a}a′ forms a set of representatives modulo 4a.

In both cases, the symmetry of the set of representatives makes it possible to consider b and −b simultaneously, except at the boundaries.

3.3 For each pair (a, b), a search region for c.

When determining lower and upper bounds on σ_{1}(a) and σ_{2}(a) as mentioned in Subsection 3.1, we obtain lower and upper bounds on σ_{1}(c) and σ_{2}(c) with very little extra work. These bounds are similar to the corresponding bounds over ℚ (see [2]), except that they also involve both the discriminant disc(K/ℚ) and the fundamental unit (see [8] for the details). Let c = (α_{c}, β_{c}) with α_{c}, β_{c} ∈ ℤ be the representation of c with respect to the integral basis. What we have to do is to translate the bounds on σ_{1}(c) and σ_{2}(c) into bounds on α_{c} and β_{c}. Let us illustrate with the case D ≡ 2, 3 (mod 4), where \{1, \sqrt{D}\} is an integral basis. (The case D ≡ 1 (mod 4), where \{1, \frac{1+\sqrt{D}}{2} \} forms an integral basis, is analogous.)

From

σ_{1}(c) = α_{c} + β_{c}\sqrt{D}  and  σ_{2}(c) = α_{c} − β_{c}\sqrt{D}

we have

α_{c} = \frac{σ_{1}(c) + σ_{2}(c)}{2}.

The bounds

l_{σ_{1}(c)} ≤ σ_{1}(c) ≤ u_{σ_{1}(c)}  and  l_{σ_{2}(c)} ≤ σ_{2}(c) ≤ u_{σ_{2}(c)}

then yield

\frac{l_{σ_{1}(c)} + l_{σ_{2}(c)}}{2} ≤ α_{c} ≤ \frac{u_{σ_{1}(c)} + u_{σ_{2}(c)}}{2} .

Hence we consider all rational integers α_{c} between these bounds and all rational integers β_{c} with

\frac{l_{σ_{1}(c)} − α_{c}}{\sqrt{D}} ≤ β_{c} = \frac{σ_{1}(c) − α_{c}}{\sqrt{D}} ≤ \frac{u_{σ_{1}(c)} − α_{c}}{\sqrt{D}}

\frac{α_{c} − u_{σ_{2}(c)}}{\sqrt{D}} ≤ β_{c} = \frac{α_{c} − σ_{2}(c)}{\sqrt{D}} ≤ \frac{α_{c} − l_{σ_{2}(c)}}{\sqrt{D}} ,

or

max \{\frac{l_{σ_{1}(c)} − α_{c}}{\sqrt{D}} , \frac{α_{c} − u_{σ_{2}(c)}}{\sqrt{D}} \} ≤ β_{c} ≤ min \{\frac{u_{σ_{1}(c)} − α_{c}}{\sqrt{D}} , \frac{α_{c} − l_{σ_{2}(c)}}{\sqrt{D}} \} .

3.4 For each triple (a, b, c), the coefficients d and e.

The method we will now describe works over an arbitrary field K.

Consider the defining expressions for I and J as equations for d and e, which are linear in e. Eliminating e, we obtain a quadratic equation for d over K. This equation has a solution if its discriminant is a square in K. (The condition that this discriminant be a square is in fact a syzygy between seminvariants of the quartic g: see [3] for more details of this viewpoint.) If the discriminant is a square, we can determine d and then solve for e. Finally we test whether the resulting quartic (a, b, c, d, e) has correct invariants and the right σ_{1}- and σ_{2}-type.

We can save much time in practice by checking first whether the discriminant of the quadratic equation for d is a square modulo some appropriately chosen moduli before testing whether it is a global square. In practice we carry out a quadratic sieve, where we only consider a triple (a, b, c) which lies in our search region if this discriminant (which is a polynomial in I, J, a, b, and c) is a square modulo each of the sieving moduli. In the program mwrank, in the case K = ℚ, sieving modulo the five rational primes 5, 7, 11, 13, 17 saves up to 90% of the cpu time, and for a real quadratic number field, sieving modulo the smallest eleven primes of degree one still saves between 30% and 70%.

3.5 Checking triviality.

Testing whether a quartic y^{2} = g(x) is trivial, i.e. whether g(x) has a root in K, is straightforward. The simplest way is to factorise g(x) in K[x], assuming that one is using a computer algebra system containing such a routine.

3.6 Testing equivalence.

Originally, we used a generalisation of the method of [1] to test equivalence of quartics. This method is based simply on the idea of finding an explicit transformation between two quartics g_{1}(x) and g_{2}(x). For a real quadratic field, the problem becomes two-dimensional, as we have to consider both the real embeddings of the quartics, and hence is considerably more difficult to explain and implement.

In [3] a much simpler method of testing equivalence was derived, based on invariant theory, and applicable to an arbitrary field K. We present this test here: see [3] for details and proofs.

It suffices to test equivalence of quartics with the same invariants I, J, since if g_{2}(x) has invariants λ^{4}I, λ^{6}J we may initially replace g_{1}(x) by λ^{2}g_{1}(x) (or g_{1}(λx)).

Proposition. Let g_{j}(x) for j = 1, 2 be quartics over 𝔒(K) with coefficients a_{j}, b_{j}, c_{j}, d_{j}, e_{j}, both having the same invariants I, J. We set for j = 1, 2

p_{j} = 3b_{j}^{2} − 8a_{j}c_{j},
r_{j} = b_{j}^{3} + 8a_{j}^{2}d_{j} − 4a_{j}b_{j}c_{j},

and

p = \frac{1}{3}(p_{1}p_{2} + 32a_{1}a_{2}I),
s = \frac{1}{27}(64I(p_{1}^{2}a_{2}^{2} + p_{1}p_{2}a_{1}a_{2} + p_{2}^{2}a_{1}^{2}) − 256Ja_{1}a_{2}(p_{1}a_{2} + p_{2}a_{1}) − p_{1}^{2}p_{2}^{2}),
r = r_{1}r_{2}.

Then we have

g_{1} and g_{2} are equivalent ⟺ x^{4} − 2px^{2} − 8rx + s has a root in K.

Remark. The quartic x^{4} − 2px^{2} − 8rx + s does not (in general) have invariants I, J, though its cubic resolvent field is the same as that of g_{1} and g_{2}.

3.7 Local solubility.

Testing local solubility of y^{2} = g(x) modulo the infinite primes of a real quadratic number field K (or, more generally, an arbitrary totally real number field) is easy. One simply has to find out whether the corresponding embedding has a solution over ℝ, i.e. whether g(x) can take non-negative values.

Let now K be an arbitrary number field, P a finite prime of K, and g(x) a polynomial over ℤ_{P}, the ring of P-adic integers in the completion K_{P}. It is clear that y^{2} = g(x) has a solution over K_{P} if and only if y^{2} = g(x) has a solution over ℤ_{P} or y^{2} = g^{∗}(x) has a solution over ℤ_{P} with x ≡ 0 (mod P), where g^{∗}(x) = x^{deg(g)}g(1/x) = ex^{4} + dx^{3} + cx^{2} + bx + a for g(x) = ax^{4} + bx^{3} + cx^{2} + dx + e. We proceed as follows (see [1]):

We first decide whether y^{2} = g(x) is soluble over ℤ_{P}: we have a list of residue classes to examine, initially consisting of all classes modulo P. We take a class x_{0} mod P^{ν} from the list and apply a special version of Hensel’s lemma to find out whether y^{2} = g(x) has a solution with x ≡ x_{0} (mod P^{ν}). There are three possible answers: either “definitely yes” or “definitely no” or “maybe”. If the lemma certainly gives a solution, we have no more to do. If it certainly gives none, we delete this class from the list. If the lemma gives us no definite information (in the “maybe” case), we replace the class x_{0} mod P^{ν} by the corresponding classes modulo P^{ν+1}. Eventually we must either find that y^{2} = g(x) is soluble over ℤ_{P}, or exhaust our list, in which case y^{2} = g(x) is insoluble. This procedure is guaranteed to come to an end, as the “maybe” case cannot occur for sufficiently large ν.

If y^{2} = g(x) is insoluble over ℤ_{P}, we go on to consider y^{2} = g^{∗}(x), starting now with the one class 0 mod P. If this too does not give a solution over ℤ_{P}, our quartic y^{2} = g(x) is insoluble over K_{P}.

For g(x) = ax^{4} + bx^{3} + cx^{2} + dx + e, local solubility is guaranteed for all odd primes not dividing 4I(g)^{3} − J(g)^{2}. Thus we can, as in Section 2, restrict to testing local solubility modulo finitely many primes.

3.8 Global solubility.

To test for global solubility of y^{2} = g(x), we simply search for a point over K. This is realised by loops on the numerator and the denominator of x and testing whether g(x) is a square. Here one can save much time by sieving, i.e. by checking first whether g(x) is a square modulo some appropriate moduli. The number of moduli should not be too large, because we then need more time for initializing arrays for local squares/non-squares than we save; and too few moduli do not reject enough global non-squares. It is often preferable to use composite moduli (e.g. containing small powers of 2 and 3) instead of primes. We found that 72 = 2^{3} · 3^{2}, 77 = 7 · 11, 65 = 5 · 13 was the best choice in our case.

3.9 Points on the elliptic curve from the global points on the quartics.

If y^{2} = g(x) has a K-rational point (x_{0}, y_{0}), we first apply a transformation sending x_{0} to ∞; this leads to an equivalent quartic g^{∗}(x) = a^{∗}x^{4} + b^{∗}x^{3} + c^{∗}x^{2} + d^{∗}x + e^{∗}, in which a^{∗} ∈ K^{∗}^{2}. Then the point

(\frac{3(3b^{∗}^{2} − 8a^{∗}c^{∗})}{4a^{∗}}, \frac{27(b^{∗}^{3} + 8a^{∗}^{2}d^{∗} − 4a^{∗}b^{∗}c^{∗})}{8a^{∗}^{3/2}})

lies on the elliptic curve y^{2} = x^{3} − 27Ix − 27J, which is isomorphic to the original curve E.

The theoretical basis for the general 2-descent method is the fact that the points we thus obtain on E(K) are in the same coset of 2E(K) in E(K) if and only if they come from equivalent quartics.

4. The relevant (I, J) pairs

We have described in Section 3 how to determine all reduced quartics for one fixed pair (I, J). We will now explain how to find all relevant (I, J) pairs.

Let us start with the case K = ℚ. We may assume that the elliptic curve E over ℚ is given in the form

E : y^{2} = f(x) = x^{3} + Ax + B with A, B ∈ ℤ,

and we set

I = I(f) = I(0, 1, 0, A, B) = −3A

and

J = J(f) = J(0, 1, 0, A, B) = −3^{3}B.

As required, I and J differ from

c_{4}(E) = −2^{4}3A and 2c_{6}(E) = −2^{6}3^{3}B

by a 4th and a 6th power. The question is whether we can divide out further 4th and 6th prime powers from I = −3A and J = −3^{3}B. This can be done (for a prime p satisfying p^{4} | I and p^{6} | J) if every quartic over ℤ with invariants I and J which is p-adically soluble is equivalent to a quartic over ℤ with invariants p^{−4}I and p^{−6}J. In this case we say that I and J can be p-reduced. In addition, we might possibly have to multiply I and J by 4th and 6th prime powers. This must be done if we cannot prove that p^{4}I and p^{6}J can be p-reduced. In [1] the following criteria for p-reducibility are stated in three lemmas:

Lemma 3: p ≠ 2, 3: p^{4} | I, p^{6} | J  ⟺ I, J can be p-reduced.
Lemma 4: p = 3:  3^{5} | I, 3^{9} | J
or 3^{4} ∥ I, 3^{6} ∥ J, 3^{15} | 4I^{3} − J^{2} ⟺ I, J can be 3-reduced.
Lemma 5: p = 2:  2^{6} | I, 2^{9} | J, 2^{10} | 2^{3}I + J ⟹ I, J can be 2-reduced.

Note that for p = 2, we only have sufficient conditions for reducibility, while for all odd primes we have necessary and sufficient conditions.

This shows that for primes p ≠ 2, 3, we can always make I and J free of 4th and 6th powers. For p = 3 and p = 2, the situation is more complicated; in both cases p^{4} | I and p^{6} | J may occur, but we can always avoid p^{8} | I and p^{12} | J. Let us explain more precisely how to find the relevant (I, J) pairs over ℚ:

• For all primes p ≠ 2, 3, we may assume that p^{4} /| I or p^{6} /| J.

• p = 3: We may assume that 3^{8} /| I or 3^{12} /| J. If 3^{5} | I, 3^{9} | J or 3^{4} ∥ I, 3^{6} ∥ J, 3^{15} | 4I^{3} − J^{2} hold, we replace (I, J) by (3^{−4}I, 3^{−6}J).

• p = 2: We may assume that 2^{8} /| I or 2^{12} /| J. If 2^{4} | I, 2^{6} | J, we replace (I, J) by (2^{−4}I, 2^{−6}J). But we also take into consideration the pair (I′, J′) = (2^{4}I, 2^{6}J). If 2^{6} | I′, 2^{9} | J′, 2^{10} | 2^{3}I′ + J′, i.e. 2^{2} | I, 2^{3} | J, 2^{4} | 2I + J, we can restrict to the pair (I, J); otherwise we consider the two pairs (I, J) and (I′, J′) = (2^{4}I, 2^{6}J).

Hence we have either one or two relevant pairs of invariants over ℚ.

Remark. If c_{4} and c_{6} are the invariants of a global minimal model for E over ℚ, then the invariant values I = c_{4}, J = 2c_{6} are automatically p-reduced for all odd primes p (including p = 3). The pairs to be considered are thus (c_{4}, 2c_{6}) in all cases, and also (2^{4}c_{4}, 2^{7}c_{6}) unless 2^{2} | c_{4}, 2^{2} | c_{6}, and 2^{3} | c_{4} + c_{6}.

Let us now come to the case K = ℚ(\sqrt{D}), D > 0. Analogously to the case K = ℚ, we may assume that we have an elliptic curve of the form

E : y^{2} = x^{3} + Ax + B with A, B ∈ 𝔒(K),

we set I = −3A and J = −3^{3}B, and try to divide out 4th and 6th powers from I and J. Therefore we need analogous versions of Lemmas 3, 4, and 5 over number fields (at least over quadratic number fields). The first thing we had to do was write down in detail the proofs of Lemma 3, 4, and 5 over ℚ, since [1] only contains a sketch of the proof of Lemma 3; the proofs of Lemma 4 and 5 were omitted, because they are “similar to that of Lemma 3, but far more tedious … ”. Then we could generalise these lemmas to (quadratic) number fields. In [8] we have given in detail all proofs over (quadratic) number fields. They did not require a very high theoretical level, but an enormous amount of time and patience. Here we will confine ourselves to just listing the results. We will restrict to prime ideals which are principal, as we will only apply the algorithm over quadratic number fields of class number 1. Lemma 3 holds for arbitrary number fields; Lemma 4 too, but with an additional condition for ramification index 2. Lemma 5 only holds for quadratic number fields, but it should be considered as a great success to have such a lemma for real and imaginary quadratic number fields of arbitrary discriminant.

As before, we say that the pair I, J can be P-reduced if every quartic over 𝔒(K) with invariants I, J which is P-adically soluble is equivalent to a quartic over 𝔒(K) with invariants π^{−4}I, π^{−6}J, where π = π_{P} ∈ K is a generator of P, i.e. P = (π) = π · 𝔒(K).

Lemma 3. Let K be an arbitrary number field and P = (π) a prime ideal of K dividing the rational prime p ≠ 2, 3. If

π^{4} | I, π^{6} | J,

then I, J can be P-reduced.

Lemma 4. Let K be an arbitrary number field and P = (π) a prime ideal of K dividing the rational prime 3 with ramification index ε = ε_{P/3}. If

π^{ε+4} | I, π^{3ε+6} | J
or π^{6} | I, π^{9} ∥ J, π^{21} | 4I^{3} − J^{2} and ε = 2
or π^{4} ∥ I, π^{6} ∥ J, π^{3ε+12} | 4I^{3} − J^{2},

then I, J can be P-reduced.

Lemma 5. Let K = ℚ(\sqrt{D}) be a quadratic number field and P = (π) a prime ideal of K dividing the rational prime 2. Then we have

(a) for (2) = P, i.e. D ≡ 5 (mod 8) and π = 2:

2^{7} | I, 2^{10} | J ⟹ I, J can be P-reduced;

(b) for (2) = P_{1}P_{2} with P_{1} ≠ P_{2}, i.e. D ≡ 1 (mod 8) and P = P_{1} or P_{2}:

π^{6} | I, π^{9} | J, π^{10} | π^{3}I + J ⟹ I, J can be P-reduced;

(c) for (2) = P^{2}, i.e. D ≡ 2, 3 (mod 4):

π^{8} | I, π^{11} ∥ J
or π^{9} ∥ I, π^{13} ∥ J
or π^{10} | I, π^{15} | J, π^{16} | π^{5}I + J ⟹ I, J can be P-reduced.

Just as in the case K = ℚ, the conditions in Lemma 3 are necessary and sufficient for P-reducibility, and those in Lemma 5 are only sufficient. The situation in Lemma 4 is more complicated: In the case ε = 1, the conditions are the same as over ℚ; they are necessary and sufficient. For ε ≥ 2, however, they are only sufficient.

Let us now deduce from these lemmas the relevant (I, J) pairs over a quadratic number field K = ℚ(\sqrt{D}). Lemma 5 shows that they depend on the decomposition of the rational prime 2 in K.

• Just as over ℚ, we may assume I and J to be free of 4th and 6th powers of prime elements belonging to primes not dividing 2 and 3.

• Let P = (π) be a prime ideal dividing 3. The ramification index ε of P over 3 is 1 or 2. As over ℚ we may exclude the case π^{8} | I, π^{12} | J. If either

\begin{aligned}ε = 1 & and & & π^{5} | I, π^{9} | J \\ & & or & π^{4} ∥ I, π^{6} ∥ J, π^{15} | 4I^{3} − J^{2}, \end{aligned}

or

ε = 2 and  π^{6} | I, π^{12} | J
or π^{6} | I, π^{9} ∥ J, π^{21} | 4I^{3} − J^{2}
or π^{4} ∥ I, π^{6} ∥ J, π^{18} | 4I^{3} − J^{2},

we replace (I, J) by (π^{−4}I, π^{−4}J).

• For prime ideals dividing 2, we must consider three cases:

(a) D ≡ 5 (mod 8), i.e. (2) = P (π = 2):

We may exclude that 2^{8} | I, 2^{12} | J. If 2^{4} | I, 2^{6} | J, we replace (I, J) by (2^{−4}I, 2^{−6}J). But we also take into consideration the pair (I′, J′) = (2^{4}I, 2^{6}J). If 2^{7} | I′, 2^{10} | J′, i.e. 2^{3} | I, 2^{4} | J, we can restrict to the pair (I, J), otherwise we must consider the two pairs (I, J) and (I′, J′) = (2^{4}I, 2^{6}J).

(b) D ≡ 1 (mod 8), i.e. (2) = P_{1}P_{2} with P_{1} ≠ P_{2} and P_{1} = (π_{1}), P_{2} = (π_{2}):

Let π be π_{1} or π_{2}. As in case (a) we may exclude π^{8} | I, π^{12} | J. If π^{4} | I, π^{6} | J, we replace (I, J) by (π^{−4}I, π^{−6}J). But we also take into consideration the pair (I′, J′) = (π^{4}I, π^{6}J). We have

π^{6} | I′, π^{9} | J′, π^{10} | π^{3}I′ + J′ ⟺ π^{2} | I, π^{3} | J, π^{4} | πI + J.

This means: If (π_{1}^{2} | I, π_{1}^{3} | J, π_{1}^{4} | π_{1}I + J) and (π_{2}^{2} | I, π_{2}^{3} | J, π_{2}^{4} | π_{2}I + J),

then only (I, J) is relevant; if (π_{1}^{2} | I, π_{1}^{3} | J, π_{1}^{4} | π_{1}I + J) and (π_{2}^{2} /| I or π_{2}^{3} /| J or π_{2}^{4} /| π_{2}I + J),

then (I, J) and (π_{2}^{4}I, π_{2}^{6}J) are relevant; if (π_{1}^{2} /| I or π_{1}^{3} /| J or π_{1}^{4} /| π_{1}I + J) and (π_{2}^{2} | I, π_{2}^{3} | J, π_{2}^{4} | π_{2}I + J),

then (I, J) and (π_{1}^{4}I, π_{1}^{6}J) are relevant; if (π_{1}^{2} /| I or π_{1}^{3} /| J or π_{1}^{4} /| π_{1}I + J) and (π_{2}^{2} /| I or π_{2}^{3} /| J or π_{2}^{4} /| π_{2}I + J),

then (I, J), (π_{1}^{4}I, π_{1}^{6}J), (π_{2}^{4}I, π_{2}^{6}J), and (π_{1}^{4}π_{2}^{4}I, π_{1}^{6}π_{2}^{6}J) = (2^{4}I, 2^{6}J) are relevant. So in this case we have to consider one, two, or four pairs of invariants.

(c) D ≡ 2, 3 (mod 4), i.e. (2) = P^{2} with P = (π):

Here we can only exclude that π^{12} | I, π^{18} | J. If π^{8} | I, π^{12} | J, we replace (I, J) by (π^{−8}I, π^{−12}J); if π^{4} | I, π^{6} | J, we replace (I, J) by (π^{−4}I, π^{−6}J). But we also take into consideration the two pairs (I′, J′) = (π^{4}I, π^{6}J) and (I′′, J′′) = (π^{8}I, π^{12}J). If π^{9} ∥ I′′, π^{13} ∥ J′′ (i.e. π ∥ I, π ∥ J), or π^{10} | I′′, π^{15} | J′′, π^{16} | π^{5}I′′ + J′′ (i.e. π^{2} | I, π^{3} | J, π^{4} | πI + J),

then (I′′, J′′) is not relevant. If π^{8} | I′, π^{11} ∥ J′ (i.e. π^{4} | I, π^{5} ∥ J),

then (I′, J′) is not relevant. Thus we have the following cases: If π^{4} | I, π^{5} ∥ J, then only (I, J) is relevant; otherwise, if π ∥ I, π ∥ J or π^{2} | I, π^{3} | J, π^{4} | πI + J, then the two pairs (I, J) and (I′, J′) = (π^{4}I, π^{6}J) = (4I, ±8J) are relevant; otherwise, the three pairs (I, J), (I′, J′) = (π^{4}I, π^{6}J) = (4I, ±8J), and (I′′, J′′) = (π^{8}I, π^{12}J) = (16I, 64J) are relevant.

Hence there are one, two, or three relevant (I, J) pairs in this case.

5. Examples for general 2-descent

When we implemented general 2-descent over real quadratic number fields of class number 1, we saw that the search region on the first three coefficients a, b, c of the quartics often becomes enormously large. Even for the four number fields with the smallest discriminant, namely ℚ(\sqrt{5}), ℚ(\sqrt{8}) = ℚ(\sqrt{2}), ℚ(\sqrt{12}) = ℚ(\sqrt{3}), and ℚ(\sqrt{13}), we had to test many curves in order to find examples with “reasonable” cpu times. We have listed below two examples over each of the four fields. All examples have trivial 2-torsion. In ℚ(\sqrt{5}) and ℚ(\sqrt{13}), the rational prime 2 is inert, i.e. we have either one or two relevant (I, J) pairs. We include one example for each case. In ℚ(\sqrt{2}) and ℚ(\sqrt{3}), the rational prime 2 is ramified, i.e. there are one, two, or three pairs of invariants. For both D we have given one example with one pair and one example with three pairs.

We ran these examples on an SGI Challenge. The fastest example we found, a curve with rank 1 and two (I, J) pairs over ℚ(\sqrt{5}), took 5 m, 30 s.

The curves are defined as E = [a_{1}, a_{2}, a_{3}, a_{4}, a_{6}] where the a_{i} are the standard Weierstrass coefficients, and each coefficient is denoted by a pair of integers (α, β) as in Section 2.

Example 1: K = ℚ(\sqrt{5}), E = [(2, 0), (−2, 0), (−1, −1), (0, 1), (0, −1)]. One (I, J) pair: ((64, 0), (−160, 432)). Three inequivalent nontrivial globally soluble quartics: #1: (a, b, c, d, e) = ((1, 0), (0, 0), (2, 0), (4, −4), (5, 0))

↦ P_{1} = ((0, 0), (1, 0)). #2: (a, b, c, d, e) = ((1, 0), (0, 0), (−46, 30), (−204, 124), (−246, 155))

↦ P_{2} = ((8, −5), (−33, 21)). #3: (a, b, c, d, e) = ((1, 0), (0, 0), (−4, −6), (−4, −12), (1, −7))

↦ P_{3} = ((1, 1), (−1, −2)) = P_{1} + P_{2}. Rank = 2. Total cpu time: 19m, 49s.

Example 2: K = ℚ(\sqrt{5}), E = [(−2, 0), (−2, −1), (2, −2), (−2, 1), (0, 0)]. Two (I, J) pairs: ((14, −6), (−35, 25)) and ((224, −96), (−2240, 1600)). Seven inequivalent nontrivial globally soluble quartics: (I, J) = ((14, −6), (−35, 25)) (cpu time 19s): #1: (a, b, c, d, e) = ((1, 0), (1, −1), (2, −1), (3, −2), (2, −1))

↦ P_{1} = (\frac{1}{4}(−2, 3), \frac{1}{8}(3, 4)). (I, J) = ((224, −96), (−2240, 1600)) (cpu time 8m, 1s): #2: (a, b, c, d, e) = ((1, 0), (0, 0), (8, −4), (−16, 8), (12, −4))

↦ P_{2} = ((−1, 1), (−4, 3)). #3: (a, b, c, d, e) = ((1, 0), (0, 0), (−220, 140), (−2112, 1304), (−5648, 3492))

↦ P_{3} = ((37, −23), (−228, 141)). #4: (a, b, c, d, e) = ((1, 0), (0, 0), (−16, 14), (−40, 24), (−19, 13))

↦ P_{4} = ((3, −2), (−3, 2)) = P_{1} − P_{2} − P_{3}. #5: (a, b, c, d, e) = ((1, 0), (0, 0), (−28, −52), (−192, −280), (−272, −476))

↦ P_{5} = ((5, 9), (−20, −25)) = P_{1} − 4P_{2} − P_{3}. #6: (a, b, c, d, e) = ((1, 0), (0, 0), (−16, −34), (−104, −136), (−99, −195))

↦ P_{6} = ((3, 6), (−11, −10)) = −2P_{1} + 7P_{2} + 3P_{3}. #7: (a, b, c, d, e) = ((1, 0), (0, 0), (−304, 164), (−3248, 1928), (−9924, 6060))

↦ P_{7} = ((51, −27), (−356, 215)) = P_{1} + P_{2}. Rank = 3. Total cpu time: 8m, 20s.

Example 3: K = ℚ(\sqrt{2}), E = [(2, −2), (−2, 2), (−2, 0), (1, 2), (−2, 0)]. One (I, J) pair: ((4, −12), (16, 36)). No nontrivial globally soluble quartics. Rank = 0.

Total cpu time: 31m, 16s.

Example 4: K = ℚ(\sqrt{2}), E = [(0, 0), (2, 1), (0, 0), (1, 0), (−1, −1)]. Three (I, J) pairs: ((3, 4), (5, 8)), ((12, 16), (40, 64)), and ((48, 64), (320, 512)). One nontrivial globally soluble quartic. (I, J) = ((3, 4), (5, 8)) (cpu time 1m, 47s): No nontrivial globally soluble quartics. (I, J) = ((12, 16), (40, 64)) (cpu time 7m, 56s): #1: (a, b, c, d, e) = ((1, 0), (0, 0), (−2, 2), (−4, 2), (0, 2))

↦ P_{1} = ((0, −1), (1, −1)). (I, J) = ((48, 64), (320, 512)) (cpu time 1h, 42m, 31s): No nontrivial globally soluble quartics. Rank = 1. Total cpu time: 1h, 52m, 14s.

Example 5: K = ℚ(\sqrt{13}), E = [(0, 2), (0, −1), (1, 2), (0, 1), (0, 1)]. One (I, J) pair: ((16, −16), (−112, 64)). One nontrivial globally soluble quartic: #1: (a, b, c, d, e) = ((1, −2), (10, 2), (−4, −8), (6, 4), (−1, −1))

↦ P_{1} = (\frac{1}{4}(−3, 0), \frac{1}{8}(−3, −2)). Rank = 1. Total cpu time: 17h, 59m, 10s.

Example 6: K = ℚ(\sqrt{13}), E = [(0, 0), (1, 2), (0, 0), (2, 3), (1, 1)]. Two (I, J) pairs: ((7, −1), (31, −10)) and ((112, −16), (1984, −640)). No nontrivial globally soluble quartics. (I, J) = ((7, −1), (31, −10)) (cpu time 10m, 43s): No nontrivial globally soluble quartics. (I, J) = ((112, −16), (1984, −640)) (cpu time 5h, 35m, 12s): No nontrivial globally soluble quartics. Rank = 0. Total cpu time: 5h, 44m, 4s.

Example 7: K = ℚ(\sqrt{3}), E = [(2, 2), (1, 1), (0, 0), (0, 2), (−2, −2)]. One (I, J) pair: ((52, 24), (−844, −468)). Three inequivalent nontrivial globally soluble quartics. #1: (a, b, c, d, e) = ((2, 1), (0, 2), (8, −6), (−26, 14), (31, −17))

↦ P_{1} = ((−2, −1), (10, 5)). #2: (a, b, c, d, e) = ((2, 1), (2, 0), (2, 0), (−8, 2), (−9, 6))

↦ P_{2} = (\frac{1}{121}(1756, −1405), \frac{1}{1331}(169325, −77612)). #3: (a, b, c, d, e) = ((2, 1), (1, −1), (2, −6), (14, −10), (18, −10))

↦ P_{3} = (\frac{1}{2}(32, 19), \frac{1}{4}(−599, −349)) = −3P_{1} − P_{2}. Rank = 2. Total cpu time: 10h, 56m, 11s.

Example 8: K = ℚ(\sqrt{3}), E = [(−2, 2), (1, −1), (0, 0), (0, −2), (2, −2)]. Three (I, J) pairs: ((163, −94), (−6334, 3657)), ((52, −24), (−952, 576)), and ((304, 160), (9344, 5568)). No nontrivial globally soluble quartics. (I, J) = ((163, −94), (−6334, 3657)) (cpu time 2h, 12m, 13s): No nontrivial globally soluble quartics. (I, J) = ((52, −24), (−952, 576)) (cpu time 8h, 9m, 58s): No nontrivial globally soluble quartics. (I, J) = ((304, 160), (9344, 5568)) (cpu time 20h, 17m, 47s): No nontrivial globally soluble quartics. Rank = 0. Total cpu time: 30h, 39m, 58s.

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. J. E. Cremona, Algorithms for Modular Elliptic Curves, Cambridge University Press, 1992.

3. J. E. Cremona, Classical invariants and elliptic curves, preprint (1996).

4. P. B. Garrett, Holomorphic Hilbert modular forms, Wadsworth, 1990.

5. H. Graf, Konstruktion elliptischer Kurven hohen Ranges über quadratischen Zahlkörpern der Klassenzahl eins, Diploma thesis, Universität des Saarlandes, Saarbrücken, 1995.

6. D. Husemöller, Elliptic curves, Springer-Verlag, 1987.

7. K. Kramer, A family of semistable elliptic curves with large Tate-Shafarevitch groups, Proc. Amer. Math. Soc. 89 No. 3 (1983), 379–386.

8. P. Serf, The rank of elliptic curves over real quadratic number fields of class number 1, PhD thesis, Universität des Saarlandes, Saarbrücken, 1995.

9. J. H. Silverman and J. Tate, Rational points on elliptic curves, Springer-Verlag, 1992.

10. J. Tate, Rational points on elliptic curves, Lectures held at Haverford College, 1961.

Department of Mathematics, University of Exeter, Laver Building, North Park Road, Exeter EX4 4QE, U.K.

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

Fachbereich 9 Mathematik, Universität des Saarlandes, Postfach 151150, D-66041 Saarbrücken, Germany

E-mail address: pascale@math.uni-sb.de