Opened 13 years ago

Last modified 5 years ago

#8829 closed enhancement

Saturation for MW-groups of elliptic curves over number fields. — at Version 21

Reported by: Robert Bradshaw Owned by: John Cremona
Priority: major Milestone: sage-8.1
Component: elliptic curves Keywords: saturation
Cc: Peter Bruin, Kiran Kedlaya Merged in:
Authors: Robert Bradshaw, John Cremona Reviewers: John Cremona
Report Upstream: N/A Work issues:
Branch: u/cremona/8829 (Commits, GitHub, GitLab) Commit: 0e1e35f624edb087d3fb1ddc21226fec7acfafad
Dependencies: #8828 Stopgaps:

Status badges

Description (last modified by John Cremona)

Implementation of saturation of points on elliptic curves over number fields. Originap 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.

Change History (22)

comment:1 Changed 13 years ago by Robert Bradshaw

Status: newneeds_review

Some dependance on #8828.

comment:2 Changed 13 years ago by John Cremona

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.

Changed 13 years ago by Robert Bradshaw

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

comment:3 in reply to:  2 Changed 13 years ago by Robert Bradshaw

Replying to cremona:

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?

comment:4 Changed 13 years ago by John Cremona

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.

comment:5 Changed 13 years ago by John Cremona

Authors: Robert Bradshaw
Reviewers: John Cremona
Status: needs_reviewneeds_work

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.

comment:6 Changed 13 years ago by Robert Bradshaw

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.

comment:7 in reply to:  6 Changed 13 years ago by John Cremona

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.

comment:8 Changed 12 years ago by John Cremona

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

comment:9 Changed 12 years ago by John Cremona

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

comment:10 Changed 10 years ago by David Roe

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

comment:11 Changed 10 years ago by John Cremona

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

comment:12 in reply to:  11 Changed 10 years ago by John Cremona

Replying to cremona:

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.

comment:13 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11sage-5.12

comment:14 Changed 9 years ago by John Cremona

Dependencies: #8828

comment:15 Changed 9 years ago by Nils Bruin

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

comment:16 Changed 9 years ago by For batch modifications

Milestone: sage-6.1sage-6.2

comment:17 Changed 9 years ago by Peter Bruin

Cc: Peter Bruin added

comment:18 Changed 9 years ago by For batch modifications

Milestone: sage-6.2sage-6.3

comment:19 Changed 8 years ago by For batch modifications

Milestone: sage-6.3sage-6.4

comment:20 Changed 7 years ago by John Cremona

I do not know why this was left drifting, but I really need it myself now so will look at it again, rebase on 6.8 and see what we can do. But I only have one day before a week off, so...

comment:21 Changed 7 years ago by John Cremona

Authors: Robert BradshawRobert Bradshaw, John Cremona
Branch: u/cremona/8829
Commit: 0e1e35f624edb087d3fb1ddc21226fec7acfafad
Description: modified (diff)
Keywords: saturation added

New commits:

be41e01first work on updating #9929 to a working branch (not done yet)
4b4fc21#8829: ell_height now passes its doctests...
0e1e35f#8829: refactored saturation; ell_number_field passes its doctests but more testing and tests needed...
Note: See TracTickets for help on using tickets.