Sage: Ticket #15483: Simon 2-descent gives RuntimeError for an elliptic curve over a quadratic field
https://trac.sagemath.org/ticket/15483
<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>
The following tries to do 2-descent on an elliptic curve over a quadratic field:
</p>
<pre class="wiki">K.<s>=QuadraticField(229)
c4=2173-235*(1-s)/2
c6=-124369+15988*(1-s)/2
E=EllipticCurve([-c4/48,-c6/864])
E.simon_two_descent()
</pre><p>
It fails with a <code>RuntimeError</code>:
</p>
<pre class="wiki">Traceback (most recent call last):
...
RuntimeError:
*** at top-level: ans=bnfellrank(K,[0,0,0,
*** ^--------------------
*** in function bnfellrank: ...eqtheta,rnfeq,bbnf];rang=
*** bnfell2descent_gen(b
*** ^--------------------
*** in function bnfell2descent_gen: ...riv,r=nfsqrt(nf,norm(zc))
*** [1];if(DEBUGLEVEL_el
*** ^--------------------
*** array index (1) out of allowed range [none].
An error occurred while running Simon's 2-descent program
</pre><p>
The problem is apparently that the square root of <code>norm(zc)</code> (which is indeed a square) is not computed due to a precision bug; see <a class="ticket" href="https://trac.sagemath.org/ticket/15483#comment:7" title="Comment 7">comment:7</a> below.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/15483
Trac 1.2John CremonaWed, 04 Dec 2013 19:52:22 GMT
https://trac.sagemath.org/ticket/15483#comment:1
https://trac.sagemath.org/ticket/15483#comment:1
<p>
There are many similar bug reports with separate trac tickets. I have no idea if this is a new bug or not. Anyway, the version Sage has of DS's scripts are not the most recent one so there is no point in reporting this back to him unless you check that it happens with the scripts on his web page and you email him without mentioning Sage, otherwise he will just assume that the problem lies with Sage (which is possible).
</p>
<p>
Several of us spend hours or even days in 2011 sage Days (more than one) working on this sort of thing and gave up. We were trying to do more, namely rewrite the interface so that it can use a gp2c-compiled version of the scripts. One day I'll have another go at that.
</p>
<p>
Meanwhile, this entry is to make sure that no-one wastes any time at all looking into the versions of the scripts which Sage currently includes; you should test against the current versions.
</p>
TicketPeter BruinWed, 04 Dec 2013 21:32:35 GMTdescription changed
https://trac.sagemath.org/ticket/15483#comment:2
https://trac.sagemath.org/ticket/15483#comment:2
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/15483?action=diff&version=2">diff</a>)
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15483#comment:1" title="Comment 1">cremona</a>:
</p>
<blockquote class="citation">
<p>
There are many similar bug reports with separate trac tickets. I have no idea if this is a new bug or not. Anyway, the version Sage has of DS's scripts are not the most recent one so there is no point in reporting this back to him unless you check that it happens with the scripts on his web page and you email him without mentioning Sage, otherwise he will just assume that the problem lies with Sage (which is possible).
</p>
</blockquote>
<p>
I searched for other tickets related to Simon's code and did not find reports of this particular problem. We should first upgrade to the latest version of his script and then see which of the various problems listed at <a class="new ticket" href="https://trac.sagemath.org/ticket/11041" title="#11041: enhancement: Implement the number field method for computing 2-Selmer groups of ... (new)">#11041</a> persist. I added this ticket to that list for easier reference.
</p>
TicketwuthrichFri, 27 Dec 2013 23:40:04 GMTupstream changed
https://trac.sagemath.org/ticket/15483#comment:3
https://trac.sagemath.org/ticket/15483#comment:3
<ul>
<li><strong>upstream</strong>
changed from <em>N/A</em> to <em>Not yet reported upstream; Will do shortly.</em>
</li>
</ul>
<p>
Lorenzini reported me a similar bug and I had a look. I now believe that this is a bug in Simon's script as I can reproduce it outside sage. I used the version of his file dated 06/04/2011, which is the newest I found on the web, while sage has one dated the 25/03/2009. So besides that bug, the file needs to be updated anyway. I tried both in sage's gp (2.5.5) and the current alpha (2.6.1).
</p>
<p>
I send an email to Denis and see if and how fast we can hope for a solution of this. Otherwise, I may at least update the script, later.
</p>
<p>
Lorenzini's example is a bit simpler:
</p>
<pre class="wiki">R.<t> = QQ[]
L.<g> = NumberField(t^3 - 9*t^2 + 13*t - 4)
E1 = EllipticCurve(L,[1-g*(g-1),-g^2*(g-1),-g^2*(g-1),0,0])
E1.rank()
</pre>
TicketJohn CremonaMon, 30 Dec 2013 16:06:30 GMTdescription changed
https://trac.sagemath.org/ticket/15483#comment:4
https://trac.sagemath.org/ticket/15483#comment:4
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/15483?action=diff&version=4">diff</a>)
</li>
</ul>
TicketFor batch modificationsThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/15483#comment:5
https://trac.sagemath.org/ticket/15483#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:57:04 GMTdependencies set
https://trac.sagemath.org/ticket/15483#comment:6
https://trac.sagemath.org/ticket/15483#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 script to the latest version.
</p>
TicketPeter BruinWed, 12 Feb 2014 10:46:34 GMTdescription changed
https://trac.sagemath.org/ticket/15483#comment:7
https://trac.sagemath.org/ticket/15483#comment:7
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/15483?action=diff&version=7">diff</a>)
</li>
</ul>
<p>
It seems that the bug is caused by a precision problem in <code>subst</code>, called by <code>nfrealsign</code> in <code>ell.gp</code>. The following GP input demonstrates this (using the latest version of <code>ell.gp</code>, see <a class="closed ticket" href="https://trac.sagemath.org/ticket/11005" title="#11005: enhancement: Update Simon's GP scripts (closed: fixed)">#11005</a>):
</p>
<pre class="wiki">\r src/ext/pari/simon/ell.gp
b = -1554544300737274875964190134520312870631312460283689944298138572669148295776039072867720281361776956435252620954745928376624817557704277432961924925312*y + 23524523971732905757341977352314040726186200302188191824300117738073539522011689544444863977622786771332621915440577829842674416407299864303146477224320
a = Mod(b, y^2 - 229);
\p 38 \\ default precision
K = bnfinit(y^2 - 229);
nfrealsign(K, a, 1) \\ result: 1
nfrealsign(K, a, 2) \\ result: -1 (wrong)
subst(b, y, K.roots[2]) \\ result: -7.695704335233296721 E112, incorrect to this precision
\p 500 \\ increase precision
K = bnfinit(y^2 - 229);
nfrealsign(K, a, 1) \\ result: 1
nfrealsign(K, a, 2) \\ result: 1
subst(b, y, K.roots[2]) \\ result: 55550556624985845118007242443189926820306719407.796355955086894963616120700422308457186069825115395206111444495243228840597412527828358943327267422898011087182852030228685210492253493260963313348652457717717703991690402543456279919008587884729307897541432624377818611055431792706380900043638904108307170236335925883131494247446074384269328376967381902948861789570537169455258630011202296209679102466188417
</pre><p>
The value of <code>K.roots</code> does not seem to be the problem; the roots are calculated correctly to the requested precision.
</p>
TicketPeter BruinWed, 12 Feb 2014 11:41:54 GMT
https://trac.sagemath.org/ticket/15483#comment:8
https://trac.sagemath.org/ticket/15483#comment:8
<p>
The basic problem seems to be that PARI is too optimistic about the resulting precision when adding real numbers:
</p>
<pre class="wiki">? b = -1554544300737274875964190134520312870631312460283689944298138572669148295776039072867720281361776956435252620954745928376624817557704277432961924925312*y + 23524523971732905757341977352314040726186200302188191824300117738073539522011689544444863977622786771332621915440577829842674416407299864303146477224320
? K = bnfinit(y^2 - 229);
? u=polcoeff(b,1)*K.roots[2]
%167 = -2.3524523971732905757341977352314040726 E151
? v=polcoeff(b,0)*1.
%168 = 2.3524523971732905757341977352314040726 E151
? u+v
%169 = -7.695704335233296721 E112
? precision(u)
%170 = 38
? precision(v)
%171 = 38
? precision(u+v)
%172 = 19
</pre>
TicketPeter BruinWed, 12 Feb 2014 12:15:38 GMTupstream changed
https://trac.sagemath.org/ticket/15483#comment:9
https://trac.sagemath.org/ticket/15483#comment:9
<ul>
<li><strong>upstream</strong>
changed from <em>Not yet reported upstream; Will do shortly.</em> to <em>Reported upstream. No feedback yet.</em>
</li>
</ul>
<p>
E-mailed <code>pari-dev</code> and Denis Simon about the precision issue, also suggesting a quick fix for <code>ell.gp</code>.
</p>
TicketPeter BruinWed, 12 Feb 2014 12:27:54 GMT
https://trac.sagemath.org/ticket/15483#comment:10
https://trac.sagemath.org/ticket/15483#comment:10
<p>
The quick fix is to increase the bound in the precision check in <code>nfrealsign</code> from 10 digits to 38 digits (128 bits). This at least makes the error in my example and that reported by Lorenzini disappear.
</p>
TicketPeter BruinWed, 12 Feb 2014 12:38:03 GMTstatus changed; commit, branch set
https://trac.sagemath.org/ticket/15483#comment:11
https://trac.sagemath.org/ticket/15483#comment:11
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>d34a77ab7abe4072349e10e0154a598da94b7c31</em>
</li>
<li><strong>branch</strong>
set to <em>u/pbruin/15483-two_descent_precision</em>
</li>
</ul>
TicketPeter BruinWed, 12 Feb 2014 12:42:12 GMTstatus changed
https://trac.sagemath.org/ticket/15483#comment:12
https://trac.sagemath.org/ticket/15483#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
This needs a doctest...
</p>
TicketgitWed, 12 Feb 2014 14:59:20 GMTcommit changed
https://trac.sagemath.org/ticket/15483#comment:13
https://trac.sagemath.org/ticket/15483#comment:13
<ul>
<li><strong>commit</strong>
changed from <em>d34a77ab7abe4072349e10e0154a598da94b7c31</em> to <em>b662aba98ad4122a82fc135cf9b5dbf58de2ba0e</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=b662aba98ad4122a82fc135cf9b5dbf58de2ba0e"><span class="icon"></span>b662aba</a></td><td><code>add/fix doctests for simon_two_descent</code>
</td></tr></table>
TicketPeter BruinWed, 12 Feb 2014 15:00:10 GMTstatus changed
https://trac.sagemath.org/ticket/15483#comment:14
https://trac.sagemath.org/ticket/15483#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketPeter BruinWed, 12 Feb 2014 15:04:00 GMTupstream changed; author set
https://trac.sagemath.org/ticket/15483#comment:15
https://trac.sagemath.org/ticket/15483#comment:15
<ul>
<li><strong>upstream</strong>
changed from <em>Reported upstream. No feedback yet.</em> to <em>Workaround found; Bug reported upstream.</em>
</li>
<li><strong>author</strong>
set to <em>Peter Bruin</em>
</li>
</ul>
TicketJeroen DemeyerWed, 12 Feb 2014 22:09:52 GMT
https://trac.sagemath.org/ticket/15483#comment:16
https://trac.sagemath.org/ticket/15483#comment:16
<p>
I quite like the suggestion by Karim Belabas to use <code>nfsign()</code> together with <code>nfnewprec</code>. I think that's a lot better than the current patch, which is really just a hack.
</p>
<p>
Maybe you should ask Denis Simon what he thinks (perhaps with a proof-of-concept patch)? Ideally, he fixes his script "upstream".
</p>
TicketPeter BruinWed, 12 Feb 2014 22:36:44 GMT
https://trac.sagemath.org/ticket/15483#comment:17
https://trac.sagemath.org/ticket/15483#comment:17
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15483#comment:16" title="Comment 16">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
I quite like the suggestion by Karim Belabas to use <code>nfsign()</code> together with <code>nfnewprec</code>. I think that's a lot better than the current patch, which is really just a hack.
</p>
<p>
Maybe you should ask Denis Simon what he thinks (perhaps with a proof-of-concept patch)? Ideally, he fixes his script "upstream".
</p>
</blockquote>
<p>
I completely agree with all of this and hope that we will soon hear Denis's opinion (I e-mailed him and pari-dev simultaneously). The current patch is indeed fundamentally a hack and will hopefully be superseded by a better solution.
</p>
TicketJohn CremonaThu, 13 Feb 2014 09:34:08 GMT
https://trac.sagemath.org/ticket/15483#comment:18
https://trac.sagemath.org/ticket/15483#comment:18
<p>
Sorry that I have not had time to join this discussion -- I am very interested in the outcome.
</p>
<p>
It would be good to get Denis to adapt his script. He has done this in the past several times. I have found that it does not work for someone else to revise his script and send him the result; he want to do it himself and remain sole author. But a proof-of-concept patch might help him.
</p>
TicketJeroen DemeyerThu, 13 Feb 2014 09:43:12 GMT
https://trac.sagemath.org/ticket/15483#comment:19
https://trac.sagemath.org/ticket/15483#comment:19
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15483#comment:18" title="Comment 18">cremona</a>:
</p>
<blockquote class="citation">
<p>
It would be good to get Denis to adapt his script. He has done this in the past several times. I have found that it does not work for someone else to revise his script and send him the result; he want to do it himself and remain sole author. But a proof-of-concept patch might help him.
</p>
</blockquote>
<p>
Good to know. I also needed to make some changes to his scripts for the PARI-2.7 port (<a class="closed ticket" href="https://trac.sagemath.org/ticket/15767" title="#15767: enhancement: Upgrade PARI to 2.7.1 (closed: fixed)">#15767</a>).
</p>
TicketJeroen DemeyerMon, 24 Feb 2014 08:51:41 GMT
https://trac.sagemath.org/ticket/15483#comment:20
https://trac.sagemath.org/ticket/15483#comment:20
<p>
Did you get any answer from Denis Simon? If not, we should try to implement the <code>nfsign()</code> solution ourselves.
</p>
TicketPeter BruinMon, 24 Feb 2014 11:42:59 GMT
https://trac.sagemath.org/ticket/15483#comment:21
https://trac.sagemath.org/ticket/15483#comment:21
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15483#comment:20" title="Comment 20">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Did you get any answer from Denis Simon?
</p>
</blockquote>
<p>
Unfortunately not (yet).
</p>
<blockquote class="citation">
<p>
If not, we should try to implement the <code>nfsign()</code> solution ourselves.
</p>
</blockquote>
<p>
If you want to do it, go ahead, but to be honest, it seems a bit pointless to me at the moment.
</p>
<p>
Although I agreed above that the increase from 10 to 38 in the precision check was just a hack, there is actually a reason for the 38. (The following assumes a 64-bit word length.) For any bound <em>n</em> < 38 in this test, a 1-bit error in the result already has catastrophic consequences: a number that should be negative is taken to be a positive number with 64 bits of precision, due to the precision being only 1 bit, and that bit being affected by a round-off error). For <em>n</em> >= 38, the round-off errors have to accumulate to at least 65 bits of precision for the problem to occur (wrongly trusting the positivity of a 128-bit number). Of course that can happen, but it is extremely unlikely and I would be surprised if you could find any example.
</p>
TicketJeroen DemeyerMon, 24 Feb 2014 13:07:22 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/15483#comment:22
https://trac.sagemath.org/ticket/15483#comment:22
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Jeroen Demeyer</em>
</li>
</ul>
TicketVolker BraunThu, 27 Feb 2014 21:28:50 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/15483#comment:23
https://trac.sagemath.org/ticket/15483#comment:23
<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/15483-two_descent_precision</em> to <em>b662aba98ad4122a82fc135cf9b5dbf58de2ba0e</em>
</li>
</ul>
Ticket