Saturation for MW-groups of elliptic curves over number fields.

[robertwb]

Implementation of saturation of points on elliptic curves over number fields. Original patch by Robert Bradshaw in 2010, refactored and made into a git branch by John Cremona in 2015.

I also implemented the simple case of E.gens() for E(K) when E/Q and [K:Q] = 2.

CC: @pjbruin @kedlaya

Component: elliptic curves

Keywords: saturation

Author: Robert Bradshaw, John Cremona

Branch: ae6b11c

Reviewer: David Roe, Kiran Kedlaya, Frédéric Chapoton

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

[robertwb]

comment:1

Some dependance on #8828.

[JohnCremona]

comment:2

I have had a quick look and will go through this in more detail later (after #8828 is completed, probably). I spent a long time on my C++ implementation of this (over QQ but the algorithm is general) so am quite familiar with the details.

Here are two references you should give: [1] S. Siksek "Infinite descent on elliptic curves", Rocky Mountain J of M, Vol 25 No. 4 (1995), 1501-1538. [2] M. Prickett, "Saturation of Mordell-Weil groups of elliptic curves over number fields", U of Nottingham PhD thesis (2004), http://etheses.nottingham.ac.uk/52/.

Martin Prickett implemented this in Magma, but the code was very slow and hard to read so it never got incorporated into Magma releases.

Incidentally, it was for this that I implemented group structure for curves over GF(q) in the first place! In my C++ implementation I cache a lot of the information of this group structure so that when you do p-saturation for larger and larger p, the structures are already there. A good example is to take one of those curves of very high rank: I think I once successfully p-saturated the rank 24 curve at all p < 10^6 (the bound was totally out of reach, something like 10^100).

Another point which might be useful over number fields: it suffices to use degree one primes to reduce modulo.

[robertwb]

Attachment: 8829-ec-nf-sat.patch.gz

[robertwb]

comment:3

Replying to @JohnCremona:

I have had a quick look and will go through this in more detail later (after #8828 is completed, probably). I spent a long time on my C++ implementation of this (over QQ but the algorithm is general) so am quite familiar with the details.

Here are two references you should give: [1] S. Siksek "Infinite descent on elliptic curves", Rocky Mountain J of M, Vol 25 No. 4 (1995), 1501-1538. [2] M. Prickett, "Saturation of Mordell-Weil groups of elliptic curves over number fields", U of Nottingham PhD thesis (2004), http://etheses.nottingham.ac.uk/52/.

Ah, those look like good references to read too :).

Martin Prickett implemented this in Magma, but the code was very slow and hard to read so it never got incorporated into Magma releases.

Incidentally, it was for this that I implemented group structure for curves over GF(q) in the first place! In my C++ implementation I cache a lot of the information of this group structure so that when you do p-saturation for larger and larger p, the structures are already there.

The way I do it is consider many p at once, and for each curve over GF(q) I see which primes in my set it could help with, though this won't scale as far. I'm sure there's still lots of room for improvement.

A good example is to take one of those curves of very high rank: I think I once successfully p-saturated the rank 24 curve at all p < 10^6 (the bound was totally out of reach, something like 10^100).

That reminds me--I was wondering if there's any way to go from min(h(P)) to a bound on the regulator for rank > 1.

Another point which might be useful over number fields: it suffices to use degree one primes to reduce modulo.

Good point. Those get pretty rare for large degree number fields though, right?

[JohnCremona]

comment:4

You might also like to look at my C++ code which is in eclib, in src/qcurves. I can point to the right files if it is not clear. In case you wonder, "TLSS" stands for "Tate-Lichtenbaum-Samir_Siksek" since I use the TL map when the p-torsion in E(GF(q)) is not cyclic and Samir's original method when it is. Samir only used reduction modulo primes where p exactly divided the order, and in particular for which the reduction had cyclic p-part. But Martin and I discovered that this can fail when there is a p-isogeny. Here, fail means in the sense that there can exist points which are not multiples of p in E(QQ) but which map to zero in E(GF(q))/p for all q.

In MP's thesis he proves that this cannot happen if you use all q, or all but a finite number, or all but a finite number of degree 1 primes, .... some of these results we then found had been proved elsewhere (3 or 4 times, independently, within 3 or 4 years!). But it can happen if you leave out the q for which the quotient has non-cyclic p-part.

[JohnCremona]

comment:5

Patch applies fine to 4.4.1 and tests pass.

This functionality is badly needed!

We now have heights for points on curves defined over number_fields
but no associated regulator function. I suggest that the function
regulator_of_points() be moved up from ell_rational_field to
ell_number_field. This tcan then be called instead of the code in
lines 424-432 [line numbers are from the patched file, not the patch].

Line 439 uses a function self.height_function() which does not exist.
This block needs to be replaced by something sensible. If one has a lower bound on the height of non-torsion
points, then a bound on the index can be deduced from standard
geometry of numbers estimates. To get such a lower bound, see papers
of Cremona & Siksek (over Q) and Thongjunthug (over number fields) for
an algorithm which would need to be implemented. (Not hard over Q,
not much harder for totally real fields, quite a lot worse over fields
with a complex embedding). Until this is done, I don't think this
saturation function can allow maxprime==0.

In the rank one code: when large primes p (say, over 20!) are being
tested then the division_points code will be expensive since it
involves constructing the multiplication-by-p map. I would recommend
using a reduction strategy here just as in the general case. To check
p-saturation just find primes q such that #E(Fq) is divisible by p and
then see if the reduction of P mod q is a multiple of p. This will
almost always prove saturation very quickly. If it fails for several
(say 5) q then try to divide P by p; else use more q, and so on.
There is one theoretical drawback here: this strategy might fail if
there is a rational p-isogeny. Over Q, we know which p this might
happen for and I would first test for the existence of isogenies of
primes degree, and use the division test (as here) for any primes that
show up. Over number fields that's harder to deal with, but again we
can fall back on the division test to rpove that P cannot be divided
by p.

The function list_of_multiples(P,n) duplicated the generic function
multiples() which I wrote for just this sort of purpose!

I don't like the loop through all linear combinations for small
primes. Even with p=2 there are curves with 24 independent points out
there and 2^24 divisions is not nice to contemplate. If you want this
short cut, do it based on the size of p^r.

The main code with reduction etc looks fine to me (but I did not check
the logic rigorously).

The gens function for E(K) when E is defined over Q and [K:Q]=2 looks
fine. For a more general case we could always try using
simon_two_descent (followed by saturation). Trying such an examples
led me to:

sage: K.<a> = NumberField(x^2-2)
sage: E = EllipticCurve([a,0])
sage: P = E(0,0)
sage: P.has_finite_order()
True
sage: P.order()
2
sage: P.height()
0
sage: E.saturation([P], verbose=True, max_prime=5)
## infinite loop

This is caused as follows: The height matrix is [0] with det=0 but
reg / min(heights) is NaN so reg / min(heights) < 1e-6 is False!.
This will need fixing. At the very least, I would discard any points
of finite order before doing anything else with them. Then
min(heights) will never be 0.

Most of the above is easy to deal with. The hard part is computing a
suitable max_prime form a lower height bound on points. I suggest
that for now you make it compulsory to have a positive max_prime and
add a TODO.

[JohnCremona]

Author: Robert Bradshaw

[JohnCremona]

Reviewer: John Cremona

[robertwb]

comment:6

Thank you for all your input. self.height_function comes from #8828, though as you suggest we could make max_prime mandatory for now (and for rank > 1 once that goes in). That's a good point about large primes in the rank one case. I found the loop through all linear combinations to be much faster in practice for small primes, but the hard coded p == 2 case was left by accident, I meant to cap that on p^r as I did the others.

I probably won't fix and polish this up before finishing my thesis, but at the latest we should be able to get it done during the workshop at MSRI next month.

[JohnCremona]

comment:7

Replying to @robertwb:

Thank you for all your input. self.height_function comes from #8828, though as you suggest we could make max_prime mandatory for now (and for rank > 1 once that goes in). That's a good point about large primes in the rank one case. I found the loop through all linear combinations to be much faster in practice for small primes, but the hard coded p == 2 case was left by accident, I meant to cap that on p^r as I did the others.

I probably won't fix and polish this up before finishing my thesis, but at the latest we should be able to get it done during the workshop at MSRI next month.

OK -- looking forward to it! I'll take a look at #8828 by then as well.

[JohnCremona]

comment:8

Since rwb is now busy at Google, and I want this functionality, I am now implementing the changes I suggested above!

[JohnCremona]

comment:9

I made a separate ticket for the regulator functions. See #9372.

[roed314]

comment:10

How is this going John? It seems to have been awhile....

[JohnCremona]

comment:11

See #12509: until we can fix the height computation, saturation cannot be carried out properly. It's still on my to-do list though.

[JohnCremona]

comment:12

Replying to @JohnCremona:

See #12509: until we can fix the height computation, saturation cannot be carried out properly. It's still on my to-do list though.

#12509 is now up for review.

[JohnCremona]

Dependencies: #8828

[JohnCremona]

comment:75

I hope I got it right this time. The correct branch is public/8829 and I basically redid the edits I had already done this morning on the wrong branch.

---

Last 10 new commits:

9d66f35	trac 8829 fix for py3
a2f5023	Merge branch 'develop' into 8829
5b40a83	#8829: move p-saturation code to a new file and fix tests and imports
8abe3dc	#8829 fix some docstrings and remove some internal functions
847d276	#8829 fix a bug (typo n for p)
8c71585	#8829: put back a one-line internal function
7b3c188	#8829 fix docstring typos
d242123	#8829 correct spelling divison (*4)
63770c3	Merge branch 'develop' into 8829-new
37e2285	#8829 after review (2)

[JohnCremona]

Changed commit from cd2b023 to 37e2285

[JohnCremona]

Changed branch from u/cremona/8829 to public/8829

[roed314]

Reviewer: David Roe, Kiran Kedlaya, Frédéric Chapoton

[roed314]

comment:76

It looks like you've addressed everything. I ran all tests and checked that the loop in comment 5 is no longer a problem.

[JohnCremona]

comment:77

Thanks a lot! This ticket was opened in 2010, so I'll be celebrating. Now, if any of you would like to head on over to #22345...

[fchapoton]

comment:78

Very well, and I share your joy, but you introduced a .next(), which is not compatible with python3 (see patchbot plugin report). To be fixed in a later ticket, please.

[JohnCremona]

comment:79

That's a pity I thought the next () was rather neat. You can fix it here if you want.

[fchapoton]

comment:80

no, no, let us wait and do that later

[fchapoton]

comment:81

By the way, John, could you tell LMFDB people about #23671, please ?

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

ae6b11c

Changed .next() to next() in saturation.py for py3 compatibility

[sagetrac-git]

Changed commit from 37e2285 to ae6b11c

[kedlaya]

comment:83

Replying to @fchapoton:

no, no, let us wait and do that later

Isn't it just this one-line change? If so, no reason to postpone it...

[roed314]

comment:84

Looks good to me!

[vbraun]

Changed branch from public/8829 to ae6b11c

[jdemeyer]

Changed commit from ae6b11c to none

[jdemeyer]

comment:86

This is causing doctest failures: #23840.

[JohnCremona]

comment:87

I'm pretty certain it will be the usual nonsense of mathematically equivalent outputs. I'll look at #23840 and judge properly.