Prime Number Theorem

Theorem

The prime-counting function $\pi \left({n}\right)$, that is, the number of primes less than $n$, satisfies:

$\displaystyle \lim_{n \to \infty} \pi \left({n}\right) \frac {\ln \left({n}\right)} n = 1$

or equivalently,

$\displaystyle \pi \left({n}\right) \sim \frac n {\ln \left({n}\right)}$

Proof

The proof presented here is a version of Donald Newman's proof. For ease of reading, the proof is broken into parts, with the goal of each part presented.

The Mangoldt Equivalency

We begin by proving that the claim

$\displaystyle \lim_{N \to \infty} \frac 1 N \sum_{n=1}^N \Lambda \left({n}\right) = 1$

where $\Lambda$ is the Mangoldt Function, is logically equivalent to the Prime Number Theorem.

Observe:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \sum_{n=1}^N \Lambda \left({n}\right)\)	\(=\)	\(\displaystyle \Lambda \left({1}\right) + \Lambda \left({2}\right) + \cdots + \Lambda \left({N}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle 0 + \ln \left({2}\right) + \ln \left({3}\right) + \ln \left({2}\right) + \ln \left({5}\right) + 0 + \ln \left({7}\right) + \ln \left({2}\right) + \ln \left({3}\right) + 0 + \cdots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Notice this sum will have:

• as many $\ln(2)$ terms as there are powers of $2$ less than or equal to $N$
• as many $\ln(3)$ terms as there are powers of $3$ less than or equal to $N$

and in general, if $p$ is a prime less than $N$, $\ln (p)$ will occur in this sum $\left \lfloor {\log_p (N) } \right \rfloor$ times.

But :

$\displaystyle \ln (p) \left \lfloor {\log_p (N)} \right \rfloor \sim \ln (p) \log_p (N) = \ln(N)$

so

$\displaystyle \sum_{p \text{ prime} \leq N} \ln(p) \left \lfloor {\log_p(N)} \right \rfloor \sim \sum_{p \text{ prime} \le N} \ln(N) = \pi(N) \ln(N)$

Therefore

$\displaystyle \sum_{n=1}^N \Lambda(n) \sim \pi(N) \ln(N)$

and so if

$\displaystyle \lim_{N \to \infty} \frac{1}{N} \sum_{n=1}^N \Lambda(n) = 1$

then

$\displaystyle \lim_{N \to \infty} \frac{1}{N} \pi(N) \ln(N) = 1$

and vice versa.

But this last eqn is precisely the Prime Number Theorem; hence our statement regarding the Mangoldt function is logically equivalent to the Prime Number Theorem.

The Zeta Equivalency

While useful, the Mangoldt function is a discrete function that is not very much easier to work with than $\pi(n)$ itself.

It behooves us to find another statement equivalent to the Prime Number Theorem.

The claim about the Mangoldt function is equivalent (clearly) to the statement that the average of the coefficients of the function of $z$ defined as:

$\displaystyle \sum_{n=1}^\infty \frac{\Lambda(n)}{n^z}$

tend to $1$.

Let $ \left\{{ p_1, p_2, p_3, \dots }\right\}$ be an enumeration of the prime numbers, ie, $\left\{{ 2, 3, 5, 7, 11, \dots }\right\}$.

As we have seen, in the sum of Mangoldt functions, the $\ln(p)$ term will appear once for each power of $p$. So, we expand out this function just defined above as:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \sum_{n=1}^\infty \frac{\Lambda(n)}{n^z}\)	\(=\)	\(\displaystyle \ln(p_1) \left({\frac{1}{p_1^z} + \frac{1}{p_1^{2z} } + \frac{1}{p_1^{3z} } + \cdots}\right) + \ln(p_2) \left({\frac{1}{p_2^z} + \frac{1}{p_2^{2z} } + \cdots}\right) + \cdots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \ln(p_1) \sum_{n=1}^\infty \left({\left({ p_1^{-z} }\right)^n}\right) + \ln(p_2) \sum_{n=1}^\infty \left({\left({p_2^{-z} }\right)^n}\right) + \cdots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \ln(p_1) \frac{p_1^{-z} }{1-p_1^{-z} } + \ln(p_2) \frac{p_2^{-z} }{1-p_2^{-z} } + \cdots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Sum of Infinite Geometric Progression
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sum_{p \text{ prime} } \ln(p) \frac{p^{-z} }{1-p^{-z} }\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

This function of $z$ can be recognized as:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \sum_{p \text{ prime} } \ln(p) \frac{p^{-z} }{1-p^{-z} }\)	\(=\)	\(\displaystyle \sum_{p \text{ prime} } \left({1-p^{-z} }\right) \frac{-(0-\ln(p) p^{-z})}{\left({1-p^{-z} }\right)^2}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sum_{p \text{ prime} } \frac{d}{dz} \ln \left({\frac{1}{1-p^{-z} } }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac{d}{dz} \left({\sum_{p \text{ prime} } \ln \left({ \frac{1}{1-p^{-z} } }\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac{d}{dz} \left({\ln \prod_{p \text{ prime} } \frac{1}{1-p^{-z} } }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac{d}{dz} \ln \left({\zeta(z)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	$\prod_{p \text{ prime} } \frac{1}{1-p^{-z} }$ is the Riemann zeta function
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac{\zeta'(z)}{\zeta(z)}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Hence, the Prime Number Theorem is logically equivalent to the statement that the average of the first $N$ coefficients of $\tfrac{\zeta'}{\zeta}$ tend to $1$ as $N$ goes to infinity.

The Proof of the Prime Number Theorem

Now we demonstrate the truth of this claim regarding $\frac{\zeta'}{\zeta}$. Doing so proves the Prime Number Theorem.

We know that all of the coefficients of $\zeta$ are precisely $1$.

So the statement:

• The average of the first $N$ coefficients of $\frac{\zeta'}{\zeta}$ tend to $1$ as $N$ goes to infinity

is equivalent to the statement:

• The average of the first $N$ coefficients of $\frac{\zeta'}{\zeta} - \zeta$ tend to $0$ as $N$ goes to infinity.

The latter will be more convenient for our purposes.

We write:

$\displaystyle \frac{\zeta'(z)}{\zeta(z)} - \zeta(z) = \frac{1}{\zeta(z)} \left({ \zeta'(z) - \zeta^2 (z) }\right)$

so that we can use knowledge of the inverse and square of $\zeta$, and knowledge of its derivative:

$\displaystyle \frac{1}{\zeta(z)} \left({ \zeta'(z) - \zeta^2 (z) }\right) = \left({ \sum_{n=1}^\infty \frac{\mu(n)}{n^z} }\right) \left({ \left({ \sum_{n=1}^\infty \frac{\log(n)}{n^z} }\right) - \left({ \sum_{n=1}^\infty \frac{d(n)}{n^z} }\right) }\right)$

where $\mu(n)$ is the Moebius function and $d(n)$ is the divisor function.

Given this form of the function, we can see that the average of the first $N$ coefficients is:

$\displaystyle \frac{1}{N} \sum_{ab \leq N} \left({ \mu(a) \left({ \log(b) - d(b) }\right) }\right)$

Hence the Prime Number Theorem is equivalent to the statement that this expression tends to $0$ as $N \to \infty$.

At this point, we can add $0 = 2\gamma / N - 2\gamma / N$, where $\gamma$ is Eulers constant:

$\displaystyle = \frac{1}{N} \sum_{ab \leq N} \left({ \mu(a) \left({ \ln(b) - d(b) }\right) }\right) + 1 \frac{2 \gamma}{N}- \frac{2\gamma}{N}$

Using a convenient property of the Moebius function, this $1$ is just

$\displaystyle 1 = \underbrace{ \sum_{a \backslash 1} \mu(a)}_{=1} + \underbrace{\sum_{a \backslash 2} \mu(a)}_{=0} + \dots + \underbrace{\sum_{a \backslash N} \mu(a)}_{=0}$

$\displaystyle = \sum_{n=1}^N \left({ \sum_{a \backslash n} \mu(a) }\right)$

and so

$\displaystyle = \frac{1}{N} \sum_{ab \leq N} \left({ \mu(a) \left({ \ln(b) - d(b) }\right) }\right) + 1 \frac{2\gamma}{N}- \frac{2\gamma}{N} = \frac{1}{N} \sum_{ab \leq N} \left({ \mu(a) \left({ \ln(b) - d(b) }\right) }\right) + \frac{1}{N} \sum_{n=1}^N \left({ \sum_{a \backslash n} \mu(a)2\gamma }\right) - \frac{2\gamma}{N}$

$\displaystyle = \frac{1}{N} \sum_{ab \leq N} \left({ \mu(a) \left({ \ln(b) - d(b) + 2\gamma }\right) }\right) - \frac{2\gamma} N$

By the theorem of the order of the divisor function, we recognize this is just

$\displaystyle = \frac{1}{N} \sum_{a \leq N} \mu(a) O \left({ -\sqrt{N} }\right) - \frac{2\gamma}{N} $

and by the order of the Moebius function, we have

$\displaystyle = \frac 1 N o \left({ N}\right) O \left({-\sqrt N}\right) - \frac {2\gamma} N = O \left({ \frac{-1}{\sqrt N}}\right) o \left({N}\right) - \frac{2\gamma}{N}$

As $N \to \infty$, we have

$\displaystyle \lim_{N \to \infty} \left({ O \left({ \frac{-1}{\sqrt{N}}}\right) o \left({N}\right) - \frac{2\gamma}{N} }\right) $

which clearly goes to $0$ as $O \left({\frac{-1}{\sqrt{N}}}\right)$ dominates $ o \left({N}\right)$.

Notes

There are a large number of proofs of the PNT. The first proofs, given independently by Hadamard and Poussin in 1896, relied on the theory of functions of a complex variable. The original theorem of Hadamard used in that proof is given on ProofWiki as "Ingham's Theorem on Convergent Dirichlet Series," which is used in the order of the Moebius function, an essential part of the above proof.

Selberg and Erdős would later give an elementary proof of the PNT, in 1948. Their proof did not make use of any analytic function theory, and relied entirely on basic properties of logarithms. Dispute over whether to publish their results jointly or separately created a life-long feud between the two mathematicians.

While the PNT states that $\pi(n)$ is asymptotic to $\dfrac{n}{\log(n)}$, it states nothing about the error of this approximation beyond $\pi(n)-\dfrac{n}{\log(n)}=O\left({ n^\alpha }\right)$, where $\alpha < 1$. This follows from the PNT because if the error was of the form $O\left({ n^\alpha }\right), \alpha \geq 1$, the PNT would be false. Investigations into the error of the approximation to $\pi(n)$ continue, most notably with ongoing research on the Riemann Hypothesis. If the hypothesis is true, then the error is $\pi(n)-\dfrac{n}{\log(n)}=O\left({\sqrt{n}}\right)$; if the hypothesis is false, the error is $O\left({ n^\alpha }\right)$ for some $\alpha > \dfrac 1 2$.