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 \dots \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)\dots (101,103),(107,109)\dots$$

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.

Chebyshev's Estimates For π(x)

Pafnuty Chebyshev proved Bertrand's Postulate that there is at least one prime between a number and its double, $n\le p\le 2n$, and came close to proving the Prime Number Theorem. 

In this post we'll recreate his estimates for the prime counting function $\pi (x)$ which came close to the actual PNT. The approach is inspired by a note by Franz Lemmermeyer [pdf].

A Bit Of History

We've previously discussed how Gauss and Legendre used experimental evidence to suggest that the prime counting function $\pi (x)$ is of the form $\frac{x}{\ln (x)}$, and that this approximation gets better for larger $x$ - in the sense that the ratio between the true count and this approximation gets ever closer to 1.

$$\pi (x)\sim \frac{x}{\ln (x)}$$

This is the Prime Number Theorem (PNT), which took another 100 years to be proved by Hadamard and de la Vallee-Poussin in 1896.  

Before that final proof, around 1850, Chebyshev got  close to proving the PNT by showing that $\pi (x)$ can be bounded as follows, where $c_1,c_2$ are constants $>0$.

$$c_1\frac{x}{\ln (x)}<\pi (x)<c_2\frac{x}{\ln (x)}$$

This is a remarkable result, and in fact was strong enough to prove Bertrand's Postulate that there is a prime between a number and its double, $n<p<2n$.

Starting With Combinations

We start with an observation about binomial coefficients:

$$2^{2n}=(1+1{)}^{2n}=(\genfrac{}{}{0ex}{}{2n}{0})+\dots +\dots (\genfrac{}{}{0ex}{}{2n}{n})+\dots +(\genfrac{}{}{0ex}{}{2n}{2n})$$

Because $(\genfrac{}{}{0ex}{}{2n}{n})$ is only one of those terms we can say:

$$\begin{array}{rl}{2}^{2n}& >(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{n!n!}\\ \\ & =\frac{(2n)\cdot (2n-1)\cdot \dots \cdot (n+1)}{n\cdot (n-1)\cdot (n-2)\dots \cdot 2\cdot 1}\end{array}$$

Looking at that fraction, we can say that the numerator contains primes $n<p\le 2n$, and these primes don't appear in the denominator. This means each of those primes divides the  whole fraction without remainder, and so does the product of those primes.

$$\prod _{n<p\le 2n}p\text{ divides }(\genfrac{}{}{0ex}{}{2n}{n})$$

How many primes are there $n<p\le 2n$? The answer is of course $\pi (2n)-\pi (n)$.

If we raised $n$ to this number, it would be smaller than the actual product of those primes $\prod _{n<p\le 2n}$. This is because each of those primes is greater than $n$.

$$n^{\pi (2n)-\pi (n)}<\prod _{n<p\le 2n}p\le (\genfrac{}{}{0ex}{}{2n}{n})<2^{2n}$$

We can take logs and simplify:

$$\boxed{{\displaystyle \pi (2n)-\pi (n)<2\ln (2)\cdot \frac{n}{\ln (n)}}}$$

We now have a relation relating $\pi (n)$ to $n$. Intuitively it hints at $\pi (n)$ being of the form $n/\ln (n)$.

To find a form for $\pi (n)$ not involving $\pi (2n)$ we use induction.

Upper Bound

Let's try the following form for $\pi (n)$:

$$\pi (2^k)\le 3\cdot \frac{2^k}{k}$$

We can examine our inequality with $n=2^k$:

$$\begin{array}{rl}\pi (2^{k+1})& \le \pi (2^k)+2\ln (2)\cdot \frac{2^k}{\ln (2^k)}\\ & =\pi (2^k)+2\cancel{\ln (2)}\cdot \frac{2^k}{k\cancel{\ln (2)}}\\ & =\pi (2^k)+\frac{2^{k+1}}{k}\end{array}$$

Our proposed form for $\pi (n)$ gives us

$$\begin{array}{rl}\pi (2^{k+1})& \le 3\cdot \frac{2^k}{k}+2\cdot \frac{2^k}{k}\\ & =5\cdot \frac{2^k}{k}\\ \pi (2^{k+1})& \le 3\cdot \frac{2^{k+1}}{k+1}\end{array}$$

That last inequality appears to be only true for $k>5$ because $5\cdot \frac{2^k}{k}<3\cdot \frac{2^{k+1}}{k+1}$ is only true for $k>5$. However, numerically checking $\pi (2^{k+1})$ for $k\le 5$ confirms it is true for all $k$.

We've shown that if $\pi (2^k)\le 3\cdot \frac{2^k}{k}$ is true for $k$ it is also true for $k+1$. We've also shown it is true for some $k$, for example, $k=1$ because $\pi (2^1)=1\le 3\cdot \frac{2^1}{1}=6$. This completes the induction proof for this form of $\pi (2^k)$.

Now, if we set $2^k<x\le 2^{k+1}$ we can say

$$\begin{array}{rl}\pi (x)& \le \pi (2^{k+1})\\ & \le 3\cdot \frac{2^{k+1}}{k+1}=6\cdot \frac{2^k}{k+1}\\ & \le 6\cdot \frac{2^k}{k}=6\ln (2)\cdot \frac{2^k}{\ln (2^k)}\\ \pi (x)& \le 6\ln (2)\cdot \frac{x}{\ln (x)}\end{array}$$

That least step requires $x\ge e$, but we can numerically verify that $\pi (x)\le 6\ln (2)\frac{x}{\ln (x)}$ is true for $x<e$.

And so finally we have an upper bound for the prime counting function $\pi (x)$, 

$$\boxed{{\displaystyle \pi (x)\le 6\ln (2)\frac{x}{\ln (x)}}}$$

On its own, the upper bound isn't enough to tell us about the true form of $\pi (x)$. We need the lower bound to be of a similar form, and fairly tight too.

Lower Bound

Going back to the binomial coefficients

$$2^{2n}=(1+1{)}^{2n}=(\genfrac{}{}{0ex}{}{2n}{0})+\dots +(\genfrac{}{}{0ex}{}{2n}{n})+\dots +(\genfrac{}{}{0ex}{}{2n}{2n})$$

we can see that $(\genfrac{}{}{0ex}{}{2n}{n})$ is the largest element, which means it must be $\ge$ than the average of these $2n$ terms (we have $2n+1$ terms but we can combine the first and last which each have a value of 1), so

$$\frac{2^{2n}}{2n}\le (\genfrac{}{}{0ex}{}{2n}{n})$$

Taking logs gives us

$$2n\ln 2-\ln (2n)\le \ln (\genfrac{}{}{0ex}{}{2n}{n})$$

We now need to think about the prime factorisation of $(\genfrac{}{}{0ex}{}{2n}{n})$. To do this we need to take a short diversion.

We know that  $(\genfrac{}{}{0ex}{}{2n}{n})$ is $\frac{(2n)!}{n!n!}$, so we need to think about the prime factorisation of $n!$. Luckily this is not too difficult. If $v_p(n)$ is the highest power of a prime $p$ dividing $n$, then $$\boxed{{\displaystyle v_p(n!)=\sum _m\lfloor \frac{n}{p^m}\rfloor }}$$ This is because in the set of numbers $\{1,2,3,\dots ,n\}$ there are $\lfloor \frac{n}{p}\rfloor$ multiples of $p$, $\lfloor \frac{n}{p^2}\rfloor$ multiples of $p^2$, $\lfloor \frac{n}{p^3}\rfloor$ multiples of $p^3$, and so on, each contributing 1 to $v_p(n!)$. Now, because $(\genfrac{}{}{0ex}{}{2n}{n})$ is $\frac{(2n)!}{n!n!}$, and because $v_p(a/b)=v_p(a)-v_p(b)$, we can say $$v_p(\genfrac{}{}{0ex}{}{2n}{n})=\sum _m(\lfloor \frac{2n}{p^m}\rfloor -2\lfloor \frac{n}{p^m}\rfloor )$$ Let's focus on that form $\lfloor 2x\rfloor -2\lfloor x\rfloor$. It only takes values 0 or 1. This is easy to see if we write $x=a+b$ where $a$ is the integer part of $x$, and $b$ is the fraction. $$\begin{array}{rl}\lfloor 2x\rfloor -2\lfloor x\rfloor & =\lfloor 2a+2b\rfloor -2\lfloor a+b\rfloor \\ \\ & =\cancel{2a}+\lfloor 2b\rfloor \cancel{-2a}-2\lfloor b\rfloor \\ \\ & =\{\begin{array}{l}0\text{ for }b<\frac{1}{2}\\ 1\text{ for }b>\frac{1}{2}\end{array}\end{array}$$ The largest $m$ is $\lfloor \frac{\ln (2n)}{\ln p}\rfloor$ because a larger $m$ would give $p^m>2n$ which isn't possible. So $v_p$ reduces as follows: $$\begin{array}{rl}{v}_p(\genfrac{}{}{0ex}{}{2n}{n})& =\sum _{1\le m\le \lfloor \frac{\ln (2n)}{\ln p}\rfloor }(\lfloor \frac{2n}{p^m}\rfloor -2\lfloor \frac{n}{p^m}\rfloor )\\ \\ & \le \sum _{1\le m\le \lfloor \frac{\ln (2n)}{\ln p}\rfloor }1\\ \\ v_p(\genfrac{}{}{0ex}{}{2n}{n})& \le \lfloor \frac{\ln (2n)}{\ln p}\rfloor \end{array}$$ Knowing how $(\genfrac{}{}{0ex}{}{2n}{n})$ factorises into primes $p$ will be helpful.

We can now proceed:

$$\begin{array}{rl}2n\ln 2-\ln (2n)& \le \ln (\genfrac{}{}{0ex}{}{2n}{n})\\ \\ & \le \sum _{p\le 2n}\lfloor \frac{\ln (2n)}{\ln p}\rfloor \ln p\\ \\ & \le \sum _{p\le 2n}\ln (2n)\\ \\ & =\ln (2n)\cdot \pi (2n)\end{array}$$

Re-arranging gives us a lower bound for $\pi (2n)$:

$$\pi (2n)\ge \ln (2)\cdot \frac{2n}{\ln (2n)}-1$$

This is almost of the form we want $\pi (n)\ge c_1\cdot \frac{x}{\ln x}$. 

We can use induction again to prove that

$$\pi (x)\ge \frac{\ln (2)}{2}\cdot \frac{x}{\ln x}$$

Let's start with $2n<x\le 2n+2$, so

$$\pi (x)\ge \pi (2n)\ge \ln (2)\cdot \frac{2n}{\ln (2n)}-1$$

We're going to replace that $2n/\ln (2n)$ with an expression for $n$, and by assuming $x>16$:

$$\frac{2n}{\ln (2n)}-\frac{n+1}{\ln (2n)}=\frac{n-1}{\ln (2n)}\ge \frac{7}{4\ln 2}\ge \frac{1}{\ln 2}$$

We can manually show that the desired expression $\pi (x)\ge \frac{\ln 2}{2}\cdot \frac{x}{\ln x}$ is valid for $x\le 16$

This gives us:

$$\begin{array}{rl}\pi (x)\ge \pi (2n)& \ge \ln (2)\cdot \frac{2n}{\ln (2n)}-1\\ \\ & \ge \ln (2)(\frac{1}{\ln 2}+\frac{n+1}{\ln (2n)})-1\\ \\ & =\cancel{\ln (2)}\left(\frac{\ln (2n)+(n+1)\ln (2)}{\cancel{\ln (2)}\ln (2n)}\right)-1\\ \\ & =1+\frac{(n+1)\ln (2)}{\ln (2n)}-1\\ \\ & \ge \frac{(n+1)\ln (2)}{\ln (x)}\text{ because }x>2n\\ \\ & \ge \frac{(x/2)\ln (2)}{\ln (x)}\text{ because }x\le 2n+2\\ \end{array}$$

So we finally have 

$$\boxed{{\displaystyle \pi (x)\ge \frac{\ln (2)}{2}\cdot \frac{x}{\ln x}}}$$

The following illustrates these lower and upper bounds for $x\le 500$.

Bertrand's Postulate

Can Chebyshev's estimates be used to prove Bertrand's Postulate that there is a prime $p$ between $n$ and $2n$? Let's find out. 

Bertrand's postulate is the same as saying $\pi (2x)-\pi (x)>0$.

The smallest difference is when we take the lower bound for $\pi (2x)$, and the upper bound for $\pi (x)$:

$$\begin{array}{rl}{c}_1\frac{2x}{\ln (2x)}-c_2\frac{x}{\ln (x)}& >0\\ \\ 2c_1\cdot \ln (x)& >c_2\cdot (\ln (x)+\ln (2))\\ \\ (2c_1-c_2)\cdot \ln (x)& >c_2\cdot \ln (2)\end{array}$$

We can see that $(2c_1-c_2)$ must be positive, and so 

$$\boxed{{\displaystyle 2c_1>c_2}}$$

In our case, the bounds $c_1=\frac{1}{2}\ln (2)$ and $c_2=6\ln (2)$ aren't tight enough to prove Bertrand's Postulate. 

Chebyshev and others actually developed tighter bounds for $\pi (x)$ which do meet this requirement, $c_1=0.92$ and $c_2=1.11$, but those tighter bounds require much more work.

Thoughts

It is interesting that 

• Chebyshev's estimates for the prime counting function $\pi (x)$ are derived from the binomial coefficients of the expansion $(1+1{)}^{2n}$, a rather surprising source of useful inequalities. 

• the estimates are intimately linked to the prime factorisation of factorials. 

• the trail, albeit with some algebra work, can lead to a form for $\pi (x)$ that is $x/\ln (x)$, a form which hints at the Prime Number Theorem.

Additional work by Chebyshev showed that $c_1$ and $c_2$ can be as close to 1 as desired for large enough $x$.