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: 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)}}

>>> 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)}}

Over a number field:

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)}}

>>> 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)}}
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: 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)

>>> 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)

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: 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)

>>> 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)
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: 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

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

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: 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

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

An example where the points are not 11-saturated:

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))

>>> 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))

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

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

>>> from sage.all import *
>>> saturator.p_saturation([res[Integer(1)], P - Integer(6)*Q, R], Integer(11))
False
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: E = EllipticCurve([0,0,1,-7,6])

>>> from sage.all import *
>>> E = EllipticCurve([Integer(0),Integer(0),Integer(1),-Integer(7),Integer(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: 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

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

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: 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)]

>>> 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.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: 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)])]

>>> 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)])]