Opened 11 years ago
Last modified 7 weeks ago
#10973 needs_work enhancement
Integral points on elliptic curves over number fields — at Version 35
Reported by: | justin | Owned by: | cremona |
---|---|---|---|
Priority: | major | Milestone: | sage-9.7 |
Component: | elliptic curves | Keywords: | sd32 |
Cc: | cremona, gagansekhon, jen | Merged in: | |
Authors: | Justin Walker, Aly Deines, Jennifer Balakrishnan | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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).
Apply only trac_10973_v8.patch
Change History (48)
Changed 11 years ago by
comment:1 Changed 11 years ago by
- Type changed from PLEASE CHANGE to enhancement
Changed 11 years ago by
comment:2 Changed 11 years ago by
New version of .py file, fixing a problem with bogus interaction with Maxima.
Changed 11 years ago by
comment:3 Changed 11 years ago by
The patch trac_10973 should apply w/o problems against sage-4.7.alpha1.
The previous attachments are replaced by this one.
comment:4 Changed 11 years ago by
This patch is related to, and appears to fix, the problem described by #10152.
Changed 11 years ago by
Updated patch with code to reject requests w/o generators; replaces previous patch of same name.
comment:5 Changed 11 years ago by
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.
Changed 11 years ago by
comment:6 Changed 11 years ago by
- Cc gagansekhon added
comment:7 Changed 11 years ago by
comment:8 Changed 11 years ago by
- Status changed from new to needs_review
This should do it. This is a small fix to the previous patch, it now passes the tests.
comment:9 Changed 11 years ago by
comment:10 Changed 11 years ago by
comment:11 Changed 11 years ago by
- Status changed from needs_review to needs_work
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.
comment:12 follow-up: ↓ 13 Changed 11 years ago by
- Status changed from needs_work to needs_review
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).
comment:13 in reply to: ↑ 12 Changed 11 years ago by
Replying to aly.deines:
If
E
is a curve overQ
, 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.
comment:14 follow-up: ↓ 17 Changed 11 years ago by
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
comment:15 Changed 11 years ago by
- Cc jen added
comment:16 Changed 11 years ago by
- Keywords sd32 added
comment:17 in reply to: ↑ 14 Changed 10 years ago by
Replying to was:
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.
comment:18 follow-up: ↓ 20 Changed 10 years ago by
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.
comment:19 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_review to positive_review
Positive review. In my reviewer's patch I fix the following:
- Now applies to 4.7.2 with no fuzz.
- 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.
- 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.
comment:20 in reply to: ↑ 18 ; follow-up: ↓ 21 Changed 10 years ago by
Replying to cremona:
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).
comment:21 in reply to: ↑ 20 Changed 10 years ago by
Replying to cremona:
Replying to cremona:
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.
comment:22 Changed 10 years ago by
- Description modified (diff)
- Milestone set to sage-4.8
- Reviewers set to John Cremona
comment:23 Changed 10 years ago by
- Status changed from positive_review to needs_work
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
comment:24 Changed 10 years ago by
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.
comment:25 Changed 10 years ago by
Line 617: replace by initQ = 10^118
:-)
comment:26 Changed 10 years ago by
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)]
comment:27 Changed 10 years ago by
In the documentation, you refer to ticket 10152. This should be 10973 instead.
comment:28 Changed 10 years ago by
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: ...
comment:29 Changed 10 years ago by
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.
comment:30 Changed 10 years ago by
- Description modified (diff)
- Milestone sage-4.8 deleted
- Reviewers John Cremona deleted
See comments at #12095
comment:31 follow-up: ↓ 33 Changed 10 years ago by
Did you intentionally remove the reviewer and milestone fields? If you did, I don't understand why.
comment:32 Changed 10 years ago by
For the patchbot: apply Trac10973.7.patch
comment:33 in reply to: ↑ 31 Changed 10 years ago by
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).
comment:34 Changed 10 years ago by
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)
comment:35 Changed 9 years ago by
- Description modified (diff)
patchbot, apply only trac_10973_v8.patch
This code goes into "sage/schemes/elliptiic_curves". It works, but needs work.