Question

This is a question about the open problem Fibonacci divisibility from the Open Problem Garden.

The problem, originally stated in 1960 by D.D. Wall, has several equivalent formulations one of which is:

Find a prime $p$ with $p^2|a_{p-\left(\frac{p}{5}\right)}$,

where $a_n$ is the $n$-th Fibonacci number. Such primes are often called Wall-Sun-Sun primes.

Since always $p|a_{p-\left(\frac{p}{5}\right)}$ Crandall, Dilcher and Pomerance assumed uniform distribution of the residues and proposed the heuristic $\log \log y -\log \log x$ for the number of such primes in the interval $[x,y]$. Several authors did computer aided searches and no such prime was found up to $9.7 \times 10^{14}$. That confuses me and therefore my question.

Q: Is the heuristic of Crandall, Dilcher and Pomerance (maybe in its patched version by Klaska) still considered state of the art? If not, are there other approaches?

Edit: For me the question is sufficiently answered. That is more that I could hope for. Thank you very much!

Answer 1

As quid mentioned, Klyve and I have done some computational investigations on Fibonacci-Wieferich/Wall-Sun-Sun primes. In particular, we collected all primes $p < 9.7\times10^{14}$ such that $F_{p-(p/5)} \equiv Ap \pmod{p^2}$ with $|A| < 2\times10^6$. I've just crunched our data for primes in the range from $6.5\times10^{14}$ to $9.5\times10^{14}$ to see if the incidence of small values of $A$ matches the Crandall–Dilcher–Pomerance heuristic. Here are the results:

$$\begin{matrix} p \in [6.5\times10^{14},7.0\times10^{14}) & : & 2112 & 2085 & 2083 & 2155 & 2170.39 \cr p \in [7.0\times10^{14},7.5\times10^{14}) & : & 1905 & 1915 & 2021 & 1953 & 2016.36 \cr p \in [7.5\times10^{14},8.0\times10^{14}) & : & 1867 & 1854 & 1781 & 1870 & 1882.50 \cr p \in [8.0\times10^{14},8.5\times10^{14}) & : & 1768 & 1779 & 1707 & 1669 & 1765.11 \cr p \in [8.5\times10^{14},9.0\times10^{14}) & : & 1598 & 1561 & 1650 & 1686 & 1661.35 \cr p \in [9.0\times10^{14},9.5\times10^{14}) & : & 1568 & 1592 & 1519 & 1556 & 1568.96 \cr \end{matrix}$$

The first four columns report the count of primes $p$ in the given interval whose corresponding $A$ values lie in the respective intervals $(-2\times10^6,-10^6)$, $(-10^6,0)$, $(0,10^6)$, and $(10^6,2\times10^6)$. The last column represents the value predicted by the Crandall–Dilcher–Pomerance heuristic (namely $10^6\log\left(\frac{\log y}{\log x}\right)$ for the interval from $x$ to $y$).

The agreement between experimental data and theoretical values is pretty good. If I understand Klaška's adjustment correctly, he proposes an expected count of roughly half that proposed by the Crandall–Dilcher–Pomerance heuristic. Thus, the data does not appear to support Klaška's modified heuristic. However, note that Klaška's argument is specifically for the special value $A = 0$, so the above data does not invalidate his proposed estimate.

Answer 2

A very recent paper on computations on this and related things is by Dorais and Klyve; they write that their computations (for the related Wieferich primes) are in line with a conjecture of Crandall, Dilcher, Pomerance. So, it does not appear there was much change in the general expectation and what you mention still seems to be state of the art.

Also note that Crandall, Dilcher, Pomerance were aware of inexistence up to about $10^{12}$. Now $$ \log \log (10^{15}) - \log log (10^{12}) = 0.22...$$ so that also in the larger range nothing was found does not seem to shake the heuristic of CDP too much; one would not expect to find something.