Opened 11 years ago
Closed 8 years ago
#10745 closed defect (fixed)
bug in elliptic curve gens()
Reported by:  rlm  Owned by:  cremona 

Priority:  major  Milestone:  
Component:  elliptic curves  Keywords:  
Cc:  aly.deines, cremona, gagansekhon, weigandt, was, wuthrich, robertwb  Merged in:  
Authors:  Peter Bruin  Reviewers:  Chris Wuthrich 
Report Upstream:  N/A  Work issues:  
Branch:  42c563c (Commits, GitHub, GitLab)  Commit:  42c563c4b4e834adb39d75b3b02e21ab1c3da372 
Dependencies:  #10735  Stopgaps: 
Description (last modified by )
[See #15608 for a list of open simon_two_descent tickets]
sage: a = [1, 0, 1, 1751, 31352] sage: F = EllipticCurve(a) sage: K.<d> = QuadraticField(5) sage: FK = EllipticCurve(K, a) sage: F.gens() [(52 : 111 : 1)] sage: FK.gens() []
This isn't very good, because the default in Sage is proof=True, so one would expect this to be a provable result (until reading the docs of course).
Over Q, if the result is not provable an error is raised or a warning is printed, depending on the proof
flag. This should be the same here.
Change History (29)
comment:1 Changed 11 years ago by
comment:2 Changed 11 years ago by
The output of simon_two_descent() for EK is
sage: FK.simon_two_descent() (1, 1, [])
which can be interpreted as follows: he computes the 2Selmer rank is 1, which gives a valid upper bound for the rank (=1). He fails to find points on 2coverings, so there are no points returned. *But* he uses the parity conjecture to increase the lower bound from 0 to 1.
So when we decide (in the simon_two_descent()) method) that the output is certain, we need to take this into account.
Secondly, the gens() function for curves over number fields is completely reckless:
lower,upper,gens = self.simon_two_descent(verbose=verbose,lim1=lim1,lim3=\ lim3,limtriv=limtriv,maxprob=maxprob,limbigprime=limbigprime) return gens
There is no caching, no checking of Proof, and worst of all, the gens which are returned have not been looked at at all. Just about all you can say about them is that they are points on the curve.
Who let that in? This function needs changing urgently.
comment:3 Changed 11 years ago by
 Cc wuthrich added
comment:4 Changed 11 years ago by
 Cc robertwb added
If we want to keep a gens() function for elliptic curves over number fields. We're going to need some functionality to check saturation of points over number fields. I'm ccing Robert Bradshaw because he's thought about this.
comment:5 Changed 8 years ago by
It seems that the second problem has disappeared in 6.0. I get now
sage: FK.gens(lim1=6) []
That still leaves 1).
Somehow, one should think that it would be best, if the curve remembered that it was defined over a smaller field and that it had found some points of infinite order already. In general, I think it is best if the algorithm would run through all subfield and search for points in there. ... But now I am dreaming.
comment:6 Changed 8 years ago by
I modified the docstring of gens in #13593 . It now says there that the function returns some points of infinite order. In fact Simon's script just gives back what it came across during the various ways to search for points. They are not lin. indep. for instance. And of course there is no guarantee it finds any.
Maybe this ticket should now be rewritten as:
Implement gens
correctly for elliptic curves over number fields. Extract from the points given by 2descent (in case it determines the rank) a set of linearly indep. point and then saturate the MordellWeil group.
comment:7 Changed 8 years ago by
 Description modified (diff)
comment:8 Changed 8 years ago by
comment:9 Changed 8 years ago by
 Description modified (diff)
 Status changed from new to needs_info
Given that the documentation no longer says that the points returned by gens()
are linearly independent or span a subgroup of full rank, this is technically not a bug anymore, but there is still the inconsistency with the similar function over Q. There seem to be three options:
 close this ticket as invalid or wontfix;
 use this ticket to print a warning or raise an error if
gens()
returns something other than a basis for a subgroup of full rank in the MordellWeil group;  rewrite this ticket with a more ambitious goal as in comment:6.
Any ideas?
comment:10 Changed 8 years ago by
 Description modified (diff)
comment:11 followup: ↓ 12 Changed 8 years ago by
I think 3) is covered in ticket #8829. So it does not really make sense to do duplicate it here. I don't think we should raise an error or a warning for a documented behaviour as in 2). So I would say:
either this ticket can be closed as in 1) in case the documentation is clear enough about the current behaviour or otherwise it should improve it.
or it is a suggestion to improve the gens function. It should run gens first in subfields (where it is much easier to run) and then put the resulting sets cleverly together.
comment:12 in reply to: ↑ 11 ; followup: ↓ 13 Changed 8 years ago by
Replying to wuthrich:
I think 3) is covered in ticket #8829. So it does not really make sense to do duplicate it here.
OK, I agree (I hadn't seen #8829).
I don't think we should raise an error or a warning for a documented behaviour as in 2).
In that case I think it would be good to explicitly say that this is different from the function gens()
for elliptic curves over Q. The documentation currently also says "Check rank()
or rank_bounds()
to verify the number of generators", which is somewhat misleading because even if E.rank() == len(E.gens())
nothing is guaranteed except that the points have infinite order, so you don't really verify anything by just comparing the two numbers.
So I would say:
either this ticket can be closed as in 1) in case the documentation is clear enough about the current behaviour or otherwise it should improve it.
The documentation can be improved in any case; even if we can do better in gens()
for some curves, we are certainly far away from always returning a basis for the MordellWeil group modulo torsion, so documentation improvements will not be made redundant by the other option:
or it is a suggestion to improve the gens function. It should run gens first in subfields (where it is much easier to run) and then put the resulting sets cleverly together.
There are quite a few things one could try, e.g.
 to find a suitable base field, start with the field generated by the coefficients of the Weierstrass model, and then possibly try to descend to a smaller field
 try to reduce the base field even more by finding an isogeny to an elliptic curve defined over a smaller field
 for a quadratic extension L/K and a curve E/L already defined over K, compute MW generators of E/K and of its twist by the extension L/K
How about just clarifying the documentation in this ticket and opening a new ticket for these actual improvements to gens()
?
comment:13 in reply to: ↑ 12 Changed 8 years ago by
How about just clarifying the documentation in this ticket and opening a new ticket for these actual improvements to
gens()
?
Yes, I agree that is the best to do. We can also make simon_two_descent
return only points of infinite order in the number field case, too. As it was noted in #10735.
comment:14 Changed 8 years ago by
 Branch set to u/pbruin/10745elliptic_curve_gens
 Commit set to 318230a2b970faf0abcc81729046061f01392dc1
 Dependencies set to #10735
 Status changed from needs_info to needs_review
OK, I made a branch doing what you suggested. The documentation is now hopefully clearer. Filtering out points of finite order is now always done directly after calling Simon's GP program. While I was at it, I removed the change to an integral model since this is not necessary (anymore?).
comment:15 Changed 8 years ago by
 Commit changed from 318230a2b970faf0abcc81729046061f01392dc1 to 42c563c4b4e834adb39d75b3b02e21ab1c3da372
Branch pushed to git repo; I updated commit sha1. New commits:
42c563c  cache result of simon_two_descent over QQ

comment:16 Changed 8 years ago by
Also implement caching of the result of simon_two_descent
over QQ by sharing more code between the various functions.
New commits:
42c563c  cache result of simon_two_descent over QQ

comment:17 Changed 8 years ago by
My first comment when looking at the modifications above is that I see that you changed ell.gp. Is this good ? It is very very likely that the next update of simon's scripts will forget to make this patchfix of a upstream file. Would it not be better to tell the author to change this in his version and we update our file ? This is a genuine question as I am not sure what is better. One thing to bear in mind is that it seems that Denis has not been very active on the bugs in his script recently.
comment:18 followup: ↓ 19 Changed 8 years ago by
If I understand correctly the old ell.gp returns 0 for the rank of the example in ell_number_field.py at line 2086, while the point in there is of infinite order. We should certainly report this upstream as a bug.
comment:19 in reply to: ↑ 18 Changed 8 years ago by
Replying to wuthrich:
If I understand correctly the old ell.gp returns 0 for the rank of the example in ell_number_field.py at line 2086, while the point in there is of infinite order. We should certainly report this upstream as a bug.
This is #16022, on which this ticket indirectly depends (explaining the edit of ell.gp
showing up in the branch).
comment:20 followup: ↓ 21 Changed 8 years ago by
That is not mentioned as dependency on the ticket though. How do I get to know quickly what the modifications to approve in this ticket are ? I always though that commit messages starting with the trac number were useful for that.
comment:21 in reply to: ↑ 20 Changed 8 years ago by
Replying to wuthrich:
That is not mentioned as dependency on the ticket though.
It is quite a long chain of dependencies: #10745 < #10735 < #9322 < #16009 < #16022 (plus #9322 < #16011). I'm not sure if explicitly listing all of these makes it clearer.
How do I get to know quickly what the modifications to approve in this ticket are ?
All dependencies get in via #10735, so one way to do it is to create a local branch for #10735 and type git diff color ticket/10735 ticket/10745
(replace ticket/10735
and ticket/10745
with the branch names you use).
I always though that commit messages starting with the trac number were useful for that.
Good point; usually I number the branch name, but it could indeed be useful to put the ticket number in the commit message as well.
comment:22 followup: ↓ 23 Changed 8 years ago by
 Reviewers set to Chris Wuthrich
 Status changed from needs_review to positive_review
OK, that was helpful.
All tests pass and I am happy with all modifications. Except there is one I am not certain about. You changed in gp_simon that the model is not necessarily changed to an integral model. I tried a few example and it seems to work even with nonintegral models. Why are you certain this will never cause a problem ?
Can I leave you to open a ticket for the other issue on gens ? I believe there is one for saturation, but I think we should open another one for the original problem posted in the question here.
comment:23 in reply to: ↑ 22 Changed 8 years ago by
Replying to wuthrich:
All tests pass and I am happy with all modifications.
Thanks for the review!
Except there is one I am not certain about. You changed in gp_simon that the model is not necessarily changed to an integral model. I tried a few example and it seems to work even with nonintegral models. Why are you certain this will never cause a problem ?
Denis Simon writes this in the documentation of ell.gp
:
La fonction bnfellrank() accepte toutes les courbes sous la forme [a1,a2,a3,a4,a6] Les coefficients peuvent etre entiers ou non.
One of the first things that the GP function bnfellrank()
does is indeed clearing denominators. (The specialised functions for the three possible 2torsion structures do require an integral model, but we don't call those directly.)
Can I leave you to open a ticket for the other issue on gens ? I believe there is one for saturation, but I think we should open another one for the original problem posted in the question here.
You mean for extracting a set of linearly independent points, or for the trick of looking over smaller fields first? I can open a ticket for each of those. The one for saturation is #8829.
comment:24 followup: ↓ 25 Changed 8 years ago by
Well, I guess saturation (using the height pairing anyway) should filter out the linearly dependent points too. I was rather thinking of the other issue. Maybe a simple thing would be to pass on the gens when using base_extend
. The more advanced "looking over smaller fields" seems too utopian.
comment:25 in reply to: ↑ 24 ; followup: ↓ 27 Changed 8 years ago by
Replying to wuthrich:
Well, I guess saturation (using the height pairing anyway) should filter out the linearly dependent points too.
Actually the current patch at #8829 requires the initial points to be linearly independent; it even has a doctest showing that it fails for linearly dependent points... It is probably better to fix this after #8829, though.
I was rather thinking of the other issue. Maybe a simple thing would be to pass on the gens when using
base_extend
. The more advanced "looking over smaller fields" seems too utopian.
OK, then I will open a ticket to fix at least the following (inspired by the original problem):
sage: E = EllipticCurve([1,0,1,1751,31352]) sage: K.<d>=QuadraticField(5) sage: E.gens() [(52 : 111 : 1)] sage: E.base_extend(K).gens() []
comment:26 followup: ↓ 28 Changed 8 years ago by
Well, whatever the documentation says about gens over number fields, users will assume that we are miracleworkers and hence that the gens are complete over the extension. The only situation where this is probably doable is for quadratic extensions, assuming that we can find gens for the twist. Somewhere there is code which, on given an elliptic curve over a quadratic fields when evaluating its gens function, tries to see if the curve is a basechange and if so uses this trick. I cannot remember of anyone implemented this well enough to have been let in...
comment:27 in reply to: ↑ 25 Changed 8 years ago by
comment:28 in reply to: ↑ 26 Changed 8 years ago by
Replying to cremona:
Somewhere there is code which, on given an elliptic curve over a quadratic fields when evaluating its gens function, tries to see if the curve is a basechange and if so uses this trick. I cannot remember of anyone implemented this well enough to have been let in...
I think this is part of the patch at #8829.
comment:29 Changed 8 years ago by
 Branch changed from u/pbruin/10745elliptic_curve_gens to 42c563c4b4e834adb39d75b3b02e21ab1c3da372
 Resolution set to fixed
 Status changed from positive_review to closed
I'm not sure that, when the gens() function was added over number fields at SD22, we thought it through very well. In particular, I don't think that Simon's code necessarily passes the "proof=True" criteria (but cannot be more specific). Except that the points it returns are points on the curve...