On Computing the Rank of Elliptic Curves

Jeff Achter

May 1992

Where man looks up, and proud to claim His rank within the social frame, Sees a grand system round him roll, Himself its centre, sun and soul! Far from the shocks of Europe; far From every wild, elliptic star.

— Thomas Moore, Epistle II.

The theory of elliptic curves is singular in the way it lies at the intersection of so many branches of mathematics. One can arrive at it by studying the sums of cubes, the theory of doubly-periodic meromorphic functions, or the Jacobians of varieties. One can use the resulting theory to answer the original questions, to test more general theorems of algebraic geometry, or to design public-key cryptosystems.

One of the fundamental arithmetic results is the Mordell-Weil theorem, which says that the group of K-rational points on an abelian variety, and in particular the group of ℚ-rational points on an elliptic curve, is finitely generated. The goal of this paper is to outline the proof of this theorem for elliptic curves with a rational 2-torsion point; to show how the proof yields a partially effective algorithm for computing the rank of the group; and to discuss the results of this algorithm’s implementation.

1 INTRODUCTION TO ELLIPTIC CURVES  May 1992

The theory developed here is embodied in a computer program which computes the rank of elliptic curves. I used this program to estimate the rank of over 100, 000 elliptic curves. Much has been made of Mazur’s description of such a process, in which one computes descents by day and images by night [Tat]. However, I didn’t have an abundance of days and nights in which to perform the computations. Therefore, I ran the computations simultaneously on about sixty SPARCstations. The results of the calculations match up well with those of Brumer and McGuinness [B-M].

This paper should be accessible to an undergraduate student of mathematics, such as myself. Most of the results described here, particularly those in the first section, are readily available in any number of sources. I have particularly relied on the forthcoming book of Silverman and Tate, Rational Points on Elliptic Curves [S-T]. In general, an easily-understood version of any theorem presented here may be found in that book. A readable but more erudite version can be found in either [Sil] or the expositions of Cassels [Cas 1] and Tate [Tat].

The first section is an introduction to some of the basic definitions and properties concerning elliptic curves. The second section presents some of the details of the proof of the Mordell-Weil theorem. Special attention is called to aspects of the proof which lead to a partially effective algorithm. The next section outlines a proof of a more general weak Mordell-Weil theorem. The fourth section describes some of the issues involved in implementing heuristics for computing the rank of the Mordell-Weil group. In the final section I present the results of the computations, and attempt to relate the numerical observations to certain conjectures regarding the rank of elliptic curves.

1 Introduction to Elliptic Curves

Elliptic curves can be defined in several different ways. One of the most concrete descriptions is that an elliptic curve is a nonsingular cubic in two variables. Such a curve may be described by an

1 INTRODUCTION TO ELLIPTIC CURVES  May 1992

equation:

ax^{3} + bx^{2}y + cxy^{2} + dy^{3} + ex^{2} + fxy + gy^{2} + hx + iy + j = 0

Naturally, the coefficients a through j can be taken from any field. In this discussion we will chiefly be concerned with the rational case, where all of the coefficients lie in ℚ, the set of rational numbers.^{1}

The nonsingularity condition just means that the cubic can’t have any cusps or nodes. As it turns out that the theory of singular cubics is in many ways simpler than that of elliptic curves, we really aren’t losing anything with this restriction. Once we insist that the curve be nonsingular, a straight line intersecting the curve in two points must intersect it in a third point, as well. It’s simply a question of counting them correctly.

The easiest case to think of looks like this:

However, sometimes it may seem that a line isn’t intersecting the curve in three places.

In the first case shown above, the line is actually tangent to the cubic at one of the points of intersection. If we simply count the line as intersecting the cubic twice at that point, the general

1Elliptic curves can also be defined as projective curves of genus one. If this definition makes sense to you, you can probably safely skip to the Implementation section.

1 INTRODUCTION TO ELLIPTIC CURVES  May 1992

principle is upheld. Slightly trickier is the second case; the line appears to intersect the curve transversely at two points, and no others.

In this case, we need to move into the projective plane. Actually, we only need one point from it. From one viewpoint, we use the projective plane so that geometric theorems work neatly. For example, we might wish to characterize the intersection of lines by saying “any two distinct lines intersect in exactly one point.” Unfortunately, this isn’t quite true; parallel lines never meet in the affine plane. So to the affine plane we can simply add a “point at infinity” corresponding to each possible line slope. Then even two parallel lines will intersect, since they meet at the point at infinity corresponding to their common slope.

That having been said, we should properly consider the elliptic curve as lying in the projective plane. Even though it may appear that the line in the figure above only intersects the curve twice, it also intersects it at the point at infinity corresponding to all vertical lines. Only one point at infinity must be added to the set of regular points on the elliptic curve in order to have any line intersect the curve in three places. Call that point O.

The important thing to abstract from all of this is that, given a pair of points P and Q lying on an elliptic curve E, we can construct a third point, R, which also lies on the curve. Ultimately, a similar process will yield an actual group law on the points. Let L be the line connecting P and Q. Following the approach of Silverman and Tate, we can define P ∗ Q to be the third point of intersection of L and E. For the reasons outlined above, this does yield a composition law on the set of points on E. This construction will be crucial in defining a group law on the points.

We can write down explicit formulas for computing P ∗ Q in terms of the coefficients of the curve and the coordinates of P and Q. Things are somewhat more manageable if we insist that the curve be in normal form. A nonsingular cubic with at least one rational point is birationally equivalent to a curve of the form y^{2} = x^{3} + ax^{2} + bx + c. We can pick a, b and c so that the points on the first curve are in bijection with the points on a curve in normal form, with the possible

1 INTRODUCTION TO ELLIPTIC CURVES  May 1992

exception of a few easily identified points. Thus, it suffices to restrict our attention to curves defined by

E : y^{2} = x^{3} + ax^{2} + bx + c.

Roughly speaking, the real trace of such a curve will either look like this:

or this:

depending on whether x^{3} + ax^{2} + bx + c has one or three real roots.

In any event, we can now determine explicit formulas for the composition of points. Let P = (x_{0}, y_{0}) and Q = (x_{1}, y_{1}). Initially let’s consider the most straight-forward case, where x_{0} ≠ x_{1}, and neither P nor Q is O.

We start by constructing the line L between P and Q. It is given by y = λx+μ, where the slope λ is easily calculated to be (y_{1} − y_{0})/(x_{1} − x_{0}). We can compute μ from λ: μ = y_{0} − λx_{0} = y_{1} − λx_{1}.

Now, L intersects E in three places. By substituting for y in the equation for E, we find that the intersections are given by the solutions to

(λx + μ)^{2} = x^{3} + ax^{2} + bx + c.

1 INTRODUCTION TO ELLIPTIC CURVES  May 1992

This is a cubic in x, and we know that two of the solutions are x_{0} and x_{1}. The third solution will be the desired x_{2}. So

x^{3} + (a − λ^{2})x^{2} + (b − 2λμ)x + (c − μ^{2}) = (x − x_{0})(x − x_{1})(x − x_{2}).

By looking at the coefficients of x^{2}, we shortly arrive at

\begin{aligned}x_{2} & = & λ^{2} − a − x_{0} − x_{1} \\ y_{2} & = & λx_{2} + μ. \end{aligned}

If P = Q, then following the discussion at the beginning of this section, we take the line tangent to E at P. Computing the tangent to the curve at a particular point is merely a question of differentiating; the slope is found to be λ = dy/dx = (3x^{2} + 2ax + b)/2y. The calculations for μ, x_{2} and y_{2} proceed exactly as above with this different value of λ.

What if P and Q are distinct points but have the same x-coordinate? Then the line L between them intersects E in O, the point at infinity. So P ∗ Q = O.

We should describe the situation where one of the points is O. Recall that all vertical lines contain O. So to find P ∗ O we simply draw the vertical line through P and take the other point of intersection. Thus, O ∗ P is the other point on E with the same x-coordinate as P.

Finally, since the tangent line to E at O has a triple intersection at O, we set O ∗ O = O.

Thus far we have only presented a rule for combining two points. As mentioned earlier, this doesn’t actually define a group law. For example, there is no obvious choice for an identity element. However, we can build on top of this definition to get a proper group law. Let P + Q = (P ∗ Q) ∗ O. In geometric terms, this means take the line connecting P and Q, find its third point of intersection with E, and reflect that point around the x-axis. This does, in fact, define a group law, with O serving as the identity element. Inverses are given by −(x, y) = (x, −y). The details of this are deferred to [S-T] or the industrious reader. With the explicit formulas in hand

2 THE MORDELL-WEIL THEOREM  May 1992

the computations are straight forward, if somewhat tedious. Note that this group is automatically abelian, because of the geometric nature of the definition; the line between P and Q is the same as the line between Q and P.

This description has been a little vague about where these points lie. The pictures presented above probably suggested that the points are real, that is, x and y are in ℝ. However, these addition formulas work equally well if x and y are complex solutions to the defining equation of E. If the coefficients a, b and c are rational, then the set of rational solutions forms a group, as well. The addition formulas combine the coefficients and coordinates through addition, subtraction, multiplication and division. Fields are closed under these operations; so if the coefficients and coordinates lie in a certain field, then the result is in that field, as well. We write E(ℂ) to denote the group of complex points on E, E(ℝ) for the real points, etc. The focus of this project is the structure of the group E(ℚ).

2 The Mordell-Weil Theorem

Once the set E(ℚ) has been endowed with a group law, it makes sense to ask about the structure of that group. It turns out to be easier if we consider the points of finite order and the points of infinite order separately. This section largely provides an overview of results in this area; few theorems are actually proved. Specific proofs are given to the extent that they motivate the algorithm described in section 4.

It makes sense to consider the points of finite and infinite order separately. We say that a point P has m-torsion if mP = O. (Writing mP just means adding P to itself m times.)

2 THE MORDELL-WEIL THEOREM  May 1992

As a starting point, we can easily characterize the 2-torsion points, sometimes denoted E(ℚ)[2]. Clearly, 2O = O. Otherwise, let P = (x_{0}, y_{0}) be a point such that 2P = O, or, equivalently, P = −P. Now, the negative of a point is simply that point reflected around the x-axis. So if a point is its own inverse, it must actually lie on the x-axis; y_{0} = 0. Furthermore, x_{0} is a solution to the equation f(x) = x^{3} + ax^{2} + bx + c = 0. Elementary considerations show that a rational solution to this polynomial equation must actually be an integer. Thus, we get a point of order two for every integral root of f(x). The set of 2-torsion points actually forms a subgroup of E(ℚ). This subgroup, E(ℚ)[2], is either the trivial group, ℤ/2ℤ, or ℤ/2ℤ ⊕ ℤ/2ℤ, depending on whether f(x) has zero, one or three integral roots.

It turns out that in general, for m ≥ 1, P ∈ E(ℚ)[m] will have integer coordinates. Furthermore, let D be the discriminant of f(x), namely, −4a^{3}c + a^{2}b^{2} + 18abc − 4b^{3} − 27c^{2}. Then either y_{0} = 0 (and m = 2), or y^{2}|D. This result is known as the Nagell-Lutz theorem.

Note that this gives an effective method for determining the torsion group of an elliptic curve. First, there is an easy algorithm to check if a point has finite order; simply take P, 2P, 3P, etc., until an m is found such that either mP = O, mP doesn’t have integer coordinates, or the y-coordinate of mP doesn’t divide the discriminant. Since there are only finitely many integers which divide D, the algorithm wil terminate after finitely many steps.

is torsion(a,b,c,P)  /* Is P a torsion point on y^{2} = x^{3} + ax^{2} + bx + c? */

Q=(x,y) ← O

repeat

Q ← Q + P until (Q = O) or (Q isn’t an integer point) or (y^{2} ∤ D) if (Q = O)

return( true ) else

return( false )

Additionally, we only need test a finite set of points for finite order.

torsion group(a,b,c)  /* Find torsion subgroup of y^{2} = x^{3} + ax^{2} + bx + c. */

torsion ← {O}

D ← −4a^{3}c + a^{2}b^{2} + 18abc − 4b^{3} − 27c^{2}

for each divisor y of D

for each integer solution x of x^{3} + ax^{2} + bx + c − y^{2} P ← (x,y)

2 THE MORDELL-WEIL THEOREM  May 1992

if is torsion(a,b,c,P)

torsion ← torsion ∪ {P} return( torsion )

This is a pretty good characterization of the finite part of the group. However, the group E(ℚ) could contain elements of infinite order, as well. That this can happen is evidenced by

y^{2} = x^{3} + 17.

Clearly, the point P = (1/4, 33/8) lies on the curve, since (1/4)^{3} + 17 = 1089/64 = (33/8)^{2}. But its coordinates aren’t integers, while all points of finite order have integer coordinates. So P must be of infinite order.

A priori, it’s not obvious that we will be able to discern any structure, at all, on the torsion-free portion of the E(ℚ). It turns out that, even though the group E(ℚ) may not be finite, it is always finitely generated. There exists a finite set of points so that any other point is equal to some linear combination of that set of points; E(ℚ) ≅ E(ℚ)_{tor} ⊕ ℤ^{r}. In other words, there is a set of points P_{1}, P_{2}, …, P_{r} so that for a Q ∈ E(ℚ), we can find integers c_{1}, …, c_{r} and a T ∈ E(ℚ)_{tor} so that Q = T +c_{1}P_{1} +c_{2}P_{2} +⋯+c_{r}P_{r}. The rank of an elliptic curve is r, the size of a smallest torsion-free generating set.

This theorem was proved by Mordell in 1922, and subsequently generalized to arbitrary abelian varieties over number fields by Weil. An elementary proof of this theorem proceeds in two sections. The first part is the “weak” Mordell-Weil theorem. Let 2E(ℚ) denote the subgroup obtained by doubling all the points in E(ℚ): 2E(ℚ) = {2P |P ∈ E(ℚ)}. The weak Mordell-Weil theorem states that the index [E(ℚ) : 2E(ℚ)] is finite.

For the second part, it is necessary to introduce the notion of a height function. The height function may be thought of as a measure of how big a point is. In order to prove the Mordell-Weil theorem, it’s necessary to show that the height function behaves nicely with respect to the group

2 THE MORDELL-WEIL THEOREM  May 1992

law on the points. Once these two pieces are established, the theorem follows easily.

The proof given here assumes that there is a rational point of order two on the curve. While the theorem is true without this assumption, the proof is somewhat simpler if we can stay in the rational numbers. Now, if E is a curve given in Weierstrass form, then a rational point of order two looks like (x_{0}, 0) with x_{0} an integer. We can make a change of coordinates, (x, y) ↦ (x − x_{0}, y) which sends (x_{0}, 0) to (0, 0). Obviously, such a change won’t affect the structure of the group E(ℚ). Thus, given the restriction that we’re considering curves with a rational two-torsion point, we can assume that E is given by y^{2} = x^{3} + ax^{2} + bx.

2.1 Weak Mordell-Weil Theorem

The goal is to show that the image of the multiplication-by-two map [2] : E(ℚ) → E(ℚ) has finite index. The approach taken here is to break the map [2] into two pieces, and show that the image at each step has finite index. In general, one can show that a subgroup H of some group G has finite index by exhibiting a one-to-one map from G/H into some finite group. This, in turn, can be done by showing that H is the kernel of a map from G to a finite group. Such a method will be used here.

Initially, we need to find a group G and a pair of maps f, g so that the following diagram commutes:

[figure: E(ℚ); E(ℚ); G; f; g; [2]]

In other words, g(f(P)) = [2](P) = 2P. For any particular curve E, we’ll pick a related elliptic curve \overline{E} and maps ϕ : E(ℚ) → \overline{E}(ℚ) and ψ : \overline{E}(ℚ) → E(ℚ). These will be given by explicit formulas. Some of the motivation for the specific choices of \overline{E}, ϕ and ψ is given in [S-T].

2 THE MORDELL-WEIL THEOREM  May 1992

Given a curve E : y^{2} = x^{3} + ax^{2} + bx, define the curve \overline{E} by

\overline{E} : y^{2} = x^{3} + \overline{a}x^{2} + \overline{b}x
\overline{a} = −2a
\overline{b} = a^{2} − 4b.

In a sense, E and \overline{E} are duals of each other. Applying the construction twice yields \overline{\overline{E}} : y^{2} = x^{3} + (−2 · −2a)x^{2} + (4a^{2} − 4(a^{2} − 4b))x, or y^{2} = x^{3} + 4ax^{2} + 16b. This is almost the same as the original curve, E; for if (x_{0}, y_{0}) is a point on E, then (4x_{0}, 8y_{0}) must be a point on \overline{\overline{E}}. It’s similarly easy to identify a point on \overline{\overline{E}} with a point on E. In fact, the two curves are isomorphic via this identification. This will be useful in constructing the maps ϕ and ψ.

Define the map ϕ : E → \overline{E} by (x, y) ↦ (\frac{y^{2}}{x^{2}} , y \frac{x^{2}−b}{x^{2}}). This is well-defined everywhere on E except O, the point at infinity, and the two-torsion point T = (0, 0), which is the only point on E with a zero x-coordinate. We can extend the definition to everywhere on E.

ϕ : E →  \overline{E}
P ↦ (\frac{y^{2}}{x^{2}} , y \frac{x^{2} − b}{x^{2}}) P = (x, y) ≠ T, O
\overline{O}  P = O or P = T.

Here, \overline{O} is the point at infinity on \overline{E}.

One can use an identical construction to get a map from \overline{E} to \overline{\overline{E}}. What we actually want, however, is a map from \overline{E} back to the original curve, E. Thus, we combine the above map with (x, y) ↦ (x/4, y/8) to define ψ.

ψ : \overline{E} →  E
P ↦ (\frac{\overline{y}^{2}}{4\overline{x}^{2}} , \overline{y} \frac{\overline{x}^{2} − \overline{b}}{8\overline{x}^{2}}) P = (\overline{x}, \overline{y}) ≠ \overline{T} , \overline{O}
O  P = \overline{O} or P = \overline{T} .

2 THE MORDELL-WEIL THEOREM  May 1992

The maps ϕ and ψ are partially characterized by the following proposition.

Proposition 2.1 Let E, \overline{E}, ϕ and ψ be defined as above.

1. The maps ϕ and ψ are homomorphisms.

2. The kernel of ϕ is \{O, T \}, and the kernel of ψ is \{\overline{O}, \overline{T} \}.

3. The composition of the maps is multiplication by two, i.e., ψ ∘ ϕ = [2], and ϕ ∘ ψ = \overline{[2]}.

The proof of this proposition is simple, but tedious; the approach is merely indicated here. Proving that ϕ is a homomorphism is a matter of verifying that the group law is preserved: ϕ(P + Q) = ϕ(P) + ϕ(Q). This, in turn, is a matter of turning the crank, and confirming that the rational functions obtained through addition and application of ϕ match up as they should. The price of having such concrete definitions of ϕ and the group law is that many cases must be separately checked. Of course, if ϕ is a homomorphism, then ψ is too, because of the way it was constructed.

Showing that ker ϕ = {O, T } is trivial, given the definition of ϕ; all other points are mapped to “affine points” on \overline{E}. The same argument works for ψ.

Finally, ψ ∘ ϕ(P) = 2P. This, too, can be verified through purely algebraic computations.

Thus far, we have broken multiplication by two into two maps, as promised. It remains to show that the index of the image of each map is finite, that is, [\overline{E}(ℚ) : ϕ(E(ℚ))] and [E(ℚ) : ψ(\overline{E}(ℚ))] are finite. As before, the approach is to (seemingly arbitarily) define a map, and then show that it behaves nicely. The following definitions and lemmas will be stated for the ϕ : E → \overline{E} half of the problem; the analogous statements for ψ can be made and proven in the same way.

We can define a map \overline{α} : \overline{E}(ℚ) → ℚ^{∗}/ℚ^{∗2}. Recall that ℚ^{∗} is the multiplicative group of rational units, and ℚ^{∗2} is the subgroup consisting of perfect squares. So ℚ^{∗}/ℚ^{∗2} is like the nonzero rational numbers, with two elements identified if their quotient is the square of a rational number.

\overline{α} : \overline{E}(ℚ) → ℚ^{∗}/ℚ^{∗2}
\overline{O} ↦ 1 (mod ℚ^{∗2})
\overline{T} ↦ \overline{b} (mod ℚ^{∗2})
(\overline{x}, \overline{y}) ↦ \overline{x} (mod ℚ^{∗2}).

The following proposition characterizes the behavior of \overline{α}.

Proposition 2.2 Let E, \overline{E}, ϕ and \overline{α} be as above.

1. The map \overline{α} : \overline{E}(ℚ) → ℚ^{∗}/ℚ^{∗2} is a homomorphism of groups.

2. The kernel of \overline{α} is ϕ(E(ℚ)), and \overline{α} induces a natural injection \frac{\overline{E}(ℚ)}{ϕ(E(ℚ)} ↪ \frac{ℚ^{∗}}{ℚ^{∗2}} .

3. Let p_{1}, …, p_{r} be the distinct primes dividing \overline{b}. Then the image of \overline{α} is contained in the subgroup of ℚ^{∗}/ℚ^{∗2} with representatives

{(−1)^{ϵ_{0}}p_{1}^{ϵ_{1}}p_{2}^{ϵ_{2}} ⋯ p_{r}^{ϵ_{r}}|ϵ_{i} ∈ {0, 1}} ⊂ ℚ^{∗}/ℚ^{∗2}.

4. The index [\overline{E}(ℚ) : ϕ(E(ℚ))] is finite.

Proving the first part of this proposition is a routine calculation. Things start getting interesting with the proof of the second part. What it means is that any point in \overline{E}(ℚ) whose x-coordinate is a square must come from E(ℚ), via ϕ.

The easy part of the inclusion is that ϕ(E(ℚ)) ⊆ ker \overline{α}. To do this, we must show that if P ∈ E(ℚ), then ϕ(P) is the square of a rational number. But this is obvious from the definition. Certainly, O and T get sent to \overline{O}, and \overline{α} takes \overline{O} to 1 in ℚ^{∗}/ℚ^{∗2}. Otherwise, if P = (x, y), then the x-coordinate of ϕ(P) is y^{2}/x^{2}, which is obviously the square of a rational number.

2 THE MORDELL-WEIL THEOREM  May 1992

It is slightly trickier to show that ker \overline{α} ⊆ ϕ(E(ℚ)); any element of the kernel comes from a point in E(ℚ). So suppose that (\overline{x}, \overline{y}) ∈ \overline{E}(ℚ) gets sent to 1 by \overline{α}. Then \overline{x} = w^{2} for some rational w. We’ll try to find a point in E(ℚ) which would be mapped to (\overline{x}, \overline{y}).

Actually, since ker ϕ contains two elements, we should really be looking for two elements P_{1} = (x_{1}, y_{1}) and P_{2} = (x_{2}, y_{2}), where the P_{i} are rational points on E which are sent to (\overline{x}, \overline{y}). Define these points by

\begin{matrix}x_{1} = \frac{1}{2}(w^{2} − a + \frac{\overline{y}}{w}) & y_{1} = x_{1}w \\ x_{2} = \frac{1}{2}(w^{2} − a − \frac{\overline{y}}{w}) & y_{2} = −x_{2}w. \end{matrix}

There are a couple of ways to show that P_{i} ∈ E(ℚ). The first method is purely mechanical. Simply substitute x_{i} into x^{3} +ax^{2} +bx, and verify that the result is the square of a rational number. This will work, even though the actual computation is something of a nuisance.

A second way uses a little more information about the situation. Initially, we see that x_{1}x_{2} = b.

x_{1}x_{2} = \frac{1}{2}(w^{2} − a + \frac{\overline{y}}{w}) · \frac{1}{2}(w^{2} − a − \frac{\overline{y}}{w})
= \frac{1}{4}[(w^{2} − a)^{2} − \frac{\overline{y}^{2}}{w^{2}} ]
= \frac{1}{4}[(\overline{x} − a)^{2} − \frac{\overline{y}^{2}}{\overline{x}}]
= \frac{1}{4} \frac{\overline{x}^{3} − 2a\overline{x}^{2} + a^{2}\overline{x} − \overline{y}^{2}}{\overline{x}} .

Now we know that (\overline{x}, \overline{y}) is on \overline{E}(ℚ), so \overline{y}^{2} = \overline{x}^{3} − 2a\overline{x}^{2} + (a^{2} − 4b)\overline{x}. Applying this knowledge to the last line, we find that x_{1}x_{2} = b.

How does this help us prove that P_{i} ∈ E(ℚ)? We have to show that y_{i}^{2} = x_{i}^{3} + ax^{2} + bx; or, equivalently, that \frac{y_{i}^{2}}{x_{i}^{2}} = x_{i} + a + \frac{b}{x_{i}}. Now, \frac{y_{i}^{2}}{x_{i}^{2}} = w^{2} by the definition of y_{i}, and we know that b = x_{1}x_{2}. So we’ve reduced the problem to showing that

w^{2} = x_{1} + a + x_{2}.

2 THE MORDELL-WEIL THEOREM  May 1992

But this comes from the definition of x_{1} and x_{2};

x_{1} + x_{2} = \frac{1}{2}(w^{2} − a + \frac{\overline{y}}{w}) + \frac{1}{2}(w^{2} − a − \frac{\overline{y}}{w}) = w^{2} − a.

Thus, ϕ(P_{1}) = ϕ(P_{2}) = (\overline{x}, \overline{y}) = (w^{2}, \overline{y}), and ker \overline{α} ⊆ ϕ(E(ℚ)). The kernel of \overline{α} is ϕ(E(ℚ), and so \overline{α} induces a one-to-one map \overline{E}(ℚ)/ϕ(E(ℚ)) ↪ ℚ^{∗}/ℚ^{∗2}.

We now turn to the third part of the proposition. Let S = {p_{1}, p_{2}, …, p_{r}} be the set of primes which divide \overline{b}. Let R^{∗} be the subgroup of ℚ^{∗} given by

R^{∗} = {±p_{1}^{e_{1}}p_{2}^{e_{2}} ⋯ p_{r}^{e_{r}}|e_{i} ∈ ℤ}.

The claim is that im \overline{α} ⊆ R^{∗}/R^{∗2} ⊂ ℚ^{∗}/ℚ^{∗2}. In other words, let \overline{P} = (\overline{x}, \overline{y}) be a rational point on \overline{E}. It turns out that we can write \overline{x} = \frac{m}{e^{2}} and \overline{y} = \frac{n}{e^{3}} , where m, e and n are integers, and gcd(m, e) = gcd(n, e) = 1. What we have to show is that if p|m and p ∉ S, then p^{2}|m. (Since e is squared, we don’t have to worry about its factors.)

Initially, we substitute \overline{x} = m/e^{2} and \overline{y} = n/e^{3} into the equation for \overline{E}. We get

\begin{aligned}\frac{n^{2}}{e^{6}} & = & \frac{m^{3}}{e^{6}} + \overline{a}\frac{m^{2}}{e^{4}} + \overline{b}\frac{m}{e^{2}} \\ n^{2} & = & m^{3} + \overline{a}m^{2}e^{2} + \overline{b}e^{4}m \\ n^{2} & = & m · (m^{2} + \overline{a}me^{2} + \overline{b}e^{4}). \end{aligned}

Supposes q divides m but not (m^{2} + \overline{a}me^{2} + \overline{b}e^{4}). Then q^{2}|m, as well, for if q|n^{2} then q^{2}|n^{2}. Suppose q divides (m^{2} + \overline{a}me^{2} + \overline{b}e^{4}) but not m. Then q can’t divide \overline{b}e^{4}, either. In particular, q

divides neither e nor m, and so we don’t have to worry about it.

Finally, suppose q divides both m and (m^{2} + \overline{a}me^{2} + \overline{b}e^{4}). Then q|(m^{2} + \overline{a}me^{2}), and the last term \overline{b}e^{4} must also be a multiple of q. Since q|m we can’t have q|e. Therefore, q must divide \overline{b}.

This gives a fairly complete picture of what kinds of primes can divide m. (We don’t have to

2 THE MORDELL-WEIL THEOREM  May 1992

worry about e, since primes which divide e automatically occur with even exponent in x = m/e^{2}.) For most primes p, an even power of p must divide m. The only way that a prime can not have an even power of p dividing m/e^{2} is if p|\overline{b}. This, of course, is precisely the claim.

The final part of the proposition follows easily. The size of R^{∗}/R^{∗2} is easily seen to be 2^{r+1}, and \overline{E}(ℚ)/ϕ(E(ℚ)) maps injectively into it. So the index [\overline{E}(ℚ) : ϕ(E(ℚ))] ≤ 2^{r+1}, and is certainly finite.

So now we know that the multiplication map [2] : E(ℚ) → E(ℚ) factors through the group on a related curve \overline{E} via E(ℚ) →^{ϕ} \overline{E}(ℚ) →^{ψ} E(ℚ). The most recent proposition shows that the images at each step, ϕ(E(ℚ)) and ψ(\overline{E}(ℚ)) are finite. The ultimate goal is the result that the index [E(ℚ) : 2E(ℚ)] = [E(ℚ) : ψϕ(E(ℚ))] is finite. The final step doesn’t require any knowledge of elliptic curves; it’s a simple question of group theory.

Proposition 2.3 Let A and B be abelian groups with homomorphisms ϕ : A → B and ψ : B → A, such that ψ ∘ ϕ = [2]_{A} and ϕ ∘ ψ = [2]_{B}. Also, suppose that [B : ϕ(A)] and [A : ψ(B)] are finite. Then the index [A : 2A] is finite.

The proof is straight-forward. Take a_{1}, …, a_{m} and b_{1}, …, b_{n} to be coset representatives for ψ(B) in A and ϕ(A) in B, respectively. One shows that the set {a_{i} + ψ(b_{j})} is a complete set of coset representatives for 2A in A.

Applying this proposition we find that [E(ℚ) : 2E(ℚ)] is finite, as desired.

2.2 Height functions

The other half of the Mordell-Weil theorem requires a notion of the height of a point. This yields a tool which is useful in establishing a set’s finitude.

The classic method of descent uses the absolute value function in order to show that, for example, a given polynomial has no integer solutions. One shows that, given a particular integer solution, one can produce another solution whose absolute value is strictly smaller. This yields a

2 THE MORDELL-WEIL THEOREM  May 1992

contradiction. On one hand, one claims that there is an infinite sequence of integers with strictly decreasing absolute value. On the other hand, the set of integers with absolute value less than some particular value is finite.

This notion of the size of a solution works quite well for studying integers. However, it is not as well suited to studies of rational solutions to equations. The key fact used in the strategy outlined above is that, for any bound B, the set {x ∈ ℤ||x| ≤ B} is finite. If we let x take on rational values, however, this assertion is no longer true. For example, one could take the set \{1, \frac{1}{2}, \frac{1}{3}, …\}. We need a slightly different measure of the size of a rational number.

Let’s define the height of a rational number x to be the maximum of the absolute value of its numerator and denominator. More formally, let x = \frac{m}{n}, where m and n are relatively prime. Define the height function by H(x) = max{|m|, |n|}. This enjoys the same sort of finiteness property described above. Specifically, for any B, the set {x ∈ ℚ|H(x) ≤ B} is finite.

This definition can be extended to the rational points on an elliptic curve. Let H(P) = H((x, y)) = H(x). A similar finiteness property still holds, namely, {P ∈ E(ℚ)|H(P) ≤ B} is finite for any fixed bound B. This is because there are only finitely many choices for the x-coordinate, and any value of x yields at most two points on the curve E.

The height function behaves somewhat multiplicatively on the rationals; it makes sense to compare H(x)H(y) to H(xy). Notationally, however, it’s desirable to have a function which acts additively. There is an addition law on points on an elliptic curve, while there’s no multiplication function. So define the logarithmic height by h(x) = log H(x). For any rational number x, H(x) is at least 1, and so h(x) is a nonnegative real number. This definition is extended in the obvious way to rational points on elliptic curves.

So much for the motivation of h. In order to prove the Mordell-Weil theorem, one must establish certain properties of this height function.

Proposition 2.4 Define the height function h : E(ℚ) → ℝ as above.

2 THE MORDELL-WEIL THEOREM  May 1992

1. For every B ∈ ℝ, the set {P ∈ E(ℚ)|h(P) ≤ M} is finite.

2. For every P_{0} ∈ E(ℚ) there is a constant κ_{0}, depending only on P_{0} and E, such that h(P + P_{0}) ≤ 2h(P) + κ_{0} for all P ∈ E(ℚ).

3. There is a constant κ, depending only on E, such that h(2P) ≥ 4h(P) − κ.

This proposition relates the addition law on the curve to a number-theoretic value. Ultimately, it will allow us to reduce the geometric question to a number-theoretic one, and then use number theory in order to obtain an answer.

The first part of this proposition follows from the disccusion above; the proof of the latter two parts is left to [S-T]. Essentially, one works with the concrete descriptions of the addition laws, and attempts to compute the height of the resulting value. This can be a little intricate. The quotients given by the addition formulae aren’t necessarily in “lowest form.” One must show that there isn’t too much cancellation between the numerator and the denominator, in order to put a lower bound on the resulting height.

2.3 Mordell-Weil Theorem

Given the theorem of the height function and the weak Mordell-Weil theorem, we can prove the desired theorem.

Proposition 2.5 Let E be an elliptic curve with a rational point of order two. Then E(ℚ) is finitely generated.

The weak Mordell-Weil theorem says that the group E(ℚ)/2E(ℚ) is finite, so we can take a finite set of representatives Q = {Q_{1}, Q_{2}, …, Q_{n}} for the cosets of 2E(ℚ) in E(ℚ).

Recall that the second part of proposition 2.4 says for each Q_{i} there is a κ_{i}, so that h(Q_{i} + P) ≤ 2h(P) + κ_{i} for all rational points P. Since there are only finitely many Q_{i}, we can take κ′ to be

2 THE MORDELL-WEIL THEOREM  May 1992

the maximum of the κ_{i}. Thus, h(Q_{i} + P) ≤ 2h(P) + κ′ for all Q_{i} ∈ Q and P ∈ E(ℚ). Let κ be the constant from the same proposition such that h(2P) ≥ 4h(P) − κ. Then the set R = {P ∈ E(ℚ)|h(P) ≤ κ′ + κ} is finite, as well. As we will see shortly, Q ∪ R generates all of E(ℚ).

To prove this claim, we must show that any P ∈ E(ℚ) can be written as a combination of elements of Q ∪ R.

In a way, this proof is inductive. Indeed, if the error-terms κ and κ_{0} were zero, one could prove the theorem by induction on the height. Even with the error term, however, the proof is elementary.

The point P must have a coset representative Q_{i_{1}} in E(ℚ)/2E(ℚ); P −Q_{i_{1}} ∈ 2E(ℚ). So there’s a P_{1} such that P −Q_{i_{1}} = 2P_{1}. Similarly, we can find an index i_{2} and a point P_{2} so that P_{1}−Q_{i_{2}} = 2P_{2}. In fact, we can continue this chain as far as we like. Substituting after the m^{th} iteration, we find

\begin{aligned}P & = & Q_{i_{1}} + 2(Q_{i_{2}} + 2(Q_{i_{3}} + · + P_{m})) \\ & = & Q_{i_{1}} + 2Q_{i_{2}} + 4Q_{i_{3}} + ⋯ + 2^{m−1}Q_{i_{m}} + 2^{m}P_{m}. \end{aligned}

Each of the Q_{i_{j}} is in Q, of course. If we can show that we can pick a (finite) m so that P_{m} ∈ Q ∪ R, we’re finished. The strategy is to show that the height decreases enough at each step to force P_{m} into R. We want to show that at, say, the j^{th} step of the chain, the size is decreasing. Proposition 2.4 gives us

4h(P_{j}) ≤ h(2P_{j}) + κ = h(P_{j−1} − Q_{i_{j}}) + κ ≤ 2h(P_{j−1}) + κ′ + κ.

We can isolate h(P_{j}).

\begin{aligned}h(P_{j}) & ≤ & \frac{1}{2}h(P_{j−1}) + \frac{κ′ + κ}{4} \\ & = & \frac{3}{4}h(P_{j−1}) − \frac{1}{4}(h(P_{j−1}) − (κ′ + κ)). \end{aligned}

2 THE MORDELL-WEIL THEOREM  May 1992

If h(P_{j−1}) ≤ κ′ + κ, then we’re done, since P_{j−1} ∈ R. Otherwise, h(P_{j}) ≤ 3/4h(P_{j−1}). The height is decreasing by a factor of 3/4 at every step. After some finite number of steps, the height of h(P_{m}) will be less than the bound κ′ + κ, and so P_{m} will be in R. This concludes the proof of the Mordell-Weil theorem.

2.4 Effectivity

The proof of the Mordell-Weil theorem, while correct, in a sense is not the best possible. The proof is nonconstructive; it tells us that the rank is finite, without specifying how to find it. Almost every step seems computable. However, at the last (and crucial) step, there is no known algorithm guaranteed to solve the problem which arises. In any given case, however, any one of several informal heuristics may prove sufficient to compute the rank. What this requires is a slightly closer analysis of what is happening in the proof of the weak Mordell-Weil theorem.

Before that, we should review some facts about the structure of E(ℚ). There is a torsion part of the group. This has a 2-torsion component, E(ℚ)[2], and another (finite) component, E(ℚ)_{tor−2}. As for the torsion-free part, we know that it is finitely generated as a ℤ-module. If r is the rank of the group, then the torsion-free portion E(ℚ)_{∞} is isomorphic to ℤ^{r}. In summary, we have

E(ℚ) ≅ E(ℚ)[2] ⊕ E(ℚ)_{tor−2} ⊕ E(ℚ)_{∞} ≅ (ℤ/2ℤ)^{s} ⊕ E(ℚ)_{tor−2} ⊕ ℤ^{r},

where s is the number of rational points of order two on E, and E(ℚ)_{tor−2} is a finite group with order relatively prime to two. The weak Mordell-Weil theorem says something about E(ℚ)/2E(ℚ). This group looks like

E(ℚ)/2E(ℚ) ≅ (\frac{ℤ/2ℤ}{2ℤ})^{s} ⊕ E(ℚ)_{tor−2}/2E(ℚ)_{tor−2} ⊕ (ℤ/2ℤ)^{r}
≅ (ℤ/2ℤ)^{s} ⊕ (ℤ/2ℤ)^{r}
≅ (ℤ/2ℤ)^{s+r}.

2 THE MORDELL-WEIL THEOREM  May 1992

So [E(ℚ) : 2E(ℚ)] = s + r. It’s easy to compute s. Recall that a point has order two only if its y-coordinate is zero. We’re working with the representation y^{2} = x^{3} + ax^{2} + bx for E. So points of order two are given by solutions to x^{3} + ax^{2} + bx = x(x^{2} + ax + b) = 0. It’s not surprising that we find (0, 0) ∈ E(ℚ)[2]. The other two solutions will be rational if and only if

x = \frac{−a ± \sqrt{a^{2} − 4b}}{2}

is rational, that is, if and only if a^{2} − 4b is a perfect square. This gives us an easy way to determine s.

Now, if one is careful in the proof of proposition 2.3, and then applies the result to the specific case here, one can show that

[E(ℚ) : 2E(ℚ)] = \frac{[E(ℚ) : ψ(\overline{E}(ℚ))][\overline{E}(ℚ) : ϕ(E(ℚ))]}{[ker ψ : ker ψ ∩ ϕ(E(ℚ))]}.

Essentially, this consists of guarding against overcounting in the enumeration of coset representatives. We can see that \overline{T} ∈ ϕ(E(ℚ)) if and only if \overline{b} = a^{2} − 4b is a perfect square. This means that ker ψ ∩ ϕ(E(ℚ)) is either \{\overline{O}\} or \{\overline{O}, \overline{T} \} depending on whether a^{2} − 4b is not or is a perfect square, respectively. The index [ker ψ : ker ψ ∩ ϕ(E(ℚ))] is therefore 2 − s. In summary,

[E(ℚ) : 2E(ℚ)] = 2^{r+s} = \frac{[E(ℚ) : ψ(\overline{E}(ℚ))][\overline{E}(ℚ) : ϕ(E(ℚ))]}{2^{2−s}}.

This gives us an explicit formula for the rank.

2^{r} = \frac{[E(ℚ) : ψ(\overline{E}(ℚ))][\overline{E}(ℚ) : ϕ(E(ℚ))]}{4}.

By the isomorphism in proposition 2.2, \overline{α}(\overline{E}(ℚ)) ≅ \overline{E}(ℚ)/ϕ(E(ℚ)). Similarly, α(E(ℚ)) ≅ E(ℚ)/ψ(\overline{E}(ℚ)). So we get the extremely useful formula

2^{r} = \frac{#α(E(ℚ)) · #\overline{α}(\overline{E}(ℚ))}{4}.

The upshot of all of this is that we can compute the rank of an elliptic curve if we can compute the size of im α and im \overline{α}.

As before, this discussion will focus on \overline{α}; the argument for α proceeds in the same way. We know that \overline{α} maps \overline{E}(ℚ) into R^{∗}/R^{∗2}. To determine that image, we have to figure out which points in \overline{E}(ℚ) give rise to nontrivial elements of R^{∗}/R^{∗2}. Evidently, \overline{O} gets sent to the identity element. Also, \overline{T} will be mapped into R^{∗}/R^{∗2}. It remains to find out which rational numbers, modulo squares, can occur as the \overline{x}-coordinates of points on \overline{E}. As before, write \overline{x} = m/e^{2}, \overline{y} = n/e^{3}. Then n^{2} = m · (m^{2} + \overline{a}me^{2} + \overline{b}e^{4}).

Let q be the squarefree part of m. We saw above that q must divide (m^{2} + \overline{a}me^{2} + \overline{b}e^{4}) and \overline{b}, as well. Let qq′ = \overline{b}, qm′ = q. Then

n^{2} = m′q · (q^{2}m^{′2} + \overline{a}qm′e^{2} + qq′e^{4}).

Since q divides everything on the left side, it divides n^{2}, too. Because q is squarefree and q|n^{2}, we have q|n. Write qn′ = n.

\begin{aligned}(qn′)^{2} & = & m′q · (q^{2}m^{′2} + \overline{a}qm′e^{2} + qq′e^{4}) \\ n^{′2} & = & m′ · (qm^{′2} + \overline{a}m′e^{2} + q′e^{4}). \end{aligned}

At this point, m′ and (qm^{′2} + \overline{a}m′e^{2} + q′e^{4}) are relatively prime, and their product is a square. This means each of them is a square, and thus n′ has a factorization n′ = MN, where

3 WEAK MORDELL-WEIL: REPRISE  May 1992

\begin{aligned}M^{2} & = & m′ \\ N^{2} & = & qm^{′2} + \overline{a}m′e^{2} + q′e^{4}. \end{aligned}

Thus, we can eliminate m′.

\begin{aligned}M^{2}N^{2} & = & M^{2}(qM^{4} + \overline{a}M^{2}e^{2} + q′e^{4}) \\ N^{2} & = & qM^{4} + \overline{a}M^{2}e^{2} + q′e^{4}. \end{aligned}

So if there is a point \overline{E}(ℚ) which gives a nontrivial element of R^{∗}/R^{∗2}, it will correspond to a solution to the last equation given above, where qq′ = \overline{b}. This is how we can attempt to craft an algorithm to determine the rank of an elliptic curve. Simply take all integer factorizations \overline{b} = qq′, and see whether the resulting equation has a nontrivial solution. The curve corresponding to such an equation is often called a covering space. Every equation with an integral solution, or covering space with an integral point, corresponds to an element of α(\overline{E}(ℚ)). So we can compute #α and #\overline{α}, and thus compute r.

This would work fine, were we able to determine whether the diophantine equations which arise admit solutions. Unfortunately, there is no known finite decision procedure which will determine if such a solution exists. This is not to say that no such decision procedure exists. While it is known that no algorithm can solve arbitrary diophantine equations, this doesn’t rule out a method for solving this specific class of diophantine problems.

At any rate, this is the obstacle to effectivity in the Mordell-Weil theorem.

3 Weak Mordell-Weil: Reprise

What we have just seen for elliptic curves with a rational 2-torsion point actually holds true in a much broader context. If E is any elliptic curve, then the group E(ℚ) is finitely generated. Also, if

3 WEAK MORDELL-WEIL: REPRISE  May 1992

K is a number field, that is, a finite extension of ℚ contained in ℂ, then E(K) is finitely generated. And we needn’t restrict our attention to elliptic curves; if A is any abelian variety defined over a number field K, then A(K) is finitely generated. In this section we will outline a proof of a more general weak Mordell-Weil theorem, namely, A(K)/mA(K) is finite for any integer m ≥ 1.

Not surprisingly, this theorem will require somewhat more advanced tools. Before, we could describe everything in terms of explicit computations with rational functions. The price of the increased generality of the theorem is an increased abstraction in the method of proof. The method given here will require elements of Galois theory, algebraic number theory, and a little bit of Kummer theory. Most of it follows the approach of Chapter VIII in [Sil]. A more explicit development of the necessary Kummer theory may be found in [Lan].

We should fix some notation before we start. Let A be an abelian variety. By analogy with elliptic curves, let A(K) denote the group of points defined over some field K. We will always take K to be a number field, and \overline{K} its algebraic closure. For any integer m, [m] : A → A is the multiplication-by-m map; A(K)[m] is the set of points of order m; and mA(K) = {mP |P ∈ A(K)}. Finally, let A[m] = A(\overline{K})[m].

The general strategy is to introduce a pairing between A(K)/mA(K) and another group, in this case a Galois group of a certain extension L over K. Then A(K)/mA(K) is finite if and only if Gal(L, K) is finite, that is, if and only if L is a finite extension. To deduce the finitude of [L : K], we will combine the fact that A has good reduction almost everywhere with considerations from algebraic number theory.

As an initial reduction step, we can show that it suffices to assume that all the m-torsion points are defined over K. Let d be the dimension of A. We shall see below that A(\overline{K})[m] ≅ (ℤ/mℤ)^{2d}, and thus is finite. Since the coordinates of each point satisfy some algebraic relation (depending on the definition of A), each point P ∈ A(\overline{K})[m] is defined over a finite extension K(P) over K. The m-torsion points actually lie in a finite extension K′ of K, taken to be the compositum of the

3 WEAK MORDELL-WEIL: REPRISE  May 1992

(finitely many) K(P). The following proposition shows that it suffices to consider K = K′ in order to prove the weak Mordell-Weil theorem.

Proposition 3.1 Let K′ be a Galois extension of K such that A(K′)/mA(K′) is finite. Then A(K)/mA(K) is finite, too.

One can prove this by showing that there is an exact sequence

0 → \frac{A(K) ∩ mA(K′)}{mA(K)} → \frac{A(K)}{mA(K)} → \frac{A(K′)}{mA(K′)}.

The group A(K)∩mA(K′)/mA(K) injects into the set Map(Gal(K′, K), A[m]). But Gal(K′, K) and A[m] are both finite, and so A(K) ∩ mA(K′)/mA(K) is finite. Since the outside terms of the exact sequence are finite, so is the middle term, A(K)/mA(K). We actually won’t need this until a little later in the proof; but this justifies our assumption that A[m] ⊂ A(K), and A is defined over K.

3.1 Multiplication by [m]

We will need a good understanding of the map [m] in order for the proof to work. By using the techniques of algebraic geometry, we will arrive at the following proposition.

Proposition 3.2 Let A be an abelian variety of degree d defined over a field F, m a positive integer relatively prime to charF. Then the map [m] : A → A is a surjective, separable morphism of degree m^{2d}. In particular, ker[m] = A(F)[m] ≅ (ℤ/mℤ)^{2d}.

There isn’t space here to properly develop all of the necessary concepts ab initio. Elementary algebraic geometry (and quite a bit more) may be found in [Har]. As a starting point, assume Mumford’s theorem of the cube [Mum 2]:

3 WEAK MORDELL-WEIL: REPRISE  May 1992

Proposition 3.3 Let D be a divisor on A, I ⊆ {1, 2, 3} and S_{I} a morphism

\begin{aligned}S_{I} : & A × A × A & → & A \\ & (x_{1}, x_{2}, x_{3}) & ↦ & ∑_{i∈I} x_{i}. \end{aligned}

Then

∑_{i∈I}(−1)^{|I|}S_{I}^{∗}D = 0.

An easy corollary is that if f, g and h are morphisms from A to A, and D is a divisor on A, then

(f + g + h)^{∗}D − (f + g)^{∗}D − (f + h)^{∗}D − (g + h)^{∗}D + f^{∗}D + g^{∗}D + h^{∗}D ∼ 0.

We’ll now use this information to characterize [m]. Take f to be [m], g the identity function [1], and h = [−1] the inverse map. Clearly, [m] + [m′] = [m + m′]. Then

[m]^{∗}D − [m + 1]^{∗}D − [m − 1]^{∗}D + [m]^{∗}D + D + [−1]^{∗}D ∼ 0.

Taking a cue from [Hin] observe that in general, given a group G and a map f : ℤ → G such that f(n + 1) + f(n − 1) − 2f(n) = a, it’s true that f(n) = ((n^{2} − n)/2)a + n(f(1) − f(0)) + f(0). The proof of this is an easy induction on n. Applying this lemma with f(n) = [n]^{∗}D yields

[m]^{∗}D ∼ \frac{m^{2} + m}{2}D + \frac{m^{2} − m}{2}[−1]^{∗}D.

This can be used to show that [m] is surjective. Take D to be an ample divisor on A, 0 ∉ D. Since [−1] is an automorphism of A, [−1]^{∗}D is ample, as well. Applying the formula gives [m]^{∗}D is an ample divisor. Certainly [m]^{∗}D ∩ker[m] = ∅. But [m]^{∗}D is ample; therefore, ker[m] must be of

3 WEAK MORDELL-WEIL: REPRISE  May 1992

dimension zero. Since dim ker[m] + dim im [m] = d, we have dim im [m] = d, and [m] is surjective of finite type. Let p = charF. The map [m] is separable if p does not divide the degree of [m].

It remains to prove the second part of the proposition. On an abelian variety of dimension d, it makes sense to talk about the intersection index of a set of d divisors. In general, if we have a surjective morphism f : X → Y, and divisors D_{1}, …, D_{d} on Y, then the intersection numbers are related by

(f^{∗}D_{1} · f^{∗}D_{2} ⋯ f^{∗}D_{d}) = (degf)(D_{1} ⋯ D_{d}).

Now, pick an ample symmetric divisor D on A, that is, [−1]^{∗}D = D. Then we know that [m]^{∗}D ∼ m^{2}D. Taking the d-fold self-intersection of D yields

deg[m] \overbrace{(D · D ⋯ D)}^{d times} = ([m]^{∗}D · [m]^{∗}D ⋯ [m]^{∗}D)
= (m^{2}D · m^{2}D ⋯ m^{2}D)
= m^{2d}(D · D ⋯ D)
deg[m] = m^{2d}.

This gives the size of the m-torsion group, m^{2d}. If m is prime, this is sufficient to characterize the structure of the group. Otherwise, one can prove by induction on the factorization of m that A[m] ≅ (ℤ/mℤ)^{2d}. This completes the proof of proposition 3.2.

3.2 The Kummer pairing

If L is any extension of K, then the Galois group Gal(L, K) acts on points P ∈ A(L) by acting on the coordinates of P. Now, it turns out that the map [m] : A → A is surjective. This means that, for any point P on the variety, we can find a point Q so that [m]Q = mQ = P. With this in mind, we can define the Kummer pairing:

κ : Gal(\overline{K}, K) × A(K) → A[m]
σ × P ↦ σ(Q) − Q for some Q : mQ = P.

It’s not obvious that this is actually a well-defined map; for we have some freedom about the choice of Q, and the result might not actually be an m-torsion point. To prove the latter, observe that

m(κ(σ, P)) = m(σ(Q) − Q) = mσ(Q) − mQ = σ(mQ) − P = σ(P) − P = O.

The last step follows because P ∈ A(K), and σ holds K fixed. As for the former contention, suppose that mQ = mR = P. Then m(R − Q) = 0, and R′ = R − Q ∈ A[m]. Writing R = Q + R′,

σ(R) − R = σ(Q + R′) − (Q + R′) = σ(Q) − Q + σ(R′) − R′ = σ(Q) − Q + R′ − R′ = σ(Q) − Q.

The penultimate step works because we assumed that A[m] ⊂ A(K), so R′ is defined over K and σ holds R′ fixed. This shows that the pairing is well-defined.

One can further show that κ(σ + τ, P) = κ(σ, P) + κ(τ, P), and κ(σ, P + Q) = κ(σ, P) + κ(σ, Q). In other words, κ is a bilinear pairing.

We can characterize the kernel of this pairing on the left and the right. Let L = K([m]^{−1}A(K)) be the compositum of K(Q) for all Q ∈ A(\overline{K}) such that mQ ∈ A(K).

Proposition 3.4 The kernel of the Kummer pairing κ is Gal(\overline{K}, L) on the left, and mA(K) on the right.

As an immediate corollary, we find that the induced pairing

Gal(L, K) × A(K)/mA(K) → A[m]

3 WEAK MORDELL-WEIL: REPRISE  May 1992

is a perfect bilinear pairing. Since A[m] is finite, if we can show that L is a finite extension then we know that A(K)/mA(K) is finite.

First, consider the kernel on the left. Suppose that σ ∈ Gal(\overline{K}, L). Then κ(σ, P) = σ(Q) − Q = O, since Q is defined over L, and σ holds L fixed. For the other inclusion, suppose that σ ∈ Gal(\overline{K}, K) is such that κ(σ, P) = O for all P ∈ A(K). Then σ holds [m]^{−1}P fixed for all P. This is precisely how L is defined; σ fixes L, and σ ∈ Gal(\overline{K}, L).

Second, consider the kernel on the right. Suppose that κ(σ, P) = O for all σ ∈ Gal(\overline{K}, K). Then for any Q such that mQ = P, we have σ(Q) − Q = O for all σ. Since Q is held fixed by all the σ, it is defined over K; P = mQ ∈ mA(K). It’s similarly easy to show that any P ∈ mA(K) is in the kernel on the right.

Now we have to show that L is a finite extension of K. To do this, we will prove that L is ramified at only finitely many places of K, and that the group Gal(L, K) is abelian of exponent m. This will require information about how the reduced abelian variety A(K) behaves at at residue fields corresponding to nonarchimedean valuations v. Then, we use this knowledge to show that [L : K] is finite.

It’s easy to show that L is an abelian extension of exponent m over K. This simply means that Gal(L, K) is abelian, and every σ ∈ Gal(L, K) has order dividing m. The kernel on the left of the Kummer pairing is Gal(\overline{K}, L), and so we have an injection

Gal(L, K) ↪ Hom(A(K), A[m]).

Recall that A[m] is abelian of exponent m. The set of homomorphisms Hom(A(K), A[m]) forms a group with the law (σ + τ)(P) = σ(P) + τ(P). Since A[m] is abelian, so is Hom(A(K), A[m]). Furthermore, any map from a group into A[m] will necessarily be of order dividing m. Since Gal(L, K) injects into the group Hom(A(K), A[m]), it too enjoys these properties.

3 WEAK MORDELL-WEIL: REPRISE  May 1992

3.3 Reduction

We now have to show that L is unramified outside of some finite set of places, S. This requires a theory of the reduction of an abelian variety. Arguably, such a discussion should take place using the language of schemes. Instead, I shall try to keep the exposition as concrete as possible. Initially we will take a detailed look at the reduction mod p of rational elliptic curves. The concepts introduced will be generalized to the reduction of an abelian variety at a nonarchimedean place.

Let E be an elliptic curve y^{2} = x^{3} + ax^{2} + bx + c, where a, b and c are integers, and let p be a prime. We can look at the curve “mod p.” Let ã denote the coset corresponding to a in ℤ/pℤ. Then there is a curve Ẽ : y^{2} = x^{3} +ãx^{2} +b̃x+c̃defined over ℤ/pℤ. When will this curve be nonsingular? Recall that a curve is singular if and only if its discriminant D is nonzero. The argument which demonstrates this in the rational case also works in ℤ/pℤ. The discriminant of Ẽ is simply D̃, since reduction mod p commutes with the various arithmetic operations. Thus, Ẽ is singular only when p|D, for that is precisely when D ≡ 0 mod p. We say that a curve has good reduction at p if the reduced curve Ẽ is nonsingular. Any curve has good reduction everywhere except at the finitely many primes which divide its discriminant.

We can also reduce a point P = (x, y) ∈ E(ℚ), provided that p doesn’t divide the denominators of x or y. It’s not hard to see that P̃ ∈ Ẽ(ℤ/pℤ). Since all torsion points have integer coordinates, we get a well-defined homomorphism of groups.

\begin{matrix}E(ℚ)_{tor} & → & Ẽ(ℤ/pℤ) \\ (x, y) & ↦ & (x̃, ỹ) \\ O & ↦ & Õ. \end{matrix}

The only element which gets sent to Õ is O, and so the map is actually an injection. As long as p ∤ D, E(ℚ)_{tor} ↪ Ẽ(ℤ/pℤ). In particular, E(ℚ)[m] ↪ Ẽ(ℤ/pℤ)[m].

These concepts generalize in a couple of ways. First, we can consider points over any number

3 WEAK MORDELL-WEIL: REPRISE  May 1992

field K. Recall some basic facts about nonarchimedean valuations, most of which are in the first few pages of [Lan]. The reader is also invited to examine the eminently lucid exposition [Cas 2].

Let O be the ring of integers of K. Let M_{K} be a complete set of distinct valuations on K, and M_{K}^{0} ⊂ M_{K} the set of nonarchimedean valuations. A v ∈ M_{K}^{0} corresponds to some prime ideal p of O. Associated to such an ideal is the completion K_{p} and the residue field k = O/p. With this notation, we can still reduce a curve E(K) as above, obtaining Ẽ defined over k_{v}. Again, the reduced curve Ẽ will be nonsingular so long as p does not divide D, that is, ord_{p}(D) = 0.

Second, we can work with any abelian variety A. Such a variety has an embedding into some projective space ℙ^{n}. (See [Mum 1] for details.) The variety can thus be described as the intersection of finitely many polynomials f_{i}(x_{0}, x_{1}, …, x_{n}). The obvious choice for Ã, the reduction of A mod p, is the intersection of the f̃_{i}, where f̃is obtained from f by simply reducing the coefficients.

The description of singularity here will be in terms of the various properties of polynomials. One probably wouldn’t want to actually compute any of the polynomials involved. However, the resulting theory can be used to show that A almost always has good reduction, without recourse to conceptually high-powered machinery.

As before, let d be the dimension of A. The Jacobian matrix J of A is given by ||(∂f_{i}/∂x_{j})||. (The differentiation is purely formal; we are not working with a notion of continuity here.) We say that A is nonsingular at a point P if evaluating J at P yields a matrix of rank n − d. Equivalently, J is singular at P if all of the (n − d) × (n − d) submatrices have determinant zero. Now, the determinant of a matrix is given by a polynomial in the entries of that matrix. Furthermore, even though there are lots of (n − d) × (n − d) submatrices of J, there are certainly only finitely many of them. So A is singular at a point P if and only if each of the determinant polynomials D_{i} vanishes at P.

At this point we turn to the classical tool of elimination theory, which can tell us when all of these polynomials have a common zero (see section 9 of [Sch]). Here, it suffices to recall that there

3 WEAK MORDELL-WEIL: REPRISE  May 1992

is a polynomial expression D in the coefficients of the D_{i}, which is equal to zero if and only if the D_{i} have a common nontrivial zero. Since A is nonsingular by definition, D is nonzero. The reduction of Ã is accomplished in the expected way; Ã is nonsingular if J̃ has the expected rank, that is, if D̃ ≢ 0 mod v. Since D has nontrivial valuation at only finitely many of the v, Ã is nonsingular except at finitely many places. One can similarly show that Ã is actually has a group law on it at almost all places [Ner]. We formalize this information in the following proposition.

Proposition 3.5 A has good reduction at almost all places; there is a finite set S ⊂ M_{K} so that A has good reduction for all v ∈ M_{K}\S.

Let S = {v : Ã (mod v) is not an abelian variety }. The following lemma will be useful below.

Proposition 3.6 Let v be a nonarchimedean valuation, v ∉ S. Then the reduction map A[m] ↪ Ã(k_{v}) is injective.

By proposition 3.5, A will have good reduction at such a place, and thus be an abelian variety of the same dimension. Proposition 3.2 says that the size of A[m] is independent of the field A is defined over, so long as certain degenerate cases are ruled out.

Proposition 3.7 Let L be defined as above. If A has good reduction at v, then L is unramified at v.

We can characterize ramification by the effect of the inertia group. Let K′ be a Galois extension of K, v a place over K, and v′ an extension of v to K′. The group Gal(K′, K) acts on the residue fields k and k′. The inertia group I_{v,v′} is the set of elements of Gal(K′, K) which act trivially on k′. We say that a subset of k′ is unramified at v if it is held fixed by I_{v,v′}.

Recall that L is the compositum of fields K(Q), where mQ ∈ A(K). Certainly if K(Q) is unramified at v for all Q, then L is unramified at v. Using the notation introduced above, we look at the action of the inertia group I_{v,v′} on Q. Take some σ ∈ I_{v,v′}. Ultimately, we want to show

3 WEAK MORDELL-WEIL: REPRISE  May 1992

that σ holds Q fixed, that is, σ(Q) − Q = O. By definition of the inertia group, σ acts trivially on Ẽ_{v′}(k′). Hence,

{ \atop σ(Q) − Q} = σ(Q̃) − Q̃ = Õ.

Furthermore, σ(Q) − Q is a point of order m:

m(σ(Q) − Q) = σ(mQ) − mQ = σ(P) − P = O.

Now, σ(Q) − Q is a point of order m, which gets sent to Õ under reduction mod v′. But A has good reduction at v, and so the points of order m inject into Ẽ_{v′}(k′). This means that σ(Q)−Q = O, that is, Q is held fixed by σ. This concludes the proof that K′ is unramified outside of S, and thus L is unramified outside S.

3.4 The final step

At this point, we have seen that L is abelian of exponent m, and that it is unramified outside of a finite set of places S. It remains to show that this means L is actually a finite extension of K.

Let R_{S} be the ring of S-integers, that is,

R_{S} = {a ∈ K : v(a) ≥ 0 for all v ∈ M_{K}, v ∉ S}.

We can augment S by any finite set of places we choose; for if the resulting field L′ is a finite extension of K, and L ⊆ L′, then L is a finite extension of K as well. Thus, we can assume that S has been chosen so that R_{S} is a principal ideal domain. (It will only take finitely many more places to accomplish this, since the class number is finite.) Additionally, assume that all the primitive m^{th} roots of unity ζ^{j} are contained in K.

3 WEAK MORDELL-WEIL: REPRISE  May 1992

Elementary Kummer theory shows that if L is abelian of exponent m, then it is obtained from K by adjoining m^{th} roots of elements of K. The reader is referred to [Lan] for a proof of this fact. Thus, L ⊂ K( ^{m} \sqrt{a} : a ∈ K), and L is the maximal field unramified outside S. The goal is to show that only finitely many m^{th} roots need be adjoined to K in order to get L. We need the following proposition.

Proposition 3.8 Let v be a discrete valuation on K with v(m) = 0. Then v is unramified in K( ^{m} \sqrt{a}) if and only if ord_{v}(a) ≡ 0 mod m.

This makes intuitive sense, when one considers any particular v = p over K = ℚ. Obviously, the prime ideal (5) ⊂ ℚ will ramify in ℚ( ^{3} \sqrt{75}), while it will not ramify in ℚ( ^{3} \sqrt{375}) = ℚ( ^{3} \sqrt{3}). The proposition is simply a formalization of this notion.

Since L is unramified at places outside of S, the m^{th} root of some a ∈ K can be in L only if ord_{v}(a) ≡ 0 mod m for all places v ∉ S. Actually, since L is the maximal possible extension, the implication works both ways; L is the compositum of all fields K( ^{m} \sqrt{a}) for a ∈ K such that ord_{v}(a) ≡ 0 mod m for v ∉ S. It’s not hard to see that K( ^{m} \sqrt{a}) = K( ^{m} \sqrt{a^{1+jm}}). So when adjoining m^{th} roots, it suffices to take one representative for each coset in K^{∗}/K^{∗m}. At this point, all we have to do is establish the finitude of

T_{S} = {a ∈ K^{∗}/K^{∗m} : ord_{v}(a) ≡ 0 (mod m) for v ∈ M_{K}, v ∉ S}.

Indeed, we will see that R_{S}^{∗}/R_{S}^{∗m} ≅ T_{S}. To see this, consider the natural map R_{S}^{∗} → T_{S} given by a ↦ a (mod K^{∗m}). This is a surjection. Let a ∈ K^{∗} be a representative for an element of T_{S}. Now, the prime ideals of R_{S} correspond to the valuations v ∉ S. Furthermore, a’s valuation everywhere outside of S is a multiple of m. So the ideal aR_{S} is actually the m^{th} power of an ideal in R_{S}. Since we’ve chosen S so that R_{S} is a principal ideal domain, we have aR_{S} = b^{m}R_{S} for some b ∈ K^{∗}, and a = ub^{m} for some u ∈ R_{S}^{∗}. Clearly, u and a correspond to the same element in T_{S}.

4 IMPLEMENTATION  May 1992

Thus, R_{S}^{∗} maps onto T_{S} in the natural way.

It’s not hard to see that R_{S}^{∗m} gets mapped to the trivial element of T_{S}. So we know that R_{S}^{∗}/R_{S}^{∗m} maps onto T_{S}. It turns out that this map is actually an isomorphism, but we don’t really need this fact. Let p_{i} be a uniformizer for each v_{i} ∈ S, and u_{1}, …, u_{t} be a set of generators for the units in R_{S}. (Theorem 2.6.4 of [Lan] shows that the group of S-units is finitely generated.) Then

{ζ^{ϵ_{0}}p_{1}^{ϵ_{1}}p_{2}^{ϵ_{2}} ⋯ p_{r}^{ϵ_{r}}u_{1}^{ϵ_{r+1}} ⋯ u_{t}^{ϵ_{r+t}}|ϵ_{i} ∈ {0, …, m − 1}

is a set of representatives for for R_{S}^{∗}/R_{S}^{∗m}, and clearly finite.

This completes the proof of the weak Mordell-Weil theorem. To trace up the chain of implications, recall that we now know that R_{S}^{∗}/R_{S}^{∗m} is finite; T_{S} is finite; [L : K] is finite; Gal(L, K) is finite; A(K)/mA(K) is finite, as desired.

4 Implementation

I have written a program which attempts to compute the rank of E(ℚ) for an elliptic curve of the form y^{2} = x^{3} + ax^{2} + bx. (Recall that setting c = 0 ensures that there will be at least one point of order two, (0, 0), on the curve. This, in turn, is necessary for the detailed proof of the Mordell-Weil theorem given above.) In this section I discuss the construction of the program and some of the trade-offs involved in its implementation.

My ultimate goal was to craft a routine which would take a description of an elliptic curve and return the rank of that curve. Early on, I had to decide which computer language I would use for the implementation. Obvious choices include Mathematica, C++, LISP and C. The first three languages are attractive in that they have more-or-less transparent support of arbitrary-precision integer arithmetic. This is useful — in fact, vital — for attempting to find points on the covering spaces.

4 IMPLEMENTATION  May 1992

Joseph Silverman has already written an elliptic curve computation package in Mathematica, and at first I hoped to interface my code with his. However, I find the Mathematica environment quite poor for program development. Also, Mathematica maintains most of its information in such generality that the actual execution time is extremely unsatisfactory. Finally, even though Mathematica is widespread in the academic community, it is a private piece of software, and my personal bias is towards making software as freely available as possible.

I held somewhat similar reservations about C++; it simply isn’t as available as LISP and C. So for me, the choice came down to LISP or C. At this point, it was a matter of personal preference; I am more familiar with C. In particular, I know I can write faster code in C then I can in LISP. The functional-programming paradigm didn’t offer many advantages for this particular project. Thus, the program is written in C.

Since C doesn’t have native support for larger (> 32 bit) integer arithmetic, I had to add in my own. There are a few packages available for arbitrary precision arithmetic. Typically these are slowed down by frequent dynamic memory operations. Additionally, different packages are optimized for different sized integers. Pari, for example, performs best on numbers of forty or fifty digits. However, the program for computing the rank really only requires integers on the order of twenty digits, and often the numbers are much smaller. So, using [Knu] as my guide I wrote hp.c, a high-precision integer arithmetic library.

The file numth.c contains a number of useful number-theoretic algorithms, such as greatest common divisor, primality, factorization, etc. The factorization routine in particular is quite primitive. Profiling experiments reveal that it isn’t a bottleneck, so I have focused my attentions elsewhere. However, it is an obvious site for improvements. The package lists.h is a very basic set of primitives for maintaining list-like arrays. The lists have a compile-time maximum size; operations supported are creation, insertion and deletion of elements, list-length inquiry, randomaccess address, and disposal. It is far from general, but it performs the necessary job for the larger

4 IMPLEMENTATION  May 1992

program.

The actual algorithm for computing the rank of the Mordell-Weil group and auxiliary routines are found in rank.c. At its highest level, the algorithm is quite simple.

ec rank(a,b)  /* Returns the rank of y^{2} = x^{3} + ax^{2} + bx. */
r ← rank( α(a,b) )  /* Find rank of image of ϕ. */
\overline{r} ← rank( α(\overline{a},\overline{b}) )  /* Find rank of image of ψ. */

rank ← r + \overline{r} − 2 return( rank )

The tricky part is determining the size of the images ϕ(E(ℚ)) and ψ(\overline{E}(ℚ)). Recall that these images inject into ℚ^{∗}/ℚ^{∗2}. There’s an obvious approach to computing the rank of α(a, b), which falls out of our proof of the weak Mordell-Weil theorem.

rank(α(a,b))

candidates ← sq free fac(b)  /* Find square-free factors of b */
image ← ∅  /* Image of ϕ(E(ℚ)) */

for each b_{1} ∈ candidates b_{2} ← b/b_{1} if ( b_{1}m^{4} + am^{2}e^{2} + b_{2}e^{4} = n^{2} ) has an integer solution

image ← image ∪ {b_{1}}

add in O and T

return( log_{2}( —image— ) )

This would work well enough, were the computations described at every line effective. (The logarithm is taken in the last step in order to return the rank of the group, since every element has order 2.) However, there is no known algorithm which will determine if the equation b_{1}m^{4} + am^{2}e^{2} + b_{2}e^{4} = n^{2} has a nontrivial solution in a finite amount of time. All one can do is hope. Of course, some instances of this problem are easily solved. For example, if b_{1}, a and b_{2} are all negative, there will clearly be no solution; there aren’t even any real solutions. Additionally, if the equation has no solution mod p for some prime p, then there is no solution in the integers.

4 IMPLEMENTATION  May 1992

Checking for solutions mod p is a finite process; one must only let x and y take on all of the (finitely many) possible distinct values, and check explicitly for a solution.

If such considerations fail to rule out the existence of a solution, one is forced to try a bruteforce check for integral solutions. This is typically done until either a solution is found, or the computation is arbitrarily aborted after some range.

This is why any “algorithm” to compute the rank of an elliptic curve can really only be a heuristic, given the current state of the art. We can only hope that the computer successfully finds points or proves that they don’t exist.

The algorithm presented above has a two disadvantages, even beyond the crucial lack of effectivity. First, in practice the algorithm often finds an image set with an impossible number of elements. Since the image of α is a subgroup of R^{∗}/R^{∗2}, whose order is a power of 2, the size of the image must be a power of 2, as well. A second, related criticism is that the algorithm ignores the group structure of im α; it merely treats it as a set. It is not implausible that a better algorithm could be crafted by taking advantage of the group structure.

Indeed, this is the case. The following algorithm maintains separate sets for b_{1}’s which definitely give rise to a point in the image, b_{1}’s which definitely don’t, and b_{1}’s it couldn’t definitely say either about. It takes advantage of the group structure in the following way. Suppose H ⊂ G is a subgroup. If h ∈ H, g ∈ G and their product hg is in H, then g must be in H, as well. Similarly, if k ∉ H, and kg ∈ H, then g ∉ H.

rank(α(a,b))

S ← nonarch places(b)  /* Find the nonarchimedean places dividing (b) */

def in ← ∅ def out ← ∅

for each g in ⟨S⟩  /* ⟨S⟩ is the group generated by S */

if g ∈⟨def in⟩

end this iteration of main loop

for each k ∈def out  /* def out isn’t a group */

if g·k ∈⟨def in⟩ def out ← def out ∪ {g}

4 IMPLEMENTATION  May 1992

end this iteration of main loop

/* We have to do some actual work */

b_{1} ← g b_{2} ← b/b_{1}

switch( solvable(b_{1}m^{4} + am^{2}e^{2} + b_{2}e^{4} = n^{2}) )  /* One of three things happens */

case is sol:

def in ← def in ∪ {g} case no sol:

def out ← def in ∪ {g} case cant tell:

dont know ← def in ∪ {g} check again to clean up dont know return( rank(def in) )

This is the algorithm I actually used. Most of the details are self-explanatory. I would only add a note about the implementation of the group law on R^{∗}/R^{∗2}. Recall that this group has coset representatives

{(−1)^{ϵ_{0}}p_{1}^{ϵ_{1}}p_{2}^{ϵ_{2}} ⋯ p_{r}^{ϵ_{r}}|ϵ_{i} ∈ {0, 1}} ⊂ ℚ^{∗}/ℚ^{∗2}.

So on a computer, it makes sense to represent any element of R^{∗}/R^{∗2} as an n + 1-bit word. As for implementing the group law, we have p · p = 1 · 1 = 1, p · 1 = 1 · p = p for each prime p. So if we have two elements g = g_{0}g_{1} ⋯ g_{n} and h = h_{0}h_{1} ⋯ h_{n}, then their product is given by (gh)_{i} = g_{i} + h_{i} mod 2. Bitwise addition mod 2 can be accomplished by exclusive-or’ing the two values together; thus, gh = XOR(g, h).

In computing whether an element is in the span of a set of elements, one essentially performs an orthogonalization operation. I find it interesting that a similar computation arises in the work of Brumer, Kramer and McGuinness [BKM]. As part of their algorithm to compute the 2-Selmer group of an elliptic curve, they wind up inverting a matrix over ℤ/2ℤ.

Even though I wrote the program to be as efficient as I could, it still takes several seconds to compute the rank of an elliptic curve. While this may not be prohibitive to the casual investigator,

5 RESULTS AND DISCUSSION  May 1992

it becomes a problem when one is looking at a large number of curves. I wanted to compute the rank of about one hundred thousand curves. (The choice of curves is discussed below.) Rather than wait sixty days for one SPARCstation to complete the calculations, I harnessed sixty SPARCstations for one day. These computations lend themselves to a coarse-grained distributed network. Every computer in the network can be assigned a range of curves to look at. Such an assignment is simple, as the family of curves y^{2} = x^{3} + ax^{2} + bx has an obvious parameterization. Each computer can industriously work on its segment of the problem space, without need for communication with other computers. I chose to implement parallelism using Curtis Yarvin’s QuaHog system [Yar]. QuaHog daemons are running on most SPARCstations in the Brown University computer science department. Each daemon monitors the load level on its machine. The driver program tells its local QuaHog daemon that it has sixty jobs, say, and roughly describes their resource requirements. The jobs are farmed out appropriately to idle nodes throughout the network. The system is designed to cause as little trauma to other users as possible. If a node where a Qua-Hog job is running is suddenly getting heavy use, the job will exit gracefully. The master program then resubmits the job, which will then run on another node. Since the basic program was written to be easily restarted, there is fairly graceful process migration.

5 Results and Discussion

The rank of elliptic curves has been an object of computer-aided investigation for a relatively long time. By the 1950’s, Birch and Swinnerton-Dyer were letting results from computer experiments guide their conjectures [B-S]. They performed a 2-descent similar to the one described in section 4 on curves of the form y^{2} = x^{3} − Ax − B, y^{2} = x^{3} − A, and y^{2} = x^{3} − Ax. Relying particularly on numerical evidence gained from computing the rank of curves y^{2} = x^{3} − Ax, they formulated a two-part conjecture. A gentle explanation of the Birch-Swinnerton-Dyer conjecture is outlined in [Zag]. Essentially, it relates the local behavior of an elliptic curve E to its global behavior. The

5 RESULTS AND DISCUSSION  May 1992

L-series of E is

L(E, s) = ∏_{p} \frac{1}{1 − a(p)p^{−s} + ϵ(p)p^{1−2s}} (Re(s) > \frac{3}{2}).

Here, the product is taken over all primes p, a(p) = #Ẽ(ℤ/pℤ), and ϵ(p) is zero if p divides the discriminant of E, and one otherwise. The first part of the BSD conjecture may be stated as follows.

Conjecture 5.1 The L-series of E continues meromorphically to s = 1, and it has a zero there with order equal to the rank of E(ℚ).

Birch and Swinnerton-Dyer’s calculations bore out this prediction on the curves they examined. Since then, a considerable body of evidence for the conjecture has accumulated. Some of this is numerical; we will consider such results shortly. Some of the evidence is more theoretical; implications of the conjecture have been verified for certain classes of elliptic curves. Note that, if true, the BSD conjecture would provide an effective method for determining the rank of an elliptic curve. We would merely have to compute L(E, 1), L′(E, 1), L′′(E, 1), etc., to some desired degree of accuracy.

5 RESULTS AND DISCUSSION  May 1992

Let p be a prime, p ≡ 5 mod 8. The rank of the curve y^{2} = x^{3} + px cannot be bigger than 1. Conjecturally this bound is always reached, and the rank of such a curve is 1. Bremner and Cassels produced points of infinite order for all such p less than 1000 [B-C]. Taking advantage of the structure of this particular class of curves, they actually carried out a second descent. (The method of section 4 is sometimes called a first descent; finding points on E is reduced to finding points on each of a finite set of curves. In a second descent, one examines each of those covering spaces by a further descent process.) This was necessary, as a straight brute force search might not encounter a generator in a reasonable amount of time. Indeed, Bremner and Cassels have characterized the generators as sometimes being “rather large.” As an example they cite the generator for y^{2} = x^{3} + 877x, whose x-coordinate is

\frac{375, 494, 528, 127, 162, 193, 105, 504, 069, 942, 092, 792, 346, 201}{6, 215, 987, 776, 871, 505, 425, 463, 220, 780, 697, 238, 044, 100}.

Using a computer search, Bremner extended this result for such curves with 1000 < p < 5000 [Bre]. He also computed L′(E, 1) for all 1000 < p < 20, 000, and found it to be nonzero. Thus, the computer produced numerical evidence that the BSD conjecture is compatible with the conjecture for the rank of y^{2} = x^{3} + px.

Computers are now sufficiently powerful that we can investigate the behavior of large classes of curves. Zagier and Kramarz examined the L-series for elliptic curves x^{3} + y^{3} = m (or, equivalently, y^{2} = x^{3} − 432m^{2}) [Z-K]. They assumed that the BSD conjecture is true, and thus were able to compute a rank for each of the curves. Before their work, there was apparently a sort of folk conjecture that the rank of an elliptic curves is as low as possible. The BSD conjecture says that the parity of the rank is even or odd depending on whether the sign of the functional equation is + or −. It was believed that, for any large sample of curves, half of them would have rank zero, and half have rank one, with higher ranks occurring in a vanishingly small percentage of the curves. What they found really didn’t support this conjecture. Rather, they found that about a quarter (23.3%) of the curves with an even functional equation actually have rank 2 or higher. Additionally, ranks of 3 or higher occurred in about 2% of the curves with odd rank. While this is a small percentage, it could well be a significant deviation from zero; a set of 70,000 curves was examined.

Perhaps a few words of caution about such computer experiments are appropriate here. The obvious source of error is an error in programming. This seems to have been a particular concern of Birch and Swinnerton-Dyer.

On the other hand, in translating an elaborate scheme of calculation into a machine program one is bound to make mistakes. Most of these are found before the program is used for production runs; they show up because the program grinds to a halt or produces ridiculous results. But a program which is believed to work may still contain logical errors which only have an effect in rare circumstances: and indeed most computers have anomalies which cause them occasionally not to behave in the way that their specifications suggest. In fact, our program for stage (ii) was imperfect in that a very few equivalences were missed by the machine.

For these reasons we believe that results obtained from a computer should not be automatically trusted. In some cases they can be checked because they have properties which were not essentially used in the course of the calculation and which would be unlikely to survive if an error had been made.... But if checks of this sort are not available, results should not be fully trusted until they have been independently reproduced by a different programmer using a different machine. We do not think this sets an unreasonable standard, now that computers are becoming so widely available; and we are satisfied that lower standards have already led to a number of untrue results being published and believed. [B-S]

Statistical experiments such as [Z-K] raise additional methodological questions. Fundamen-

tally, one has to decide if one’s sample set of curves is representative of the behavior of all elliptic

curves. There really isn’t any way to definitively answer this.

Brumer and McGuinness argue that the set of curves with prime conductor is typical of the

whole set [B-M]. (The conductor of a curve, like its discriminant, measures its singularity at var-

ious reductions.) They had a Macintosh II estimate the rank of the 310,716 elliptic curves with

prime conductor less than 10^{8}. The rank was primarily computed using the parity conjecture and

the order of vanishing of the L-series. Additionally, they searched for independent points as a

lower bound for the rank. Thus, assuming the BSD conjecture, they found the following rank dis-

tribution. Results for curves positive and negative discriminants are shown separately, as Brumer

and McGuinness argue that the difference in rank distribution is significant.

\begin{matrix}rank & 0 & 1 & 2 & 3 & 4 & 5 \\ D > 0 & 27.87 & 45.51 & 21.68 & 4.62 & 0.33 & 0.0 \\ D < 0 & 31.30 & 46.41 & 18.71 & 3.35 & 0.21 & 0.0025 \\ all & 30.04 & 46.08 & 19.80 & 3.82 & 0.26 & 0.0016 \end{matrix}

5 RESULTS AND DISCUSSION  May 1992

This roughly corroborates the findings of Zagier and Kramarz; they found that 23.9% of the curves have rank at least 2, which is far from the earlier near-zero estimate.

I used the algorithm developed in this paper to predict the rank of all nonsingular curves y^{2} = x^{3} + ax^{2} + bx with −30 ≤ a ≤ 30 and −900 ≤ b ≤ 900. In a sense, the difficulty of finding the rank grows linearly in the size of b, and quadratically in the size of a; this explains the shape of the chosen search space. Recall that the key step of computing the rank is finding an integral point on a 2-covering space of the form N^{2} = qM^{4} + \overline{a}M^{2}e^{2} + q′e^{4}. The program attempts to prove that no such solution exists using certain elementary considerations. After that, it searches for solutions with |M|, |e| ≤ 40.

Of the 107,100 curves examined, it was able to precisely determine the rank of 16,719. The observed rank distributions match up nicely with those reported by Brumer and McGuinness. For purposes of comparison, separate statistics are given here for curves with positive and negative discriminant. However, it does not appear that the sign of the discriminant systematically influenced the rank of the curve.

\begin{matrix}rank & 0 & 1 & 2 & 3 & 4 \\ D > 0 & 29.12 & 45.36 & 20.99 & 4.25 & 0.27 \\ D < 0 & 28.96 & 45.76 & 21.09 & 3.90 & 0.29 \\ all & 29.06 & 45.54 & 21.03 & 4.09 & 0.28 \end{matrix}

In my opinion, the similarity between these numbeers and those of Brumer and McGuinness is interesting for a number of reasons. First, it obviously lends support to their hypotheses about the distribution of rank. Second, this may say something about the set of all elliptic curves. Recall that Brumer and McGuinness had examined the set of elliptic curves with (small) prime conductor. I looked at a collection of curves with small discriminant. Furthermore, the numbers above represent only the curves for which I was able to precisely determine the rank. It is intriguing that these two seemingly disparate sets correspond so well. One could tentatively say that the

5 RESULTS AND DISCUSSION  May 1992

numbers reported above are characteristic of any large set of elliptic curves.

This summarizes the situation for the curves whose rank was successfully computed. What can we say about the remaining ones? In each such case, the algorithm could neither prove nor disprove the existence of an integer point on certain curves. Thus, it can compute lower and upper bounds for them. (Obviously, these lower and upper bounds agree when it has actually computed the rank.) The lower and upper bounds were distributed as follows:

rank  0  1  2  3  4  5  6  7  8
min 46.17 39.02 12.85 1.86 0.11 0.002
max 4.54 17.87 28.60 26.94 15.44 5.54 0.99 0.074 0.002

Even though the curves where the lower and upper rank bounds differ may seem like failures, we can still infer some information about the Selmer Tate-Shafarevich group associated to the curve, Sel = Sel(E, ℚ) and � = � (E, ℚ). A full discussion of these groups is left to chapter X of [Sil]. Here we merely recall that associated to every isogeny of elliptic curves defined over K ϕ : E(K) → E′(K) there is an exact sequence

0 → E(K) → E(K) →^{ϕ} E′(K) → Sel(E, K)[ϕ] → � (E, K)[ϕ] → 0.

In our case, the isogeny is [2] , K = ℚ and E = E′. Thus, there is an exact sequence

0 → E(ℚ)/2E(ℚ) → Sel[2] → � [2] → 0.

All of the groups in the sequence are finite. The Selmer group is effectively computable. (See [BKM] for an actual algorithm.) So in order to determine what E(ℚ)/2E(ℚ), we merely have to figure out what part of Sel[2] comes from E(ℚ)/2E(ℚ), and what part of it comes from � [2]. Unfortunately, there is no algorithm guaranteed to do this.

REFERENCES  May 1992

As Silverman remarks, the group � [2] can be interpreted as the group of 2-covering spaces which have an element mod p for every p. The identity element of this group is the class of covering spaces which actually have a ℚ-rational point. This intuition explains why the sequence given above is exact.

Covering spaces for which the program is unable to produce an integral point or to rule one out could well correspond to elements of � [2]. In view of this, it appears that the family examined tends to have a nontrivial � .

Zagier and Kramarz that the percentage of curves with trivial � tends to zero asymptotically as one considers a set of elliptic curves. For such curves there is a mod p point on every curve which lifts to a rational point. In view of this, it is a bit surprising that my program only completely determined E(ℚ)/2E(ℚ) for about one sixth of the curves. One possibility is that their family of curves is nonrepresentative, of the family y^{2} = x^{3} + ax^{2} + bx if not of all elliptic curves. They present some evidence that the family x^{3} + y^{3} = m may be anomalous. I feel that the discrepancy is probably to the brevity of the search for integer points. There is simply no way that a first descent will produce the generating point of y^{2} = x^{3} + 877x. As a remedy, one could derive and implement second and third descents. This increases the number of curves one must examine, but (probably) reduces the height of points on each of the curves.

References

[Bre] A. Bremner, “On the equation y^{2} = x(x^{2} + p),” in Number Theory and Applications, ed. R. Mollin, Kluwer Academic Publishers, 1989, 3-22.

[B-C] A. Bremner and J.W.S. Cassels, “On the equation y^{2} = x(x^{2} + p),” Mathematics of Computation, 42:185 (1984), 257-264.

REFERENCES  May 1992

[B-S] B. Birch and H.P.F. Swinnerton-Dyer, “Notes on elliptic curves (I) and (II),” J. Reine

Angew. Math., 212 (1963), 7-25; 218 (1965), 79-108.

[BKM] A. Brumer, K. Kramer, and O. McGuinness, “Calculating Selmer groups of elliptic curves with all 2-torsion points rational,” 1991 [to appear].

[B-M] A. Brumer and O. McGuinness, “The behavior of the Mordell-Weil group of elliptic

curves,” Bull. Amer. Math. Soc., 23:2 (1990), 375-382.

[Cas 1] J.W.S. Cassels, “Diophantine equations with special reference to elliptic curves,” J. Lon-

don Math. Soc., 41 (1966), 193-291.

[Cas 2] J.W.S. Cassels, Local Fields, Cambridge University Press, 1986 (New York).

[Har] R. Hartshorne, Algebraic Geometry, Springer-Verlag, 1977 (New York).

[Hin] M. Hindry, Geometrie Arithmetique, lecture notes, Université Paris, 1991.

[Knu] D. Knuth, The Art of Computer Programming, Volume 2; Seminumerical Algorithms, Addison-Wesley, 1981 (Reading).

[Lan] S. Lang, Fundamentals of Diophantine Geometry, Springer-Verlag, 1983 (New York). [Mum 1] D. Mumford, “On the equations defining abelian varieties,” Inventiones Mathematicae, 1

(1966), 287-354.

[Mum 2] D. Mumford, Abelian Varieties, Oxford University Press, 1970 (Bombay).

[Ner] A. Neron, Geometrie Diophantienne, lecture notes, Publications Mathematiques D’Orsay, 1967.

[Sch] A. Schinzel, Selected Topics on Polynomials, University of Michigan Press, 1982 (Ann Arbor).

REFERENCES  May 1992

[Shi] G. Shimura, “Reduction of algebraic varieties with respect to a discrete valuation of the basic field,” Amer. J. Math., 77 (1955), 134-176.

[Sil] J. Silverman, The Arithmetic of Elliptic Curves, Springer-Verlag, 1986 (New York). [S-T] J. Silverman and J. Tate, Rational Points on Elliptic Curves, Springer-Verlag, 1992 (New

York) [to appear].

[Tat] J. Tate, “The arithmetic of elliptic curves,” Inventiones Mathematicae, 23 (1974), 179-206.

[Yar] C. Yarvin, QuaHog, computer software.

[Zag] D. Zagier, “The Birch-Swinnerton-Dyer conjecture from a naive point of view,” Arithmetic Algebraic Geometry, ed. G. van derGeer, F. Oort, J. Steebrink, Birkhauser, 1991 (Boston), 377-389.

[Z-K] D. Zagier and G. Kramarz, “Numerical investigations related to the L-series of certain elliptic curves,” J. Indian Math. Soc., 52 (1987), 51-69.