Opened 12 years ago

Last modified 3 months ago

#10973 needs_work enhancement

Integral points on elliptic curves over number fields

Reported by: Justin Walker Owned by: John Cremona
Priority: major Milestone: sage-9.8
Component: elliptic curves Keywords: sd32
Cc: John Cremona, Gagan Sekhon, Jennifer Balakrishnan Merged in:
Authors: Justin Walker, Aly Deines, Jennifer Balakrishnan Reviewers:
Report Upstream: N/A Work issues:
Branch: public/10973 (Commits, GitHub, GitLab) Commit: 0774d5990a14f8b923ec6f876891f5f8ee871487
Dependencies: Stopgaps:

Status badges

Description (last modified by John 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 Walker 12 years ago.
ell_int_points.py (19.3 KB) - added by Justin Walker 12 years ago.
This code goes into "sage/schemes/elliptiic_curves". It works, but needs work.
trac_10973 (20.5 KB) - added by Gagan Sekhon 12 years ago.
trac_10973.2 (20.9 KB) - added by Justin Walker 12 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 Gagan Sekhon 12 years ago.
trac_10973.2.patch (62.8 KB) - added by Alyson Deines 11 years ago.
This replaces the previous patch
trac_10973.3.patch (62.9 KB) - added by Alyson Deines 11 years ago.
replaces previous patch
report.txt (8.5 KB) - added by William Stein 11 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 Alyson Deines 11 years ago.
Replaces previous patch.
Trac10973.5.patch (41.8 KB) - added by Alyson Deines 11 years ago.
Replaces previous patch, corrects Authors.
report2.txt (1.4 KB) - added by William Stein 11 years ago.
second short report -- looking good!
Trac10973.6.patch (50.8 KB) - added by Alyson Deines 11 years ago.
replaces previous patch
Trac10973.7.patch (50.7 KB) - added by John Cremona 11 years ago.
Replaces all previous: reviewer's patch
trac_10973_v8.patch (51.5 KB) - added by Frédéric Chapoton 9 years ago.
replaces all previous patches ; rebased on 5.11

Download all attachments as: .zip

Change History (97)

Changed 12 years ago by Justin Walker

Attachment: intpts.sage added

comment:1 Changed 12 years ago by Justin Walker

Type: PLEASE CHANGEenhancement

Changed 12 years ago by Justin Walker

Attachment: ell_int_points.py added

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

comment:2 Changed 12 years ago by Justin Walker

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

Changed 12 years ago by Gagan Sekhon

Attachment: trac_10973 added

comment:3 Changed 12 years ago by Justin Walker

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 12 years ago by Justin Walker

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

Changed 12 years ago by Justin Walker

Attachment: trac_10973.2 added

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

comment:5 Changed 12 years ago by Gagan Sekhon

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 12 years ago by Gagan Sekhon

Attachment: trac_10973.patch added

comment:6 Changed 12 years ago by Gagan Sekhon

Cc: Gagan Sekhon added

Changed 11 years ago by Alyson Deines

Attachment: trac_10973.2.patch added

This replaces the previous patch

comment:7 Changed 11 years ago by Alyson 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 Alyson Deines

Attachment: trac_10973.3.patch added

replaces previous patch

comment:8 Changed 11 years ago by Alyson Deines

Status: newneeds_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 Alyson Deines

Authors: Justin WalkerJustin Walker, Aly Deines

comment:10 Changed 11 years ago by Alyson Deines

Authors: Justin Walker, Aly DeinesJustin Walker, Aly Deines, Jennifer Balakrishnan

Changed 11 years ago by William Stein

Attachment: report.txt added

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

comment:11 Changed 11 years ago by William Stein

Status: needs_reviewneeds_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 Alyson Deines

Attachment: Trac10973.4.patch added

Replaces previous patch.

comment:12 Changed 11 years ago by Alyson Deines

Status: needs_workneeds_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 Alyson Deines

Attachment: Trac10973.5.patch added

Replaces previous patch, corrects Authors.

comment:13 in reply to:  12 Changed 11 years ago by William Stein

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 William Stein

Attachment: report2.txt added

second short report -- looking good!

comment:14 Changed 11 years ago by William Stein

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 Jennifer Balakrishnan

Cc: Jennifer Balakrishnan added

comment:16 Changed 11 years ago by William Stein

Keywords: sd32 added

Changed 11 years ago by Alyson Deines

Attachment: Trac10973.6.patch added

replaces previous patch

comment:17 in reply to:  14 Changed 11 years ago by John 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 John 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 John Cremona

Description: modified (diff)
Status: needs_reviewpositive_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 John Cremona

Attachment: Trac10973.7.patch added

Replaces all previous: reviewer's patch

comment:20 in reply to:  18 ; Changed 11 years ago by John 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 11 years ago by John 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 11 years ago by Jeroen Demeyer

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

comment:23 Changed 11 years ago by Jeroen Demeyer

Status: positive_reviewneeds_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 11 years ago by Jeroen Demeyer

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

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

comment:26 Changed 11 years ago by Jeroen Demeyer

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

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

comment:28 Changed 11 years ago by Jeroen Demeyer

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

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

See comments at #12095

comment:31 Changed 11 years ago by Jeroen Demeyer

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

comment:32 Changed 11 years ago by Andrey Novoseltsev

For the patchbot: apply Trac10973.7.patch

comment:33 in reply to:  31 Changed 10 years ago by John 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 John 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 Frédéric Chapoton

Description: modified (diff)

patchbot, apply only trac_10973_v8.patch

comment:36 Changed 9 years ago by Frédéric 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 Frédéric Chapoton

apply only trac_10973_v8.patch

comment:38 Changed 9 years ago by Frédéric Chapoton

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

comment:39 Changed 9 years ago by Frédéric Chapoton

apply only trac_10973_v8.patch

comment:40 Changed 9 years ago by Frédéric 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 Frédéric Chapoton

Milestone: sage-5.13
Status: needs_workneeds_review

I have corrected the last failing doctest

apply only trac_10973_v8.patch

Needs review !

comment:42 Changed 9 years ago by Frédéric Chapoton

Description: modified (diff)

comment:43 Changed 9 years ago by John Cremona

I checked that the new patch applies fine and passes tests (all tests in sage/schemes/elliptic_curves). 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.

Version 0, edited 9 years ago by John Cremona (next)

comment:44 Changed 9 years ago by John 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 9 years ago by John 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 9 years ago by Frédéric Chapoton

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

comment:47 Changed 9 years ago by Frédéric Chapoton

for the patchbots: apply trac_10973_v8.patch

Changed 9 years ago by Frédéric Chapoton

Attachment: trac_10973_v8.patch added

replaces all previous patches ; rebased on 5.11

comment:48 Changed 9 years ago by Frédéric 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 9 years ago by John Cremona

Branch: u/cremona/trac10973intpts
Commit: 7f5036284d4b31fb81bd69a9bf0a1927c70f3206
Description: modified (diff)
Status: needs_reviewneeds_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 Changed 9 years ago by Frédéric Chapoton

Why is this "needs works" ?

comment:51 in reply to:  50 Changed 9 years ago by John 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 9 years ago by For batch modifications

Milestone: sage-6.1sage-6.2

comment:53 Changed 9 years ago by For batch modifications

Milestone: sage-6.2sage-6.3

comment:54 Changed 8 years ago by git

Commit: 7f5036284d4b31fb81bd69a9bf0a1927c70f320610243adf8021440a184eb36695a00af49a41cb27

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 8 years ago by For batch modifications

Milestone: sage-6.3sage-6.4

comment:56 Changed 7 years ago by Frédéric Chapoton

Branch: u/cremona/trac10973intptspublic/ticket/10973
Commit: 10243adf8021440a184eb36695a00af49a41cb270c14fa06b0f0b15922f2bb2cab4761e85e962536
Milestone: sage-6.4sage-6.9

rebased


New commits:

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

comment:57 Changed 7 years ago by git

Commit: 0c14fa06b0f0b15922f2bb2cab4761e85e9625363985a09232406547e38a02607a80b217a559c215

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 7 years ago by Frédéric Chapoton

Milestone: sage-6.9sage-6.10

comment:59 Changed 7 years ago by John Cremona

Branch: public/ticket/10973u/cremona/10973
Commit: 3985a09232406547e38a02607a80b217a559c215f9208472a60f135532d19deff365f8a45dc8572c

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 6 years ago by Frédéric Chapoton

Branch: u/cremona/10973public/10973
Commit: f9208472a60f135532d19deff365f8a45dc8572c196ddc194ab3ce9dc19f53dccc4676b2d6fd5753
Milestone: sage-6.10sage-7.4

rebased again


New commits:

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

comment:61 Changed 6 years ago by git

Commit: 196ddc194ab3ce9dc19f53dccc4676b2d6fd57536a1a0b8ec8710a79281e1506fbed7988ef393fc0

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 6 years ago by git

Commit: 6a1a0b8ec8710a79281e1506fbed7988ef393fc00715968866c6db7f68cb274a6f4bfe4a3f80599e

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 6 years ago by git

Commit: 0715968866c6db7f68cb274a6f4bfe4a3f80599e871adda033a43b5bbd34ce1111de6fcdb379b34c

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

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

comment:64 Changed 6 years ago by John 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 4 years ago by git

Commit: 871adda033a43b5bbd34ce1111de6fcdb379b34c748216dac716b87b62627ac4b6a229e4f36e8e2c

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

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

comment:66 Changed 4 years ago by git

Commit: 748216dac716b87b62627ac4b6a229e4f36e8e2c9cb7356fc96b55c377a3a4a60d72846f91bd266a

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

9cb7356Merge branch 'develop' into 10973

comment:67 Changed 4 years ago by John 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 4 years ago by John Cremona (previous) (diff)

comment:68 Changed 4 years ago by John 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 4 years ago by John Cremona (previous) (diff)

comment:69 Changed 4 years ago by git

Commit: 9cb7356fc96b55c377a3a4a60d72846f91bd266a9fe35b9a59cfac0d639be8fb981040231f3494c8

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 years ago by Frédéric Chapoton

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

comment:71 Changed 4 years ago by Frédéric Chapoton

Milestone: sage-7.4sage-8.7

comment:72 Changed 4 years ago by git

Commit: 9fe35b9a59cfac0d639be8fb981040231f3494c80774d5990a14f8b923ec6f876891f5f8ee871487

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

0774d59fixing blocks

comment:73 Changed 4 years ago by John Cremona

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

comment:74 Changed 4 years ago by Erik Bray

Milestone: sage-8.7sage-8.8

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

comment:75 Changed 3 years ago by Erik Bray

Milestone: sage-8.8sage-8.9

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

comment:76 Changed 3 years ago by Erik Bray

Milestone: sage-8.9sage-9.1

Ticket retargeted after milestone closed

comment:77 Changed 3 years ago by Matthias Köppe

Milestone: sage-9.1sage-9.2

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.

comment:78 Changed 2 years ago by Matthias Köppe

Milestone: sage-9.2sage-9.3

comment:79 Changed 22 months ago by Matthias Köppe

Milestone: sage-9.3sage-9.4

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

comment:80 Changed 17 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

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

comment:81 Changed 12 months ago by Matthias Köppe

Milestone: sage-9.5sage-9.6

comment:82 Changed 8 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:83 Changed 3 months ago by Matthias Köppe

Milestone: sage-9.7sage-9.8
Note: See TracTickets for help on using tickets.