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_i{P}_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)

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 $\mathbf{Q}$

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

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 $\mathbf{Q}$:

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)

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)

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)

INPUT:

• Eq – an elliptic curve over a finite field

• Plist – list of points on $Eq$

• p – a prime number

OUTPUT:

A list of $r\le 2$ vectors in ${\mathbf{F}}_{p^n}$, the images of the points in $G\otimes {\mathbf{F}}_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 ${\mathbf{F}}_p$, otherwise use the Weil pairing to define two independent maps to ${\mathbf{F}}_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\cdot 7^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)

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=\mathbf{Q}(\alpha )$, where $amodq$ = 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)]

Make live