Opened 2 years ago

Closed 2 years ago

#23962 closed defect (fixed)

rank() of elliptic curves should always consult Cremona database

Reported by: mderickx Owned by:
Priority: blocker Milestone: sage-8.1
Component: elliptic curves Keywords:
Cc: cremona Merged in:
Authors: Jeroen Demeyer Reviewers: Maarten Derickx, John Cremona
Report Upstream: N/A Work issues:
Branch: 3cff14c (Commits) Commit: 3cff14c2ea4863634fac9f9009f65efcecbf6b1a
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

sage: E1 = EllipticCurve([0, -1, 1, -929, -10595])
sage: E2 = EllipticCurve('571a1')
sage: E2.rank()
Unable to compute the rank with certainty (lower bound=0).
This could be because Sha(E/Q)[2] is nontrivial.
Try calling something like two_descent(second_limit=13) on the
curve then trying this command again.  You could also try rank
with only_use_mwrank=False.
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
<ipython-input-3-d3aae2f31e01> in <module>()
----> 1 E2.rank()

/usr/local/src/sage-config/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_rational_field.pyc in rank(self, use_database, verbose, only_use_mwrank, algorithm, proof)
   2119                     print("with only_use_mwrank=False.")
   2120                     del E.__mwrank_curve
-> 2121                     raise RuntimeError('Rank not provably correct.')
   2122                 else:
   2123                     misc.verbose("Warning -- rank not proven correct", level=1)

RuntimeError: Rank not provably correct.

The problem is that E1 and E2 are the same curve, but constructed in a different way. When the first line is removed, the rank computation works. The reason is that EllipticCurve('571a1') looks up the elliptic curve in the Cremona database (which includes the fact that the rank is 0) but only if the curve does not exist already.

The solution seems easy: always look up the rank of elliptic curves in the database.

I am also simplifying and cleaning up the implementation of rank() a bit.


This ticket leads to random doctest failures (which is how this was originally reported):

sage -t --long src/sage/schemes/elliptic_curves/sha_tate.py
**********************************************************************
File "src/sage/schemes/elliptic_curves/sha_tate.py", line 915, in sage.schemes.elliptic_curves.sha_tate.Sha.two_selmer_bound
Failed example:
    sh.two_selmer_bound()
Exception raised:
    Traceback (most recent call last):
      File "/home/patchbot/sage-patchbot/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 515, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/patchbot/sage-patchbot/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 885, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.schemes.elliptic_curves.sha_tate.Sha.two_selmer_bound[1]>", line 1, in <module>
        sh.two_selmer_bound()
      File "/home/patchbot/sage-patchbot/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/sha_tate.py", line 934, in two_selmer_bound
        r = E.rank()
      File "/home/patchbot/sage-patchbot/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_rational_field.py", line 2121, in rank
        raise RuntimeError('Rank not provably correct.')
    RuntimeError: Rank not provably correct.
**********************************************************************
1 item had failures:
   1 of  10 in sage.schemes.elliptic_curves.sha_tate.Sha.two_selmer_bound
    [155 tests, 1 failure, 55.87 s]

Change History (37)

comment:1 follow-up: Changed 2 years ago by tscrim

This might come from #23544.

comment:2 in reply to: ↑ 1 Changed 2 years ago by jdemeyer

  • Description modified (diff)

Replying to tscrim:

This might come from #23544.

I don't think so. I was reported om sage-release to fail on Sage 8.1.beta7.

The code seems to involve the Cremona database and the eclib library, not PARI/GP.

I don't understand the failure though: the curve is contained in the small Cremona database which is installed by default. So the rank should just be read from the database.

comment:3 Changed 2 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Cc cremona added
  • Description modified (diff)
  • Summary changed from Doctest failure in src/sage/schemes/elliptic_curves/sha_tate.py to Uniqueness of elliptic curves causes data not to be read from Cremona database

comment:4 Changed 2 years ago by mderickx

  • Authors Jeroen Demeyer deleted
  • Cc cremona removed
  • Description modified (diff)
  • Summary changed from Uniqueness of elliptic curves causes data not to be read from Cremona database to Doctest failure in src/sage/schemes/elliptic_curves/sha_tate.py

The rank should, but maybe the two_selmer_bound which might be different from the rank is not read from the database.

comment:5 Changed 2 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Cc cremona added
  • Description modified (diff)
  • Summary changed from Doctest failure in src/sage/schemes/elliptic_curves/sha_tate.py to Uniqueness of elliptic curves causes data not to be read from Cremona database

comment:6 Changed 2 years ago by mderickx

  • Authors Jeroen Demeyer deleted
  • Cc cremona removed
  • Description modified (diff)
  • Summary changed from Uniqueness of elliptic curves causes data not to be read from Cremona database to Doctest failure in src/sage/schemes/elliptic_curves/sha_tate.py

Sorry ignore my last comment, I should have read the full traceback

comment:7 Changed 2 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Cc cremona added
  • Description modified (diff)
  • Summary changed from Doctest failure in src/sage/schemes/elliptic_curves/sha_tate.py to rank() of elliptic curves should always consult Cremona database

comment:8 Changed 2 years ago by jdemeyer

  • Description modified (diff)

comment:9 Changed 2 years ago by jdemeyer

  • Description modified (diff)

comment:10 Changed 2 years ago by jdemeyer

  • Branch set to u/jdemeyer/doctest_failure_in_src_sage_schemes_elliptic_curves_sha_tate_py

comment:11 Changed 2 years ago by jdemeyer

  • Commit set to 96765dc2be80e53bee137853ebf85ec9e40681c1
  • Status changed from new to needs_review

New commits:

96765dcrank() of elliptic curves should always consult Cremona database

comment:12 follow-up: Changed 2 years ago by charpent

  • Status changed from needs_review to needs_info

As far as I can tell :

  • EllipticCurve is standard
  • therefore, <some elliptic_curve>.rank() is also standard
  • database_cremona_ellcurve is optional

If you wish to always consult Cremona database in any case, database_cremona_ellcurve should become standard.

Unless I am gravely mistaken, of course...

Last edited 2 years ago by charpent (previous) (diff)

comment:13 in reply to: ↑ 12 Changed 2 years ago by jdemeyer

  • Status changed from needs_info to needs_review

Replying to charpent:

If you wish to always consult Cremona database in any case

There is a small database which is standard. So consulting "the" Cremona database really means: the large one if that's installed, otherwise the small one.

Also, I'm not saying that consulting always must succeed. The code to get the rank from the database is wrapped in a try:/except LookupError: block and I'm not changing that.

comment:14 follow-ups: Changed 2 years ago by cremona

A couple of comments.

  1. When the new output incudes something like "(guess = 0)" it is not a guess, it is a proved lower bound. (Not saying a lot if it is zero, but it can be positive). Please change "guess" to "lower bound".
  1. I see that the cached rank is no longer a dict with True/False? keys but a single pair (r,T/F). I don't know the reason for this change. I may try to compute the rank with Proof=True (default), got a warning an retired with Proof=False. How does this behave now?

comment:15 in reply to: ↑ 14 Changed 2 years ago by jdemeyer

Replying to cremona:

  1. I see that the cached rank is no longer a dict with True/False? keys but a single pair (r,T/F). I don't know the reason for this change.

This is just a simplification. I found the code dealing with the dict rather complicated. A simple tuple (rank, proven) does the job too.

comment:16 in reply to: ↑ 14 Changed 2 years ago by jdemeyer

  • Status changed from needs_review to needs_work

Replying to cremona:

I may try to compute the rank with Proof=True (default), got a warning an retired with Proof=False.

Neither the old nor the new code deals with that. But you are right that it should.

comment:17 Changed 2 years ago by git

  • Commit changed from 96765dc2be80e53bee137853ebf85ec9e40681c1 to 3cff14c2ea4863634fac9f9009f65efcecbf6b1a

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

3cff14crank() of elliptic curves should always consult Cremona database

comment:18 Changed 2 years ago by jdemeyer

  • Status changed from needs_work to needs_review

Fixed the caching of non-proven output from eclib and the exception message.

comment:19 follow-ups: Changed 2 years ago by mderickx

Hi Jeroen,

Very nice that you found out the cause. I'm trying to see the link to your example and the doctest failure. Because your example fails 100% of the time while the doctest only fails sporadically. Is the explanation that the curve E1 is actually already created on line 362 with sage: E = EllipticCurve([0, -1, 1, -929, -10595]) # 571A and that it is quite random wether this curve still exists or is already garbage collected around the line 915 where the doctest failure occurs?

In the mean time I was able to replicate the doctest failure on arando. I needed to test it with sage -t --global-iterations 1000 before an error showed up. It started failing on the 775th iteration and then it kept failing until the 798th doctest. This might indicate that the randomness might depend on the system load (objects being garbage collected sooner maybe).

P.s. I think it would be good to add the doctest:

    sage: E1 = EllipticCurve([0, -1, 1, -929, -10595])
    sage: E2 = EllipticCurve('571a1')
    sage: E2.rank()
    0

at the top of the file to make sure that we now have a doctest that fails 100% of the time prior to your fix, but works after it.


New commits:

3cff14crank() of elliptic curves should always consult Cremona database
Last edited 2 years ago by mderickx (previous) (diff)

comment:20 Changed 2 years ago by cremona

THanks! Positive review once tests pass and Maarten is happy.

comment:21 in reply to: ↑ 19 Changed 2 years ago by jdemeyer

Replying to mderickx:

Is the explanation that the curve E1 is actually already created on line 362 with sage: E = EllipticCurve([0, -1, 1, -929, -10595]) # 571A and that it is quite random wether this curve still exists or is already garbage collected around the line 915 where the doctest failure occurs?

Exactly.

comment:22 Changed 2 years ago by charpent

FYI, a make ptestlong started before Cremona's comment passed with no errors whatsoever.

It seems to me that comment 20 implies yet another patch-push-test cycle. I'll refrain from ptesting it until that.

comment:23 in reply to: ↑ 19 ; follow-ups: Changed 2 years ago by jdemeyer

Replying to mderickx:

I think it would be good to add the doctest:

    sage: E1 = EllipticCurve([0, -1, 1, -929, -10595])
    sage: E2 = EllipticCurve('571a1')
    sage: E2.rank()
    0

at the top of the file to make sure that we now have a doctest that fails 100% of the time prior to your fix, but works after it.

That's what the 1888b1 (*) test does. It's testing the essence of this patch, namely that rank() should work for curves which are in the database but which are not constructed using the Cremona label. Personally, I don't think that adding E2 = EllipticCurve('1888b1') would add anything interesting to that test.

(*) I looked for a curve which is not used anywhere else in doctests but for which eclib also fails to compute the rank due to a non-trivial Sha[2]. Thanks to the LMFDB for the handy query page!

comment:24 in reply to: ↑ 23 Changed 2 years ago by cremona

Replying to jdemeyer:

(*) I looked for a curve which is not used anywhere else in doctests but for which eclib also fails to compute the rank due to a non-trivial Sha[2]. Thanks to the LMFDB for the handy query page!

We are working on an api for the LMFDB which would make it easy to get all this data (and more) using only an internet connection, making the optional database almost redundant.

comment:25 in reply to: ↑ 23 ; follow-up: Changed 2 years ago by mderickx

That's what the 1888b1 (*) test does. It's testing the essence of this patch, namely that rank() should work for curves which are in the database but which are not constructed using the Cremona label. Personally, I don't think that adding E2 = EllipticCurve('1888b1') would add anything interesting to that test.

(*) I looked for a curve which is not used anywhere else in doctests but for which eclib also fails to compute the rank due to a non-trivial Sha[2]. Thanks to the LMFDB for the handy query page!

Thanks for this explanation, the test itself suffices, and I am happy with the rest of the code (although there might be some nitpicking that your tuple instead of dict change made the caching of .__gens and the .__rank less consistent and I like coding style consistency).

I would like to add a little bit more explanation to this test later this evening (I have to leave now). Since now the text around this test does not seem to make clear the subtle issue that different ways of initialising the same globally unique elliptic curve should give actually an object that behaves the same (ok it has the link to this trac ticket).

comment:26 in reply to: ↑ 25 Changed 2 years ago by jdemeyer

Replying to mderickx:

although there might be some nitpicking that your tuple instead of dict change made the caching of .__gens and the .__rank less consistent and I like coding style consistency.

That's true but I wanted to leave that for a separate ticket.

I would like to add a little bit more explanation to this test later this evening (I have to leave now). Since now the text around this test does not seem to make clear the subtle issue that different ways of initialising the same globally unique elliptic curve should give actually an object that behaves the same (ok it has the link to this trac ticket).

OK. Does this ticket have positive review from you apart from that documentation issue?

comment:27 Changed 2 years ago by git

  • Commit changed from 3cff14c2ea4863634fac9f9009f65efcecbf6b1a to 7b9206cb121643c70a974b502d352bb1afeb8b76

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

7b9206cShow that rank is known when constructing curve from database

comment:28 Changed 2 years ago by jdemeyer

I added a small extra test. Is this what you had in mind?

comment:29 Changed 2 years ago by mderickx

  • Authors changed from Jeroen Demeyer to Jeroen Demeyer, Maarten Derickx
  • Branch changed from u/jdemeyer/doctest_failure_in_src_sage_schemes_elliptic_curves_sha_tate_py to public/23962
  • Commit changed from 7b9206cb121643c70a974b502d352bb1afeb8b76 to 48eaa0aa8c3573e266d6264e04b0cf9eeda873cb
  • Reviewers set to Maarten Derickx

The change I had in mind was slightly different. I agree with the code you have written till now, so that part gets positive review from me. Do you agree with my added extra explanation in the test?


New commits:

48eaa0aTrac #23962: explain why we use database by default

comment:30 Changed 2 years ago by jdemeyer

  • Status changed from needs_review to needs_work

The fact that "Elliptic curves are globally unique even if they are initialized differently" is already tested in src/sage/schemes/elliptic_curves/constructor.py

So there is no need for the extra test

        Elliptic curves are globally unique even if they are initialized differently::

            sage: E1 = EllipticCurve([-517, -4528])
            sage: E2 = EllipticCurve('1888b1')
            sage: E1 is E2
            True

comment:31 Changed 2 years ago by mderickx

Yes, I know, but I like my doctest to tell a story, this is mainly an example leading up to the explanatory text coming after it.

comment:32 Changed 2 years ago by jdemeyer

OK, fine. Could you just remove the duplicate blank line and limit your lines to 72 characters in length?

comment:33 Changed 2 years ago by jdemeyer

  • Authors changed from Jeroen Demeyer, Maarten Derickx to Jeroen Demeyer
  • Branch changed from public/23962 to u/jdemeyer/doctest_failure_in_src_sage_schemes_elliptic_curves_sha_tate_py
  • Commit changed from 48eaa0aa8c3573e266d6264e04b0cf9eeda873cb to 7b9206cb121643c70a974b502d352bb1afeb8b76
  • Status changed from needs_work to positive_review

In order to move forward with this blocker ticket, I suggest to merge the code here and move the discussion about the docs to a new ticket: #23974


New commits:

3cff14crank() of elliptic curves should always consult Cremona database
7b9206cShow that rank is known when constructing curve from database

comment:34 Changed 2 years ago by git

  • Commit changed from 7b9206cb121643c70a974b502d352bb1afeb8b76 to 3cff14c2ea4863634fac9f9009f65efcecbf6b1a
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. This was a forced push. New commits:

comment:35 Changed 2 years ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:36 Changed 2 years ago by mderickx

  • Reviewers changed from Maarten Derickx to Maarten Derickx, John Cremona

comment:37 Changed 2 years ago by vbraun

  • Branch changed from u/jdemeyer/doctest_failure_in_src_sage_schemes_elliptic_curves_sha_tate_py to 3cff14c2ea4863634fac9f9009f65efcecbf6b1a
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.