S(cid:19)eminaire BOURBAKI Novembre 2002 55e ann(cid:19)ee, 2002-2003,no 909, p. 1 a(cid:18) 26 CATALAN’S CONJECTURE [after Mih(cid:21)ailescu] by Yuri F. BILU To E.W. 1. INTRODUCTION In 1844 Crelle’s journal published the following note [13]. Note extraited’unelettreadress(cid:19)eea(cid:18)l’(cid:19)editeurparMr. E. Catalan,R(cid:19)ep(cid:19)etiteura(cid:18) l’(cid:19)ecolepolytechnique deParis. Je vous prie, Monsieur, de vouloir bien (cid:19)enoncer, dans votre recueil, le th(cid:19)eor(cid:18)eme suivant,quejecrois vrai,bienqueje n’aiepas encorer(cid:19)eussi a(cid:18) le d(cid:19)emontrercompl(cid:18)etement : d’autres serontpeut-^etreplusheureux: Deuxnombresentierscons(cid:19)ecutifs, autresque8et9,nepeuvent^etre des puissances exactes ; autrement dit : l’(cid:19)equation xm(cid:0)yn =1, dans laquelle les inconnues sont enti(cid:18)eres et positives, n’admet qu’une seule solution. Thus, we have the following conjecture. Conjecture 1.1 (Catalan). | Equation xu yv =1 has no solutions in integers (cid:0) x;y;u;v >1 other than 32 23 =1. (cid:0) Now,158yearsafter,theconjectureiscompletelyproved. Letusbrie(cid:13)yreviewthe most important events which lead to the solution of this celebrated problem. This is not a comprehensivehistoricalaccountof Catalan’sproblem;the lattercanbe found in Ribenboim’s book [34] and Mignotte’s survey [26]. Seven years after Catalan’s note appeared, Lebesgue [21] proved that equation xm y2 =1 has no solutions in positive integers x;y;m with m>1. In 1965 Ko (cid:0) Chao[18]showedthatequationx2 yn =1hasnosolutionsinpositiveintegersx;y;n (cid:0) with n>1 other than 32 23 =1. These two results reduce Catalan’s conjecture to (cid:0) the following assertion. SOCIE(cid:19)TE(cid:19)MATHE(cid:19)MATIQUEDEFRANCE2004 2 Y.F. BILU Conjecture 1.2. | Equation (1) xp yq =1 (cid:0) has no solutions in non-zero integers x;y and odd primes p;q. Notice that we no longer assume x and y positive. It is convenient, because now the problem is symmetric: if (x;y;p;q) is a solution, then so is ( y; x;q;p). This (cid:0) (cid:0) will be repeatedly used in the sequel. From now on Conjecture 1.2 will be referred to as Catalan’s conjecture and (1) as Catalan’s equation. Cassels [12] discovered important arithmetical properties of solutions of Catalan’s equation. Hisresults(seeProposition2.1)areindispensableinmostofthesubsequent works on Catalan’s equation. In1976Tijdeman [37]madeabreakthrough. UsingBaker’stheory,heprovedthat the exponents p and q are bounded by an explicit absolute constant. Together with theclassicalresultofBaker[6]thisimpliesthat x and y areboundedbyanexplicit j j j j absolute constant as well, and Catalan’s problem is thereby decidable. In a di(cid:11)erent direction, Inkeri [16,17] and others obtained algebraic criteria of solubility of (1) in terms of the exponents p and q. In the nineties, Mignotte and Roy used Inkeri-type criteria, Tijdeman’s argument and electronic computations to obtain tight lower and upper bounds for p and q. (Upper bounds were also obtained by Blass et al. [10] and O’Neil [32].) By 2000, it was provedthat p and q lie between 107 and 1018. See [29] for more precise results and a survey of this period. In 1999 Preda Miha(cid:21)ilescu enters the scene. In his (cid:12)rst paper [29] he drastically re(cid:12)ned Inkeri’s criterion. And quite recently, after several unsuccessful attempts, he (cid:12)nally settled [30] Catalan’s conjecture: Theorem 1.3 (Miha(cid:21)ilescu). | Conjecture 1.2 is true. The present paper contains a reasonablyself-contained proof of this result. Plan of the paper. | InSection 2we recallCassels’relationsand derive theirimme- diateconsequence,inparticular,Hyyr(cid:127)o’slowerboundsfor x and y . InSection3we j j j j very brie(cid:13)y review algebraic criteria for Catalan’s equation in terms of p and q, and proveMiha(cid:21)ilescu’s\doubleWieferich"criterion. InSection4weusebinarylogarithmic forms, Tijdeman’s argument, and computations by Mignotte and Roy to show that p 1modq. Section5containsgenerallemmas. InSection6Theorem1.3isreduced 6(cid:17) to three more technical statements, which are proved in the three (cid:12)nal section. ASTE(cid:19)RISQUE294 (909) CATALAN’S CONJECTURE 3 Acknowledgements. | My deepest gratitude goes to Hendrik W. Lenstra and Yann Bugeaud,whocarefullyreadthemanuscriptandsuggestednumerouscorrectionsand improvements. I am indebted to Yann Bugeaud, Andrew Glass, Guillaume Hanrot, Maurice Mignotte and Preda Miha(cid:21)ilescu for explaining to me various results from Sections 2 and 4 and other useful discussions. I also thank Bruno Angl(cid:18)es, John Coates, Gabi Hecke, Shanta Laishram, Hendrik W. Lenstra, Tauno Mets(cid:127)ankyl(cid:127)a and GisbertWu(cid:127)stholz,whodetectedinaccuraciesinpreviousversionsofthisnote. Finally, I thank Denis Benois and Leonid Positselski for a tutorial in commutative algebra. 1.1. Notation In the sequel we assume, unless the contrary is indicated explicitly, that x;y are non-zero integers and p;q are odd prime numbers satisfying (2) xp yq =1: (cid:0) Aswehadalreadynoticed,(2)impliesthat( y)q ( x)p =1,andallthestatements (cid:0) (cid:0) (cid:0) below remain true with x;y;p;q replaced by y; x;q;p. (cid:0) (cid:0) We denote by (cid:16) a primitive p-th root of unity and put K =Q((cid:16)); G=Gal(K=Q): The principal ideal (1 (cid:16)) will be denoted by p. Recall that it is a prime ideal of K (cid:0) and that (p)=pp(cid:0)1. More speci(cid:12)c notation will be introduced at the appropriate places. 2. CASSELS’ RELATIONS AND LOWER ESTIMATES FOR x j j AND y j j Cassels [12] proved that q x and py. More precisely, he established the following j j relations. Proposition 2.1 (Cassels). | There exist a non-zero integer a and a positive inte- ger v such that (3) x 1=pq(cid:0)1aq; y=pav; (cid:0) xp 1 (4) (cid:0) =pvq; x 1 (cid:0) and, symmetrically, there exist a non-zero integer b and a positive integer u such that (5) y+1=qp(cid:0)1bp; x=qub; yq +1 (6) =qup: y+1 SOCIE(cid:19)TE(cid:19)MATHE(cid:19)MATIQUEDEFRANCE2004 4 Y.F. BILU The following consequence is crucial. Corollary 2.2. | The number (cid:21):=(x (cid:16))=(1 (cid:16)) is an algebraic integer. The (cid:0) (cid:0) principal ideal ((cid:21)) is a q-th power of an ideal of the (cid:12)eld K. Proof. | Sincep(x 1)by(3),theprimeidealp=(1 (cid:16))dividesx (cid:16),butp2 does j (cid:0) (cid:0) (cid:0) not. Hence (cid:21) is an algebraic integer, not divisible by p, and the same is true for its conjugates(cid:21)(cid:27),where(cid:27) G. Identity(1 (cid:16)(cid:27))(cid:21)(cid:27) (1 (cid:16)(cid:28))(cid:21)(cid:28) =(cid:16)(cid:28) (cid:16)(cid:27) impliesthat 2 (cid:0) (cid:0) (cid:0) (cid:0) fordistinct(cid:27);(cid:28) G,thegreatestcommondivisorof(cid:21)(cid:27) and(cid:21)(cid:28) divides((cid:16)(cid:28) (cid:16)(cid:27))=p. 2 (cid:0) Hence the numbers (cid:21)(cid:27) are pairwise co-prime. Now rewrite (4) as (cid:21)(cid:27) =vq. Since the factors are pairwise co-prime, each (cid:27)2G principal ideal ((cid:21)(cid:27)) is aQq-th power of an ideal. Cassels’ relations imply various lower estimates for the variables x and y in terms of p and q. For instance, (3) and (5) immediately yield (7) x >pq(cid:0)1 1; j j (cid:0) (8) y >qp(cid:0)1 1; j j (cid:0) and this can be re(cid:12)ned without much e(cid:11)ort. Hyyr(cid:127)o [15] obtained an estimate of a di(cid:11)erent kind: x >q(2p+1)(2qp(cid:0)1+1) j j (and similarly for y ). Since Hyyr(cid:127)o’s paper is not easily available, I prove below a j j slightly weaker estimate, which is totally su(cid:14)cient for our purposes. It is an easy consequence of the following proposition. Proposition 2.3. | If p does not divide q 1 then qp(cid:0)2 (u 1). (cid:0) (cid:0) (cid:12) (cid:12) Proof. | Rewriting (6) as ( y)q(cid:0)1 1 + ( y)q(cid:0)2 1 + +( y 1)=q(up 1); (cid:0) (cid:0) (cid:0) (cid:0) (cid:1)(cid:1)(cid:1) (cid:0) (cid:0) (cid:0) (cid:0) (cid:1) (cid:0) (cid:1) we deduce that (y+1) (q(up 1)). Now (5) implies that up 1modqp(cid:0)2. Since p j (cid:0) (cid:17) does not divide the order qp(cid:0)3(q 1) of the multiplicative group modqp(cid:0)2, this im- (cid:0) plies that u 1modqp(cid:0)2. (cid:17) Corollary 2.4. | We have x >qp(cid:0)1. j j Proof. | If p(q 1) then p<q and the result follows from (7). If p does not di- j (cid:0) videq 1then qp(cid:0)2 (u 1),and,sinceuispositive,thisimpliesu>qp(cid:0)2+1. Since (cid:0) (cid:0) x=qub, we have x(cid:12)>qu>qp(cid:0)1+q, better than wanted. j j(cid:12) Remark 2.5. | This version of Hyyr(cid:127)o’s argument is due to Mignotte and Bugeaud. It was kindly communicated to me by Yann Bugeaud. Using more advanced tools, Miha(cid:21)ilescu [30, Appendix A] obtained a much sharper estimate x > q2p(cid:0)2=2 4. j j (cid:0) (cid:1) ASTE(cid:19)RISQUE294 (909) CATALAN’S CONJECTURE 5 3. ALGEBRAIC CRITERIA Using Cassels’ relations and some algebraic number theory, one may get various algebraic criteria of solvability of Catalan’s equation with given exponents p and q. The most famous criterion is due to Inkeri [16,17]: Theorem 3.1 (Inkeri). | With the notation of Subsection 1.1, put K =Q(p p) p (cid:0) if p 3mod4 and K =K if p 1mod4. Then either pq(cid:0)1 1modq2 or q divides p (cid:17) (cid:17) (cid:17) the class number of the (cid:12)eld K . p It will be explained in Subsection 4.4 how algebraic criteria of this kind, together with electronic computations, allow one to obtain lowerbounds for p and q. Re(cid:12)nements of and supplements for Inkeri’s criterion were suggested by Mignotte [25], Schwarz [35] and others; see [26] for a survey of these results. I would es- pecially mention the paper by Bugeaud and Hanrot [11], which strongly in(cid:13)uenced Miha(cid:21)ilescu’s work. Veri(cid:12)cation of Inkeri’s criterion for a given pair (p;q) requires computing certain class numbers, which seriously a(cid:11)ects its computational e(cid:14)ciency. Miha(cid:21)ilescu [29] madeamajorstepforward,showingthatthe classnumberconditioncanbe omitted. Theorem 3.2 (Miha(cid:21)ilescu). | For any solution of (x;y;p;q) of (2) we have q2 x j and (9) pq(cid:0)1 1modq2: (cid:17) Congruence(9)(calledWieferich’s relation)willbeusedinSection4toprovethat p 1modq. Relation q2 x is crucial in the proof of Theorem 6.3.2. 6(cid:17) j By symmetry, one has qp(cid:0)1 1modp2. Pairs (p;q), satisfying this and (9) are (cid:17) called double Wieferich pairs. Only six such pairs are currently known: (2;1093);(3;1006003);(5;1645333507);(83;4871);(911;318917);(2903;18787): I sketch the proof of Theorem 3.2, because it is very instructive and can serve as a goodmodelofthe muchmoreinvolvedproofofTheorem1.3. See[24,33]fordi(cid:11)erent proofs. 3.1. Proof of Theorem 3.2 For a 1;2;:::;p 1 let (cid:27) be the element of G=Gal(K=Q) be de(cid:12)ned by a 2f (cid:0) g (cid:16) (cid:16)a. In the group ring Z[G] consider elements 7! p(cid:0)1 (cid:2) = ac=p (cid:27)(cid:0)1 (c=1;2;:::;p 1): c b c a (cid:0) Xa=1 In particular, (cid:2) =0 and (cid:2) =(cid:27) + +(cid:27) . Ideal =((cid:2) ;(cid:2) ;:::;(cid:2) ) 1 2 (p+1)=2 p(cid:0)1 1 2 p(cid:0)1 (cid:1)(cid:1)(cid:1) I ofZ[G]iscalledtheStickelbergerideal. ItsmainpropertyistheStickelbergertheorem: SOCIE(cid:19)TE(cid:19)MATHE(cid:19)MATIQUEDEFRANCE2004 6 Y.F. BILU any (cid:2) annihilates the class group of K. That is, for any ideal a of K and any 2I (cid:2) , the ideal a(cid:2) is principal. See [39, Section 6.2] for the details. 2I Let(cid:19)=(cid:27) bethecomplexconjugation. Miha(cid:21)ilescuprovesthefollowingassertion. p(cid:0)1 Proposition 3.1.1. | For any (cid:2) (1 (cid:19)) , the element (x (cid:16))(cid:2) is a q-th power 2 (cid:0) I (cid:0) in K. Proof. | Write (cid:2)=(1 (cid:19))(cid:2)0, where (cid:2)0 . Put (cid:21):=(x (cid:16))=(1 (cid:16)). By Corol- (cid:0) 2I (cid:0) (cid:0) lary 2.2 the principal ideal ((cid:21)) is a q-th power: ((cid:21))=aq. By the Stickelberger the- orem a(cid:2)0 is a principal ideal, say, ((cid:11)). It follows that (cid:21)(cid:2)0 =((cid:11))q, or (cid:21)(cid:2)0 =(cid:17)(cid:11)q, (cid:16) (cid:17) where (cid:17) is a unit of K. We obtain 1 (cid:16) (cid:2)0 (cid:17) (cid:11) q (10) (x (cid:16))(cid:2) = (cid:0) : (cid:0) (cid:18)1 (cid:16)(cid:19) (cid:17) (cid:16)(cid:11)(cid:17) (cid:0) Since (cid:17) is a unit, (cid:17)=(cid:17) is a root of unity(1) . The quotient (1 (cid:16))=(1 (cid:16)) is a root of (cid:0) (cid:0) unity as well. Thus, (x (cid:16))(cid:2) is a q-th powertimes a root of unity. Since any root of (cid:0) unity in K is a q-th power, so is (x (cid:16))(cid:2). (cid:0) Proof of q2 x. | Since(1 (cid:16)x)(cid:2) isequalto(x (cid:16))(cid:2) timesarootofunity,itisaq-th j (cid:0) (cid:0) power as well. On the other hand, q x implies that (1 (cid:16)x)(cid:2) 1modq. Since q is j (cid:0) (cid:17) unrami(cid:12)edinK,thisimpliesthat(1 (cid:16)x)(cid:2) 1modq2 (cf. Proposition5.3.1below). (cid:0) (cid:17) However, if (cid:2)= n (cid:27), then a quick calculation shows that (cid:27)2G (cid:27) P (1 (cid:16)x)(cid:2) 1 x n (cid:16)(cid:27)modq2: (cid:27) (cid:0) (cid:17) (cid:0) (cid:27)X2G It follows that either q2 x or q n (cid:16)(cid:27). In the latter case q n for any (cid:27) G. j j (cid:27)2G (cid:27) j (cid:27) 2 However, this is not true if, for iPnstance, (cid:2)=(1 (cid:19))(cid:2) = (cid:27)(cid:0)1 (cid:27)(cid:0)1 +(cid:27)(cid:0)1 + +(cid:27)(cid:0)1 : (cid:0) 2 (cid:0) 1 (cid:0)(cid:1)(cid:1)(cid:1)(cid:0) (p(cid:0)1)=2 (p+1)=2 (cid:1)(cid:1)(cid:1) p(cid:0)1 Thus, q2 x. . j Proof of (9). | This is just an elementary exercise. Since q2 x, the (cid:12)rst equality j in (3) implies that (11) pq(cid:0)1aq 1modq2: (cid:17)(cid:0) Since pq(cid:0)1 1modq, we have aq 1modq, which implies aq 1modq2, which, (cid:17) (cid:17)(cid:0) (cid:17)(cid:0) together with (11), implies (9). (1)Itisanalgebraicinteger,andforany(cid:27)2Gwehavej((cid:17)=(cid:17))(cid:27)j=1 ASTE(cid:19)RISQUE294 (909) CATALAN’S CONJECTURE 7 4. LOGARITHMIC FORMS, TIJDEMAN’S ARGUMENT AND THE RELATION p 1modq 6(cid:17) As I mentioned in the introduction, Tijdeman [37] applied Baker’s theory of logarithmicformtoestablishane(cid:11)ectiveupper boundforthe solutions,reducingthe problem to a (cid:12)nite computation. In this section we use Tijdeman’s argument and electronic computations due to Mignotte and Roy to prove the following important theorem. Theorem 4.1. | Let (x;y;p;q) be a solution of (2). Then p 1modq. 6(cid:17) The relation p 1modq is indispensable for Miha(cid:21)ilescu’s proof. It is repeatedly 6(cid:17) used in Section 6 and in the proof of Theorem 6.3.2. A reader ready to take Theo- rem 4.1 for granted may skip the rest of this section. Whenwritingthissection,Ipro(cid:12)tedalotfromhelpfulexplanationsandsuggestions of Maurice Mignotte and Andrew Glass. 4.1. Logarithmic forms In this subsection we recall Baker’s lower bound for logarithmic forms (cid:3)=b log(cid:11) + +b log(cid:11) : 1 1 n n (cid:1)(cid:1)(cid:1) Here b ;:::;b are non-zero integers and (cid:11) ;:::;(cid:11) are usually algebraic numbers. 1 n 1 n To avoid unnecessary technicalities, we shall assume that (cid:11) ;:::;(cid:11) are positive ra- 1 n tional numbers, distinct from 1. Thisistotallysu(cid:14)cientforapplicationsinCatalan’s problem. De(cid:12)netheheightofarationalnumber(cid:11)=(cid:22)=(cid:23) (where(cid:22)and(cid:23) arerelativelyprime integers) by h((cid:11))=logmax (cid:22); (cid:23) . Assume that (cid:3)=0. Then it is rather easy to fj j j jg 6 bound (cid:3) frombelow. Indeed,e(cid:3) 1isanon-zerorationalnumberwithdenominator j j (cid:0) bounded by e(h((cid:11)1)+(cid:1)(cid:1)(cid:1)+h((cid:11)n))B, where B =max b ;:::; b : 1 n fj j j jg It follows that (12) (cid:3) e(cid:0)(h((cid:11)1)+(cid:1)(cid:1)(cid:1)+h((cid:11)n))B; j j(cid:29) where here and below in this subsection the positive constants implied by O(), (cid:1) and are absolute and e(cid:11)ective. (cid:28) (cid:29) However,(12)istooweakforapplications: oneneedso(B)intheexponent. Suchan estimatewasobtainedbyGelfond[14]forn=2andbyBaker[2{5]inthegeneralcase. Baker’sinequality belongs to the top arithmetical results of the twentieth century. The modern estimate [7,22,23,38]is of the form (13) (cid:3) >e(cid:0)c(n)h((cid:11)1)(cid:1)(cid:1)(cid:1)h((cid:11)n)logB j j SOCIE(cid:19)TE(cid:19)MATHE(cid:19)MATIQUEDEFRANCE2004 8 Y.F. BILU (provided (cid:3)=0.) See the recent volume [40] for the history of the subject and the 6 present state of art. When one wants to be explicit, the numerical value of the constant c(n) becomes vital. For growingn, the best result is due to Matveev [22,23],who showed that one may take c(n)=cn with an explicit absolute constant c. However,inCatalan’sproblemoneuses(13)onlywithn=2andn=3. Therefore itispracticaltohavespecialboundsforthesetwocases,whicharenumericallysharper than the general bound (13). Such bounds were obtained by Laurent, Mignotte and Nesterenko[20]forbinaryformsandbyBennettet al. [8]forternaryforms. Hereisa simpli(cid:12)ed form of the Laurent-Mignotte-Nesterenkoresult (see Corollary 2 from [20, Section 2]), to be used in Subsection 4.3 below. Proposition 4.1.1. | Let (cid:11) ;(cid:11) be multiplicatively independent positive ratio- 1 2 nal numbers and b ;b positive integers. Let A ;A be real numbers satisfying 1 2 1 2 A >max h((cid:11) );1 fori=1;2. PutB =b =A +b =A and(cid:3)=b log(cid:11) b log(cid:11) . i i 1 2 2 1 1 1 2 2 f g (cid:0) Then (14) log (cid:3) > 24:34(max logB+0:14; 21 )2A A : 1 2 j j (cid:0) f g This is asymptotically weaker than (13) when B grows (because logB is replaced by (logB)2), but for small B inequality (14) is very sharp numerically. Idonotformulatethe resultof[8], becauseitisveryinvolvedandwillnotbeused here. 4.2. An informal introduction to Tijdeman’s argument In this subsection we assume that p>q. In Catalan’s problem, the most obvious logarithmic form to try is (cid:3)=plog x qlog y . The upper estimate is obvious: j j(cid:0) j j (cid:3) 6 x(cid:0)p. The lower estimate coming from (13) is (cid:3) >e(cid:0)O(plogjxjlogjyj), and j j j j j j comparing the two estimates does not yield any interesting consequence. Tijdeman’s [37] brilliant idea was to use (cid:3)=qlog y+1 plog x. Upper bound j j(cid:0) j j isnowslightlyworse: (cid:3) q y (cid:0)1. Forthe lowerbound, weuseCassels’relations(6) j(cid:28) j j toobtain(cid:3)=plog(cid:11) qlogq,where(cid:11)=(q b)q(cid:0)1u(cid:0)1(recallthatu>0). Itiseasyto (cid:0) j j show(seeSubsection4.3)thath((cid:11))=log u +O(1)6(q=p)log y +O(1). Now(13) j j j j implies that (cid:3) >e(cid:0)O((q=p)logjyjlogqlogp), which, compared with the lower estimate, j j implies that (15) p qlogqlogp: (cid:28) If (14) is used instead of (13), then one obtains the slightly weaker inequality (16) p qlogq(logp)2: (cid:28) Similarly, using (cid:3)=qlog y+1 plog x 1 =pqlog(cid:12) qlogq+plogp j j(cid:0) j (cid:0) j (cid:0) ASTE(cid:19)RISQUE294 (909) CATALAN’S CONJECTURE 9 with (cid:12) =bq=ap, one obtains the estimate (17) q (logp)2logq: (cid:28) Together with (15) this implies an e(cid:11)ective upper bound for p, as wanted. As I already mentioned in Subsection 4.1, Tijdeman’s argument does not require thefullstrengthofBaker’sinequality. Oneneedsalowerboundforbinarylogarithmic forms to obtain (15) and a lower bound for ternary logarithmic form to obtain (17). Langevin [19] made Tijdeman’s work explicit by proving that p;q 610110. This bound has been re(cid:12)ned several times until O’Neil [32] (see also [10]) proved that p63:2 1017 and q 62:6 1012, and Mignotte [29]announcedthat p67:8 1016 and (cid:1) (cid:1) (cid:1) q 67:2 1011. Mignotte used the already mentioned bounds for binary and ternary (cid:1) logarithmic forms from [20] and [8], respectively. 4.3. Explicit Tijdeman’s inequality InthissubsectionweapplyProposition4.1.1toobtainanexplicitanalogueof(16). Proposition 4.3.1. | For any solution of (2) we have 2 p+1 (18) p624:34q max log +0:14; 21 logq: (cid:18) (cid:26) logq (cid:27)(cid:19) Inequality(18)willbeusedinSubsection4.5. Itislesssharpthanthecorrespond- ing results from [27] and [10], but easier to prove and su(cid:14)cient for our purposes. Proof of Proposition 4.3.1. | We may assume that (19) p>10000qlogq; and, in particular, p>q, since otherwise (18) holds trivially. As indicated in Subsection 4.2, we will compareupper and lowerestimates for the quantity (cid:3)=qlog y+1 plog x =plog(cid:11) qlogq; j j(cid:0) j j (cid:0) with (cid:11)=(q b)q(cid:0)1u(cid:0)1, where b Z and u Z are de(cid:12)ned in Proposition 2.1. >0 j j 2 2 The upper estimate is trivial. Rewriting Catalan’s equation (2) as plog x =qlog y +log(1+y(cid:0)q); j j j j we obtain (20) (cid:3)=qlog 1+y(cid:0)1 log 1+y(cid:0)q : (cid:0) (cid:0) (cid:1) (cid:0) (cid:1) Since log(1+t) 62t for t 61=2, this implies that j j j j j j (21) (cid:3) 62y (cid:0)q+2q y (cid:0)1 63q y (cid:0)1; j j j j j j j j and (cid:3) <1 by (8). Equality (20) implies also that (cid:3)=0: the (cid:12)rst term always j j 6 dominates overthe second one. SOCIE(cid:19)TE(cid:19)MATHE(cid:19)MATIQUEDEFRANCE2004 10 Y.F. BILU For the lower bound, let us estimate h((cid:11)). Since log (q b)q(cid:0)1 =logu+((cid:3)+qlogq)=p6logu+1; j j (cid:0) (cid:1) we have h((cid:11))6logu+1. Also, q and (cid:11) are multiplicatively independent: other- wise, (cid:3) would have been a multiple of logq, contradicting the previously established inequality 0< (cid:3) <1. j j Thus, we are in a position to use Proposition4.1.1. We obtain (22) log (cid:3) > 24:34(max logB+0:14;21 )2(logu+1)logq j j (cid:0) f g with B =p=logq+q=(logu+1). Proposition2.3 and (19) imply that (23) u>qp(cid:0)2 >e9000q(logq)2: Hence B 6(p+1)=logq . Substituting this into (22) and combining the resulting inequality with (21), we obtain 2 log y p+1 1 log(3q) (24) j j 624:34 max log +0:14;21 logq 1+ + : logu (cid:18) (cid:26) logq (cid:27)(cid:19) (cid:18) logu(cid:19) logu Further, (6) implies that q y q(cid:0)1 >qup, whence j j log y (25) p6(q 1) j j (cid:0) logu 2 p+1 1 (q 1)log(3q) 624:34(q 1) max log +0:14; 21 logq 1+ + (cid:0) : (cid:0) (cid:18) (cid:26) logq (cid:27)(cid:19) (cid:18) logu(cid:19) logu Using(19)and(23),oneeasilyshowsthattheright-handsideof(25)doesnotexceed the right-hand side of (18). The proposition is proved. 4.4. Lower bounds for p and q One can bound exponents p and q from below, using algebraic criteria (see Sec- tion3)andelectroniccomputations. ThishasbeenrealizedbyMignotteandRoy[27{ 29]. To show that q >Q , one has to verify an algebraiccriterion (Inkeri’sor other), 0 forallpairs(p;q)satisfyingq 6Q ,p>q and(18). Actually,MignotteandRoyused 0 sharper, than (18), inequalities. With Inkeri-type criteria, Mignotte and Roy managed to provethat (26) min p;q >105; f g using several months of computations. With Miha(cid:21)ilescu’s criterion (Theorem 3.2) this requiredonlya fewhoursof computations,andwith one monthof computations they managed to prove that min p;q >107. I am aware about the computations of f g Granthamand Wheeler showing that min p;q >3:2 108 but I havenever seen this f g (cid:1) result announced in print. Inequality (26) will be used in Subsection 4.5. ASTE(cid:19)RISQUE294