# 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?

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.

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.

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

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

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.

-
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

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

-
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
oops. sure wish I could take that back.... – Mike Bennett Jan 4 '12 at 3:41
@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
@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

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.

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

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.

-
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