Fortunately

This Numberphile video talks about the Fortune conjecture, and as presented, it seems quite mysterious. But it’s less so once you think about it.

Let’s start with Euclid’s proof that the number of primes is infinite. If you assume the contrary, that there are exactly $l n$ primes which we can denote $l p_1, p_2, p_3, …, p_n$, then there exists a number $l q=p_1p_2p_3…p_n+1$. That number isn’t divisible by any of $l p_1$ through $l p_n$; there is always a remainder of $l 1$. So either $l q$ is a prime not in our list of “all” the primes, or it is a composite whose prime factors are not in our list. Either way we’ve shown there exists at least one prime not in our list, contradicting our claim that the list was complete. The only way to avoid this contradiction is if the list of primes is infinite.

Fine, but now let’s think more about multiplying primes together. We can regard $l p_1$ through $l p_n$ as a list of the first $l n $ primes. Then $l p_n\# = p_1p_2p_3…p_n$ is called the $l n$th primorial, and we can use it to prove the size of the gaps between successive primes has no upper bound. Because $l p_n\#+1$ might or might not be a prime, but $l p_n\#+2$ definitely isn’t — $l p_n\#$ is always even (since its first prime factor is 2), and $l 2$ is even, so $l p_n\#+2$ is even. Likewise, except for $l p_1\#$, $l p_n\#+3$ is divisible by $l 3$ since $l 3$ is a factor of both terms. $l p_n\#+4$ is divisible by 2. $l p_n\#+5$ (except for $l p_1\#$ and $l p_2\#$) is divisible by 5. And so on: for all $l m$ where $l 2\le m\le p_n$, $l p_n\#+m$ is divisible by the prime factors of $l m$. And $l p_n\#+p_n+1$ is even. So the $l p_n$ consecutive numbers from $l p_n\#+2$ through $l p_n\#+p_n+1$ are all composite. And since there is no upper limit on the primes, that means there is no upper limit on the gap betwen consecutive primes.

By the same logic, for $l n\ge 3$, while $l p_n\#-1$ may or may not be prime, $l p_n\#-2$ through $l p_n\#-p_n-1$ must be composite.

For example: $l p_3\# = 2\times3\times5 = 30$. It happens that $l p_3\#+1 = 31$ is prime. But $l p_3\#+2$ through $l p_3\#+5+1$ are $l 32, 33, 34, 35, 36$: five consecutive composite numbers. $l 37$ is prime, and the gap between $l 31$ and $l 37$ is $l 6 = p_n+1$. In addition, $l p_3\#-2$ through $l p_3\#-5-1$ are $l 28, 27, 26, 25, 24$: five more consecutive composite numbers, and there is another gap of $l 6$ between $l 23$ and $l 29$.

For other values of $l n$, the strings of composite numbers may be even longer than $l p_n$. There is no reason why $l p_n\#+p_n+2$ and numbers above that couldn’t also be composite. For instance, $l p_5\# = 2310$, $l 2311$ is prime, and the $l p_n=13$ numbers starting with $l 2312$ are composite, but then so are the next $l 8$ for a total of $l 21$ consecutive composites. And if $l p_n\#+1$ is composite, then that and $l p_n\#$ itself extend the gap by another two, and if additionally $l p_n\#-1$ is composite then the string must extend at least down to $l p_n\#-p_n-1$, for a length about double the minimum.

(Long composite strings also can occur far from a primorial, and generally do. For example, there are $l 33$ consecutive composites between the primes 1327 and 1361. Generally, above $l p_2\#=6$, the gap associated with a primorial is smaller than the maximum size gap that can be found before that primorial.)

So we don’t know how far it is from the $l n$th primorial to the next prime (after $l p_n\#+1$), only that (1) the distance $l m$ is at least $l p_{n+1}$ and (2) $l m$ has no prime factors less than or equal to $l p_n$ — because then $l p_n\#+m$ would be composite.

That distance $l m$ is called a Fortunate number, named for Reo Fortune (who was $l not$ professionally a mathematician, but a social anthropologist, and who was married, not for very long, to Margaret Mead). The first several primorials, the first prime after that primorial plus one, and the corresponding Fortunate number, are:

All the Fortunate numbers shown here, and in fact all the known Fortunate numbers, are odd. But they have to be. They’re the difference between a prime greater than $l 2$, which must be odd, and a primorial, which must be even.

But they all are not just odd; they all are prime. They do not have to be, or at least there is no evident reason they have to be. Fortune’s conjecture is that there are no composite Fortunate numbers. There is no known proof, but there is no known counterexample either.

Paul Carpenter has defined the less-Fortunate numbers analogously: just as the Fortunate numbers are the distances between $l p_n\#$ and the smallest prime greater than $l p_n\#+1$, the less-Fortunate numbers are the distances between $l p_n\#$ and the largest prime less than $l p_n\#-1$. All the known less-Fortunate numbers also are prime.

The primeness of the Fortunate and less-Fortunate numbers may seem surprising at first. But remember: for $l p_n\#+m$ (or $l p_n\#-m$) to be prime, $l m$ must have no prime factors less than $l p_{n+1}$. Then if the (less-)Fortunate number $l m$ is to be composite, it must be no smaller than $l p_{n+1}^2$. In other words, that prime must end a string of at least $l p_{n+1}^2$ consecutive composite numbers.

Which is a lot!

For instance, as mentioned above, the Fortunate number associated with $l p_5\#$ is $l 23$. That’s bigger than the minimum value of $l p_6=13$, but it’s smaller than the gap of $l 33$ found earlier.

But suppose $l p_5\#$ had a composite Fortunate number. Its minimum value would then be not $l 13$ but $l 13^2 = 169$! A much larger prime gap than you would expect to find at that point. There is no reason such a gap could not occur there, a priori, but it would have to be considered hugely unlikely.

But hugely unlikely times infinity is still infinity. The most improbable things will happen after enough trials, right?

Yes, except that as you go to higher and higher numbers, the discrepancy between the size gap you expect and the size needed for a composite Fortunate number gets larger.

By the prime number theorem, asymptotically the average gap between prime numbers up through integer $l N$ is roughly $l \log(N)$. The $l n$th prime is about $l n\log(n)$. The $l n$th primorial is about $l e^{n \log(n)}$. So the average gap through the $l n$th primorial is about $l n\log(n) \approx p_n$. Compare this to the gap of at least $l p_{n+1}^2$ needed for a composite Fortunate number. The latter is vastly larger, and vaster for larger and larger $l n$.

It’s not just that the probability is low, it’s getting lower as you go. If it’s getting lower fast enough, even an infinite number of trials won’t be enough. That’s the kind of thing that’s happening here, and so Fortune’s conjecture is considered likely to be true.

And if it isn’t true, the first counterexample is probably inconceivably above the limits we can compute, and will never be found.