Gaps Between Primes - Part 1/2

 We've seen:

• the primes are not so thinly spread out that the sum of their reciprocals converges
• the primes appear to have a density of $1/\ln(x)$ around $x$

Intuitively, this suggests that there must be a constraint on the gaps between primes. 

This post explores the question of gaps between primes.

A video accompanying this post is here: [youtube], and slides here [pdf].

Factorials

Let's remind ourselves of factorials. The factorial of a counting number $n$ is the product of all the whole numbers between 1 and that number, and is written $n!$.

$$ n! = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1 $$

For example, $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$.    

It is clear that factorials are not primes. In fact they are almost the antithesis of primes, because $n!$ contains every number below $n$ as a factor. The only exceptions are $2!=2$, $1!=1$ and $0!=1$ which are small enough not to have factors.

Prime Gaps

Let's consider a sequence of numbers from $5!+2$ to $5!+5$.

$$ 5! + 2 = (5 \cdot 4 \cdot 3 \cdot 1 +1)\cdot 2 $$

$$ 5! +3 = (5 \cdot 4 \cdot 2 \cdot 1 +1)\cdot 3 $$

$$ 5! +4 = (5 \cdot 3 \cdot 2 \cdot 1 +1)\cdot 4 $$

$$ 5! +5 = (4 \cdot 3\cdot 2 \cdot 1 +1)\cdot 5 $$

We can see all the numbers from $(5!+2)$ to $(5!+5)$ are not prime. We can generalise this to say that the entire sequence from $n!$ to $(n!+n)$ is not prime, a sequence of length $n-1$. 

Because $n$ can be as large as desired, we've just proved there is no upper limit on prime gaps.

The primes continue to surprise us. We started with the fact that the primes can't be too sparse, and yet we have proved there is no upper limit on the gaps between primes. Both facts can be true if large prime gaps are rare. 

Distribution of Prime Gaps

If we counted all the prime gaps in a moderately large range, we'd expect large gaps to be rare. It isn't obvious whether medium sized gaps would occur more or less often than the smallest gaps.

The following plot shows the logarithm of frequency of prime gaps in the range 1 to 500,000,000. We can see there is only one prime gap of size 1, that between $p=2$ and $p=3$.

Note: the convention for prime gaps sizes is $p_{n+1}-p_n$, so the gap between 2 and 3 is 1, not 0.

It is surprising to see the distribution so tightly constrained. The overall shape appears to be very linear, and there are clear regions above and below the line where no prime gap counts seem to occur. 

Twin Prime Conjecture

Looking again at the distribution, gaps of size 2 seem to occur more often than almost all other sizes. You may have noticed these twin primes pop up more often than expected along the number line:

$$(3,5),(5,7),(11,13),(17,19)\ldots(101,103),(107,109)\ldots$$

The Twin Prime Conjecture says that we'll keep finding twin primes along the number line, that they don't run out. This is yet another simple statement about primes that remains unproven.

Next Time..

In part 2 we'll see how simplified probabilistic models of the primes can help explain the prime gap distribution.