As a child, I was inspired by Arthur C. Clarke‘s 1956 science fiction novel The City and the Stars to search for patterns in prime numbers. Chapter 6 begins:

Jeserac sat motionless within a whirlpool of numbers. The first thousand primes, expressed in the binary scale that had been used for all arithmetical operations since electronic computers were invented, marched in order before him. Endless ranks of l’s and o’s paraded past, bringing before Jeserac’s eyes the complete sequences of all those numbers that possessed no factors except themselves and unity. There was a mystery about the primes that had always fascinated Man, and they held his imagination still. Jeserac was no mathematician, though sometimes he liked to believe he was. All he could do was to search among the infinite array of primes for special relationships and rules which more talented men might incorporate in general laws. … He knew the laws of distribution that had already been discovered, but always hoped to discover more.

My 95-cent childhood copy of The City and the Stars.

Indeed, I remember manually plotting the smallest primes on graph paper searching for patterns. Today, for example, I know that the prime number theorem  describes the asymptotic distribution of the primes, which become less common as they become larger. If \pi(x) is the number of primes less than or equal to x, then \pi(x) \sim x / \log x, for large x.

Here I present an elementary proof of a weak form of the prime number theorem based on a proof by Jan-Hendrik Evertse, which itself was based on work by Paul Erdős.

First recall the binomial theorem

(a+b)^n = \sum_{m=0}^n \binom{n}{m}a^{n-m}b^m,

where the binomial coefficients

\binom{n}{m} = \frac{n!}{m!(n-m)!}.

Also recall the floor function

\lfloor x\rfloor =\max\{n\in \mathbb {Z} \mid n\leq x\},

so

x−1<\lfloor x \rfloor≤x.

Write \log x = \log_e x for the natural logarithm, as is common in pure mathematics and theoretical physics.

Introductory Lemmas

Lemma A: Number of times a prime divides a factorial

\nu_p(n!)=\sum_{m=1}^\infty \left\lfloor \frac{n}{p^m} \right\rfloor

To count the number of times that prime p divides n!, note that each multiple of p\le n contributes a factor of p, each multiple of p^2\le n contributes another factor of p, each multiple of p^3\le n contributes yet another factor of p, and so on, so that

\nu_p(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots = \sum_{m=1}^\infty \left\lfloor \frac{n}{p^m} \right\rfloor,

where all terms in the sum vanish when p^m > n.

Lemma B: Prime product divides binomial coefficient

0<2b\le a \Rightarrow \prod_{a-b+1\le p\le a} \hspace{-1em}p\hspace{1em} \Bigg| \binom{a}{b}

Since

\binom{a}{b} = \frac{a!}{b!(a-b)!} = \frac{a(a-1)\cdots (a-b-1)}{b(b-1) \cdots \hspace{2.1em} 1\hspace{2.1em}},

each prime b<b+1\le a-b+1\le p\le a divides the numerator but not the denominator, and thus so does their product.

Lemma C: Prime power divides binomial coefficient

a > b > 0,\ p^m\Big| \binom{a}{b}\ \Rightarrow\ p^m \le a

By Lemma A, the number of times a prime divides a binomial coefficient

\begin{aligned}\nu_p\left(\binom{a}{b}\right)&=\nu_p\left(\frac{a!}{b!(a-b)!}\right)\\ &= \sum_{m=1}^\infty \left( \left\lfloor \frac{a}{p^m} \right\rfloor-\left\lfloor \frac{a-b}{p^m} \right\rfloor-\left\lfloor \frac{b}{p^m} \right\rfloor \right).\end{aligned}

Each positive integer summand

\begin{aligned}&\left\lfloor \frac{a}{p^m} \right\rfloor-\left\lfloor \frac{a-b}{p^m} \right\rfloor-\left\lfloor \frac{b}{p^m} \right\rfloor \\& < \frac{a}{p^m}-\left( \frac{a-b}{p^m}-1 \right)-\left( \frac{b}{p^m}-1\right)=2,\end{aligned}

and so must be either 0 or 1. Furthermore, since each summand with p^m>a>b is 0, the sum can grow no larger than the largest m for which p^m \le a.

Lemma D: Bounds on the symmetric binomial coefficient

n\in\mathbb{N}_1\ \Rightarrow\ \frac{2^n}{n+1} \le \binom{n}{\lfloor n /2 \rfloor }\le 2^{n-1}

For the lower bound, since the central binomial coefficient (corresponding to the middles of the rows of Pascal’s triangle) is largest,

2^n=(1+1)^n=\sum_{m=0}^n\binom{n}{m}1^m 1^{n-m}\le(n+1) \binom{n}{\lfloor n/2 \rfloor}.

For the upper bound, first let n=2k+1 be odd, so

\binom{2k+1}{k}=\binom{2k+1}{k+1}

and

\begin{aligned}\binom{n}{\lfloor n/2 \rfloor} &=\binom{2k+1}{k}=\frac{1}{2}\left( \binom{2k+1}{k}+\binom{2k+1}{k+1} \right) \\& \le \frac{1}{2}\sum_{m=0}^{2k+1} \binom{2k+1}{m}=(1+1)^{2k}=2^{2k}=2^{n-1}.\end{aligned}

Next let n=2k be even, so

\binom{2k}{k-1}=\binom{2k}{k+1}=\binom{2k}{k}\frac{k}{k+1}\ge \frac{1}{2}\binom{2k}{k}

and

\begin{aligned}\binom{n}{\lfloor n/2 \rfloor} &=\binom{2k}{k}\le\frac{1}{2}\left( \binom{2k}{k-1}+\binom{2k}{k}+\binom{2k}{k+1} \right) \\& \le \frac{1}{2}\sum_{m=0}^{2k} \binom{2k}{m}=(1+1)^{2k-1}=2^{2k-1}=2^{n-1}.\end{aligned}

Pascal’s triangle and binomial coefficients.

Theorem

The number of primes less than or equal to x\ge 3 is bounded above and below by multiples of x/\log x, specifically

\frac{1}{2} \frac{x}{\log x} \le \pi(x) \le 2 \frac{x}{\log x}.

Equivalently, in Donald Knuth‘s notation, \pi(x) = \Theta(x / \log x), and in G. H. Hardy‘s notation, \pi(x) \asymp x/\log x. (The stronger relation \pi(x) \sim x / \log x is harder to prove.)

Bounding the prime counting function.

By direct calculation, both bounds are good for 3\le x\le 500, as in the above graph. Let n=\lfloor x \rfloor, so n\le x < n+1.

Lower bound

Prime factor the central binomial coefficient

\binom{n}{\lfloor n/2 \rfloor} = p_1^{k_1}\cdots p_t^{k_t}.

By Lemma C, 1<p_m \le p_m^{k_m}\le n, and so p_m \le n for m=1, \ldots,t. Thus the number of prime factors t \le \pi(n), which combined with Lemma D gives

\frac{2^n}{n+1} \le \binom{n}{\lfloor n/2 \rfloor} \le n^{\pi(n)},

and so

\begin{aligned}\pi(x)&=\pi(n)\ge \frac{n \log 2-\log(n+1)}{\log n}\\ & \ge \frac{(x-1)\log 2-\log(x+1)}{\log x}\\ & \ge \frac{1}{2}\frac{x}{\log x},\end{aligned}

where the final inequality is by Appendix Lemma E.

Upper bound

Proceed by induction. If n=2m+1 is odd, then by Lemma D and B,

2^{2m} \ge \binom{2m+1}{m}\ge \prod_{m+2\le p \le 2m+1} \hspace{-1.8em}p\hspace{0.8em} \ge (m+2)^{\pi(2m+1)-\pi(m+1)},

and so

\pi(2m+1)-\pi(m+1)\le \frac{2m \log 2}{\log(m+2)}.

Use the induction hypothesis on \pi(m+1) with m+2>m+1>n/2 to find

\begin{aligned}\pi(n)=\pi(2m+1)&=\frac{2m \log 2}{\log(m+2)}+\pi(m+1) \\ &\le \frac{2m \log 2}{\log(m+2)}+2\frac{m+1}{\log(m+1)} \\ & < \frac{2m\log 2 + 2m+2+\log 2}{\log(m+1)}\\ & < \frac{n(\log 2 + 1)+1}{\log(n/2)}\\ & < 2\frac{n}{\log n},\end{aligned}

where the final inequality is by Appendix Lemma F. If n is even, then n-1 is odd and

\pi(n)=\pi(n-1)\le 2\frac{n-1}{\log(n-1)}<2\frac{n}{\log n},

as x/\log x is increasing for x>e .

Appendix Lemmas

Lemma E: For lower bound

L(x)=\frac{(x-1)\log 2-\log(x+1)}{\log x}\ge \frac{1}{2}\frac{x}{\log x}=R(x)\Leftarrow x>100

The left and right functions don’t intersect after x ≈ 19.1.

If the difference

\Delta(x) = L(x)-R(x),

then the derivative

\Delta^\prime(x) = N(x)/D(x),

where

N=N_0+N_1 x+N_2 x^2,

and

\begin{aligned}N_0 &= 2 \log 2 + 2\log(1+x)\\&>0 \Leftarrow x>-1/2,\\ N_1 &=1-3\log x+ 2\log 2\log x+2\log(1+x) \\ &> 1-3\log x+2\log 2\log x + 2\log x \\&= 1+(2\log 2-1)\log x\\&>(2\log 2-1)\log x\\&> 0 \Leftarrow x>1, \\N_2 &= 1-2\log 2-\log x + 2\log 2\log x\\&= (1-2\log 2)(1-\log x)\\&>0 \Leftarrow x>e,\\D& =2x(1+x)(\log x)^2\\&>0\Leftarrow x>1.\end{aligned}

Hence, \Delta'(x) >0 for x>e, L(x) and R(x) continue separating after crossing at x\approx 19.1, and the lemma follows.

Lemma F: For upper bound

L(x)= \frac{n(\log 2 + 1)+1}{\log(n/2)} < 2\frac{n}{\log n}=R(x)\Leftarrow x>500

The left and right functions don’t intersect after x ≈ 106.

If the difference

\Delta(x) = L(x)-R(x),

then the derivative

\Delta^\prime(x) = N(x)/D(x),

where

N=N_0+N_2 (\log x)^2,

and

N_0=2\log 2(m_0\log x+b_0)x <0 \Leftrightarrow \log x > -\frac{b_0}{m_0}\Leftrightarrow x > \exp\left(-\frac{b_0}{m_0}\right) \Leftrightarrow x > \exp\left(\frac{1}{1+2/\log 2}\right)\approx 1.29, N_2=-1+(m_2\log x+b_2)x < 0 \Leftarrow \log x > -\frac{b_2}{m_2}=-\frac{1+2\log 2-(\log 2)^2}{\log 2-1} \Leftrightarrow x >\exp\left(\log 2-1-\frac{2}{\log 2-1}\right)\approx 498,

and

D=x(\log x)^2(\log x-\log 2)^2>0 \Leftarrow x>2.

Hence, generously, \Delta'(x) <0 for x>500, L(x) and R(x) continue separating after crossing at x\approx 106, and the lemma follows.

The sum of the reciprocals of the natural numbers diverges, but slowly, like the logarithm of the number of terms. The sum of the reciprocals of the prime numbers also diverges, but even more slowly, like the logarithm of the logarithm of the number of terms, as the primes are sparse in the naturals!

Here I attempt elementary proofs that

H_n = \sum_{m\le n} \frac{1}{m} = \mathcal{\Theta}(\log n),

where m,n \in \mathbb{N}_1 = \mathbb{Z}^+, and

S_n = \sum_{p\le n} \frac{1}{p} = \mathcal{\Theta}(\log \log n),

where p \in \mathbb{P} is a prime number, as in Fig. 1. In both cases, I will try to bound the sums below and above to show they are of the same order, a g(x) \le f(x) \le b g(x) so f(x) = \Theta(g(x)). The results are not new, but the presentation is.

Figure 1: Inverse numbers partial sums (red) increase like a log function, while inverse primes partial sums (blue) increase as the log of a log.

Sum of Reciprocals of Naturals

Lower Bound

The harmonic inverse numbers sum overestimates the corresponding integral as

H_n = \sum_{m=1}^n\frac{1}{m} >\int_1^{n+1}\hspace{-1.3em}\text{d}x\frac{1}{x} = \log(n+1),

where the sum is the area bounded by blue rectangles to the hyperbola 1/x, as in Fig. 2.

Figure 2: Tall blue rectangle sums overestimate the red integral area under the hyperbola, while short yellow rectangle sums underestimate it, for n=3.

Upper Bound

Similarly, the shifted sum underestimates the corresponding integral as

-1+H_n = -1 + \sum_{m=1}^n\frac{1}{m}= \sum_{m=2}^n\frac{1} {m}≤\int^n_{1}\hspace{-0.6em}\text{d}x\frac{1}{x} = \log n.

where the sum is the area bounded by short yellow rectangles to 1/x, and so

H_n ≤ \log n+1.

Tight Bound

Combine the lower and upper bounds to find

\log(n+1)<H_n≤\log n + 1,

and so

H_n = \sum_{m\le n} \frac{1}{m} = \mathcal{\Theta}(\log n).

Sum of Reciprocals of Primes

Lower Bound

The inverse numbers sum is dominated by

H_n = \sum_{m\le n} \frac{1}{m} < \sum_{n\ge p|m} \frac{1}{m} = \prod_{p\le n}\left(\sum_{k=0}^\infty \frac{1}{p^k}\right),

where the second sum is over all natural numbers m = p_1^{c_1} p_2^{c_2} \cdots p_r^{c_r} divisible by primes p \le n , which includes arbitrarily large m generated by the finite product of the infinite sum. The latter is a geometric series with start 1 and ratio 1/p, so

H_n < \prod_{p\le n} \left( 1-\frac{1}{p} \right)^{-1} < \prod_{p\le n} e^{2/p} = \exp\left({2\sum_{p\le n} 1/p}\right),

as e^{2/p} >1+2/p > (1-1/p)^{-1} for p\ge 2, and the product of exponentials is the exponential of the sum. Take logs of both sides to find

\log H_n < 2 \sum_{p\le n} \frac{1}{p} = 2 S_n

and since \log n < \log(n+1) < H_n from earlier,

S_n > \frac{1}{2} \log H_n > \frac{1}{2}\log\log n.

Upper Bound

Raise the inverse primes sum to the kth power and write it as a multidimensional sum over the inverse prime factors product

S_n^k = \left(\sum_{p\le n} \frac{1}{p}\right)^k = \hspace{-0.7em} \sum_{p_1,p_2,\cdots,p_k < n} \frac{1}{p_1 p_2\cdots p_k } < \sum_{m\le n^k} \frac{k!}{m},

as any reciprocal 1/m appears at most k! times with one prime from each of the k factors in any order in the product p_1p_2 \cdots p_k \le n^k. Since H_x \le \log x + 1 from earlier, write

S_n^k < k! H_{n^k} \le k! (\log n^k + 1) \le k!\, k\, 2\log n,

as 1 \le \log x for x \ge e > 2. Take the kth root of both sides to find

S_n < (k!\, k\, 2\log n)^{1/k} < k\, e\, 2(\log n)^{1/k},

as

\begin{aligned}(k!)^{1/k} &\le (k^k)^{1/k} = k, \\ k^{1/k} &= \left(e^{\log k}\right)^{1/k} = e^{(\log k) / k} < e^1 = e,\\ 2^{1/k} &\le 2,\end{aligned}

for k \ge 1. Now take k = \lfloor 1 + \log\log n \rfloor to get

\begin{aligned}S_n &< (1 + \log\log n) e 2 (\log n)^{1/(1+\log\log n)}\\ &= (1 + \log\log n) e 2 e^{\log\log n/(1+\log\log n)}\\ & \le (1 + \log\log n) e 2 e.\end{aligned}

Finally, for n \ge 3,

\begin{aligned}S_n &< 2e^2 \left(\frac{1}{\log\log n} + 1\right) \log\log n \\& \le 2e^2 \left(\frac{1}{\log\log 3} + 1\right) \log\log n \\& = C \log\log n,\end{aligned}

where the constant C = 2e^2(1/\log\log 3 + 1) \approx 172.

Tight Bound

Combine the lower and upper bounds to find

\frac{1}{2}\log\log n < S_n \lesssim 172 \log \log n,

and so

S_n = \sum_{p\le n} \frac{1}{p} = \mathcal{\Theta}(\log \log n).