bug in elliptic curve gens()

[rlmill]

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

Depends on #10735

CC: @adeines @JohnCremona @sagetrac-gagansekhon @sagetrac-weigandt @williamstein @categorie @robertwb

Component: elliptic curves

Author: Peter Bruin

Branch/Commit: 42c563c

Reviewer: Chris Wuthrich

Issue created by migration from https://trac.sagemath.org/ticket/10745

[JohnCremona]

comment:1

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

[JohnCremona]

comment:2

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.

[sagetrac-weigandt]

comment:4

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.

[chriswuthrich]

comment:5

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.

[chriswuthrich]

comment:6

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.

[chriswuthrich]

comment:8

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

[pjbruin]

comment:9

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?

[chriswuthrich]

comment:11

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.

[pjbruin]

comment:12

Replying to @categorie:

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()?

[chriswuthrich]

comment:13

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.

[pjbruin]

Dependencies: #10735

[pjbruin]

Author: Peter Bruin

[pjbruin]

comment:14

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

[pjbruin]

Commit: 318230a

[pjbruin]

Branch: u/pbruin/10745-elliptic_curve_gens

[sagetrac-git]

Changed commit from 318230a to 42c563c

[sagetrac-git]

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

42c563c

cache result of simon_two_descent over QQ

[pjbruin]

comment:16

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

[chriswuthrich]

comment:17

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.

[chriswuthrich]

comment:18

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.

[pjbruin]

comment:19

Replying to @categorie:

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

[chriswuthrich]

comment:20

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.

[pjbruin]

comment:21

Replying to @categorie:

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.

[chriswuthrich]

Reviewer: Chris Wuthrich

[chriswuthrich]

comment:22

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.

[pjbruin]

comment:23

Replying to @categorie:

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.

[chriswuthrich]

comment:24

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.

[pjbruin]

comment:25

Replying to @categorie:

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()
[]

[JohnCremona]

comment:26

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

[pjbruin]

comment:27

Replying to @pjbruin:

Replying to @categorie:

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.

[pjbruin]

comment:28

Replying to @JohnCremona:

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.

[vbraun]

Changed branch from u/pbruin/10745-elliptic_curve_gens to 42c563c