# 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:

- $\pi \left({n}\right) \sim \dfrac n {\ln \left({n}\right)}$

where $\sim$ denotes asymptotic equivalence.

## Proof

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

From the Von Mangoldt Equivalence, the **Prime Number Theorem** is logically equivalent to:

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

where $\Lambda$ is the von Mangoldt function.

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

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

From Zeta Equivalence to Prime Number Theorem, the Prime Number Theorem is logically equivalent to the statement that:

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

Now we demonstrate the truth of this claim regarding $\dfrac{\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:

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

From Reciprocal of Riemann Zeta Function, Square of Riemann Zeta Function and Derivative of Riemann Zeta Function:

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

where:

- $\mu \left({n}\right)$ is the Möbius function
- $d \left({n}\right)$ 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_{a b \mathop \le N} \left({ \mu \left({a}\right) \left({ \ln \left({b}\right) - d \left({b}\right)}\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 the Euler-Mascheroni constant:

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

Using a convenient property of the Möbius function, this $1$ is just:

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

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

and so:

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

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

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

and by Order of Möbius Function:

- $\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({\dfrac{-1}{\sqrt N}}\right)$ dominates $o \left({N}\right)$.

## Interpretation

The **Prime Number Theorem** can also be rendered as:

- $\displaystyle \lim_{x \mathop \to \infty} \dfrac {\pi \left({x}\right) / x} {1 / \ln x} = 1$

where it can be interpreted as the probability that a number chosen at random will be prime.

Thus, for large $n$, that probability is approximately equal to $\dfrac 1 {\ln n}$.

## Historical Note

The Prime Number Theorem (PNT) was first conjectured by Carl Friedrich Gauss when he was $14$ or $15$, but he was never able to prove it.

He also posited the suggestion that it could be approximated by the Eulerian logarithmic integral $\displaystyle \operatorname {Li} \left({x}\right) = \int_2^x \frac {\mathrm d t}{\ln \left({t}\right)}$.

It took another century before a proof was found.

Pafnuty Lvovich Chebyshev was the first one to provide any support for Gauss's conjecture when he proved in $1850$ that:

- $\dfrac 7 8 < \dfrac {\pi \left({x}\right)} {x / \ln x} < \dfrac 9 8$

for all sufficiently large $x$.

He also proved that if the limit of the expression in question *does* exist, then its value must be $1$.

Since then, several complete proofs have been discovered.

The first proofs were given independently by Jacques Salomon Hadamard and Charles de la Vallée Poussin in $1896$.

They relied on the theory of functions of a complex variable.

The original theorem of Hadamard used in that proof is given on $\mathsf{Pr} \infty \mathsf{fWiki}$ as **Ingham's Theorem on Convergent Dirichlet Series**, which is used in Order of Möbius Function, an essential part of the above proof.

Atle Selberg and Paul 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 \left({n}\right)$ is asymptotic to $\dfrac n {\ln \left({n}\right)}$, it states nothing about the error of this approximation beyond:

- $\pi \left({n}\right) - \dfrac n {\ln \left({n}\right)} = 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 \ge 1$, the PNT would be false.

Investigations into the error of the approximation to $\pi \left({n}\right)$ continue, most notably with ongoing research on the Riemann Hypothesis.

If the hypothesis is true, then the error is:

- $\pi \left({n}\right) - \dfrac n {\ln \left({n}\right)} = O \left({\sqrt n}\log n\right)$

If the hypothesis is false, the error is: $O \left({ n^\alpha }\right)$ for some $\alpha > \dfrac 1 2$