Analytic number theory · The Lumenary

Lens

MotivationH

How many primes are there below a million?

Euclid proved that the primes never run out. But how thinly are they spread? Around 1792, the teenage Carl Friedrich Gauss counted the primes in blocks of a thousand from tables and observed that near $x$ about one number in $\log x$ is prime (natural logarithm). So the number of primes up to $x$ should be roughly

\pi(x) \approx \frac{x}{\log x} \qquad\text{or, better,}\qquad \pi(x) \approx \operatorname{li}(x) = \int_0^x \frac{dt}{\log t}.

For $x = 10^6$ : $\pi(x) = 78498$ , $x/\log x \approx 72382$ , and $\operatorname{li}(x) \approx 78628$ . Proving that $\pi(x)/(x/\log x) \to 1$ — the prime number theorem — took a century and a new idea: Bernhard Riemann's 1859 memoir, which studied the primes through the complex function

\zeta(s) = \sum_{n=1}^\infty \frac{1}{n^s} = \prod_{p} \frac{1}{1 - p^{-s}} \qquad (\operatorname{Re} s > 1),

and showed that the distribution of primes is governed by the zeros of $\zeta$ . The theorem was proved in 1896 by Jacques Hadamard and Charles de la Vallée Poussin. Riemann also conjectured that all the non-trivial zeros lie on the line $\operatorname{Re} s = \tfrac12$ ; this Riemann hypothesis is still open, and it is equivalent to the statement that $\pi(x) = \operatorname{li}(x) + O(\sqrt x \log x)$ — the primes are as regular as they could possibly be.

Analytic number theory answers arithmetic questions with analysis: generating functions (Dirichlet series), complex integration, Fourier analysis and estimates. This lesson assumes elementary number theory and complex analysis (holomorphic functions, analytic continuation, the residue theorem).

IntuitionH

Three ideas

Unique factorisation is an Euler product. Expanding $\prod_p (1 + p^{-s} + p^{-2s} + \cdots)$ produces each $n^{-s}$ exactly once, because each $n$ factors uniquely into primes. So the analytic properties of $\zeta(s)$ — a pole at $s = 1$ , where $\sum 1/n$ diverges — say something about primes: there must be infinitely many, and $\sum_p 1/p$ must diverge.
Logarithmic derivatives count primes. Taking $-\frac{d}{ds}\log$ of the Euler product gives $-\zeta'(s)/\zeta(s) = \sum_n \Lambda(n) n^{-s}$ , where $\Lambda(n) = \log p$ if $n = p^k$ and $0$ otherwise. The poles of $-\zeta'/\zeta$ are the pole and the zeros of $\zeta$ , and complex integration (Perron's formula) turns them into terms of $\psi(x) = \sum_{n \leq x}\Lambda(n)$ : the pole at $s = 1$ gives the main term $x$ , and each zero $\rho$ gives a term $-x^\rho/\rho$ .
Zeros are frequencies. If $\rho = \beta + i\gamma$ , then $x^\rho = x^\beta e^{i\gamma\log x}$ oscillates in $\log x$ with frequency $\gamma$ and amplitude $x^\beta$ . The primes are the "sound" and the zeros its "spectrum" (an analogy; the precise statement is von Mangoldt's explicit formula, Theorem 9). Zeros with $\beta = 1$ would destroy the prime number theorem; zeros with $\beta = \frac12$ give the smallest possible error terms.

A heuristic that gets many predictions right is Cramér's model: pretend each $n \geq 3$ is prime independently with probability $1/\log n$ . It predicts $\pi(x) \approx \operatorname{li}(x)$ with fluctuations of size about $\sqrt x$ (up to logarithms) — consistent with the Riemann hypothesis. It is a model, not a theorem, and it is known to be wrong in some details (Maier, 1985).

DefinitionsH

Definitions

Definition— arithmetic functions and Dirichlet convolution

An arithmetic function is a map $f : \N_{\geq 1} \to \C$ . The Dirichlet convolution is $(f * g)(n) = \sum_{d \mid n} f(d)\, g(n/d)$ . The function $f$ is multiplicative if $f(mn) = f(m)f(n)$ whenever $\gcd(m, n) = 1$ (and $f(1) = 1$ ), and completely multiplicative if this holds for all $m, n$ . Important examples: $\varepsilon(n) = [n = 1]$ (the identity for $*$ ), $\mathbf{1}(n) = 1$ , $\operatorname{id}(n) = n$ , $\log(n)$ , Euler's $\varphi$ , the divisor function $d = \mathbf{1} * \mathbf{1}$ , the Möbius function $\mu(n) = (-1)^k$ if $n$ is a product of $k$ distinct primes and $\mu(n) = 0$ if $n$ has a square factor, and the von Mangoldt function $\Lambda(n) = \log p$ if $n = p^k$ ( $k \geq 1$ ) and $0$ otherwise.

Definition— Dirichlet series

The Dirichlet series of $f$ is $D(f, s) = \sum_{n \geq 1} f(n)\, n^{-s}$ , $s = \sigma + it$ . If it converges absolutely at $s_0$ , it converges absolutely and uniformly on $\operatorname{Re} s \geq \operatorname{Re} s_0$ and defines a holomorphic function on $\operatorname{Re} s > \operatorname{Re} s_0$ . The Riemann zeta function is $\zeta(s) = D(\mathbf{1}, s)$ for $\operatorname{Re} s > 1$ .

Definition— prime-counting functions

$\pi(x) = \#\{p \leq x\}$ , $\theta(x) = \sum_{p \leq x}\log p$ , $\psi(x) = \sum_{n \leq x}\Lambda(n) = \sum_{p^k \leq x}\log p$ , and $\operatorname{li}(x) = \int_0^x dt/\log t$ (principal value at $t = 1$ ). We write $f \sim g$ if $f/g \to 1$ , $f = O(g)$ or $f \ll g$ if $|f| \leq Cg$ for some constant $C$ , and $f \asymp g$ if $f \ll g \ll f$ .

Definition— Dirichlet characters and L-functions

A Dirichlet character modulo $q$ is a homomorphism $\chi : (\Z/q\Z)^\times \to \C^\times$ , extended to $\Z$ by $\chi(n) = \chi(n \bmod q)$ if $\gcd(n, q) = 1$ and $\chi(n) = 0$ otherwise. It is completely multiplicative and periodic. The principal character $\chi_0$ is $1$ on all $n$ coprime to $q$ ; there are $\varphi(q)$ characters modulo $q$ . The Dirichlet $L$ -function is $L(s, \chi) = \sum_n \chi(n) n^{-s} = \prod_p (1 - \chi(p)p^{-s})^{-1}$ for $\operatorname{Re} s > 1$ .

Worked examplesH

Examples

Example— Dirichlet series of familiar functions

For $\operatorname{Re} s > 1$ (or $> 2$ where noted), Proposition 2 below gives

\sum_n \frac{\mu(n)}{n^s} = \frac{1}{\zeta(s)}, \qquad \sum_n \frac{d(n)}{n^s} = \zeta(s)^2, \qquad \sum_n \frac{\varphi(n)}{n^s} = \frac{\zeta(s - 1)}{\zeta(s)}\ (\operatorname{Re} s > 2), \qquad \sum_n \frac{\Lambda(n)}{n^s} = -\frac{\zeta'(s)}{\zeta(s)},

from the convolution identities $\mu * \mathbf{1} = \varepsilon$ , $d = \mathbf{1} * \mathbf{1}$ , $\varphi * \mathbf{1} = \operatorname{id}$ and $\Lambda * \mathbf{1} = \log$ (formalised below). For instance $\Lambda * \mathbf{1} = \log$ says $\sum_{d \mid 12}\Lambda(d) = \Lambda(2) + \Lambda(3) + \Lambda(4) = 2\log 2 + \log 3 = \log 12$ .

Example— Characters modulo 4 and modulo 5

Modulo $4$ there are two characters: $\chi_0$ and $\chi_4$ with $\chi_4(1) = 1$ , $\chi_4(3) = -1$ . Then

L(1, \chi_4) = 1 - \frac13 + \frac15 - \frac17 + \cdots = \frac{\pi}{4},

the series of Mādhava and Leibniz. Modulo $5$ , $(\Z/5)^\times$ is cyclic of order $4$ , generated by $2$ , and a character is determined by $\chi(2) \in \{1, i, -1, -i\}$ : two characters are real ( $\chi_0$ and the Legendre symbol $\left(\frac{\cdot}{5}\right)$ ) and two are complex conjugates.

$n \bmod 5$	$1$	$2$	$3$	$4$
$\chi_0$	$1$	$1$	$1$	$1$
$\chi_1$	$1$	$i$	$-i$	$-1$
$\chi_2 = \left(\frac{\cdot}{5}\right)$	$1$	$-1$	$-1$	$1$
$\chi_3 = \overline{\chi_1}$	$1$	$-i$	$i$	$-1$

Example— Special values of ζ

Euler showed $\zeta(2) = \pi^2/6$ (the Basel problem, 1734) and more generally $\zeta(2k) = (-1)^{k+1}B_{2k}(2\pi)^{2k}/(2(2k)!)$ with Bernoulli numbers $B_{2k}$ . The continued function also has values at negative integers: $\zeta(0) = -\tfrac12$ , $\zeta(-1) = -\tfrac{1}{12}$ , and $\zeta(-2k) = 0$ for $k \geq 1$ (the trivial zeros). These are values of the analytic continuation — the series $\sum n^{-s}$ diverges for $\operatorname{Re} s \leq 1$ . The first non-trivial zero is $\rho_1 = \tfrac12 + 14.134725\ldots\, i$ .

ProofH

The main theorems

Theorem— Proposition 1 (the ring of arithmetic functions; Möbius inversion)

Under pointwise addition and Dirichlet convolution, arithmetic functions form a commutative ring with identity $\varepsilon$ ; $f$ is invertible if and only if $f(1) \neq 0$ . Convolutions of multiplicative functions are multiplicative. Moreover $\mu * \mathbf{1} = \varepsilon$ , that is, $\sum_{d \mid n}\mu(d) = 0$ for $n > 1$ , and consequently

g(n) = \sum_{d \mid n} f(d) \ \text{ for all } n \quad\Longleftrightarrow\quad f(n) = \sum_{d \mid n}\mu(d)\, g(n/d) \ \text{ for all } n.

Proof

Commutativity and associativity follow from writing $(f * g)(n) = \sum_{ab = n} f(a)g(b)$ and $((f * g) * h)(n) = \sum_{abc = n} f(a)g(b)h(c)$ ; distributivity and $f * \varepsilon = f$ are immediate. If $f(1) \neq 0$ , the equations $(f * g)(1) = 1$ and $(f * g)(n) = 0$ for $n > 1$ determine $g(1) = 1/f(1)$ and then, recursively, $g(n) = -\frac{1}{f(1)}\sum_{d \mid n, d > 1} f(d)g(n/d)$ . If $\gcd(m, n) = 1$ , divisors of $mn$ are uniquely products $d_1 d_2$ with $d_1 \mid m$ , $d_2 \mid n$ , which gives multiplicativity of $f * g$ . Since $\mu * \mathbf{1}$ is multiplicative, it suffices to check prime powers: $\sum_{d \mid p^k}\mu(d) = 1 - 1 + 0 + \cdots = 0$ for $k \geq 1$ . Finally, if $g = f * \mathbf{1}$ then $g * \mu = f * (\mathbf{1} * \mu) = f * \varepsilon = f$ , and conversely if $f = g * \mu$ then $f * \mathbf{1} = g$ .

∎

Theorem— Proposition 2 (Dirichlet series multiply)

If $D(f, s)$ and $D(g, s)$ converge absolutely, then so does $D(f * g, s)$ , and $D(f * g, s) = D(f, s)\, D(g, s)$ .

Proof

$D(f, s)D(g, s) = \sum_{a, b} f(a)g(b)(ab)^{-s}$ is an absolutely convergent double series, so it may be summed in any order; grouping the terms with $ab = n$ gives $\sum_n (f * g)(n) n^{-s}$ , and the same grouping of $\sum|f(a)||g(b)||(ab)^{-s}|$ bounds $\sum_n |(f * g)(n)||n^{-s}|$ .

∎

Theorem— Theorem 3 (Euler product; Euler's theorem on Σ 1/p)

For $\operatorname{Re} s > 1$ , $\zeta(s) = \prod_p (1 - p^{-s})^{-1}$ , the product converging absolutely; in particular $\zeta(s) \neq 0$ there. More generally $D(f, s) = \prod_p \big(\sum_{k \geq 0} f(p^k)p^{-ks}\big)$ for multiplicative $f$ with $D(|f|, \sigma)$ convergent. Consequently $\sum_p 1/p = \infty$ , and there are infinitely many primes.

Proof

Fix $s$ with $\sigma = \operatorname{Re} s > 1$ and let $P(N) = \prod_{p \leq N}(1 - p^{-s})^{-1} = \prod_{p \leq N}\sum_{k \geq 0} p^{-ks}$ . Multiplying out finitely many absolutely convergent series, $P(N) = \sum_{n \in S_N} n^{-s}$ where $S_N$ is the set of $n$ all of whose prime factors are $\leq N$ — each such $n$ appears exactly once by unique factorisation. Every $n \leq N$ is in $S_N$ , so $|\zeta(s) - P(N)| \leq \sum_{n > N} n^{-\sigma} \to 0$ . The product converges absolutely because $\sum_p |p^{-s}| < \infty$ , and a convergent product of non-zero factors with this property is non-zero. The same argument works for multiplicative $f$ .

For the divergence, let $1 < \sigma < 2$ . Taking logarithms, $\log\zeta(\sigma) = \sum_p \sum_{k \geq 1}\frac{p^{-k\sigma}}{k} = \sum_p p^{-\sigma} + R(\sigma)$ , where $0 \leq R(\sigma) \leq \sum_p \sum_{k \geq 2} p^{-k} = \sum_p \frac{1}{p(p - 1)} < 1$ . Since $\zeta(\sigma) \geq \int_1^\infty x^{-\sigma}\,dx = \frac{1}{\sigma - 1} \to \infty$ as $\sigma \to 1^+$ , $\sum_p p^{-\sigma}$ is unbounded, so $\sum_p p^{-1} = \infty$ by monotone convergence.

∎

Differentiating the logarithm of the Euler product termwise gives $-\zeta'(s)/\zeta(s) = \sum_p \sum_k (\log p)\, p^{-ks} = \sum_n \Lambda(n) n^{-s}$ , matching $\Lambda * \mathbf{1} = \log$ and Proposition 2.

Theorem— Theorem 4 (Chebyshev's bounds)

For all $x \geq 1$ and integers $n \geq 1$ :

$\prod_{p \leq n} p \leq 4^n$ , hence $\theta(x) \leq x\log 4$ ;
$2^n \leq (n + 1)\operatorname{lcm}(1, 2, \dots, n)$ , hence $\psi(n) \geq n\log 2 - \log(n + 1)$ .

Consequently $\psi(x) \asymp x$ , $\theta(x) \asymp x$ and $\pi(x) \asymp x/\log x$ .

Proof

(1) Induction on $n$ (Erdős's argument). For $n \leq 2$ it is clear; for even $n > 2$ the product equals that for $n - 1$ . For $n = 2m + 1$ : every prime $p$ with $m + 1 < p \leq 2m + 1$ divides $\binom{2m+1}{m} = \frac{(2m+1)!}{m!\,(m+1)!}$ (it divides the numerator but not the denominator), and $\binom{2m+1}{m} = \binom{2m+1}{m+1}$ are two terms of $\sum_j\binom{2m+1}{j} = 2^{2m+1}$ , so $\binom{2m+1}{m} \leq 4^m$ . Hence $\prod_{p \leq 2m+1} p \leq \prod_{p \leq m+1}p \cdot \binom{2m+1}{m} \leq 4^{m+1}\cdot 4^m = 4^{2m+1}$ . Taking logarithms gives $\theta(n) \leq n\log 4$ , and $\theta(x) = \theta(\lfloor x \rfloor)$ .

(2) The exponent of a prime $p$ in $\operatorname{lcm}(1, \dots, n)$ is the largest $k$ with $p^k \leq n$ , so $\log\operatorname{lcm}(1, \dots, n) = \sum_{p^k \leq n}\log p = \psi(n)$ . Each binomial coefficient $\binom{n}{j}$ divides $\operatorname{lcm}(1, \dots, n)$ : by Kummer's theorem the exponent of $p$ in $\binom{n}{j}$ is the number of carries when adding $j$ and $n - j$ in base $p$ , which is at most the number of base- $p$ digits of $n$ beyond the first, i.e. at most $\lfloor\log n/\log p\rfloor$ . So $2^n = \sum_{j=0}^n \binom{n}{j} \leq (n + 1)\operatorname{lcm}(1, \dots, n)$ ; take logarithms.

For the consequences: $\theta \leq \psi$ , and $\psi(x) - \theta(x) = \sum_{k \geq 2}\theta(x^{1/k}) \ll \sqrt x\log x$ (there are at most $\log_2 x$ non-zero terms, each $\leq \theta(\sqrt x) \leq \sqrt x\log 4$ ), so both are $\asymp x$ . Then $\pi(x) \geq \theta(x)/\log x \gg x/\log x$ , and $\theta(x) \geq \sum_{\sqrt x < p \leq x}\log p \geq \frac12\log x\,(\pi(x) - \sqrt x)$ gives $\pi(x) \ll x/\log x$ .

∎

Theorem— Theorem 5 (analytic continuation to Re s > 0)

For $\operatorname{Re} s > 1$ ,

\zeta(s) = \frac{s}{s - 1} - s\int_1^\infty \frac{\{x\}}{x^{s+1}}\,dx,

where $\{x\} = x - \lfloor x \rfloor$ . The right-hand side is meromorphic on $\operatorname{Re} s > 0$ with a single simple pole, at $s = 1$ , of residue $1$ . So $\zeta$ continues meromorphically to $\operatorname{Re} s > 0$ , and $\zeta(s) - \frac{1}{s - 1}$ is holomorphic there.

Proof

For $\operatorname{Re} s > 1$ , partial summation gives

\sum_{n \geq 1} n^{-s} = \sum_{n \geq 1} n\big(n^{-s} - (n + 1)^{-s}\big) = \sum_{n \geq 1} n \cdot s\int_n^{n+1} x^{-s-1}\,dx = s\int_1^\infty \lfloor x \rfloor x^{-s-1}\,dx,

(the boundary terms $N\cdot(N+1)^{-s} \to 0$ ). Writing $\lfloor x \rfloor = x - \{x\}$ and $s\int_1^\infty x^{-s}\,dx = \frac{s}{s - 1}$ gives the formula. Since $0 \leq \{x\} < 1$ , the integral converges absolutely and locally uniformly on $\operatorname{Re} s > 0$ , so it is holomorphic there. Finally $\frac{s}{s - 1} = 1 + \frac{1}{s - 1}$ .

∎

Theorem— Theorem 6 (the functional equation; proof sketched)

The completed zeta function $\Lambda(s) = \pi^{-s/2}\,\Gamma(s/2)\,\zeta(s)$ extends to a meromorphic function on $\C$ whose only poles are simple poles at $s = 0$ and $s = 1$ , and

\Lambda(1 - s) = \Lambda(s).

Hence $\zeta$ is meromorphic on $\C$ with a single simple pole at $s = 1$ ; $\zeta(-2k) = 0$ for $k = 1, 2, \dots$ (the poles of $\Gamma(s/2)$ must cancel); and all other zeros — the non-trivial zeros — lie in the critical strip $0 \leq \operatorname{Re} s \leq 1$ , symmetric about the real axis and about the critical line $\operatorname{Re} s = \tfrac12$ .

Proof sketch (Riemann's second proof). Let $\vartheta(t) = \sum_{n \in \Z} e^{-\pi n^2 t}$ for $t > 0$ . Poisson summation applied to the Gaussian $e^{-\pi x^2 t}$ , whose Fourier transform is $t^{-1/2}e^{-\pi \xi^2/t}$ , gives $\vartheta(1/t) = \sqrt{t}\,\vartheta(t)$ . For $\operatorname{Re} s > 1$ , $\int_0^\infty e^{-\pi n^2 t}t^{s/2}\,\frac{dt}{t} = \pi^{-s/2}\Gamma(s/2)n^{-s}$ , so $\Lambda(s) = \int_0^\infty \frac{\vartheta(t) - 1}{2}\,t^{s/2}\,\frac{dt}{t}$ . Splitting the integral at $t = 1$ and using $\vartheta(1/t) = \sqrt t\,\vartheta(t)$ on $(0, 1)$ gives

\Lambda(s) = -\frac{1}{s} - \frac{1}{1 - s} + \int_1^\infty \frac{\vartheta(t) - 1}{2}\left(t^{s/2} + t^{(1-s)/2}\right)\frac{dt}{t},

in which the integral is entire (the integrand decays like $e^{-\pi t}$ ) and the whole expression is visibly symmetric under $s \mapsto 1 - s$ . Zeros of $\zeta$ in $\operatorname{Re} s < 0$ come from poles of $\Gamma(s/2)$ only, and $\zeta \neq 0$ on $\operatorname{Re} s > 1$ (Theorem 3), so by symmetry the non-trivial zeros lie in $0 \leq \operatorname{Re} s \leq 1$ . Details: Davenport, Chapter 8; Titchmarsh, Chapter II. Mathlib proves the functional equation (below). $\square$

Theorem— Theorem 7 (no zeros on the line Re s = 1)

$\zeta(1 + it) \neq 0$ for every real $t$ .

Proof

At $t = 0$ there is a pole. For $\sigma > 1$ , the Euler product gives $\log\zeta(s) = \sum_p\sum_{k \geq 1}\frac{p^{-ks}}{k} = \sum_{n \geq 2}\frac{\Lambda(n)}{\log n}n^{-s}$ , so

\log|\zeta(\sigma + it)| = \operatorname{Re}\log\zeta(\sigma + it) = \sum_{n \geq 2}\frac{\Lambda(n)}{\log n}\,n^{-\sigma}\cos(t\log n).

Therefore, with $\theta_n = t\log n$ ,

\log\left|\zeta(\sigma)^3\,\zeta(\sigma + it)^4\,\zeta(\sigma + 2it)\right| = \sum_{n \geq 2}\frac{\Lambda(n)}{\log n}\,n^{-\sigma}\big(3 + 4\cos\theta_n + \cos 2\theta_n\big) \geq 0,

because $3 + 4\cos\theta + \cos 2\theta = 2(1 + \cos\theta)^2 \geq 0$ (Mertens' trick, formalised below). So $|\zeta(\sigma)^3\zeta(\sigma + it)^4\zeta(\sigma + 2it)| \geq 1$ for all $\sigma > 1$ .

Suppose $\zeta(1 + it) = 0$ with $t \neq 0$ . As $\sigma \to 1^+$ : $\zeta(\sigma)^3 \sim (\sigma - 1)^{-3}$ (simple pole of residue $1$ , Theorem 5); $\zeta(\sigma + it)^4 = O\big((\sigma - 1)^4\big)$ (a zero at $1 + it$ , and $\zeta$ is holomorphic there); and $\zeta(\sigma + 2it)$ stays bounded, because $\zeta$ is holomorphic at $1 + 2it \neq 1$ . So the product is $O(\sigma - 1) \to 0$ , contradicting the lower bound $1$ .

∎

Theorem— Theorem 8 (the prime number theorem; proof outlined)

\psi(x) \sim x, \qquad \theta(x) \sim x, \qquad \pi(x) \sim \frac{x}{\log x} \sim \operatorname{li}(x).

Outline of a proof (D. J. Newman's, as presented by Zagier, 1997).

$\theta(x) = O(x)$ — Theorem 4.
The function $\Phi(s) = \sum_p (\log p)\,p^{-s}$ differs from $-\zeta'(s)/\zeta(s)$ by $\sum_p \frac{(\log p)\, p^{-s}}{p^s - 1}$ , which is holomorphic for $\operatorname{Re} s > \frac12$ . By Theorems 5 and 7, $-\zeta'/\zeta$ has a simple pole with residue $1$ at $s = 1$ and no other poles on $\operatorname{Re} s \geq 1$ . So $\Phi(s) - \frac{1}{s - 1}$ extends holomorphically to a neighbourhood of $\operatorname{Re} s \geq 1$ .
Newman's analytic theorem: if $f$ is bounded and locally integrable on $[0, \infty)$ and its Laplace transform $g(z) = \int_0^\infty f(t)e^{-zt}\,dt$ extends holomorphically to a neighbourhood of $\operatorname{Re} z \geq 0$ , then $\int_0^\infty f(t)\,dt$ converges (and equals $g(0)$ ). The proof is a single clever contour integral.
Apply it to $f(t) = \theta(e^t)e^{-t} - 1$ , bounded by step 1, whose Laplace transform is $\frac{\Phi(z + 1)}{z + 1} - \frac{1}{z}$ , holomorphic on $\operatorname{Re} z \geq 0$ by step 2. So $\int_1^\infty \frac{\theta(x) - x}{x^2}\,dx$ converges.
If $\theta(x) \geq \lambda x$ for some $\lambda > 1$ and arbitrarily large $x$ , then since $\theta$ is increasing, $\int_x^{\lambda x}\frac{\theta(t) - t}{t^2}\,dt \geq \int_1^\lambda \frac{\lambda - u}{u^2}\,du > 0$ for those $x$ , contradicting convergence; similarly for $\lambda < 1$ . So $\theta(x) \sim x$ .
Partial summation: $\pi(x) = \frac{\theta(x)}{\log x} + \int_2^x \frac{\theta(t)}{t\log^2 t}\,dt$ , and the integral is $O(x/\log^2 x)$ , so $\pi(x) \sim x/\log x$ ; also $\operatorname{li}(x) \sim x/\log x$ by L'Hôpital.

Complete proof: Zagier, Newman's short proof of the prime number theorem, Amer. Math. Monthly 104 (1997). The classical proofs use the zero-free region $\sigma > 1 - c/\log(|t| + 2)$ (de la Vallée Poussin, 1899), which gives the error term $\psi(x) = x + O\big(x e^{-c'\sqrt{\log x}}\big)$ . $\square$

Theorem— Theorem 9 (von Mangoldt's explicit formula; stated)

For $x > 1$ not a prime power,

\psi(x) = x - \sum_\rho \frac{x^\rho}{\rho} - \log 2\pi - \frac12\log\left(1 - x^{-2}\right),

where $\rho$ runs over the non-trivial zeros of $\zeta$ with multiplicity, the sum taken as $\lim_{T \to \infty}\sum_{|\operatorname{Im}\rho| < T}$ .

This is proved by integrating $-\frac{\zeta'(s)}{\zeta(s)}\frac{x^s}{s}$ around a large rectangle and collecting residues: $x$ from the pole at $s = 1$ , $-x^\rho/\rho$ from each zero, $-\log 2\pi = -\zeta'(0)/\zeta(0)$ from $s = 0$ , and $-\frac12\log(1 - x^{-2}) = \sum_k \frac{x^{-2k}}{2k}$ from the trivial zeros (Davenport, Chapter 17). It explains everything:

If every zero has real part at most $\Theta$ , then $\psi(x) = x + O(x^\Theta\log^2 x)$ ; conversely a zero with real part $\beta$ forces errors of size $x^{\beta - \varepsilon}$ infinitely often. The prime number theorem is equivalent to "no zeros on $\operatorname{Re} s = 1$ ".
The Riemann hypothesis ( $\Theta = \frac12$ ) is equivalent to $\psi(x) = x + O(\sqrt x\log^2 x)$ , and to $\pi(x) = \operatorname{li}(x) + O(\sqrt x\log x)$ (von Koch, 1901).
Each pair of zeros $\frac12 \pm i\gamma$ contributes the wave $-2\operatorname{Re}\frac{x^\rho}{\rho} = -\frac{4\sqrt x\,\big(\cos(\gamma\log x) + 2\gamma\sin(\gamma\log x)\big)}{1 + 4\gamma^2}$ , of amplitude about $2\sqrt x/\gamma$ ; the visualisation below adds these waves one by one.

What is known and what is open. Proved: infinitely many zeros lie on the critical line (Hardy, 1914), in fact a positive proportion (Selberg, 1942), more than $40\%$ (Conrey, 1989); every zero with $0 < \operatorname{Im}\rho \leq 3 \cdot 10^{12}$ is on the line (Platt and Trudgian, 2021); $\pi(x) - \operatorname{li}(x)$ changes sign infinitely often (Littlewood, 1914). Open: the Riemann hypothesis itself; even the existence of some $\Theta < 1$ with no zeros in $\operatorname{Re} s > \Theta$ ; the twin prime conjecture; Goldbach's conjecture for even numbers.

Theorem— Theorem 10 (Dirichlet's theorem on primes in arithmetic progressions)

If $\gcd(a, q) = 1$ , there are infinitely many primes $p \equiv a \pmod q$ ; in fact $\sum_{p \equiv a \ (q)} 1/p = \infty$ .

Proof for $q = 4$ , and the general strategy. For $\sigma > 1$ and a character $\chi$ mod $q$ , the Euler product of $L(s, \chi)$ gives, as in Theorem 3,

\log L(\sigma, \chi) = \sum_p \frac{\chi(p)}{p^\sigma} + O(1) \qquad (\sigma \to 1^+).

Take $q = 4$ . For $\chi_0$ , $L(\sigma, \chi_0) = (1 - 2^{-\sigma})\zeta(\sigma) \to \infty$ , so $\sum_{p \text{ odd}} p^{-\sigma} \to \infty$ . For $\chi_4$ , the alternating series $L(\sigma, \chi_4) = 1 - 3^{-\sigma} + 5^{-\sigma} - \cdots$ converges for $\sigma > 0$ and is continuous in $\sigma$ , and $L(1, \chi_4) = \frac{\pi}{4} > 0$ , so $\log L(\sigma, \chi_4)$ stays bounded as $\sigma \to 1^+$ . Adding and subtracting,

\sum_{p \equiv 1 \ (4)}\frac{1}{p^\sigma} = \frac12\left(\sum_{p \text{ odd}}\frac{1}{p^\sigma} + \sum_p\frac{\chi_4(p)}{p^\sigma}\right) \to \infty, \qquad \sum_{p \equiv 3 \ (4)}\frac{1}{p^\sigma} = \frac12\left(\sum_{p \text{ odd}}\frac{1}{p^\sigma} - \sum_p\frac{\chi_4(p)}{p^\sigma}\right) \to \infty.

For general $q$ , the orthogonality relation $\frac{1}{\varphi(q)}\sum_\chi \overline{\chi(a)}\chi(n) = [n \equiv a \bmod q]$ (for $\gcd(a, q) = 1$ ) gives

\sum_{p \equiv a \ (q)}\frac{1}{p^\sigma} = \frac{1}{\varphi(q)}\sum_\chi \overline{\chi(a)}\log L(\sigma, \chi) + O(1).

The principal character contributes $\frac{1}{\varphi(q)}\log\frac{1}{\sigma - 1} + O(1) \to \infty$ , and the theorem follows once $L(1, \chi) \neq 0$ for every $\chi \neq \chi_0$ (each such $L(s, \chi)$ is holomorphic on $\operatorname{Re} s > 0$ by partial summation). For complex $\chi$ this follows from $\prod_\chi L(\sigma, \chi) \geq 1$ (a $3$ - $4$ - $1$ -type argument); for real $\chi$ it is the deep point, proved by Dirichlet via his class number formula ( $L(1, \chi) = \frac{\pi h}{\sqrt{|d|}}$ for imaginary quadratic characters with $|d| > 4$ , and $h \geq 1$ ). Full proof: Apostol, Chapter 7; Davenport, Chapters 1–4. Mathlib proves the theorem (below). $\square$

With more work (the zero-free region for $L$ -functions) one gets the prime number theorem for arithmetic progressions: $\pi(x; q, a) \sim \frac{1}{\varphi(q)}\frac{x}{\log x}$ — the primes are equidistributed among the $\varphi(q)$ admissible classes.

Explore

Explore: building the staircase from zeros

The plot shows the right-hand side of the explicit formula (Theorem 9) truncated to the first $N$ pairs of zeros $\frac12 \pm i\gamma_k$ , against the line $y = x$ . With $N = 0$ you see the smooth main term $x - \log 2\pi$ . Increase $N$ : every zero adds a wave of amplitude about $2\sqrt x/\gamma_k$ , and the waves conspire to build a staircase that jumps by $\log p$ at each prime power $p^k$ — at $2, 3, 4, 5, 7, 8, 9, 11, 13, \dots$ — exactly as the true $\psi(x)$ does. Seven zeros already locate the small primes; with infinitely many the staircase is exact. The second experiment computes the zeros and compares the same truncation with the true $\psi(x)$ .

ψ(x) rebuilt from the zeros of ζ

The true ψ(x) jumps by log p at every prime power pᵏ; watch the jumps appear as N grows.

explicit formula with N pairs of zeros
y = x

pairs of zeros NN = 7

Trace along xx = 1.5

explicit formula with N pairs of zeros: y = −0.0006
y = x: y = 1.5

Where the pole lives. The series $\sum n^{-p}$ converges exactly for $p > 1$ ; at $p = 1$ its partial sums grow like $\log N$ . This divergence is the pole of $\zeta(s)$ at $s = 1$ , which by Theorem 3 forces infinitely many primes. Move $p$ towards $1$ and watch the convergence slow down.

Partial sums of ζ(p) = Σ 1/nᵖ

Convergent for p > 1 (ζ(2) = π²/6 ≈ 1.645); divergent like log N at p = 1.

Examples

Term aₙ of the series

a_n =

partial sums Sₙ
terms aₙ

Partial sums up to NN = 400

pp = 1.5

S₄₀₀ = a₁ + … + a₄₀₀ = 2.512438

Partial sums on a screen are evidence, never proof: a series can look settled and still diverge, as the harmonic series does.

Formal mathematicsF

Analytic number theory in Lean and Mathlib

Mathlib has a substantial library of analytic number theory: arithmetic functions, $L$ -series, the Riemann zeta function on all of $\C$ , Chebyshev's functions and Dirichlet's theorem. We start with Proposition 1, proved by the three-line ring computation of the text, and Mathlib's version with sums:

moebius_inversionLean 4Proved here from basic factsFormally verified

/-- **Möbius inversion**, proved in the ring of arithmetic functions under Dirichlet convolution
`*`. If `g = f * ζ` — that is, `g(n) = ∑_{d ∣ n} f(d)` — then `f = g * μ`, i.e.
`f(n) = ∑_{d ∣ n} μ(d) g(n/d)`. The proof is three lines of algebra, using associativity of `*` and
the identity `ζ * μ = 1` (Mathlib: `coe_zeta_mul_moebius`), which says `∑_{d ∣ n} μ(d) = 0` for
`n > 1`. -/
theorem moebius_inversion (f g : ArithmeticFunction ℤ) (h : g = f * ζ) : f = g * μ :=
  calc f = f * 1 := (mul_one f).symm
    _ = f * ((ζ : ArithmeticFunction ℤ) * μ) := by rw [coe_zeta_mul_moebius]
    _ = (f * ζ) * μ := (mul_assoc _ _ _).symm
    _ = g * μ := by rw [h]