§12.3 Prime Number Theorem

12.3 Prime Number Theorem

Prime numbers have been a central object of study in number theory since antiquity. From the times of Euclid, it was known that there were infinitely many primes. The prime counting function $𝜋 (𝑛)$ is defined to be the number of primes not exceeding $𝑛$ . The Prime Number Theorem states formally that:

Theorem 12.3.1.6 (Prime Number Theorem).

The prime counting function

𝜋 (𝑥)

is asymptotically equal to

\frac{𝑥}{log 𝑥}

, i.e.,

{lim}_{𝑥 \to \infty} \frac{𝜋 (𝑥) log 𝑥}{𝑥} = 1

This result was first conjectured by Gauss and Legendre in the late 18th century based on empirical evidence, while early results given by P. L. Chebyshev and J. J. Sylvester proved that the ratio $\frac{log (𝑛) 𝜋 (𝑛)}{𝑛}$ is bounded between two positive constants for large $𝑛$ . The full asymtotic relation was finally proven independently by Hadamard and de la Vallée Poussin in 1896 using complex analysis and properties of the Riemann $𝜁$ -function.

The logarithmic integral function, defined by

Li (𝑥) = \int_{2}^{𝑥} \frac{d 𝑡}{log 𝑡}

is of considerable interest as it much better approximates the prime counting function $𝜋 (𝑥)$ than $\frac{𝑥}{log 𝑥}$ does. It can be trivially shown that $Li (𝑥) \sim \frac{𝑥}{log 𝑥}$ by the realization that

\begin{aligned} Li (𝑥) & = {\frac{𝑡}{log 𝑡} |}_{2}^{𝑥} + \int_{2}^{𝑥} \frac{d 𝑡}{{log}^{2} 𝑡} = \frac{𝑥}{log 𝑥} + \int_{2}^{𝑥} \frac{d 𝑡}{{log}^{2} 𝑡} + 𝒪︀ (1) \\ = \frac{𝑥}{log 𝑥} + \frac{𝑥}{{log}^{2} 𝑥} + \frac{2 𝑥}{{log}^{3} 𝑥} + \frac{6 𝑥}{{log}^{4} 𝑥} + \dots + 𝒪︀ (1) \\ = \frac{𝑥}{log 𝑥} + ℴ︀ (\frac{𝑥}{{log}^{2} 𝑥}) . \end{aligned}

We have previously seen how the Riemann $𝜁$ -function could be used to determine properties of the distribution of primes. The proof of the Prime Number Theorem depends on a more subtle connection between $𝜁$ and $𝜋$ . The most efficient way to construct such a connection has been the subject of much experimentation. The proof we proceed to provide may seem arbitrary, we provide this connection via auxiliary functions. But a look into history reveals the many failed experiments and attempts that ultimately led to the simplicity of the proof presented below.

Define the first and second Chebyshev functions $𝜗 (𝑥), 𝜓 (𝑥)$ by

𝜗 (𝑥) = \sum_{\begin{matrix} 𝑝 \leq 𝑥 \\ 𝑝 prime \end{matrix}} log 𝑝, 𝜓 (𝑥) = \sum_{𝑛 \leq 𝑥} Λ (𝑛) = \sum_{\begin{matrix} (𝑝, 𝑘) : 𝑝^{𝑘} \leq 𝑥 \\ 𝑝 prime \end{matrix}} log 𝑝 .

We hence derive that

𝜓 (𝑥) = \sum_{𝑘 = 1}^{\infty} \sum_{\begin{matrix} 𝑝^{𝑘} \leq 𝑥 \\ 𝑝 prime \end{matrix}} log 𝑝 = \sum_{𝑘 = 1}^{\infty} \sum_{\begin{matrix} 𝑝 \leq \sqrt[𝑘]{𝑥} \\ 𝑝 prime \end{matrix}} log 𝑝 = \sum_{𝑘 = 1}^{\infty} 𝜗 (𝑥^{\frac{1}{𝑘}}) \geq 𝜗 (𝑥) .

Grouping by primes, we see that this is in fact equivalent to

\begin{aligned} 𝜓 (𝑥) & = \sum_{\begin{matrix} 𝑝 \leq 𝑥 \\ 𝑝 prime \end{matrix}} \sum_{\begin{matrix} 𝑘 : 𝑝^{𝑘} \leq 𝑥 \\ 𝑘 \in ℕ \end{matrix}} log 𝑝 = \sum_{\begin{matrix} 𝑝 \leq 𝑥 \\ 𝑝 prime \end{matrix}} \sum_{\forall 𝑘 \leq {log}_{𝑝} 𝑥} log 𝑝 \\ = \sum_{\begin{matrix} 𝑝 \leq 𝑥 \\ 𝑝 prime \end{matrix}} \sum_{𝑘 = 1}^{⌊ \frac{log 𝑥}{log 𝑝} ⌋} log 𝑝 = \sum_{\begin{matrix} 𝑝 \leq 𝑥 \\ 𝑝 prime \end{matrix}} ⌊ \frac{log 𝑥}{log 𝑝} ⌋ log 𝑝 \leq \sum_{\begin{matrix} 𝑝 \leq 𝑥 \\ 𝑝 prime \end{matrix}} log 𝑥 . (12.3 . 1) \end{aligned}

Hence we have for any $𝑥 > 1$ ,

0 \leq 𝜗 (𝑥) \leq 𝜓 (𝑥) \leq 𝜋 (𝑥) log 𝑥 . (12.3 . 2)

Theorem 12.3.1.

We have the following limit equivalences:

\underset{𝑥 \to \infty}{lim sup} \frac{𝜋 (𝑥) log 𝑥}{𝑥} = \underset{𝑥 \to \infty}{lim sup} \frac{𝜓 (𝑥)}{𝑥} = \underset{𝑥 \to \infty}{lim sup} \frac{𝜗 (𝑥)}{𝑥} (12.3 . 3)

and

\underset{𝑥 \to \infty}{lim inf} \frac{𝜋 (𝑥) log 𝑥}{𝑥} = \underset{𝑥 \to \infty}{lim inf} \frac{𝜓 (𝑥)}{𝑥} = \underset{𝑥 \to \infty}{lim inf} \frac{𝜗 (𝑥)}{𝑥} . (12.3 . 4)

Proof.

Let $0 < 𝛼 < 1$ be arbitrary and suppose $𝑥 > 1$ . By definition, we have

\begin{aligned} 𝜗 (𝑥) & = \sum_{\begin{matrix} 𝑝 \leq 𝑥 \\ 𝑝 prime \end{matrix}} log 𝑝 = \sum_{\begin{matrix} 𝑝 \leq 𝑥^{𝛼} \\ 𝑝 prime \end{matrix}} log 𝑝 + \sum_{\begin{matrix} 𝑥^{𝛼} < 𝑝 \leq 𝑥 \\ 𝑝 prime \end{matrix}} log 𝑝 \geq \sum_{\begin{matrix} 𝑥^{𝛼} < 𝑝 \leq 𝑥 \\ 𝑝 prime \end{matrix}} log 𝑝 \\ = log (𝑥^{𝛼}) \sum_{\begin{matrix} 𝑥^{𝛼} < 𝑝 \leq 𝑥 \\ 𝑝 prime \end{matrix}} \frac{log 𝑝}{log (𝑥^{𝛼})} > log (𝑥^{𝛼}) \sum_{\begin{matrix} 𝑥^{𝛼} < 𝑝 \leq 𝑥 \\ 𝑝 prime \end{matrix}} 1 \\ = 𝛼 log 𝑥 (𝜋 (𝑥) - 𝜋 (𝑥^{𝛼})) \geq 𝛼 log 𝑥 (𝜋 (𝑥) - 𝑥^{𝛼}) . \end{aligned}

Hence we have that

\frac{𝛼 𝜋 (𝑥) log 𝑥}{𝑥} - 𝛼 𝑥^{𝛼 - 1} log 𝑥 < \frac{𝜗 (𝑥)}{𝑥} \leq \frac{𝜓 (𝑥)}{𝑥} \leq \frac{𝜋 (𝑥) log 𝑥}{𝑥} (12.3 . 5)

by virtue of (12.3.2) $(12.3.2) (12.3.2)$ . Letting $𝑥 \to \infty$ and taking the limit supremum yields

\begin{aligned} 𝛼 \underset{𝑥 \to \infty}{lim sup} (\frac{𝜋 (𝑥) log 𝑥}{𝑥} - 𝑥^{𝛼 - 1} log 𝑥) & = 𝛼 \underset{𝑥 \to \infty}{lim sup} \frac{𝜋 (𝑥) log 𝑥}{𝑥} \leq \underset{𝑥 \to \infty}{lim sup} \frac{𝜗 (𝑥)}{𝑥} \\ \leq \underset{𝑥 \to \infty}{lim sup} \frac{𝜓 (𝑥)}{𝑥} \leq \underset{𝑥 \to \infty}{lim sup} \frac{𝜋 (𝑥) log 𝑥}{𝑥} . \end{aligned}

Letting

𝛼 \to 1^{-}

yields (12.3.3)

(12.3.3) (12.3.3)

. The proof of (12.3.4)

(12.3.4) (12.3.4)

follows similarly by taking limit infimums in (12.3.5)

(12.3.5) (12.3.5)

and

𝛼 \to 1^{-}

. ⁠

□

Theorem 12.3.2.

The Laplace transform of $𝜓 \circ exp$ defined as

𝑓 (𝑠) = \int_{0}^{\infty} 𝜓 (e^{𝑡}) e^{- 𝑠 𝑡} d 𝑡 (12.3 . 6)

converges for $ℜ𝔢 𝑠 > 1$ and defines a holomorphic function on this domain. Moreover, the function $𝑔$ defined by

𝑔 (𝑡) = lim_{𝜎 \to 1^{+}} [𝑓 (𝑠) - \frac{1}{𝑠 - 1}], 𝑠 = 𝜎 + i 𝑡

converges uniformly with respect to

𝑡

on compact subsets of

ℝ

and is continuous thereon.

Proof.

Let $𝑢 = e^{𝑡}$ , $d 𝑢 = e^{𝑡} d 𝑡$ . Then we obtain

\begin{aligned} 𝑓 (𝑠) & = \int_{1}^{\infty} 𝜓 (𝑢) 𝑢^{- 𝑠 - 1} d 𝑢 = \sum_{𝑛 = 1}^{\infty} \int_{𝑛}^{𝑛 + 1} 𝜓 (𝑢) 𝑢^{- 𝑠 - 1} d 𝑢 \\ = \sum_{𝑛 = 1}^{\infty} 𝜓 (𝑛) \int_{𝑛}^{𝑛 + 1} 𝑢^{- 𝑠 - 1} d 𝑢 = \sum_{𝑛 = 1}^{\infty} \sum_{𝑚 = 1}^{𝑛} Λ (𝑚) {\frac{𝑢^{- 𝑠}}{- 𝑠} |}_{𝑛}^{𝑛 + 1} \\ = \frac{1}{𝑠} \sum_{𝑛 = 1}^{\infty} \sum_{𝑚 = 1}^{𝑛} Λ (𝑚) [𝑛^{- 𝑠} - {(𝑛 + 1)}^{- 𝑠}] \\ = \frac{1}{𝑠} \sum_{𝑚 = 1}^{\infty} Λ (𝑚) \sum_{𝑛 = 𝑚}^{\infty} [𝑛^{- 𝑠} - {(𝑛 + 1)}^{- 𝑠}] \\ = \frac{1}{𝑠} \sum_{𝑚 = 1}^{\infty} Λ (𝑚) 𝑚^{- 𝑠} = \frac{1}{𝑠} \sum_{𝑛 = 1}^{\infty} \frac{Λ (𝑛)}{𝑛^{𝑠}} . \end{aligned}

by absolute convergence and the fact that the inner summation “telescopes.” By Proposition 12.2.9 $Proposition 12.2.9 Proposition 12.2.9$ , we have that for $ℜ𝔢 𝑠 > 1$ ,

𝑓 (𝑠) = - \frac{1}{𝑠} \frac{𝜁^{'} (𝑠)}{𝜁 (𝑠)} ⟹ 𝑓 (𝑠) - \frac{1}{𝑠 - 1} = - \frac{1}{𝑠} (\frac{𝜁^{'} (𝑠)}{𝜁 (𝑠)} + \frac{1}{𝑠 - 1}) - \frac{1}{𝑠} . (12.3 . 7)

The expression $\frac{𝜁^{'} (𝑠)}{𝜁 (𝑠)} + \frac{1}{𝑠 - 1}$ is meromorphic in $ℂ$ . Because $𝜁 (𝑠)$ has a simple pole at $𝑠 = 1$ with residue $1$ , it follows that

𝜁 (𝑠) = \frac{1}{𝑠 - 1} + 𝑙 (𝑠)

for some entire function $𝑙 : ℂ \to ℂ$ . By Proposition 12.2.6 $Proposition 12.2.6 Proposition 12.2.6$ and Theorem 12.2.11 $Theorem 12.2.11 Theorem 12.2.11$ , the quantity $𝜁 (𝑠) (𝑠 - 1) = 1 + (𝑠 - 1) 𝑙 (𝑠)$ does not vanish for $ℜ𝔢 𝑠 \geq 1$ (at $𝑠 = 1$ , the simple pole $𝜁$ cancels with the simple zero of $𝑠 - 1$ ). Hence,

\begin{aligned} \frac{𝜁^{'} (𝑠)}{𝜁 (𝑠)} + \frac{1}{𝑠 - 1} & = \frac{𝜁^{'} (𝑠) (𝑠 - 1) + 𝜁 (𝑠)}{𝜁 (𝑠) (𝑠 - 1)} = \frac{\frac{d}{d 𝑠} (𝜁 (𝑠) (𝑠 - 1))}{1 + (𝑠 - 1) 𝑙 (𝑠)} \\ = \frac{𝑙^{'} (𝑠) (𝑠 - 1) + 𝑙 (𝑠)}{1 + (𝑠 - 1) 𝑙 (𝑠)} \end{aligned}

and the displayed expression define holomorphic functions on $ℜ𝔢 𝑠 \geq 1$ (observe that the numerator is entire).

For a compact subset $𝐼 \subset ℝ$ , the complex rectangle $𝐾 = {𝑥 + i 𝑦 : 1 \leq 𝑥 \leq 2, 𝑦 \in 𝐼}$ is compact in $ℂ$ . Thus, by uniform continuity (given by Theorem 1.2.26 $Theorem 1.2.26 Theorem 1.2.26$ ), $\forall 𝜀 > 0$ , $\exists 𝛿 > 0$ such that $\forall 𝑠_{1} = 𝜎_{1} + i 𝑡_{1} \in 𝐾, \forall 𝑠_{2} = 𝜎_{2} + i 𝑡_{2} \in 𝐾 : | 𝑠_{1} - 𝑠_{2} | < 𝛿,$

| 𝑓 (𝑠_{1}) - \frac{1}{𝑠_{1} - 1} - 𝑓 (𝑠_{2}) + \frac{1}{𝑠_{2} - 1} | < 𝜀 .

In particular, for $𝜎_{1} = 1$ such that $𝑡_{2} = 𝑡_{1}$ ( $= 𝑡$ ), we have

𝑠 = 𝜎 + i 𝑡 \in 𝐾 : | 𝜎 - 1 | < 𝛿 ⟹ | 𝑓 (1 + i 𝑡) - \frac{1}{i 𝑡} - 𝑓 (𝑠) + \frac{1}{𝑠 - 1} | < 𝜀,

where $𝛿$ is chosen independently of $𝑡$ . Therefore, $𝑔 (𝑡)$ converges uniformly on compact subsets of $ℝ$ and is continuous thereon. ⁠ $□$