The Prime Number Theorem via Complex Analysis

The Prime Number Theorem (PNT) states that the number of primes up to

x

, denoted

π (x)

, is asymptotic to

x / lo g x

. Equivalently,

ψ (x) \sim x

, where

ψ

is the Chebyshev function. The proof via complex analysis hinges on the non-vanishing of the Riemann zeta function

ζ (s)

on the line

Re (s) = 1

and a Tauberian argument. First proved independently by Hadamard and de la Vallée Poussin in 1896, following Riemann's 1859 program. Applies throughout analytic number theory, cryptography heuristics, and the distribution of arithmetic objects.

The Prime Number Theorem is the central quantitative statement about the distribution of prime numbers: the asymptotic density of primes near a large integer $n$ is approximately $1/ lo g n$ . Its importance lies in transforming a discrete, seemingly erratic sequence into a smooth analytic law, and in revealing that prime distribution is governed by the analytic continuation and zero-free regions of the Riemann zeta function. The complex-analytic proof is a triumph of the principle that arithmetic information is encoded in the analytic behavior of generating Dirichlet series. The surprising fact: the entire theorem follows from the single qualitative input that $ζ (s) \neq = 0$ for $Re (s) = 1$ — no quantitative zero-free region is needed for PNT itself, only for error terms.

The Core Insight

Encode the primes in the Euler product for $ζ (s)$ . Taking a logarithmic derivative converts the product into a Dirichlet series whose coefficients are the von Mangoldt function $Λ (n)$ , summing to the Chebyshev $ψ (x)$ . A contour-integral (Perron/Mellin) representation of $ψ (x)$ then expresses it as a sum over the poles of $- ζ^{'} (s) / ζ (s)$ . The pole at $s = 1$ contributes the main term $x$ ; the absence of zeros on $Re (s) = 1$ guarantees all other contributions are $o (x)$ . Thus $ψ (x) \sim x ⟺ ζ (1 + i t) \neq = 0$ .

Formal Statement

Prime-counting and Chebyshev functions

For real $x \geq 2$ define:

π (x) = p \leq x \sum 1, ϑ (x) = p \leq x \sum lo g p, ψ (x) = p^{k} \leq x \sum lo g p = n \leq x \sum Λ (n)

⟳

π

counts primes;

ϑ

weights each prime by

lo g p

;

ψ

also counts prime powers, since

Λ (n) = lo g p

n = p^{k}

and

0

otherwise.

Here $Λ$ is the von Mangoldt function. These three functions are asymptotically equivalent in a precise sense and PNT can be stated through any of them. The logarithmic integral

li (x) = \int_{0}^{x} \frac{d t}{lo g t} (principal value), li (x) \sim \frac{x}{lo g x}

⟳integrate by parts repeatedly to get

li (x) = \frac{x}{l o g x} \sum_{k = 0}^{N} \frac{k !}{( l o g x ) ^{k}} + O (x / (lo g x)^{N + 2})

; the leading term is

x / lo g x

is the sharpest elementary main term.

Prime Number Theorem

As $x \to \infty$ ,

π (x) \sim \frac{x}{lo g x}, equivalently π (x) \sim li (x), ϑ (x) \sim x, ψ (x) \sim x

⟳the equivalences follow from partial summation (Abel summation) linking

π

ϑ

and from

ψ (x) - ϑ (x) = \sum_{k \geq 2} ϑ (x^{1/ k}) = O (x lo g x)

The notation $f \sim g$ means $f (x) / g (x) \to 1$ .

The Riemann zeta function and its Euler product

For $Re (s) = σ > 1$ ,

ζ (s) = n = 1 \sum \infty \frac{1}{n ^{s}} = p prime \prod (1 - p^{- s})^{- 1}

⟳expand each factor as a geometric series

\sum_{k \geq 0} p^{- k s}

and multiply; unique factorization of integers gives every

n^{- s}

exactly once.

ζ

extends to a meromorphic function on

C

with a single simple pole at

s = 1

with residue

1

. The logarithmic derivative generates

Λ

- \frac{ζ ^{'} ( s )}{ζ ( s )} = n = 1 \sum \infty \frac{Λ ( n )}{n ^{s}}, σ > 1

⟳

lo g ζ (s) = - \sum_{p} lo g (1 - p^{- s}) = \sum_{p} \sum_{k \geq 1} \frac{p ^{- k s}}{k}

; differentiate term-by-term to get

\sum_{p} \sum_{k} (lo g p) p^{- k s} = \sum_{n} Λ (n) n^{- s}

Why It Holds / Derivation

PNT via the Newman–Tauberian route

We prove $ψ (x) \sim x$ . We follow D. J. Newman's analytic simplification (1980), the cleanest modern complex-analytic proof.

Step 1 — Reduce to a Dirichlet series. From [5], the generating identity holds for

σ > 1

. Define

Φ (s) = p \sum \frac{lo g p}{p ^{s}} = - \frac{ζ ^{'} ( s )}{ζ ( s )} - p \sum k \geq 2 \sum \frac{lo g p}{p ^{k s}}, σ > 1

⟳split [5] into

k = 1

(the

Φ

sum) and

k \geq 2

; the latter converges for

σ > \frac{1}{2}

, hence is holomorphic there.

So $Φ (s)$ and $- ζ^{'} / ζ$ differ by a function holomorphic on $σ > \frac{1}{2}$ .

Step 2 — Pole and non-vanishing. Since

ζ

has a simple pole at

s = 1

- ζ^{'} / ζ

has a simple pole at

s = 1

with residue

+ 1

. The crucial analytic input is:

ζ (1 + i t) \neq = 0 for all t \in R, t \neq = 0

⟳use

3 + 4 cos θ + cos 2 θ = 2 (1 + cos θ)^{2} \geq 0

applied to

lo g ∣ ζ^{3} (σ) ζ^{4} (σ + i t) ζ (σ + 2 i t) ∣

; a zero at

1 + i t

would force this expression

\to - \infty

, a contradiction.

Consequently $Φ (s) - \frac{1}{s - 1}$ extends holomorphically to an open neighborhood of the closed half-plane $Re (s) \geq 1$ .

Step 3 — Integral representation. Using

ψ (x) = \sum_{n \leq x} Λ (n)

and partial summation, the key object is

\frac{Φ ( s )}{s} = s \int_{1}^{\infty} \frac{ϑ ( x )}{x ^{s + 1}} d x / s = \int_{1}^{\infty} \frac{ϑ ( x )}{x ^{s + 1}} d x, σ > 1

⟳

Φ (s) = \sum_{p} (lo g p) p^{- s} = s \int_{1}^{\infty} ϑ (x) x^{- s - 1} d x

by Abel summation, since

ϑ

is the partial-sum (step) function of the coefficients

lo g p

Step 4 — The Tauberian theorem (Newman). Substitute

x = e^{t}

ϑ (e^{t}) = e^{t} f (t) + \dots

; the relevant convergence theorem is:

Analytic Theorem. Let $g (t)$ ( $t \geq 0$ ) be bounded and locally integrable, with Laplace transform $G (z) = \int_{0}^{\infty} g (t) e^{- z t} d t$ holomorphic for $Re (z) > 0$ . If $G$ extends holomorphically to $Re (z) \geq 0$ , then $\int_{0}^{\infty} g (t) d t$ converges and equals $G (0)$ .

Apply with $g (t) = ϑ (e^{t}) e^{- t} - 1$ . One checks $G (z) = \frac{Φ ( z + 1 )}{z + 1} - \frac{1}{z}$ , which by Step 2 is holomorphic on $Re (z) \geq 0$ . Boundedness of $g$ requires Chebyshev's bound $ϑ (x) = O (x)$ .

\int_{1}^{\infty} \frac{ϑ ( x ) - x}{x ^{2}} d x converges

⟳this is the change of variables

t = lo g x

applied to

\int_{0}^{\infty} g (t) d t = G (0)

from the analytic theorem.

Step 5 — From convergence to asymptotics. Suppose

ϑ (x) \geq λ x

for some

λ > 1

on a sequence

x \to \infty

. Since

ϑ

is nondecreasing,

\int_{x}^{λ x} \frac{ϑ ( t ) - t}{t ^{2}} d t \geq \int_{x}^{λ x} \frac{λ x - t}{t ^{2}} d t = \int_{1}^{λ} \frac{λ - u}{u ^{2}} d u > 0

⟳bound

ϑ (t) \geq ϑ (x) \geq λ x

[x, λ x]

, substitute

t = ux

; the resulting positive constant is independent of

x

, contradicting Cauchy convergence of [9].

The same with $λ < 1$ (using $ϑ (t) \leq ϑ (λ x) \leq λ x$ , wait—) gives the lower contradiction; both force $ϑ (x) / x \to 1$ . Hence $ϑ (x) \sim x$ , and by [3] $ψ (x) \sim x$ and $π (x) \sim li (x)$ . $■$

The Chebyshev bound is not optional

Step 4 silently uses $ϑ (x) = O (x)$ to guarantee $g$ is bounded. This is Chebyshev's elementary estimate (1852), proved via the central binomial coefficient $(n 2 n)$ . Without it the Laplace transform may not even define a holomorphic function in the required half-plane. PNT is not purely complex-analytic in a vacuum — it rests on a prior elementary upper bound.

Bernhard Riemann | 1826–1866

Riemann's eight-page 1859 memoir "Über die Anzahl der Primzahlen unter einer gegebenen Größe" introduced the modern viewpoint: study $π (x)$ via the analytic continuation of $ζ (s)$ to all of $C$ , its functional equation relating $s \leftrightarrow 1 - s$ , and its nontrivial zeros. He wrote down an exact "explicit formula" for $π (x)$ as a sum over zeros and conjectured the Riemann Hypothesis (all nontrivial zeros on $Re (s) = \frac{1}{2}$ ). He did not prove PNT — several of his assertions were established only decades later by von Mangoldt, Hadamard, and de la Vallée Poussin. The complex-analytic proof of PNT is the realization, in its minimal form, of Riemann's program.

Building Intuition

Think of $ψ (x) = \sum_{n \leq x} Λ (n)$ as a signal. The Mellin/Perron formula

ψ (x) = x - ρ \sum \frac{x ^{ρ}}{ρ} - lo g (2 π) - \frac{1}{2} lo g (1 - x^{- 2})

⟳shift the contour in

ψ (x) = \frac{1}{2 π i} \int_{c - i \infty}^{c + i \infty} (- \frac{ζ ^{'}}{ζ} (s)) \frac{x ^{s}}{s} d s

across all poles;

s = 1

gives

x

, each nontrivial zero

ρ

gives

- x^{ρ} / ρ

, the trivial zeros give the log terms.

decomposes $ψ$ into a main term $x$ plus oscillations indexed by the zeros $ρ = β + iγ$ . Each zero contributes a wave $x^{β}$ in amplitude and $cos (γ lo g x)$ in phase. PNT, $ψ (x) \sim x$ , holds precisely when every such wave has amplitude $o (x)$ , i.e. $β < 1$ for all $ρ$ . The Riemann Hypothesis would put every $β = \frac{1}{2}$ , making the error $O (x lo g^{2} x)$ — the smallest conceivable. So: primes are as regularly distributed as the zeros of $ζ$ are far left of the line $Re (s) = 1$ .

Critical strip, the line Re(s)=1, and the contour of the Perron integral

<svg viewBox="0 0 640 420" xmlns="http://www.w3.org/2000/svg">
<rect width="640" height="420" fill="#0a0e17"/>
<!-- axes -->
<line x1="60" y1="210" x2="600" y2="210" stroke="#94a3b8" stroke-width="1.2"/>
<line x1="320" y1="30" x2="320" y2="390" stroke="#94a3b8" stroke-width="1.2"/>
<text x="605" y="205" fill="#e2e8f0" font-size="13">σ</text>
<text x="328" y="42" fill="#e2e8f0" font-size="13">t</text>
<!-- critical strip 0<sigma<1 -->
<rect x="320" y="30" width="120" height="360" fill="#1e293b" opacity="0.5"/>
<text x="350" y="380" fill="#e2e8f0" font-size="11">critical strip</text>
<!-- sigma=1/2 critical line -->
<line x1="380" y1="30" x2="380" y2="390" stroke="#d4a853" stroke-width="2" stroke-dasharray="6 4"/>
<text x="385" y="50" fill="#d4a853" font-size="12">Re(s)=1/2</text>
<!-- sigma=1 line: NON-VANISHING -->
<line x1="440" y1="30" x2="440" y2="390" stroke="#e2e8f0" stroke-width="1.6"/>
<text x="446" y="70" fill="#e2e8f0" font-size="12">Re(s)=1</text>
<text x="446" y="86" fill="#94a3b8" font-size="10">ζ ≠ 0 here</text>
<!-- pole at s=1 -->
<circle cx="440" cy="210" r="5" fill="#d4a853"/>
<text x="446" y="225" fill="#d4a853" font-size="11">pole s=1 (main term x)</text>
<!-- nontrivial zeros on critical line -->
<circle cx="380" cy="120" r="3.5" fill="#e2e8f0"/>
<circle cx="380" cy="160" r="3.5" fill="#e2e8f0"/>
<circle cx="380" cy="260" r="3.5" fill="#e2e8f0"/>
<circle cx="380" cy="300" r="3.5" fill="#e2e8f0"/>
<text x="300" y="115" fill="#94a3b8" font-size="10">ρ (zeros)</text>
<!-- Perron contour c+iT -->
<path d="M 500 60 L 500 360" stroke="#d4a853" stroke-width="1.6"/>
<text x="505" y="55" fill="#d4a853" font-size="11">contour Re(s)=c&gt;1</text>
<!-- shift arrow -->
<path d="M 495 210 L 445 210" stroke="#d4a853" stroke-width="1.4" marker-end="url(#a)"/>
<defs><marker id="a" markerWidth="8" markerHeight="8" refX="6" refY="3" orient="auto"><path d="M0,0 L6,3 L0,6 Z" fill="#d4a853"/></marker></defs>
<text x="35" y="195" fill="#94a3b8" font-size="10">0</text>
</svg>

Worked Examples

Numerical check of the main term and error

Given:

x = 1 0^{9}

. Compare

π (x)

with

x / lo g x

and

li (x)

. Steps:

$lo g (1 0^{9}) = 9 lo g 10 \approx 20.7233$ .
$x / lo g x \approx 1 0^{9} /20.7233 \approx 4.8255 \times 1 0^{7}$ .
$li (1 0^{9}) \approx 5.0849234 \times 1 0^{7}$ (numerically).
True value: $π (1 0^{9}) = 50847534$ .

Comparison: Relative error of

x / lo g x

(50847534 - 48254942) /50847534 \approx 5.1%

— slowly improving as predicted. Relative error of

li (x)

(50847534 - 50849234) /50847534 \approx - 3.3 \times 1 0^{- 5}

π (1 0^{9}) = 50847534, li (1 0^{9}) \approx 50849234, error \approx 1700 \approx 3.4 x / lo g x

The vastly superior accuracy of $li$ illustrates why it, not $x / lo g x$ , is the genuine main term.

From $\psi$ to $\pi$ via partial summation

Given: Assume

ψ (x) = x + O (x e^{- c l o g x})

(de la Vallée Poussin error). Derive the corresponding error for

π (x)

. Steps:

First $ϑ (x) = ψ (x) - O (x lo g x) = x + O (x e^{- c l o g x})$ .
Abel summation: $π (x) = \frac{ϑ ( x )}{lo g x} + \int_{2}^{x} \frac{ϑ ( t )}{t lo g ^{2} t} d t$ .
Substitute $ϑ (t) = t + E (t)$ , $E (t) = O (t e^{- c l o g t})$ :

π (x) = \frac{x}{lo g x} + \int_{2}^{x} \frac{d t}{lo g ^{2} t} + \frac{E ( x )}{lo g x} + \int_{2}^{x} \frac{E ( t )}{t lo g ^{2} t} d t .

The first two terms recombine into $li (x)$ ; the error integrals are dominated by $O (x e^{- c^{'} l o g x})$ .

π (x) = li (x) + O (x e^{- c l o g x})

This is the classical PNT with error term, equivalent to a zero-free region $σ > 1 - c / lo g (∣ t ∣ + 2)$ .

Common Misconceptions

PNT does not require the Riemann Hypothesis

A frequent error is to believe RH is needed for PNT. It is not. PNT follows from the strictly weaker fact $ζ (1 + i t) \neq = 0$ . RH only sharpens the error term to $O (x lo g^{2} x)$ . Conversely, knowing PNT gives essentially no zero-free region beyond the line $σ = 1$ itself.

$x/\log x$ vs. $\operatorname{li}(x)$ — both are correct, but unequal in quality

Both $x / lo g x$ and $li (x)$ are valid statements of " $π (x) \sim \cdot$ ", yet $π (x) - x / lo g x \sim x / lo g^{2} x \to \infty$ in absolute terms while staying $o (x / lo g x)$ . Asymptotic equivalence ( $\sim$ ) is about ratios, not differences. $li (x)$ captures the next-order corrections and is dramatically more accurate numerically.

$\pi(x)<\operatorname{li}(x)$ is NOT always true — Skewes' number

All computed data suggest $π (x) < li (x)$ . Yet Littlewood (1914) proved $π (x) - li (x)$ changes sign infinitely often. The first sign change (Skewes' number) is astronomically large — below $1.4 \times 1 0^{316}$ . This warns against extrapolating numerical "patterns": the oscillation terms $\sum_{ρ} x^{ρ} / ρ$ eventually overwhelm any finite empirical trend.

Connections

PNT sits at the hub of analytic number theory. Its proof is the prototype for the Wiener–Ikehara Tauberian Theorem, which abstracts Step 4. The non-vanishing $ζ (1 + i t) \neq = 0$ generalizes to Dirichlet L-functions, yielding the Prime Number Theorem in Arithmetic Progressions (Dirichlet's theorem with density $1/ φ (q)$ ). The error-term refinements connect directly to the Riemann Hypothesis and zero-free regions. The same machinery — Euler product, logarithmic derivative, Tauberian inversion — underlies the Chebotarev Density Theorem and the Sato–Tate Conjecture. Finally, the Selberg–Erdős Elementary Proof (1948) shows PNT can be obtained without complex analysis, a celebrated alternative route.

Real-World Applications

Cryptographic key generation (RSA, ECC). PNT predicts that a random odd $b$ -bit number is prime with probability $\approx 2/ (b ln 2)$ , so primality testing finds large primes in expected $O (b)$ trials — the quantitative backbone of RSA modulus generation.
Hash table and load estimates. Using primes for modular hashing relies on the density of primes near a target size, ensured by PNT.
Pseudorandom number generation. Linear congruential and lagged-Fibonacci generators with prime moduli use prime-gap heuristics derived from PNT.
Sieve theory and computational number theory. The complexity of the Sieve of Eratosthenes, $O (n lo g lo g n)$ , uses $\sum_{p \leq n} 1/ p \sim lo g lo g n$ (Mertens), a PNT-adjacent estimate.
Prime-counting algorithms (Meissel–Mertens–Lehmer, analytic methods). Modern computation of $π (1 0^{27})$ uses analytic formulas built on the explicit formula [11].
Statistical models of primes (Cramér's model). Treating primes as a Poisson process with density $1/ lo g n$ — justified by PNT — guides conjectures on prime gaps and twin primes.
Quantum chaos and random matrix theory. The Montgomery–Odlyzko law links zeta zero spacings to GUE eigenvalues; PNT supplies the mean density of zeros that normalizes these statistics.

Historical Development

1737 — Euler. Proves $\sum_{p} 1/ p$ diverges and establishes the Euler product for $ζ (s)$ , the first analytic link between primes and $ζ$ .
1798 / 1808 — Legendre. Conjectures $π (x) \approx x / (lo g x - B)$ with $B \approx 1.08366$ from numerical data.
1792–1849 — Gauss. Conjectures (in private notebooks, age 15) $π (x) \sim li (x)$ , the form that proved most accurate.
1852 — Chebyshev. Proves $0.921 x / lo g x < π (x) < 1.106 x / lo g x$ for large $x$ and that if $π (x) / (x / lo g x)$ has a limit, it is $1$ . Introduces $ϑ, ψ$ .
1859 — Riemann. Memoir on $π (x)$ : analytic continuation, functional equation, explicit formula, and the Riemann Hypothesis. Sets the program but proves no asymptotic.
1895 — von Mangoldt. Proves Riemann's explicit formula for $ψ (x)$ rigorously, reducing PNT to the non-vanishing of $ζ$ on $Re (s) = 1$ .
1896 — Hadamard & de la Vallée Poussin (independently). Prove $ζ (1 + i t) \neq = 0$ and deduce PNT. De la Vallée Poussin adds the zero-free region and error $O (x e^{- c l o g x})$ .
1948 — Selberg & Erdős. "Elementary" (no complex analysis) proof of PNT via Selberg's symmetry formula, sparking a famous priority dispute.
1980 — D. J. Newman. Drastically simplifies the analytic proof using a short contour-integral Tauberian theorem — now the standard graduate presentation.

Subtleties & Limits

The qualitative PNT is settled; the frontier is the size of the error term, governed entirely by the location of zeta zeros.

Riemann Hypothesis. $π (x) = li (x) + O (x lo g x)$ is equivalent to RH. Unproven; one of the Clay Millennium Problems.
Best unconditional zero-free region. The Vinogradov–Korobov region $σ > 1 - c / (lo g ∣ t ∣)^{2/3} (lo g lo g ∣ t ∣)^{1/3}$ gives the current best error $O (x exp (- c (lo g x)^{3/5} (lo g lo g x)^{- 1/5}))$ — still far from RH.
Sign changes (Littlewood/Skewes). Pinning the first crossing of $π (x) = li (x)$ and understanding the oscillation $π (x) - li (x) = Ω_{\pm} (x lo g lo g lo g x / lo g x)$ remains delicate.
Prime gaps. PNT gives average gap $lo g n$ but not maximal/minimal gaps; the twin prime and bounded-gap problems (Zhang, Maynard) lie beyond it.
Effective constants. Making $c$ explicit and uniform in companion theorems (e.g. for $L$ -functions, Siegel zeros) is an active obstacle, e.g. the ineffectivity of Siegel's bound.