2016-02-22-elliptic-curves-part3.sagews

February 22, 2016: Elliptic curves (part 3)

William Stein

Notes:

• Homework 6: graded and returned. Everybody got 0% or 100%.

• We will do modular forms too this week

• Homework 7 is about modular forms. Requires more advanced programming skills (for loops / if statements).

Elliptic curves continued

Sage has a lot of big tables of elliptic curves included. They are all a little funny to use though, since we always optimize for speed of access and iterating through, rather than ease of use.... and nobody does much work on this code (it could be easily improved)...

3.2 Cremona's tables of elliptic curves

Copy in Sage (via a sqlite database, made by Andrew Ohana...) of this data: http://johncremona.github.io/ecdata/

Exercise: Use Cremona's tables to determine how many distinct isomorphism classes of ellliptic curves have conductor 2016. Will there be any curves (of conductor 2017) next year?!

factor(2016)

2^5 * 3^2 * 7

# hint
C = CremonaDatabase()
C[11]

{'allcurves': {'a1': [[0, -1, 1, -10, -20], 0, 5], 'a3': [[0, -1, 1, 0, 0], 0, 5], 'a2': [[0, -1, 1, -7820, -263580], 0, 1]}, 'allbsd': {'a1': [5, 1.26920930427955, 0.253841860855911, 1.0, 1], 'a3': [1, 6.34604652139777, 0.253841860855911, 1.0, 1], 'a2': [1, 0.253841860855911, 0.253841860855911, 1.0, 1]}, 'degphi': {'a1': 1}, 'allgens': {'a1': [], 'a3': [], 'a2': []}}

# hint
C = CremonaDatabase()
C[2016]['allcurves'].keys()

['f1', 'f2', 'h2', 'h3', 'h1', 'j1', 'h4', 'b1', 'b2', 'd4', 'd2', 'd3', 'd1', 'k2', 'k1', 'm1', 'm2', 'c4', 'g4', 'g3', 'g2', 'g1', 'i1', 'i2', 'a1', 'a2', 'j2', 'c3', 'c2', 'c1', 'e1', 'e2', 'l2', 'l1', 'n1', 'n2']

i = 0
for E in C:
    print E
    i += 1
    if i > 10:
        break

Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field Elliptic Curve defined by y^2 + y = x^3 - x^2 over Rational Field Elliptic Curve defined by y^2 + x*y + y = x^3 + 4*x - 6 over Rational Field Elliptic Curve defined by y^2 + x*y + y = x^3 - 36*x - 70 over Rational Field Elliptic Curve defined by y^2 + x*y + y = x^3 - 171*x - 874 over Rational Field Elliptic Curve defined by y^2 + x*y + y = x^3 - x over Rational Field Elliptic Curve defined by y^2 + x*y + y = x^3 - 2731*x - 55146 over Rational Field Elliptic Curve defined by y^2 + x*y + y = x^3 - 11*x + 12 over Rational Field Elliptic Curve defined by y^2 + x*y + y = x^3 + x^2 - 10*x - 10 over Rational Field Elliptic Curve defined by y^2 + x*y + y = x^3 + x^2 - 135*x - 660 over Rational Field

for E in C.iter([2016]):
    print E

Elliptic Curve defined by y^2 = x^3 - 405*x + 4104 over Rational Field Elliptic Curve defined by y^2 = x^3 - 7020*x + 226368 over Rational Field Elliptic Curve defined by y^2 = x^3 - 405*x - 4104 over Rational Field Elliptic Curve defined by y^2 = x^3 - 7020*x - 226368 over Rational Field Elliptic Curve defined by y^2 = x^3 - 129*x + 520 over Rational Field Elliptic Curve defined by y^2 = x^3 - 444*x - 3008 over Rational Field Elliptic Curve defined by y^2 = x^3 - 2019*x + 34918 over Rational Field Elliptic Curve defined by y^2 = x^3 + 141*x + 2410 over Rational Field Elliptic Curve defined by y^2 = x^3 - 201*x - 880 over Rational Field Elliptic Curve defined by y^2 = x^3 - 3036*x - 64384 over Rational Field Elliptic Curve defined by y^2 = x^3 - 1011*x + 11594 over Rational Field Elliptic Curve defined by y^2 = x^3 + 429*x - 5290 over Rational Field Elliptic Curve defined by y^2 = x^3 + 1887*x + 45740 over Rational Field Elliptic Curve defined by y^2 = x^3 - 13548*x + 477920 over Rational Field Elliptic Curve defined by y^2 = x^3 + 15*x + 124 over Rational Field Elliptic Curve defined by y^2 = x^3 - 300*x + 1888 over Rational Field Elliptic Curve defined by y^2 = x^3 - 129*x - 520 over Rational Field Elliptic Curve defined by y^2 = x^3 - 2019*x - 34918 over Rational Field Elliptic Curve defined by y^2 = x^3 - 444*x + 3008 over Rational Field Elliptic Curve defined by y^2 = x^3 + 141*x - 2410 over Rational Field Elliptic Curve defined by y^2 = x^3 - 201*x + 880 over Rational Field Elliptic Curve defined by y^2 = x^3 - 1011*x - 11594 over Rational Field Elliptic Curve defined by y^2 = x^3 - 3036*x + 64384 over Rational Field Elliptic Curve defined by y^2 = x^3 + 429*x + 5290 over Rational Field Elliptic Curve defined by y^2 = x^3 - 45*x - 152 over Rational Field Elliptic Curve defined by y^2 = x^3 - 780*x - 8384 over Rational Field Elliptic Curve defined by y^2 = x^3 - 45*x + 152 over Rational Field Elliptic Curve defined by y^2 = x^3 - 780*x + 8384 over Rational Field Elliptic Curve defined by y^2 = x^3 + 15*x - 124 over Rational Field Elliptic Curve defined by y^2 = x^3 - 300*x - 1888 over Rational Field Elliptic Curve defined by y^2 = x^3 + 15*x + 16 over Rational Field Elliptic Curve defined by y^2 = x^3 - 75*x + 142 over Rational Field Elliptic Curve defined by y^2 = x^3 + 15*x - 16 over Rational Field Elliptic Curve defined by y^2 = x^3 - 75*x - 142 over Rational Field Elliptic Curve defined by y^2 = x^3 + 1887*x - 45740 over Rational Field Elliptic Curve defined by y^2 = x^3 - 13548*x - 477920 over Rational Field

︠debeb282-e408-4c50-9131-69e4633a3fea︠

︠5acb6f88-9f88-4494-bed9-3630e156b96di︠
%md
### 3.3 Stein-Watkins tables

In 2001 at Harvard... I started making large tables of elliptic curves by just writing down lots of curves.
Mark Watkins got involved and wrote lots of very fast code.  Together we made the SteinWatkins tables, which
are a large table of curves of conductor up to $10^9$.  We don't have all curves up to that bound -- just a lot.  We also have curves of prime conductor up to some huge bound.

3.3 Stein-Watkins tables

In 2001 at Harvard... I started making large tables of elliptic curves by just writing down lots of curves. Mark Watkins got involved and wrote lots of very fast code. Together we made the SteinWatkins tables, which are a large table of curves of conductor up to $10^9$. We don't have all curves up to that bound -- just a lot. We also have curves of prime conductor up to some huge bound.

i = 0
for E in SteinWatkinsAllData(10):
    print E.curves
    print EllipticCurve(E.curves[0][0]).conductor()
    i += 1
    if i > 5:
        break

[[[1, 1, 0, -63, -1539], '(3,6,1)', 'X', '1']] 1000002 [[[1, 1, 1, -1843618, 962738063], '[5,1,1]', '1', '1']] 1000002 [[[1, 1, 1, -567, -147], '[5,7,1]', '1', '1']] 1000002 [[[1, 0, 1, -364, -1366], '[9,3,1]', 'X', '1']] 1000002 [[[0, 1, 0, 10300, -1000108], '(8,6,1)', 'X', '1']] 1000004 [[[0, 1, 1, -831, -9475], '[3,3,1,1]', '1', '1']] 1000005

︠383a576e-c441-4b1b-8254-074d2653543f︠

︠8ee15b74-0f4b-4800-b9be-2f16f98fea98︠

︠fc5c760b-073a-4429-8846-75595af1131b︠
i = 0
for E in SteinWatkinsPrimeData(1):
    print E.curves
    print EllipticCurve(E.curves[0][0]).conductor()
    i += 1
    if i > 5:
        break

[[[1, 0, 1, -472, -3951], '[1]', '1', '1']] 100000937 [[[0, -1, 1, 97, 280], '(1)', 'X', '1']] 100000963 [[[1, 0, 0, -75, 536], '(1)', 'X', '1']] 100001183 [[[1, 0, 0, -120, -167], '[1]', 'X', '1']] 100001399 [[[0, -1, 1, -22, 490], '(1)', 'X', '1']] 100002251 [[[0, 1, 1, -180, 738], '[1]', 'X', '1']] 100002629

︠3ae688a1-fa28-4648-832b-ee6a08556a6b︠

︠f1af5570-9f95-426e-a89d-250cf34075e4︠

︠244836b0-c987-4569-997f-264d6a67c8c9︠


︠03e55c3a-825e-49b8-8d30-371639105c1bi︠
%md
### 3.4 New table: all 238,764,310 curves of naive height up to $2.9\cdot 10^{10}$

http://wstein.org/papers/2016-height/

Not in Sage.  Is maybe 30GB or so...

If anybody wanted to make a version of this that could be made available in Sage, I would be happy to provide guidance.

3.4 New table: all 238,764,310 curves of naive height up to $2.9\cdot 10^{10}$

http://wstein.org/papers/2016-height/

Not in Sage. Is maybe 30GB or so...

If anybody wanted to make a version of this that could be made available in Sage, I would be happy to provide guidance.

︠1fe22272-3381-4ff8-8d6b-57089af5b748︠

︠49f77b4e-6662-4199-851b-b16e519ef2dc︠

︠cd661503-f6f1-4403-983a-aab48abfebe4︠

︠64214c72-a6a3-4053-b547-753b4511feebi︠
%md
### 3.5 The LMFDB:

(Not easily usable from Sage as far as I know but well worth knowing about.)

    John Cremona via googlegroups.com 3:43 AM (9 hours ago)

    My article about the LMFDB based on the talk I gave at FoCM in
    December 2014 is now available (Open Access) at

<br>
http://www.springer.com/-/3/AVL5RydpAgfPWjhr63PM .

    Thanks to all who contributed.

    John

3.5 The LMFDB:

(Not easily usable from Sage as far as I know but well worth knowing about.)

John Cremona via googlegroups.com 3:43 AM (9 hours ago)

My article about the LMFDB based on the talk I gave at FoCM in
December 2014 is now available (Open Access) at

http://www.springer.com/-/3/AVL5RydpAgfPWjhr63PM .

Thanks to all who contributed.

John

︠db9430c7-bb18-4440-bb4f-f8ac4d9c3789︠

︠d4a2cc68-555e-4720-a61b-50511f718211︠

︠2dd6a4b4-53b5-4d56-922e-db810e1dce16i︠
%md
## 4. Magma versus Sage

If you want to do a range of explicit computations with elliptic curves, you will very likely use Sage or Magma.  If you're **really** serious, you'll use both.

Note, as mentioned above, that both Sage and Magma are far ahead of all other software for elliptic curves.

- [Magma reference manual about elliptic curves.](https://magma.maths.usyd.edu.au/magma/handbook/part/16)

- [Sage reference manual about elliptic curves.](http://doc.sagemath.org/html/en/reference/plane_curves/index.html#elliptic-curves)

- [Pari reference manual about elliptic curves.](http://pari.math.u-bordeaux.fr/dochtml/html.stable/Functions_related_to_elliptic_curves.html) -- pari is part of Sage and has some unique powerful functionality, e.g., `ellheegner`...

### History:

When I started contributing to Magma in 1999, I remember that it was way, way behind PARI.
I remember having lunch with John Cannon (founder of Magma), and telling him we could
"kill Pari" if only Magma would have dramatically faster code for computing
$a_p = p + 1 - \#E(\FF_p)$; he responded "I don't want to kill Pari."

In any case, a few years later, John wisely hired Mark Watkins to work fulltime on Magma,
and Mark has been working there for over a decade.   Mark is definitely one of the top
people in the world at implementing (and using) computational number theory algorithms,
and he's ensured that Magma can do a lot.  Some of that "do a lot" means catching up with (and surpassing!)
what was in Pari and Sage for a long time (e.g., point counting, $p$-adic $L$-functions, etc.)

However, in addition, many people have visited Sydney and added functionality for doing higher descents
to Magma, which is **not available in any open source software**.   Search for Magma in [this paper](http://arxiv.org/abs/1602.01894)
to see how, even today, there seems to be no open source way to compute the rank of the curve $y^2 = x^3 + 169304x + 25788938$.

### Situation today

There are several elliptic curves algorithms available **only in Magma** (e.g., higher descents) ... and some available **only in Sage** ($L$-function rank bounds, some overconvergent modular symbols, zeros of $L$-functions, images of Galois representations).  I could be wrong about stuff not in Sage, since **WITH MONEY** almost anything can get implemented in a year...  And Magma has money.

The code bases are completely separate, which is a very good thing.
Any time something gets implemented in one, it gets (or should get) tested via a big run
through tables of elliptic curves up to some bound.  This usually results in numerous
bugs being found.  I remember  refereeing the "integral points" code in Sage by running it
against all curves up to some bound and comparing to what Magma output, and getting many
discrepancies, which showed that there were bugs in both Sage and Magma.

However, we would be way better off if Sage could do everything Magma does.  For example, isn't this disturbing???

    > On Feb 16, 2016, at 8:33 AM, Matthew Young <[e-mail]> wrote:
    > In fact, we didn't get rank 0 using any
    >> analytic approach, and had to resort to some subtle descent machinery
    >> using Magma:
    >>
    >> y^2 = x^3 + 169304*x + 25788938 and y^2 = x^3 + 77108*x − 22146514.
    >
    > For fun, I had my student see if she could compute the central L-values
    > for these two curves.  She got analytic values of Sha of 16 and 4 (I don't
    > remember now which was which).  One curve took about 5 hours, and the
    > other about 3 hours.

    This is troubling. Both of these curves have S^2(E) = (Z/2)^2 and the
    Cassels-Tate pairing (as computed by Magma) is trivial on S^2(E). This
    means [2]_* : S^4(E) —> S^2(E) is a surjection, so Sha(E)[2]/2 Sha(E)[4]
    is trivial. This can’t happen when the order of Sha is 4.

    Maybe I’m misunderstanding something. If I’m not, then either the value
    of 4 for Sha is incorrect, or there’s a serious bug in Magma’s
    CasselsTatePairing command.

    If there’s a bug, we should look for the occurrence of smallest conductor
    and send it to Steve Donnelly.

    Jamie

4. Magma versus Sage

If you want to do a range of explicit computations with elliptic curves, you will very likely use Sage or Magma. If you're really serious, you'll use both.

Note, as mentioned above, that both Sage and Magma are far ahead of all other software for elliptic curves.

• Magma reference manual about elliptic curves.

• Sage reference manual about elliptic curves.

• Pari reference manual about elliptic curves. -- pari is part of Sage and has some unique powerful functionality, e.g., ellheegner...

History:

When I started contributing to Magma in 1999, I remember that it was way, way behind PARI. I remember having lunch with John Cannon (founder of Magma), and telling him we could "kill Pari" if only Magma would have dramatically faster code for computing $a_p = p + 1 - \#E(\FF_p)$; he responded "I don't want to kill Pari."

In any case, a few years later, John wisely hired Mark Watkins to work fulltime on Magma, and Mark has been working there for over a decade. Mark is definitely one of the top people in the world at implementing (and using) computational number theory algorithms, and he's ensured that Magma can do a lot. Some of that "do a lot" means catching up with (and surpassing!) what was in Pari and Sage for a long time (e.g., point counting, $p$-adic $L$-functions, etc.)

However, in addition, many people have visited Sydney and added functionality for doing higher descents to Magma, which is not available in any open source software. Search for Magma in this paper to see how, even today, there seems to be no open source way to compute the rank of the curve $y^2 = x^3 + 169304x + 25788938$.

Situation today

There are several elliptic curves algorithms available only in Magma (e.g., higher descents) ... and some available only in Sage ($L$-function rank bounds, some overconvergent modular symbols, zeros of $L$-functions, images of Galois representations). I could be wrong about stuff not in Sage, since WITH MONEY almost anything can get implemented in a year... And Magma has money.

The code bases are completely separate, which is a very good thing. Any time something gets implemented in one, it gets (or should get) tested via a big run through tables of elliptic curves up to some bound. This usually results in numerous bugs being found. I remember refereeing the "integral points" code in Sage by running it against all curves up to some bound and comparing to what Magma output, and getting many discrepancies, which showed that there were bugs in both Sage and Magma.

However, we would be way better off if Sage could do everything Magma does. For example, isn't this disturbing???

> On Feb 16, 2016, at 8:33 AM, Matthew Young <[e-mail]> wrote:
> In fact, we didn't get rank 0 using any
>> analytic approach, and had to resort to some subtle descent machinery
>> using Magma:
>>
>> y^2 = x^3 + 169304*x + 25788938 and y^2 = x^3 + 77108*x − 22146514.
>
> For fun, I had my student see if she could compute the central L-values
> for these two curves.  She got analytic values of Sha of 16 and 4 (I don't
> remember now which was which).  One curve took about 5 hours, and the
> other about 3 hours.

This is troubling. Both of these curves have S^2(E) = (Z/2)^2 and the
Cassels-Tate pairing (as computed by Magma) is trivial on S^2(E). This
means [2]_* : S^4(E) —> S^2(E) is a surjection, so Sha(E)[2]/2 Sha(E)[4]
is trivial. This can’t happen when the order of Sha is 4.

Maybe I’m misunderstanding something. If I’m not, then either the value
of 4 for Sha is incorrect, or there’s a serious bug in Magma’s
CasselsTatePairing command.

If there’s a bug, we should look for the occurrence of smallest conductor
and send it to Steve Donnelly.

Jamie

#y^2 = x^3 + 169304*x + 25788938
E = EllipticCurve([169304, 25788938])

E.conductor()

597895772568922304

N(sqrt(E.conductor()))

7.73237203301110e8

Example computation using my favorite curve in Sage and Magma.

# My fav curve:
E = EllipticCurve('389a')
show(E)

$\displaystyle y^2 + y = x^{3} + x^{2} - 2 x$

E.ainvs()

(0, 1, 1, -2, 0)

E.rank()

2

E.integral_points()

[(-2 : 0 : 1), (-1 : 1 : 1), (0 : 0 : 1), (1 : 0 : 1), (3 : 5 : 1), (4 : 8 : 1), (6 : 15 : 1), (39 : 246 : 1), (133 : 1539 : 1), (188 : 2584 : 1)]

%magma
E := EllipticCurve([0,1,1,-2,0]);
print Rank(E);
print IntegralPoints(E);

2 [ (-2 : 0 : 1), (-1 : -2 : 1), (0 : -1 : 1), (1 : -1 : 1), (3 : -6 : 1), (4 : 8 : 1), (6 : 15 : 1), (39 : -247 : 1), (133 : -1540 : 1), (188 : -2585 : 1) ] [ <(-2 : 0 : 1), 1>, <(-1 : -2 : 1), 1>, <(0 : -1 : 1), 1>, <(1 : -1 : 1), 1>, <(3 : -6 : 1), 1>, <(4 : 8 : 1), 1>, <(6 : 15 : 1), 1>, <(39 : -247 : 1), 1>, <(133 : -1540 : 1), 1>, <(188 : -2585 : 1), 1> ]

︠7dbe7ce1-ff89-4309-aa91-b1d271930b80︠

︠5695d3a1-d411-469a-b2bf-6c37262d6fb4i︠
%md
**Exercise:**
1. Make up a few elliptic curves and compute the integral points on them.

2. Try to find an elliptic curve with at least 12 integral points on it.  You can search using Google if you want... or whatever.

3. Make a guess: do you think the number of integral points on elliptic curves is uniformly bounded, or are there elliptic curves over $\QQ$ with arbitrarily many integral points?  (If not brave enough to make a guess, how might you use tables to make a guess.  What computations would you do?)

4. Make a guess: do you think the ranks of elliptic curves over $\QQ$ are uniformly bounded, or are there elliptic curves with arbitrarily large rank?

Exercise:

1. Make up a few elliptic curves and compute the integral points on them.

2. Try to find an elliptic curve with at least 12 integral points on it. You can search using Google if you want... or whatever.

3. Make a guess: do you think the number of integral points on elliptic curves is uniformly bounded, or are there elliptic curves over $\QQ$ with arbitrarily many integral points? (If not brave enough to make a guess, how might you use tables to make a guess. What computations would you do?)

4. Make a guess: do you think the ranks of elliptic curves over $\QQ$ are uniformly bounded, or are there elliptic curves with arbitrarily large rank?

︠8e5819f9-0407-405d-8fe7-2f44c51ec602︠

︠0298c9dc-f615-4a34-a8bc-f6aff5736a60︠

︠c56e0bf5-c939-49c4-90c9-665f34f240e9︠

︠9d8a5c8d-13b4-40e4-8e11-dd46b589d6db︠

︠6bd16bf2-a599-4ae0-9ea7-13b11e4f6845i︠
%md
# Modular Forms (start)

Read the theoretical definition of modular forms somewhere, e.g., in my book, before Wednesday: http://wstein.org/books/modform/
I'm going to assume you know the basic definitions, and just tell you how to compute with them:

 - What commands to type and what you get
 - The basic idea behind the algorithms that are being used (mainly "modular symbols")

Modular Forms (start)

Read the theoretical definition of modular forms somewhere, e.g., in my book, before Wednesday: http://wstein.org/books/modform/ I'm going to assume you know the basic definitions, and just tell you how to compute with them:

• What commands to type and what you get

• The basic idea behind the algorithms that are being used (mainly "modular symbols")

M = ModularForms(43)
M

Modular Forms space of dimension 4 for Congruence Subgroup Gamma0(43) of weight 2 over Rational Field

M.basis()

[ q + 2*q^5 + O(q^6), q^2 - 1/2*q^4 + q^5 + O(q^6), q^3 - 1/2*q^4 + 2*q^5 + O(q^6), 1 + 4/7*q + 12/7*q^2 + 16/7*q^3 + 4*q^4 + 24/7*q^5 + O(q^6) ]

show(M.newforms('a'))

[$\displaystyle q - 2q^{2} - 2q^{3} + 2q^{4} - 4q^{5} + O(q^{6})$, $\displaystyle q + a_{1}q^{2} - a_{1}q^{3} + \left(-a_{1} + 2\right)q^{5} + O(q^{6})$]

show(M.hecke_matrix(2))

$\displaystyle \left(\begin{array}{rrrr} 0 & 2 & -2 & 0 \\ 1 & -\frac{1}{2} & -\frac{3}{2} & 0 \\ 0 & -\frac{1}{2} & -\frac{3}{2} & 0 \\ 0 & 0 & 0 & 3 \end{array}\right)$