Padua and Pisa are exponentially far apart

Publicacions Matem`atiques, Vol 41 (1997), 631–651. PADUA AND PISA ARE EXPONENTIALLY FAR APART Benjamin M. M. de Weger∗ Abstract We answer the question posed by Ian Stewart which Padovan numbers are at the same time Fibonacci numbers. We give a result on the difference between Padovan and Fibonacci numbers, and on the growth of Padovan numbers with negative indices. 1. Introduction 1.1. What this paper is not about. This paper has nothing to do with Italian topography. It is about Padovan numbers and their distances to Fibonacci numbers. Briefly said the main result of this paper is an explicit lower bound for these distances, which grows exponentially. The problem solved here is a generalization of a question asked by Ian Stewart in his Scientific American Mathematical Recreations column [S]. In this column Stewart described the similarities between Padovan and Fibonacci numbers, and remarked that, appropriately, Pisa, the city of Fibonacci, and Padua, the city with Italian name Padova, are roughly only 100 miles apart. As we show that Padovan and Fibonacci numbers are far apart, this might serve as an explanation for our title. 1.2. Padovan and Fibonacci numbers. The Padovan numbers Pm, named after Richard Padovan, are defined by P0=1,P 1=0,P 2=0,P m+1 =Pm−1+Pm−2, ∗This author’s research was supported by the Netherlands Mathematical Research Foundation SWON with financial aid from the Netherlands Organization for Scientific Research NWO. This paper was written while the author enjoyed the hospitality of the Centre de Recerca Matem`atica, Institut d’Estudis Catalans, Bellaterra, Catalunya. 632 B. M. M. de Weger and the Fibonacci numbers Fn, named after Leonardo ‘Fibonacci’ Pisano, are defined by F0=0,F 1=1,F n+1 =Fn+Fn−1. Note that in our definition the indices of the Padovan numbers are shifted by 5 compared to Stewart’s definition. We list a few of these numbers: m012345 678910 Pm100101 11223 m11 12 13 14 15 16 17 18 19 20 Pm4 5 7 9 12 16 21 28 37 49 m21 22 23 24 25 26 27 28 29 ... Pm65 86 114 151 200 265 351 465 616 ... n012345 678910 Fn011235 813213455 n11 12 13 14 15 16 ... Fn89 144 233 377 610 987 ... It will be clear from the definition that Padovan and Fibonacci numbers can be extended to negative indices. For the Fibonacci numbers this does not give essentially new numbers, as F−n=(−1)n+1Fn. But the Padovan numbers lack such symmetry, and thus are interesting for negative indices too. We also list a few of them: m123456 78910 P−m−110−12−2 11−34 m11 12 13 14 15 16 17 18 19 20 P−m−304−77−3−411−14 10 m21 22 23 24 25 26 27 28 29 30 P−m1−15 25 −24 9 16 −40 49 −33 −7 m31 32 ... P−m56 −89 ... Padua and Pisa 633 These short tables already illustrate the growth behaviour of the sequences. Whereas Pmand Fngrow very regularly, indeed exponentially, with Fnshowing the faster growth rate, the P−mshow oscillating behaviour, with still exponentially but slowly growing amplitude. These observations are warranted by the following lemma, which is easy to prove, e.g. by mathematical induction. Lemma 1. (i) Let γbe the real root of x3−x−1, and let δbe the non-real root of x3−x−1with positive imaginary part. Let λ=1 23 5−6γ+4γ2,µ=1 23 5−6δ+4δ2. Then for all m∈Z Pm=λγm+µδm+µδm. (ii) Let α=1 21+√5,β=1 21−√5. Then for all n∈Z Fn=1 √5αn−1 √5βn. Because |β|<1 the term 1 √5βntends to 0 as ngrows, so that this lemma implies at once that Fn∼1 √5αnas n→∞, indeed showing exponential growth with growth rate α=1.61 ... . Similarly, because |δ|<1, the terms µδmand µδmtend to 0 as m grows, so that the lemma shows that Pm∼λγmas m→∞, indeed showing exponential growth with growth rate γ=1.32 ... . Note that Pmis the nearest integer to λγmif m≥5. When studying Pmfor negative indices we prefer to write P−m=λγ−m+µδ−m+µδ−m with mpositive. Now it’s the term λγ−mthat tends to 0 as m→∞, whereas the other two terms in the above expression for P−m grow exponentially in absolute value. Notice that (1) µδ−m+µδ−m=µδ−m1+µδ−m µδ−m, 634 B. M. M. de Weger where the number µδ −m µδ−mis on the unit circle (and travels around it as m varies). This explains the oscillating behaviour. The amplitude is |δ−m|, which is equal to γm/2, since γδδ= 1, and thus |δ|=δδ1/2=γ−1/2. Thus the growth rate of the amplitude is only γ1/2=1.15 ... . 1.3. Stewart’s first question. Stewart in his column [S] asked two specific questions on Padovan numbers with nonnegative indices. First, he remarks that some Padovan numbers are Fibonacci numbers too, namely P1=P2=P4=0=F0, P0=P3=P5=P6=P7=1=F1=F2, P8=P9=2=F3, P10 =3=F4, P12 =5=F5, P17 =21=F8, and asks whether there are other solutions, and whether the number of solutions is finite or infinite. In this paper we answer this question in showing that there are no other solutions. Stewart did not care about Padovan numbers with negative indices. Had he done so, he certainly would have noticed (also counting Pm=−Fnas solution) that P−3=P−12 =0=F0, −P−1=P−2=−P−4=P−7=P−8=P−21 =1=F1=F2, P−5=−P−6=2=F3, −P−9=−P−11 =−P−16 =3=F4, −P−32 =89=F11. A natural question is whether these are all the solutions of P−m=±Fn. It follows from results of Evertse [E] and van der Poorten and Schlickewei [PS] that the number of solutions is finite, and even an explicit upper bound for the number of solutions can be given. We conjecture that the ones mentioned above are all the solutions, but we have no idea how to attack this problem. It follows from a result of Mignotte [M2] that an equation of the type um=vnhas only finitely many solutions, and can be solved effectively and practically, when {um}and {vn}both are recurrence sequences with one dominating root, i.e. of the characteristic roots (such as γ,δ,δfor {Pm}) one is in absolute value strictly larger than the others (γ). Indeed, the very first paper in which a diophantine problem was explicitly solved Padua and Pisa 635 by the methods that we use in this paper, was a problem of this type, cf. Baker and Davenport [BD]. It seems that our present result is the first explicit equation of this type involving a second and a third order recurrence sequence. 1.4. Stewart’s second question. Stewart’s second question is which Padovan numbers are squares. There obviously are the solutions P1=P2=P4=0 2, P0=P3=P5=P6=P7=1 2, P11 =2 2, P14 =3 2, P20 =7 2. We have no idea how to prove anything in this direction. Stewart might also have noticed that P−3=P−12 =0 2, −P−1=P−2=−P−4=P−7=P−8=P−21 =1 2, P−10 =P−13 =−P−17 =2 2, P−25 =3 2, P−26 =4 2, P−23 =5 2, P−28 =7 2, but he didn’t. Again we have no clue whatsoever how to proceed with this problem. 1.5. Results I. However, we can answer two other questions Stewart did not ask. The first one we get almost for free from our method for solving Pm=Fn. Namely we can prove the following result. Theorem 2. (i) If mand nare nonnegative integers such that |Pm−Fn|≤P1/2 m, then m≤29 and n≤15. (ii) If mand nare nonnegative integers such that Pm=Fnthen (2) |Pm−Fn| >max Pm m1.4615×1015 ,Pm e1.7950×109(log m)2,0.24174P1/2 m. 636 B. M. M. de Weger An answer to Stewart’s original question to find the solutions of Pm=Fnfollows immediately from (i), upon inspection of the tables in Section 1.2. In (i) we could in principle have derived a similar result with the exponent 1/2 replaced by any δ<1. A similar remark holds for (ii), with the constant 0.24174 adjusted accordingly. In (ii), when mis larger than approximately 10353605, the first term in the max expression is the best one. It shows that asymptotically |Pm−Fn|P1− mfor an arbitrarily small >0, and thus that Padua and Pisa are indeed exponentially far apart (note that Pm∼λγm). For msmaller than approximately 1.1549 ×1013, the third term in the max expression is the best one. As an immediate application we now are able to instantaneously solve problems of the type |Pm−Fn|≤106, say. Namely, (i) tells us that there are no solutions with Pm≥1012, and if Pm<1012 then, by the fact that Pmis the nearest integer to λγmfor m≥5, we immediately have m≤104. The solutions now are easy to determine. 1.6. Results II. The other problem we’ll address in this paper is the growth behaviour of P−m. As we saw above this sequence oscillates with exponentially growing amplitude, thus shows complicated behaviour, getting small compared to the amplitude when the number µδ −m µδ−mon the unit circle happens to come near to −1. This happens when Arg µ+mArg δ is near to an odd integer times 1 2π. Nevertheless there is a result of Mignotte [M1] that yields a lower bound for |P−m|, and in the following theorem we will make this explicit. This might serve as a meager substitute for our inability to solve P−m=±Fn, but this seems more or less to be at the limit of the available methods. Theorem 3. (i) If mis a nonnegative integer such that |P−m|≤γm/4, then m≤ 30. (ii) If mis a nonnegative integer not equal to 3or 12 then (3) |P−m|>max γm/2 m8.4019×1015 ,γm/2 e6.3164×1011(log m)2,0.22848γm/4. From (i) it follows that the sequence {Pm}m∈Zhas exactly 5 zeroes, namely at m=−12,−3,1,2,4. This result is due to Beukers [B], with a different proof. Padua and Pisa 637 Similar remarks as those immediately following the statement of Theorem 2 can be made here. Especially we want to remark that asymptotically |P−m|γ(m/2)(1−)for an arbitrarily small >0, and thus although in the oscillation P−mcan become a bit smaller than the amplitude γm/2, this never becomes really dramatic. Also, an application such as finding all solutions to |P−m|≤106is now instantaneous: from (i) we obtain γm<1024, hence m≤196. 1.7. Perrin numbers. Stewart in his column also considers the Perrin numbers A, defined like the Padovan numbers by A+1 =A−1+A−2, but with different initial conditions: A0=3,A 1=0,A 2= 2. They satisfy A=γ+δ+δ=3P+2P+1. Our methods will certainly be able to prove the following assertions, or in case they are false, to prove similar assertions with the constants replaced by the correct ones. We leave details of such proofs to the interested reader. Assertions 4. (i) If and nare nonnegative integers such that |A−Fn|≤A1/2 , then ≤29 and n≤18. (ii) If and nare nonnegative integers such that A=Fnthen |A−Fn|>max A 1016 ,A e1010(log )2,0.10540A1/2 . (iii) If is a nonnegative integer such that |A−|≤γ/4, then m≤29. (iv) If is a nonnegative integer then |A−|>max γ/2 1016 ,γ/2 e1012(log )2,0.13019γ/4. 2. Proof of Theorem 2 2.1. Preparations. We start with noting that α=1.61803 ... , β =−0.61803 ... , γ=1.32471 ... , δ =−0.66235 ...+0.56227 ...i, γδδ=1,|δ|=γ−1/2=0.86883 ... , λ=0.17700 ... , µ=0.41149 ...−0.27622 ...i, λµµ=1 23,|µ|= (23λ)−1/2=0.49560 ... . 638 B. M. M. de Weger Lemma 1 gives us at once that (4) |Pm−Fn|≥ 1 √5αn−λγm−1 √5α−n+2|µ|γ−m/2. We may assume without loss of generality that m≥11, so that Pm≥4. From Lemma 1 we have |Pm−λγm|≤2|µ|γ−m/2≤2|µ|γ−11/2<0.21111, so that by m≥11 and Pm≥4 we find inequalities that we will use repeatedly: λγm>P m−0.21111 ≥1−0.21111 4Pm>0.94722Pm,(5) Pm>λγ m−0.21111 ≥1−0.21111 λγ11 λγm>0.94590λγm.(6) Next we want to estimate the error term in (4). A rough estimate is (7) 1 √5α−n+2|µ|γ−m/2<1 √5+2|µ|γ−11/2<0.65832. But we can do much better. First we remark that if in some cases we can prove that |Pm−Fn|> cλγmfor some constant c>0, then we are essentially done, as it immediately follows that |Pm−Fn|>c Pmfor some other constant c>0. In the case that α−n≥γ−m/2 we have 1 √5αn−λγm≤1 √5γm/2−λγm<0, so by (4) and (7) |Pm−Fn|≥λγm−1 √5αn−0.65832 ≥λγm1−1 λγm/2√5−0.65832 ≥λγm1−1 λγ11/2√5−0.65832 λγ11  (8) >0.29323λγm, Padua and Pisa 639 and with (5) this yields |Pm−Fn|>0.27775Pm. So in this case Pm=Fn, and |Pm−Fn|≤P1/2 mat once implies Pm≤12, and also the inequality (2) is obvious in this case. So we may assume that α−n<γ −m/2, and then we find for the error term in (4) a much better estimate than (7), namely (9) 1 √5α−n+2|µ|γ−m/2<1 √5+2|µ|γ−m/2<1.4385γ−m/2. To deal with the main term of (4) we introduce a linear form in logarithms of algebraic numbers: Λ=−log(λ√5) + nlog α−mlog γ. Notice that (10)  1 √5αn−λγm =λγmeΛ−1. It follows that Λ = 0. In the case Λ ≤−1 we have eΛ−1=1−eΛ≥ 1−e−1, so by (4), (7) and (10) we find |Pm−Fn|≥λγm1−e−1−0.65832 ≥λγm1−e−1−0.65832 λγ11 >0.46343λγm, which is covered by (8). So we may assume that Λ >−1. Then eΛ−1>(1 −e−1)|Λ|, and with (10) this gives us an important estimate: (12)  1 √5αn−λγm >0.63212λγm|Λ|. The last special case we have to deal with is the case n>m. Then n≥m+1≥12, so Λ≥log α λ√5+ 11 log α γ>3.6081. With (4), (7) and (12) this yields (13) |Pm−Fn|>2.2807λγm−0.65832 ≥λγm2.2807 −0.65832 λγ11 >2.1120λγm, which again is covered by (8). So we may assume that n≤m. 646 B. M. M. de Weger 3. Proof of Theorem 3 3.1. Preparations. This proof follows to a large extent the line of argument set out in the previous proof1, and is in details a bit simpler. For m≥0 we write (cf. (1)) P−m=µδ−m1+µ µδ δm+λγ−m, and notice that λγ−mnow is exponentially small, that |µδ−m|=|µ|γm/2 is large, and that µ µδ δmlies on the unit circle. So we put µ µ=eiψ,δ δ=eiφ, where we take ψ,φ ∈(−π,π] (in the sequel, π=3.14159 ... is the number satisfying eiπ =−1). Indeed, ψ=1.18235 ... , φ=−1.40771 ... . Without loss of generality we may assume that m≥10, say. We put Λ=ψ+mφ +(2−1)π, where we take ∈Zsuch that Λ ∈(−π,π]. Notice that by m≥10 we have 2−1= 1 π(Λ −ψ+m|φ|)<0.44810m+0.62365 <m, and also 2−1≥5. Hence (23) max{|2−1|,m}=m. So we now have (24) P−m=µδ−m1−eiΛ+λγ−m. If Λ ≥π 3then eiΛ−1=2sin 1 2Λ≥1, hence by (24) we have |P−m|≥|µ|γm/2−λγ−m≥|µ|−λγ−15γm/2>0.49300γm/2. 1As my colleague Henk Hoogland would say: this is going to be a proof by texteditor. The reader interested in writing out a proof of the Assertions 4 can obtain the L a T EX-code of this paper from the author upon request. Padua and Pisa 647 In this case the statements of the theorem are immediate. If Λ <π 3then eiΛ−1=2sin 1 2Λ≥3 π|Λ|, hence (24) gives (25) |P−m|≥|µ|γm/23 π|Λ|−λγ−m. 3.2. Application of transcendence theory. A lower bound for |λ|is again furnished by transcendence theory. Indeed, [BW] and [V] give (by (23) and on noting that Λ =0) (26) |Λ|>max{m−CBW ,e −CV(log m)2}, where CBW and CVare large absolute constants that can be computed explicitly. In fact, for CBW we find C=18×4! ×34×1925×log 36 ×hµ µ×hδ δ×h(−1), where −1 is to be interpreted as eiπ. Now we have the function hon the sextic field Q(δ, δ). Using hξ ξ≤2h(ξ) we find hµ µ<2.0904,h δ δ<0.23462,h (−1) = π 6<0.52360, so we find for CBW in (26) that (27) C<8.4017 ×1015. And for CVwe have CV= 285000 ×65×4×h µ µ×h δ δ×h(−1), and we find h µ µ<2.0904,h  δ δ<1.5955,h (−1) = 3.4π 3<3.5605. Notice that in applying Voutier’s Theorem 3 we have taken B=m2 (whence the factor 4), which by 2−1≤mis larger than 1 3h(−1) +2−1 3h(µ/µ) m 3h(−1) +2−1 3h(δ/δ). 648 B. M. M. de Weger For the constant CVin (26) this leads to (28) CV<6.3162 ×1011. 3.3. Finishing the proof. Now from (25), (26) and (28) we obtain (29) |P−m|≥0.47327 γm/2 e6.3162×1011(log m)2−λγ−m. The right hand side is positive if m≥1.8506 ×1015. So we now have proved that if P−m= 0 then m<1.8506 ×1015. If m≥1.8506 ×1015 then 0.47327 λ λγ 3 2m e6.3162×1011(log m)2>e 1.0840×1010 . It then follows from (29) that (30) if m≥1.8506 ×1015 then |P−m|>γm/2 e6.3163×1011(log m)2, which is a major step towards the proof of (ii). Assume that |P−m|≤γm/4. Then (30) immediately implies that m<1.2335 ×1016.Thuswehave (31) if m≥1.2335 ×1016 then |P−m|>γ m/4>0.22848γm/4, which is another major step towards the proof of both (i) and (ii). In a moment we will show that if m<1.2335×1016 then |P−m|≤γm/4 has only the solutions mentioned in the statement (i) in the theorem. Assuming this for the moment, we can now finish the proof of (ii) in a similar way as we did in the proof of Theorem 2. Notice that the number 0.22848 <0.228482 ...=γ−21/4is the smallest nonzero value of |P−m|/γm/4, that occurs for P−21 = 1. This proves that (32) if m<1.2335 ×1016 then |P−m|>0.22848γm/4. Further, by m<1.2335 ×1016 it follows that γm/4<0.22848m8.4019×1015 , and thus by (32) we have (33) if m<1.2335 ×1016 then |P−m|>0.22848γm/4>γm/2 e6.3164×1015 . Padua and Pisa 649 Now (30), (31), (32) and (33) together imply two of the three bounds in (ii), and the third one follows by a similar reasoning, of which we do not give the details. 3.4. Application of computational diophantine approximation. It remains to prove that if m<1.2335 ×1016 then the inequality |P−m|≤γm/4has no solutions with m≥31 (notice that the solutions with m≤30 are very easy to find). This we do by the same computational diophantine approximation technique that we used in the proof of Theorem 2, using again the linear form Λ. This time we omit some numerical details. From (25) and our inequality and m≥31 we have |Λ|≤ π 3|µ|1+ λ γ155/4γ−m/4, thus (34) |Λ|<2.1130γ−m/4. Consider the lattice Γ = {Cx|x∈Z2}defined by the matrix C=10 1034φ 1034π, where [·] stands for rounding to the nearest integer. Further, consider the point y=0 −1034ψ For a possible solution mthe distance dto look at now is the distance between the lattice point Cm 2−1and the point y, being the length of the vector Cm 2−1−y=m Λ, with Λ=−1034ψ+m1034φ+(2−1) 1034π. The distance dbetween yand the nearest lattice point is larger than 8.9716 ×1016 (we omit numerical details behind this fact). It follows as in Section 2.4 that |Λ|>6.4192 ×10−18, 650 B. M. M. de Weger and now together with (34) we immediately find that m≤573. Again we repeat the game, with 1034 replaced by 107. Now we have d>2377.3, and we derive |Λ|>1.1602 ×10−4, and now together with (34) we immediately find that m≤139. Finally, finding the solutions with 31 ≤m≤139 can simply be done by enumeration. This completes the proof of Theorem 3. References [BD] A. Baker and H. Davenport, The equations 3x2−2=y2and 8x2−7=z2,Quart. J. Math. Oxford Ser. (2) 20 (1969), 129–137. [BW] A. Baker and G. W¨ ustholz, Logarithmic forms and group varieties, J. Reine Angew. Math. 442 (1993), 19–62. [B] F. Beukers, The zero-multiplicity of ternary recurrences, Compositio Math. 77 (1991), 165–177. [E] J.-H. Evertse, On sums of S-units and linear recurrences, Compositio Math. 53 (1984), 225–244. [M1] M. Mignotte, A note on linear recursive sequences, J. Austral. Math. Soc. Ser. A 20 (1975), 241–244. [M2] M. Mignotte, Une extension du th´eor`eme de Skolem-Mahler, C.R. hebd. S´eanc. Acad. Sci. Paris S´er. A 288 (1979), 233–235. [PS] A. J. van der Poorten and H. P. Schlickewei, Additive relations in fields, J. Austral. Math. Soc. Ser. A 51 (1991), 154–170. [S] I. Stewart, Mathematical Recreations: Tales of a neglected number, Scientific American 274 (1996), 92–93. [V] P. M. Voutier, Linear forms in three logarithms, to appear. Padua and Pisa 651 [dW] B. M. M. de Weger, Algorithms for diophantine equations, CWI-tract no. 65, Centrum voor Wiskunde en Informatica, Amsterdam (1989). Mathematical Institute University of Leiden and Econometric Institute Erasmus University Rotterdam P.O. Box 1738 3000 DR Rotterdam THE NETHERLANDS e-mail: dew[email protected] Primera versi´o rebuda el 14 d’Octubre de 1996, darrera versi´o rebuda el 17 de Mar¸c de 1997