Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Can the difference of two distinct Fibonacci numbers be a square infinitely often?

There are few solutions with indices $<10^{4}$ the largest two being $F_{14}-F_{13}=12^2$ and $F_{13}-F_{11}=12^2$

Probably this means there are no identities between near neighbours.

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.

Are there other solutions besides the small ones?

[Added later] Here is a link to elliptic curves per François Brunault's comment.

According to DIOPHANTINE EQUATIONS, FIBONACCI HYPERBOLAS,. AND QUADRATIC FORMS. Keith Brandt and John Koelzer.

Fibonacci numbers with consecutive odd indices are the only solutions to $$ x^2-3xy+y^2 = -1 \qquad (1)$$

Fibonacci numbers with consecutive even indices are the only solutions to $$ x^2-3xy+y^2 = 1 \qquad (2)$$

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).

The closed form of $l(x,y)$ might be of interest, can't find the identity at the moment.

Probably a genus 0 curve with integral points $F_{2n},F_{2n+1}$ will be better.

Added much later

Does some generalization of the $abc$ conjecture predict something?

For 3 Fibonacci numbers identities are much easier:

$$ F_{4n+1}+F_{4n+3}-F_3 = L_{2n+1}^2$$

share|improve this question
2  
Another note: for differences of consecutive Fibonacci's, or gaps of $2$ (i.e. F_{n+2}-F_n) the answer is that the only square values are $1$ and $144$. This follows from a result of J. Cohn, On square Fibonacci numbers, J. London Math. Soc. 39 1964. –  Alan Haynes Jan 3 '12 at 12:01
4  
Using Cohn's characterization of when $F_n = 2x^2$ (it's true only when n = 0, 3, or 6), and simplifying $F_{n+3} - F_n = 2F_{n+1}$, the only examples separated by 3 are $F_5 - F_2 = 4$, and $F_8 - F_5 = 16$. Similarly, to find all pairs separated by 4, simplify $F_{n+2} - F_{n-2} = F_{n+1} + F_{n-1} = L_n$ to get that the Lucas number $L_n$ must be a square, so n = 1 or 3, giving $F_5 - F_1 = 4$ as the only solution. Both characterizations come from J. Cohn's paper "Square Fibonacci Numbers, Etc." Fibonacci Quarterly 2 1964, pp. 109-113. –  Zack Wolske Jan 3 '12 at 13:48
3  
In a similar fashion, you can show that there is a solution (and exactly one) separated by 6 terms: $F_{15} - F_9 = 576 = 24^2$. But this example relies on the Lucas number $L_3$ being a square, so there's no hope that it produces an infinite family. –  Zack Wolske Jan 3 '12 at 14:54
3  
Shorey and Stewart proved that in any non-trivial second-order linear recurrence sequence, there are only finitely many perfect powers. (See Bugeaud-Mignotte-Siksek www-irma.u-strasbg.fr/~bugeaud/travaux/fibo.pdf) So after fixing the gap, there are only finitely many squares. I don't know whether this can be made effective. –  François Brunault Jan 3 '12 at 19:35
3  
The result of Shorey and Stewart is effective (though rather non-explicit!). For fixed $j$ with $F_k-F_j=x^2$, the link to elliptic curves comes from the fact that Fibonacci numbers are the $y$-values satisfying $x^2-5 y^2 = \pm 4$. I don't see how to prove finiteness for the general problem, ineffectively or otherwise (but 10 hours as department head has undeniably left my brain enfeebled). –  Mike Bennett Jan 4 '12 at 3:28
show 16 more comments

4 Answers 4

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.

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 http://oeis.org/A053028), 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.

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.

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}$.

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$.

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.

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}$.

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.

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.

EDIT: 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.

EDIT 2: 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.

share|improve this answer
    
There is a gap here where my argument assumes that no higher powers of a primitive divides its Fibonacci number. As far as I know, it's not resolved. –  Zack Wolske Jan 5 '12 at 11:49
    
Something similar to yours is: warwick.ac.uk/~maseap/papers/fnpm.pdf FIBONACCI NUMBERS AT MOST ONE AWAY FROM A PERFECT POWER YANN BUGEAUD, FLORIAN LUCA, MAURICE MIGNOTTE, SAMIR SIKSEK –  joro Jan 7 '12 at 7:27
    
@joro: It looks like their decomposition works because 1 appears with both even and odd index in the sequence, so they can apply the argument for even differences (or sums) twice. That's why the same argument won't work for $F_n + 2 = y^p$. –  Zack Wolske Jan 7 '12 at 15:02
    
The gap can be resolved as follows: If $p$ is an odd prime dividing a Fibonacci number with odd index (it need not be a primitive factor), then it does not divide any Lucas number. This follows from $\gcd(F_a, F_b) = F_{\gcd(a,b)}$. We can always find such a prime with odd exponent in the factorization of $F_q$ for q >3 and odd, since otherwise we get $F_q = x^2$ or $F_q = 2x^2$. –  Zack Wolske Jan 7 '12 at 15:08
    
@Zack With "the squares do not divide $F_{2^k}$ " you mean $F_{2^k}$ is squarefree? –  joro Jan 4 '13 at 9:40
show 1 more comment

Reporting on some computations: the only solutions to $F_k - F_j = x^2$ with $0\leq j < k$ and $1 \leq x \leq 10^6$ are these:

{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}

where the format is {j,k,x}.

share|improve this answer
7  
It's easy enough to search well past $x = 10^6$. The following gp code takes little only ~10 minutes here to try $F_k-F_j$ for all $j < k \leq 10^4$, and thus all $x$ up to $\sqrt{F_{9998}} > 10^{1000}$. Not too surprisingly, though, it finds no further solutions other than the spurious $(j,k,x)=(1,2,0)$. for(j=0,10^4,for(k=j+1,10^4,if(issquare(fibonacci(k)-fibonacci(j),&x),print([j,‌​k,x])))) –  Noam D. Elkies Jan 4 '12 at 3:32
    
and I find no new ones up to $10^{200}$... –  Mike Bennett Jan 4 '12 at 3:40
3  
oops. sure wish I could take that back.... –  Mike Bennett Jan 4 '12 at 3:41
2  
@Noam Wouldn't your code be significantly faster if you precompute fibonacci(i) in f[i] and then check issquare(f[k]-f[i])? You need not compute fibonacci(i) many times. –  joro Jan 4 '12 at 7:22
3  
@joro Good question. I didn't do it that way because (i) A table vector(N+1,i,fibonacci(i-1)) takes about $N^2$ space, (ii) I thought the issquare test would take longer in any case (that turns out not to be the case, though $F_j$ takes only $O(\log(j))$ operations to compute), and (iii) Precomputing the table would make the code longer than one command ;-) –  Noam D. Elkies Jan 4 '12 at 14:56
show 2 more comments

This is a slight elaboration on joro's comment; I was hoping that someone else would write a better version of this.

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.

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.

share|improve this answer
    
Thank you. Is it possible $x^2-x y-y^2 = -1$ to be a typo?. I get $x^2-x y-y^2 = +1$ –  joro Jan 6 '12 at 10:34
    
Right, thank you. –  David Speyer Jan 6 '12 at 13:12
    
The package "desing" de-singularized the surface. If I have done it right I see no curves on it (and the remaining solutions must be quite large). –  joro Jan 6 '12 at 13:22
1  
AFAIK, there are no proven major results on integer points on affine pieces of K3 surfaces. However, Vojta's conjecture predicts that the set of such points lies on a finite union of curves. So assuming Vojta's conjecture, one might be able to make further progress. –  Joe Silverman Jan 4 '13 at 23:21
    
A finite union of genus zero curves (plus finitely many counterexamples), due to Siegel's theorem. I think that what joro was saying above was that there are no rational curves on this surface, but I may have misunderstood him. –  David Speyer Jan 5 '13 at 1:24
add comment

I get numerical support for the link with integral points on genus 1 curves.

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).

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$$

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.

Here are curves where $x$ corresponds to $F_{2n+1}$ on the first curve and $F_{2n}$ on the second curve.

 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)     

Lack of integral points on both curves would mean no solution for the given gap.

share|improve this answer
    
You can definitely handle this kind of curves using Magma : magma.maths.usyd.edu.au/magma/handbook/text/1352#14935 If you don't have access to Magma you can do limited computation at magma.maths.usyd.edu.au/calc –  François Brunault Jan 4 '12 at 16:32
    
Treating $F_k,F_{k-2}$ as variables and using the curves described in the question appears to lead to a surface. –  joro Jan 5 '12 at 13:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.