Opened 9 years ago

Closed 6 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) Commit: 42c563c4b4e834adb39d75b3b02e21ab1c3da372
Dependencies: #10735 Stopgaps:

Description (last modified by jdemeyer)

[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 9 years ago by cremona

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...

comment:2 Changed 9 years ago by cremona

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 2-Selmer rank is 1, which gives a valid upper bound for the rank (=1). He fails to find points on 2-coverings, 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 9 years ago by wuthrich

  • Cc wuthrich added

comment:4 Changed 9 years ago by weigandt

  • 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 6 years ago by wuthrich

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 6 years ago by wuthrich

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 2-descent (in case it determines the rank) a set of linearly indep. point and then saturate the Mordell-Weil group.

comment:7 Changed 6 years ago by cremona

  • Description modified (diff)

comment:8 Changed 6 years ago by wuthrich

I propose to close this after #13593 and #5153 as these two overlap a lot with the ticket here. Once they are closed. Then we open a new ticket enhancement for the saturation over number field (unless that exists already).

Last edited 6 years ago by wuthrich (previous) (diff)

comment:9 Changed 6 years ago by pbruin

  • 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:

  1. close this ticket as invalid or wontfix;
  2. 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 Mordell-Weil group;
  3. rewrite this ticket with a more ambitious goal as in comment:6.

Any ideas?

comment:10 Changed 6 years ago by jdemeyer

  • Description modified (diff)

comment:11 follow-up: Changed 6 years ago by wuthrich

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 ; follow-up: Changed 6 years ago by pbruin

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 Mordell-Weil 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 M-W 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 6 years ago by wuthrich

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 6 years ago by pbruin

  • Authors set to Peter Bruin
  • Branch set to u/pbruin/10745-elliptic_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 6 years ago by git

  • Commit changed from 318230a2b970faf0abcc81729046061f01392dc1 to 42c563c4b4e834adb39d75b3b02e21ab1c3da372

Branch pushed to git repo; I updated commit sha1. New commits:

42c563ccache result of simon_two_descent over QQ

comment:16 Changed 6 years ago by pbruin

Also implement caching of the result of simon_two_descent over QQ by sharing more code between the various functions.


New commits:

42c563ccache result of simon_two_descent over QQ

comment:17 Changed 6 years ago by wuthrich

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 patch-fix 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 follow-up: Changed 6 years ago by 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.

comment:19 in reply to: ↑ 18 Changed 6 years ago by pbruin

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 follow-up: Changed 6 years ago by wuthrich

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 6 years ago by pbruin

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 follow-up: Changed 6 years ago by wuthrich

  • 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 non-integral 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 6 years ago by pbruin

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 non-integral 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 2-torsion 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 follow-up: Changed 6 years ago by wuthrich

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 ; follow-up: Changed 6 years ago by pbruin

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 follow-up: Changed 6 years ago by cremona

Well, whatever the documentation says about gens over number fields, users will assume that we are miracle-workers and hence that the gens are complete over the extension. The only situation where this is probably do-able 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 base-change 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 6 years ago by pbruin

Replying to pbruin:

Replying to wuthrich:

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

This is now #16034.

comment:28 in reply to: ↑ 26 Changed 6 years ago by pbruin

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 base-change 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 6 years ago by vbraun

  • Branch changed from u/pbruin/10745-elliptic_curve_gens to 42c563c4b4e834adb39d75b3b02e21ab1c3da372
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.