The Prime Number Theorem and Dirichlet's Theorem

One-line statement: The Prime Number Theorem (PNT) asserts

π (x) \sim x / ln x

, while Dirichlet's Theorem guarantees infinitely many primes in every admissible arithmetic progression

a, a + q, a + 2 q, \dots

with

g cd (a, q) = 1

. Key result in words: Primes thin out logarithmically, and they distribute evenly among the

φ (q)

admissible residue classes modulo

q

. Where it applies: Analytic number theory, cryptography, sieve theory, random matrix heuristics, distribution of arithmetic functions. Who/when: Conjectured by Gauss (1792–1796) and Legendre (1798); Dirichlet (1837) for progressions; PNT proved independently by Hadamard and de la Vallée Poussin (1896).

The Prime Number Theorem quantifies the asymptotic density of primes: the prime-counting function $π (x)$ , which counts primes $\leq x$ , satisfies $π (x) \sim x / ln x$ , equivalently $π (x) \sim Li (x)$ . Dirichlet's Theorem on arithmetic progressions refines the qualitative question of which integers are prime by proving that any coprime residue class contains infinitely many primes, and (in its quantitative form, the PNT for arithmetic progressions) that primes are equidistributed among the $φ (q)$ such classes. Both theorems rest on the analytic continuation and non-vanishing of $L$ -functions — the Riemann zeta function $ζ (s)$ for PNT and Dirichlet $L$ -functions $L (s, χ)$ for progressions. The surprising fact is that a statement about integers (primes) is most naturally proved through the complex analysis of $ζ (s)$ on the line $Re (s) = 1$ : the prime counting bound is equivalent to $ζ (1 + i t) \neq = 0$ .

The Core Insight

Counting primes is a problem in harmonic analysis on the integers. The link is the Euler product, which encodes the multiplicative structure of $Z$ into an analytic object. Taking logarithms converts the product over primes into a sum, and a contour integral (Perron's formula) inverts that sum back into a count. The location of zeros of the relevant $L$ -function controls the error term: the boundary of the critical strip ( $Re (s) = 1$ being zero-free) gives the qualitative asymptotic, while the Riemann Hypothesis would give the optimal square-root error. Dirichlet's masterstroke was to detect a single residue class with characters $χ$ — orthogonal functions that act as a discrete Fourier basis on $(Z / q Z)^{\times}$ — turning "primes $\equiv a (mod q)$ " into a linear combination of $lo g L (s, χ)$ .

Formal Statement

Prime-counting and auxiliary functions

Let $p$ range over primes. Define

π (x) = p \leq x \sum 1, θ (x) = p \leq x \sum ln p, ψ (x) = p^{k} \leq x \sum ln p = n \leq x \sum Λ (n),

⟳

θ

(Chebyshev's first function) sums logs of primes;

ψ

(second function) sums the von Mangoldt function

Λ (n) = ln p

n = p^{k}

and

0

otherwise, weighting prime powers.

The logarithmic integral is

Li (x) = \int_{2}^{x} \frac{d t}{ln t} = \frac{x}{ln x} (1 + \frac{1 !}{ln x} + \frac{2 !}{ln ^{2} x} + \dots) .

⟳integrate by parts repeatedly on

\int d t / ln t

to generate the asymptotic series; this shows

Li (x) \sim x / ln x

but is a strictly better approximant.

Dirichlet characters and L-functions

A Dirichlet character mod $q$ is a completely multiplicative function $χ : Z \to C$ , periodic mod $q$ , with $χ (n) = 0$ iff $g cd (n, q) > 1$ . The associated L-function is

L (s, χ) = n = 1 \sum \infty \frac{χ ( n )}{n ^{s}} = p \prod (1 - \frac{χ ( p )}{p ^{s}})^{- 1}, Re (s) > 1.

⟳the Euler product follows from complete multiplicativity of

χ

plus unique factorization; expand each factor as a geometric series and multiply.

The principal character $χ_{0}$ takes value $1$ on units; then $L (s, χ_{0}) = ζ (s) \prod_{p ∣ q} (1 - p^{- s})$ .

Prime Number Theorem

As $x \to \infty$ ,

π (x) \sim \frac{x}{ln x}, equivalently ψ (x) \sim x, θ (x) \sim x .

⟳partial summation (Abel summation) converts between

π

θ

ψ

; the three statements are equivalent. The

ψ

form is analytically cleanest.

With the classical (de la Vallée Poussin) zero-free region, the sharpest unconditional error is

π (x) = Li (x) + O (x exp (- c ln x)) (c > 0) .

⟳the error stems from a zero-free region

σ > 1 - c / ln ∣ t ∣

; optimizing the contour shift against the

∣ t ∣

-dependence yields the

exp (- c ln x)

rate. Under RH this improves to

O (x ln x)

Dirichlet's Theorem

If $g cd (a, q) = 1$ , the arithmetic progression ${a + n q : n \geq 0}$ contains infinitely many primes. Quantitatively (PNT for progressions),

π (x; q, a) := p \leq x p \equiv a (q) \sum 1 \sim \frac{1}{φ ( q )} \frac{x}{ln x} .

⟳the factor

1/ φ (q)

reflects equidistribution over the

φ (q)

invertible residue classes; it follows from

L (1, χ) \neq = 0

for all

χ \neq = χ_{0}

combined with the orthogonality of characters.

Why It Holds / Derivation

PNT via the zeta function (Newman/Wiener–Ikehara skeleton)

Step 1 — Logarithmic derivative. From the Euler product

ζ (s) = \prod_{p} (1 - p^{- s})^{- 1}

, take

- lo g

and differentiate:

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

⟳

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

; differentiate term-by-term to recover

Λ (n)

as Dirichlet coefficients.

Step 2 — Perron / contour inversion. Express the smoothed count as a contour integral:

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

⟳

\frac{1}{2 π i} \int x^{s} / s d s

is the discontinuous Heaviside integral, equal to

1

for

x > 1

and

0

for

0 < x < 1

; integrating term-by-term over

Λ (n) x^{s} n^{- s}

recovers

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

Step 3 — Shift the contour to $Re (s) = 1$ . Move the line of integration leftward. The pole of

ζ (s)

s = 1

(simple, residue

1

) gives

- ζ^{'} / ζ

a simple pole with residue

1

, contributing the main term:

Res_{s = 1} (- \frac{ζ ^{'} ( s )}{ζ ( s )} \frac{x ^{s}}{s}) = x .

⟳near

s = 1

ζ (s) = \frac{1}{s - 1} + γ + \dots

, so

- ζ^{'} / ζ \sim 1/ (s - 1)

; multiply by

x^{s} / s

and read off the residue at

s = 1

, giving

x^{1} /1 = x

Step 4 — Non-vanishing on the line $Re (s) = 1$ . The crux:

ζ (1 + i t) \neq = 0

for all real

t \neq = 0

. This uses the inequality

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

⟳apply this with

ϕ = t ln p

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

; the nonnegativity forces

∣ ζ (σ + i t) ∣

to not vanish faster than

(σ - 1)

allows, ruling out a zero at

σ = 1

Step 5 — Tauberian conclusion. With no zeros on

Re (s) = 1

, the boundary integral over

Re (s) = 1

contributes

o (x)

. The Wiener–Ikehara Tauberian theorem (or Newman's contour argument) then converts the analytic behavior into

ψ (x) \sim x

. Partial summation gives

π (x) \sim x / ln x

■

Dirichlet's Theorem: detecting a residue class

Step 1 — Orthogonality of characters. For

g cd (a, q) = 1

\frac{1}{φ ( q )} χ mod q \sum \overline{χ (a)} χ (n) = {10 n \equiv a (q) else .

⟳the characters form an orthonormal basis of functions on

(Z / q Z)^{\times}

; this is the column-orthogonality relation of the character table of a finite abelian group.

Step 2 — Sum over primes. Multiply by

Λ (n) n^{- s}

and sum:

n \equiv a (q) \sum \frac{Λ ( n )}{n ^{s}} = \frac{1}{φ ( q )} χ \sum \overline{χ (a)} (- \frac{L ^{'} ( s , χ )}{L ( s , χ )}) .

⟳

- L^{'} / L (s, χ) = \sum_{n} χ (n) Λ (n) n^{- s}

by the same logarithmic-derivative computation as for

ζ

; substitute and use orthogonality from [11].

Step 3 — Behavior at $s \to 1^{+}$ . The principal character term contributes a pole (from

L (s, χ_{0}) \sim 1/ (s - 1)

up to local factors), giving divergence

\sim \frac{1}{φ ( q )} lo g \frac{1}{s - 1}

p \equiv a (q) \sum p^{- s} \sim \frac{1}{φ ( q )} lo g \frac{1}{s - 1} (s \to 1^{+}) .

⟳only

χ_{0}

gives a pole; the non-principal terms stay bounded — provided

L (1, χ) \neq = 0

— so they cannot cancel the divergence.

Step 4 — The hard lemma: $L (1, χ) \neq = 0$ for $χ \neq = χ_{0}$ . Complex characters: a vanishing

L (1, χ) = 0

would force

L (1, \overset{χ}{ˉ}) = 0

, producing a double cancellation contradicting

\prod_{χ} L (s, χ) \geq 1

(a Dedekind-zeta-type product with nonnegative Dirichlet coefficients). Real characters (the delicate case):

L (1, χ) > 0

follows from Dirichlet's class number formula

L (1, χ) = \frac{2 h l o g ε}{D}

(real) or

\frac{2 π h}{w ∣ D ∣}

(imaginary), all manifestly positive.

⟳the real-character case is the unique one resisting purely analytic argument; the class number formula identifies

L (1, χ)

with a positive geometric/arithmetic invariant of a quadratic field.

Step 5 — Conclusion. Since [13] diverges as

s \to 1^{+}

, the sum

\sum_{p \equiv a (q)} p^{- s}

has infinitely many terms — there are infinitely many such primes, and the leading constant

1/ φ (q)

yields equidistribution.

■

Bernhard Riemann | 1826–1866

Though the PNT was proved by Hadamard and de la Vallée Poussin, its entire framework descends from Riemann's single 1859 memoir "Über die Anzahl der Primzahlen unter einer gegebenen Größe." In eight pages, Riemann analytically continued $ζ (s)$ to all of $C$ , established the functional equation relating $s$ to $1 - s$ , introduced the explicit formula expressing $ψ (x)$ as a sum over the nontrivial zeros $ρ$ , and conjectured that all such zeros lie on $Re (s) = 1/2$ . His explicit formula

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

makes precise the slogan: the primes are music, and the zeros are the frequencies. Every modern error term in PNT is a statement about how far left the zeros stay.

Building Intuition

Think of $Λ (n)$ as the "prime mass" placed at $n$ . The Euler product says this mass is multiplicatively organized. Taking a Dirichlet series is like taking a Fourier/Laplace transform: smooth, global behavior of the transform ( $ζ$ near $s = 1$ ) encodes the average density of mass, while singularities away from $s = 1$ (the zeros) encode oscillations in the prime count.

The main term $x$ in $ψ (x) \sim x$ comes from the one pole at $s = 1$ . Each zero $ρ = β + iγ$ contributes a wave $- x^{ρ} / ρ = - x^{β} e^{iγ l n x} / ρ$ — an oscillation of amplitude $x^{β}$ and frequency $γ / (2 π)$ in $lo g x$ . If any zero had $β = 1$ , its wave would be as large as the main term and PNT would fail; that is exactly why $ζ (1 + i t) \neq = 0$ is the heart of the proof.

For Dirichlet: characters are the Fourier modes on the clock face $Z / q Z$ . Asking "is $p \equiv a$ ?" is asking for one Fourier coefficient. The principal character is the "DC component" carrying the bulk $x / φ (q)$ ; the others are bounded ripples — if their $L$ -functions don't vanish at $s = 1$ .

Prime counting: $\pi(x)$ against its approximants $x/\ln x$ and $\operatorname{Li}(x)$

<svg viewBox="0 0 640 400" xmlns="http://www.w3.org/2000/svg">
<rect width="640" height="400" fill="#0a0e17"/>
<line x1="60" y1="350" x2="600" y2="350" stroke="#94a3b8" stroke-width="1.5"/>
<line x1="60" y1="350" x2="60" y2="40" stroke="#94a3b8" stroke-width="1.5"/>
<text x="320" y="385" fill="#e2e8f0" font-size="14" text-anchor="middle">x</text>
<text x="20" y="200" fill="#e2e8f0" font-size="14" transform="rotate(-90 20 200)" text-anchor="middle">count</text>
<!-- Li(x): top curve (best approx) -->
<path d="M60,330 Q200,250 350,170 T600,70" fill="none" stroke="#d4a853" stroke-width="2.5"/>
<text x="500" y="95" fill="#d4a853" font-size="13">Li(x)</text>
<!-- pi(x): staircase-like, just below Li -->
<path d="M60,332 Q200,256 350,178 T600,82" fill="none" stroke="#e2e8f0" stroke-width="2" stroke-dasharray="2,3"/>
<text x="430" y="135" fill="#e2e8f0" font-size="13">&#960;(x)</text>
<!-- x/ln x: lower curve (underestimates) -->
<path d="M60,338 Q200,285 350,225 T600,130" fill="none" stroke="#94a3b8" stroke-width="2"/>
<text x="470" y="175" fill="#94a3b8" font-size="13">x / ln x</text>
<text x="60" y="368" fill="#94a3b8" font-size="11">0</text>
<text x="590" y="368" fill="#94a3b8" font-size="11" text-anchor="end">large x</text>
<text x="320" y="30" fill="#e2e8f0" font-size="13" text-anchor="middle">All three are asymptotic; Li(x) tracks &#960;(x) far more closely.</text>
</svg>

Worked Examples

Estimating $\pi(10^9)$ three ways

Given:

x = 1 0^{9}

. True value:

π (1 0^{9}) = 50, 847, 534

. Step 1 — Crude PNT estimate.

ln (1 0^{9}) = 9 ln 10 \approx 20.723

. So

\frac{x}{ln x} = \frac{1 0 ^{9}}{20.723} \approx 48, 254, 942.

Relative error vs. truth:

(50.85 - 48.25) /50.85 \approx 5.1%

. Step 2 — Logarithmic integral. Numerically

Li (1 0^{9}) \approx 50, 849, 235

. Relative error:

(50, 849, 235 - 50, 847, 534) /50, 847, 534 \approx 3.3 \times 1 0^{- 5}

— far superior. Step 3 — Why Li wins.

Li (x)

includes the correction series

\frac{x}{l n x} (1 + \frac{1}{l n x} + \dots)

; the first correction alone adds

\approx 48, 254, 942/20.723 \approx 2, 328, 000

, recovering most of the gap.

π (1 0^{9}) \approx Li (1 0^{9}) \approx 50, 849, 235 (error \sim 1700, \approx 0.003%)

Counting primes in a residue class mod 12

Given: Estimate primes

\leq 1 0^{6}

with

p \equiv 7 (mod 12)

. Here

q = 12

φ (12) = φ (4) φ (3) = 2 \cdot 2 = 4

, and

g cd (7, 12) = 1

so the class is admissible. Step 1 — Total primes.

π (1 0^{6}) = 78, 498

. Step 2 — Equidistribution prediction. By PNT for progressions [6], each of the

4

admissible classes (

1, 5, 7, 11 mod 12

) should hold

\approx π (1 0^{6}) /4

π (1 0^{6}; 12, 7) \approx \frac{78 , 498}{4} = 19, 624.5.

Step 3 — Compare to actual count. The true value is

π (1 0^{6}; 12, 7) = 19, 617

— within

0.04%

of prediction, illustrating tight equidistribution. (Small "Chebyshev bias" effects favor non-quadratic-residue classes, a subtler second-order phenomenon.)

π (1 0^{6}; 12, 7) \approx \frac{1}{φ ( 12 )} π (1 0^{6}) \approx 19, 625 (actual 19, 617)

Common Misconceptions

" $π (x) \sim x / ln x$ means $π (x) - x / ln x \to 0$ ." False. Asymptotic equivalence

f \sim g

means

f / g \to 1

, not

f - g \to 0

. In fact

π (x) - x / ln x \to + \infty

— the difference grows roughly like

x / ln^{2} x

. " $Li (x)$ always overestimates $π (x)$ ." Numerically true for all tested

x

, but false in principle: Littlewood (1914) proved

π (x) - Li (x)

changes sign infinitely often. The first sign change occurs below Skewes' number, an astronomically large bound, never yet reached by computation. "Dirichlet's theorem needs the Riemann Hypothesis." No — it only needs

L (1, χ) \neq = 0

, an unconditional fact. RH (and GRH) only sharpen the error terms, not existence. "Primes are equally likely in all residue classes mod $q$ ." Only among the

φ (q)

coprime classes. Classes with

g cd (a, q) > 1

contain at most one prime. And even among coprime classes, the Chebyshev bias gives a slight, persistent preference for quadratic non-residues. Non-admissible progression. The progression

a = 6, q = 9

has

g cd (6, 9) = 3

, so every term

6, 15, 24, \dots

is divisible by

3

— it contains no primes at all (beyond none). Dirichlet's hypothesis

g cd (a, q) = 1

is essential; dropping it destroys the conclusion entirely. Failure without non-vanishing. If one hypothetically allowed

L (1, χ) = 0

for some real

χ

, the proof of [13] collapses: the bounded character terms could cancel the principal-term divergence, and one could not conclude infinitely many primes in the class. This is exactly why the real-character case (handled via the class number formula) is the linchpin of the entire theorem.

Connections

The PNT and Dirichlet's theorem sit at the confluence of several frameworks. The Euler product ties them to Unique Factorization and the multiplicative structure of $Z$ . The analytic engine is the Riemann Zeta Function and its generalization to Dirichlet L-functions, both special cases of Automorphic L-functions in the Langlands program. The non-vanishing arguments belong to the broader theory of Tauberian Theorems (Wiener–Ikehara, Newman). The error term in [5] is governed by Zero-Free Regions, whose conjectural optimum is the Riemann Hypothesis; for progressions the analogue is the Generalized Riemann Hypothesis. Equidistribution links to Chebotarev Density Theorem (the Galois-theoretic generalization where Dirichlet's theorem is the abelian case over $Q$ ). Sieve-theoretic refinements connect to the Bombieri–Vinogradov Theorem, which gives GRH-quality average control unconditionally.

Real-World Applications

RSA and public-key cryptography. Generating an $n$ -bit prime relies on PNT: the density $\approx 1/ ln (2^{n}) = 1/ (n ln 2)$ predicts that random odd candidates are prime with calculable probability, so primality testing needs only $O (n)$ trials on average.
Cryptographic key distribution. Dirichlet's theorem assures that primes of special forms (e.g. $p \equiv 3 (mod 4)$ for Blum integers, or safe primes $p = 2 q + 1$ ) exist in abundance, underpinning Rabin and Diffie–Hellman parameter selection.
Hash table and pseudorandom design. Choosing prime moduli in well-distributed residue classes (informed by equidistribution) minimizes collision clustering.
Riemann Hypothesis-driven complexity bounds. Deterministic primality (AKS) and discrete-log algorithm analyses use PNT-type prime densities to bound search ranges.
Random matrix theory / quantum chaos. The pair-correlation of zeta zeros (Montgomery–Odlyzko) matches eigenvalue statistics of the GUE ensemble, connecting prime distribution to physics of disordered/chaotic quantum systems.
Coding theory. Constructing BCH and Reed–Solomon codes over $F_{q}$ requires primes/prime powers in given ranges; PNT estimates feasibility.
Numerical analysis of $L$ -functions. Sieving and computing $π (x; q, a)$ to verify GRH numerically and to test the Chebyshev bias relies on the equidistribution baseline.

Historical Development

1792–1796: Gauss, as a teenager, conjectures from prime tables that the density of primes near $x$ is $\sim 1/ ln x$ , equivalently $π (x) \approx Li (x)$ (recorded in letters; published 1849).
1798: Legendre publishes the empirical formula $π (x) \approx x / (ln x - 1.08366)$ .
1837: Dirichlet proves infinitely many primes in coprime progressions, inventing Dirichlet characters and $L$ -functions — the birth of analytic number theory. His proof of $L (1, χ) \neq = 0$ uses the class number formula.
1848–1852: Chebyshev proves $0.92 x / ln x < π (x) < 1.11 x / ln x$ and introduces $ψ, θ$ ; establishes Bertrand's postulate.
1859: Riemann's memoir introduces the analytic continuation, functional equation, explicit formula, and the Riemann Hypothesis — laying every conceptual tool for PNT.
1896: Hadamard and de la Vallée Poussin independently prove PNT, each establishing $ζ (1 + i t) \neq = 0$ ; de la Vallée Poussin also gives the first zero-free region and error term, and PNT for arithmetic progressions.
1914: Littlewood proves $π (x) - Li (x)$ changes sign infinitely often, overturning the empirical belief that $Li$ always overestimates.
1948–1949: Selberg and Erdős give an elementary (zeta-free) proof of PNT via Selberg's symmetry formula, sparking a famous priority dispute.
1980: Newman publishes a short, clean Tauberian contour proof, now standard in textbooks.

Subtleties & Limits

The Riemann Hypothesis (RH) asserts every nontrivial zero of

ζ

has

Re (s) = 1/2

. It is equivalent to the optimal error

π (x) = Li (x) + O (x ln x)

— and remains unproven, a Clay Millennium Problem. The Generalized RH (GRH) extends this to all Dirichlet

L

-functions, controlling

π (x; q, a)

uniformly. Uniformity in $q$ (the deep frontier). PNT for progressions [6] is known to hold with good error only for

q

small relative to

x

. The Siegel–Walfisz theorem gives uniformity for

q \leq (ln x)^{A}

but with an ineffective constant, because of the possible existence of Siegel zeros — exceptional real zeros of

L (s, χ)

extremely close to

s = 1

for real

χ

. No one has ruled out Siegel zeros; their hypothetical existence would not contradict known theorems but would distort prime distribution and is the single most stubborn obstruction to effective bounds. Chebyshev's bias. Numerically,

π (x; q, a)

for

a

a quadratic non-residue tends to exceed that for residues. Rubinstein–Sarnak (1994) showed this bias has a precise meaning under GRH plus a linear independence hypothesis on zeros — but it remains conditional. Largest known prime gaps and Cramér's model. PNT controls averages, not individual gaps; the maximal gap below

x

is conjectured (Cramér) to be

O (ln^{2} x)

, far beyond current proof.