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

• John Cremona

class sage.schemes.elliptic_curves.saturation.EllipticCurveSaturator(E, verbose=False)

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.

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

full_p_saturation(Plist, p)

Full $$p$$-saturation of Plist.

INPUT:

• Plist (list) – a 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: 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)


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)

p_saturation(Plist, p, sieve=True)

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.

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


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


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


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,P-6*Q,R],11)
False

sage.schemes.elliptic_curves.saturation.p_projections(Eq, Plist, p, debug=False)

INPUT:

• $$Eq$$ – An elliptic curve over a finite field.

• $$Plist$$ – a 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])


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


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

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=\QQ(\alpha)$$, where $$a \mod q =$$.

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