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

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

2012-01-03T10:54:14Z

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

Answer by Kevin O'Bryant for Can the difference of two distinct Fibonacci numbers be a square infinitely often?

2012-01-03T21:35:34Z

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

Answer by joro for Can the difference of two distinct Fibonacci numbers be a square infinitely often?

2012-01-04T13:00:29Z

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.

Answer by Zack Wolske for Can the difference of two distinct Fibonacci numbers be a square infinitely often?

2012-01-05T08:35:01Z

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.

Answer by David Speyer for Can the difference of two distinct Fibonacci numbers be a square infinitely often?

2012-01-05T16:15:59Z

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.