# When has the Borel-Cantelli heuristic been wrong?

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:

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.

• One has to be careful with this heuristic in the presence of algebraic structure, such as an Elliptic curve. A good example is Fermat's last theorem for n=3, heuristically false but of course actually true: mathoverflow.net/a/103493/766 Apr 15, 2015 at 20:35
• I'm not sure what you are looking for. There is a function field example of Swan ams.org/mathscinet-getitem?mr=144891 , elaborated by Conrad, Conrad and Gross math.uconn.edu/~kconrad/articles/genuszero.pdf : For any $f \in \mathbb{F}_2[u]$, the polynomial $f^8+u^3$ is not irreducible in $\mathbb{F}_2[u]$, although $\sum_{f \in \mathbb{F}_2[u]} 1/\deg(f^8+u^3)$ diverges and there is no obvious obstacle. Apr 15, 2015 at 20:56
• Well, if you don't subtract the one to get to the Mersenne primes, the same logic would suggest that there are infinitely many primes of the form $2^n$, no? Apr 15, 2015 at 21:40
• How about the Maier phenomenon that occasionally there are intervals around $x$ of length $(\log x)^{100}$ say with substantially more (or fewer) primes than one would expect? Apr 15, 2015 at 21:58
• @DavidSpeyer, for the convenience of anyone reading this let me point out in that example in $\mathbf F_2[u]$ that there is an obstacle, but it's not local: if $f(0) \not= 0$ then $\mu(f^8+u^3) = 1$, so $f^8 + u^3$ can't be irreducible (it's easier to see this if $f(0) = 0$). The calculation of the M\"obius function of $f^8+u^3$ is, as you say, not obvious. Apr 16, 2015 at 4:51

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).

• This is a nice example for this question as Lang and Stark had previously applied "probabilistic reasoning" to it to get $10$ as the barrier, and even noted that there might be finitely many "exceptional families" that surpassed this. It was left to Elkies to actually exhibit one. Further, the "$x^3+ax+b$ is a square" condition (and estimation of its probability) is exactly what Granville is using in his rank heuristics, so it gives some indication that his guess might underestimate reality. Apr 16, 2015 at 17:00

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$.

• The work to decide whether 78557 is the smallest such $n$ continues, seventeenorbust.com Apr 16, 2015 at 23:20
• @GerryMyerson: en.wikipedia.org/wiki/Sierpinski_number says that 78557 is the minimum for the form Stefan mentioned. Apr 17, 2015 at 2:21
• @user, I missed that --- but it seems to me that the result you cite depends on the primality of numbers like $2^{9092392}+40291$, and that those numbers have been shown to be probable primes, but have not been proved to be primes. E.g., en.wikipedia.org/wiki/Megaprime cites this number as a probable prime, but not as a prime. Apr 17, 2015 at 3:17
• @GerryMyerson: Oh I missed that! =) Apr 17, 2015 at 3:40

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.

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.

• If $n\ge2$, the argument gives $p=k2^{n+2}+1$. For this, use the fact that $2$ is a square imod $p$. This can be used to detect the first factor of $F_5$. It is a prime number of the form $k2^7+1$. But $k\ne1,3,4$ (not prime) $k\ne2$ (because another $F_m$ cannot be a factor). So the first candidate is $5\cdot128+1=641$, a factor found by Euler. Apr 19, 2015 at 20:58