F = K(gn (x), y hn (x)).

The functions in F are those that are invariant under translation by elements

of E[n]. Those on the right are those that are of the form h(n(x, y)). There-

fore, we have proved the proposition.

9.6 The Torsion Subgroup: Doud™s Method

Let E : y 2 = x3 + Ax + B be an elliptic curve de¬ned over Z. The Lutz-

Nagell Theorem (Section 8.1) says that if (x, y) ∈ E(Q) is a torsion point,

then either y = 0 or y 2 |4A3 + 27B 2 . This allows us to determine the torsion,

as long as we can factor 4A3 + 27B 2 , and as long as it does not have many

square factors. In this section, we present an algorithm due to Doud [35] that

avoids these di¬culties and is usually much faster in practice.

Let p ≥ 11 be a prime not dividing 4A3 +27B 2 . By Theorem 8.9, the kernel

of the map from the torsion of E(Q) to E(Fp ) is trivial. Therefore, the order

of the torsion subgroup of E(Q) divides #E(Fp ). If we use a few values of

p and take the greatest common divisor of the values of #E(Fp ), then we

obtain a value b that is a multiple of the order of the torsion subgroup of

E(Q). We consider divisors n of b, running from largest divisor to smallest,

and look for a point of order n on E (of course, we should look at only the

values of n allowed by Mazur™s theorem).

In order to work analytically, we multiply the equation for E by 4 to obtain

E1 : y1 = 4x3 + 4Ax + 4B, with y1 = 2y.

2

The period lattice for E1 is generated by ω1 and ω2 , with ω2 ∈ R. The

points in the fundamental parallelogram corresponding to real x, y under the

map of Theorem 9.10 lie on the line ω2 R, and also on the line 1 ω1 + ω2 R

2

when the cubic polynomial 4x3 + 4Ax + 4B has 3 real roots. Doubling a point

on the second line yields a point on the ¬rst line. Therefore, if n is odd, all

© 2008 by Taylor & Francis Group, LLC

303

SECTION 9.6 THE TORSION SUBGROUP: DOUD™S METHOD

n-torsion points come from the line ω2 R, hence lie in the subgroup generated

by n ω2 , so „˜( n ω2 ) must be an integer. If n is even and z ∈ C/(Zω1 + Zω2 )

1 1

has order n, then z generates the same subgroup of C/(Zω1 + Zω2 ) as one of

1 1 1 1 1 1

n ω2 or n ω2 + 2 ω1 or n ω2 + 2 ω1 + 2 ω2 . Therefore, if there is a torsion point

of order n, then at least one of these three values of z must yield an integral

value of x = „˜(z).

The strategy is therefore to evaluate

1

if n is odd or if 4x3 + 4Ax + 4B has only one real root

„˜( ω2 )

n

1 1 1 1 1 1

„˜( ω2 ), „˜( ω2 + ω1 ), „˜( ω2 + ω1 + ω2 )

n n 2 n 2 2

3

if n is even and 4x + 4Ax + 4B has 3 real roots

for each divisor of b, starting with the largest n. If we ¬nd a numerical value

of x that is close to an integer, we test whether y 2 = x3 + Ax + B yields

an integral value of y. It can be checked whether or not (x, y) has order n

by computing n(x, y). If so, then (since n is the largest divisor of b not yet

excluded), we have the largest cyclic subgroup of the torsion group. Since

only the 2-torsion can be noncyclic (Corollary 3.13), we need to see only if

there is a point of order 2 not already in the subgroup generated by (x, y).

If n(x, y) = ∞, we continue with n and smaller divisors that are still allowed

by Mazur™s theorem and the value of b. We thus obtain all torsion points in

E(Q).

The AGM method (Theorem 9.24) calculates ω1 and ω2 quickly. The fol-

lowing allows us to compute „˜.

PROPOSITION 9.35

Let z ∈ C and let u = e2πiz/ω2 . Let „ = ω1 /ω2 (with the requirement that „

is in the upper half plane) and let q = e2πi„ . Then „˜(z) =

∞

2

2πi 1 u u u 2

’

qn

+ + +n .

12 (1 ’ u) (1 ’ q n u)2 (q ’ u)2 (1 ’ q n )2

2

ω2 n=1

PROOF Let f (z) denote the right-hand side of the equation. Since |q| < 1,

it is easy to see that the series de¬ning f (z) converges uniformly on compact

subsets of C that do not contain points in the lattice ω1 Z + ω2 Z. Therefore,

f (z) is analytic away from these lattice points. Moreover, it has a double pole

at each lattice point. Using the fact that u = 1 + (2πi/ω2 )z + · · · , we ¬nd

that the Laurent expansion of f (z) around z = 0 starts (1/z 2 ) + · · · .

Since u is invariant under z ’ z + ω2 , so is f (z). Changing z to z + ω1

multiplies u by q. A straightforward calculation shows that f is invariant

under u ’ qu. Therefore f is doubly periodic.

The di¬erence f (z)’„˜(z) is a doubly periodic function with no poles except

possibly simple poles at the lattice points. By Theorem 9.1, this implies that

© 2008 by Taylor & Francis Group, LLC

304 CHAPTER 9 ELLIPTIC CURVES OVER C

the di¬erence is a constant; call it C. The roots of the cubic polynomial

4T 3 ’ g2 T ’ g3 are the x-coordinates of the points of order 2, namely „˜( 1 ω1 ),

2

„˜( 2 ω2 ), and „˜( 1 (ω1 + ω2 )). Since there is no T 2 term, the sum of these three

1

2

roots is 0. Therefore,

1 1 1

f ( ω1 ) + f ( ω2 ) + f ( (ω1 + ω2 )) = 3C.

2 2 2

The following lemma shows that C = 0, which yields the proposition.

LEMMA 9.36

1 1 1

f ( ω1 ) + f ( ω2 ) + f ( (ω1 + ω2 )) = 0.

2 2 2

PROOF The values of u corresponding to the three values of z are

u = q ’1/2 .

u = ’1, u = q 1/2 ,

We may divide by the factor (2πi/ω2 )2 , hence we ignore it. The sum of

the three terms 1/12 yields 1/4, which cancels the value of u/(1 ’ u)2 when

u = ’1. The ¬nal term inside the sum de¬ning f (z) is independent of u and

thus yields

∞

qn

’6 . (9.29)

(1 ’ q n )2

n=1

We now consider the remaining terms.

The value u = ’1 (substituted into the sum in f ) yields

∞

qn

’2 . (9.30)

(1 + q n )2

n=1

Combining (9.29) and (9.30) yields

∞

q n + q 2n + q 3n

’8 . (9.31)

(1 ’ q 2n )2

n=1

The value u = q 1/2 (substituted into the sum in f ) yields (the value of

u/(1 ’ u)2 at u = q 1/2 is included in the ¬rst summation)

∞ ∞

1 1

q n+ 2 q n’ 2

+

1 1

n=0 (1 ’ q (q n’ 2 ’ 1)2

n+ 2 )2

n=1

(9.32)

∞ 1

q n’ 2

=2 .

1

n=1 (1 ’ q

n’ 2 )2

© 2008 by Taylor & Francis Group, LLC

305

SECTION 9.6 THE TORSION SUBGROUP: DOUD™S METHOD

Similarly, the value u = ’q 1/2 (substituted into the sum in f ) yields

∞ 1

q n’ 2

’2 . (9.33)

1

n=1 (1 ’ q

n’ 2 )2

Since 1 1

q n’ 2 q n’ 2 4q 2n’1

’ = ,

(1 ’ q 2n’1 )2

1 1

(1 ’ q n’ 2 )2 (1 + q n’ 2 )2

the sum of (9.31), (9.32), (9.33) is

∞

q n + q 2n + q 3n q 2n’1

’

8 + . (9.34)

(1 ’ q 2n )2 (1 ’ q 2n’1 )2

n=1

Di¬erentiating the series for 1/(1 ’ X) yields the identity

∞

1

mX m’1 .

=

(1 ’ X)2 m=1

Substituting X = q 2n’1 , multiplying by q 2n’1 , and summing over n yields

∞ ∞ ∞

q 2n’1

mq (2n’1)m

= (9.35)

(1 ’ q 2n’1 )2

n=1 m=0 n=1

⎛ ⎞

∞

⎝ d⎠ q N .

= (9.36)

N =1 d|N, N/d odd

Similarly, we obtain

∞ ∞ ∞

qn

mq n(2m’1)

=

(1 ’ q 2n )2

n=1 m=0 n=1

⎛ ⎞ (9.37)

∞

d + 1⎠ N

⎝

= q

2

N =1 d|N, d odd

and

∞ ∞ ∞

q 3n

mq n(2m+1)

=

(1 ’ q 2n )2

n=1 m=0 n=1

⎛ ⎞ (9.38)

∞

d ’ 1⎠ N

⎝

= q.

2

N =1 d|N, d odd

Also, the method yields

⎛ ⎞

∞ ∞

2n

q ⎝ d⎠ q N .

= (9.39)

(1 ’ q 2n )2

n=1 N =1 d|N, N/d even

© 2008 by Taylor & Francis Group, LLC

306 CHAPTER 9 ELLIPTIC CURVES OVER C

Using (9.35), (9.37), (9.38), and (9.39), we ¬nd that (9.34) equals

⎛ ⎞

∞

⎝ d⎠ q N .

’ ’

8 d d (9.40)

N =1 d|N, N/d odd d|N, d odd d|N, N/d even

We claim that for all N ≥ 1,

’ ’

d d d = 0.

d|N, N/d odd d|N, d odd d|N, N/d even

Write N = 2a u with a ≥ 0 and u odd. Then

2a d1

d=

d1 |u

d|N, N/d odd

d= d

d|N, d odd d|u

d= d2 .

d2 |2a’1 u

d|N, N/d even

If a = 0, the last sum is interpreted to be 0. In this case, the claim is easily

seen to be true. If a ≥ 1, then the divisors of 2a’1 u are of the form 2j d3 with

0 ¤ j ¤ a ’ 1 and d3 |u. Therefore,

(1 + 2 + 22 + · · · + 2a’1 )d3 = (2a ’ 1)

d2 = d3 .

d2 |2a’1 u d3 |u d3 |u

The claim follows easily. This completes the proof of the lemma.

Since C = 0, the proof of the proposition is complete.

Example 9.3

Consider the curve

E : y 2 = x3 ’ 58347x + 3954150.

We have 4A2 + 27B 2 = ’372386507784192, which factors as 218 317 11, al-

though we do not need this factorization. Since 11 divides this number, we

skip 11 and start with p1 = 13. The number of points in E(F13 ) is 10. The

number of points in E(F17 ) is also 10. Either of these facts implies that the

number of torsion points in E(Q) divides 10. Using the AGM, we calculate

ω2 = 0.198602 · · · .

ω1 = i0.156713 . . . ,

This yields „ = i0.78908 · · · and q = 0.0070274 · · · . We calculate

„˜(ω2 /10) = 2539.82553 . . . ,

© 2008 by Taylor & Francis Group, LLC

307

EXERCISES

which is not close to an integer. However,

1

„˜(ω2 /10 + ω1 ) = ’213.00000 . . . .

2

This yields the point

(x, y) = (’213, 2592)

on E. An easy check shows that this is a point of order 10. Since the order of

the torsion subgroup divides 10, we have determined that the torsion in E(Q)

consists of the multiples of (’213, 2592).

Exercises

9.1 (a) Show that d3 ≡ d5 (mod 12) for all integers d.

(b) Show that

d5 ≡ 0 (mod 12)

d3 + 7

5

d|n d|n

for all positive integers n.

(c) Show that

(2π)4

g2 = (1 + 240X),

12

∞ n

where X = n=1 σ3 (n)q .

(d) Show that

(2π)6

(1 ’ 504Y ),

g3 =

216

∞

σ5 (n)q n .

where Y = n=1

(e) Show that

1728(2π)’12 ∆ = (1 + 240X)3 ’ (1 ’ 504Y )2 . (9.41)

(f) Show that the right side of (9.41) is congruent to 144(5X + 7Y )

mod 1728.

∞

(g) Conclude that (2π)’12 ∆ = dn q n , with dn ∈ Z.

n=0

(h) Compute enough coe¬cients to obtain that

∞

’12

en q n )

(2π) ∆ = q(1 +

n=1

with en ∈ Z.

© 2008 by Taylor & Francis Group, LLC

308 CHAPTER 9 ELLIPTIC CURVES OVER C

∞

(i) Show that (2π)12 /∆ = q ’1 fn q n with fn ∈ Z.

n=0

(j) Show that

∞

1

cn q n

j= +

q n=0

with cn ∈ Z.

ai bi

∈ SL2 (Z) for i = 1, 2, 3 with M2 M1 = M3 . Let

9.2 Let Mi =

ci di

„1 ∈ F. Let

a1 „1 + b1 a2 „2 + b2

„2 = , „3 = .

c1 „1 + d1 c2 „2 + d2

Show that

a3 „1 + b3

„3 = .

c3 „1 + d3

9.3 Let k ≥ 0 be an integer. Let f be a meromorphic function on the upper

half plane such that f has a q-expansion at i∞ (as in Equation (9.15))

and such that

a„ + b

= (c„ + d)k f („ )

f

c„ + d

ab

for all „ ∈ H and for all ∈ SL2 (Z). Show that

cd

1 1 k

ordi∞ (f ) + ordρ (f ) + ordi (f ) + ordz (f ) = .

3 2 12

z=i,ρ,i∞

ab

9.4 The stabilizer in SL2 (Z) of a point z ∈ H is the set of matrices

cd

such that (az + b)/(cz + d) = z.

(a) Show that the stabilizer of i has order 4.

(b) Show that the stabilizer of ρ has order 6.

(c) Show that the stabilizer of i∞ consists of the matrices of the form

1b

± with b ∈ Z.

01

(d) Show that the stabilizer of each z ∈ H has order at least 2.

It can be shown that the stabilizer of each element in the fundamental

domain F has order 2 except for i and ρ.

9.5 Let E : y 2 = 4x3 + Ax + B, with A, B ∈ R be an elliptic curve de¬ned

over R. We know by Theorem 9.21 that E(C) C/L for some lattice

L. The goal of this exercise is to show that L has one of the two shapes

given in part (i) below.

© 2008 by Taylor & Francis Group, LLC

309

EXERCISES

(a) Let „ ∈ F. Show that j(„ ) = j(’„ ).

(b) Show that if „ is in the fundamental domain F , then either ’„ ∈ F,

or („ ) = ’1/2, or |„ | = 1 with ’1/2 ¤ („ ) ¤ 0.

(c) Suppose that „ ∈ F and that j(„ ) ∈ R. Show that („ ) = 0,

or („ ) = ’1/2, or |„ | = 1 with ’1/2 ¤ („ ) ¤ 0 (Hint: Use

Corollary 9.18.)

(d) Let „ ∈ H. Show that if |„ | = 1 then (’1/(„ + 1)) = ’1/2.

(e) Let L be a lattice with g2 (L) = ’A and g3 (L) = ’B. Show

that there exists „ ∈ H such that („ ) = 0 or ’1/2 and j(L) =

j(Z„ + z).

(f) Show that if „ ∈ H is such that („ ) = 0 or ’1/2, then we have

g2 („ ), g3 („ ) ∈ R.

(g) By Corollary 9.20, there exists » ∈ C such that L = (»)(Z„ + Z).

Show that if j = 0, 1728 then »2 ∈ R. (Hint: Use Equations

(9.14).)

This shows that L is obtained from the lattice Z„ + Z by an ex-

pansion by |»| and a rotation by 0, 90—¦ , 180—¦ , or 270—¦ .

(h) Let 0 = y ∈ R. Let M be the lattice ( 1 + iy)Z + Z. Show that iM

2

has {y + 1 i, 2y} as a basis.

2

(i) Assume that j = 0, 1728. Show that L has a basis {ω1 , ω2 } with

ω2 ∈ R and (ω1 ) = 0 or 1 ω2 . Therefore, the lattice L is either

2

rectangular or a special shape of parallelogram.

(j) Use the facts that j(ρ) = 0 and j(i) = 1728 to prove (i) in the

cases that j(E) = 0 and j(E) = 1728. (The condition that »2 ∈ R

gets replaced by »6 ∈ R and »4 ∈ R, respectively. However, the

lattices for „ = ρ and „ = i have extra symmetries.)

9.6 Let L be a lattice that is stable under complex conjugation (that is, if

ω ∈ L then ω ∈ L). This is the same as requiring that the elliptic curve

associated to L is de¬ned over R (see Exercise 9.5).

(a) Show that „˜(z) = „˜(z).

(b) Show that if t ∈ R and if ω2 ∈ R is a real period, then

1

∈ R.

„˜ ω2 + it

2

(Hint: Use (a), the periodicity of „˜, and the fact that „˜(’z) =

„˜(z).)

(c) Di¬erentiate the result of (b) to show that „˜ (z) ∈ iR for the

points 1 ω2 + it in (b). This path, for 0 ¤ t ¤ ω1 , corresponds to

2

x moving along the x-axis between the two parts of the graph in

© 2008 by Taylor & Francis Group, LLC

310 CHAPTER 9 ELLIPTIC CURVES OVER C

Figure 2.1(a) on page 10. The points don™t appear on the graph

because y is imaginary. For the curve in Figure 2.1(b) on page 10, x

moves to the left along the x-axis, from the point on the x-axis back

to the point at in¬nity, corresponding to the fact that ω1 = 1 ω2 +it

2

for appropriate t (see Exercise 9.5).

9.7 De¬ne the elliptic integral of the second kind to be

√

1 ’ k 2 x2

1

√ dx, ’1 < k < 1.

E(k) =

1 ’ x2

0

(a) Show that

π/2

(1 ’ k 2 sin2 θ)1/2 dθ.

E(k) =

0

(b) Show that the arc length of the ellipse

x2 y2

+ 2 =1

a2 b

with b ≥ a > 0 equals 4bE( 1 ’ (a/b)2 ).

This connection with ellipses is the origin of the name “elliptic inte-

gral.” The relation between elliptic integrals and elliptic curves, as in

Section 9.4, is the origin of the name “elliptic curve.” For more on

elliptic integrals, see [78].

9.8 Let E be the elliptic curve y 2 = 4x3 ’ 4x. Show that

∞ 1

dx 1

t’3/4 (1 ’ t)’1/2 dt = β(1/4, 1/2),

ω2 = =

x(x2 ’ 1) 2

1 0

1 p’1

’ t)q’1 dt is the beta function. A classical

where β(p, q) = t (1

0

result says that

“(p)“(q)

.

β(p, q) =

“(p + q)

Therefore,

1 “(1/4)“(1/2)

ω2 = .

2 “(3/4)

© 2008 by Taylor & Francis Group, LLC