The question of knowing whether there are infinitely many Fibonacci primes is an open question. As $F_p$ is prime only if $p$ is prime, one has $\pi_{FP}(x)\le \pi(\log_{\phi} x+0.5\log 5)$, but numerical computations seem to show that this quantity is roughly equal to $\log_{\phi}\log_{\phi}x$, where $\pi_{FP}(x)$ is the number of Fibonacci primes below $x$. Is there any heuristics suggesting this estimation should be true?
Thanks in advance.

  • $\begingroup$ What is Fibonacci prime? And what is $\phi$? $\endgroup$ – Lior Bary-Soroker Aug 4 '14 at 17:50
  • $\begingroup$ A Fibonacci prime is a prime occurring in Fibonacci sequence, and $\phi=\dfrac{1+\sqrt{5}}{2}$ is the so-called golden ratio. $\endgroup$ – Sylvain JULIEN Aug 4 '14 at 18:02
  • 3
    $\begingroup$ Gregory P. B. Dresden, in his review of Einsiedler, Manfred; Everest, Graham; Ward, Thomas(4-EANG); Primes in elliptic divisibility sequences, LMS J. Comput. Math. 4 (2001), 1–13, writes, "...the Mersenne numbers are thought to be prime infinitely often; as for the Fibonaccis, it's anyone's guess." $\endgroup$ – Gerry Myerson Aug 5 '14 at 3:49

We need to find a reasonable-sounding answer for the following question: for a fixed prime $p$; what is the probability that $F_p$ is prime?

A prime $q<F_p$ divides $F_p$ if and only if $z(q)$ divides $p$, where $z$ is the classical Fibonacci entry point. Therefore, we must have $z(q)=p$ for our candidate prime factor.

First, we must limit the size of $q$-it can't be any number. Since $q$ is prime, $z(q)$ is a divisor of $q-\left ( \frac{q}{5} \right )$ (exercise), and in particular it is $\leq q+1 \approx q$. We conclude that $q\gtrsim p$.

On the other hand, from $F_n \sim \varphi^n/\sqrt 5$ and $q<F_p$ one has $q\lesssim\varphi ^p$ (and this is the best we can hope for as there is equality when $q=F_p$ is prime).

What is the probability that $z(q)=p$? Since we know nothing about $q$ and $p$ except that they are prime, it is not too absurd to assume that $z(q)$ is a random integer between $\log q/\log \varphi$ and $q+1$, so its probability to be $p$ is about $\frac 1 q$ (I will return on this point later).

The probability that for a fixed $p$ a candidate prime factor $q$ of $F_p$ does not exist is then about $$ \prod_{p<q<\varphi^p} \left ( 1-\frac 1 q \right ) \approx \frac{\text{e}^{-\gamma}}{\log \varphi ^p} \Big/ \frac{\text{e}^{-\gamma}}{\log p}=\frac 1 {\log \varphi} \frac{\log p}{p}$$ by Mertens.

The expected count of those primes up to $x$ is the sum of the individual probabilities up to $\log_\varphi x$ (the quantity of Fibonacci numbers up to $x$), that is $$ \frac 1 {\log \varphi}\sum_{p <\log_\varphi x} \frac{\log p}{p} ,$$ and Čebyšëv tells us this is about $\log_\varphi \log_\varphi x$.

Now, a comment:

The assumption I made about the probability of $z(q)=p$ is very rough, and has a high probability of being wildly inaccurate. The reason is that we know something more than only the primality of $p$ and $q$: $z(q)$ isn't just any random number between $\log_\varphi q$ and $q+1$, it is a divisor either of $q+1$ or $q-1$! So, in order for $z(q)=p$ to be true, necessarily $q \equiv \pm 1 \pmod p$. For a more refined heuristic one would then have to take the product only over those $q$, and use some widely-believed statistic on the factorization of shifted primes-the calculations are not immediate and I haven't carried them out, but this is a thorny point and I am open to discussion about more sensible assumptions.

Another good starting point would be the nice paper by Cubre and Rouse.


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.