Engineering / Mathematics — The Distribution of Primes
The Error Term in the Prime Number Theorem
How closely li(x) approximates pi(x), the connection to zeta zeros, and what the Riemann hypothesis would give.
Executive summary
The prime number theorem fixes the leading behaviour of the prime counting function but says nothing about the error. The size of that error is controlled by the location of the zeros of the Riemann zeta function.
The Riemann hypothesis is exactly the assertion that the error is as small as it could possibly be, and it remains open.
Learning objectives
- State the known unconditional error bound.
- Relate zero-free regions to error terms.
- State what the Riemann hypothesis would give.
01The unconditional bound
Error term, unconditional
π(x) = li(x) + O(x · exp(−c · (ln x)^{3/5} (ln ln x)^{−1/5})) for some constant c > 0.
This is stronger than any power saving of the form x/(ln x)^k but far weaker than a saving of a power of x. It comes from the widest zero-free region currently known for the zeta function, due to Vinogradov and Korobov.
02Zeros and errors
The explicit formula makes the relationship exact rather than merely suggestive: the error in approximating ψ(x) by x is a sum over the non-trivial zeros of the zeta function.
ψ(x) = x − Σ_ρ x^ρ/ρ − ln(2π) − (1/2)ln(1 − x^{−2})Each zero ρ contributes a term of magnitude x^{Re(ρ)}. A zero with real part close to 1 contributes an error nearly as large as the main term; zeros with real part 1/2 contribute only √x.
| Assumption | Zero-free region | Error in π(x) |
|---|---|---|
| Prime number theorem | No zeros on Re(s) = 1 | o(x/ln x) |
| Classical | Narrow region left of Re(s) = 1 | O(x exp(−c√(ln x))) |
| Vinogradov–Korobov | Wider region | Current unconditional bound |
| Riemann hypothesis | All non-trivial zeros on Re(s) = 1/2 | O(√x ln x) |
03What the Riemann hypothesis would give
Error term under RH
If every non-trivial zero of ζ has real part 1/2, then
π(x) = li(x) + O(√x · ln x).
This is essentially best possible: the error cannot be smaller than about √x, so the hypothesis asserts the error is as small as it could conceivably be. The primes would then be as regularly distributed as a random-like sequence permits.
The computational consequences are real but narrower than sometimes suggested. Under RH, deterministic primality testing by a bounded Miller-Rabin base search becomes provably polynomial, and various algorithmic bounds sharpen. RSA and Diffie-Hellman security are unaffected — the hypothesis concerns the distribution of primes, not the difficulty of factoring.
04Frequently asked questions
Has the hypothesis been verified numerically?
Many billions of zeros have been checked and all lie on the critical line. This is strong evidence and no proof, and the Littlewood sign-change result is a reminder that numerical evidence in this area can mislead badly.
Why does the error involve x^{Re(ρ)}?
Because the explicit formula expresses the error as a sum of terms x^ρ/ρ over zeros, and the magnitude of x^ρ is x raised to the real part. The imaginary part contributes oscillation, not size.
Is there a generalised version?
Yes — the generalised Riemann hypothesis extends the claim to Dirichlet L-functions, and it is what underpins conditional bounds on the least quadratic non-residue and on deterministic primality testing.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 88-90.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.