When has the Borel-Cantelli heuristic been wrong?

Question

The Borel-Cantelli lemma is very frequently used to give a heuristic for whether or not certain statements in number theory are true.

For example, it gives some evidence that there are finitely many Fermat Primes, that is primes of the form $F_n=2^{2^{n}}+1$. Since the asymptotic density of the primes around $x$ is $\frac{1}{\log x}$, we expect that $$\text{Pr}\left(F_n\text{ is a prime number}\right)\approx \frac{1}{2^n}.$$ As the series $\sum_{n=1}^\infty \frac{1}{2^n}$ converges, Borel-Cantelli suggests that there will be finitely many Fermat Primes.

More examples:

• Infinitude of the Mersenne Primes, since $\sum_{n=1}^\infty \frac{1}{n}$ diverges.
• Heuristic justification for the ABC conjecture on Tao's blog.
• Two different heuristics that there are only finitely many elliptic curves of rank greater than $21$. The first is due to Granville, and the second is recent work of of Garton, Park, Poonen, Voight and Wood.

In the case of Mersenne primes and Fermat primes, some major assumptions are made about independence, but even then, Borel-Cantelli can only ever be a heuristic since a "probability $0$ event" could still occur.

My question is: How reliable is this heuristic? Are there any known cases/past conjectures where the Borel-Cantelli heuristic has been incorrect?

Edit: As Terence Tao mentions, the Borel-Cantelli heuristic fails for the $n=3$ case of Fermat's last theorem due to algebraic structure. Examples like this are exactly what I am looking for.

Answer 1

There is an example of Elkies in Appendix II (page 718, and 13 in the PDF) of this paper.

The context therein is that we want "large" integral points on elliptic curves, so $y^2=x^3+ax+b$ with each of these an integral parameter. The proper yardstick by which to measure is to try to maximize $x$ in terms of $a$ and $b$, namely by the quotient $\rho=\frac{\log x}{\log \max(|a|^{1/2},|b|^{1/3})}$. Considering $|a|\sim T^2$ and $|b|\sim T^3$, the probabilistic heuristic says $x^3+ax+b$ is square about $1/x^{3/2}$ of the time (for large $x\gg T$), and summing gives $$\sum_{x\sim T^\lambda}\sum_{a\sim T^2}\sum_{b\sim T^3} \frac{1}{x^{3/2}}\approx \frac{T^5}{T^{\lambda/2}}$$ for the number of such integral points in a dyadic $x$-interval of size $T^\lambda$. So when $\lambda \ge 10+\epsilon$, there should be no solutions as $T\rightarrow\infty$ (equivalently stated, for every $\epsilon \gt 0$ there should be finitely many integral points with $\rho\ge 10+\epsilon$).

But Elkies cleverly recalls Pell, and considers the polynomial equation $$Q(t)Y(t)^2=X(t)^3+A(t)X(t)+B(t)$$ for polynomials $A,B,Q,X,Y$ with $Q$ quadratic. The idea will then be to specialize the $t$-parameter so that $Q(t)$ is square (if there is one integral $t$ with $Q(t)$ square, there are infinitely many). By counting parameters he finds there are four cases (of degrees of $A,B,X,Y$) with prospects of a solution with $\rho\rightarrow 12$ as $t\rightarrow\infty$, and in the smallest case this solution is defined over the rationals: $$X(t)=6(108t^4-120t^3+72t^2-28t+5)$$ $$Y(t)=72(54t^5-60t^4+45t^3-21t^2+6t-1)$$ $$Q(t)=2(9t^2-10t+3),A(t)=132,B(t)=-144(8t-1)$$ with $X(t)\sim B(t)^4/2^{25}3^4$ so that $\rho\rightarrow 12$ on the sparse set of $t$-values with $Q(t)$ square (note that $Q(1)=4=2^2$, indeed the whole $ABQXY$-system was scaled by 2 to force this).

This is mentioned (in 11.5) in the above citation for Granville's rank heuristic, though for the latter there is a more recent version specified to rank 21 (rather than rank 7 in quadratic twist families).

Answer 2

The Borel-Cantelli heuristic suggests that for any odd $n \in \mathbb{N}$, there is some $k \in \mathbb{N}$ such that $n+2^k$ is prime -- and for small $n$ this is in fact true (in particular, for any odd $n \leq 771$ some $k \leq 29$ works). However for $n = 78557$ this fails, i.e. $78557 + 2^k$ is composite for every $k$.

Answer 3

I may as well convert my comment to an answer. The probability that a randomly chosen degree $d$ polynomial in $\mathbb{F}_p[u]$ is irreducible is $d^{-1} \cdot (1+O(p^{-d/2}))$. So, if $g(T,u)$ is a polynomial in $\mathbb{F}_p[T,u]$, with degree $k$ in $T$, you'd expect $g(f(u), u)$ to be irreducible with probability roughly $\deg(g(f(u),u))^{-1} =(k \deg f(u)+c)^{-1}$ for $\deg f(u)$ large. Since there are $\approx p^d$ polynomials of degree $d$, one expects $\approx p^d/(dk+c)$ polynomials $f$ of degree $d$ for which $g(f(u), u)$ is irreducible which goes to $\infty$ as $d$ grows.

There are two obvious ways this can go wrong:

(1) There is some polynomial $\pi(u)$ such that $g(f(u), u)$ is divisible by $\pi(u)$ for all $f(u)$.

(2) The polynomial $g(T, u)$ factors as $g_1(T, u) \cdot g_2(T,u)$ over $\overline{\mathbb{F}}_p[u]$.

Buniakowsky's conjecture states that, for the analogous problem over the integers, these are the only obstacles to $g(T)$ taking prime values for infinitely many $T$.

However, Swan shows that $f(u)^8 + u^3$ is never irreducible, for $f(u) \in \mathbb{F}_2[u]$, although $T^8+u^3$ suffers neither of the previous problems. Rather, the problem is that $\mu(f(u)^8+u^3)$ is always $0$ or $1$ (where $\mu$ is the obvious generalization of the Mobius function to $\mathbb{F}_2[u]$). Conrad, Conrad and Gross explain, in a very readable paper, how Buniakowsky's conjecture should be adjusted to compensate for this issue.

Answer 4

In your question you mention a heuristic that there are finitely many Fermat primes. However, an order argument shows that $2^{2^n}+1$ can only be divisible by primes of the form $k2^{n+1}+ 1$. This changes the estimate to infinitely many Fermat primes, and even predicts a constant fraction of Fermat numbers being prime(!)

Maybe an even more sophisticated heuristic brings the estimate back to finite. Either way, at least one of the heuristics must be wrong.

EDIT: But wait! The same order argument that shows that only primes of the form $k2^{n+1}+1$ can be factors, also shows that those primes are intrinsically more likely to be factors. A prime $p_k=k2^{n+1}+1$ divides $F_n=2^{2^n}+1$ if and only if $2$ has order $2^{n+1}$ modulo $p_k$. There are $2^n$ residue classes modulo $p_k$ with this order. So, the probability that $2$ is one of these residue classes, and hence the probability that $p_k$ is a factor of $F_n$, is heuristically $\sim 1/k$.

I believe this again predicts finitely many Fermat primes. At this point, I would not be surprised to see a yet more sophisticated argument predicting the opposite.