Saturation of elliptic curve points can cause an infinite loop

[JohnCremona]

Possibly related to #9247.

The method saturation() for sets of points on elliptic curves over Q calls eclib in a loop which is optimistically headed "while True:". Unfortunately this really can cause infinite looping. Here's an example (the curve has conductor 130017):

E = EllipticCurve([1, 0, 1, -977842, -372252745])
P = E([-192128125858676194585718821667542660822323528626273/336995568430319276695106602174283479617040716649, 70208213492933395764907328787228427430477177498927549075405076353624188436/195630373799784831667835900062564586429333568841391304129067339731164107, 1])
P.height()
E.saturation([P]) ## OK, saturated
E.saturation([2*P]) ## loops!

The problem is that there are various different ways in which the saturation inside the loop (line 2097 of ell_rational_field.py) can fail, and one -- probably the one here -- is due to a lack of precision. I will look into how to increase the precision used in eclib from Sage. (In this example, after mwrank_set_precision(200) it works fine, but not with 150.)

CC: @rlmill @williamstein

Component: elliptic curves

Keywords: saturation

Author: John Cremona

Reviewer: Robert Miller

Merged: sage-4.6.2.alpha2

Issue created by migration from https://trac.sagemath.org/ticket/10590

[JohnCremona]

comment:1

Problem fixed.

I added a function mwrank_get_precision() (by wrapping eclib's existing decimal_precision() function). Testing revealed that mwrank_set_precision(mwrank_get_precision()) had the effect of reducing the precision by at least 1 (exactly on for precision<803, the getting worse) on account or rounding errors in the conversion to/from base 2/base 10. That is fixed by adding some code to the wrapper function for set_precision().

This new functionality is used in the saturation() function to catch failures due to lack of precision and gradually increase the precision until success is gained. At the end the precision is put back to what it was.

In all the above, "precision" only refers to the floating point precision used by the NTL library withing eclib, not to anything else in Sage.

Patch has been tested on a 64-bit machine on the whole library (including long tests).

[rlmill]

Author: John Cremona

[rlmill]

comment:2

This looks good to me! Passes tests on sage-4.6.1.rc0.

[rlmill]

Reviewer: Robert Miller

[JohnCremona]

Attachment: trac_10590-precision.patch.gz

Applies to 4.6.2.alpha0

[JohnCremona]

comment:3

The new patch only differs from the first one in (new) lines 2115-2118 of ell_rational_field.py, in the saturation() method: before, if the current precision was > 100 then the initial working precision was actually reduced to 100, which is silly. Now, if the user has "manually" increased precision already, that is used as the starting point.

I discovered this with an example where precision of 300 was needed (250 was too small).

I am switching this to "needs work" and then right away back to "needs review".

[rlmill]

comment:5

Perhaps the two commented lines which print information about precision changes should be put into verbose commentary. This patch passes the usual testing process, and the code all looks good. John, can you suggest a more thorough way of reviewing this patch?

[JohnCremona]

comment:6

It's a very good idea to have verbose=True cause output of precision changes.

Testing hints: it's no good giving input which is already saturated since eclib will prove saturation without using any floating point arithmetic at all. You need to give unsaturated input, and there is no need to have rank>1 to exercise the precision code, so loop through the (extended) database, pick rank one curves E with generator P and run E.saturate([k*P]) for small k>1.

OK, so I should do this.

[rlmill]

comment:7

I ran a loop as you suggested, and it seems that the new code never hangs (at least on the swath I tested). However, when I tried a keyboard interrupt to stop the loop, it just hanged. Maybe there should be a separate ticket to ensure that interrupts are handled properly.

[JohnCremona]

comment:8

Good point about interrupts. I don't have the expertise to know what to do though, sorry.

If it's to be in a separate ticket can you make this one "positive review"? And I hope you will, since the pre-patched code is no better regarding interrupts; if anything it is worse (see ticket title!)

[jdemeyer]

comment:10

Replying to @rlmill:

Maybe there should be a separate ticket to ensure that interrupts are handled properly.

I've been working a lot on interrupts in Sage. If you create that ticket, be sure to cc me.

[jdemeyer]

Merged: sage-4.6.2.alpha2