search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.36k stars 462 forks source link

Integral points on elliptic curves over number fields #10973

Open 667aa960-5c62-4445-bf8d-25c93fb0a27b opened 13 years ago

667aa960-5c62-4445-bf8d-25c93fb0a27b commented 13 years ago

Incorporate work done by Rado Kirov and Jackie Anderson at Sage Days 22, based on Magma implementation by Cremona's student Nook.

See also #12095 (now tagged as duplicate).

Converted to git by John Cremona, 2013-12-18

CC: @JohnCremona @sagetrac-gagansekhon @jbalakrishnan

Component: elliptic curves

Keywords: sd32

Author: Justin Walker, Aly Deines, Jennifer Balakrishnan

Branch/Commit: public/10973 @ 0774d59

Issue created by migration from https://trac.sagemath.org/ticket/10973

667aa960-5c62-4445-bf8d-25c93fb0a27b commented 13 years ago

Attachment: intpts.sage.gz

667aa960-5c62-4445-bf8d-25c93fb0a27b commented 13 years ago

Attachment: ell_int_points.py.gz

This code goes into "sage/schemes/elliptiic_curves". It works, but needs work.

667aa960-5c62-4445-bf8d-25c93fb0a27b commented 13 years ago
comment:2

New version of .py file, fixing a problem with bogus interaction with Maxima.

4c1287a7-ef03-4280-b43d-41d57e0137f9 commented 13 years ago

Attachment: trac_10973.gz

667aa960-5c62-4445-bf8d-25c93fb0a27b commented 13 years ago
comment:3

The patch trac_10973 should apply w/o problems against sage-4.7.alpha1.

The previous attachments are replaced by this one.

667aa960-5c62-4445-bf8d-25c93fb0a27b commented 13 years ago
comment:4

This patch is related to, and appears to fix, the problem described by #10152.

667aa960-5c62-4445-bf8d-25c93fb0a27b commented 13 years ago

Attachment: trac_10973.2.gz

Updated patch with code to reject requests w/o generators; replaces previous patch of same name.

4c1287a7-ef03-4280-b43d-41d57e0137f9 commented 13 years ago
comment:5

minor error in all.py, +from ell_int_points.py import should be +from ell_int_points import The new patch that I will be uploading in a minute fixes that.

4c1287a7-ef03-4280-b43d-41d57e0137f9 commented 13 years ago

Attachment: trac_10973.patch.gz

4dfe6752-6233-4f7f-8e0e-e1363b12c1b7 commented 13 years ago

Attachment: trac_10973.2.patch.gz

This replaces the previous patch

4dfe6752-6233-4f7f-8e0e-e1363b12c1b7 commented 13 years ago
comment:7

The tests pass on all files except ell_ergos.py and constructor.py, specifically, the tests which call S_integral_points([]) are having issues.

All examples from the paper referenced now pass as do all examples from #10152, so once this is implemented, this also fixes #10152.

4dfe6752-6233-4f7f-8e0e-e1363b12c1b7 commented 13 years ago

replaces previous patch

4dfe6752-6233-4f7f-8e0e-e1363b12c1b7 commented 13 years ago
comment:8

Attachment: trac_10973.3.patch.gz

This should do it. This is a small fix to the previous patch, it now passes the tests.

4dfe6752-6233-4f7f-8e0e-e1363b12c1b7 commented 13 years ago

Changed author from Justin Walker to Justin Walker, Aly Deines

4dfe6752-6233-4f7f-8e0e-e1363b12c1b7 commented 13 years ago

Changed author from Justin Walker, Aly Deines to Justin Walker, Aly Deines, Jennifer Balakrishnan

williamstein commented 13 years ago

Attachment: report.txt

This is a list of 14 issues I had reading through trac_10973.3.patch.

williamstein commented 13 years ago
comment:11

Please see the rather long file report.txt that I posted with a bunch of issues I noticed when reading through trac_10973.3.patch.

4dfe6752-6233-4f7f-8e0e-e1363b12c1b7 commented 13 years ago

Attachment: Trac10973.4.patch.gz

Replaces previous patch.

4dfe6752-6233-4f7f-8e0e-e1363b12c1b7 commented 13 years ago
comment:12

Trac10973.4.patch addresses everything in report.txt.

This returns the same result as the original integral_points over Q with all curves of conductor up to 1000 (and also agrees with Magma). This also finds the missing points referred to in ticket #10152.

We compared times on all curves over Q of conductor less then 1000; the original implementation was usually 2 to 8 times faster, though in certain instances it did not find all integral points (this was ticket #10152). So this is a bit of a slowdown.

If E is a curve over Q, then E.integral_points() calls the method in ell_rational_points.py (the previous, faster, not always correct, method).

4dfe6752-6233-4f7f-8e0e-e1363b12c1b7 commented 13 years ago

Attachment: Trac10973.5.patch.gz

Replaces previous patch, corrects Authors.

williamstein commented 13 years ago
comment:13

Replying to @adeines:

If E is a curve over Q, then E.integral_points() calls the method in ell_rational_points.py (the previous, faster, not always correct, method).

Why? Surely it would definitely be better to return a correct answer by default. I can imagine leaving the old code in with an not-by-default option to call it and docs that mention it is faster.

williamstein commented 13 years ago

Attachment: report2.txt

second short report -- looking good!

williamstein commented 13 years ago
comment:14

Here's a list of curves where your code and the latest (?) Magma V2.17-4 give different answers. I checked these by hand, and Magma is clearly totally wrong (missing definitely integral points) in each case.

1264i1, 1328b1, 1656f1, 1848i1

williamstein commented 13 years ago

Changed keywords from none to sd32

4dfe6752-6233-4f7f-8e0e-e1363b12c1b7 commented 13 years ago

replaces previous patch

JohnCremona commented 12 years ago
comment:17

Attachment: Trac10973.6.patch.gz

Replying to @williamstein:

Here's a list of curves where your code and the latest (?) Magma V2.17-4 give different answers. I checked these by hand, and Magma is clearly totally wrong (missing definitely integral points) in each case.

1264i1, 1328b1, 1656f1, 1848i1

Update. Using Sage-4.7.2 and Magma V2.17-9, these all agree:

sage: E = EllipticCurve("1264i1")
sage: E.integral_points()
[(2 : 0 : 1), (4 : 10 : 1), (18 : 80 : 1), (246404 : 122312970 : 1)]
sage: magma(E).IntegralPoints()
[ (2 : 0 : 1), (4 : -10 : 1), (18 : 80 : 1), (246404 : 122312970 : 1) ]
sage: E = EllipticCurve("1328b1")
sage: E.integral_points()
[(2 : 2 : 1), (4386 : 290438 : 1)]
sage: magma(E).IntegralPoints()
[ (2 : 2 : 1), (4386 : 290438 : 1) ]
sage: E = EllipticCurve("1656f1")
sage: E.integral_points()
[(3 : 0 : 1), (6 : 18 : 1), (27 : 144 : 1), (336678 : 195353910 : 1)]
sage: magma(E).IntegralPoints()
[ (3 : 0 : 1), (6 : -18 : 1), (27 : 144 : 1), (336678 : -195353910 : 1) ]
sage: E = EllipticCurve("1848i1")
sage: E.integral_points()
[(2 : 3 : 1), (3206 : 181557 : 1)]
sage: magma(E).IntegralPoints()
[ (2 : 3 : 1), (3206 : 181557 : 1) ]

That is using vanilla Sage (i.e. without any patches from this ticket). I am about to do a more systematic test.

JohnCremona commented 12 years ago
comment:18

I am testing this now. It looks as if all the points raised in William's last report have been dealt with.

It looks odd to me to have the main integral_points function which is a method of the EllipticCurve_number_field class defined in a separate file, so that in ell_number_field.py you only see the line integral_points = integral_points. I did not know that would work! But, given that it does, it is cleaner. I will check to see that the documentation is not thereby hidden.

JohnCremona commented 12 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,4 @@
 Incorporate work done by Rado Kirov and Jackie Anderson at Sage Days 22, based on Magma implementation by Cremona's student Nook.

+Apply only Trac10973.7.patch
JohnCremona commented 12 years ago
comment:19

Positive review. In my reviewer's patch I fix the following:

  1. Now applies to 4.7.2 with no fuzz.
  2. Added QQ to import list on line 332 of ell_number_field.py, otherwise testing ell_int_pts failed, but testing ell_number_field did not -- since the test for that function silverman_height_bounds was incomplete! I fixed that too.
  3. Fixed a warning in docbuild by adding a blank line at line 69 of the same file.

It is now true that for an elliptic curve E over Q we have both the new E.silverman_height_bounds(), which gives lower and upper bounds, and the old E.silverman_height_bound(), which only gives one of them. The latter can be deleted but that will require some tweaking of any code which uses it. I have left that for another ticket.

JohnCremona commented 12 years ago

Replaces all previous: reviewer's patch

JohnCremona commented 12 years ago
comment:20

Attachment: Trac10973.7.patch.gz

Replying to @JohnCremona:

I am testing this now. It looks as if all the points raised in William's last report have been dealt with.

The first curve where Sage-4.7.2 fails to find the same number of integral points as Magma V2.17-9 is 2082a1 where Sage-4.7.2 finds x-coordinates -11,-2,4,13 but not 507525709 (!). But the new version does find that last one.

I will carry on testing, but there is no need to delay merging this (expect perhaps if I find a curve for which the new code fails to find all known points).

JohnCremona commented 12 years ago
comment:21

Replying to @JohnCremona:

Replying to @JohnCremona:

I am testing this now. It looks as if all the points raised in William's last report have been dealt with.

The first curve where Sage-4.7.2 fails to find the same number of integral points as Magma V2.17-9 is 2082a1 where Sage-4.7.2 finds x-coordinates -11,-2,4,13 but not 507525709 (!). But the new version does find that last one.

I will carry on testing, but there is no need to delay merging this (expect perhaps if I find a curve for which the new code fails to find all known points).

For all curves of conductor up to 10000, there are precisely 3 where Sage-4.7.2 misses integral points compared with Magma V2.17-9, namely 2082a1, 6104b1, 8470g1, 8470g2; in each case just one point is missed. And the new code agrees with Magma in all these cases. Regarding timings, up to 10000 Sage-4.7.2 took 157m while Magma took 943m; that may be an unfair comparison though since Sage took generators from the DB while Magma (I think) computed them from scratch. I will redo this with the current patch applied.

jdemeyer commented 12 years ago

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
 Incorporate work done by Rado Kirov and Jackie Anderson at Sage Days 22, based on Magma implementation by Cremona's student Nook.

-Apply only Trac10973.7.patch
+Apply only [attachment: Trac10973.7.patch](https://github.com/sagemath/sage-prod/files/10652394/Trac10973.7.patch.gz)
jdemeyer commented 12 years ago

Reviewer: John Cremona

jdemeyer commented 12 years ago
comment:23

I unfortunately get several doctest failures (with sage-4.8.alpha2 + various patches). Did you test this patch with the new PARI (merged in sage-4.8.alpha1)? I am also afraid that there are speed regressions, I am seeing a timeout:

sage -t  -force_lib devel/sage/sage/schemes/elliptic_curves/ell_int_points.py
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.8.alpha3/devel/sage-main/sage/schemes/elliptic_curves/ell_int_points.py", line 12:
    sage: E.integral_points()
Expected:
    [(-11 : -19 : 1), (-2 : 29 : 1), (4 : -16 : 1), (13 : -43 : 1), (507525709 : 11433453531221 : 1)]
Got:
    [(-11 : 29 : 1), (-2 : -28 : 1), (4 : 11 : 1), (13 : 29 : 1), (507525709 : -11433961056931 : 1)]
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.8.alpha3/devel/sage-main/sage/schemes/elliptic_curves/ell_int_points.py", line 22:
    sage: E.integral_points()
Expected:
    [(-41 : -266 : 1), (-27 : 294 : 1), (-13 : 266 : 1), (19 : 74 : 1), (22
    : -49 : 1), (27 : -6 : 1), (29 : -14 : 1), (43 : -154 : 1), (53 : 266 :
    1), (71 : 490 : 1), (414 : -8379 : 1), (1639 : 66346 : 1), (1667 :
    -68054 : 1), (23036693 : 110568192854 : 1)]
Got:
    [(-41 : 266 : 1), (-27 : 294 : 1), (-13 : -266 : 1), (19 : 74 : 1), (22 : -49 : 1), (27 : 6 : 1), (29 : -14 : 1), (43 : 154 : 1), (53 : 266 : 1), (71 : -490 : 1), (414 : 8379 : 1), (1639 : 66346 : 1), (1667 : 68054 : 1), (23036693 : 110568192854 : 1)]
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.8.alpha3/devel/sage-main/sage/schemes/elliptic_curves/ell_int_points.py", line 31:
    sage: E.integral_points(algorithm = "old")
Expected:
    [(-1 : 0 : 1), (0 : 6 : 1), (3 : 12 : 1), (10 : 33 : 1), (15 : 56 : 1), (24 : 110 : 1), (43 : 264
    : 1), (98 : 924 : 1), (395 : 7656 : 1)]
Got:
    [(-1 : 0 : 1), (0 : 6 : 1), (3 : 12 : 1), (10 : 33 : 1), (15 : 56 : 1), (24 : 110 : 1), (43 : 264 : 1), (98 : 924 : 1), (395 : 7656 : 1), (1681690 : 2179974753 : 1)]
*********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.8.alpha3/devel/sage-main/sage/schemes/elliptic_curves/ell_int_points.py", line 34:
    sage: E.integral_points()
Expected:
    [(-1 : 0 : 1), (0 : -7 : 1), (3 : 12 : 1), (10 : -44 : 1), (15 : 56 :
    1), (24 : 110 : 1), (43 : 264 : 1), (98 : -1023 : 1), (395 : -8052 : 1),
    (1681690 : 2179974753 : 1)]
Got:
    [(-1 : 0 : 1), (0 : 6 : 1), (3 : -16 : 1), (10 : 33 : 1), (15 : -72 : 1), (24 : 110 : 1), (43 : -308 : 1), (98 : -1023 : 1), (395 : 76
56 : 1), (1681690 : -2181656444 : 1)]
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.8.alpha3/devel/sage-main/sage/schemes/elliptic_curves/ell_int_points.py", line 46:
    sage: E.integral_points()
Expected:
    [(-14 : 17 : 1), (-12 : -22 : 1), (-7 : 38 : 1), (-1 : 22 : 1), (0 : -18
    : 1), (13 : -22 : 1), (14 : -32 : 1), (21 : 66 : 1), (33 : -192 : 1),
    (44 : 257 : 1), (63 : 458 : 1), (98 : -1012 : 1), (175 : -2398 : 1),
    (1533 : -60792 : 1), (1561 : 60896 : 1), (18888968 : -82103620687 : 1)]
Got:
    [(-14 : 17 : 1), (-12 : 33 : 1), (-7 : -32 : 1), (-1 : 22 : 1), (0 : -18 : 1), (13 : -22 : 1), (14 : 17 : 1), (21 : -88 : 1), (33 : -1
92 : 1), (44 : -302 : 1), (63 : 458 : 1), (98 : -1012 : 1), (175 : 2222 : 1), (1533 : -60792 : 1), (1561 : 60896 : 1), (18888968 : -821036
20687 : 1)]
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.8.alpha3/devel/sage-main/sage/schemes/elliptic_curves/ell_int_points.py", line 131:
    sage: ellpts.abs_log_height(list(P2))
Expected:
    1.09861228866811
Got:
    3.21887582486820
**********************************************************************
The following tests failed:

        sage -t  -force_lib devel/sage/doc/en/bordeaux_2008/elliptic_curves.rst # Time out
        sage -t  -force_lib devel/sage/sage/schemes/elliptic_curves/ell_int_points.py # 6 doctests failed
jdemeyer commented 12 years ago
comment:24

Minor comment: could you format the copyright notice of the added file as shown in http://sagemath.org/doc/developer/conventions.html#headings-of-sage-library-code-files. I am also very surprised to see William Stein in the copyright statement, he is not even an author of this ticket.

jdemeyer commented 12 years ago
comment:25

Line 617: replace by initQ = 10^118 :-)

jdemeyer commented 12 years ago
comment:26

If you word-wrap doctest results (which is a good idea), try to word-wrap them more logically, i.e. write

[(-41 : -266 : 1), (-27 : 294 : 1), (-13 : 266 : 1), (19 : 74 : 1),
(22 : -49 : 1), (27 : -6 : 1), (29 : -14 : 1), (43 : -154 : 1),
(53 : 266 : 1), (71 : 490 : 1), (414 : -8379 : 1), (1639 : 66346 : 1),
(1667 : -68054 : 1), (23036693 : 110568192854 : 1)]

instead of

[(-41 : -266 : 1), (-27 : 294 : 1), (-13 : 266 : 1), (19 : 74 : 1), (22 
: -49 : 1), (27 : -6 : 1), (29 : -14 : 1), (43 : -154 : 1), (53 : 266 : 
1), (71 : 490 : 1), (414 : -8379 : 1), (1639 : 66346 : 1), (1667 : 
-68054 : 1), (23036693 : 110568192854 : 1)]
jdemeyer commented 12 years ago
comment:27

In the documentation, you refer to ticket 10152. This should be 10973 instead.

jdemeyer commented 12 years ago
comment:28

Indentation at the top should probably be

r"""
Integral Points of Elliptic Curves over Number Fields

The following examples are from trac ticket #10152.  Previously Magma was finding ore 
integral points on these curves than Sage.  We resolved this issue.

EXAMPLES::

    sage: E = EllipticCurve('2082a1')
    sage: E.integral_points(algorithm = "old")
    [(-11 : 29 : 1), (-2 : 29 : 1), (4 : 11 : 1), (13 : 29 : 1)]
    sage: E.integral_points()
    [(-11 : -19 : 1), (-2 : 29 : 1), (4 : -16 : 1), (13 : -43 : 1), (507525709 : 11433453531221 : 1)]

::

    sage: ...
JohnCremona commented 12 years ago
comment:29

Since setting this to positive review I have done more testing and was about to revert it to "needs work" myself anyway: in a test of all curves to conductor 10000 I found that the new code appears to hang on 9615d1.

JohnCremona commented 12 years ago
comment:30

See comments at #12095

JohnCremona commented 12 years ago

Description changed:

--- 
+++ 
@@ -1,4 +1,6 @@
 Incorporate work done by Rado Kirov and Jackie Anderson at Sage Days 22, based on Magma implementation by Cremona's student Nook.

-Apply only [attachment: Trac10973.7.patch](https://github.com/sagemath/sage-prod/files/10652394/Trac10973.7.patch.gz)
+See also #12095 (now tagged as duplicate).

+Apply only Trac10973.7.patch
+
JohnCremona commented 12 years ago

Changed reviewer from John Cremona to none

jdemeyer commented 12 years ago
comment:31

Did you intentionally remove the reviewer and milestone fields? If you did, I don't understand why.

novoselt commented 12 years ago
comment:32

For the patchbot: apply Trac10973.7.patch

JohnCremona commented 12 years ago
comment:33

Replying to @jdemeyer:

Did you intentionally remove the reviewer and milestone fields? If you did, I don't understand why.

I did not (at least, not intentionally).

JohnCremona commented 12 years ago
comment:34

Noting that one effect of this code is to improve integral-point-finding over QQ (though it is still not always correct, see comment 29 above, we should at least add a stopgap trigger for integral points over QQ, to alert the user to known issues. Example: without this patch, 

sage: E = EllipticCurve("2082a1")
sage: P = E.gens()[0]
sage: E.integral_points()
[(-11 : 29 : 1), (-2 : 29 : 1), (4 : 11 : 1), (13 : 29 : 1)]
sage: 13*P
(507525709 : 11433453531221 : 1)
fchapoton commented 11 years ago

Description changed:

--- 
+++ 
@@ -2,5 +2,4 @@

 See also #12095 (now tagged as duplicate).

-Apply only Trac10973.7.patch
-
+Apply only trac_10973_v8.patch
fchapoton commented 11 years ago
comment:35

patchbot, apply only trac_10973_v8.patch