Opened 11 years ago

Closed 8 years ago

# bug in elliptic curve gens()

Reported by: Owned by: rlm cremona major elliptic curves aly.deines, cremona, gagansekhon, weigandt, was, wuthrich, robertwb Peter Bruin Chris Wuthrich N/A 42c563c 42c563c4b4e834adb39d75b3b02e21ab1c3da372 #10735

[See #15608 for a list of open simon_two_descent tickets]

```sage: a = [1, 0, 1, -1751, -31352]
sage: F = EllipticCurve(a)
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.

### comment:1 Changed 11 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 11 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:4 Changed 11 years ago by weigandt

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

• Description modified (diff)

### comment:8 Changed 8 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 8 years ago by wuthrich (previous) (diff)

### comment:9 Changed 8 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 8 years ago by jdemeyer

• Description modified (diff)

### comment:11 follow-up: ↓ 12 Changed 8 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: ↓ 13 Changed 8 years ago by pbruin

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 8 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 8 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 8 years ago by git

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

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 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: ↓ 19 Changed 8 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 8 years ago by pbruin

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: ↓ 21 Changed 8 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 8 years ago by pbruin

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: ↓ 23 Changed 8 years ago by wuthrich

• Reviewers set to Chris Wuthrich
• Status changed from needs_review to positive_review

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

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: ↓ 25 Changed 8 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: ↓ 27 Changed 8 years ago by pbruin

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: E.gens()
[(52 : 111 : 1)]
sage: E.base_extend(K).gens()
[]
```

### comment:26 follow-up: ↓ 28 Changed 8 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 8 years ago by pbruin

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.