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.