bug in elliptic curve saturation: update to eclib bugfix release 20220621 required.

[JohnCremona]

In eclib version v20210310 the code for saturating points on elliptic curves over QQ was greatly improved, but a small logic error was introduced leading to the following:

sage: E = EllipticCurve([0, 0, 0, -17607, -889490])
sage: Q = E([-82,54])
sage: E.saturation([2*Q])
([(-82 : 54 : 1)], 2, 2.36570863272098)
sage: E.saturation([2*Q], max_prime=10)
([(11649/16 : -1234751/64 : 1)], 1, 9.46283453088392)

The point list [2*Q] is certainly not saturated at 2, and when no saturation bound is given this is detected automaically OK, but when any bound is given it is not. (The reason, for those interested, is that the code in eclib treats primes dividing Tamagawa numbers separately, and here 2 is such a prime.)

I don't see a way to fix this in Sage, but I have fixed the relevant bugs in eclib and made a new release which is https://github.com/JohnCremona/eclib/releases/download/20220621/eclib-20220621.tar.bz2

Upstream: Fixed upstream, in a later stable release.

CC: @dimpase @mkoeppe

Component: elliptic curves

Keywords: eclib

Author: John Cremona

Branch/Commit: 9b65d73

Reviewer: Dima Pasechnik

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

[JohnCremona]

Description changed:

--- 
+++ 
@@ -10,4 +10,4 @@

The point list [2*Q] is certainly not saturated at 2, and when no saturation bound is given this is detected automaically OK, but when any bound is given it is not. (The reason, for those interested, is that the code in eclib treats primes dividing Tamagawa numbers separately, and here 2 is such a prime.)

-I don't see a way to fix this in Sage other than fixing the bug in eclib (which I will now do) and update eclib. +I don't see a way to fix this in Sage, but I have fixed the relevant bugs in eclib and made a new release which is https://github.com/JohnCremona/eclib/releases/download/20220621/eclib-20220621.tar.bz2

[JohnCremona]

comment:2

I hope I can get the new eclib version working more easily than last time (the last version was 20210625, so almost exactly a year ago).

In my new branch (based on current develop branch) I updated the package-version.txt and fixed the checksum.ini, after putting the new tar.bz2 file into upstream/. I deleted the patch in the patches directory since those changes are in the upstream source now. Then "sage -i -c eclib" worked fine, all checks passed. But when I run anything relevant I get errors:

sage: E = EllipticCurve([0,0,0,-17607,-889490])
sage: E.rank()

gives a segfault.

The new version should be completely compatible, i.e. no changes are needed to the interface.

./sage -t src/sage/libs/eclib/constructor.py

is fine, but

./sage -t src/sage/libs/eclib/interface.py

causes a lot of segfaults, e.g.

sage -t --warn-long 94.9 --random-seed=269743671597642066957592066085711042976 src/sage/libs/eclib/interface.py
**********************************************************************
File "src/sage/libs/eclib/interface.py", line 155, in sage.libs.eclib.interface.mwrank_EllipticCurve.set_verbose
Failed example:
    E.saturate() # no output
Exception raised:
    Traceback (most recent call last):
      File "/home/john/sage/local/lib/python3.10/site-packages/sage/doctest/forker.py", line 695, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/john/sage/local/lib/python3.10/site-packages/sage/doctest/forker.py", line 1093, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.libs.eclib.interface.mwrank_EllipticCurve.set_verbose[1]>", line 1, in <module>
        E.saturate() # no output
      File "/home/john/sage/local/lib/python3.10/site-packages/sage/libs/eclib/interface.py", line 570, in saturate
        self.__two_descent_data().saturate(bound, lower)
      File "/home/john/sage/local/lib/python3.10/site-packages/sage/libs/eclib/interface.py", line 370, in __two_descent_data
        self.two_descent(self.__verbose)
      File "/home/john/sage/local/lib/python3.10/site-packages/sage/libs/eclib/interface.py", line 348, in two_descent
        self.__descent.do_descent(self.__curve,
      File "sage/libs/eclib/mwrank.pyx", line 1061, in sage.libs.eclib.mwrank._two_descent.do_descent (build/cythonized/sage/libs/eclib/mwrank.cpp:5622)
        sig_on()
    cysignals.signals.SignalError: Segmentation fault

I'll post the branch here and hope someone can help. Dima usually can!

[JohnCremona]

comment:3

I will go and read the latest edition of the developers' guide to see why this does not work:

$ git push trac eclib-20220621:trac/u/cremona/34029
X11 forwarding request failed on channel 0
Enumerating objects: 13, done.
Counting objects: 100% (13/13), done.
Delta compression using up to 8 threads
Compressing objects: 100% (6/6), done.
Writing objects: 100% (7/7), 686 bytes | 686.00 KiB/s, done.
Total 7 (delta 4), reused 0 (delta 0)
remote: FATAL: W refs/heads/trac/u/cremona/34029 sage cremona DENIED by fallthru
remote: error: hook declined to update refs/heads/trac/u/cremona/34029
To trac.sagemath.org:sage.git
 ! [remote rejected]       eclib-20220621 -> trac/u/cremona/34029 (hook declined)
error: failed to push some refs to 'git@trac.sagemath.org:sage.git'

[JohnCremona]

comment:4

Well, in fact I found the problem in an email from Volker to me from 2013.... (delete "trac/" from the remote branch name).

---

New commits:

2818d1c

#34029: eclib update to 20220621

[JohnCremona]

Commit: 2818d1c

[JohnCremona]

Branch: u/cremona/34029

[dimpase]

comment:5

seems that output changed, thus doctests fail, e.g.

File "src/sage/libs/eclib/mwrank.pyx", line 589, in sage.libs.eclib.mwrank._mw.__init__
Failed example:
    EQ.search(1)
Expected:
    P1 = [0:1:0]         is torsion point, order 1
    P1 = [-3:0:1]         is generator number 1
    saturating up to 20...Saturation index bound (for points of good reduction)  = 3
    Reducing saturation bound from given value 20 to computed index bound 3
    Checking saturation at [ 2 3 ]
...

Got:
    P1 = [0:1:0]         is torsion point, order 1
    P1 = [-3:0:1]         is generator number 1
    saturating up to 20...Saturation index bound (for points of good reduction)  = 3
    Reducing saturation bound from given value 20 to computed index bound 3
    Tamagawa index primes are [ 2 ]
    Checking saturation at [ 2 3 ]
...

so the new output has the line Tamagawa index primes are [ 2 ], and the old does not.

[dimpase]

comment:6

or here:

File "src/sage/libs/eclib/interface.py", line 1213, in sage.libs.eclib.interface.mwrank_MordellWeil.sat
urate
Failed example:
    EQ.saturate()
Expected:
    saturating basis...Saturation index bound (for points of good reduction) = 3
    Tamagawa index primes are [ ]
    Checking saturation at [ 2 3 ]
    Checking 2-saturation
    Points were proved 2-saturated (max q used = 11)
    Checking 3-saturation
    Points were proved 3-saturated (max q used = 13)
    done
    (True, 1, '[ ]')
Got:
    saturating basis...Saturation index bound (for points of good reduction)  = 3
    Tamagawa index primes are [ 2 ]
    Checking saturation at [ 2 3 ]
    Checking 2-saturation 
    Points were proved 2-saturated (max q used = 11)
    Checking 3-saturation 
    Points were proved 3-saturated (max q used = 13)
    done
    (True, 1, '[ ]')

again, Tamagawa index primes are [ 2 ] vs Tamagawa index primes are [ ]

[JohnCremona]

comment:8

Yes of course, I did not mark the ticket as ready for review yet. But yesterday I could not even test it for the reasons I mentioned. I'll reinstall today and try again.

But thanks for testing. The explanation for the difference in "Tamagawa index primes" is that these should include primes dividing the number of real components (which is 2 here) as well as the p-adic components (which are all 1 here).

I'll fix the doctests once I can get the new code to work. I don't know why it is giving me segfaults. "sage -mwrank" works OK.

[JohnCremona]

comment:9

The good news is that I rebuilt sage from scratch and now it works. I'll fix the doctests and update the branch.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 2818d1c to 7293ebf

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

7293ebf

fixed some doctests for eclib-20220621

[JohnCremona]

comment:11

Commit 7293ebf fixes the doctests, I will add a new doctest to show that the problem posted here has been solved before setting to "needs review".

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7293ebf to 604ca73

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

604ca73

#34029: add doctest

[JohnCremona]

Changed keywords from none to eclib

[JohnCremona]

comment:14

The two failing doctests in the logs have nothing to do with the changes on this ticket.

[dimpase]

comment:15

One also needs to deal with potentially outdated eclibs provided by the system. Meaning that you have to decide whether to allow the older versions at all

currently 20210625 is allowed from the system, and no other versions (cf. #31443)

Anyway, build/pkgs/eclib/spkg-configure.m4 has to be updated. E.g. if you only want to allow 20220621, you simply need to replace the corresponding value in this file.

If you want to allow more, it'd be more work. One can also do testing for eclib bugs there, and rejecting buggy system eclib (that's what we do with Pari).

Indeed, testing this on Fedora 34 (which has 20210625) and getting

File "src/sage/schemes/elliptic_curves/ell_rational_field.py", line 2615, in sage.schemes.elliptic_curves.ell_rational_field.EllipticCurve_rational_field.saturation
Failed example:
    E.saturation([2*Q], max_prime=10)
Expected:
    ([(-82 : 54 : 1)], 2, 2.36570863272098)
Got:
    ([(11649/16 : -1234751/64 : 1)], 1, 9.46283453088392)
...
File "src/sage/libs/eclib/interface.py", line 727, in sage.libs.eclib.interface.mwrank_MordellWeil
Failed example:
    EQ.search(1)
Expected:
    P1 = [0:1:0]     is torsion point, order 1
    P1 = [-3:0:1]     is generator number 1
    saturating up to 20...Saturation index bound (for points of good reduction)  = 3
    Reducing saturation bound from given value 20 to computed index bound 3
    Tamagawa index primes are [ 2 ]
    Checking saturation at [ 2 3 ]
    Checking 2-saturation 
...
Got:
    P1 = [0:1:0]         is torsion point, order 1
    P1 = [-3:0:1]         is generator number 1
    saturating up to 20...Saturation index bound (for points of good reduction)  = 3
    Reducing saturation bound from given value 20 to computed index bound 3
    Checking saturation at [ 2 3 ]
    Checking 2-saturation 
...

(no wonder, it's the old eclib tested against updated doctests)

[JohnCremona]

comment:16

Thanks Dima, I wanted to ask you about that m4 file. I think we should just allow only eclib 20220621. And I expect to make a similar restriction for future releases. The only downside for (most of) those building Sage is that Sage will build eclib, as it always has done.

I'll update that m4 file.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 604ca73 to 9b65d73

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

9b65d73

#34029: update spkg-configure.m4

[dimpase]

comment:18

lgtm

[dimpase]

Reviewer: Dima Pasechnik

[dimpase]

comment:19

We can actually hardcode this design, so that spkg-configure.m4 gets the version from package-version. But that's a minor issue.

[JohnCremona]

comment:20

Replying to @dimpase:

We can actually hardcode this design, so that spkg-configure.m4 gets the version from package-version. But that's a minor issue.

Thanks. If the hard-coding is easy we could do that now?

[dimpase]

comment:21

I tried

--- a/build/pkgs/eclib/spkg-configure.m4
+++ b/build/pkgs/eclib/spkg-configure.m4
@@ -1,7 +1,7 @@
 SAGE_SPKG_CONFIGURE([eclib], [
   SAGE_SPKG_DEPCHECK([ntl pari flint], [
     dnl Trac #31443, #34029: use existing eclib only if the version reported by pkg-config is correct
-    m4_pushdef([SAGE_ECLIB_VER],["20220621"])
+    m4_pushdef([SAGE_ECLIB_VER],["m4_include([build/pkgs/eclib/package-version.txt])"])
     PKG_CHECK_MODULES([ECLIB], [eclib = SAGE_ECLIB_VER], [
       AC_CACHE_CHECK([for mwrank version == SAGE_ECLIB_VER], [ac_cv_path_MWRANK], [
         AC_PATH_PROGS_FEATURE_CHECK([MWRANK], [mwrank], [

but my m4 foo is not strong enough to make it work without warnings (something about multiple inclusion of this file pops up). Maybe Matthias knows a fix.

[dimpase]

comment:22

I've also started a round of tests on https://github.com/sagemath/sagetrac-mirror/actions/runs/2554535605 - just in case.

[mkoeppe]

comment:23

We do use m4_include for a similar purpose in build/pkgs/perl_mongodb/spkg-configure.m4. I think you are overquoting

[dimpase]

Changed upstream from Reported upstream. Developers acknowledge bug. to Fixed upstream, in a later stable release.

[vbraun]

Changed branch from u/cremona/34029 to 9b65d73