Activate

Saturation of Mordell-Weil 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 finitely-generated Abelian group.

The process of $p$-saturating a given set of points is implemented here. The naive algorithm simply checks all $(p^r-1)/(p-1)$ 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 in Plist.

OUTPUT:

(newPlist, exponent) where newPlist has the same length as Plist and spans the $p$-saturation of the span of Plist, which contains that span with index p**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,-1-2*i)
sage: full_p_saturation([8*P],2,verbose=True)
 --starting full 2-saturation
Points were not 2-saturated, 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 7-saturated and we gain index exponent 1. Running this example with verbose=True shows that it uses the code for when the reduction has p-rank 2 (which occurs for the reduction modulo $(16-5i)$), which uses the Weil pairing:

sage: full_p_saturation([P,Q+3*R,Q-4*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 in Plist.

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 with newP, the subgroup generated contains that generated by Plist with index $p$. Note that while proving the points $p$-saturated, the lin_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,-1-2*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 19-saturation 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 19-torsion modulo Fractional ideal (i + 14), projecting points
 --> [(184 : 27 : 1), (0 : 0 : 1), (196 : 1 : 1)]
 --rank is now 1
There is 19-torsion modulo Fractional ideal (i - 14), projecting points
 --> [(15 : 168 : 1), (0 : 0 : 1), (196 : 1 : 1)]
 --rank is now 2
There is 19-torsion 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 19-saturated
(True, {})

An example where the points are not 11-saturated:

sage: res = p_saturation([P+5*Q,P-6*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],P-6*Q,R],11)
(True, {})