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

class sage.schemes.elliptic_curves.saturation.EllipticCurveSaturator(E, verbose=False)[source]¶

Bases: SageObject

Class for saturating points on an elliptic curve over a number field.

INPUT:

E – an elliptic curve defined over a number field, or \(\QQ\)
verbose – boolean (default: False); verbosity flag

Note

This function is not normally called directly by users, who may access the data via methods of the EllipticCurve classes.

add_reductions(q)[source]¶

Add reduction data at primes above q if not already there.

INPUT:

q – a prime number not dividing the defining polynomial of self.__field

OUTPUT:

Returns nothing, but updates self._reductions dictionary for key q to a dict whose keys are the roots of the defining polynomial mod q and values tuples (nq, Eq) where Eq is an elliptic curve over \(GF(q)\) and nq its cardinality. If q divides the conductor norm or order discriminant nothing is added.

EXAMPLES:

Over \(\QQ\):

Sage

sage: from sage.schemes.elliptic_curves.saturation import EllipticCurveSaturator
sage: E = EllipticCurve('11a1')
sage: saturator = EllipticCurveSaturator(E)
sage: saturator._reductions
{}
sage: saturator.add_reductions(19)
sage: saturator._reductions
{19: {0: (20, Elliptic Curve defined by y^2 + y = x^3 + 18*x^2 + 9*x + 18
               over Finite Field of size 19)}}

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.saturation import EllipticCurveSaturator
>>> E = EllipticCurve('11a1')
>>> saturator = EllipticCurveSaturator(E)
>>> saturator._reductions
{}
>>> saturator.add_reductions(Integer(19))
>>> saturator._reductions
{19: {0: (20, Elliptic Curve defined by y^2 + y = x^3 + 18*x^2 + 9*x + 18
               over Finite Field of size 19)}}

Sage Live

from sage.schemes.elliptic_curves.saturation import EllipticCurveSaturator
E = EllipticCurve('11a1')
saturator = EllipticCurveSaturator(E)
saturator._reductions
saturator.add_reductions(19)
saturator._reductions

Over a number field:

Sage

sage: x = polygen(QQ);  K.<a> = NumberField(x^2 + 2)
sage: E = EllipticCurve(K, [0,1,0,a,a])
sage: from sage.schemes.elliptic_curves.saturation import EllipticCurveSaturator
sage: saturator = EllipticCurveSaturator(E)
sage: for q in primes(20):
....:     saturator.add_reductions(q)
sage: saturator._reductions
{2:  {},
 3:  {},
 5:  {},
 7:  {},
 11: {3:  (16, Elliptic Curve defined by y^2 = x^3 + x^2 + 3*x + 3
                over Finite Field of size 11),
      8:  (8,  Elliptic Curve defined by y^2 = x^3 + x^2 + 8*x + 8
                over Finite Field of size 11)},
 13: {},
 17: {7:  (20, Elliptic Curve defined by y^2 = x^3 + x^2 + 7*x + 7
                over Finite Field of size 17),
      10: (18, Elliptic Curve defined by y^2 = x^3 + x^2 + 10*x + 10
                over Finite Field of size 17)},
 19: {6:  (16, Elliptic Curve defined by y^2 = x^3 + x^2 + 6*x + 6
                over Finite Field of size 19),
      13: (12, Elliptic Curve defined by y^2 = x^3 + x^2 + 13*x + 13
                over Finite Field of size 19)}}

Python

>>> from sage.all import *
>>> x = polygen(QQ);  K = NumberField(x**Integer(2) + Integer(2), names=('a',)); (a,) = K._first_ngens(1)
>>> E = EllipticCurve(K, [Integer(0),Integer(1),Integer(0),a,a])
>>> from sage.schemes.elliptic_curves.saturation import EllipticCurveSaturator
>>> saturator = EllipticCurveSaturator(E)
>>> for q in primes(Integer(20)):
...     saturator.add_reductions(q)
>>> saturator._reductions
{2:  {},
 3:  {},
 5:  {},
 7:  {},
 11: {3:  (16, Elliptic Curve defined by y^2 = x^3 + x^2 + 3*x + 3
                over Finite Field of size 11),
      8:  (8,  Elliptic Curve defined by y^2 = x^3 + x^2 + 8*x + 8
                over Finite Field of size 11)},
 13: {},
 17: {7:  (20, Elliptic Curve defined by y^2 = x^3 + x^2 + 7*x + 7
                over Finite Field of size 17),
      10: (18, Elliptic Curve defined by y^2 = x^3 + x^2 + 10*x + 10
                over Finite Field of size 17)},
 19: {6:  (16, Elliptic Curve defined by y^2 = x^3 + x^2 + 6*x + 6
                over Finite Field of size 19),
      13: (12, Elliptic Curve defined by y^2 = x^3 + x^2 + 13*x + 13
                over Finite Field of size 19)}}

Sage Live

x = polygen(QQ);  K.<a> = NumberField(x^2 + 2)
E = EllipticCurve(K, [0,1,0,a,a])
from sage.schemes.elliptic_curves.saturation import EllipticCurveSaturator
saturator = EllipticCurveSaturator(E)
for q in primes(20):
    saturator.add_reductions(q)
saturator._reductions

full_p_saturation(Plist, p)[source]¶

Full \(p\)-saturation of Plist.

INPUT:

Plist – list of independent points on one elliptic curve
p – integer; a prime number

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

sage: from sage.schemes.elliptic_curves.saturation import EllipticCurveSaturator
sage: E = EllipticCurve('389a')
sage: K.<i> = QuadraticField(-1)
sage: EK = E.change_ring(K)
sage: P = EK(1 + i, -1 - 2*i)
sage: saturator = EllipticCurveSaturator(EK, verbose=True)
sage: saturator.full_p_saturation([8*P], 2)
 --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: saturator = EllipticCurveSaturator(EK, verbose=False)
sage: saturator.full_p_saturation([P, Q, R], 3)
([(i + 1 : -2*i - 1 : 1), (0 : 0 : 1), (-1 : 1 : 1)], 0)

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.saturation import EllipticCurveSaturator
>>> E = EllipticCurve('389a')
>>> K = QuadraticField(-Integer(1), names=('i',)); (i,) = K._first_ngens(1)
>>> EK = E.change_ring(K)
>>> P = EK(Integer(1) + i, -Integer(1) - Integer(2)*i)
>>> saturator = EllipticCurveSaturator(EK, verbose=True)
>>> saturator.full_p_saturation([Integer(8)*P], Integer(2))
 --starting full 2-saturation
Points were not 2-saturated, exponent was 3
([(i + 1 : -2*i - 1 : 1)], 3)

>>> Q = EK(Integer(0), Integer(0))
>>> R = EK(-Integer(1), Integer(1))
>>> saturator = EllipticCurveSaturator(EK, verbose=False)
>>> saturator.full_p_saturation([P, Q, R], Integer(3))
([(i + 1 : -2*i - 1 : 1), (0 : 0 : 1), (-1 : 1 : 1)], 0)

Sage Live

from sage.schemes.elliptic_curves.saturation import EllipticCurveSaturator
E = EllipticCurve('389a')
K.<i> = QuadraticField(-1)
EK = E.change_ring(K)
P = EK(1 + i, -1 - 2*i)
saturator = EllipticCurveSaturator(EK, verbose=True)
saturator.full_p_saturation([8*P], 2)
Q = EK(0, 0)
R = EK(-1, 1)
saturator = EllipticCurveSaturator(EK, verbose=False)
saturator.full_p_saturation([P, Q, R], 3)

An example where the points are not 7-saturated and we gain index exponent 1. Running this example with verbose=True would show 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

sage: saturator.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)

Python

>>> from sage.all import *
>>> saturator.full_p_saturation([P, Q + Integer(3)*R, Q - Integer(4)*R], Integer(7))
([(i + 1 : -2*i - 1 : 1),
  (2869/676 : 154413/17576 : 1),
  (-7095/502681 : -366258864/356400829 : 1)], 1)

Sage Live

saturator.full_p_saturation([P, Q + 3*R, Q - 4*R], 7)

p_saturation(Plist, p, sieve=True)[source]¶

Checks whether the list of points is \(p\)-saturated.

INPUT:

Plist – 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

Note

The sieve is much more efficient when the points are saturated and the number of points or the prime are large.

OUTPUT:

Either False if the points are \(p\)-saturated, or (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\).

EXAMPLES:

Sage

sage: from sage.schemes.elliptic_curves.saturation import EllipticCurveSaturator
sage: E = EllipticCurve('389a')
sage: K.<i> = QuadraticField(-1)
sage: EK = E.change_ring(K)
sage: P = EK(1 + i, -1 - 2*i)
sage: saturator = EllipticCurveSaturator(EK)
sage: saturator.p_saturation([P], 2)
False
sage: saturator.p_saturation([2*P], 2)
(0, (i + 1 : -2*i - 1 : 1))

sage: Q = EK(0, 0)
sage: R = EK(-1, 1)
sage: saturator.p_saturation([P, Q, R], 3)
False

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.saturation import EllipticCurveSaturator
>>> E = EllipticCurve('389a')
>>> K = QuadraticField(-Integer(1), names=('i',)); (i,) = K._first_ngens(1)
>>> EK = E.change_ring(K)
>>> P = EK(Integer(1) + i, -Integer(1) - Integer(2)*i)
>>> saturator = EllipticCurveSaturator(EK)
>>> saturator.p_saturation([P], Integer(2))
False
>>> saturator.p_saturation([Integer(2)*P], Integer(2))
(0, (i + 1 : -2*i - 1 : 1))

>>> Q = EK(Integer(0), Integer(0))
>>> R = EK(-Integer(1), Integer(1))
>>> saturator.p_saturation([P, Q, R], Integer(3))
False

Sage Live

from sage.schemes.elliptic_curves.saturation import EllipticCurveSaturator
E = EllipticCurve('389a')
K.<i> = QuadraticField(-1)
EK = E.change_ring(K)
P = EK(1 + i, -1 - 2*i)
saturator = EllipticCurveSaturator(EK)
saturator.p_saturation([P], 2)
saturator.p_saturation([2*P], 2)
Q = EK(0, 0)
R = EK(-1, 1)
saturator.p_saturation([P, Q, R], 3)

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

sage: saturator = EllipticCurveSaturator(EK, verbose=True)
sage: saturator.p_saturation([P, Q, R], 19)
Using sieve method to saturate...
E has 19-torsion over Finite Field of size 197, projecting points
--> [(15 : 168 : 1), (0 : 0 : 1), (196 : 1 : 1)]
--rank is now 1
E has 19-torsion over Finite Field of size 197, projecting points
--> [(184 : 27 : 1), (0 : 0 : 1), (196 : 1 : 1)]
--rank is now 2
E has 19-torsion over Finite Field of size 293, projecting points
--> [(139 : 16 : 1), (0 : 0 : 1), (292 : 1 : 1)]
 --rank is now 3
Reached full rank: points were 19-saturated
False

Python

>>> from sage.all import *
>>> saturator = EllipticCurveSaturator(EK, verbose=True)
>>> saturator.p_saturation([P, Q, R], Integer(19))
Using sieve method to saturate...
E has 19-torsion over Finite Field of size 197, projecting points
--> [(15 : 168 : 1), (0 : 0 : 1), (196 : 1 : 1)]
--rank is now 1
E has 19-torsion over Finite Field of size 197, projecting points
--> [(184 : 27 : 1), (0 : 0 : 1), (196 : 1 : 1)]
--rank is now 2
E has 19-torsion over Finite Field of size 293, projecting points
--> [(139 : 16 : 1), (0 : 0 : 1), (292 : 1 : 1)]
 --rank is now 3
Reached full rank: points were 19-saturated
False

Sage Live

saturator = EllipticCurveSaturator(EK, verbose=True)
saturator.p_saturation([P, Q, R], 19)

An example where the points are not 11-saturated:

Sage

sage: saturator = EllipticCurveSaturator(EK, verbose=False)
sage: res = saturator.p_saturation([P + 5*Q, P - 6*Q, R], 11); res
(0, (-5783311/14600041*i + 1396143/14600041
     : 37679338314/55786756661*i + 3813624227/55786756661 : 1))

Python

>>> from sage.all import *
>>> saturator = EllipticCurveSaturator(EK, verbose=False)
>>> res = saturator.p_saturation([P + Integer(5)*Q, P - Integer(6)*Q, R], Integer(11)); res
(0, (-5783311/14600041*i + 1396143/14600041
     : 37679338314/55786756661*i + 3813624227/55786756661 : 1))

Sage Live

saturator = EllipticCurveSaturator(EK, verbose=False)
res = saturator.p_saturation([P + 5*Q, P - 6*Q, R], 11); res

That means that the 0’th point may be replaced by the displayed point to achieve an index gain of 11:

Sage

sage: saturator.p_saturation([res[1], P - 6*Q, R], 11)
False

Python

>>> from sage.all import *
>>> saturator.p_saturation([res[Integer(1)], P - Integer(6)*Q, R], Integer(11))
False

Sage Live

saturator.p_saturation([res[1], P - 6*Q, R], 11)

sage.schemes.elliptic_curves.saturation.p_projections(Eq, Plist, p, debug=False)[source]¶

INPUT:

Eq – an elliptic curve over a finite field
Plist – list of points on \(Eq\)
p – a prime number

OUTPUT:

A list of \(r\le2\) vectors in \(\GF{p^n}\), the images of the points in \(G \otimes \GF{p}\), where \(r\) is the number of vectors is the \(p\)-rank of \(Eq\).

ALGORITHM:

First project onto the \(p\)-primary part of \(Eq\). If that has \(p\)-rank 1 (i.e. is cyclic), use discrete logs there to define a map to \(\GF{p}\), otherwise use the Weil pairing to define two independent maps to \(\GF{p}\).

EXAMPLES:

This curve has three independent rational points:

Sage

sage: E = EllipticCurve([0,0,1,-7,6])

Python

>>> from sage.all import *
>>> E = EllipticCurve([Integer(0),Integer(0),Integer(1),-Integer(7),Integer(6)])

Sage Live

E = EllipticCurve([0,0,1,-7,6])

We reduce modulo \(409\) where its order is \(3^2\cdot7^2\); the \(3\)-primary part is non-cyclic while the \(7\)-primary part is cyclic of order \(49\):

Sage

sage: F = GF(409)
sage: EF = E.change_ring(F)
sage: G = EF.abelian_group()
sage: G
Additive abelian group isomorphic to Z/147 + Z/3
 embedded in Abelian group of points on Elliptic Curve
  defined by y^2 + y = x^3 + 402*x + 6 over Finite Field of size 409
sage: G.order().factor()
3^2 * 7^2

Python

>>> from sage.all import *
>>> F = GF(Integer(409))
>>> EF = E.change_ring(F)
>>> G = EF.abelian_group()
>>> G
Additive abelian group isomorphic to Z/147 + Z/3
 embedded in Abelian group of points on Elliptic Curve
  defined by y^2 + y = x^3 + 402*x + 6 over Finite Field of size 409
>>> G.order().factor()
3^2 * 7^2

Sage Live

F = GF(409)
EF = E.change_ring(F)
G = EF.abelian_group()
G
G.order().factor()

We construct three points and project them to the \(p\)-primary parts for \(p=2,3,5,7\), yielding 0,2,0,1 vectors of length 3 modulo \(p\) respectively. The exact vectors output depend on the computed generators of \(G\):

Sage

sage: Plist = [EF([-2,3]), EF([0,2]), EF([1,0])]
sage: from sage.schemes.elliptic_curves.saturation import p_projections
sage: [(p, p_projections(EF, Plist, p)) for p in primes(11)]  # random
[(2, []), (3, [(0, 2, 2), (2, 2, 1)]), (5, []), (7, [(5, 1, 1)])]
sage: [(p, len(p_projections(EF, Plist, p))) for p in primes(11)]
[(2, 0), (3, 2), (5, 0), (7, 1)]

Python

>>> from sage.all import *
>>> Plist = [EF([-Integer(2),Integer(3)]), EF([Integer(0),Integer(2)]), EF([Integer(1),Integer(0)])]
>>> from sage.schemes.elliptic_curves.saturation import p_projections
>>> [(p, p_projections(EF, Plist, p)) for p in primes(Integer(11))]  # random
[(2, []), (3, [(0, 2, 2), (2, 2, 1)]), (5, []), (7, [(5, 1, 1)])]
>>> [(p, len(p_projections(EF, Plist, p))) for p in primes(Integer(11))]
[(2, 0), (3, 2), (5, 0), (7, 1)]

Sage Live

Plist = [EF([-2,3]), EF([0,2]), EF([1,0])]
from sage.schemes.elliptic_curves.saturation import p_projections
[(p, p_projections(EF, Plist, p)) for p in primes(11)]  # random
[(p, len(p_projections(EF, Plist, p))) for p in primes(11)]

sage.schemes.elliptic_curves.saturation.reduce_mod_q(x, amodq)[source]¶

The reduction of x modulo the prime ideal defined by amodq.

INPUT:

x – an element of a number field \(K\)
amodq – an element of \(GF(q)\) which is a root mod \(q\) of the defining polynomial of \(K\). This defines a degree 1 prime ideal \(Q=(q,\alpha-a)\) of \(K=\QQ(\alpha)\), where \(a \bmod q\) = amodq.

OUTPUT: the image of x in the residue field of \(K\) at the prime \(Q\)

EXAMPLES:

Sage

sage: from sage.schemes.elliptic_curves.saturation import reduce_mod_q
sage: x = polygen(QQ)
sage: pol = x^3 - x^2 - 3*x + 1
sage: K.<a> = NumberField(pol)
sage: [(q, [(amodq, reduce_mod_q(1 - a + a^4, amodq))
....:       for amodq in sorted(pol.roots(GF(q), multiplicities=False))])
....:  for q in primes(50, 70)]
[(53, []),
 (59, [(36, 28)]),
 (61, [(40, 35)]),
 (67, [(10, 8), (62, 28), (63, 60)])]

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.saturation import reduce_mod_q
>>> x = polygen(QQ)
>>> pol = x**Integer(3) - x**Integer(2) - Integer(3)*x + Integer(1)
>>> K = NumberField(pol, names=('a',)); (a,) = K._first_ngens(1)
>>> [(q, [(amodq, reduce_mod_q(Integer(1) - a + a**Integer(4), amodq))
...       for amodq in sorted(pol.roots(GF(q), multiplicities=False))])
...  for q in primes(Integer(50), Integer(70))]
[(53, []),
 (59, [(36, 28)]),
 (61, [(40, 35)]),
 (67, [(10, 8), (62, 28), (63, 60)])]

Sage Live

from sage.schemes.elliptic_curves.saturation import reduce_mod_q
x = polygen(QQ)
pol = x^3 - x^2 - 3*x + 1
K.<a> = NumberField(pol)
[(q, [(amodq, reduce_mod_q(1 - a + a^4, amodq))
      for amodq in sorted(pol.roots(GF(q), multiplicities=False))])
 for q in primes(50, 70)]