Opened 12 years ago
Closed 12 years ago
#7576 closed enhancement (fixed)
improvements to the prove_BSD function
Reported by: | rlm | Owned by: | cremona |
---|---|---|---|
Priority: | major | Milestone: | sage-4.3.1 |
Component: | elliptic curves | Keywords: | |
Cc: | Merged in: | sage-4.3.1.rc1 | |
Authors: | Robert Miller | Reviewers: | William Stein |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This patch makes several improvements to the prove_BSD function:
- better handling of when the Heegner index is computed
- speeds up several cases and makes some other cases possible
- uses results from Dimitar Jetchev's thesis when applying the Kolyvagin bound
Attachments (1)
Change History (17)
comment:1 Changed 12 years ago by
- Description modified (diff)
comment:2 Changed 12 years ago by
- Status changed from new to needs_review
comment:3 Changed 12 years ago by
- Status changed from needs_review to needs_work
comment:4 Changed 12 years ago by
- Status changed from needs_work to needs_review
I think I've addressed all your comments, including handling the alarm better.
comment:5 Changed 12 years ago by
- Status changed from needs_review to needs_work
New report:
- The alarm doesn't work perfectly. On boxen.math with this patch applied to a clean sage-4.3, this fails on the command line (and when doctesting):
sage: E = EllipticCurve('198b') sage: E.prove_BSD(verbosity=1, secs_hi=1)
Otherwise, everse looks good.
comment:6 Changed 12 years ago by
- Status changed from needs_work to needs_review
comment:7 Changed 12 years ago by
- Status changed from needs_review to positive_review
comment:8 Changed 12 years ago by
- Status changed from positive_review to needs_work
For 438e1 and 960d1, we get:
RuntimeError Traceback (most recent call last) /home/wstein/<ipython console> in <module>() /home/wstein/sage/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_rational_field.pyc in prove_BSD(self, verbosity, simon, proof, secs_hi) 6372 print 'p = 2: true by 2-descent' 6373 else: -> 6374 raise RuntimeError("ord2(#Sha) was computed to be %d, but ord2(#Sha_an) is %d for this curve (%s)! This may be a counterexample to BSD, but is more likely a bug."%(sha_ord_2,sha_an.ord(2),self)) 6375 6376 # reduce set of remaining primes to a finite set RuntimeError: ord2(#Sha) was computed to be 1, but ord2(#Sha_an) is 0 for this curve (Elliptic Curve defined by y^2 + x*y + y = x^3 - 130*x - 556 over Rational Field)! This may be a counterexample to BSD, but is more likely a bug.
comment:9 Changed 12 years ago by
Copying from Facebook again:
Jamie Weigandt I read that Robert has implemented a fast 2-isogeny descent. Can this compute the honest 2-Selmer group of a given elliptic curve? I thought these bugs might be arising from the fact that mwrank does not always do this. With 438e, it erroneously computes the rank bound to be 1, while it should be 0. With 960d the optimal curve has sha of order 4 while sha is trivial for an isogenous curve, so mwrank returns a rank bound of 0.
comment:10 Changed 12 years ago by
For the record, it is hardly correct to say that a rank bound of 1 is wrong when the rank is zero! But I know from communication from Weigandt that what the verbose output of mwrank claims to be the "2-Selmer rank" is not always that.
I should send rlm the example he sent me.
comment:11 Changed 12 years ago by
Needs work:
sage: for E in cremona_optimal_curves([1001..2000]): print E.cremona_label(); print E.prove_BSD(verbosity=1, secs_hi=1) ... 1014g1 p = 2: Unverified since it is difficult to access the rank bound for Sha[2] computed by MWrank Interrupting Mwrank... Timeout stopped Heegner index computation... Proceeding to use heegner_index_bound instead. True for p not in {2, 5} by Kolyvagin. Kolyvagin's bound for p = 5 applies by Stein et al. ALERT: p = 5 left in Kolyvagin bound --------------------------------------------------------------------------- UnboundLocalError Traceback (most recent call last) /virtual/scratch/wstein/build/sage-4.3.1.alpha2/<ipython console> in <module>() /virtual/scratch/wstein/build/sage-4.3.1.alpha2/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_rational_field.pyc in prove_BSD(self, verbosity, simon, proof, secs_hi) 6603 if verbosity > 0: 6604 print 'ALERT: p = %d left in Kolyvagin bound'%p -> 6605 print ' 0 <= ord_p(#Sha) <= %d'%ord_p_bound 6606 print ' ord_p(#Sha_an) =', sha_an.ord(p) 6607 for p in primes_to_remove: UnboundLocalError: local variable 'ord_p_bound' referenced before assignment
comment:12 Changed 12 years ago by
- Status changed from needs_work to needs_review
I wasn't able to include a doctest for EllipticCurve('1014g1').prove_BSD(verbosity=1, secs_hi=1)
because it gives a very strange pexpect bug when run from a doctest, even though it runs perfectly fine from the command line.
Changed 12 years ago by
comment:13 Changed 12 years ago by
I tried the following conductor "swaths" and the only error I ran into was caused by the issue at #7575 (I also interrupted a few since they were taking forever):
- range(350,450)
- range(800, 840)
comment:14 Changed 12 years ago by
Just tried range(1200, 1220)
, with similar results (although #7575 did not rear its head).
comment:15 Changed 12 years ago by
- Status changed from needs_review to positive_review
comment:16 Changed 12 years ago by
- Merged in set to sage-4.3.1.rc1
- Resolution set to fixed
- Reviewers set to William Stein
- Status changed from positive_review to closed
REFEREE REPORT:
E.g., the proof one should be:
I find it useful to try making a simple function with the given docstring in the notebook, then evaluate and introspect that, to see what Sphinx does.
``secs_hi`` - how many seconds to try to compute the Heegner index
-- change "how many seconds" to "maximum number of seconds", which is more precise.This might be related to how you setup the alarm. It's hard to tell.
Also, the above hard-coded 100 makes me a little nervous. What happens if we go through the whole list of 100 and don't find one that works? (Highly unlikely in practice, of course.) Then we think the last one we looked at does work. Not good.
It's trivial that
ord_p(#Sha)>=0
, since#Sha
is an integer, andord_p(n)>=0
for any integer n.