Gaps Between Primes Using Probabilistic Models - Part 2/2

In this post we continue to look at the gaps between primes, and introduce the idea of using probabilistic models for primes.

The video for this topic is here (youtube), and accompanying slides are here (pdf).

Probabilistic models of primes, despite being built on rather broad simplifications, can match numerical evidence fairly well. Predictions from some of these models can become worthy conjectures about the primes. 

Here we build a particularly simple probabilistic model, and use it to predict the distribution of prime gaps.

Probability of a Prime

The Prime Number Theorem tells us the density of primes around $x$ is approximately $1/\ln(x)$. It isn't a big leap to interpret this density as a probability. So the probability $n$ is prime is simply

$$\Pr(n\text{ prime})=\frac{1}{\ln(n)}$$

Prime Gaps

A prime gap at $n$ of size 4 is a sequence {prime, not prime, not prime, not prime, prime}. The probability of this sequence is

$$\frac{1}{\ln(n)}\cdot\left(1-\frac{1}{\ln(n+1)}\right)\cdot\left(1-\frac{1}{\ln(n+2)}\right)\cdot\left(1-\frac{1}{\ln(n+3)}\right)\cdot\frac{1}{\ln(n+4)}$$

For $n$ much larger than $a$, we can approximate $\ln(n+a)\approx\ln(n)$, simplifying the probability

$$\left(1-\frac{1}{\ln(n)}\right)^{3}\cdot\left(\frac{1}{\ln(n)}\right)^{2}$$

We can generalise this to prime gaps of size $k$ having a sequence {prime, k-1 not prime, prime}. 

$$\left(1-\frac{1}{\ln(n)}\right)^{k-1}\cdot\left(\frac{1}{\ln(n)}\right)^{2}$$

Prime Gap Counts

Now we know the probability of a gap of size $k$, we can say the expected number of gaps of that size amongst the first $N$ numbers is approximately the probability summed over all the $n$ up to $N$.

$$\sum_{n}^{N}\left(1-\frac{1}{\ln(n)}\right)^{k-1}\cdot\left(\frac{1}{\ln(n)}\right)^{2}$$

Using another approximation that for most n between 1 and $N$, $\ln(n)\approx\ln(N)$, this simplifies further.

$$N\cdot\left(1-\frac{1}{\ln(N)}\right)^{k-1}\cdot\left(\frac{1}{\ln(N)}\right)^{2}$$

We can take the logarithm of this count to give us a linear function of the gap size $k$.

$$(k-1)\cdot\ln\left(1-\frac{1}{\ln(N)}\right)+2\ln\left(\frac{1}{\ln(N)}\right)+\ln(N)$$

Plotting a graph of the logarithm of the counts for each prime gap $k$ should give us a straight line. The gradient will be negative because it is the logarithm of $\left(1-\frac{1}{\ln(N)}\right)$, which is always less than 1. 

The following plot shows this probabilistic model works surprisingly well given the simplifications we made. 

Improved Model

Our simple model has many imperfections, and a significant one is that it doesn't take into account that every other number in a given range, the even numbers, are never prime. 

If we want to assert that the probability of an odd number being prime is zero, but also preserve the density of primes being $1/\ln(x)$ in the neighbourhood of $x$, we can double the probability of the odd numbers being prime to $2/\ln(x)$. 

The probability of a prime gap of size $k$ now only includes odd numbers in the sequence {prime, $k/2-1$ not prime, prime }. Following the same steps as before, and noting that we're only applying the probability to half the numbers in the range 1 to $N$, we have a new estimate for the prime gap counts.

$$\frac{N}{2}\cdot\left(1-\frac{2}{\ln(N)}\right)^{\frac{1}{k}-1}\cdot\left(\frac{2}{\ln(N)}\right)^{2}$$

The following plot shows that for smaller gaps this model is indeed an improvement. Modelling the behaviour of larger gaps requires more sophisticated models.

What Have We Learned?

It is useful to compare any probabilistic model with a naive one. Here we can compare our probabilistic primes model to coin tosses. The following compares the predicted prime gaps amongst the first $5\times10^8$ numbers with expected contiguous chains of heads (or tails) amongst $5\times10^8$ throws.

A linear log-count of sequences isn't unique, in fact it is common for chains of independent events.What we can say is:

• the correct order of magnitude for predicted prime gaps suggests the $1/\ln(x)$ probability is about right.
• the primes appear fairly randomly as if they were independent events.

You can explore this graph yourself online (link).

Animated Prime Gaps

As a fun aside, the following animates the prime gaps as $N$ grows up to $5\times10^8$, together with the predicted gap counts from the above two models.

Further Reading

Harald Cramér, in the 1930s, developed his probabilistic model for primes and used it to develop conjectures about the primes. His 1936 paper is considered to have kicked off the field:

• "On the order of magnitude of the difference between consecutive prime numbers".

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.

Chebyshev's Estimates For $\pi(x)$

Pafnuty Chebyshev proved Bertrand's Postulate that there is at least one prime between a number and its double, $n \leq p \leq 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} = {2n \choose 0}  +  \ldots + \ldots {2n \choose n} + \ldots + {2n \choose 2n}$$

Because ${2n \choose n}$ is only one of those terms we can say:

$$ \begin{align} 2^{2n} &> {2n \choose n} = \frac{(2n)!}{n!n!} \\ \\ &= \frac{(2n)\cdot(2n-1)\cdot \ldots \cdot (n+1)}{n\cdot(n-1)\cdot(n-2)\ldots \cdot 2 \cdot 1} \end{align}$$

Looking at that fraction, we can say that the numerator contains primes $n<p \leq 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 \leq 2n} p \text{ divides } {2n \choose n} $$

How many primes are there $n<p \leq 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 \leq 2n}$. This is because each of those primes is greater than $n$.

$$ n^{\pi(2n) - \pi(n)} < \prod_{n<p \leq 2n} p  \leq  {2n \choose n} < 2^{2n}$$

We can take logs and simplify:

$$ \boxed{ \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) \leq 3 \cdot \frac{2^k}{k} $$

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

$$ \begin{align} \pi(2^{k+1}) & \leq \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{align}$$

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

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

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\leq5$ confirms it is true for all $k$.

We've shown that if $\pi(2^k) \leq 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 \leq 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 \leq 2^{k+1}$ we can say

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

That least step requires $x \geq e$, but we can numerically verify that $\pi(x) \leq 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{ \pi(x) \leq 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} = {2n \choose 0}  +  \ldots  + {2n \choose n} + \ldots + {2n \choose 2n}$$

we can see that ${2n \choose n}$ is the largest element, which means it must be $\geq$ 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} \leq {2n \choose n}$$

Taking logs gives us

$$ 2n\ln2 - \ln(2n) \leq \ln {2n \choose n} $$

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

We know that  ${2n \choose 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{v_p(n!) = \sum_m \left \lfloor \frac{n}{p^m} \right \rfloor }$$ This is because in the set of numbers $\{ 1,2,3,\ldots,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 ${2n \choose n}$ is $\frac{(2n)!}{n!n!}$, and because $v_p(a/b) = v_p(a)-v_p(b)$, we can say $$ v_p{2n \choose n} = \sum_m \left( \left \lfloor \frac{2n}{p^m} \right \rfloor - 2\left \lfloor \frac{n}{p^m} \right \rfloor \right)$$ 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{align} \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{cases} 0 \text { for } b<\frac12 \\ 1 \text{ for } b>\frac12 \end{cases} \end{align}$$ 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{align} v_p{2n \choose n} &= \sum_{1\leq m \leq \lfloor \frac{\ln(2n)}{\ln p} \rfloor} \left( \left \lfloor \frac{2n}{p^m} \right \rfloor - 2\left \lfloor \frac{n}{p^m} \right \rfloor \right) \\ \\ &\leq \sum_{1\leq m \leq \lfloor \frac{\ln(2n)}{\ln p} \rfloor} 1 \\ \\ v_p{2n \choose n} &\leq  \left \lfloor \frac{\ln(2n)}{\ln p} \right \rfloor \end{align} $$ Knowing how ${2n \choose n}$ factorises into primes $p$ will be helpful.

We can now proceed:

$$\begin{align} 2n\ln2 - \ln(2n) &\leq \ln {2n \choose n} \\ \\ &\leq \sum_{p\leq 2n} \left \lfloor \frac{\ln(2n)}{\ln p}\right \rfloor \ln p  \\ \\ &\leq \sum_{p \leq 2n} \ln(2n)\\ \\  &= \ln(2n)\cdot \pi(2n)  \end{align}$$

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

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

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

We can use induction again to prove that

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

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

$$ \pi(x) \geq \pi(2n) \geq \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)} \geq \frac{7}{4\ln2} \geq \frac{1}{\ln2} $$

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

This gives us:

$$\begin{align} \pi(x) \geq \pi(2n) & \geq \ln(2) \cdot \frac{2n}{\ln(2n)} -1 \\ \\  &\geq \ln(2)\left(\frac{1}{\ln2} + \frac{n+1}{\ln(2n)}\right) -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 \\ \\ &\geq \frac{(n+1)\ln(2)}{\ln(x)} \text{ because } x > 2n \\ \\ &\geq \frac{(x/2)\ln(2)}{\ln(x)} \text{ because } x \leq 2n+2 \\ \\ \end{align}$$

So we finally have 

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

The following illustrates these lower and upper bounds for $x\leq 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{align} 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{align} $$

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

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

In our case, the bounds $c_1 = \frac12 \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$. 

Harmonic Primes Grow Like Log(Log(x))

Thinking of the ordinary counting numbers $n$, we've seen that:

• $\sum 1/n$ diverges - post.
• $\sum 1/n$ grows like $\log(n)$ - post.

Now thinking about the primes $p$, we've seen that:

• $\sum 1/p$ diverges - post, and post.

..but we haven't yet asked how $\sum_{p \leq n} 1/p$ grows - does it grow like $\log(n)$?

Euler's 1737 Assertion

In 1737 Euler presented a paper "Variae observationes circa series infinitas" to the St Petersburg Academy. You can view the source and translation here.

The last theorem in the paper, theorem 19, says that "The sum of the reciprocals of the prime numbers,

$$\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \frac{1}{11} + \frac{1}{13} + \ldots$$

is infinitely great but is infinitely times less than the sum of the harmonic series

$$1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \ldots$$

And the sum of the former is the as the logarithm of the sum of the latter."

This is interpreted fairly widely as Euler saying that for large $x$, the partial sum of inverse primes $p$ up to $x$ is approximately $\log \log x$.

$$ \sum_{p \leq x }\frac{1}{p} \approx \log \log x $$

Sadly, Euler's proof is not considered rigorous by modern standards. Showing how $\sum 1/p$ grows is not as simple as our previous proofs, and it took a while to find a suitably accessible reference. We'll be following the work of Paul Pollack's "Euler and the Partial Sums of the Prime Harmonic Series" paper [pdf]. 

Paul's paper actually proves a stronger result than Euler's assertion, valid for $x>e^4$:

$$ \left|  \sum_{p \leq x} \frac{1}{p} - \log \log x  \right|  < 6 $$

Proof Overview

The proof centres on showing that $\sum_{p \leq x} \frac{1}{p}$ is bounded above and below by functions that are of the form $\log \log x + C$ where $C$ is a constant. 

To achieve that comparison, we'll be making use of three intermediate results, which we'll derive first.

First Result $\left| \log \zeta(s) - P(s) \right|< \frac{1}{2}$

Let's start with the Euler product formula.

$$ \zeta(s) = \sum_n \frac{1}{n^s} = \prod_n \left( \frac{1}{1-p^{-s}} \right) $$

We can take the logarithm because $\zeta(s)$ converges for $s>1$.

$$ \log \zeta(s) = - \sum_p \log (1-p^{-s}) $$

We can use $\log (1+x)=x-\frac{x^2}{2}+\frac{x^3}{3}-\cdots$ for $|x|<1$ to expand the logarithm.

$$\begin{align} \log \zeta(s) &= \sum_p \sum_k \frac{1}{kp^{ks}}\\ &=  P(s) +  \sum_p \sum_{k \geq 2} \frac{1}{kp^{ks}} \end{align}$$

We've isolated $P(s) = \sum1/p^s$ which looks like a step in the right direction. Let's focus on that double sum.

Since $s>1$, and $1/kp^{ks}\leq 1/2p^{ks}$ for $k \geq 2$, 

$$ 0<  \sum_p \sum_{k \geq 2} \frac{1}{kp^{ks}} \leq \frac{1}{2} \sum_p \sum_{k \geq 2} \frac{1}{p^{k}}  $$

Also, since $(1-x)^{-1} = 1 + x + x^2+\ldots$ for $|x|<1$, we can say 

$$\begin{align} \sum_p \sum_{k \geq 2} \frac{1}{kp^{ks}} &\leq \frac{1}{2} \sum_p \sum_{k \geq 2} \frac{1}{p^{k}} \\ &= \frac{1}{2} \sum_p  (\frac{1}{p^{2}} + \frac{1}{p^{3}} + \frac{1}{p^{4}} + \ldots) \\ &= \frac{1}{2} \sum_p \frac{1}{p} (\frac{1}{p} + \frac{1}{p^2} + \frac{1}{p^3} + \ldots) \\ &= \frac{1}{2} \sum_p \frac{1}{p} (-1 + (1-\frac{1}{p})^{-1})  \\ &= \frac{1}{2} \sum_p \frac{1}{p(p-1)} \end{align}$$

Since the primes $p$ are a subset of the counting numbers $n$ we can say

$$\frac{1}{2} \sum_p \frac{1}{p(p-1)} < \frac{1}{2} \sum_{n \geq 2} \frac{1}{n(n-1)} = \frac{1}{2}$$

That last step uses $\sum_{n \geq 2} \frac{1}{n(n-1)} = \sum_{n \geq 2} \frac{1}{n-1}-\frac{1}{n} = 1$ which can be seen by writing out the first few terms to see how all but the first term cancel.

This leaves us with a nice result, that the difference between the zeta function and $P(s)$, the prime zeta function with primes raised to $s>1$, is bounded by a finite value.

$$ \boxed{0 < \log \zeta(s) - P(s) < \frac{1}{2}}$$

Note that this does not say anything about the prime harmonic series $\sum 1/p$ because that would require $s=1$.

Second Result $1<(s-1) \cdot \zeta(s) < s$

We have already used integral comparison tests to find that:

$$ \frac{1}{s-1}<\zeta(s)<\frac{1}{s-1}+1 $$

It is easy to rearrange this:

$$ \boxed{1<(s-1) \cdot \zeta(s) < s }$$

Third Result $\left| P(s+1) - \log \frac{1}{s} \right| < \frac{1}{2}$

Let's now focus on just the smaller range $0 < s < \frac{1}{2}$. We replace $s$ with $s+1$ in our previous results to ensure the expressions remain valid. 

The first result gives us:

$$0 < \log \zeta(s) - P(s) < \frac{1}{2}$$

for $s>1$.

$$-\frac{1}{2} < P(s+1) - \log \zeta(s+1) < 0$$

for $0<s<\frac{1}{2}$.

The second result gives us:

$$ 1< (s-1)\cdot \zeta(s) < s$$

for $s>1$.

$$ 1< s \cdot \zeta(s+1) < \frac{3}{2}$$

for $0<s<\frac{1}{2}$. Taking logarithms gives us

$$ 0<  \log \zeta(s+1) - \log \frac{1}{s} < \log \frac{3}{2} < \frac{1}{2}$$

Adding these two inequalities gives us our third result.

$$  -\frac12 <  P(s+1) - \log \frac{1}{s} < \frac12  $$

$$ \boxed{ | P(s+1) - \log \frac{1}{s} | < \frac12 } $$

for $0<s<\frac{1}{2}$. We can do this because $a_1<b_1<c_1$ and $a_2<b_2<c_2$ implies $a_1+a_2 < b_1+b_2 < c_1+c_2$.

Comparison

We start by defining a function $S(\lambda, x)$ which is a function of a function $\lambda(t)$ defined over the small domain $t \in [0,1]$:

$$ S(\lambda, x) = \sum_p p^{-1-\frac{1}{\log x}} \cdot \lambda(p^{-\frac{1}{\log x}}) $$

It looks rather convoluted, but we'll see it simplifies dramatically if we use a function $\lambda_0(t)$ with the following definition:

$$ \lambda_0(t) = \begin{cases} 1/t & \text{if } 1/e \leq t \leq 1 \\ 0 & \text{if } 0 \leq t < 1/e \end{cases} $$

A visualisation of this function is helpful.

Let's look at what $1/e \leq t \leq 1$ means:

$$ \begin{align} 1/e &\leq t \leq 1 \\ 1/e &\leq p^{-\frac{1}{\log x}} \leq 1 \\ -1 &\leq -\frac{1}{\log x} \log p \leq 0 \\ -\log x &\leq - \log p \leq 0 \\ 0 &\leq  p \leq x \end{align}$$

This is the range we're interested in for our original question about how $\sum_{p \leq x} 1/p$ grows. 

We can perform a similar analysis to find that for the other range $0 \leq t < 1/e$ leads to $x<p<\infty$, which usefully contributes 0 to the sum $S(\lambda_0, x)$.

So this definition of $\lambda_0(t)$ reduces $S(\lambda_0, x)$ nicely:

$$ \begin{align} S(\lambda, x) &= \sum_p p^{-1-\frac{1}{\log x}} \cdot \lambda(p^{-\frac{1}{\log x}}) \\ &= \sum_p p^{-1-\frac{1}{\log x}} \cdot p^{+\frac{1}{\log x}} \\ &= \boxed{\sum_p \frac{1}{p}}  \end{align}$$

Our plan now is to find other functions $\lambda(t)$ which are larger than, and smaller than, this $\lambda_0(t)$, which hopefully can give us specific bounds around $\sum_{p \leq x}1/p$.

Let's try a linear form for these $\lambda(t)=\alpha + \beta t$.

$$\begin{align} S(\lambda, x) &= \sum_p p^{-1-\frac{1}{\log x}} \cdot \lambda(p^{-\frac{1}{\log x}}) \\ &= \sum_p p^{-1-\frac{1}{\log x}} \cdot (\alpha + \beta \cdot p^{-\frac{1}{\log x}}) \\ &= \alpha \cdot P(1+\frac{1}{\log x}) + \beta \cdot P(1 + \frac{2}{\log x}) \end{align}$$

We can apply the previous third result about $P(s+1)$ if we ensure $0<s<\frac12$. We can do this if $x > e^4$ so $s=\frac{2}{\log x} < \frac12$.

$$\begin{align} -\frac12 < P(1+ \frac{1}{\log x}) - \log \log x &< \frac12 \\ -\frac12 < P(1+ \frac{2}{\log x}) - \log \log x + \log 2  &< \frac12 \\ \end{align}$$

Continuing, and taking care that $\alpha$ or $\beta$ could be negative,

$$\begin{align}  -\frac{|\alpha|}{2} < \alpha P(1+ \frac{1}{\log x}) - \alpha \log \log x < \frac{|\alpha|}{2} \\  -\frac{|\beta|}{2} < \beta P(1+ \frac{2}{\log x}) - \beta \log \log x + \beta \log 2 < \frac{|\beta|}{2} \\  -\frac{|\alpha|}{2} - \frac{|\beta|}{2} < S(\lambda, x) - \alpha \log \log x - \beta \log \log x + \beta \log 2 < \frac{|\alpha|}{2} + \frac{|\beta|}{2} \end{align}$$

The next step is true for $\beta$ positive or negative:

$$ -\frac{|\alpha|}{2} - |\beta|(\frac12 + \log 2) < S(\lambda, x) - \alpha \log \log x - \beta \log \log x < \frac{|\alpha|}{2} + |\beta|(\frac12 + \log 2)$$

Noting that $\lambda(1)=\alpha + \beta$, we can rearrange as:

$$ -\frac{|\alpha|}{2} - |\beta|(\frac12 + \log 2) < S(\lambda, x)  - \lambda(1) \log \log x < \frac{|\alpha|}{2} + |\beta|(\frac12 + \log 2) $$

Or more concisely.

$$ \boxed{ \left | S(\lambda, x)  - \lambda(1) \log \log x \right | < \frac{|\alpha|}{2} + |\beta|(\frac12 + \log 2) }$$

Now lets look at two linear versions of $\lambda(t)$:

• Upper bound $\lambda_U(t)=-et + (e+1) \geq \lambda_0(t)$. 
• Lower bound $\lambda_L(t)=\frac{e}{e-1}t - \frac{1}{e-1} \geq \lambda_0(t)$. 

Note that $\alpha + \beta = 1$ for both.

Visualising these is helpful.

Since $\lambda_U(t) \geq \lambda_0(t)$, we can say $S(\lambda_U,x) \geq \sum_{p \leq x}1/p$:

$$\begin{align} \sum_{p \leq x} \frac{1}{p}  &< \log \log x + \frac{|\alpha|}{2} + |\beta|(\frac12 + \log 2) \\ &= \log \log x + \frac{e+1}{2} + e(\frac12 + \log 2) \\ \sum_{p \leq x} \frac{1}{p} &< \log \log x + 6 \end{align} $$

This is an upper bound for the growth of the prime harmonic series. Let's find the lower bound.

Since $\lambda_L(t) \leq \lambda_0(t)$, we can say $S(\lambda_L,x) \leq \sum_{p \leq x}1/p$:

$$\begin{align} \sum_{p \leq x} \frac{1}{p}  &> \log \log x -\frac{|\alpha|}{2} - |\beta|(\frac12 + \log 2) \\ &=  \log \log x - \frac{1}{2(e-1)} - \frac{e}{e-1}(\frac12 + \log 2) \\ \sum_{p \leq x} \frac{1}{p} &> \log \log x + 3 \end{align} $$

 

Putting all this together:

$$ \log \log x + 3 < \sum_{p \leq x} \frac{1}{p} < \log \log x + 6  $$

So we can now finally say:

$$ \boxed{ \sum_{p \leq x} \frac{1}{p} \text{ grows like } \log \log x }$$

The following chart compares $\sum_{p \leq n} \frac{1}{p}$ with $\log \log x$ for $x\leq 1000$. 

The chart also shows the difference, which appears to be approaching $\frac12$.

Thoughts

That the partial sum of inverse primes grows like $\log \log$ means it grows very very slowly. 

Consider the following comparison between $x$, $\log x$, and $\log \log x$:

x	ln x	ln ln x
10	2.30	0.83
1000	6.91	1.93
1000000	13.82	2.63
1000000000	20.72	3.03
1000000000000	27.63	3.32

Remembering that the infinite harmonic prime series diverges, a good question to ask if whether the distribution of the primes is almost at the limit of sparsity beyond which the series would converge. 

Another Proof $\sum \frac{1}{p}$ Diverges

Ivan Niven authored a very short and rather fun proof that the sum of inverse primes diverges. 

The proof was published in 1971 in the American Mathematical Monthly vol 78, issue 3, 272-273. It is available as open access here: https://www.tandfonline.com

Although the proof is short, it moves at a pace that might leave some behind. Here we'll work through the proof and explain each step more fully.

Video: [youtube]

Slides: [pdf]

Square-Free Numbers

The proof starts with the idea of square-free positive integers. 

We can write any counting number m as a unique product of a square $j^{2}$ and square-free factor $k$. 

$$m=k\cdot j^{2}$$

Remember that any integer is a unique product of primes. We can split these primes into two groups, one group with primes raised to an even power, which together can be written as a square, and the other group with primes not raised to any power. 

For example, $360=(2\cdot5)\cdot(2\cdot3)^{2}$ has a square-free factor of 10, and a square factor of 36. On the other hand, $30=(2\cdot3\cdot5)$ is entirely square-free. 

 

$\sum' 1/k$  Diverges

Let's look at the following inequality, where $k$ are the square-free integers less than $n$.

$$\left(\sum_{k<n}\frac{1}{k}\right)\left(\sum_{j<n}\frac{1}{j^{2}}\right)\geq\sum_{m<n}\frac{1}{m}$$

The inequality is true because multiplying out the two series would give us not just the terms $1/m$, but also many more. The two sides are only equal when $n=2$. 

As $n\rightarrow\infty$, the right hand side becomes the harmonic series which we know diverges. We also know the second sum converges to $\pi^{2}/6$. That means the sum over square-free integers $\sum1/k$ must diverge, a neat result we'll use very soon.

Proof By Contradiction

Let's assume, perhaps incorrectly, the sum of prime reciprocals $\sum1/p$ converges to a finite \beta. 

The partial sum is less than the full sum, $\sum_{p<n}1/p<\beta$, so we can write the following. 

$$\exp(\beta)>\exp\left(\sum_{p<n}\frac{1}{p}\right)=\prod_{p<n}\exp(\frac{1}{p})$$

We can also truncate the Taylor series for $e^{x}$ to say $e^{x}>1+x$. Applying this to $\exp(1/p)$ lets us write the following.

$$\prod_{p<n}\exp(\frac{1}{p})>\prod_{p<n}(1+\frac{1}{p})$$

Multiplying out that product would give a series with terms $1/k$ where each $k$ is square-free. This is because each prime contributes to any $k$ at most once. We'd also end up with more terms than are in $\sum_{p<n}1/k$ for $n>3$. 

$$\prod_{p<n}(1+\frac{1}{p})\geq\sum_{k<n}\frac{1}{k}$$

Let's put all this together.

$$\exp(\beta)>\exp\left(\sum_{p<n}\frac{1}{p}\right)=\prod_{p<n}\exp(\frac{1}{p})>\prod_{p<n}(1+\frac{1}{p})\geq\sum_{k<n}\frac{1}{k}$$

This suggests that as $n\rightarrow\infty$ the finite $\exp(\beta)$ is greater than $\sum1/k$, which we showed was divergent. This is clearly a contradiction, so our assumption that $\sum1/p$ converges was wrong. 

$$\boxed{\sum\frac{1}{p}\rightarrow\infty}$$

Integral Comparison Tests

Understanding the behaviour of continuous functions is often easier than discrete functions. We can gain insights into discrete sums like $\sum\frac{1}{x}$ by exploring the related continuous integral $\int\frac{1}{x}dx$.

This is a simple but powerful technique used a lot in number theory, and worth becoming familiar with.

Video: [youtube]

Slides: [pdf]

Lower & Upper Bounds For The Growth Of $\sum1/n$

The picture below shows a graph of $y=\frac{1}{x}$, together with rectangles representing the fractions $\frac{1}{n}$.

Lower Bound

If we consider the range $1\leq x\leq4$ we can see the area of the three taller rectangles $1+\frac{1}{2}+\frac{1}{3}$ is greater than the area under the curve $\int_{1}^{4}\frac{1}{x}dx$. By extending the range to $n$ we can make a general observation.

$$\sum_{1}^{n}\frac{1}{x}>\int_{1}^{n+1}\frac{1}{x}dx$$

The integral has an upper limit of $n+1$ because the width of the last rectangle extends from $x=n$ to $x=n+1$. We can perform the integral to simplify the expression.

$$\boxed{\sum_{1}^{n}\frac{1}{x}>\ln(n+1)}$$

This is a rather nice lower bound on the growth of the harmonic series.

Upper Bound

Let's now look at the shorter rectangles. In the range $1\leq x\leq4$ we can see the area of the three shorter rectangles $\frac{1}{2}+\frac{1}{3}+\frac{1}{4}$ is less than the area under the curve $\int_{1}^{4}\frac{1}{x}dx$. Again, by extending the range to n we can make a general observation.

$$\sum_{2}^{n}\frac{1}{x}<\int_{1}^{n}\frac{1}{x}dx$$

The harmonic sum starts at 2 because this time we're looking at rectangles extending to the left of a given $x$. We can adjust the limit of the sum using $\sum_{1}^{n}\frac{1}{x}=1+\sum_{2}^{n}\frac{1}{x}$.

$$\sum_{1}^{n}\frac{1}{x}-1<\int_{1}^{n}\frac{1}{x}dx$$

Again, we can perform the integral.

$$\boxed{\sum_{1}^{n}\frac{1}{x}<\ln(n)+1}$$

This is a nice upper bound to the growth of the harmonic series.

Convergence Of $\zeta(s)=\sum1/n^{s}$

The picture below shows a graph of $y=\frac{1}{x^{s}}$, together with rectangles representing the fractions $\frac{1}{x^{s}}$. The shape of the graph assumes $s>0$. If $s$ was $\leq0$ then it is easy to see $\sum1/n^{s}$ would diverge because each term would be $\geq1$.

If we consider the range $1\leq x\leq4$ we can see the area of the three shorter pink rectangles is less than the area under the curve $\int_{1}^{4}\frac{1}{x^{s}}dx$. By extending the range to $k$ we can make a general observation.

$$\sum_{2}^{k}\frac{1}{x^{s}}<\int_{1}^{k}\frac{1}{x^{s}}dx$$

The sum starts at 2 because we're looking at rectangles extending to the left of a given x. We can adjust the limit of the sum using $\sum_{1}^{k}\frac{1}{x^{s}}=1+\sum_{2}^{k}\frac{1}{x^{s}}$.

$$\sum_{1}^{k}\frac{1}{x^{s}}-1<\int_{1}^{k}\frac{1}{x^{s}}dx$$

The integral is easily evaluated.

$$\sum_{1}^{k}\frac{1}{x^{s}}<\frac{k^{1-s}-1}{1-s}+1$$

As $k\rightarrow\infty$, the right hand side only converges when $s>1$. Because it is less than the right hand side, the sum $\sum1/x^{s}$ also converges when $s>1$. We haven't yet ruled out the possibility the sum might also converge for some $s \leq 1$.

If we now consider the three taller rectangles $1+\frac{1}{2^{s}}+\frac{1}{3^{s}}$ in the range $1\leq x\leq4$, we can see their area is greater than the area under the curve $\int_{1}^{4}\frac{1}{x^{s}}dx$. By extending the range to $k$, we can make a general observation.

$$\sum_{1}^{k}\frac{1}{x^{s}}>\int_{1}^{k+1}\frac{1}{x^{s}}dx$$

The integral has an upper limit of $k+1$ because the width of the last rectangle extends from $x=k$ to $x=k+1$. We can perform the integral to simplify the expression.

$$\sum_{1}^{k}\frac{1}{x^{s}}>\frac{(k+1)^{1-s}-1}{1-s}$$

As $k\rightarrow\infty$, the right hand side diverges when $s\leq1$. Because it is greater than the right hand side, the sum $\sum1/x^{s}$ also diverges when $s\leq1$. We have now ruled out the possibility the sum might converge for some $s \leq 1$.

$$\boxed{\zeta(s)=\sum1/n^{s}\text{ only converges for }s>1}$$

We can go further. The two inequalities together provide a lower and upper bound for the zeta function.

$$\boxed{\frac{1}{s-1}<\zeta(s)<\frac{1}{s-1}+1}$$

Convergence Of Infinite Products

Infinite Series (Sums)

At school we learned about infinite series.

$$  \sum_{n=1}^\infty a_n = a_1+ a_2 + a_3 + \ldots  $$

If the partial sum $\sum_{n=1}^{x} a_n$ tends to a limit as $x \rightarrow \infty$, we can say the series converges to a finite sum. There are many tests that can be used to see if a series converges or not, such as the popular ratio test:

$$ \lim_{n \rightarrow \infty} | \frac{a_{n+1}}{a_n} | <1 $$

If we think about the series $\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \ldots$, the ratio test gives us $|\frac{ 2^{n-1} }{ 2^{n} }| = \frac{1}{2}$, confirming the series is absolutely convergent.

Infinite Products

Infinite products don't seem to be discussed as much as series.

$$ \prod_{n=1}^\infty a_n = a_1 \times a_2 \times a_3 \times \ldots  $$

When do such infinite products converge? Let's think about this before jumping to the answer.

Thoughts

It seems intuitive that if the elements $a_n$ are getting larger, the product grows and diverges. The following example gets ever larger and doesn't converge. 

$$  2 \times 3 \times 4 \times 5 \times \ldots $$

Let's look at another example.

$$ 0.5 \times 0.55 \times 0.555 \times 0.5555 \times \ldots $$

Here the elements are getting larger, but are individually less than 1, so it isn't immediately obvious whether the product converges or not.

What if the product contains a zero? That sounds easy. A single zero would immediately make the overall product zero. 

But what about this product? 

$$ -2 \times -1 \times 0 \times 1 \times 2 \times \ldots $$

With the zero, we'd suggest the product is zero overall. But without that zero, the product gets larger and diverges. Is the single zero somehow 'powerful' enough to cancel the infinity?

Definition

A consensus has emerged around infinite products which may, or may not, seem natural.

If the partial product $\prod_{n=1}^{x} a_n$ converges to a non-zero limit $P$ as $x \rightarrow \infty$, we say the infinite product converges to $P$.

This makes sense but the fact that the limit needs to be non-zero sets infinite products apart from infinite series.

If a finite number of zeros $a_n$ can be removed from a product, and the remaining product converges, we say the infinite product converges to 0.

This is rather specific, and means that we can't say a product with infinitely many zero elements converges. For example, we can't say the following converges:

$$  1 \times 0 \times 1 \times 0 \times 1 \times 0 \times 1 \times \ldots $$

Let's look at some examples to bring these ideas to life.

Example 1

Does the following infinite product converge or diverge?

$$ \prod_{n=1}^{\infty}(1+\frac{1}{n}) $$

If we consider the partial sum, and look at at the first few elements of this product, we'll see a pattern.

$$ \begin{align} \prod_{n=1}^{N}(1+\frac{1}{n}) &=  \prod_{n=1}^{N}(\frac{n+1}{n}) \\ \\ &= \frac{\cancel{2}}{1} \times \frac{\cancel{3}}{\cancel{2}} \times \frac{4}{\cancel{3}} \times  \ldots \times \frac{N+1}{N} \\ \\ &= N + 1 \end{align} $$

As $N \rightarrow \infty$, this partial sum tends to $\infty$, so the infinite product diverges. This isn't surprising when we look at each element and that they are all above 1.

Example 2

Let's now look at an example where each element is less than 1. Notice $n$ starts at 2, not 1. 

$$ \prod_{n=2}^{\infty}(1-\frac{1}{n}) $$

Again, if we consider the partial sum, and look at at the first few elements of this product, we'll see a pattern.

$$ \begin{align} \prod_{n=2}^{N}(1-\frac{1}{n}) &=  \prod_{n=2}^{N}(\frac{n-1}{n}) \\ \\ &= \frac{1}{\cancel{2}} \times \frac{\cancel{2}}{\cancel{3}} \times \frac{\cancel{3}}{4} \times  \ldots \times \frac{N-1}{N} \\ \\ &= \frac{1}{N} \end{align} $$

As $N \rightarrow \infty$, this partial sum tends to 0. Because this limit is not a non-zero limit, as required by the definitions above, we say the infinite product diverges. 

Turning Products Into Sums

We can convert a product into a sum using logarithms.

$$ \begin{align} \ln (\prod_{n=1}^\infty a_n) &= \ln( a_1 \times a_2 \times a_3 \times \ldots)  \\ \\ &= \sum_{n=1}^\infty \ln(a_n) \end{align}$$

We can say the infinite product converges if the sum $\sum_{n=1}^\infty \ln(a_n)$ converges. 

If that product tends to zero, this sum tends to $-\infty$, which is why we say the infinite product diverges to zero, not converges to zero.

A Different Test For Convergence

If we can rewrite the product elements as $(1 + a_n)$ where $a_n >0$ we can use a simpler convergence test.

$$ \begin{align} \prod_{n=1}^\infty (1 + a_n) &\leq  \prod_{n=1}^\infty e^{ a_n} \\ \\ &=   e^{\sum_{n=1}^\infty a_n} \end{align} $$

The inequality comes from $e^x=1 + x + O(x^2)$. We can make the following conclusion.

If $\sum_{n=1}^\infty a_n$ converges, then so does the product $\prod_{n=1}^\infty (1 + a_n)$, as long as $a_n >0$.

This test allows us to easily say the following infinite series converges:

$$ \prod_{n=1}^\infty (1 + \frac{1}{n^2}) $$

We can say this because we know $\sum_{n=1}^{\infty} \frac{1}{n^2}$ converges.

Infinite Products Over Complex Numbers

There is an equivalent form of the previous test for complex $z_n$.

If $\sum_{n=1}^\infty |a_n|$ converges, then so does the product $\prod_{n=1}^\infty (1 + a_n)$, as long as $a_n \neq -1$.