35
$\begingroup$

As the title says, I need help proving or disproving that there is only one Fibonacci number that's the sum of two (positive) cubes, $2$. I did a small brute force test with Fibonacci numbers below $10^{15}$ but I couldn't find anything.

Edit: A possibly fast way to factor sums of cubes is described in another question here.

I tested Hagen von Eitzen's $F_{3n} - F^3_{n+1}$ up to $n = 200000$ and brute force up to $10^{21}$ but no results. As the numbers grow bigger the chance of a cube gets smaller.

$\endgroup$
  • 2
    $\begingroup$ $F_{3n}-F_{n+1}^3$ is relatively small and hence has some chance to be a cube "by chance". But otherwise the exponential growth makes the existence of larger solutions somewhat unlikely. $\endgroup$ – Hagen von Eitzen May 10 '14 at 22:00
  • 2
    $\begingroup$ @WillJagy I read that there are an infinite number of fibonacci numbers that are the sum of squares, but I couldn't find anything supporting if this was true or not for cubes. $\endgroup$ – qwr May 10 '14 at 22:40
  • 1
    $\begingroup$ every other Fibonacci number is a Markov number and therefore the sum of two squares. en.wikipedia.org/wiki/Markov_number Not sure about cubes, and given that you are just curious and did not get this from any specific text, not sure there is a method for dealing with cubes here. $\endgroup$ – Will Jagy May 10 '14 at 22:47
  • 4
    $\begingroup$ I think it is worth to consider the problem under another perspective. It is well-known that $n$ belongs to the Fibonacci sequence iff $5n^2\pm 4$ is a square, so it suffices to find all the integer solutions of $$5(a^3+b^3)^2 = c^2\pm 4.$$ $\endgroup$ – Jack D'Aurizio May 22 '14 at 22:27
  • 5
    $\begingroup$ $F_{3n} - F_{n+1}^3 = F_n^3 - F_{n-1}^3$. By the case $p=3$ of Fermat's Last Theorem, this is never a cube except for the trivial cases $n=0,1,2$. $\endgroup$ – Robert Israel May 23 '14 at 1:47
10
$\begingroup$

On the assumption there isn't an "easy" reason for the answer to be yes or no, here is a heuristic justification of the conjecture.

There are only $O(n^{2/3})$ ways to write a sum of two (positive) cubes that is a number less than $n$; a "random" number of size $\Theta(n)$ therefore has a probability $O(n^{-1/3})$ of being a sum of two cubes, with the hidden constant not being too small. (probably a little less than $1/3$)

The expected number of ways to write a Fibonacci number as a sum of two cubes is thus something like

$$ O\left( \sum_{n=0}^{\infty} F_n^{-1/3} \right) \approx O\left( \sum_{n=0}^{\infty} \varphi^{-n/3} \right) \approx O\left( \frac{1}{1 - \varphi^{-1/3}} \right)$$

so it's probably a small finite number. Your empirical evidence says the small finite number is probably $1$.

It is quite possible that the conjecture is true, but for no good reason at all, which would make it very hard to come up with a proof. It might even be independent of Peano's axioms!

$\endgroup$
6
$\begingroup$

There are no further solutions for $n \leq 300$. Even dropping the positivity condition the only other solutions are $F_6 = 8 = 2^3 + 0^3 = 0^3 + 2^3$. This corroborates Hurkyl's heuristic that it is almost certain that there are no other Fibonacci numbers that are sums of two cubes. I doubt that this can be proved, though the search technique described below can surely be used well past $n=300$, because the main difficulty is factoring $F_n$, and $F_{300}$ has only about $60$ digits.

To try to express an integer $f$ as $a^3+b^3$, use the factorization $a^3 + b^3 = (a+b)(a^2-ab+b^2)$. For each pair $(x,y)$ such that $f=(x,y)$, check whether $3(4x-y^2)$ is a square, since that's the criterion for $(x, y) = (a^2-ab+b^2, a+b)$ [the point is that $4x-y^2 = 3(a-b)^2$].

I did this for $f=F_n$ and all $n \leq 300$ using this table of Fibonacci factorizations (discarding the 100 values of $n$ for which $F_n\bmod 9 \in \{3,4,5,6\}$, since such a number can never be the sum of two cubes). This took only ~30 seconds in gp, even though some candidates $F_n$ in this range have more than a million factors. Only the known solutions for $F_3=2$ and $F_6=8$ were found.

(also reported at MSE question 822435.)

$\endgroup$
  • $\begingroup$ Can I see your code? Maybe it can be written in Java as well, albeit with a significant loss in efficiency, no doubt. $\endgroup$ – Brian J. Fink Aug 18 '14 at 3:39
2
$\begingroup$

In the interest of accuracy, I am completely rewriting my answer. As Random Excess said in the comments, every Fibonacci number is either a sum or a difference of two squares, and I think this can be helpful, because we can compare the sums of cubes that are also sums or differences of squares: $$2, 9, 16, 28, 35, 65, 72, 91, 128\dots$$ to the Fibonacci sequence: $$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,89\dots$$ As you can see, the only number they have in common this early in both sequences is $2$. This could make your search faster by limiting the number of terms in the sequence of sums of cubes, and in the right hands, it might also be used to prove your conjecture! I hope this helps!

I also think Jack D'Aurizio's idea of using: $$5(a^3+b^3)^2=c^2\pm~4$$ which is just another way of checking that $$F_n=a^3+b^3$$ has merit because it means you only have to examine each sum of cubes once.

Keep in mind as well: $$\begin{align}(a^3+b^3)&=(a+b)(a^2-ab+b^2)\\ &=(a+b)(a^2-2ab+b^2+ab)\\ &=(a+b)((a-b)^2+ab) \end{align}$$

I am testing a program that uses the formula mentioned above and have discovered that it is extremely slow, because I have to check both cases and take the square root. You might like to check this answer as it may be faster to check the interval instead for an integer. The simplest way I know of to do this is to take the floor value of both numbers: $$\left\lfloor\frac{1+\sqrt{5}}{2}(a^3+b^3)-\frac{1}{a^3+b^3}\right\rfloor\lower{1em}{\LARGE,}\left\lfloor\frac{1+\sqrt{5}}{2}(a^3+b^3)+\frac{1}{a^3+b^3}\right\rfloor$$ If both numbers are equal, the number is not Fibonacci. If they are different, it is!

Edit: Forget about everything I said above. It turns out to be far more efficient to iterate through the Fibonacci numbers, testing the sums of cubes for each one, as: $$a\leqslant\sqrt[\LARGE 3]{\frac{F_n}{2}},b=\sqrt[\LARGE 3]{F_n-a^3}$$ So in short, my answer was right the first time. My program could still be more efficient, but it's up to $\require{enclose}\enclose{horizontalstrike}{F_{122} F_{141}}F_{168}$ already. I'm also using the modular constraints$\mod 63$ to catch some of the ones that are definitely not sums of cubes, which makes the program even faster. Instead of checking the sums of cubes directly, I am checking for this for every $a,b$: $$(a+b)\mid F_n\\ \frac{F_n}{a+b}=a^2-ab+b^2$$ So far, $F_3=2$ is the only sum of cubes in the Fibonacci sequence.

$\endgroup$
1
$\begingroup$

I thought I would add my thoughts.
Using the constraints for moduluses in this question, one can find the periods of the fibbonacci sequence modulus the same integers:
$F_n \mod 7$ gives the following period
$0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1$
$F_n \mod 9$ gives the following period
$0,1,1,2,3,5,8,4,3,7,1,8,0,8,8,7,6,4,1,5,6,2,8,1$
$F_n \mod 63$ gives the following period
$0,1,1,2,3,5,8,13,21,34,55,26,18,44,62,43,42,22,1,23,24,47,8,55,0,55,55,47,39,23,62,22,21,43,1,44,45,26,8,34,42,13,55,5,60,2,62,1$
Using these numbers one can derive:
if $F_n = a^3+b^3$, none of the following have an integer solution.
$16x+4=n$
$16x+11=n$
$24x+4=n$
$24x+5=n$
$24x+7=n$
$24x+8=n$
$24x+17=n$
$24x+19=n$
$48x+4=n$
$48x+5=n$
$48x+7=n$
$48x+16=n$
$48x+17=n$
$48x+19=n$
$48x+20=n$
$48x+28=n$
$48x+29=n$
$48x+31=n$
$48x+32=n$
$48x+36=n$
$48x+40=n$
$48x+41=n$
$48x+43=n$
$48x+44=n$
So if one can show that all integers above some constant satisfy atleast one of the above, and then test $F_1...F_c$ for having being a sum of 2 cubes where $c$ is that constant, you would have a proof.

$\endgroup$
  • 2
    $\begingroup$ There's one major problem with the modular constraints you based your equations on. They treat perfect cubes and differences of cubes just like sums of cubes. This can result in false positives within the Fibonacci sequence--for example, $8$, $34$, and $55$, just to name a few. $\endgroup$ – Brian J. Fink May 17 '14 at 3:23
  • $\begingroup$ OK my bad...apparently the modular constraints are the same regardless of the sign of either term! Oops! $\endgroup$ – Brian J. Fink May 19 '14 at 19:14
  • $\begingroup$ Unfortunately, your constraints - which would IMHO be better written just as e.g. $n\not\equiv 4\pmod {16}$, etc. - don't cover all the residue classes mod 48; for instance, all $n\equiv 1\bmod 48$ will still 'fall through' your sieve. $\endgroup$ – Steven Stadnicki May 21 '14 at 0:37
  • 3
    $\begingroup$ There will walways be some residue class that falls through finitely many modular constraints - simply because there exists one solution $\endgroup$ – Hagen von Eitzen May 23 '14 at 6:39
  • 1
    $\begingroup$ @Darksonn Hagen von Eitzen was referring to problems (such as this one) in which there is some solution. The modular restrictions have to allow this solution to exist and consequently allow infinitely many other candidate values too. Of course, other methods can then be used to rule them out; but purely modular arithmetic approach would be insufficient. $\endgroup$ – Peter Košinár May 24 '14 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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