Can the difference of two distinct Fibonacci numbers be a square infinitely often? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T22:07:06Z http://mathoverflow.net/feeds/question/84797 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/84797/can-the-difference-of-two-distinct-fibonacci-numbers-be-a-square-infinitely-often Can the difference of two distinct Fibonacci numbers be a square infinitely often? joro 2012-01-03T10:54:14Z 2013-01-04T22:47:01Z <blockquote> <p>Can the difference of two distinct Fibonacci numbers be a square infinitely often?</p> </blockquote> <p>There are few solutions with indices $&lt;10^{4}$ the largest two being $F_{14}-F_{13}=12^2$ and $F_{13}-F_{11}=12^2$</p> <p>Probably this means there are no identities between near neighbours.</p> <p>Since Fibonacci numbers are the only integral points on some genus 0 curves the problem is equivalent to finding integral points on one of few varieties. Fixing $F_j$ leads to finding integral points on a quartic model of an elliptic curve.</p> <blockquote> <p>Are there other solutions besides the small ones?</p> </blockquote> <p><em>[Added later]</em> Here is a link to elliptic curves per François Brunault's comment.</p> <p>According to <a href="http://www.math-cs.ucmo.edu/~mjms/2006.2/kbrandt.ps" rel="nofollow">DIOPHANTINE EQUATIONS, FIBONACCI HYPERBOLAS,. AND QUADRATIC FORMS. Keith Brandt and John Koelzer.</a></p> <p>Fibonacci numbers with consecutive odd indices are the only solutions to $$x^2-3xy+y^2 = -1 \qquad (1)$$</p> <p>Fibonacci numbers with consecutive even indices are the only solutions to $$x^2-3xy+y^2 = 1 \qquad (2)$$</p> <p>Given $F_n$ and $F_{n+2}$ one can compute $F_{n+k}$ using the linear Fibonacci recurrence and $F_{n+k}$ will be a linear combination $l(x,y)$ of $x,y$. Adding $l(x,y)-x=z^2$ to (1) or (2) gives a genus 1 curve. (Or just solve $l(x,y)-x=z^2$ and substitute in (1) or (2) to get a genus 1 quartic).</p> <p>The closed form of $l(x,y)$ might be of interest, can't find the identity at the moment.</p> <p>Probably a genus 0 curve with integral points $F_{2n},F_{2n+1}$ will be better.</p> <p><strong>Added much later</strong></p> <blockquote> <p>Does some generalization of the $abc$ conjecture predict something?</p> </blockquote> <p>For 3 Fibonacci numbers identities are much easier:</p> <p>$$F_{4n+1}+F_{4n+3}-F_3 = L_{2n+1}^2$$</p> http://mathoverflow.net/questions/84797/can-the-difference-of-two-distinct-fibonacci-numbers-be-a-square-infinitely-often/84839#84839 Answer by Kevin O'Bryant for Can the difference of two distinct Fibonacci numbers be a square infinitely often? Kevin O'Bryant 2012-01-03T21:35:34Z 2012-01-04T02:19:05Z <p>Reporting on some computations: the only solutions to $F_k - F_j = x^2$ with $0\leq j &lt; k$ and $1 \leq x \leq 10^6$ are these:</p> <pre><code>{0,1,1}, {0,2,1}, {1,3,1}, {2,3,1}, {3,4,1}, {1,5,2}, {2,5,2}, {5,8,4}, {6,11,9}, {0,12,12}, {11,13,12}, {13,14,12}, {6,13,15}, {9,15,24} </code></pre> <p>where the format is {j,k,x}.</p> http://mathoverflow.net/questions/84797/can-the-difference-of-two-distinct-fibonacci-numbers-be-a-square-infinitely-often/84882#84882 Answer by joro for Can the difference of two distinct Fibonacci numbers be a square infinitely often? joro 2012-01-04T13:00:29Z 2012-01-04T13:00:29Z <p>I get numerical support for the link with integral points on genus 1 curves.</p> <p>For $x,y=F_n,F_{n+2}$ experimentally the closed form is $F_{n+k}=l(x,y)= F_{k} y -F_{k-2} x$ (probably provable by induction).</p> <p>For a fixed gap $k$ solutions correspond to (positive?) integral points on: $$z^{4} + (2 {F_{k-2}} - 3 {F_{k}} + 2) x z^{2} + ({F_{k-2}}^{2} - 3 {F_{k-2}} {F_{k}} + {F_{k}}^{2} + 2 {F_{k-2}} - 3 {F_{k}} + 1) x^{2} + {F_{k}}^{2}=0$$ or $$z^{4} + (2 {F_{k-2}} - 3 {F_{k}} + 2) x z^{2} + ({F_{k-2}}^{2} - 3 {F_{k-2}} {F_{k}} + {F_{k}}^{2} + 2 {F_{k-2}} - 3 {F_{k}} + 1) x^{2} - {F_{k}}^{2}=0$$</p> <p>Just noticed that if one accepts negative Fibonacci numbers (as described on wikipedia) $F_{-n}=(-1)^{n+1} F_n$ there are some more small solutions.</p> <p>Here are curves where $x$ corresponds to $F_{2n+1}$ on the first curve and $F_{2n}$ on the second curve.</p> <pre><code> 1 (z^4 + x*z^2 - x^2 + 1, z^4 + x*z^2 - x^2 - 1) 2 (z^4 - x*z^2 - x^2 + 1, z^4 - x*z^2 - x^2 - 1) 3 (z^4 - 2*x*z^2 - 4*x^2 + 4, z^4 - 2*x*z^2 - 4*x^2 - 4) 4 (z^4 - 5*x*z^2 - 5*x^2 + 9, z^4 - 5*x*z^2 - 5*x^2 - 9) 5 (z^4 - 9*x*z^2 - 11*x^2 + 25, z^4 - 9*x*z^2 - 11*x^2 - 25) 6 (z^4 - 16*x*z^2 - 16*x^2 + 64, z^4 - 16*x*z^2 - 16*x^2 - 64) 7 (z^4 - 27*x*z^2 - 29*x^2 + 169, z^4 - 27*x*z^2 - 29*x^2 - 169) 8 (z^4 - 45*x*z^2 - 45*x^2 + 441, z^4 - 45*x*z^2 - 45*x^2 - 441) 9 (z^4 - 74*x*z^2 - 76*x^2 + 1156, z^4 - 74*x*z^2 - 76*x^2 - 1156) 10 (z^4 - 121*x*z^2 - 121*x^2 + 3025, z^4 - 121*x*z^2 - 121*x^2 - 3025) 11 (z^4 - 197*x*z^2 - 199*x^2 + 7921, z^4 - 197*x*z^2 - 199*x^2 - 7921) 12 (z^4 - 320*x*z^2 - 320*x^2 + 20736, z^4 - 320*x*z^2 - 320*x^2 - 20736) 13 (z^4 - 519*x*z^2 - 521*x^2 + 54289, z^4 - 519*x*z^2 - 521*x^2 - 54289) 14 (z^4 - 841*x*z^2 - 841*x^2 + 142129, z^4 - 841*x*z^2 - 841*x^2 - 142129) 15 (z^4 - 1362*x*z^2 - 1364*x^2 + 372100, z^4 - 1362*x*z^2 - 1364*x^2 - 372100) 16 (z^4 - 2205*x*z^2 - 2205*x^2 + 974169, z^4 - 2205*x*z^2 - 2205*x^2 - 974169) 17 (z^4 - 3569*x*z^2 - 3571*x^2 + 2550409, z^4 - 3569*x*z^2 - 3571*x^2 - 2550409) 18 (z^4 - 5776*x*z^2 - 5776*x^2 + 6677056, z^4 - 5776*x*z^2 - 5776*x^2 - 6677056) 19 (z^4 - 9347*x*z^2 - 9349*x^2 + 17480761, z^4 - 9347*x*z^2 - 9349*x^2 - 17480761) 20 (z^4 - 15125*x*z^2 - 15125*x^2 + 45765225, z^4 - 15125*x*z^2 - 15125*x^2 - 45765225) 21 (z^4 - 24474*x*z^2 - 24476*x^2 + 119814916, z^4 - 24474*x*z^2 - 24476*x^2 - 119814916) 22 (z^4 - 39601*x*z^2 - 39601*x^2 + 313679521, z^4 - 39601*x*z^2 - 39601*x^2 - 313679521) 23 (z^4 - 64077*x*z^2 - 64079*x^2 + 821223649, z^4 - 64077*x*z^2 - 64079*x^2 - 821223649) 24 (z^4 - 103680*x*z^2 - 103680*x^2 + 2149991424, z^4 - 103680*x*z^2 - 103680*x^2 - 2149991424) </code></pre> <p>Lack of integral points on both curves would mean no solution for the given gap. </p> http://mathoverflow.net/questions/84797/can-the-difference-of-two-distinct-fibonacci-numbers-be-a-square-infinitely-often/84935#84935 Answer by Zack Wolske for Can the difference of two distinct Fibonacci numbers be a square infinitely often? Zack Wolske 2012-01-05T08:35:01Z 2013-01-04T22:47:01Z <p>All of the solutions for $F_{n + 4m} - F_n$ are the ones listed, barring the cases $m=2$ and $m=12$ where I still have some kinks to work out.</p> <p>Following Will Sawin's suggestion, we write $F_{n + m} - F_n$ as a reccurence, with some initial terms. Taking $n=0$ tells us that $F_m$ is one term, and $F_{m+1} - 1$ is the next. Extrapolating backwards, we have the general term $F_{m-i} + (-1)^i F_i$. So we see that if $m=4k+2$, then the term $i = 2k+1$ gives us $0$, and the next term gives us $F_{2k} + F_{2k+2} = L_{2k+1}$, so we have a copy of the Fibonacci numbers, multiplied by $L_{2k+1}$. That is, $F_{n + 4k+2} - F_n = L_{2k+1}F_{n + 2k+1}$. If $m = 4k$, then the term $i=2k$ gives us $2F_{2k}$, and the next term gives us $F_{2k+1} - F_{2k-1}=F_{2k}$, so we have a copy of the Lucas numbers, multiplied by $F_{2k}$. That is, $F_{n + 4k} - F_n = F_{2k}L_{n + 2k}$. This is useful, because there are certain primes which never divide Lucas numbers (see <a href="http://oeis.org/A053028" rel="nofollow">http://oeis.org/A053028</a>), so if $F_{2k}$ contains one of these primes (exactly one is easiest, but any odd multiple will do), then the product cannot be a square.</p> <p>Agol gave a link to a paper in the comments (http://www.fq.math.ca/Scanned/7-1/ferns.pdf) which also contains this result.</p> <p>Let's find all squares where $m = 2^k$. The cases $k=0, 1$ were given by AH in the comments, and the case $k=2$ is also included there. We need two facts about Lucas numbers, both of which are easy to show. First, $3 | L_m$ iff $m \equiv 2 \pmod{4}$ and second, $7 | L_m$ iff $m \equiv 4 \pmod{8}$.</p> <p>Since $4 | 2^k$, we can write $F_{n + 2^k} - F_n = F_{2^{k-1}}L_{n + 2^{k-1}}$. I have not resolved the case $k = 3$ (this gap has been fixed, see 2nd edit below), it is equivalent to finding Lucas numbers $x$ in the Diophantine equation $x^2 + 2 = 3y^2$. For now assume $k > 3$. By the facts above, we know that $3$ and $7$ cannot both divide a Lucas number, so we want to show that each of them divide $F_{2^{k-1}}$, and that neither $3^2$ nor $7^2$ do so. That both 3 and 7 divide follows from $F_8=21$ and $F_n | F_{2n}$. That both 9 and 49 don't divide follows by induction: the base case is $F_8$; and we have $F_{2^{k+1}} = F_{2^k}L_{2^k}$, and neither 3 nor 7 can divide $L_{2^k}$ when $k>2$. Then by induction the squares do not divide $F_{2^k}$ for $k \geq 3$, and neither $3$ nor $7$ divide $L_{2^k}$, since $2^k \equiv 0 \pmod{8}$. Hence there are no squares when $m = 2^k$ and $k > 3$.</p> <p>For the general case of $m=4k$, we write $F_{n + 4k} - F_n = F_{2k}L_{n + 2k} = F_{k}L_{k}L_{n + 2k}$ and invoke Carmichael's theorem: for each $n>3$, there is at least one prime $p | F_n$ which divides no previous Fibonacci number. Such a prime is called a primitive. Further - this is not part of the theorem - $p^2 \nmid F_n$ (after trying to work out a proof of this, I went to the literature and found that this is a conjecture in P. Ribenboim "Square classes of Fibonacci and Lucas numbers" Port. Math 46 (1989), 159-175. I'm not sure if it's been proven or falsified since then). Taking $n$ to be odd, we exploit the fact that $p$ does not divide any Lucas number, since its Fibonacci entry point is odd (see C. Ballot and M. Elia, "Rank and period of primes in the Fibonacci sequence; a trichotomy," Fib. Quart., 45 (No. 1, 2007), 56-63). If the odd part of $k$ is greater than $3$, we are done, since we can continue splitting $F_{k} = F_{k/2}L_{k/2}$ until we have an odd indexed Fibonacci number, and use a primitive for it. So we now have only $k = 3\cdot2^i$ left to consider. $i = 0$ and $i=1$ are easy to deal with: $F_{n + 12} - F_n = F_{6}L_{n + 6} = 8L_{n+6}$ and we know $L_{n+6} = 2x^2$ only if $n=0$ or negative (from J. Cohn's paper "Square Fibonacci Numbers, Etc." Fibonacci Quarterly 2 1964, pp. 109-113). $F_{n + 24} - F_n = F_{12}L_{n + 12} = 12^2L_{n+6}$ and we know $L_{n+12} = x^2$ has no solutions (again barring negative Fibonacci numbers - in these cases no solutions are distinct from the positive ones). $i=2$ causes me some trouble, and led to the negative solution $F_{36} - F_{-12} = 3864^2$. I also leave this unresolved.</p> <p>For $i > 2$, we proceed as in the argument for powers of $2$. Both $7$ and $47$ divide $F_{3\cdot2^{i+1}}$ exactly once, with the base case being $F_{48}$, and they cannot both divide $L_{n + 3\cdot2^{i+1}}$, since $47 | L_m$ iff $m \equiv 8 \pmod{16}$.</p> <p>The other even differences should fall the same way, although the formula for those fixes a Lucas number and varies the Fibonacci numbers, we can still find a primitive for the odd part of the Fibonacci index, but I'll have to patch up some pieces where the odd part is 3 or 1.</p> <p>I've had some success with the odd differences using J. Cohn's trick: $L_m | (F_{n+2m} + F_n)$ when $3 \nmid m$ and $2|m$, and the fact that $L_m \equiv 3 \pmod{4}$ for such $m$, but no arguments covering infinitely many differences.</p> <p><strong>EDIT:</strong> The other even numbers are easier. Writing $F_{n + 4k+2} - F_n = L_{2k+1}F_{n + 2k+1}$ and considering $F_{n + 2k+1}$, the primitive argument removes all indices $n+2k+1$ with an odd part greater than $3$. The same argument as above works for all powers of $2$, since $3$ never divides $L_{2k+1}$. Finally, when the odd part is $3$, it's easier than before, since $7$ divides $F_{3\cdot2^i}$ for $i > 2$, $7^2$ never does, and $7$ and cannot divide the Lucas numbers since they have odd index. $i= 0, 1$ and $2$ are solved by finding all Lucas numbers which are squares, or $2$ times a square.</p> <p><strong>EDIT 2:</strong> For $m=2^3$, we want to know if $F_4L_{n+4} = 3L_{n+4}$ is a square. This is solved in M. Goldman. "On Lucas Numbers of the Form $px^2$ where $p=3,7,47,2207$". Math. Reports Canada Acad. Sci. (June 1988). The only example is n+4 = 2, which either does or doesn't happen according to your taste.</p> http://mathoverflow.net/questions/84797/can-the-difference-of-two-distinct-fibonacci-numbers-be-a-square-infinitely-often/84970#84970 Answer by David Speyer for Can the difference of two distinct Fibonacci numbers be a square infinitely often? David Speyer 2012-01-05T16:15:59Z 2012-01-06T13:13:00Z <p>This is a slight elaboration on joro's comment; I was hoping that someone else would write a better version of this.</p> <p>The integer points on $x^2-xy-y^2 = 1$ are precisely the pairs $(F_{2n+1}, F_{2n})$. So looking for solutions of the form $F_{2n+1} - F_{2m+1} = z^2$ is looking for integer points on $$x_1^2 - x_1 y_1 - y_1^2 = x_2^2 - x_2 y_2 - y_2^2 = 1,\ x_1 -x_2 = z^2.$$ The other three possibilities give similar equations. </p> <p>Each of these is a $K3$ surface. Here is where a better answer would review the major results on integer points on $K3$ surfaces. But I don't know them, so I'm going to stop here and hope someone else fills it in.</p>