The Torsion subgroup of an Elliptic Curve
November 15th, 2006One of the central results in the study of Elliptic curves is the Mordell-Weil theorem, which asserts that the group E(K) is finitely generated. Thus it consists of a finite part- the torsion subgroup - and a free abelian part, the rank of which is notoriously difficult to compute. However, the torsion subgroup is relatively accessible, and this is something I’ve been playing with for a while. It covers a range of techniques and ideas and attempting a concrete implementation in Maple has helped considerably in my understanding of those, even if it is effectively reinventing the wheel given the existence of John Cremona’s Algorithms for elliptic curves. The procedures themselves and worked examples are after the cut; first, some theory.
Mazur’s Theorem
Let E/Q be an elliptic curve. Then the torsion subgroup Etors(Q) is one of the following fifteen groups:
Z/nZ for 1≤n≤10 or n=12;
Z/2Z X Z/2nZ 1≤n≤4.Further, each of these groups does occur as an Etors(Q).
This result is particularly handy as it allows for an experimental approach to be taken, gathering enough computational evidence to determine which form the torsion subgroup takes; knowledge of the order of points being especially useful. For instance, the presence of an order 7 element instantly shows that Etors(Q) is Z/7Z. Better still, there are results which aid in finding such points:
Nagell-Lutz Theorem
Let E/Q be an elliptic curve of the form
(that is, with the usual labelling of coefficients, a_1=a_3=0) with a,b,c integers. If P an element of E(Q) has finite order then x(P), y(P) are also integers.
Further, For such a point either y(P)=0 or y(P) divides
Hence for such curves it is sufficient to look for integer points; and only finitely many such points are suitable candidates for being torsion points.
Good and Bad Reduction
What of Elliptic curves not in the above form? It is possible to bound the number of torsion elements (and generate candidates) by working over finite fields (which I’ve coincidentally considered before). Save for finitely many primes of bad reduction - those which divide the discriminant of the elliptic curve - it transpires that the torsion subgroup maps injectively to E(Fp). For small primes, this is readily found without anything more sophisticated than brute force. Testing a number of primes can give an upper bound whilst naive searches for integer points can provide a lower bound: appealing again to Mazur’s theorem then usually settles the question.
Procedures
I’ve bundled together various Maple procedures based on these ideas as torsion_tools.mpl; they require gla.mpl. Various number theory subprocedures are included to make it all work (the numtheory package is invoked as well), but the following procedures should be the only ones you’re likely to need to work with directly.
ellorder(point)
gla.mpl comes with a procedure, modgetorder for calculating the order of a point when working modulo a prime; ellorder should now always be used instead. When working on gla, I’d been aware of the possibility of torsion points in non-finite fields, but didn’t know of any good way to ensure that a point was genuinely of infinite rather than very large order. However, due to the Nagell-Lutz result this is now easy: if any multiple of the point is non-integral, it cannot be a torsion point (since the multiple of a torsion point is a torsion point, and they have integral co-ordinates). Better still, Mazur’s theorem ensures that the maximum order of a torsion point is 12, so simply testing multiples will be fast. Thus ellorder performs repeated addition until either the group identity or a non-integral point is found, and (along with a test for the group identity as input) is therefore suitable regardless of whether you are working in a finite field. I’m keeping modgetorder around so that my earlier examples still work, hence ellorder lazily calls that when workModM is true.
torsion()
If workModM is set to true, then this simply tests all possible (x,y) pairs for membership of the curve. Any that are found are returned along with their order.
If a_1 and a_3 are both zero, then the Nagell-Lutz result holds and the algorithm given in Cremona’s book is implemented, with each point with positive y co-ordinate given, along with its order. From this it is usually obvious (by Mazur’s theorem) which group they come from; playing around with ncopies usually confirms this, or can be employed to give an explicit list of all points and the relationship between them.
Otherwise, alternative methods using reduction need to be employed, the use of which is described below.
testRange(x1,x2,y1,y2)
This provides a brute-force test of points (x,y) such that x1≤x≤x2 and y1≤y≤y2 for membership of the curve, paying attention to workModM. Whenever a point is found, it is displayed along with its order.
The variant testRangeQuiet takes the same arguments and performs a similar task, but instead returns a count of the number of points found and suppresses the points themselves. This is useful for comparing the upper bounds of several good reductions, which is precisely what the next procedure does.
boundTorsion(n)
This is actually just a wrapper for boundForOrder, feeding it the primes of bad reduction; n primes of good reduction are then used to place upper bounds on the size of the torsion subgroup; the least upper bound is found and displayed, along with the points found when working modulo that prime, which may give assist in identifying genuine torsion points.
I’m unsure as to whether 2 should always be rejected as a prime of bad reduction; if you wish to exclude it, call boundTorsion2 instead.
Examples
Exercise 8.12 of Silverman’s Arithmetic of Elliptic Curves supposedly gives examples of each possible type of torsion group; we can attempt to verify these using torsion_tools. (Start a maple worksheet and enter read “torsion_tools.mpl” to load them; this requires that both torsion_tools.mpl and gla.mpl be somewhere Maple can find them, typically your home directory.)
a) y2=x3-2
>a_1:=0;a_3:=0;a_2:=0;a_4:=0;a_6:=-2;
torsion();Nagell-Lutz search for non-identity torsion points, with order, yields:
x, y, order
Nagell-Lutz theorem applies, but no points other than the identity are found. Thus we have Z/1Z i.e., the trivial group {0}.
b) y2=x3+8
>a_1:=0;a_3:=0;a_2:=0;a_4:=0;a_6:=8;
torsion();Nagell-Lutz search for non-identity torsion points, with order, yields:
x, y, order
-2, 0, 2
We have one other point, of order 2; so the torsion subgroup is Z/2Z, consisting of the identity and (-2,0).
c) y2=x3+4
>a_1:=0;a_3:=0;a_2:=0;a_4:=0;a_6:=4;
torsion();Nagell-Lutz search for non-identity torsion points, with order, yields:
x, y, order
0, 2, 3
We have a point (0,2) of order 3; so the torsion subgroup is clearly Z/3Z. We can explicity find all the elements of the group:
>> ncopies(1,0,2);
0, 2
> ncopies(2,0,2);
0, -2
> ncopies(3,0,2);
zero
So they are the identity, P=(0,2) and 2P=(0,-2).
d) y2=x3+4x
>a_1:=0;a_3:=0;a_2:=0;a_4:=4;a_6:=0;
torsion();Nagell-Lutz search for non-identity torsion points, with order, yields:
x, y, order
0, 0, 2
2, 4, 4
Now things get slightly more interesting. We have an element P=(2,4) of order 4, so we have a subgroup of size 4 consisting of the multiples of P. Does this include the other point found, (0,0)?
> ncopies(1,2,4);
2, 4
> ncopies(2,2,4);
0, 0
> ncopies(3,2,4);2, -4
> ncopies(4,2,4);
zero
Since it does, we can safely conclude that the torsion subgroup is Z/4Z.
e) y2-y=x3-x2
>a_1:=0;a_3:=-1;a_2:=-1;a_4:=0;a_6:=0;
torsion();
Error, expected a_1=a_3=0
Try working with reduced curve modulo a prime not from the set {11}
To test l such primes call boundTorsion(l)
We are no longer in the convenient situation of being able to apply the Nagell-Lutz result. Thus we try to place a bound on the torsion:
> boundTorsion(10);
At most 5 points, example: working mod 5, brute force search for points on curve with order yields
0, 0, 5
0, 1, 5
1, 0, 5
1, 1, 5
4 points, plus point at infinity for a total of 5 points.
The torsion group can have no more than five elements, but it may of course have less. If, however, we can verify the existence of a point of order 5 (not working modulo a prime) then we are clearly done (note that after its calculations for various moduli, boundTorsion resets workModM to false.
> ncopies(5,0,0);
zero
So, as suspected, the group is Z/5Z with (0,0) a generator.
f) y2=x3+1
>a_1:=0;a_3:=0;a_2:=0;a_4:=0;a_6:=1;
torsion();
Nagell-Lutz search for non-identity torsion points, with order, yields:
x, y, order
-1, 0, 2
0, 1, 3
2, 3, 6
Another easy one; using ncopies it is readily verified that P=(2,3) is a generator for the other elements found, so the group is Z/6Z.
g) y2+y=x3-x+137
This one seems to be broken, given the structure of the exercise it should yield Z/7Z. However:
>a_1:=0;a_3:=1;a_2:=0;a_4:=-1;a_6:=167;
> torsion();
Error, expected a_1=a_3=0
Try working with reduced curve modulo a prime not from the set {11, 659, 1667}
To test l such primes call boundTorsion(l)> boundTorsion(10);
At most 1 points, example: working mod 2, brute force search for points on curve with order yields
0 points, plus point at infinity for a total of 1 points.
Or, excluding the prime 2,
> boundTorsion(2);
At most 4 points, example: working mod 3, brute force search for points on curve with order yields
0, 1, 2
1, 1, 2
2, 1, 2
3 points, plus point at infinity for a total of 4 points.
So in neither case can there be an element of order 7.
h) y2 + 7xy =x3+16x
>a_1:=7;a_3:=0;a_2:=0;a_4:=16;a_6:=0;
> torsion();
Error, expected a_1=a_3=0
Try working with reduced curve modulo a prime not from the set {2, 3, 17}
To test l such primes call boundTorsion(l)
> boundTorsion(10);
At most 8 points, example: working mod 7, brute force search for points on curve with order yields
0, 0, 24, 3, 4
4, 4, 4
5, 3, 8
5, 4, 8
6, 2, 8
6, 5, 8
7 points, plus point at infinity for a total of 8 points.
By Mazur’s Theorem, a torsion group with 8 elements (assuming there is no better bound) could be Z/8Z, or Z/2Z X Z/4Z. Thus we need to test for the existence of an order 8 element; the points found above being possibilities. However, ncopies confirms they are not suitable, so we try a brute-force search:
> testRange(-20,20,-20,20);
-8, 16, 8
-2, 4, 8
-2, 10, 8
0, 0, 2
4, 4, 4
5
So, for instance, P=(-2,10) - corresponding to (5,3) mod 7 - is of order 8, so we have Z/8Z.
i) y2+xy+y=x3-x2-14x+29
>a_1:=1;a_3:=1;a_2:=-1;a_4:=-14;a_6:=29;
> torsion();
Error, expected a_1=a_3=0
Try working with reduced curve modulo a prime not from the set {2, 3}
To test l such primes call boundTorsion(l)
> boundTorsion(10);
At most 9 points, example: working mod 11, brute force search for points on curve with order yields
1, 3, 3
1, 6, 3
3, 1, 9
3, 6, 9
8, 6, 9
8, 7, 9
9, 4, 9
9, 8, 98 points, plus point at infinity for a total of 9 points.
We suspect Z/9Z, and indeed ncopies(9,3,1) gives zero, so the suspicion is correct.
j) y2+xy=x3-45x+81
>a_1:=1;a_3:=0;a_2:=0;a_4:=-45;a_6:=81;
> torsion();
Error, expected a_1=a_3=0
Try working with reduced curve modulo a prime not from the set {2, 3, 11}
To test l such primes call boundTorsion(l)
> boundTorsion(10);
At most 10 points, example: working mod 13, brute force search for points on curve with order yields
0, 4, 10
0, 9, 10
2, 12, 2
5, 10, 5
5, 11, 5
6, 3, 5
6, 4, 5
7, 2, 107, 4, 10
9 points, plus point at infinity for a total of 10 points.
(0,4) fails, but (0,9) turns out to genuinely be of order 10 (using ellorder, for a change!). So this gives rise to a torsion group of Z/10Z.
k) y2+43xy-210y=x3-210x2
>a_1:=43;a_3:=-210;a_2:=-210;a_4:=0;a_6:=0;
> torsion();
Error, expected a_1=a_3=0
Try working with reduced curve modulo a prime not from the set {2, 3, 5, 7, 13}
To test l such primes call boundTorsion(l)
> boundTorsion(10);
At most 12 points, example: working mod 17, brute force search for points on curve with order yields
0, 0, 12
0, 6, 12
6, 0, 6
6, 3, 6
9, 13, 4
9, 14, 4
11, 10, 12
11, 16, 1213, 1, 3
13, 7, 3
14, 8, 2
11 points, plus point at infinity for a total of 12 points.
(0,0) is of order 12, so the torsion group is Z/12Z.
l) y2=x3-4x
> a_1:=0;a_3:=0;a_2:=0;a_4:=-4;a_6:=0;
> torsion();
Nagell-Lutz search for non-identity torsion points, with order, yields:
x, y, order
-2, 0, 2
0, 0, 2
2, 0, 2
Since we were able to use Nagell-Lutz, this is all the points with positive y co-ordinate. Along with the identity, there are thus at least 4 points, but none of order 4. So by Mazur’s theorem we have Z/2Z X Z/2Z, so the points above must be related. We can confirm this:
> P:=-2,0;
P := -2, 0
> Q:=0,0;
Q := 0, 0
> ella(P,Q);
2, 0
So we can think of the group as {0,P} X {0,Q}.
m) y2+xy-5y = x3 -5x2
Again, I’m unsure as to whether or not 2 should always be avoided as a prime of bad reduction since it is also misleading here, claiming no more than 4 elements. Using boundTorsion2 (and then ellorder) we find P=(0,0) of order 4, and Q=(1,2) of order 2; Q is not 2P so they are independent, that is, there are 8 elements in contradiction to the result when reducing modulo 2. The torsion group therefore appears to be (in line with the structure of the exercise) {0,Q} X {0,P} = Z/2Z X Z/4Z.
n) y2+5xy-6y=x3-3x2
> a_1:=5;a_3:=-6;a_2:=-3;a_4:=0;a_6:=0;
> torsion();
Error, expected a_1=a_3=0
Try working with reduced curve modulo a prime not from the set {2, 3, 5}
To test l such primes call boundTorsion(l)
> boundTorsion(10);
At most 12 points, example: working mod 17, brute force search for points on curve with order yields
0, 0, 6
0, 6, 6
2, 15, 2
3, 0, 33, 8, 3
5, 16, 2
11, 1, 2
12, 1, 6
12, 13, 6
14, 1, 6
14, 3, 6
11 points, plus point at infinity for a total of 12 points.
P=(0,0) has order 6, whilst the suggestion of 12 points yet none of order 12 implies Z/2Z X Z/6Z. None of the potential order 2 points above have finite order when not working modulo 17; so we search by brute force:
> testRange(-10,10,-10,10);
-3, 3, infinity
0, 0, 6
0, 6, 6
2, -2, 2
3, -9, 3
3, 0, 3
6
This turns up a point Q=(2,-2) of order 2; we must verify it is not generated by P:
> ncopies(2,0,0);
3, -9
> ncopies(3,0,0);-6, 18
> ncopies(4,0,0);
3, 0
> ncopies(5,0,0);
0, 6
As this is not the case, we conclude that the group is {0,Q} X {0,P} = Z/2Z X Z/6Z.
o) y2+17xy-120y = x3-60x2
> a_1:=17;a_3:=-120;a_2:=-60;a_4:=0;a_6:=0;
> torsion();
Error, expected a_1=a_3=0
Try working with reduced curve modulo a prime not from the set {2, 3, 5, 7}
To test l such primes call boundTorsion(l)
> boundTorsion(10);At most 16 points, example: working mod 19, brute force search for points on curve with order yields
0, 0, 8
0, 6, 8
3, 0, 4
3, 12, 4
5, 8, 2
7, 3, 4
7, 17, 4
8, 9, 8
8, 13, 8
11, 4, 8
11, 5, 8
12, 14, 8
12, 16, 8
17, 1, 2
18, 2, 2
15 points, plus point at infinity for a total of 16 points.
Again, P=(0,0) turns out to be a legitimate point of order 8; it generates 2P=(60,-900), 3P=(-30,180), 4P=(24,-144), 5P=(-30,450), 6P=(60,0), 7P=(0,120). None of the suggested points of order 2 work, so again we search, this time over much larger ranges (given the values for multiples of P)-
> testRange(-500,500,-500,500);
-40, 400, 2
-30, 180, 8
-30, 450, 8
-12, 36, 4
-12, 288, 4
0, 0, 8
0, 120, 8
24, -144, 2
30, -300, 8
30, -90, 8
60, 0, 411
Q=(-40,400) is of order 2 and not a multiple of P, so we have {0,Q} X {0,P} = Z/2Z X Z/8Z for the torsion subgroup.