The Prime Number Theorem and Dirichlet's Theorem

💡 The Core Insight

Primes, though individually unpredictable, obey precise statistical laws: globally, their density near $x$ is $1/\log x$ , and locally, they distribute equally among all allowable arithmetic progressions. The bridge between primes and analysis is built through generating functions that encode arithmetic data in their analytic properties.

Definition

The Prime Number Theorem and Dirichlet's Theorem: 1. (Prime Number Theorem) Let $\pi(x) = \#\{p \leq x : p \text{ prime}\}$ denote the prime counting function. Then

\pi(x) \sim \frac{x}{\log x} \quad \text{as } x \to \infty,

meaning $\lim_{x \to \infty} \frac{\pi(x)}{x/\log x} = 1$ . 2. (Dirichlet's Theorem) Let $a, q \in \mathbb{Z}$ with $\gcd(a,q) = 1$ . Then the arithmetic progression $\{a + nq : n \in \mathbb{N}\}$ contains infinitely many primes. More precisely, let $\pi(x; q, a) = \#\{p \leq x : p \text{ prime}, p \equiv a \pmod{q}\}$ . Then

\pi(x; q, a) \sim \frac{1}{\phi(q)} \cdot \frac{x}{\log x} \quad \text{as } x \to \infty,

where $\phi(q)$ is the <span class="wiki-link-missing">Euler totient function</span>.

TheoremMain Result

Theorem [1] (Prime Number Theorem — Analytic Form): The Riemann zeta function $\zeta(s) = \sum_{n=1}^{\infty} n^{-s}$ for $\Re(s) > 1$ extends to a meromorphic function on $\mathbb{C}$ with a simple pole at $s=1$ , and satisfies $\zeta(s) \neq 0$ for $\Re(s) = 1$ . This implies $\pi(x) \sim x/\log x$ .

Theorem [2] (Dirichlet's Theorem): For $\gcd(a,q) = 1$ , let $\chi$ be a Dirichlet character modulo $q$ , and define the Dirichlet L-function

L(s, \chi) = \sum_{n=1}^{\infty} \frac{\chi(n)}{n^s}, \quad \Re(s) > 1.

Then $L(1, \chi) \neq 0$ for all non-principal characters $\chi$ , which implies infinitely many primes in each residue class coprime to $q$ .

Proof

Proof of Theorem [1] (Sketch of classical approach): Step 1: Euler product and logarithmic connection. For $\Re(s) > 1$ , the Euler product formula gives

\zeta(s) = \prod_{p \text{ prime}} \frac{1}{1 - p^{-s}}.

Taking logarithms,

\log \zeta(s) = -\sum_p \log(1 - p^{-s}) = \sum_p \left( p^{-s} + O(p^{-2s}) \right) = \sum_p p^{-s} + O(1).

Step 2: Connection to prime counting. Define the Chebyshev function $\psi(x) = \sum_{p^k \leq x} \log p$ . By Perron's formula and Contour Integration,

\psi(x) = \frac{1}{2\pi i} \int_{c - i\infty}^{c + i\infty} \left(-\frac{\zeta'(s)}{\zeta(s)}\right) \frac{x^s}{s} ds

for suitable $c > 1$ . The PNT is equivalent to $\psi(x) \sim x$ . Step 3: Analytic continuation. The functional equation

\pi^{-s/2} \Gamma(s/2) \zeta(s) = \pi^{-(1-s)/2} \Gamma((1-s)/2) \zeta(1-s)

shows $\zeta(s)$ extends meromorphically to $\mathbb{C}$ with only a simple pole at $s=1$ (residue 1). Step 4: Zero-free region. The critical step: showing $\zeta(s) \neq 0$ on $\Re(s) = 1$ . For $\sigma > 1$ , the inequality

\zeta(\sigma)^3 |\zeta(\sigma + it)|^4 |\zeta(\sigma + 2it)| \geq 1

follows from $3 + 4\cos\theta + \cos 2\theta \geq 0$ . As $\sigma \to 1^+$ , if $\zeta(1+it) = 0$ , the left side would tend to 0, contradiction. Step 5: Shifting the contour. The zero-free region on $\Re(s) = 1$ allows shifting the integration contour in Step 2 to $\Re(s) = 1$ , picking up the residue at $s=1$ (which is $x$ ) and showing error terms are $o(x)$ . Thus $\psi(x) \sim x$ , which implies $\pi(x) \sim x/\log x$ by partial summation.

Proof of Theorem [2] (Sketch): Step 1: Orthogonality of characters. The Dirichlet characters modulo $q$ form an orthogonal basis for class functions on $(\mathbb{Z}/q\mathbb{Z})^*$ . By orthogonality,

\sum_{\chi \bmod q} \overline{\chi(a)} L(s, \chi) = \sum_{n \equiv a \pmod{q}} \frac{1}{n^s}.

Step 2: Showing $L(1, \chi) \neq 0$ . For the principal character $\chi_0$ , we have $L(s, \chi_0) = \zeta(s) \prod_{p \mid q}(1 - p^{-s})$ , which has a pole at $s=1$ . For non-principal $\chi$ :

If $\chi^2 = \chi_0$ (quadratic), use class number formula connections
In general, if $L(1, \chi) = 0$ , analyzing $\prod_{\chi} L(s, \chi)$ near $s=1$ via the product formula leads to contradictions with growth estimates

Step 3: Conclusion. Since $L(1, \chi_0)$ has a pole and $L(1, \chi) \neq 0$ for non-principal $\chi$ , the orthogonality sum shows infinitely many primes $p \equiv a \pmod{q}$ , with the asymptotic following from refined analysis. □

∎

⚠️ Common mistake

Common error: The PNT does NOT say $\pi(x) = x/\log x$ , only that the ratio tends to 1. The better approximation is the <span class="wiki-link-missing">logarithmic integral</span> $\text{li}(x) = \int_2^x \frac{dt}{\log t}$ , which satisfies $\text{li}(x) \sim x/\log x$ but $\text{li}(x) - \pi(x) = O(x e^{-c\sqrt{\log x}})$ . Also, Dirichlet's theorem requires $\gcd(a,q) = 1$ ; there are obviously no primes $p \equiv 0 \pmod{q}$ for $q > 1$ except possibly $p = q$ itself.

mathematician

Peter Gustav Lejeune Dirichlet (1837) — Proved the first deep result on primes in arithmetic progressions using the analytic properties of L-functions he introduced, creating the field of analytic number theory.

visualization

Example1

Computing π(100) and comparing with PNT approximation The primes up to 100 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. Thus $\pi(100) = 25$ . The PNT approximation gives:

\frac{100}{\log 100} = \frac{100}{\ln 100} = \frac{100}{4.605...} \approx 21.71

The relative error is $\frac{|25 - 21.71|}{25} \approx 13.2\%$ . The better approximation via the logarithmic integral:

\text{li}(100) = \int_2^{100} \frac{dt}{\log t} \approx 30.12

This overshoots but is known to be systematically higher than $\pi(x)$ for small $x$ (though this pattern eventually reverses, conjecturally around $x \approx 10^{316}$ by Skewes' number). For larger values: $\pi(10^6) = 78498$ while $10^6/\log(10^6) \approx 72382$ (error ~8%), showing convergence of the asymptotic.

Example2

Primes in arithmetic progressions modulo 4 Consider $q = 4$ . The invertible residue classes are $a \in \{1, 3\}$ with $\phi(4) = 2$ . Dirichlet's theorem predicts equal distribution:

\pi(x; 4, 1) \sim \pi(x; 4, 3) \sim \frac{1}{2} \cdot \frac{x}{\log x}

For $x = 100$ :

Primes $\equiv 1 \pmod{4}$ : 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97 — total: 11
Primes $\equiv 3 \pmod{4}$ : 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83 — total: 13

Prediction: $\frac{1}{2} \cdot 21.71 \approx 10.85$ for each class. The counts (11 and 13) are close and roughly equal, as predicted. The equidistribution becomes more pronounced as $x$ increases. This connects to the fact that the non-principal character modulo 4 is $\chi(n) = \begin{cases} 1 & n \equiv 1 \pmod{4} \\ -1 & n \equiv 3 \pmod{4} \end{cases}$ , and $L(1, \chi) = 1 - 1/3 + 1/5 - 1/7 + ... = \pi/4 \neq 0$ .

Counterexample

Why gcd condition is necessary in Dirichlet's theorem Consider the arithmetic progression $2, 6, 10, 14, 18, 22, ...$ (i.e., $a = 2, q = 4$ ). Here $\gcd(2, 4) = 2 \neq 1$ . This progression contains only one prime: $p = 2$ itself. All other terms are composite (even numbers $> 2$ ). This shows the coprimality condition $\gcd(a,q) = 1$ cannot be dropped. The underlying reason is group-theoretic: characters are defined on the unit group $(\mathbb{Z}/q\mathbb{Z})^*$ , and orthogonality relations only apply to invertible classes. Elements sharing a common factor with $q$ don't participate in the multiplicative structure that L-functions detect. More generally, if $d = \gcd(a,q) > 1$ , then every element of $a + q\mathbb{Z}$ is divisible by $d$ , so at most one prime (namely $p = d$ if it divides $a$ ) can occur.

🧠 Intuition

The sieve perspective: Imagine "sieving" the integers, removing multiples of each prime in turn (Sieve of Eratosthenes). After removing multiples of all primes up to $\sqrt{x}$ , approximately $x \prod_{p \leq \sqrt{x}}(1 - 1/p)$ numbers remain. By Mertens' theorems, this product behaves like $C/\log x$ for some constant $C$ , explaining the $x/\log x$ density. For arithmetic progressions, imagine the integers arranged in columns by residue class modulo $q$ . Sieving acts independently on each column (except for primes dividing $q$ ), so primes distribute equally among the $\phi(q)$ allowable columns. The L-function machinery makes this heuristic precise through harmonic analysis on the finite abelian group $(\mathbb{Z}/q\mathbb{Z})^*$ .

Probabilistic model: If we randomly assign each integer $n$ to be "prime" with probability $1/\log n$ , independently, we'd expect about $\int_2^x \frac{dt}{\log t} \sim x/\log x$ primes up to $x$ . The PNT says the actual deterministic distribution matches this random model asymptotically—a deep instance of pseudorandomness in number theory.

connection

Random Matrix Theory and the Montgomery-Odlyzko Law: In the 1970s, Hugh Montgomery discovered that the pair correlation of zeros of $\zeta(s)$ (when rescaled appropriately on the critical line) matches the pair correlation of eigenvalues of random matrices from the Gaussian Unitary Ensemble (GUE). Andrew Odlyzko's extensive numerical computations in the 1980s confirmed this with stunning precision. This connection suggests deep relationships between prime number distribution and Quantum Chaos, since GUE eigenvalues model energy levels of quantum systems with chaotic classical limits. The correspondence remains mysterious but has led to using random matrix theory to predict statistics of zeros and primes, with applications to cryptography and models in quantum physics.

The Prime Number Theorem and Dirichlet's Theorem

The Prime Number Theorem and Dirichlet's Theorem

Overview

Core Theory

Examples and Applications

Historical Development

Connections to Other Areas

What You Need First

What This Opens Up

See Also