Opened 11 years ago

Last modified 3 months ago

#10973 needs_work enhancement

Integral points on elliptic curves over number fields — at Version 19

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:

Status badges

Description (last modified by cremona)

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 (32)

Changed 11 years ago by justin

comment:1 Changed 11 years ago by justin

  • Type changed from PLEASE CHANGE to enhancement

Changed 11 years ago by justin

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

comment:2 Changed 11 years ago by justin

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

Changed 11 years ago by gagansekhon

comment:3 Changed 11 years ago by justin

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 justin

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

Changed 11 years ago by justin

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

comment:5 Changed 11 years ago by gagansekhon

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 gagansekhon

comment:6 Changed 11 years ago by gagansekhon

  • Cc gagansekhon added

Changed 11 years ago by aly.deines

This replaces the previous patch

comment:7 Changed 11 years ago by aly.deines

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.

Changed 11 years ago by aly.deines

replaces previous patch

comment:8 Changed 11 years ago by aly.deines

  • 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 aly.deines

  • Authors changed from Justin Walker to Justin Walker, Aly Deines

comment:10 Changed 11 years ago by aly.deines

  • Authors changed from Justin Walker, Aly Deines to Justin Walker, Aly Deines, Jennifer Balakrishnan

Changed 11 years ago by was

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

comment:11 Changed 11 years ago by was

  • 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.

Changed 11 years ago by aly.deines

Replaces previous patch.

comment:12 follow-up: Changed 11 years ago by aly.deines

  • 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).

Changed 11 years ago by aly.deines

Replaces previous patch, corrects Authors.

comment:13 in reply to: ↑ 12 Changed 11 years ago by was

Replying to aly.deines:

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.

Changed 11 years ago by was

second short report -- looking good!

comment:14 follow-up: Changed 11 years ago by 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

comment:15 Changed 11 years ago by jen

  • Cc jen added

comment:16 Changed 11 years ago by was

  • Keywords sd32 added

Changed 11 years ago by aly.deines

replaces previous patch

comment:17 in reply to: ↑ 14 Changed 11 years ago by cremona

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 Changed 11 years ago by cremona

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 11 years ago by cremona

  • Description modified (diff)
  • Status changed from needs_review to positive_review

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.

Changed 11 years ago by cremona

Replaces all previous: reviewer's patch

Note: See TracTickets for help on using tickets.