Opened 8 years ago

Last modified 4 weeks ago

#10973 needs_work enhancement

Integral points on elliptic curves over number fields

Reported by: justin Owned by: cremona
Priority: major Milestone: sage-8.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: public/10973 (Commits) Commit: 0774d5990a14f8b923ec6f876891f5f8ee871487
Dependencies: Stopgaps:

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.

See also #12095 (now tagged as duplicate).

Converted to git by John Cremona, 2013-12-18

Attachments (14)

intpts.sage (18.0 KB) - added by justin 8 years ago.
ell_int_points.py (19.3 KB) - added by justin 8 years ago.
This code goes into "sage/schemes/elliptiic_curves". It works, but needs work.
trac_10973 (20.5 KB) - added by gagansekhon 8 years ago.
trac_10973.2 (20.9 KB) - added by justin 8 years ago.
Updated patch with code to reject requests w/o generators; replaces previous patch of same name.
trac_10973.patch (20.9 KB) - added by gagansekhon 8 years ago.
trac_10973.2.patch (62.8 KB) - added by aly.deines 8 years ago.
This replaces the previous patch
trac_10973.3.patch (62.9 KB) - added by aly.deines 8 years ago.
replaces previous patch
report.txt (8.5 KB) - added by was 8 years ago.
This is a list of 14 issues I had reading through trac_10973.3.patch.
Trac10973.4.patch (42.0 KB) - added by aly.deines 8 years ago.
Replaces previous patch.
Trac10973.5.patch (41.8 KB) - added by aly.deines 8 years ago.
Replaces previous patch, corrects Authors.
report2.txt (1.4 KB) - added by was 8 years ago.
second short report -- looking good!
Trac10973.6.patch (50.8 KB) - added by aly.deines 8 years ago.
replaces previous patch
Trac10973.7.patch (50.7 KB) - added by cremona 7 years ago.
Replaces all previous: reviewer's patch
trac_10973_v8.patch (51.5 KB) - added by chapoton 5 years ago.
replaces all previous patches ; rebased on 5.11

Download all attachments as: .zip

Change History (87)

Changed 8 years ago by justin

comment:1 Changed 8 years ago by justin

  • Type changed from PLEASE CHANGE to enhancement

Changed 8 years ago by justin

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

comment:2 Changed 8 years ago by justin

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

Changed 8 years ago by gagansekhon

comment:3 Changed 8 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 8 years ago by justin

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

Changed 8 years ago by justin

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

comment:5 Changed 8 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 8 years ago by gagansekhon

comment:6 Changed 8 years ago by gagansekhon

  • Cc gagansekhon added

Changed 8 years ago by aly.deines

This replaces the previous patch

comment:7 Changed 8 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 8 years ago by aly.deines

replaces previous patch

comment:8 Changed 8 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 8 years ago by aly.deines

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

comment:10 Changed 8 years ago by aly.deines

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

Changed 8 years ago by was

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

comment:11 Changed 8 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 8 years ago by aly.deines

Replaces previous patch.

comment:12 follow-up: Changed 8 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 8 years ago by aly.deines

Replaces previous patch, corrects Authors.

comment:13 in reply to: ↑ 12 Changed 8 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 8 years ago by was

second short report -- looking good!

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

  • Cc jen added

comment:16 Changed 8 years ago by was

  • Keywords sd32 added

Changed 8 years ago by aly.deines

replaces previous patch

comment:17 in reply to: ↑ 14 Changed 7 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 7 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 7 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 7 years ago by cremona

Replaces all previous: reviewer's patch

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

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

comment:23 Changed 7 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 7 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 7 years ago by jdemeyer

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

comment:26 Changed 7 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 7 years ago by jdemeyer

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

comment:28 Changed 7 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 7 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 7 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 7 years ago by jdemeyer

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

comment:32 Changed 7 years ago by novoselt

For the patchbot: apply Trac10973.7.patch

comment:33 in reply to: ↑ 31 Changed 7 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 7 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 6 years ago by chapoton

  • Description modified (diff)

patchbot, apply only trac_10973_v8.patch

comment:36 Changed 6 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 6 years ago by chapoton

apply only trac_10973_v8.patch

comment:38 Changed 6 years ago by chapoton

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

comment:39 Changed 6 years ago by chapoton

apply only trac_10973_v8.patch

comment:40 Changed 6 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 6 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 6 years ago by chapoton

  • Description modified (diff)

comment:43 Changed 6 years ago by cremona

I checked that the new patch applies fine and passes most tests (all tests in sage/schemes/elliptic_curves except one, see below). I want to do more testing now, to test on a large range of conductors that (over QQ) we find the same integral points as Magma. In any case, I intend to run the new function on all curve of conductor <300000 in order to correct the files at http://homepages.warwick.ac.uk/staff/J.E.Cremona/ftp/data/, so I may as well do all that as part of this review.

This seems to be simply a formatting difference:

Failed example:
    E.integral_points(L = [E((4,-4)),E((0,-20)),E((-4,-28)),E((-89/5,-637*a/25))])  # long time
Expected:
    [(-12 , 4 , 1), (-8 , 28 , 1), (-7 , -29 , 1), (-4 , -28 , 1),
    (0 , -20 , 1), (1 , 17 , 1), (4 , -4 , 1), (8 , 4 , 1), (9 , -11 , 1),
    (12 , -28 , 1), (16 , 52 , 1), (25 , -115 , 1), (32 , 172 , 1),
    (44 , 284 , 1), (56 , -412 , 1), (84 , -764 , 1), (148 , 1796 , 1),
    (208 , 2996 , 1), (372 , -7172 , 1), (1368 , -50596 , 1),
    (1624 , -65444 , 1), (3264 , 186476 , 1)]
Got:
    [(-12 : 4 : 1), (-8 : 28 : 1), (-7 : -29 : 1), (-4 : -28 : 1), (0 : -20 : 1), (1 : 17 : 1), (4 : -4 : 1), (8 : 4 : 1), (9 : -11 : 1), (12 : -28 : 1), (16 : 52 : 1), (25 : -115 : 1), (32 : 172 : 1), (44 : 284 : 1), (56 : -412 : 1), (84 : -764 : 1), (148 : 1796 : 1), (208 : 2996 : 1), (372 : -7172 : 1), (1368 : -50596 : 1), (1624 : -65444 : 1), (3264 : 186476 : 1)]
**********************************************************************
1 item had failures:
   1 of  14 in sage.schemes.elliptic_curves.ell_int_points.integral_points
    [150 tests, 1 failure, 325.30 s]
Last edited 6 years ago by cremona (previous) (diff)

comment:44 Changed 6 years ago by cremona

More seriously,

sage: E = EllipticCurve('9615d1)
sage: E.integral_points()

seems to hang, thought I don't know why, while

sage: E = EllipticCurve('9615d1)
sage: E.integral_points(algorithm="old")

is fine. I think that this will need investigating before this can be merged. Hence "needs work".

I systematically checked all curves with conductor < 10000 with Magma V2.19-8. Note that thaere have been a lot of improvements in Magma's algorithm, due to Steve DOnelly but not published, since this ticket was opened. Not just bugfixes; but only over Q.

With the old algorithm in Sage for N<10000 there are only 3 cases where Sage missed integral points. Of these, 3 (6104b1, 8470g1 and 8470g2), are very easily fixed, simply by increasing the precision of the function integral_points_with_bounded_mw_coeffs from 100 to 200, thogh I have not done the necessary analysis to compute the actual precision required. The other one is 2082a1, where the MW group is cyclic of rank 1 and the integral multiples of the generator P are n*P for n=1,2,3,4,13, but the bound computed by the algorithm is 12. It should be possible to find that bug using a detailed analysis of the implementation, but I have not done that yet (though I did find one small bug, in the formula for mu there should be b2/12 and not b2).

comment:45 Changed 6 years ago by cremona

I have done some debugging, not yet complete but I'll be away for a while and wanted to record what I found so far.

2082a1: the old code is not nearly careful enough about computing elliptic logs and periods to high enough precision, and I have worked a bit on improving that, but in this example it reduces the coefficient bound first from 10^44 to 34 (that looks OK to me) and then to 12, which is not OK since the actual bound is 13. And I can see what is done wrong: in Cohen's notation you need a lower bound on d(L,0)^2 which is greater than T^2+Q, and in this second step it is not; the code makes an adjustment, which is not (as far as I can see) justified. Instead one should increase the scaling parameter C. I found that multiplying C by 100 is OK, but yields a worse bound on the coefficients, namely 56. If one did check all 34 multiples of the generator (the rank is 1) then that would be OK. But the new code here manages to get successive bounds 10^40, 53, 18 and uses 18 which works better than 34 would have done! The two implementations need further careful comparison.

9615d1, which has rank 2. The new code finds a bound of 162, and the apparent hanging happens when testing all multiples with coefficients up to that bound. This is what is taking a very long time: there are 52812 points to check, and many will have huge height. This is a good illustration of the benefit of using floating point at this stage, since on the same curve if you run integral_points_with_bounded_mw_coeffs(E,E.gens(),162) it finishes quickly (and finds all the points, namely the 15 which Magma also finds). On the other hand the old code obtains a coefficient bound of only 18, which is good enough, so it is necessary to find out why the new code does so much worse (bound 162).

I don't feel prepared to remove the "needs work" tag just yet.

comment:46 Changed 5 years ago by chapoton

I have made a new patch, correcting the one failing doctest

comment:47 Changed 5 years ago by chapoton

for the patchbots: apply trac_10973_v8.patch

Changed 5 years ago by chapoton

replaces all previous patches ; rebased on 5.11

comment:48 Changed 5 years ago by chapoton

I have made a new patch, that should work with 5.13.beta1

for the patchbots: apply trac_10973_v8.patch

comment:49 Changed 5 years ago by cremona

  • Branch set to u/cremona/trac10973intpts
  • Commit set to 7f5036284d4b31fb81bd69a9bf0a1927c70f3206
  • Description modified (diff)
  • Status changed from needs_review to needs_work

Last 10 new commits:

7f50362Trac #10973: integer points on elliptic curves over number fields
057b3cdMerge branch 'master' of git://github.com/sagemath/sage
68d0a5dMerge branch 'master' of git://github.com/sagemath/sage
88ffd55Merge branch 'master' of git://github.com/sagemath/sage
0523e0dMerge branch 'master' of git://github.com/sagemath/sage
858bb95Merge branch 'master' of git://github.com/sagemath/sage
b06bd7cMerge branch 'master' of git://github.com/sagemath/sage
17e17ddMerge branch 'master' of ssh://trac.sagemath.org:2222/sage into build_system
139dcf5Merge branch 'build_system' of git://github.com/sagemath/sage into build_system
38d22b7Merge branch 'master' of ssh://trac.sagemath.org:2222/sage into build_system

comment:50 follow-up: Changed 5 years ago by chapoton

Why is this "needs works" ?

comment:51 in reply to: ↑ 50 Changed 5 years ago by cremona

Replying to chapoton:

Why is this "needs works" ?

Because I am actively working on it! Seriously, comparing in detail Smart's paper and book and Nook's account in his thesis, I have found two things: (1) Smart does not deal properly with torsion generators, Nook does and that is in this code but I think I might be able to do better; (2) more seriously, Smart derived an upper bound for |x(P)^2\psi(P)| (relative to each embedding) which only valid for points with |x(P)| bounded below by some quantity (in the appropriate embedding), and this means that there are points, possible integral, which fail this condition and need to be considered separately. Over Q that is easily done by searching on a finite x-interval, but over a general number field it is not clear to me that the "missing" points are in a finite region. However, I am working on a bound (which certainly exists) for |x(P)^2\psi(P)| valid for all complex points with any embedding, and when that is done I will be changing some of the constants in the code.

I am not expecting the output to be different in any of the examples (but who knows), but I cannot let this in when I have identified but not yet fixed this mathematical bug!

comment:52 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:53 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:54 Changed 5 years ago by git

  • Commit changed from 7f5036284d4b31fb81bd69a9bf0a1927c70f3206 to 10243adf8021440a184eb36695a00af49a41cb27

Branch pushed to git repo; I updated commit sha1. New commits:

37d85c3Merge branch 'develop' into intpoints
7ef9e45minor fix to previous merge (conflict resolution mistake)
10243adMerge branch 'develop' into intpoints

comment:55 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:56 Changed 4 years ago by chapoton

  • Branch changed from u/cremona/trac10973intpts to public/ticket/10973
  • Commit changed from 10243adf8021440a184eb36695a00af49a41cb27 to 0c14fa06b0f0b15922f2bb2cab4761e85e962536
  • Milestone changed from sage-6.4 to sage-6.9

rebased


New commits:

0c14fa0Merge branch 'u/cremona/trac10973intpts' into 6.9.b6

comment:57 Changed 3 years ago by git

  • Commit changed from 0c14fa06b0f0b15922f2bb2cab4761e85e962536 to 3985a09232406547e38a02607a80b217a559c215

Branch pushed to git repo; I updated commit sha1. New commits:

4e98ed9Merge branch 'public/ticket/10973' into 6.10.b0
3985a09trac #10973 fixing a doctest

comment:58 Changed 3 years ago by chapoton

  • Milestone changed from sage-6.9 to sage-6.10

comment:59 Changed 3 years ago by cremona

  • Branch changed from public/ticket/10973 to u/cremona/10973
  • Commit changed from 3985a09232406547e38a02607a80b217a559c215 to f9208472a60f135532d19deff365f8a45dc8572c

New commits:

3fd00eaMerge branch 'develop' into intpoints
e5c7493merged with 6.10
f920847Merge branch 'develop' (7.1.beta3) into intpoints and fix resulting issues

comment:60 Changed 3 years ago by chapoton

  • Branch changed from u/cremona/10973 to public/10973
  • Commit changed from f9208472a60f135532d19deff365f8a45dc8572c to 196ddc194ab3ce9dc19f53dccc4676b2d6fd5753
  • Milestone changed from sage-6.10 to sage-7.4

rebased again


New commits:

196ddc1Merge branch 'u/cremona/10973' in 7.3.rc0

comment:61 Changed 3 years ago by git

  • Commit changed from 196ddc194ab3ce9dc19f53dccc4676b2d6fd5753 to 6a1a0b8ec8710a79281e1506fbed7988ef393fc0

Branch pushed to git repo; I updated commit sha1. New commits:

7d8266btrac 10973 modern py3 compatible import
6a1a0b8trac 10973 another import to py3

comment:62 Changed 2 years ago by git

  • Commit changed from 6a1a0b8ec8710a79281e1506fbed7988ef393fc0 to 0715968866c6db7f68cb274a6f4bfe4a3f80599e

Branch pushed to git repo; I updated commit sha1. New commits:

ca494b3Merge branch 'public/10973' in 7.5.b6
0715968trac 10973 python3 compatible changes

comment:63 Changed 2 years ago by git

  • Commit changed from 0715968866c6db7f68cb274a6f4bfe4a3f80599e to 871adda033a43b5bbd34ce1111de6fcdb379b34c

Branch pushed to git repo; I updated commit sha1. New commits:

871addaMerge branch 'public/10973' in 7.6.rc0

comment:64 Changed 2 years ago by cremona

Thanks for keeping this updated. I just have not been able to finish work on it (there are some mathematical issues).

comment:65 Changed 7 months ago by git

  • Commit changed from 871adda033a43b5bbd34ce1111de6fcdb379b34c to 748216dac716b87b62627ac4b6a229e4f36e8e2c

Branch pushed to git repo; I updated commit sha1. New commits:

748216dMerge branch 'public/10973' in 8.4.b1

comment:66 Changed 3 months ago by git

  • Commit changed from 748216dac716b87b62627ac4b6a229e4f36e8e2c to 9cb7356fc96b55c377a3a4a60d72846f91bd266a

Branch pushed to git repo; I updated commit sha1. New commits:

9cb7356Merge branch 'develop' into 10973

comment:67 Changed 3 months ago by cremona

I have merged the current working branch in with 8.6.beta1 and resolved the conflicts.

I also made the following test: there are 207 curves in the database (conductors < 400000, curves defined over QQ) where the old E.integral_points() missed integral points, as I found out by running every curve through Magma's IntegralPoints? function. For every one of these the current version finds all the points (the same as Magma does).

However I still think that this code is too slow over QQ and intend to make a new branch (and a new ticket #27015) to fix the problems over QQ. When that is done I will get back to this branch.

Last edited 3 months ago by cremona (previous) (diff)

comment:68 Changed 3 months ago by cremona

Correction to the above: it was true that there were 207 curves whose lists of integral points at http://johncremona.github.io/ecdata/ (since updated) were incomplete, and hence also the integral points stored in the LMFDB (not yet updated). However, in all but 3 of these cases (2082a1, 23808e1, 285928a1) the current Sage (8.5) finds all the points. So previous bug fixes have helped.

In the negative direction there are some more discrepancies, since we now (using vanilla 8.5) miss x=20829482 on 1701d1 and x=176 and 179 on 1848f1. (There will surely be more).

The complete list of missed points with Sage 8.5 is: 12 points on 11 curves:

1701d1, 1848f1, 2082a1, 3510n1, 6514b1, 177211a1, 23808e1, 268740c1, 285928a1, 66432f1, 92554e1,

missing 1 point in each case except 2 points on 1848f1.

#27015 will deal with this.

Last edited 3 months ago by cremona (previous) (diff)

comment:69 Changed 4 weeks ago by git

  • Commit changed from 9cb7356fc96b55c377a3a4a60d72846f91bd266a to 9fe35b9a59cfac0d639be8fb981040231f3494c8

Branch pushed to git repo; I updated commit sha1. New commits:

70d00f9Merge branch 'public/10973' in 8.7.b4
9fe35b9fixing the blocks EXAMPLES::

comment:70 Changed 4 weeks ago by chapoton

So what's the status here ? Should we just fix the few failing doctests ?

comment:71 Changed 4 weeks ago by chapoton

  • Milestone changed from sage-7.4 to sage-8.7

comment:72 Changed 4 weeks ago by git

  • Commit changed from 9fe35b9a59cfac0d639be8fb981040231f3494c8 to 0774d5990a14f8b923ec6f876891f5f8ee871487

Branch pushed to git repo; I updated commit sha1. New commits:

0774d59fixing blocks

comment:73 Changed 4 weeks ago by cremona

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

Note: See TracTickets for help on using tickets.