Diophantine Cohen Lectures

7/28/2019 Diophantine Cohen Lectures

1/82

Explicit Methods for Solving Diophantine Equations

Henri Cohen

Laboratoire A2XUniversit e Bordeaux 1

Tucson, Arizona Winter School, 2006


2/82

E XAMPLES (I)

Diophantine equation: system of polynomial equations to be solved in

integers , rational numbers , or other number rings.

Fermats Last Theorem (FLT) : in Z, xn + yn = zn with n 3 impliesxyz = 0 . This gave the impetus for algebraic number theory by Kummer ,

Dirichlet , . . . . Solved by these methods up to large values of n (severalmillion). Then Faltingss result on rational points on higher genus curvesproved that for xed n , only nite number of (coprime) solutions. Butnally completely solved using elliptic curves , modular forms , and Galois

representations by Ribet , Wiles , and TaylorWiles . The method of solutionis more important than FLT itself.


3/82

EXAMPLES (II)

Catalans conjecture : if m and n are at least 2, nonzero solutions of xm yn = 1 come from 32 23 = 1 . Until recently, same status as FLT:attacks using algebraic number theory solved many cases. Then Baker -type

methods were used by Tijdeman to show that the total number of (m,n,x,y ) is nite. Finally completely solved by Mih ailescu in 2001,using only the theory of cyclotomic elds , but rather deep results ( Thainestheorem ), quite a surprise. Proof later simplied by Bilu and Lenstra .


4/82

EXAMPLES (III)

The congruent number problem (Diophantus , 4th century A.D.). Find

all integers n equal to the area of a Pythagorean triangle , i.e. with all sidesrational (example (3, 4, 5) gives n = 6 ). Easy: equivalent to the existence of rational solutions of y2 = x3 n2x with y = 0 . Again, three stages. Untilthe 1970s, several hundred values solved. Then using theBirchSwinnerton Dyer conjecture (BSD) , possible to determineconjecturally but analytically if n congruent or not. Final (but not ultimate)step: a theorem of Tunnell in 1980 giving an immediate criterion for

congruent numbers, using modular forms of half-integral weight , but stillmodulo a weak form of BSD.


5/82

TOOLS (I)

Almost as many methods to solve Diophantine equations as equations.

Attempt at classication:

Local methods: the use of p-adic elds, in an elementary way(congruences modulo powers of p), or less elementary ( Strassmanns or

Weierstrasss theorem, p-adic power series, Herbrands and Skolemsmethod).

Factorization over Z. Not a very powerful method, but sometimes givesspectacular results ( Wendts criterion for the rst case of Fermats lasttheorem, Casselss results on Catalans equation ).


6/82

TOOLS (II)

Factorization over number elds , i.e., global methods. This was in factthe motivation for the introduction of number elds in order to attack Fermats last theorem (FLT) . Even though very classical, still one of themost powerful methods, with numerous applications and successes.

Diophantine approximation methods. This can come in many different

guises, from the simplest such as Runges method , to much moresophisticated ones such as Baker-type methods .

Modular methods, based on the work of Ribet , Wiles , and TaylorWiles ,

whose rst and foremost success is the complete solution of FLT, but whichhas had many applications to other problems.


7/82

TOOLS (III)

In addition, if the set of solutions has a well-understood structure , in manycases one can construct algorithmically this set of solutions, and inparticular one solution. Examples are:

The PellFermat equation x2 Dy 2 = 1, and more generally normequations N K/ Q ( ) = m , where the magical algorithm is based oncontinued fractions and Shankss infrastructure .Elliptic curves of rank 1 over Q, where the magical algorithm is basedon the construction of Heegner points , and in particular of the theory of complex multiplication .


8/82

INTRODUCTION TO LOCAL M ETHODS (I)

Examples of naive use:

The equation x2 + y2 = 3 z2 . Dividing by the square of the GCD, wemay assume x and y coprime. Then x2 and y2 are congruent to 0 or 1

modulo 3, but not both 0, hence x2

+ y2

1 (mod 3) , a contradiction.FLT I for exponent 3 . This is the equation x3 + y3 = z3 with 3 xyz .We work modulo 32 : since a cube is congruent to 0 or 1 modulo 9, if 3 xy we have x

3

+ y3

2, 0, or 2 modulo 9, which is impossible if 3 z.


9/82

INTRODUCTION TO LOCAL M ETHODS (II)

In general need properties of the eld Q p of p-adic numbers and ring of integers Z p . Reminder:

A homogeneous equation with integer coefcients has a nontrivialsolution modulo p

n

for all n 0 if and only if it has a nontrivial solution inZ p (or in Q p by homogeneity).There is a canonical integer-valued valuation v p on Q p: if x Q thenv p(x) is the unique integer such that x/p vp (x ) can be written as a rationalnumber with denominator and numerator not divisible by p. It isultrametric : v p(x + y) min( v p(x), v p(y)) .

Elements of Q p such that v p(x)

0 are p-adic integers , they form a local

ring Z p with maximal ideal pZ p . Invertible elements of Z p , called p-adicunits , are x such that v p(x) = 0 . If x Q p , canonical decompositionx = pvp (x ) y with y a p-adic unit.


10/82

INTRODUCTION TO L OCAL M ETHODS (III)

If a Q is such that v p(a) 0 and if v p(x) 1 then the power series(1 + x)a converges. If v

p(a) < 0 the power series converges for

v p(x) |v p(a)|+ 1 when p 3, and v p(x) |v p(a)|+ 2 when p = 2 . Itconverges to its expected value, for instance if m Z \ {0}theny = (1 + x)1/m satises ym = 1 + x .

Hensels lemma (or Newtons method ). Special case: if f (X ) Q p[X ]and Q p satises v p(f ( )) 1 and v p(f ( )) = 0 . There exists Q p such that f ( ) = 0 and v p( ) 1, and easily computedby Newtons iteration.Testing for local solubility is usually easy and algorithmic .


11/82

LOCAL M ETHODS : THE FERMAT Q UARTICS (I)

These are the equationsx4 + y4 = cz4 ,

where without loss of generality we may assume that c Z is not divisible

by a fourth power. Denote by Cthe projective curve x4

+ y4

= c.Note that we will only give the local solubility results, but that the globalstudy involves many methods ( factorization in number elds, elliptic

curves ), but is far from complete, although it can solve c 10000.


12/82

L OCAL M ETHODS : THE FERMAT Q UARTICS (II)

Proposition . The curve Cc is everywhere locally soluble (i.e., has points inR and in every Q p) if and only if c > 0 and the following conditions aresatised.

1. c 1 or 2 modulo 16.2. p | c , p = 2 implies p 1 (mod 8) .3. c 3 or 4 modulo 5.4. c

7 , 8 , or 11 modulo 13.

5. c 4 , 5 , 6 , 9 , 13 , 22 , or 28 modulo 29.


13/82


14/82

L OCAL M ETHODS : FERMAT S LAST THEOREM I (I)

Proposition . The following three conditions are equivalent.

1. There exists three p-adic units , , and such that p + p = p (inother words FLT I is soluble p-adically).

2. There exists three integers a , b , c in Z such that p abc witha p + b p c p (mod p2).

3. There exists a Z such that a is not congruent to 0 or 1 modulo pwith (a + 1) p a p + 1 (mod p2).

Proof: Congruences modulo p3 and Hensels lemma.


15/82

LOCAL M ETHODS : FERMAT S LAST THEOREM I (II)

Corollary . If for all a Z such that 1 a ( p 1)/ 2 we have(a + 1) p a p 1 0 (mod p2) , the rst case of FLT is true for p.Note that using Eisenstein reciprocity (which is a more difcult globalstatement), can prove that a = 1 is sufcient in the above, i.e., Wieferichscriterion : if 2 p1 1 (mod p2) then FLT I is true for p (only knownexceptions p = 1093 and p = 3511 ).


16/82

LOCAL M ETHODS : STRASSMANN S T HEOREM (I)

More sophisticated use of p-adic numbers: p-adic analysis .Theorem . If f (X ) = n 0 f n X

n with f n 0 p-adically, not identically0 , exist at most N elements x Z p such that f (x) = 0 , where N uniqueinteger such that |f n | |f N | for n < N , and |f n | < |f N | for n > N .Same theorem in extensions of Q p . Easy proof by induction on N using theultrametric inequality .


17/82

LOCAL M ETHODS : STRASSMANN S THEOREM (II)

Example : the equation x3 + 6 y3 = 1 in Z. Set = 6 1/ 3 , K = Q(), = 3 2 6 + 1 fundamental unit of K of norm 1. Dirichlets unit theoremimplies x + y = k for k Z. If = 2 2 then = 1 + 3 , and

(1 + 3 )k = exp 3(k log3(1 + 3 ))

power series in k (not in ) which converges 3-adically. Note 1, , 2

linearly independent over Q3 (X 3 + 6 irreducible in Q3[X ]). Coefcient of 2 in k = x + y + 0 2 equal to 0 gives equation in k to which can applyStrassmann , nd N = 1 , hence k = 0 only solution, so (x, y) = (1 , 0).


18/82

FACTORIZATION OVER Z : W ENDT S CRITERION (I)

Can give spectacular results. Example: Wendts criterion for FLT I .

Proposition . Let p be an odd prime, k

2 an even integer. Assume that

q = kp + 1 is a prime such that q (kk 1)R(X k 1, (X + 1) k 1)(R(P, Q ) resultant of P and Q). Then FLT I is true, i.e., x p + y p + z p = 0implies p | xyz .Proof: May assume relatively prime. Write

x p = y p + z p = ( y + z)(y p1 y p2z + + z p1) .Observe factors relatively prime (otherwise y and z not relatively prime).

Thus exists a such that y + z = a p and y p1 y p2z + + z p1 = s p .By symmetry z + x = b p and x + y = c p .


19/82

FACTORIZATION OVER Z : W ENDT S CRITERION (II)

For q = kp + 1 , equation implies

x(q

1) /k

+ y(q

1) /k

+ z(q

1) /k

0 (mod q ) .If q xyz , implies that u = ( x/z ) p mod q satises uk 1 0 (mod q )

and (u + 1) k 0 (mod q ), contradicting q R(X k 1, (X + 1) k 1).Thus q | xyz , say q | x , hence

0 2x = ( x + y) + ( z + x) (y + z) = c p + b p + ( a) p= c(q1) /k + b(q1) /k + ( a)(q1) /k (mod q ) .

As above, q | abc, and since q | x and x , y, and z pairwise coprime, cannothave q | b p = z + x or q | c p = x + y, so q | a .


20/82

FACTORIZATION OVER Z : W ENDT S CRITERION (III)

Thus y

z (mod q ), hence s p

py p1 (mod q ). On the other hand

y = ( x + y) x c p (mod q ), sos (q1) /k = s p pc(( q1) /k )( p1) (mod q ) ,

and since q c, p d(q

1) /k

(mod q ) with d = s/c p

1

mod q . Since a , scoprime, we have q s , so q d, so pk 1 (mod q ), and since k even

1 = (1)k = ( kp q )k kk pk kk (mod q ) ,contradicting the assumption q kk 1.


21/82


22/82

FACTORIZATION OVER Z : y2 = x 3 + t

By using similar naive methods, can prove the following:

If a and b are odd, if 3 b, and if t = 8 a3 b2 is squarefree, theny2 = x3 + t has no integral solution.

The example t = 7 = 8 13 12 was a challenge posed by Fermat . If a is odd, 3 b, and t = a3 4b2 is squarefree and such that t 1(mod 8) . Then y2 = x3 + t has no integral solution.


23/82

C ASSELS S RESULTS ON C ATALAN (I)

Recall that Catalans equation is xm yn = 1 , with min( m, n ) 2.Contrary to FLT, m = 2 or n = 2 must be included. Proof for n = 2 (nonontrivial solution) due to V.-A. Lebesgue in 1850 (not the Lebesgueintegral), and involves factoring over Z[i], not difcult. Proof for m = 2considerably more subtle (not really difcult) because there exist the

solutions (3)2 23 = 1 . Done by Ko Chao in the 1960s, and involvesstructure of the unit group of a real quadratic order .As for FLT, we are reduced to x p yq = 1 with p and q distinct odd primes,with symmetry map ( p, q, x, y) (q,p,y, x). Basic results on thisfound by Cassels.


24/82

C ASSELS S RESULTS ON C ATALAN (II)

Casselss proof: factoring over Z, clever reasoning, and analytic method

called Runges method , a form of Diophantine approximation. As all such,boils down to x R, |x| < 1, and x Z implies x = 0 .Exercise : use this to nd all integral solutions toy2 = x4 + x3 + x2 + x + 1 (hint in the notes).

Need arithmetic lemma and two analytic ones.

Arithmetic lemma : Let q prime, and set w( j ) = j + vq( j !). Thenq w ( j ) p/q

jis an integer coprime to q , and w( j ) is strictly increasing .

Proof: easy, although there is a slight subtlety (see notes).


25/82

C ASSELS S RESULTS ON C ATALAN (III)

Analytic lemma I : If q > p > 0 (not necessarily integral) and a 1, then(aq + 1) p < (a p + 1) q , and if a > 1 then (aq 1) p > (a p 1)q .Proof: easy undergraduate exercise.

Analytic lemma II : Assume p > q integers, q 3, p 5 as in Catalan.Set F (t) = ((1 + t) p t p)1/q , m = p/q + 1 , and let F m (t) the sum of the terms of degree at most equal to m in the Taylor series expansion of F (t) around t = 0 . For all t R such that |t| 1/ 2 we have

|F (t) F m (t)| |t|m +1

(1

|t

|)2

.

Proof: not easy undergraduate exercise (see notes).


26/82

C ASSELS S RESULTS ON C ATALAN (IV)

Factorization over Z: x p yq = 1 gives yq = x p 1 = ( x 1)r p(x) withr p(x) = ( x p 1)/ (x 1). Factors not necessarily coprime but, expandingr p(x) = (( x 1 + 1) p 1)/ (x 1) by the binomial theorem, easy to seethat p

|(x

1) is equivalent to p

|r p(x), that if d = gcd( x

1, r p(x)) then

d = 1 or d = p, and that if d = p > 2 then r p(x) p (mod p2), so thatv p(r p(x)) = 1 . Since yq = ( x 1)r p(x), condition d = p is equivalent to p | y. Casselss main theorem says that this is always true, i.e., we neverhave d = 1 .


27/82

C ASSELS S RESULTS ON C ATALAN (V)

Proof of Casselss result split into p < q and p > q . The rst case is much

easier:Proposition . If x and y are nonzero integers and p and q odd primes suchthat x p yq = 1 , then when p < q we have p | y.Proof: if not, x

1 and r p(x) are coprime, so both are q th powers since

product is. Write x 1 = aq . Since xy = 0 , a = 0 and a = 1, and(aq + 1) p yq = 1 . Set f (z) = ( aq + 1) p zq 1, decreasing function of z. If a 1 then f (a p) = ( aq + 1) p a pq 1 > 0 (binomial theorem), andf (a

p+ 1) = ( a

q+ 1)

p

(a p

+ 1)q

1 < 0 by rst analytic lemma. Sincef strictly decreasing, the y such that f (y) = 0 is not an integer, absurd.


28/82

C ASSELS S RESULTS ON C ATALAN (VI)

Similarly, if a < 0, we have a 2, and set b = a . Since p and q are oddf (a p) = ( aq + 1) p a pq 1 = ((bq 1) p b pq + 1) > 0 (binomialtheorem), andf (a p + 1) = ( aq + 1) p

(a p + 1) q

1 =

((bq

1) p

(b p

1)q + 1) < 0

again by the rst analytic lemma since b > 1. Again absurd.

Crucial corollary, due to Hyyr o:

Corollary . Same assumptions, in particular p < q . Then

|y

| pq1 + p.

Proof: since p | y and v p(r p(x)) = 1 , can write x 1 = pq1a p ,(x p 1)/ (x 1) = pvq , y = pav . Set P (X ) = X p 1 p(X 1).Clearly (X

1)2

|P (X ), so (x

1)

|(x p

1)/ (x

1)

p = p(vq

1),

so vq 1 (mod pq2). Since q > p, ( pq2) = pq3( p1) coprime to q ,hence v 1 (mod pq2). It is easily seen that v = 1 is impossible, sov pq2 + 1 , so |y| = pav pv pq1 + p.


29/82

C ASSELS S RESULTS ON C ATALAN (VII)

Case p > q more difcult.Proposition . If x and y are nonzero integers and p and q odd primes suchthat x p yq = 1 , then when p > q we have p | y.Proof: as in proof for p < q , assume by contradiction p y, so x 1 = aqhence yq = ( aq + 1) p 1, so y = a pF (1/a q) with F as in analytic lemmaII. Recall m = p/q + 1 , and set z = amq py amq F m (1/a q), so thatz = amq (F (1/a q) F m (1/a q)) . By Taylors theoremtm F m (1/t ) = 0j m

p/qj t

m j , and by arithmetic lemmaD = q m + vq (m !) is a common denominator of all the p/q

jfor 0

j

m .

Thus Da mq F m (1/a q) Z, and since mq p we have amq py Z, sothat Dz Z.


30/82

C ASSELS S RESULTS ON C ATALAN (VIII)

We now show |Dz | < 1. Applying analytic lemma II to t = 1 /a q (satises|t| 1/ 2 since a = 1):

|z

| |a|q

(|a|q

1)2

1

|a|q

2 1

|x| 3.

By Hyyr os Corollary (with ( p, q, x, y) replaced by (q,p,y, x)) we have|x| q p1 + q q p1 + 3 , so

|Dz | D|x| 3 q m + vq (m !)( p1) .

Since vq(m!) < m/ (q 1) for m 1 and m < p/q + 1 , we havem + vq(m!) ( p 1) < m q q 1

( p1) = 3 ( p 2)(q 2)q 1 0

since q 3 and p 5, proving |Dz | < 1.


31/82

C ASSELS S RESULTS ON C ATALAN (IX)Since Dz Z, we have Dz = 0 . But

Dz = Damq

p

y 0j m D p/q

j aq(m

j )

,

and by the arithmetic lemma

vq p/q

j < v q p/q m = vq(D )

for 0 j m 1, hence again by the arithmetic lemma

0 = Dz D p/q m 0 (mod q ) ,

absurd.


32/82

C ASSELS S RESULTS ON C ATALAN (IX)

Immediate but crucial corollary of Casselss theorem:

Corollary . If x and y are nonzero integers and p and q odd primes suchthat x p yq = 1 , there exist nonzero integers a and b , and positive integersu and v with q u and p v such that

x = qbu, x 1 = pq

1

aq

,x p

1

x 1 = pvq

,

y = pav, y + 1 = q p1b p , yq + 1

y + 1= qu p .

Proof: easy exercise from the main theorem.


33/82

INTRODUCTION TO N UMBER F IELDS (I)

Apart from the methods studied above, this is the oldest and most usedmethod in the subject, and as already mentioned the whole theory of number elds arose from the study of Diophantine equations, in particularFLT. Reminder:

A number eld K is a nite extension of Q, equivalently K = Q(),where root of a nonzero polynomial A Q[X ].

An algebraic integer is a root of a monic polynomial with integercoefcients. The element such that K = Q() can always be chosensuch. The set of algebraic integers of K forms a ring, denoted ZK ,containing Z[] with nite index, when chosen integral. It is a freeZ-module of rank n = [K : Q], and a Z-basis of ZK is called an integralbasis .


34/82

INTRODUCTION TO N UMBER F IELDS (II)

The ring ZK is a Dedekind domain . The essential consequence is thatany fractional ideal can be decomposed uniquely into a power product of prime ideals. This is in fact the main motivation. Crucial fact: if Z[] = ZK then it is never a Dedekind domain.

If p is a prime, let pZK = 1ig pe ii be the prime power decomposition

of pZK . The ideals pi are the prime ideals above (in other wordscontaining) p, the ei are the ramication indexes , the eld ZK / pi is a niteeld containing F p = Z/p Z with degree denoted by f i , and we have theimportant relation 1ig ei f i = n = [K : Q].


35/82

INTRODUCTION TO N UMBER F IELDS (III)

Class group Cl(K ) dened as the quotient of fractional ideals byprincipal ideals, nite group with cardinality denoted h(K ).

Unit group U (K ), group of invertible elements of ZK , or group of

algebraic integers of norm 1, is a nitely generated abelian group of rank r 1 + r 2 1 (r 1 and 2r 2 number of real and complex embeddings).Torsion subgroup nite equal to the group (K ) of roots of unity in K .


36/82

INTRODUCTION TO N UMBER F IELDS (IV)

A quadratic eld is Q( t), with t squarefree integer different from 1. Itsring of integers is either equal to Z[ t] = {a + b t, a,b Z}when t 2or 3 modulo 4, or (a + b t)/ 2, with a and b integers of same parityotherwise.

A cyclotomic eld is K = Q( ), with primitive m th root of unity. Mainresult: the ring of integers of a cyclotomic eld is Z[ ], and no larger.


37/82


38/82

FERMAT S LAST THEOREM I (FLT I) (II)Anyway, lets assume rst that ZK = Z[ ] is a UFD. We prove:Lemma . Assume that Z[ ] is a UFD. If x p + y p = z p with p xyz , there

exist Z[ ] and a unit u of Z[ ] such that x + y = u p.

Proof: may assume x , y, z pairwise coprime. Our equation can be factoredover Z[ ] as

(x + y)(x + y ) (x + y p

1

) = z p

.Claim: the factors are pairwise coprime. If some divides x + y i andx + y j for i = j , it divides also y( i j ) and x( j i ), hence i jsince x and y are coprime (in Z hence in Z[ ]). Since ( i

j )

| p in Z[ ],

we have | p, and on the other hand | (x + y i ) | z. Since p and z arecoprime, | 1, in other words is a unit, proving the claim.


39/82

FERMAT S LAST THEOREM I (FLT I) (III)

Thus product of pairwise coprime elements in Z[ ] equal to a pth power, soup to multiplication by a unit, each one is, since Z[ ] is a PID byassumption, proving the lemma.

Unfortunately, as mentioned, not very useful since condition too strict. Thisis where ideals play their magic. Denote by h p the class number of thecyclotomic eld K = Q( p). Then:


40/82


41/82

FERMAT S LAST THEOREM I (FLT I) (V)

The rest of the proof in case p h

pis specic and easy (see notes). It uses

however an additional crucial ingredient, Kroneckers theorem : if is analgebraic integer such that all the conjugates of in C have norm equal to1, then it is a root of unity . In particular, if u is a unit of Z[ ], then u/u is a

root of unity.

A prime such that p h p is called a regular prime . Known that there areinnitely many irregular primes, conjectured innitely many regular with

density e1/ 2

= 0 .607 . . . .


42/82

FERMAT S LAST THEOREM I (FLT I) (VI)

One of the crucial ingredients in the proof was bh p principal for all idealsb. We say that h p annihilates the class group Cl(K ). However, K/ Q is aGalois extension (even abelian ) with Galois group G (Z/p Z) . Thegroup ring Z[G] acts on Cl(K ), and we can look for other elements of Z[G]which annihilate Cl(K ). One such is given by the Stickelberger element ,and more generally elements of the Stickelberger ideal .


43/82

FERMAT S LAST THEOREM I (FLT I) (VII)

This is used in a simple way by Mih ailescu for Catalan: if x p yq = 1with p, q odd primes and xy = 0 , then double Wieferich condition :

pq1 1 (mod q 2) and q p1 1 (mod p2) .Note no class number condition. Only seven such pairs known, but expect

innitely many.

More sophisticated annihilator of Cl(K ) given by Thaines theorem , usedin an essential way by Mih ailescu for the complete proof of Catalan, but

also in different contexts such as the Birch and Swinnerton-Dyer conjecture .


44/82

y2 = x 3 + t REVISITED

Have already seen in special cases. Can factor in Q( t) or in Q( 3 t).Problem with units which are not roots of unity. Sometimes can take careof that, but not always. Q( 3 t) always has such units, so we do not use.Q( t) also does if t > 0, so we assume t < 0. Thus write(y t)(y + t) = x3 in imaginary quadratic eld K = Q( t). If factors not coprime, much more messy. To have factors coprime need both tsquarefree and t 1 (mod 8) . The rst condition is not really essential,the second is. We then deduce that the ideal (y t)ZK is the cube of anideal, and to conclude as in FLT I we absolutely need the condition

3 |Cl(K )|. Under all these restrictions, easy to give complete solution (seenotes). For specic t , must solve Thue equations .


45/82

THE SUPER -F ERMAT EQUATION x p + y q = z r (I)

A whole course to itself! Most salient points:

Must add the condition x , y, z coprime because not homogeneous,otherwise usually easy to construct innitely many stupid (nontrivial)

solutions. Example:

552684799301833394749443 + 507799783342085 = 65303470087 .

Set = 1 /p + 1 /q + 1 /r 1. Different behavior according to sign of : If > 0 (elliptic case ) complete and disjoint parametrizations of the(innite) set of solutions ( Beukers ).

If < 0, only a nite number of solutions ( DarmonGranville , usingFaltings ). Only a few cases solved (rational points on curves of genusg 1), and only ten cases known. Would need effective form of Faltings.


46/82

THE SUPER -F ERMAT EQUATION x p + yq = z r (II)

Elliptic case corresponds up to permutation to ( p, q, r) = (2 , 2, r ) (dihedralcase), ( p, q, r) = (2 , 3, 3) (tetrahedral case), ( p, q, r) = (2 , 3, 4) (octahedralcase), and ( p, q, r) = (2 , 3, 5) (icosahedral case), because they correspondto the nite subgroups of P SL 2(C).

Two totally different methods to treat the elliptic case. The rst is againfactoring over suitable number elds (never very large). The proofs aretedious and in the notes for some dihedral cases (very easy), and theoctahedral case ( p, q, r) = (2 , 4, 3). In the latter we only use Z[i] by writingx2 + y4 = z3 as (x + y2 i)(x y2 i) = z3 . One obtains exactly four disjointhomogeneous 2-variable parametrizations of the coprime solutions.Existence not surprising, their disjointness (i.e., any coprime solution isrepresented by a single parametrization) more surprising.


47/82

T S F p + q r (IV)


48/82

T HE SUPER -F ERMAT EQUATION x p + y q = z r (IV)

x = (s4 + 12 t4)( s8 408t4s4 + 144 t8)y = 6 ts (s4 12t4)z = s8 + 168 t4s4 + 144 t8 ,

with s odd and 3 s .

x =

2(s4 + 2 ts 3 + 6 t2s2 + 2 t3s + t4)(23s8

16ts 7

172t2s6

112t3s5

22t4s4 112t5s3 172t6s2 16t7s + 23 t8)y = 3( s t)(s + t)( s4 + 8 ts 3 + 6 t2s2 + 8 t3s + t4)z = 13 s8 + 16 ts 7 + 28 t2s6 + 112 t3s5 + 238 t4s4

+ 112 t5s3 + 28 t6s2 + 16 t7s + 13 t8 ,

with s t (mod 2) and s t (mod 3) .


49/82

THE SUPER -F ERMAT EQUATION x p + yq = z r (V)

The factoring method works in all elliptic cases except in the icosahedralcase ( p, q, r) = (2 , 3, 5). Here we must use a completely different tool(applicable also in the other elliptic cases), invented in this context byF. Klein , but reinterpreted in modern terms by Grothendieck and Belyi , thetheory of dessins denfants . This is a term coined by Grothendieck todescribe coverings of P1(C) ramied in at most 3 points. Using this, obtainin an algorithmic manner complex polynomials P , Q, and R(homogeneous in two variables) such that (for instance) P 2 + Q3 = R5 .These polynomials can in fact be chosen with coefcients in a numbereld , and by making P SL 2(C) act on them and introducing a suitable

reduction theory , can nd all parametrizations. Program initiated byF. Beukers and nished by his student J. Edwards (27 disjointparametrizations).


50/82

INTRODUCTION TO ELLIPTIC C URVES (I)

A very important set of Diophantine equations is the search for rationalpoints (or sometimes integral points ) on curves . Curves are best classiedby their genus , related to the degree. Example: a nonsingular plane curve of degree d has genus g = ( d 1)(d 2)/ 2 (so g = 0 for lines and conics,g = 1 for plane cubics, g = 3 for plane quartics). A hyperelliptic curve

y2

= f (x) where f has degree d and no multiple roots has genusg = (d 1)/ 2 (so g = 0 for d = 1 or 2, g = 1 for d = 3 or 4, g = 2 ford = 5 or 6.

An elliptic curve E over some eld K is a curve of genus 1, together with aK -rational point.

INTRODUCTION TO ELLIPTIC C URVES (II)


51/82

Study of elliptic curves important for many reasons: curves of genus zerovery well understood (everything algorithmic). curves of genus g 2 verydifcult to handle; in addition, elliptic curves have a very rich structure ,coming in particular from the fact that they have a natural group law .

Reminder on elliptic curves:

In practice, an elliptic curve can be given by equations . The simplest is asa simple Weierstrass equation y2 = x3 + ax 2 + bx + c, or a generalized

Weierstrass equation y2

+ a1xy + a3y = x3

+ a2x2

+ a4x + a6 (canonicalnumbering), together with the condition that the curve be nonsingular. Moregenerally nonsingular plane cubic with rational point, hyperelliptic quarticwith square leading coefcient y2 = a2x4 + bx3 + cx2 + dx + e,

intersection of two quadrics, and so on. All these other realizations canalgorithmically be transformed into Weierstrass form, so we will assumefrom now on that this is the case.


52/82

INTRODUCTION TO ELLIPTIC C URVES (III)

Set of projective points of an elliptic curve (if y2 = x3 + ax 2 + bx + c,afne points plus the point at innity

O= (0 : 1 : 0)) form an abelian

group under the secant and tangent method of Fermat (brief explanation: if P and Q are distinct points on the curve, draw the line joining P and Q; itmeets the curve in a third point R , and P + Q is the symmetrical point of R

with respect to the x-axis. If P = Q, do the same with the tangent).Warning : if equation of elliptic curve is not a plane cubic, the geometricconstruction of the group law must be modied.

If K = C, E (C) in canonical bijection with a quotient C/ , where is alattice of C, thanks to the Weierstrass function and its derivative.


53/82

INTRODUCTION TO E LLIPTIC C URVES (IV)

If K = Fq , important Hasse bound |E (Fq) (q + 1) | 2 q . Essentialin particular in cryptography.

If K = Q p (or a nite extension), we have a good understanding of

E (Q p) thanks in particular to Kodaira , Neron , and Tate .

And what if K = Q (or a number eld)? Most interesting, and mostdifcult case. Deserves a theorem to itself.


54/82

INTRODUCTION TO ELLIPTIC C URVES (V)This is the theorem of Mordell , generalized by Weil to number elds and toAbelian varieties.

Theorem . If E is an elliptic curve over a number eld K , the group E (K )is a nitely generated abelian group (the MordellWeil group of E over K ).

Thus E (K ) E (K )tors Zr

, with E (K )tors a nite group, and r is calledthe rank of E (K ). E (K )tors is easily and algorithmically computable, andonly a nite number of possibilities for it, known for instance for K = Q bya difcult theorem of Mazur .

One of the major unsolved problems on elliptic curves is to computealgorithmically the rank r , together with a system of generators .


55/82

INTRODUCTION TO E LLIPTIC C URVES (VI)

Goal of the rest of the course: explain methods to compute E (Q), eitherrigorously, or heuristically. There is no general algorithm, but only partialones, which luckily work in most cases. Sample techniques:

2-descent , with or without a rational 2-torsion point

3-descent with rational torsion subgroup (more general descents possible,but for the moment not very practical, work in progress of a lot of people,some present here).


56/82

INTRODUCTION TO ELLIPTIC C URVES (VII)

Use of L-functions to compute the rank, but not the generators.The Heegner point method , one of the most beautiful and amazing aspectsof this subject, important both in theory and in practice, applicable to rank

1 curves, which should form the vast majority of curves of nonzero rank, theonly ones where we must work. This is also the subject of the studentproject.


57/82

2-D ESCENT WITHOUT 2-TORSION POINT (I)

The general idea of descent , initiated by Fermat, is to map a (possibly large)

point on a given curve (or more general variety) to smaller points on othercurves. Here smaller means that the number of digits is divided by somek > 1, so it is very efcient when applicable.

The simplest is 2-descent on an elliptic curve when there exists a rational2-torsion point (see text). We study the slightly more complicated casewhere such a point does not exist. In other words, let y2 = x3 + ax + b,where we assume a and b in Z and x3 + ax + b = 0 without rational roots,

hence irreducible over Q. Denote by a root, and set K = Q().


58/82

2-D ESCENT WITHOUT 2-TORSION POINT (II)

Dene the map from E (Q) to K /K 2

by (O) = 1 and((x, y)) = x modulo K 2 . Fundamental result, easy to prove usingdenition of group law by secant and tangent:

Proposition . is a group homomorphism whose kernel is equal to 2E (Q). In particular, it induces an injective homomorphism from E (Q)/ 2E (Q) toK /K 2 , and the rank r of E (Q) is equal to dimF 2 (Im ( )) .

(Note that we assume no 2-torsion.)


59/82

2-D ESCENT WITHOUT 2-TORSION POINT (III)

Thus describe Im ( ). For this need T -Selmer group of a number eld (notof the elliptic curve).

T nite set of prime ideals of K .U T (K ) group of T -units u of K (vp (u) = 0 for p / T ).

ClT (K ) T -class group, equal to Cl(K )/ < T > with evident notation.A T -virtual square u K is such that 2 | vp (u) for all p / T .

The T -Selmer group S T (K ) is the quotient of the group of T -virtual

squares by the group K 2 of nonzero squares.


60/82

2-D ESCENT WITHOUT 2-TORSION POINT (IV)We have S T (K ) (U T (K )/U T (K )2) ClT (K )[2], so easily computableusing a computer algebra system.

Basic result linking Im ( ) with S T (K ) (not difcult):Proposition . Let T be the set of prime ideals q such that q | 32 + a and q | [ZK : Z[]] , where q prime number below q. Then Im ( ) is equal to thegroup of u S T (K ) such that N K/ Q (u) (for any lift u) is a square in Qand such that there exists a lift u of the form x .Sometimes [ZK : Z[]] = 1 so T = (but S T (K ) may still be nontrivial).

The condition on the norm is algorithmic. Unfortunately the existence of alift u of the form x is not (but luckily feasible in many cases).


61/82

2-D ESCENT WITHOUT 2-TORSION POINT (V)So let G the group of u S T (K ) whose lifts have square norm. Todetermine if u has a lift x : write u = u22 + u1 + u0 for any lift,u i Q. All lifts are of the form u 2 for = c22 + c1 + c0 , and

u 2 = q 2(c0 , c1 , c2)2 q 1(c0 , c1 , c2) + q 0(c0 , c1 , c2) ,with q i explicit quadratic forms . Condition reads q 2(c0 , c1 , c2) = 0 andq 1(c0 , c1 , c2) = 1 . The rst equation can be checked for solubility byHasseMinkowski (local-global principle for quadratic form), and thenparametrized by quadratic forms in two variables (as super-Fermat

equation). Replacing in second equation gives quartic , anddehomogenenizing gives a hyperelliptic quartic equation y2 = Q(x).

2-D ESCENT WITHOUT 2-TORSION POINT (VI)


62/82

( )

If not everywhere locally soluble, can again exclude u . Otherwise search forsolutions. If found, u Im ( ), if not we are stuck.

The group of u S T (K ) for which the corresponding quartic iseverywhere locally soluble is called the 2-Selmer group of the ellipticcurve , and is the smallest group containing E (Q)/ 2E (Q) which can bedetermined algorithmically using 2-descent. It is denoted S 2(E ). Thequotient of S 2(E ) by the (a priori unknown) subgroup E (Q)/ 2E (Q) is theobstruction to 2-descent, and is equal to X (E )[2], the part of theTateShafarevitch group of E killed by 2.

2-descent quite powerful, basis of Cremonas mwrank program. If fails,can try a second descent (solve the quartics), or a 3-descent or higher.

Exercise : try your 2-descent skills for y2 = x3 16 (both have rank 0).

3 ( )


63/82

E XAMPLE OF 3-D ESCENT (I)

Not difcult but too long to explain, so we give an interesting example.

Goal : given nonzero integers a , b, and c, determine if there exists a

nontrivial solution to ax3

+ by3

+ cz3

= 0 .As usual, easy to give condition for everywhere local solubility (see text).

To go further, for any n Z1 let E n be the elliptic curve y2 = x3 + n2 .

The point T = (0 , n ) is torsion of order 3. We dene a 3-descent map from E (Q) to Q / Q 3 by setting (O) = 1 , (T ) = 4 n2 , and otherwise((x, y)) = y n , all modulo cubes. Easy direct check that is a grouphomomorphism , kernel easy to compute (not needed here).

Projective curve C= Ca,b,c with equation ax 3 + by3 + cz3 = 0 closelylinked to curve E = E 4abc as follows.


64/82

EXAMPLE OF 3-D ESCENT (II)

Proposition . Dene (x,y,z ) = ( 4abcxyz, 4abc(by3 cz3), ax 3).1. The map sends C(Q) into E (Q) (in projective coordinates).2. Let G = {(X,Y,Z )} E (Q) such that c(Y 4abcZ ) = bZ3 for some Q . Then Im () = (C(Q)) is equal to G together with Oif

c/b Q 3 , and T if b/a Q 3 (and immediate to give preimages).

3. The set C(Q) is nonempty if and only if b/c modulo cubes belongs toIm ( ) Q / Q 3 .Proof: (1) and (2) are simple verications. For (3), C(Q) = iff Im () = ,hence iff either there exists (X,Y,Z ) E (Q) and Q withc(Y 4abcZ ) = bZ3 , or if c/b or b/a are cubes. Note = 2 cz/x . Thiseasily implies that b/c Im( ).


65/82

E XAMPLE OF 3-D ESCENT (III)

Thus, to test solubility of ax

3 +by

3 +cz

3 = 0 , proceed as follows. First testeverywhere local solubility (easy). Then compute the MordellWeil groupE (Q) using 2-descent and/or a software package like Cremonas mwrank(of course may be difcult), also torsion subgroup (easy). If (P i )1irbasis of free part, then classes modulo 3E (Q) of P 0 = T and the P i forman F3 -basis of E (Q)/ 3E (Q). Then check if b/c modulo cubes belongs tothe group generated by the ( (P i ))0ir in Q / Q

3 , simple linear algebraover F3 . Completely algorithmic, apart from the MW computations.


66/82

E XAMPLE OF 3-D ESCENT (IV)

Examples :

x3 + 55 y3 + 66 z3 = 0 . Everywhere locally soluble, cannot solvealgebraically as far as I know. Use above method. Find torsion subgroup of order 3 generated by P 0 = T = (0 , 14520). In a fraction of a second,mwrank (or 2-descent) says rank 1 and a generator P 1 = (504 , 18408).Then modulo cubes (P 0) = 2 2 32 52 11 and (P 1) = 2 32 , whileb/c = 2 2 32 5. Linear algebra immediately shows b/c not in groupgenerated by (P 0) and (P 1), so no solution.


67/82

EXAMPLE OF 3-D ESCENT (V)

Descent not always negative: x3 + 17 y3 + 41 z3 = 0 . Torsion subgroup of order 3 generated by P

0= T = (0 , 2788). Rank 1 and generator P

1=

(355278000385/ 2600388036, 426054577925356417/ 132604187507784).Modulo cubes (P 0) = 17 2 .412 , (P 1) = 17 2 , and b/c = 17 412 , so since group homomorphism, (P 0 + P 1) = b/c modulo cubes. Find in

projective coordinates P 0 + P 1 = ( X,Y,Z ) =(5942391203335522320, 251765584367435734052, 3314947244332625),compute such that c(Y 4abcZ ) = bZ3 , nd = 8363016 / 149105.Since = 2 cz/x , nd (up to projective scaling) z = 101988 , x = 149105 ,hence y = 140161 .


68/82

THE USE OF L (E, s ) (I)Extremely important method which at least determines whether or not E has nontorsion points, without giving them.

Denition of L(E, s ). Assume minimal Weierstrass equation over Q. If E has good reduction at p, dene a p = p + 1 |E (F p)| and ( p) = 1 .Otherwise dene ( p) = 0 , and a p = 0 if triple point (additive reduction ),a p = 1 or a p =

1 if double point with or without rational tangents ( split

or nonsplit multiplicative reduction ). In fact a p = p + 1 |E (F p)| still true.Then

L(E, s ) =

p

11

a p ps + ( p) p12s

,

converges for (s) > 3/ 2 because of Hasse bound |a p| 2 p1/ 2 .

THE USE OF L (E, s ) (II)

M t i t t th d t Wil T l Wil t l L(E s )


69/82

Most important theorem, due to Wiles , TaylorWiles , et al.: L(E, s )extends to a holomorphic function to the whole complex plane, satisfying afunctional equation

(E, 2

s) = (E )(E, s ) ,

with (E ) = 1 (the root number ), and(E, s ) = N s/ 2(2)s (s)L(E, s ). Here N is the conductor , divisible byall bad primes and easily computable by Tates algorithm .

Because of BSD, are interested in the value L(E, 1). If (E ) = 1,trivially L(E, 1) = 0 . Otherwise, automatic consequence , we have theexponentially convergent (so easy to compute ) series

L(E, 1) = 2n 1

ann

e2n/ N .


70/82

THE USE OF L (E, s ) (III)The Birch and Swinnerton-Dyer conjecture : precise statement, but tellsus in particular that there exist nontorsion points in E (Q) (i.e., E (Q)

innite) if and only if L(E, 1) = 0 . Unfortunately, except in the rank 1 case(Heegner point method ) does not help us much in nding the points.

What is known ( Rubin, Kolyvagin, etc... ):

If L(E, 1) = 0 then no nontorsion points. If L(E, 1) = 0 but L(E, 1) = 0 then rank 1, in particular existsnontorsion points, and can be found using Heegner points.

On the other hand, if L(E, 1) = L(E, 1) = 0 , nothing known, althoughBSD conjecture says rank at least 2.


71/82

T HE H EEGNER POINT METHOD (II)


72/82

Modular parametrization : Wiless theorem is equivalent tof E ( ) = n 1 an q

n (q = exp(2 i )) is a modular form of weight 2 on0(N ). Equivalently still, 2if E ( )d is a holomorphic differential ,invariant under 0(N ) up to the period lattice of f E , i.e.,

( ) = 2 i

if E (z) dz =

n 1ann

q n

does not depend on chosen path, and denes map from

H/ 0(N ) to C/ ,

easily extended to map from closure X 0(N ) to C/ , where latticegenerated by 2i

i f E

(z) dz , with Q a cusp . Usually (alwayshappens in practice, if not can easily be dealt with) have E , with

E (C) = C/ E , so get a map from X 0(N ) to C/ E , and composing withthe Weierstrass function , get map from X 0(N ) to E (C), the modularparametrization . Wiles: exists and unique up to sign.


73/82

THE H EEGNER POINT METHOD (III)

Complex multiplication (CM) : say is a CM point if H is a root of quadratic equation AX

2

+ BX + C = 0 with A, B , C integral withB 2 4AC < 0. Make this unique by requiring gcd(A,B,C ) = 1 andA > 0, then set ( ) = B 2 4AC .Basic result of CM (in our context): if is a suitable CM point, then

( ) E (H ) and not only ( ) E (C), where H is the Hilbert class eldof K = Q( D ). This is the magic of CM: create algebraic numbers usinganalytic functions ( Kroneckers dream of youth : do this for other number

elds).


74/82

THE H EEGNER POINT METHOD (IV)

Assume for simplicity D = ( ) discriminant of a quadratic eld(fundamental discriminant ).

Denition : Given N , is a Heegner point of level N if it satises theequivalent conditions:

( N ) = ( )N | A and gcd(A/N,B,CN ) = 1

N

|A and D

B 2 (mod 4N ).


75/82

T HE H EEGNER POINT METHOD (V)

Basic properties :

Let Heegner point of level N . If 0(N ) then ( ),

W ( ) = 1/ (N ), and more generally W Q ( ) (AtkinLehner operators )are again Heegner points of level N .

Recall natural correspondence between SL 2(Z) classes of binary

quadratic forms and the ideal class group of corresponding quadratic eld.This easily generalizes to 0(N )-equivalence as follows: naturalcorrespondence between 0(N )-equivalence classes of Heegner points of discriminant D and level N and the set of pairs (, [a]), with [a] ideal class,and Z/ 2N Z such that 2 D (mod 4N ).

THE H EEGNER POINT METHOD (VI)


76/82

( )

Main theorem of CM : Let = ( , [ ]) Heegner point of discriminant D(fundamental) and level N , K = Q( D ), H Hilbert class eld of K (maximal unramied Abelian extension of K , Gal( H/K ) Cl(K )through the Artin map Art ). Recall modular parametrization fromX 0(N ) to E . Then:

( ) E (H ) (algebraicity ) If [b] Cl(K ) then ( Shimura reciprocity ):

((, [a]))Art([ b ]) = ((, [ab 1]))

Also formula for (W ((, [a]))) and (W Q ((, [a]))) .

((, [a]1)) = ((, [a])).


77/82

T HE H EEGNER POINT METHOD (VII)

Consequence : Can compute the trace of ( ) on the elliptic curve by

P = Gal( H/K )

((, [a])) =[b ] Cl (K )

((, [ab 1])) =[b ] Cl (K )

((, [b])) ,

the sum being computed with the group law of E . By Galois theory wewill have P E (K ), so we have considerably reduced the eld of denition of the algebraic point on E . In addition, easy result:

If (E ) = 1 (which is our case since rank 1), then in fact P E (Q),which is what we want.


78/82

T HE H EEGNER POINT METHOD (VII)Thanks in particular to GrossZagier and Kolyvagin , know that P isnontorsion if and only if r = 1 (already known) and L(E D , 1) = 0 , where

E D is the quadratic twist of E by D (equation Dy2

= x3

+ ax + b).Point P often large multiple of generator, can reduce it considerably againby using GrossZagier. Get very nice algorithm.

Example : congruent number problem for n = 157 , curvey2 = x3 1572x. Rank 1. Already reasonably large example. In a coupleof minutes, nd P = ( x, y) with numerator and denominator of x having upto 36 decimal digits.

For details on all of this, see student presentation.


79/82

C OMPUTATION OF INTEGRAL POINTS (I)

Assume now that MordellWeil group E (Q) computed, say (P i )1irgenerators.

Goal : compute E (Z), i.e., integral points . Immediate warning: depends onthe chosen model , contrary to E (Q).

If P E (Z) E (Q), can write P = T + 1

i

r x i P i with x i Z and T

a torsion point. Easy result is |x| c1ec2 H 2

, with H = max i |x i | and c1 , c2easily computable explicit constants.

Now use elliptic logarithm (E (C) C/ , and maps P E (C) toz C modulo such that ( (z), (z)) = P ).


80/82

C OMPUTATION OF INTEGRAL POINTS (II)

Consequence of above: easy to show that if |x| c3 explicit, then

|(P )| c5ec2 H 2 / 2 (if we choose

(P )as small as possible.

On the other hand, thanks to a very important theorem of S. David on linearforms in elliptic logarithms , generalizing Baker-type results to the ellipticcase, can prove that we have an inequality for (P ) in the other direction,which contradicts the above for H sufciently large. Every constantexplicit . Thus get upper bound for H , and as usual in Baker-typeestimates, very large. Typically nd H 10100 (recallP = T + 1ir x i P i and H = max i |x i |).


81/82

C OMPUTATION OF INTEGRAL POINTS (II)

In the above, essential that Baker bounds be explicit , but not essential thatthey be sharp (e.g., 1080 or 10100 is just as good), because now we use themagic of the LLL algorithm: nd small vectors in lattices, and this allowsyou either to nd linear dependence relations between complex numbers, orto show that if an approximate relation exists then coefcients are boundedvery effectively. Roughly obtain a logarithmic decrease in the size of theupper bound.


82/82

C OMPUTATION OF INTEGRAL POINTS (III)

Example : y2 + y = x3 7x + 6 , famous curve because elliptic curve withsmallest conductor of rank 3, important in obtaining effective lower boundsfor the class number of imaginary quadratic elds ( Goldfeld,GrossZagier ). Using Davids bounds, nd H 1060 . Using LLL once,reduce this spectacularly to H 51. Using LLL a second time, reduce thisto

H 11(diminishing returns: another LLL gives

10, then no

improvement). Now a direct search very easy (less than 10000 trials), andnd exactly 36 integral points, a very large number.

Phenomenon not completely understood: elliptic curve of high rank withrespect to conductor have many integral points.

Documents

Diophantine Cohen Lectures