Sage: Ticket #5153: bug in simon_two_descent for elliptic curves
https://trac.sagemath.org/ticket/5153
<p>
[See <a class="closed ticket" href="https://trac.sagemath.org/ticket/15608" title="defect: metaticket for simon_two_descent issues (closed: fixed)">#15608</a> for a list of open simon_two_descent tickets]
</p>
<p>
We have
</p>
<pre class="wiki">sage: E = EllipticCurve('65a1')
sage: G = E.change_ring(QuadraticField(-56,'a'))
sage: G.simon_two_descent()
(3, 4, [(-9/4 : -3/8*a + 9/8 : 1), (-8/7 : -1/49*a + 4/7 : 1), (1 : 0 : 1),
(-6/25*a - 47/25 : 36/125*a - 368/125 : 1), (1/4 : 1/16*a - 1/8 : 1)])
</pre><p>
The documentation for simon_two_descent says that the output of Simon 2-descent is
</p>
<pre class="wiki"> OUTPUT:
integer -- "probably" the rank of self
integer -- the 2-rank of the Selmer group
list -- list of independent points on the curve.
</pre><p>
Our curve does have rank 3, but the output list above contains *five* points, so they can't be independent!
</p>
<p>
Our curve has torsion of order 2, so E(K)/2 E(K) has rank four, so the 3 and four output by Simon descent are right. The only problem is the list, which has too many points in it.
</p>
<p>
Maybe this is simply a documentation issue, and the docs for simon_two_descent should be changed to say that list is a list of points that *generate* a subgroup of the MW group of rank r, where r is the first number output by simon_two_descent.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/5153
Trac 1.1.6cremonaTue, 09 Jun 2009 11:35:33 GMT
https://trac.sagemath.org/ticket/5153#comment:1
https://trac.sagemath.org/ticket/5153#comment:1
<p>
I will email Denis Simon about this, since he has just done another bug fix in ell.gp after I reported a bug to him. Unfortunately the fix he sent works in the latest pari but not with the one Sage uses.
</p>
TicketcremonaTue, 09 Jun 2009 12:46:49 GMT
https://trac.sagemath.org/ticket/5153#comment:2
https://trac.sagemath.org/ticket/5153#comment:2
<p>
Looking at the example in more detail, I see that the points returned do generate a rank 3 group (though I had to use Magma to check the independence), so there are two problems: (1) the points in the list are not independent (even in E(K)/2E(K)) and (2) the numbers 3,4 which are supposed to be lower and upper bounds on the rank are wrong and should be 3,3.
</p>
<p>
I know how the first happens (since it is doing a descent via 2-isogeny).
</p>
<p>
This will be possible to fix once I (or someone) have eventually implemented heights of points over number fields, as I promised to do in trac <a class="closed ticket" href="https://trac.sagemath.org/ticket/360" title="enhancement: Implementation of elliptic curve height bounds in Sage (closed: wontfix)">#360</a> !
</p>
TicketdavidloefflerMon, 20 Jul 2009 19:59:58 GMTowner, component changed
https://trac.sagemath.org/ticket/5153#comment:3
https://trac.sagemath.org/ticket/5153#comment:3
<ul>
<li><strong>owner</strong>
changed from <em>was</em> to <em>davidloeffler</em>
</li>
<li><strong>component</strong>
changed from <em>number theory</em> to <em>elliptic curves</em>
</li>
</ul>
TicketdavidloefflerFri, 09 Oct 2009 09:09:07 GMTowner deleted
https://trac.sagemath.org/ticket/5153#comment:4
https://trac.sagemath.org/ticket/5153#comment:4
<ul>
<li><strong>owner</strong>
changed from <em>davidloeffler</em> to <em>(none)</em>
</li>
</ul>
TicketnbruinSun, 17 Jan 2010 01:31:16 GMTupstream set
https://trac.sagemath.org/ticket/5153#comment:5
https://trac.sagemath.org/ticket/5153#comment:5
<ul>
<li><strong>upstream</strong>
set to <em>N/A</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/5153#comment:2" title="Comment 2">cremona</a>:
</p>
<blockquote class="citation">
<p>
This will be possible to fix once I (or someone) have eventually implemented heights of points over number fields, as I promised to do in trac <a class="closed ticket" href="https://trac.sagemath.org/ticket/360" title="enhancement: Implementation of elliptic curve height bounds in Sage (closed: wontfix)">#360</a> !
</p>
</blockquote>
<p>
I am not sure that using heights is the best way to get independence if you are doing a 2-descent anyway. The easier thing to do would be to just report back a set of points that minimally generate the 2-selmer group (or at least minimally generate the part of the 2-selmer group generated by the found points)
The only thing you'd miss that way would be if one finds generators for an even index 2 subgroup of the full Mordell-Weil group. I think it's highly unlikely that that would happen.
</p>
TicketwasSun, 17 Jan 2010 05:32:41 GMT
https://trac.sagemath.org/ticket/5153#comment:6
https://trac.sagemath.org/ticket/5153#comment:6
<blockquote class="citation">
<p>
I am not sure that using heights is the best way to get independence
</p>
</blockquote>
<p>
Another excellent trick I learned from Cremona for getting independence is to use *homomorphic images*. I.e., reduce to a direct sum of groups of points over a finite field (all tensored with F_p, with p coprime to torsion). Then the rank of the group you have is a bounded below by the dimension of the image.
</p>
TicketcremonaSun, 17 Jan 2010 11:20:46 GMT
https://trac.sagemath.org/ticket/5153#comment:7
https://trac.sagemath.org/ticket/5153#comment:7
<p>
Good point -- the reference is On the computation of Mordell-Weil and 2-Selmer Groups of Elliptic Curves. Rocky Mountain Journal of Mathematics (2002) vol. 32, no. 3, pp.953--967. This is implemeneted over Q in eclib, and it would be possible to do an implementation over number fields. As Mestre points out, this method for testing independence has the great advantage that it does not depend on precision of height computations, only on linear algebra over F_2.
</p>
TicketnbruinSun, 24 Jan 2010 03:19:29 GMT
https://trac.sagemath.org/ticket/5153#comment:8
https://trac.sagemath.org/ticket/5153#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/5153#comment:6" title="Comment 6">was</a>:
</p>
<blockquote class="citation">
<p>
Another excellent trick I learned from Cremona for getting independence is to use *homomorphic images*. I.e., reduce to a direct sum of groups of points over a finite field (all tensored with F_p, with p coprime to torsion). Then the rank of the group you have is a bounded below by the dimension of the image.
</p>
</blockquote>
<p>
And those same images can also yield information on p-saturation of the group generated by the given points inside the Mordell-Weil group
(just as an independence proof via 2-Selmer groups also gives 2-saturation)
This starts to sound like a nice student project.
</p>
TicketcremonaSun, 24 Jan 2010 12:46:57 GMT
https://trac.sagemath.org/ticket/5153#comment:9
https://trac.sagemath.org/ticket/5153#comment:9
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/5153#comment:8" title="Comment 8">nbruin</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/5153#comment:6" title="Comment 6">was</a>:
</p>
<blockquote class="citation">
<p>
Another excellent trick I learned from Cremona for getting independence is to use *homomorphic images*. I.e., reduce to a direct sum of groups of points over a finite field (all tensored with F_p, with p coprime to torsion). Then the rank of the group you have is a bounded below by the dimension of the image.
</p>
</blockquote>
<p>
And those same images can also yield information on p-saturation of the group generated by the given points inside the Mordell-Weil group
(just as an independence proof via 2-Selmer groups also gives 2-saturation)
This starts to sound like a nice student project.
</p>
</blockquote>
<p>
It was! The thesis of my student Martin Prickett was about saturating Mordell-Weil groups this way, and he implemented it in Magma. See <a class="ext-link" href="http://www.warwick.ac.uk/staff/J.E.Cremona/theses/index.html"><span class="icon"></span>http://www.warwick.ac.uk/staff/J.E.Cremona/theses/index.html</a> . I have Martin's magma code but it is not easy to use. Hence the project still remains, namely to rewrite all that.
</p>
TicketweigandtSun, 28 Mar 2010 03:52:13 GMT
https://trac.sagemath.org/ticket/5153#comment:10
https://trac.sagemath.org/ticket/5153#comment:10
<blockquote class="citation">
<p>
the numbers 3,4 which are supposed to be lower and upper bounds on the rank are wrong and
should be 3,3.
</p>
</blockquote>
<p>
The numbers 3,4, are correct. G has a point of order 2 over its base feild, so the 2-rank of the 2-Selmer group is 4. However, an error like the one you're describing does occur with 438e1 over Q.
</p>
TicketcremonaWed, 31 Mar 2010 12:04:33 GMT
https://trac.sagemath.org/ticket/5153#comment:11
https://trac.sagemath.org/ticket/5153#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/5153#comment:10" title="Comment 10">weigandt</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
the numbers 3,4 which are supposed to be lower and upper bounds on the rank are wrong and
should be 3,3.
</p>
</blockquote>
<p>
The numbers 3,4, are correct. G has a point of order 2 over its base feild, so the 2-rank of the 2-Selmer group is 4. However, an error like the one you're describing does occur with 438e1 over Q.
</p>
</blockquote>
<p>
Do you mean 438e1 over Q? #torsion=2 and rank=0 but the first descent via 2-isogeny gives a rank upper bound of 2. If the rank were 2 then the 2-selmer rank would be 3. two_descent_simon() gives lower bound of 0 and 3 for the rank of the 2-Selmer group. That last one is clearly wrong. I think it is similar to the problem my 2-descent used to have: Simon does not do a second descent, so het gets the uppoer bound of 3 on the rank (not wrong!) but incorrectly calls it the 2-Selmer rank.
</p>
<p>
We should correct the docstring of two_descent_simon, and I will tell Simon that his documentation is incorrect.
</p>
TicketcremonaSat, 03 Apr 2010 16:10:55 GMT
https://trac.sagemath.org/ticket/5153#comment:12
https://trac.sagemath.org/ticket/5153#comment:12
<p>
See <a class="closed ticket" href="https://trac.sagemath.org/ticket/6955" title="defect: update simon denis pari-scripts (closed: fixed)">#6955</a> for the updating of Simon's scripts, which I am now testing.
</p>
TicketcremonaThu, 15 Jul 2010 08:33:37 GMT
https://trac.sagemath.org/ticket/5153#comment:13
https://trac.sagemath.org/ticket/5153#comment:13
<p>
Update 15/7/10: I did tell Simon that his script's documentation is misleading, and he agreed. But last time I checked he had not changed them.
</p>
TicketjdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/5153#comment:14
https://trac.sagemath.org/ticket/5153#comment:14
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketchapotonSat, 21 Sep 2013 12:27:41 GMTkeywords set
https://trac.sagemath.org/ticket/5153#comment:15
https://trac.sagemath.org/ticket/5153#comment:15
<ul>
<li><strong>keywords</strong>
<em>simon_two_descent</em> added
</li>
</ul>
TicketwuthrichSat, 28 Dec 2013 16:29:56 GMTdependencies, author set
https://trac.sagemath.org/ticket/5153#comment:16
https://trac.sagemath.org/ticket/5153#comment:16
<ul>
<li><strong>dependencies</strong>
set to <em>#13593</em>
</li>
<li><strong>author</strong>
set to <em>Chris Wuthrich</em>
</li>
</ul>
<p>
The actual issue reported to fix here, seemed first to me just a question of rewording the documentation. But then I realised that there is a bug, quite hidden, but unpleasant, linked to ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/11372" title="defect: nasty side effect of a failed simon_two_descent search (closed: fixed)">#11372</a>.
</p>
<p>
So we want simon_two_descent (over the rationals of number fields) to return three things
</p>
<ul><li>A proven lower bound for the rank
</li><li>The rank of the 2-Selmer group (this is an upper bound but not sharp in general)
</li><li>A list of points.
</li></ul><p>
I propose that the list of points is a list of points of infinite order. So I filter out the ones that are of order 2 in the list that the script returns. However they are not lin. indep. This was already done over number fields in <a class="closed ticket" href="https://trac.sagemath.org/ticket/13593" title="enhancement: tighter upper bound on elliptic curve rank (closed: fixed)">#13593</a>. So here I modify the function over rationals.
</p>
<p>
Over Q, this function then also saturates these points and, if there are sufficiently many, sets them for <code>E.gens()</code>.
</p>
<p>
That is what my proposed changes in the forthcoming commit will do.
</p>
<p>
Now, there are related issues, but they don't belong to this ticket really. The curve 438e1 gives the wrong 2-Selmer and that is <a class="closed ticket" href="https://trac.sagemath.org/ticket/10735" title="defect: Simon 2-descent only returns an upper bound on the 2-Selmer rank (closed: fixed)">#10735</a>. The fact that we don't saturate over number field should not belong to this ticket. One should open a new one for this. Also the script is outdated (see <a class="closed ticket" href="https://trac.sagemath.org/ticket/11005" title="enhancement: Update Simon's GP scripts (closed: fixed)">#11005</a>) and has plenty of other issues (<a class="new ticket" href="https://trac.sagemath.org/ticket/11041" title="enhancement: Implement the number field method for computing 2-Selmer groups of ... (new)">#11041</a>).
</p>
<p>
The bug introduced by <a class="closed ticket" href="https://trac.sagemath.org/ticket/11372" title="defect: nasty side effect of a failed simon_two_descent search (closed: fixed)">#11372</a>: In the example in the documentation, the only point found is of order 2, while the second descent concludes that the rank is 1. The result shown in the documentation were in fact from mwrank not from simon_two_descent.
</p>
TicketwuthrichSat, 28 Dec 2013 16:35:05 GMTchangetime changed; branch set
https://trac.sagemath.org/ticket/5153#comment:17
https://trac.sagemath.org/ticket/5153#comment:17
<ul>
<li><strong>changetime</strong>
changed from <em>12/28/13 16:29:56</em> to <em>12/28/13 16:29:56</em>
</li>
<li><strong>branch</strong>
set to <em>u/wuthrich/ticket/5153</em>
</li>
</ul>
TicketwuthrichSat, 28 Dec 2013 16:40:29 GMTstatus changed; commit set
https://trac.sagemath.org/ticket/5153#comment:18
https://trac.sagemath.org/ticket/5153#comment:18
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>c24c2b3b74260feb1d32c3ee2eaf0d7c2590ab57</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c24c2b3"><span class="icon"></span>c24c2b3</a></td><td><code>Trac 5153: Furhter modifications to the documentation</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=5dc87b8"><span class="icon"></span>5dc87b8</a></td><td><code>Merge branch 'u/wuthrich/ticket/13593' of git://trac.sagemath.org/sage into ticket/5153</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e5e42b8"><span class="icon"></span>e5e42b8</a></td><td><code>Trac 5153: Filter out the 2-torsion from the points returned by Simon's 2-descent.</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=b1550dc"><span class="icon"></span>b1550dc</a></td><td><code>Trac 13593: Do not put torsion points into gens.</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=9a069c7"><span class="icon"></span>9a069c7</a></td><td><code>Trac #13593: ranks of elliptic curves over number fields</code>
</td></tr></table>
TicketgitSat, 28 Dec 2013 17:56:49 GMTcommit changed
https://trac.sagemath.org/ticket/5153#comment:19
https://trac.sagemath.org/ticket/5153#comment:19
<ul>
<li><strong>commit</strong>
changed from <em>c24c2b3b74260feb1d32c3ee2eaf0d7c2590ab57</em> to <em>c3c480d23c265ddb93f8f58ab79233dcfe8ea0fa</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c3c480d"><span class="icon"></span>c3c480d</a></td><td><code>Merge branch 'u/wuthrich/ticket/13593' of git://trac.sagemath.org/sage into ticket/5153</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=bf7617d"><span class="icon"></span>bf7617d</a></td><td><code>spelling error</code>
</td></tr></table>
TicketcremonaMon, 30 Dec 2013 16:03:28 GMTdescription changed
https://trac.sagemath.org/ticket/5153#comment:20
https://trac.sagemath.org/ticket/5153#comment:20
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/5153?action=diff&version=20">diff</a>)
</li>
</ul>
TicketcremonaMon, 30 Dec 2013 17:09:35 GMT
https://trac.sagemath.org/ticket/5153#comment:21
https://trac.sagemath.org/ticket/5153#comment:21
<p>
I am worried by the documentation sentence
</p>
<pre class="wiki">To obtain a list of generators, use E.gens() after this.
</pre><p>
since the only situation in which <code>E.gens()</code> with return points found by this function are when the lower and upper rank bounds agree *and* the list of points returned has that number of points in it. Otherwise, gens are not cached and a call to E.gens() will use <code>mwrank</code>. So it is a bit misleading?
</p>
TicketwuthrichMon, 30 Dec 2013 17:17:56 GMT
https://trac.sagemath.org/ticket/5153#comment:22
https://trac.sagemath.org/ticket/5153#comment:22
<p>
I meant this as an advice to the standard user that does not care how this is done, but wants the generators.
Maybe the "after this" is confusing. Or we could add more about what happens at the back, but ?? would tell them that too.
</p>
TicketcremonaMon, 30 Dec 2013 17:28:23 GMT
https://trac.sagemath.org/ticket/5153#comment:23
https://trac.sagemath.org/ticket/5153#comment:23
<p>
I suggest just deleting "after this". We can revisit this once we have put in independence-checking over number fields (which is separate from and rather easier than saturating). If you do that, I'll give it a positive review!
</p>
TicketgitMon, 30 Dec 2013 19:05:27 GMTcommit changed
https://trac.sagemath.org/ticket/5153#comment:24
https://trac.sagemath.org/ticket/5153#comment:24
<ul>
<li><strong>commit</strong>
changed from <em>c3c480d23c265ddb93f8f58ab79233dcfe8ea0fa</em> to <em>ad2ced2b14236b9881121c47eb6ee0f20144d5dd</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ad2ced2"><span class="icon"></span>ad2ced2</a></td><td><code>Trac #5153: small change in documentation.</code>
</td></tr></table>
TicketwuthrichMon, 30 Dec 2013 19:07:04 GMT
https://trac.sagemath.org/ticket/5153#comment:25
https://trac.sagemath.org/ticket/5153#comment:25
<p>
Done.
</p>
TicketcremonaMon, 30 Dec 2013 19:58:24 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/5153#comment:26
https://trac.sagemath.org/ticket/5153#comment:26
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>John Cremona</em>
</li>
</ul>
TicketvbraunSun, 05 Jan 2014 02:56:51 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/5153#comment:27
https://trac.sagemath.org/ticket/5153#comment:27
<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>
</ul>
Ticket