Explicit Approaches to Elliptic Curves

and Modular Forms

William Stein

Associate Professor of Mathematics University of California, San Diego

Math 168a: 2005-09-26

Outline of Course and this Lecture

1. Pythagoras and Fermat

2. Mordell-Weil Groups and the BSD Conjecture

3. Modularity of Elliptic Curves

4. Computing Modular Forms

The Pythagorean Theorem

a^{2} + b^{2} = c^{2} c  a b  _{Pythagoras}_{Approx 569–475BC}

Pythagorean Triples

Triples of integers a, b, c such that a_{2} + b_{2} = c_{2}^{(3, 4, 5) ; (5, 12, 13) ; (7, 24, 25) ; (9, 40, 41) ; (11, 60, 61) ; (13, 84, 85) ; (15, 8, 17) ; (21, 20, 29) ; (33, 56, 65) ; (35, 12, 37) ; (39, 80, 89) ; (45, 28, 53) ; (55, 48, 73) ; (63, 16, 65) ; (65, 72, 97) ; (77, 36, 85) ; ⋮}

Enumerating Pythagorean Triples

(−1, 0)  (0, t)(x, y)  \begin{aligned}Slope = t & = \frac{y}{x + 1} \\ x & = \frac{1 − t^{2}}{1 + t^{2}} \\ y & = \frac{2t}{1 + t^{2}} \end{aligned} If t = \frac{r}{s}, then  a = s^{2} − r^{2}, b = 2rs, c = s^{2} + r^{2} is a Pythagorean triple, and all primitive unordered triples arise in this way.

Fermat’s “Last Theorem”

No analogue of “Pythagorean triples” with exponent 3 or higher.

Wiles’s Proof of FLT Uses Elliptic Curves An elliptic curve is a nonsingular plane cubic curve with a rational point (possibly “at infinity”).

∞ x y_{y^{2} + y = x^{3} − x}  ^{EXAMPLES} y^{2} + y = x^{3} − x^{x3 + y3 = 1 (Fermat cubic)} y^{2} = x^{3} + ax + b 3x^{3} + 4y^{3} + 5 = 0

The Frey Elliptic Curve

Suppose Fermat’s conjecture is FALSE. Then there is a prime ℓ ≥ 5 and coprime positive integers a, b, c with a^{ℓ} + b^{ℓ} = c^{ℓ}. Consider the corresponding Frey elliptic curve:

y^{2} = x(x − a^{ℓ})(x + b^{ℓ}).

Ribet’s Theorem: This elliptic curve is not modular. Wiles’s Theorem: This elliptic curve is modular. Conclusion: Fermat’s conjecture is true.

The Group Operation

x y_{y^{2} + y = x^{3} − x}^{∞}^{Point at infinity}^{⊕} ^{=}^{(−1, 0) ⊕ (0, −1) = (2, 2)}_{The set of points}_{on E forms an abelian group.}

The First 150 Multiples of (0, 0)

(The bluer the point, the bigger the multiple.)

Fact: The group E(Q) is infinite cylic, generated by (0, 0).

In contrast, y^{2} + y = x^{3} − x^{2} has only 5 rational points!

What is going on here?

x

y

y^{2} + y = x^{3} − x 10

Mordell’s Theorem

Theorem (Mordell). The group E(Q) of rational points on an elliptic curve is a finitely generated abelian group, so

E(Q) ≅ Z^{r} ⊕ T,

with T = E(Q)_{tor} finite. Mazur classified the possibilities for T. It is conjectured that r can be arbitrary, but the biggest r ever found is (probably) 24.

The Simplest Solution Can Be Huge

Simplest solution to y^{2} = x^{3} + 7823:

x = \frac{2263582143321421502100209233517777}{143560497706190989485475151904721}
y = \frac{186398152584623305624837551485596770028144776655756}{1720094998106353355821008525938727950159777043481}

(Found by Michael Stoll in 2002.)

The Central Question

Given an elliptic curve E, what is the rank of E(Q)?

Idea!: Consider the Group Modulo p

N(p) = # of solutions (mod p)

y^{2} + y = x^{3} − x (mod 7)

5P^{P}  ^{6P}^{2P}^{7P}  ^{3P}^{8P}  ^{4P}  ^{∞} N(7) = 9

Counting Points

Cambridge EDSAC: The first point counting supercomputer...

Birch and Swinnerton-Dyer

Hecke Eigenvalues

Hasse Let

a_{p} = p + 1 − N(p).

Hasse proved that

|a_{p}| ≤ 2√p.

For y^{2} + y = x^{3} − x: a_{2} = −2, a_{3} = −3, a_{5} = −2, a_{7} = −1, a_{11} = −5, a_{13} = −2,

a_{17} = 0, a_{19} = 0, a_{23} = 2, a_{29} = 6, …

Birch and Swinnerton-Dyer

17

The L-Function

Theorem (Wiles et al., Hecke) The following function extends to a holomorphic function on the whole complex plane:

L^{∗}(E, s) = _{pΔ}^{∏} (\frac{1}{1 − a_{p} · p^{−s} + p · p^{−2s}} ) .

Here a_{p} = p + 1 − #E(F_{p}) for all pΔ_{E}. Note that formally,

L^{∗}(E, 1) = _{pΔ}^{∏} (\frac{1}{1 − a_{p} · p^{−1} + p · p^{−2}} ) = _{pΔ}^{∏} (\frac{p}{p − a_{p} + 1} ) = _{pΔ}^{∏} \frac{p}{N_{p}}

Standard extension to L(E, s) at bad primes.

Real Graph of the L-Series of

y^{2} + y = x^{3} − x

More Graphs of Elliptic Curve L-functions Absolute Value of L-series on Complex

Plane for y^{2} + y = x^{3} − x

Conjectures Proliferated

“The subject of this lecture is rather a special one. I want to describe some computations undertaken by myself and Swinnerton-Dyer on EDSAC, by which we have calculated the zeta-functions of certain elliptic curves. As a result of these computations we have found an analogue for an elliptic curve of the Tamagawa number of an algebraic group; and conjectures have proliferated. [...] though the associated theory is both abstract and technically complicated, the objects about which I intend to talk are usually simply defined and often machine computable; experimentally we have detected certain relations between different invariants, but we have been unable to approach proofs of these relations, which must lie very deep.” – Birch 1965

The Birch and Swinnerton-Dyer Conjecture

Conjecture: Let E be any elliptic curve over Q. The order of vanishing of L(E, s) as s = 1 equals the rank of E(Q).

The Kolyvagin and Gross-Zagier Theorem

Theorem: If the ordering of vanishing ord_{s=1} L(E, s) is ≤ 1, then the conjecture is true for E.

Elliptic Curves are “Modular”

An elliptic curve is modular if the numbers a_{p} are coefficients of a “modular form”. Equivalently, if L(E, s) extends to a complex analytic function on C (with functional equation).

Theorem (Wiles et al.): Every elliptic curve over the rational numbers is modular.

Wiles at the Institute for Advanced Study 25

Modular Forms

The definition of modular forms as holomorphic functions satisfying a certain equation is very abstract.

For today, I will skip the abstract definition, and instead give you an explicit “engineer’s recipe” for producing modular forms. In the meantime, here’s a picture:

Computing Modular Forms: Motivation

Motivation: Data about modular forms is extremely useful to many research mathematicians (e.g., number theorists, cryptographers). This data is like the astronomer’s telescope images.

One of my longterm research goals is to compute modular forms on a huge scale, and make the resulting database widely available. I have done this on a smaller scale during the last 5

years — see http://modular.ucsd.edu/Tables/

What to Compute: Newforms

For each positive integer N there is a finite list of newforms of level N. E.g., for N = 37 the newforms are

f_{1} = q − 2q^{2} − 3q^{3} + 2q^{4} − 2q^{5} + 6q^{6} − q^{7} + ⋯
f_{2} = q + q^{3} − 2q^{4} − q^{7} + ⋯,

where q = e^{2πiz}.

The newforms of level N determine all the modular forms of level N (like a basis in linear algebra). The coefficients are algebraic integers. Goal: compute these newforms.

Bad idea – write down many elliptic curves and compute the numbers a_{p} by counting points over finite fields. No good – this misses most of the interesting newforms, and gets newforms of all kinds of random levels, but you don’t know if you get everything of a given level.

An Engineer’s Recipe for Newforms

Fix our positive integer N. For simplicity assume that N is prime.

1. Form the N + 1 dimensional Q-vector space V with basis the symbols [0], …, [N − 1], [∞].

2. Let R be the suspace of V spanned by the following vectors, for

x = 0, …, N −1, ∞:

[x] − [N − x]
[x] + [x.S]
[x] + [x.T] + [x.T^{2}]

S = ( \begin{matrix}0 & −1 \\ 1 & 0 \end{matrix} ), T = ( \begin{matrix}0 & −1 \\ 1 & −1 \end{matrix} ), and x. ( \begin{matrix}a & b \\ c & d \end{matrix} ) = (ax + c)/(bx + d).

3. Compute the quotient vector space M = V/R. This involves “intelligent” sparse Gauss elimination on a matrix with N + 1 columns.

4. Compute the matrix T_{2} on M given by

[x] ↦ [x. ( \begin{matrix}1 & 0 \\ 0 & 2 \end{matrix} )] + [x. ( \begin{matrix}2 & 0 \\ 0 & 1 \end{matrix} )] + [x. ( \begin{matrix}2 & 1 \\ 0 & 1 \end{matrix} )] + [x. ( \begin{matrix}1 & 0 \\ 1 & 2 \end{matrix} )].

This matrix is unfortunately not sparse. Similar recipe for matrices T_{n} for any n.

5. Compute the characteristic polynomial f of T_{2}.

6. Factor f = ∏ g_{i}^{e_{i}}. Assume all e_{i} = 1 (if not, use a random linear combination of the T_{n}.)

7. Compute the kernels K_{i} = ker (g_{i}(T_{2})). The eigenvalues of T_{3}, T_{5}, etc., acting on an eigenvector in K_{i} give the coefficients a_{p} of the newforms of level N.

Implementation

• I implemented code for computing modular forms that’s included with MAGMA (non-free, closed source):

http://magma.maths.usyd.edu.au/magma/.

• I want something better, so I’m implementing modular symbols algorithms as part of SAGE:

http://modular.ucsd.edu/sage/.

• I’m finishing a book on these algorithms that will be published by the American Mathematical Society.

The Modular Forms Database Project

• Create a database of all newforms of level N for each N < 100000. This will require many gigabytes to store. (50GB?)

• So far this has only been done for N < 7000 (and is incomplete), so 100000 is a major challenge.

• Involves sparse linear algebra over Q on spaces of dimension up to 200000 and dense linear algebra on spaces of dimension up to 25000.

• Easy to parallelize – run one process for each N.

• Will be very useful to number theorists and cryptographers.

• John Cremona has done something similar but only for the newforms corresponding to elliptic curves (he’s at around 120000 right now), so this should be do-able.

Goals for Math 168

• [Elliptic Curves] Definition, group structure, applications to cryptography, L-series, the Birch and Swinnerton-Dyer conjecture (a million dollar Clay Math prize problem).

• [Modular Forms] Definition (of modular forms of weight 2), connection with elliptic curves and Andrew Wiles’s celebrated proof of Fermat’s Last Theorem, how to use modular symbols to compute modular forms.

• [Research] Get everyone in 168a involved in some aspect of my research program: algorithms needed for SAGE, making data available online, efficient linear algebra, etc.