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