Opened 5 years ago
Closed 5 years ago
#23962 closed defect (fixed)
rank() of elliptic curves should always consult Cremona database
Reported by:  Maarten Derickx  Owned by:  

Priority:  blocker  Milestone:  sage8.1 
Component:  elliptic curves  Keywords:  
Cc:  John Cremona  Merged in:  
Authors:  Jeroen Demeyer  Reviewers:  Maarten Derickx, John Cremona 
Report Upstream:  N/A  Work issues:  
Branch:  3cff14c (Commits, GitHub, GitLab)  Commit:  3cff14c2ea4863634fac9f9009f65efcecbf6b1a 
Dependencies:  Stopgaps: 
Description (last modified by )
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) <ipythoninput3d3aae2f31e01> in <module>() > 1 E2.rank() /usr/local/src/sageconfig/local/lib/python2.7/sitepackages/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/sagepatchbot/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 515, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/patchbot/sagepatchbot/local/lib/python2.7/sitepackages/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/sagepatchbot/local/lib/python2.7/sitepackages/sage/schemes/elliptic_curves/sha_tate.py", line 934, in two_selmer_bound r = E.rank() File "/home/patchbot/sagepatchbot/local/lib/python2.7/sitepackages/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 followup: 2 Changed 5 years ago by
comment:2 Changed 5 years ago by
Description:  modified (diff) 

Replying to tscrim:
This might come from #23544.
I don't think so. I was reported om sagerelease 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 5 years ago by
Authors:  → Jeroen Demeyer 

Cc:  John Cremona added 
Description:  modified (diff) 
Summary:  Doctest failure in src/sage/schemes/elliptic_curves/sha_tate.py → Uniqueness of elliptic curves causes data not to be read from Cremona database 
comment:4 Changed 5 years ago by
Authors:  Jeroen Demeyer 

Cc:  John Cremona removed 
Description:  modified (diff) 
Summary:  Uniqueness of elliptic curves causes data not to be read from Cremona database → 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 5 years ago by
Authors:  → Jeroen Demeyer 

Cc:  John Cremona added 
Description:  modified (diff) 
Summary:  Doctest failure in src/sage/schemes/elliptic_curves/sha_tate.py → Uniqueness of elliptic curves causes data not to be read from Cremona database 
comment:6 Changed 5 years ago by
Authors:  Jeroen Demeyer 

Cc:  John Cremona removed 
Description:  modified (diff) 
Summary:  Uniqueness of elliptic curves causes data not to be read from Cremona database → 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 5 years ago by
Authors:  → Jeroen Demeyer 

Cc:  John Cremona added 
Description:  modified (diff) 
Summary:  Doctest failure in src/sage/schemes/elliptic_curves/sha_tate.py → rank() of elliptic curves should always consult Cremona database 
comment:8 Changed 5 years ago by
Description:  modified (diff) 

comment:9 Changed 5 years ago by
Description:  modified (diff) 

comment:10 Changed 5 years ago by
Branch:  → u/jdemeyer/doctest_failure_in_src_sage_schemes_elliptic_curves_sha_tate_py 

comment:11 Changed 5 years ago by
Commit:  → 96765dc2be80e53bee137853ebf85ec9e40681c1 

Status:  new → needs_review 
New commits:
96765dc  rank() of elliptic curves should always consult Cremona database

comment:12 followup: 13 Changed 5 years ago by
Status:  needs_review → 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...
comment:13 Changed 5 years ago by
Status:  needs_info → 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 followups: 15 16 Changed 5 years ago by
A couple of comments.
 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".
 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 Changed 5 years ago by
Replying to cremona:
 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 Changed 5 years ago by
Status:  needs_review → 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 5 years ago by
Commit:  96765dc2be80e53bee137853ebf85ec9e40681c1 → 3cff14c2ea4863634fac9f9009f65efcecbf6b1a 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
3cff14c  rank() of elliptic curves should always consult Cremona database

comment:18 Changed 5 years ago by
Status:  needs_work → needs_review 

Fixed the caching of nonproven output from eclib
and the exception message.
comment:19 followups: 21 23 Changed 5 years ago by
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 globaliterations 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:
3cff14c  rank() of elliptic curves should always consult Cremona database

comment:21 Changed 5 years ago by
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 5 years ago by
FYI, a make ptestlong
started before Cremona's comment passed with no errors whatsoever.
It seems to me that comment 20 implies yet another patchpushtest cycle. I'll refrain from ptest
ing it until that.
comment:23 followups: 24 25 Changed 5 years ago by
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() 0at 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 nontrivial Sha[2]. Thanks to the LMFDB for the handy query page!
comment:24 Changed 5 years ago by
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 nontrivial 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 followup: 26 Changed 5 years ago by
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 addingE2 = 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 nontrivial 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 Changed 5 years ago by
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 5 years ago by
Commit:  3cff14c2ea4863634fac9f9009f65efcecbf6b1a → 7b9206cb121643c70a974b502d352bb1afeb8b76 

Branch pushed to git repo; I updated commit sha1. New commits:
7b9206c  Show that rank is known when constructing curve from database

comment:29 Changed 5 years ago by
Authors:  Jeroen Demeyer → Jeroen Demeyer, Maarten Derickx 

Branch:  u/jdemeyer/doctest_failure_in_src_sage_schemes_elliptic_curves_sha_tate_py → public/23962 
Commit:  7b9206cb121643c70a974b502d352bb1afeb8b76 → 48eaa0aa8c3573e266d6264e04b0cf9eeda873cb 
Reviewers:  → 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:
48eaa0a  Trac #23962: explain why we use database by default

comment:30 Changed 5 years ago by
Status:  needs_review → 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 5 years ago by
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 5 years ago by
OK, fine. Could you just remove the duplicate blank line and limit your lines to 72 characters in length?
comment:33 Changed 5 years ago by
Authors:  Jeroen Demeyer, Maarten Derickx → Jeroen Demeyer 

Branch:  public/23962 → u/jdemeyer/doctest_failure_in_src_sage_schemes_elliptic_curves_sha_tate_py 
Commit:  48eaa0aa8c3573e266d6264e04b0cf9eeda873cb → 7b9206cb121643c70a974b502d352bb1afeb8b76 
Status:  needs_work → 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:
3cff14c  rank() of elliptic curves should always consult Cremona database

7b9206c  Show that rank is known when constructing curve from database

comment:34 Changed 5 years ago by
Commit:  7b9206cb121643c70a974b502d352bb1afeb8b76 → 3cff14c2ea4863634fac9f9009f65efcecbf6b1a 

Status:  positive_review → 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 5 years ago by
Status:  needs_review → positive_review 

comment:36 Changed 5 years ago by
Reviewers:  Maarten Derickx → Maarten Derickx, John Cremona 

comment:37 Changed 5 years ago by
Branch:  u/jdemeyer/doctest_failure_in_src_sage_schemes_elliptic_curves_sha_tate_py → 3cff14c2ea4863634fac9f9009f65efcecbf6b1a 

Resolution:  → fixed 
Status:  positive_review → closed 
This might come from #23544.