# is there any heuristics suggesting that the number of Fibonacci primes below $x$ is equivalent to $\log_{\phi}\log_{\phi}x$?

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?

• What is Fibonacci prime? And what is $\phi$? – Lior Bary-Soroker Aug 4 '14 at 17:50
• A Fibonacci prime is a prime occurring in Fibonacci sequence, and $\phi=\dfrac{1+\sqrt{5}}{2}$ is the so-called golden ratio. – Sylvain JULIEN Aug 4 '14 at 18:02
• 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." – 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.