Opened 14 years ago
Closed 9 years ago
#5153 closed defect (fixed)
bug in simon_two_descent for elliptic curves
Reported by:  William Stein  Owned by:  

Priority:  major  Milestone:  sage6.1 
Component:  elliptic curves  Keywords:  simon_two_descent 
Cc:  Merged in:  
Authors:  Chris Wuthrich  Reviewers:  John Cremona 
Report Upstream:  N/A  Work issues:  
Branch:  u/wuthrich/ticket/5153 (Commits, GitHub, GitLab)  Commit:  ad2ced2b14236b9881121c47eb6ee0f20144d5dd 
Dependencies:  #13593  Stopgaps: 
Description (last modified by )
[See #15608 for a list of open simon_two_descent tickets]
We have
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)])
The documentation for simon_two_descent says that the output of Simon 2descent is
OUTPUT: integer  "probably" the rank of self integer  the 2rank of the Selmer group list  list of independent points on the curve.
Our curve does have rank 3, but the output list above contains *five* points, so they can't be independent!
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.
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.
Change History (27)
comment:1 Changed 14 years ago by
comment:2 followup: 5 Changed 14 years ago by
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.
I know how the first happens (since it is doing a descent via 2isogeny).
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 #360 !
comment:3 Changed 13 years ago by
Component:  number theory → elliptic curves 

Owner:  changed from William Stein to David Loeffler 
comment:4 Changed 13 years ago by
Owner:  David Loeffler deleted 

comment:5 Changed 13 years ago by
Report Upstream:  → N/A 

Replying to cremona:
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 #360 !
I am not sure that using heights is the best way to get independence if you are doing a 2descent anyway. The easier thing to do would be to just report back a set of points that minimally generate the 2selmer group (or at least minimally generate the part of the 2selmer 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 MordellWeil group. I think it's highly unlikely that that would happen.
comment:6 followup: 8 Changed 13 years ago by
I am not sure that using heights is the best way to get independence
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.
comment:7 Changed 13 years ago by
Good point  the reference is On the computation of MordellWeil and 2Selmer Groups of Elliptic Curves. Rocky Mountain Journal of Mathematics (2002) vol. 32, no. 3, pp.953967. 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.
comment:8 followup: 9 Changed 13 years ago by
Replying to was:
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.
And those same images can also yield information on psaturation of the group generated by the given points inside the MordellWeil group (just as an independence proof via 2Selmer groups also gives 2saturation) This starts to sound like a nice student project.
comment:9 Changed 13 years ago by
Replying to nbruin:
Replying to was:
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.
And those same images can also yield information on psaturation of the group generated by the given points inside the MordellWeil group (just as an independence proof via 2Selmer groups also gives 2saturation) This starts to sound like a nice student project.
It was! The thesis of my student Martin Prickett was about saturating MordellWeil groups this way, and he implemented it in Magma. See http://www.warwick.ac.uk/staff/J.E.Cremona/theses/index.html . I have Martin's magma code but it is not easy to use. Hence the project still remains, namely to rewrite all that.
comment:10 followup: 11 Changed 13 years ago by
the numbers 3,4 which are supposed to be lower and upper bounds on the rank are wrong and should be 3,3.
The numbers 3,4, are correct. G has a point of order 2 over its base feild, so the 2rank of the 2Selmer group is 4. However, an error like the one you're describing does occur with 438e1 over Q.
comment:11 Changed 13 years ago by
Replying to weigandt:
the numbers 3,4 which are supposed to be lower and upper bounds on the rank are wrong and should be 3,3.
The numbers 3,4, are correct. G has a point of order 2 over its base feild, so the 2rank of the 2Selmer group is 4. However, an error like the one you're describing does occur with 438e1 over Q.
Do you mean 438e1 over Q? #torsion=2 and rank=0 but the first descent via 2isogeny gives a rank upper bound of 2. If the rank were 2 then the 2selmer rank would be 3. two_descent_simon() gives lower bound of 0 and 3 for the rank of the 2Selmer group. That last one is clearly wrong. I think it is similar to the problem my 2descent 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 2Selmer rank.
We should correct the docstring of two_descent_simon, and I will tell Simon that his documentation is incorrect.
comment:12 Changed 13 years ago by
See #6955 for the updating of Simon's scripts, which I am now testing.
comment:13 Changed 12 years ago by
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.
comment:14 Changed 9 years ago by
Milestone:  sage5.11 → sage5.12 

comment:15 Changed 9 years ago by
Keywords:  simon_two_descent added 

comment:16 Changed 9 years ago by
Authors:  → Chris Wuthrich 

Dependencies:  → #13593 
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 #11372.
So we want simon_two_descent (over the rationals of number fields) to return three things
 A proven lower bound for the rank
 The rank of the 2Selmer group (this is an upper bound but not sharp in general)
 A list of points.
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 #13593. So here I modify the function over rationals.
Over Q, this function then also saturates these points and, if there are sufficiently many, sets them for E.gens()
.
That is what my proposed changes in the forthcoming commit will do.
Now, there are related issues, but they don't belong to this ticket really. The curve 438e1 gives the wrong 2Selmer and that is #10735. 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 #11005) and has plenty of other issues (#11041).
The bug introduced by #11372: 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.
comment:17 Changed 9 years ago by
Branch:  → u/wuthrich/ticket/5153 

Modified:  Dec 28, 2013, 4:29:56 PM → Dec 28, 2013, 4:29:56 PM 
comment:18 Changed 9 years ago by
Commit:  → c24c2b3b74260feb1d32c3ee2eaf0d7c2590ab57 

Status:  new → needs_review 
New commits:
c24c2b3  Trac 5153: Furhter modifications to the documentation

5dc87b8  Merge branch 'u/wuthrich/ticket/13593' of git://trac.sagemath.org/sage into ticket/5153

e5e42b8  Trac 5153: Filter out the 2torsion from the points returned by Simon's 2descent.

b1550dc  Trac 13593: Do not put torsion points into gens.

9a069c7  Trac #13593: ranks of elliptic curves over number fields

comment:19 Changed 9 years ago by
Commit:  c24c2b3b74260feb1d32c3ee2eaf0d7c2590ab57 → c3c480d23c265ddb93f8f58ab79233dcfe8ea0fa 

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

comment:21 Changed 9 years ago by
I am worried by the documentation sentence
To obtain a list of generators, use E.gens() after this.
since the only situation in which E.gens()
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 mwrank
. So it is a bit misleading?
comment:22 Changed 9 years ago by
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.
comment:23 Changed 9 years ago by
I suggest just deleting "after this". We can revisit this once we have put in independencechecking over number fields (which is separate from and rather easier than saturating). If you do that, I'll give it a positive review!
comment:24 Changed 9 years ago by
Commit:  c3c480d23c265ddb93f8f58ab79233dcfe8ea0fa → ad2ced2b14236b9881121c47eb6ee0f20144d5dd 

Branch pushed to git repo; I updated commit sha1. New commits:
ad2ced2  Trac #5153: small change in documentation.

comment:26 Changed 9 years ago by
Reviewers:  → John Cremona 

Status:  needs_review → positive_review 
comment:27 Changed 9 years ago by
Resolution:  → fixed 

Status:  positive_review → closed 
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.