Saturation of MordellWeil groups of elliptic curves over number fields¶
Points \(P_1\), \(\dots\), \(P_r\) in \(E(K)\), where \(E\) is an elliptic curve over a number field \(K\), are said to be \(p\)saturated if no linear combination \(\sum n_iP_i\) is divisible by \(p\) in \(E(K)\) except trivially when all \(n_i\) are multiples of \(p\). The points are said to be saturated if they are \(p\)saturated at all primes; this is always true for all but finitely many primes since \(E(K)\) is a finitelygenerated Abelian group.
The process of \(p\)saturating a given set of points is implemented
here. The naive algorithm simply checks all \((p^r1)/(p1)\)
projective combinations of the points, testing each to see if it can
be divided by \(p\). If this occurs then we replace one of the points
and continue. The function p_saturation()
does one step of
this, while full_p_saturation()
repeats until the points are
\(p\)saturated. A more sophisticated algorithm for \(p\)saturation is
implemented which is much more efficient for large \(p\) and \(r\), and
involves computing the reduction of the points modulo auxiliary primes
to obtain linear conditions modulo \(p\) which must be satisfied by the
coefficients \(a_i\) of any nontrivial relation. When the points are
already \(p\)saturated this sieving technique can prove their
saturation quickly.
The method saturation()
of the class EllipticCurve_number_field
applies full \(p\)saturation at any given set of primes, or can compute
a bound on the primes \(p\) at which the given points may not be
\(p\)saturated. This involves computing a lower bound for the
canonical height of points of infinite order, together with estimates
from the geometry of numbers.
AUTHORS:
 Robert Bradshaw
 John Cremona

sage.schemes.elliptic_curves.saturation.
full_p_saturation
(Plist, p, lin_combs={}, verbose=False)¶ Full \(p\)saturation of
Plist
.INPUT:
Plist
(list)  a list of independent points on one elliptic curve.p
(integer)  a prime number.lin_combs
(dict, default null)  a dict, possibly empty, with keys coefficient tuples and values the corresponding linear combinations of the points inPlist
.
OUTPUT:
(
newPlist
, exponent) wherenewPlist
has the same length asPlist
and spans the \(p\)saturation of the span ofPlist
, which contains that span with indexp**exponent
.EXAMPLES:
sage: from sage.schemes.elliptic_curves.saturation import full_p_saturation sage: E = EllipticCurve('389a') sage: K.<i> = QuadraticField(1) sage: EK = E.change_ring(K) sage: P = EK(1+i,12*i) sage: full_p_saturation([8*P],2,verbose=True) starting full 2saturation Points were not 2saturated, exponent was 3 ([(i + 1 : 2*i  1 : 1)], 3) sage: Q = EK(0,0) sage: R = EK(1,1) sage: full_p_saturation([P,Q,R],3) ([(i + 1 : 2*i  1 : 1), (0 : 0 : 1), (1 : 1 : 1)], 0)
An example where the points are not 7saturated and we gain index exponent 1. Running this example with verbose=True shows that it uses the code for when the reduction has prank 2 (which occurs for the reduction modulo \((165i)\)), which uses the Weil pairing:
sage: full_p_saturation([P,Q+3*R,Q4*R],7) ([(i + 1 : 2*i  1 : 1), (2869/676 : 154413/17576 : 1), (7095/502681 : 366258864/356400829 : 1)], 1)

sage.schemes.elliptic_curves.saturation.
p_saturation
(Plist, p, sieve=True, lin_combs={}, verbose=False)¶ Checks whether the list of points is \(p\)saturated.
INPUT:
Plist
(list)  a list of independent points on one elliptic curve.p
(integer)  a prime number.sieve
(boolean)  if True, use a sieve (when there are at least 2 points); otherwise test all combinations.lin_combs
(dict)  a dict, possibly empty, with keys coefficient tuples and values the corresponding linear combinations of the points inPlist
.
Note
The sieve is much more efficient when the points are saturated and the number of points or the prime are large.
OUTPUT:
Either (
True
,lin_combs
) if the points are \(p\)saturated, or (False
,i
,newP
) if they are not \(p\)saturated, in which case after replacing the i’th point withnewP
, the subgroup generated contains that generated byPlist
with index \(p\). Note that while proving the points \(p\)saturated, thelin_combs
dict may have been enlarged, so is returned.EXAMPLES:
sage: from sage.schemes.elliptic_curves.saturation import p_saturation sage: E = EllipticCurve('389a') sage: K.<i> = QuadraticField(1) sage: EK = E.change_ring(K) sage: P = EK(1+i,12*i) sage: p_saturation([P],2) (True, {}) sage: p_saturation([2*P],2) (False, 0, (i + 1 : 2*i  1 : 1)) sage: Q = EK(0,0) sage: R = EK(1,1) sage: p_saturation([P,Q,R],3) (True, {})
Here we see an example where 19saturation is proved, with the verbose flag set to True so that we can see what is going on:
sage: p_saturation([P,Q,R],19, verbose=True) Using sieve method to saturate... There is 19torsion modulo Fractional ideal (i + 14), projecting points > [(184 : 27 : 1), (0 : 0 : 1), (196 : 1 : 1)] rank is now 1 There is 19torsion modulo Fractional ideal (i  14), projecting points > [(15 : 168 : 1), (0 : 0 : 1), (196 : 1 : 1)] rank is now 2 There is 19torsion modulo Fractional ideal (2*i + 17), projecting points > [(156 : 275 : 1), (0 : 0 : 1), (292 : 1 : 1)] rank is now 3 Reached full rank: points were 19saturated (True, {})
An example where the points are not 11saturated:
sage: res = p_saturation([P+5*Q,P6*Q,R],11); res (False, 0, (5783311/14600041*i + 1396143/14600041 : 37679338314/55786756661*i + 3813624227/55786756661 : 1))
That means that the 0’th point may be replaced by the displayed point to achieve an index gain of 11:
sage: p_saturation([res[2],P6*Q,R],11) (True, {})