Opened 11 years ago

Last modified 7 weeks ago

#10973 needs_work enhancement

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

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

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

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 10 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 follow-up: Changed 10 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 10 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 10 years ago by cremona

Replaces all previous: reviewer's patch

comment:20 in reply to: ↑ 18 ; follow-up: Changed 10 years ago by 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).

comment:21 in reply to: ↑ 20 Changed 10 years ago by cremona

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 jdemeyer

  • Description modified (diff)
  • Milestone set to sage-4.8
  • Reviewers set to John Cremona

comment:23 Changed 10 years ago by jdemeyer

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

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 jdemeyer

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

comment:26 Changed 10 years ago by jdemeyer

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 jdemeyer

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

comment:28 Changed 10 years ago by jdemeyer

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 cremona

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 cremona

  • Description modified (diff)
  • Milestone sage-4.8 deleted
  • Reviewers John Cremona deleted

See comments at #12095

comment:31 follow-up: Changed 10 years ago by jdemeyer

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

comment:32 Changed 10 years ago by novoselt

For the patchbot: apply Trac10973.7.patch

comment:33 in reply to: ↑ 31 Changed 10 years ago by cremona

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 cremona

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 chapoton

  • Description modified (diff)

patchbot, apply only trac_10973_v8.patch

comment:36 Changed 9 years ago by chapoton

9 doctests are failing in sage/schemes/elliptic_curves/ell_int_points.py

the failing test in _c3 seems to be a matter of precision only

The other tests must be checked mathematically.

comment:37 Changed 9 years ago by chapoton

apply only trac_10973_v8.patch

comment:38 Changed 9 years ago by chapoton

This ticket needs care from someone who can check the failing doctests.

comment:39 Changed 9 years ago by chapoton

apply only trac_10973_v8.patch

comment:40 Changed 9 years ago by chapoton

I have corrected the (short) failing doctests, and inserted the file in the doc.

There may remain one (very) long doctest failing.

comment:41 Changed 9 years ago by chapoton

  • Milestone set to sage-5.13
  • Status changed from needs_work to needs_review

I have corrected the last failing doctest

apply only trac_10973_v8.patch

Needs review !

comment:42 Changed 9 years ago by chapoton

  • Description modified (diff)
Note: See TracTickets for help on using tickets.