Sage: Ticket #10735: Simon 2-descent only returns an upper bound on the 2-Selmer rank
https://trac.sagemath.org/ticket/10735
<p>
[See <a class="closed ticket" href="https://trac.sagemath.org/ticket/15608" title="#15608: defect: metaticket for simon_two_descent issues (closed: fixed)">#15608</a> for a list of open simon_two_descent tickets]
</p>
<p>
Given an elliptic curve E the method E.simon_two_descent() returns an ordered triple. This consists of a lower bound on the Mordell-Weil rank of E, an integer which is supposed to be the F_2 dimension of the 2-Selmer group of E, and list of points, generating the part of the Mordell-Weil group that has been found.
</p>
<p>
Sometimes the second entry is larger than the actual 2-Selmer rank as computed by mwrank, and predicted by BSD. The first curve I know of for which this happens is the elliptic curve '438e1' from Cremona's tables.
</p>
<pre class="wiki">sage: E=EllipticCurve('438e1')
sage: E.simon_two_descent()
(0, 3, [(13 : -7 : 1)])
sage: E.selmer_rank() #uses mwrank
1
sage: E.sha().an()
1
</pre><p>
The explanation for this is that <code>E.simon_two_descent()</code>, unlike Cremona's <code>mwrank</code>, does not do a second descent and therefore only determines an upper bound on the 2-Selmer rank.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/10735
Trac 1.2Jeroen DemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/10735#comment:1
https://trac.sagemath.org/ticket/10735#comment:1
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketwuthrichSat, 28 Dec 2013 01:55:19 GMTupstream changed
https://trac.sagemath.org/ticket/10735#comment:2
https://trac.sagemath.org/ticket/10735#comment:2
<ul>
<li><strong>upstream</strong>
changed from <em>N/A</em> to <em>Reported upstream. No feedback yet.</em>
</li>
</ul>
<p>
This is a bug in Simon's script indeed. I have emailed him about this one, too, as it happens with the later version of his file in gp, too.
</p>
TicketwuthrichSat, 28 Dec 2013 02:02:37 GMTtype changed
https://trac.sagemath.org/ticket/10735#comment:3
https://trac.sagemath.org/ticket/10735#comment:3
<ul>
<li><strong>type</strong>
changed from <em>PLEASE CHANGE</em> to <em>defect</em>
</li>
</ul>
TicketJohn CremonaMon, 30 Dec 2013 16:04:18 GMTdescription changed
https://trac.sagemath.org/ticket/10735#comment:4
https://trac.sagemath.org/ticket/10735#comment:4
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/10735?action=diff&version=4">diff</a>)
</li>
</ul>
TicketFor batch modificationsThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/10735#comment:5
https://trac.sagemath.org/ticket/10735#comment:5
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
TicketPeter BruinTue, 11 Feb 2014 19:55:07 GMTdependencies set
https://trac.sagemath.org/ticket/10735#comment:6
https://trac.sagemath.org/ticket/10735#comment:6
<ul>
<li><strong>dependencies</strong>
set to <em>#11005</em>
</li>
</ul>
<p>
The problem still exists after <a class="closed ticket" href="https://trac.sagemath.org/ticket/11005" title="#11005: enhancement: Update Simon's GP scripts (closed: fixed)">#11005</a>, which upgrades Simon's scripts to the latest version:
</p>
<pre class="wiki">sage: E=EllipticCurve('438e1')
sage: E.simon_two_descent()
(0, 3, [])
</pre><p>
(Note: the torsion point (13, -7) is no longer returned since <a class="closed ticket" href="https://trac.sagemath.org/ticket/13593" title="#13593: enhancement: tighter upper bound on elliptic curve rank (closed: fixed)">#13593</a>.)
</p>
TicketPeter BruinThu, 13 Feb 2014 23:58:18 GMT
https://trac.sagemath.org/ticket/10735#comment:7
https://trac.sagemath.org/ticket/10735#comment:7
<p>
It seems to me that the bug is <em>not</em> caused by failing to detect non-solubility at the real place. In fact, Simon's script computes the same 2-isogeny Selmer ranks as <code>mwrank</code>, but deduces an incorrect 2-Selmer rank from these.
</p>
<p>
Output of <code>mwrank</code>:
</p>
<pre class="wiki">Curve [1,0,1,-130,-556] :
1 points of order 2:
[13:-7:1]
Using 2-isogenous curve [0,-314,0,73,0] (minimal model [1,0,1,-2050,-35884])
-------------------------------------------------------
First step, determining 1st descent Selmer groups
-------------------------------------------------------
After first local descent, rank bound = 2
rk(S^{phi}(E'))= 3
rk(S^{phi'}(E))= 1
-------------------------------------------------------
Second step, determining 2nd descent Selmer groups
-------------------------------------------------------
After second local descent, rank bound = 0
rk(phi'(S^{2}(E)))= 1
rk(phi(S^{2}(E')))= 1
rk(S^{2}(E))= 1
rk(S^{2}(E'))= 3
Third step, determining E(Q)/phi(E'(Q)) and E'(Q)/phi'(E(Q))
-------------------------------------------------------
1. E(Q)/phi(E'(Q))
-------------------------------------------------------
(c,d) =(157,6144)
(c',d')=(-314,73)
This component of the rank is 0
-------------------------------------------------------
2. E'(Q)/phi'(E(Q))
-------------------------------------------------------
This component of the rank is 0
-------------------------------------------------------
Summary of results:
-------------------------------------------------------
rank(E) = 0
#E(Q)/2E(Q) = 2
Information on III(E/Q):
#III(E/Q)[phi'] = 1
#III(E/Q)[2] = 1
Information on III(E'/Q):
#phi'(III(E/Q)[2]) = 1
#III(E'/Q)[phi] = 4
#III(E'/Q)[2] = 4
Used descent via 2-isogeny with isogenous curve E' = [1,0,1,-2050,-35884]
Rank = 0
Rank of S^2(E) = 1
Rank of S^2(E') = 3
Rank of S^phi(E') = 3
Rank of S^phi'(E) = 1
Processing points found during 2-descent...done:
now regulator = 1
Regulator = 1
The rank and full Mordell-Weil basis have been determined unconditionally.
(0.098 seconds)
</pre><p>
Output of <code>simon_two_descent</code>:
</p>
<pre class="wiki">ellrank([1,0,1,-130,-556]);
Elliptic curve: Y^2 = x^3 + x^2 - 2072*x - 35568
E[2] = [[0], [52, 0]]
Elliptic curve: Y^2 = x^3 + 157*x^2 + 6144*x
Algorithm of 2-descent via isogenies
trivial points on E(Q) = [[0, 0], [1, 1, 0], [0, 0], [0, 0]]
#K(b,2)gen = 3
K(b,2)gen = [-1, 2, 3]~
quartic ELS: Y^2 = -x^4 + 157*x^2 - 6144
no point found on the quartic
quartic ELS: Y^2 = 2*x^4 + 157*x^2 + 3072
no point found on the quartic
quartic ELS: Y^2 = -2*x^4 + 157*x^2 - 3072
no point found on the quartic
quartic ELS: Y^2 = 3*x^4 + 157*x^2 + 2048
no point found on the quartic
quartic ELS: Y^2 = -3*x^4 + 157*x^2 - 2048
no point found on the quartic
point on the quartic
points on E(Q) = [[0, 0]]
[E(Q):phi'(E'(Q))] >= 2
#S^(phi')(E'/Q) = 8 # agrees with mwrank
#III(E'/Q)[phi'] <= 4
#K(a^2-4b,2)gen = 2
K(a^2-4b,2)gen = [-1, 73]~
trivial points on E'(Q) = [[0, 0], [1, 1, 0], [0, 0], [0, 0]]
point on the quartic
points on E'(Q) = [[0, 0]]
points on E(Q) = [[0, 0]]
[E'(Q):phi(E(Q))] = 2
#S^(phi)(E/Q) = 2 # agrees with mwrank
#III(E/Q)[phi] = 1
#III(E/Q)[2] <= 4
#E(Q)[2] = 2
#E(Q)/2E(Q) >= 2
0 <= rank <= 2
points = [[0, 0]]
v = [0, 3, [[13, -7]]]
</pre><p>
The 3 in the last line, which should be the rank of the 2-Selmer group according to the documentation, is the result of computing (rank of <code>S^(phi)(E/Q)</code>) + (rank of <code>S^(phi')(E'/Q)</code>) + (rank of <code>E(Q)[2]</code>) - 2 = 1 + 3 + 1 - 2 = 3. There must be something wrong with this formula, as it is symmetric in <em>E</em> and <em>E' </em> (in this particular case, since <code>E(Q)[2]</code> and <code>E'(Q)[2]</code> both have rank 1) while the 2-Selmer ranks of <em>E</em> and <em>E' </em> are in fact different (1 and 3, respectively).
</p>
TicketwuthrichSat, 15 Feb 2014 00:19:12 GMT
https://trac.sagemath.org/ticket/10735#comment:8
https://trac.sagemath.org/ticket/10735#comment:8
<p>
That is indeed bad. The fomula (after the first descent) is indeed
</p>
<blockquote>
<p>
dim Sel_phi + dim Sel_phihat + dim E[2] - 2 .
</p>
</blockquote>
<p>
this is a upper bound to dim Sel_2 and they have the same parity. But they need not be equal as the second descent in mwrank finds. The difference is a subquotient of Sha(E').
</p>
<p>
Conclusion: The output of Simon's algorithm is an upper bound on the 2-Selmer group, which is correct in parity, but not necessarily equal.
</p>
<p>
In propose that we change the documentation, for I don't image that Simon's script could give back to full answer - though I have not looked at it.
</p>
TicketJohn CremonaSat, 15 Feb 2014 11:07:54 GMT
https://trac.sagemath.org/ticket/10735#comment:9
https://trac.sagemath.org/ticket/10735#comment:9
<p>
You are right. DS does no second descent (unlike mwrank when over Q and with 2-torsion) and the second descent can give a better upper bound on the rank.
</p>
TicketPeter BruinSat, 15 Feb 2014 12:56:54 GMTdescription, summary changed
https://trac.sagemath.org/ticket/10735#comment:10
https://trac.sagemath.org/ticket/10735#comment:10
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/10735?action=diff&version=10">diff</a>)
</li>
<li><strong>summary</strong>
changed from <em>Simon 2-descent may not check for solubility at archimedean places.</em> to <em>Simon 2-descent only returns an upper bound on the 2-Selmer rank</em>
</li>
</ul>
<p>
Changing the documentation does indeed sound like the right solution here. The correctness of the parity of this upper bound probably relies on finiteness of Ш, or doesn't it?
</p>
TicketwuthrichSat, 15 Feb 2014 13:04:23 GMT
https://trac.sagemath.org/ticket/10735#comment:11
https://trac.sagemath.org/ticket/10735#comment:11
<p>
No the correctness of the parity is unconditional. (This is used for instance in the proof of the p-parity conjecture via p-isogeny.)
</p>
TicketPeter BruinMon, 17 Feb 2014 21:00:34 GMTpriority, status changed; commit, branch, author set
https://trac.sagemath.org/ticket/10735#comment:12
https://trac.sagemath.org/ticket/10735#comment:12
<ul>
<li><strong>priority</strong>
changed from <em>major</em> to <em>minor</em>
</li>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>a47b7a1281fdc057ac148535e88a01ed113dd8fc</em>
</li>
<li><strong>branch</strong>
set to <em>u/pbruin/10735-simon_two_descent_doc</em>
</li>
<li><strong>author</strong>
set to <em>Peter Bruin</em>
</li>
</ul>
<p>
Here is a patch for the documentation of <code>simon_two_descent()</code>, including a new doctest using the example from the ticket description.
</p>
<p>
There are a few other improvements to the docstring. In particular, it contained several calls to <code>set_random_seed()</code>. These can't have any effect, because Simon's script runs inside a separate GP interpreter with its own random state, so I removed these.
</p>
TicketPeter BruinMon, 17 Feb 2014 21:09:36 GMT
https://trac.sagemath.org/ticket/10735#comment:13
https://trac.sagemath.org/ticket/10735#comment:13
<p>
Another thing: the method <code>simon_two_descent()</code> is currently not quite consistent between <strong>Q</strong> and other number fields: the method over <strong>Q</strong> removes points of finite order from the list (at least since <a class="closed ticket" href="https://trac.sagemath.org/ticket/5153" title="#5153: defect: bug in simon_two_descent for elliptic curves (closed: fixed)">#5153</a>), but the corresponding method over general number fields does not. I made the documentation consistent with this, but did not change any code. If we want to fix this, it is probably best to do it as part of <a class="closed ticket" href="https://trac.sagemath.org/ticket/10745" title="#10745: defect: bug in elliptic curve gens() (closed: fixed)">#10745</a>.
</p>
TicketwuthrichFri, 28 Mar 2014 17:51:55 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/10735#comment:14
https://trac.sagemath.org/ticket/10735#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Chris Wuthrich</em>
</li>
</ul>
<p>
We removed the points of finite order from <code>.gens()</code> for number fields but not from <code>simon_two_descent()</code>, which is a bit inconsistent, indeed. I agree to adress this in <a class="closed ticket" href="https://trac.sagemath.org/ticket/10745" title="#10745: defect: bug in elliptic curve gens() (closed: fixed)">#10745</a>.
</p>
<p>
Now to this ticket. I have run all tests and I am certainly happy with the improvement. So I give a positive review. I am not sure about the random seed issue above, but I trust you. Otherwise someone will complain at some point.
</p>
TicketgitFri, 28 Mar 2014 19:16:43 GMTstatus, commit changed
https://trac.sagemath.org/ticket/10735#comment:15
https://trac.sagemath.org/ticket/10735#comment:15
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
changed from <em>a47b7a1281fdc057ac148535e88a01ed113dd8fc</em> to <em>732191df41bcc093230a41e747514bcdef46fd40</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. Last 10 new commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=b2b66c54b8fd220e976c9d5ddcaeb6eec8ba7ff8"><span class="icon"></span>b2b66c5</a></td><td><code>Fixed calls to simon's two descent to use his own defaults (by default).</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=594de7b4cabd1359de0c33748e17dc9209f4b61b"><span class="icon"></span>594de7b</a></td><td><code>Merge branch 'u/mmasdeu/9322-defaults-for-two-descent' of git://trac.sagemath.org/sage into ticket/9322-simon_two_descent_defaults</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=db790353ddf534dc32fced15afdadb54f96cce94"><span class="icon"></span>db79035</a></td><td><code>Merge branch 'develop' into gp_simon_relative</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a92a80eb918e5f6de14269f04317a1b95b3a4b4b"><span class="icon"></span>a92a80e</a></td><td><code>Changed the doctest to make it independent of variable output.</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=275e4bef0c5027517163a50248cf417308d6bde7"><span class="icon"></span>275e4be</a></td><td><code>fix a bug in Denis Simon's 2-descent program</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=8bceb36e55fe51e86815f8432eec201d401595ea"><span class="icon"></span>8bceb36</a></td><td><code>Merge branch 'u/pbruin/16022-simon_two_descent_bug' of trac.sagemath.org:sage into gp_simon_relative</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=962d338206fb9d7ace6b1367b24f12d97e53601a"><span class="icon"></span>962d338</a></td><td><code>Merge branch 'ticket/16009-gp_simon_relative' into ticket/9322-simon_two_descent_defaults</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=4bdb5389e8b1a41ebfcf00a5c2561f0841113854"><span class="icon"></span>4bdb538</a></td><td><code>fix doctests in ell_number_field.py</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ecd28b4f5ba2bff231807a512170a6e02e2a32aa"><span class="icon"></span>ecd28b4</a></td><td><code>use default limtriv=3 for simon_two_descent over Q</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=732191df41bcc093230a41e747514bcdef46fd40"><span class="icon"></span>732191d</a></td><td><code>Merge branch 'ticket/9322-simon_two_descent_defaults' into ticket/10735-two_selmer_discrepancy</code>
</td></tr></table>
TicketPeter BruinFri, 28 Mar 2014 19:18:46 GMTstatus, dependencies changed
https://trac.sagemath.org/ticket/10735#comment:16
https://trac.sagemath.org/ticket/10735#comment:16
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>dependencies</strong>
changed from <em>#11005</em> to <em>#11005, #9322</em>
</li>
</ul>
<p>
There was just a trivial merge conflict with <a class="closed ticket" href="https://trac.sagemath.org/ticket/9322" title="#9322: defect: long time in simon_two_descent for elliptic curves (closed: fixed)">#9322</a>, which also has positive review, so I merged that branch and made it a dependency.
</p>
TicketVolker BraunMon, 31 Mar 2014 21:12:33 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/10735#comment:17
https://trac.sagemath.org/ticket/10735#comment:17
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/pbruin/10735-simon_two_descent_doc</em> to <em>732191df41bcc093230a41e747514bcdef46fd40</em>
</li>
</ul>
Ticket