Opened 11 years ago
Last modified 7 weeks ago
#10973 needs_work enhancement
Integral points on elliptic curves over number fields — at Version 22
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: | John Cremona |
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.
Apply only Trac10973.7.patch
Change History (35)
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
This code goes into "sage/schemes/elliptiic_curves". It works, but needs work.