Định lý số nguyên tố

Trước chứng minh giải tích năm 1896 của Hadamard và de la Vallée Poussin, Chebyshev (1852) đã sơ cấp chứng minh, chỉ dùng hệ số nhị thức, rằng số lượng số nguyên tố bị kẹp trong một hằng số nhân của x/log x. Chặn này là thành phần sơ cấp then chốt, đầu vào sau này cho mọi chứng minh của định lý đầy đủ, và mẹo hệ số nhị thức chính giữa chính là mẹo đứng sau chứng minh sơ cấp nổi tiếng của Erdős cho định đề Bertrand.

Ta dùng quy nạp mạnh theo $n$. Trường hợp cơ sở $n=1,2$ hiển nhiên: $\theta(1)=0$ và $\theta(2)=\log 2 < \log 4$.

Với bước quy nạp, giả sử chặn đúng với mọi số nguyên dương nhỏ hơn $n$. Nếu $n>2$ chẵn, $n$ không nguyên tố, nên $\theta(n)=\theta(n-1) < (\log4)(n-1) < (\log4)n$ theo giả thiết quy nạp áp dụng cho $n-1$.

Nếu $n=2m+1$ lẻ, xét hệ số $\binom{2m+1}{m}=\dfrac{(2m+1)!}{m!\,(m+1)!}$. Nó xuất hiện hai lần trong $2^{2m+1}$ số hạng của khai triển nhị thức $(1+1)^{2m+1}$ (một lần là $\binom{2m+1}{m}$, một lần là $\binom{2m+1}{m+1}$, và chúng bằng nhau), nên $2\binom{2m+1}{m} \le 2^{2m+1}$, cho $\binom{2m+1}{m} \le 4^m$.

Mọi số nguyên tố $p$ với $m+1 < p \le 2m+1$ chia hết tử số $(2m+1)!$ nhưng không chia hết $m!$ lẫn $(m+1)!$ (vì $p>m+1$), nên $p$ chia hết $\binom{2m+1}{m}$. Do đó tích mọi số nguyên tố như vậy chia hết $\binom{2m+1}{m}$, nên $\prod_{m+1<p\le 2m+1} p \le \binom{2m+1}{m} \le 4^m$, tức $\theta(2m+1)-\theta(m+1) \le (\log 4)\,m$.

Theo giả thiết quy nạp áp dụng cho $m+1<n$, $\theta(m+1) < (\log4)(m+1)$. Cộng lại, $\theta(n)=\theta(2m+1) < (\log4)(m+1) + (\log4)m = (\log4)(2m+1) = (\log4)n$, hoàn tất quy nạp.

Chặn Chebyshev ở trên kẹp π(x) trong một hằng số nhân của x/log x, nhưng "tiệm cận với" là một khẳng định mạnh hơn nhiều: tỉ số π(x)/(x/log x) phải tiến chính xác tới 1, không chỉ bị chặn. Việc thu hẹp khoảng cách đó từ "bị chặn" xuống "chính xác bằng 1" cần một ý tưởng hoàn toàn khác — nhận thức năm 1859 của Riemann rằng sự phân bố số nguyên tố được mã hóa trong các không điểm phức của hàm zeta ζ(s).

Chứng minh này là một bản phác thảo lô-gic của con đường giải tích, không phải một suy diễn tự chứa — nó cần giải tích phức được giới thiệu sau này trong chương trình (xem chủ đề hàm zeta Riemann để biết chi tiết). Lập luận có ba giai đoạn.

Giai đoạn 1 (quy về θ): một lập luận tổng từng phần quen thuộc cho thấy $\pi(x) \sim x/\log x$ tương đương $\theta(x) \sim x$, với $\theta(x)=\sum_{p\le x}\log p$ như trong chặn Chebyshev ở trên.

Giai đoạn 2 (mã hóa θ qua ζ): công thức tường minh của Riemann biểu diễn $\theta(x)$ (chính xác hơn là $\psi(x)=\sum_{p^k\le x}\log p$ gần gũi) gần như chính xác qua các không điểm của $\zeta(s)=\sum_n n^{-s}=\prod_p(1-p^{-s})^{-1}$: số hạng chính $x$ đến từ cực đơn của $\zeta$ tại $s=1$, và mỗi không điểm $\rho=\beta+i\gamma$ của $\zeta$ đóng góp một số hạng sai số dao động cỡ $x^{\beta}$.

Giai đoạn 3 (sự kiện không triệt tiêu then chốt): $\psi(x)\sim x$ — và do đó định lý — đúng khi và chỉ khi không không điểm nào có $\beta=1$, tức $\zeta(1+it) \ne 0 \text{ for all } t \in \mathbb{R}$. Hadamard và de la Vallée Poussin chứng minh sự không triệt tiêu này độc lập vào năm 1896, dùng một bất đẳng thức lượng giác sơ cấp ($3+4\cos\theta+\cos2\theta\ge0$) áp dụng cho $\log|\zeta(\sigma)^3\zeta(\sigma+it)^4\zeta(\sigma+2it)|$ khi $\sigma\to1^+$: một không điểm tại $1+it$ sẽ buộc biểu thức này về $-\infty$, điều bất đẳng thức cấm. Chứng minh năm 1980 của Newman rút gọn hệ quả của Giai đoạn 3 thành một lập luận Tauberian ngắn gọn, nhưng khung lô-gic — cực tại $1$, không điểm ở nơi khác, không triệt tiêu trên đường $\operatorname{Re}(s)=1$ — chính xác như Riemann và Hadamard đã đặt ra.