Integral points on elliptic curves over number fields

[RalphieBoy]

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

[RalphieBoy]

Attachment: intpts.sage.gz

[RalphieBoy]

Attachment: ell_int_points.py.gz

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

[RalphieBoy]

comment:2

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

[sagetrac-gagansekhon]

Attachment: trac_10973.gz

[RalphieBoy]

comment:3

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

The previous attachments are replaced by this one.

[RalphieBoy]

comment:4

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

[RalphieBoy]

Attachment: trac_10973.2.gz

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

[sagetrac-gagansekhon]

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.

[sagetrac-gagansekhon]

Attachment: trac_10973.patch.gz

[adeines]

Attachment: trac_10973.2.patch.gz

This replaces the previous patch

[adeines]

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.

[adeines]

replaces previous patch

[adeines]

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.

[adeines]

Changed author from Justin Walker to Justin Walker, Aly Deines

[adeines]

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

[williamstein]

Attachment: report.txt

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

[williamstein]

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.

[adeines]

Attachment: Trac10973.4.patch.gz

Replaces previous patch.

[adeines]

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

[adeines]

Attachment: Trac10973.5.patch.gz

Replaces previous patch, corrects Authors.

[williamstein]

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.

[JohnCremona]

comment:73

I have a current branch called intptsQ which I made good progress on in December and will get back to.

[embray]

comment:74

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

[embray]

comment:75

Tickets still needing working or clarification should be moved to the next release milestone at the soonest (please feel free to revert if you think the ticket is close to being resolved).

[embray]

comment:76

Ticket retargeted after milestone closed

[mkoeppe]

comment:77

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[mkoeppe]

comment:79

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

comment:80

Setting a new milestone for this ticket based on a cursory review.