The Prime Number Theorem already tells us that \pi(x), the count of primes up to x, is closely shadowed by the smooth logarithmic integral \operatorname{Li}(x)=\int_2^x \tfrac{dt}{\ln t}. What it does not pin down is the size of the error \pi(x)-\operatorname{Li}(x). How close can the real primes be forced to hug their smooth prediction — and could a genius one day prove an error term far smaller than anything we can currently guarantee?

There is a precise ceiling, and it has a name. The Riemann Hypothesis is exactly the statement that the primes are as regularly distributed as they possibly could be — that the error is no bigger than a shade over \sqrt{x}. This page makes that slogan into a theorem: RH is logically equivalent to the sharpest possible error in the Prime Number Theorem. Not a consequence, not a heuristic — an equivalence, provable in both directions.

Where the error comes from: the explicit formula

The engine underneath everything is the explicit formula for the Chebyshev function \psi(x)=\sum_{p^k\le x}\ln p. Von Mangoldt's exact identity reads

where the sum runs over the non-trivial zeros \rho=\beta+i\gamma of \zeta. The leading x is the main term; the two tail terms are bounded and harmless. Everything about the error term \psi(x)-x lives in that middle sum over zeros.

Now look at the size of a single zero's contribution. Since |x^{\rho}| = x^{\Re(\rho)} = x^{\beta}, each term satisfies

So the height \gamma of a zero only damps its term through the denominator, but the real part \beta sits in the exponent — it controls how fast the term grows with x. The whole error is governed by how far right the zeros reach: \Theta := \sup_{\rho}\beta.

The equivalence, made precise

Because the error is dominated by x^{\Theta} where \Theta=\sup_\rho\beta, pushing every zero onto the critical line \beta=\tfrac12 is exactly what squeezes the error down to \sqrt{x}. This is the Koch equivalence.

The \psi form and the \pi form differ only in their polylog factor (\ln^2 x versus \ln x) — that discrepancy is just the bookkeeping of converting the prime-power count \psi into the prime count \pi by partial summation against 1/\ln t. The heart of both is the same \sqrt{x}. Helge von Koch proved this crisp form in 1901, four decades after Riemann's original 1859 memoir.

The derivation in one breath

Why does \Theta=\tfrac12 give \sqrt{x}\,\ln^2 x? Truncate the zero sum at height T. Two facts about the zeros do the work:

• Density. The number of zeros up to height T is N(T)\sim \tfrac{T}{2\pi}\ln T, so \sum_{|\gamma|\le T}\tfrac{1}{|\rho|}\asymp \ln^2 T.
• Uniform size on RH. If RH holds, every surviving term is \tfrac{x^{1/2}}{|\rho|}, so the truncated sum is \lesssim \sqrt{x}\,\ln^2 T.

Balancing the truncation error against T\approx x turns \ln^2 T into \ln^2 x, giving \psi(x)-x = O(\sqrt{x}\,\ln^2 x). Run the argument in reverse — a single zero with \beta>\tfrac12 would inject a term of true size x^{\beta} that no cancellation can hide, blowing the \sqrt{x} bound — and you get the converse. Hence the equivalence: the error is \asymp\sqrt{x} if and only if \sup_\rho\beta=\tfrac12.

Seeing it: the error versus its ceiling

Below, the jagged lower curve is the actual error |\pi(x)-\operatorname{Li}(x)|, with \pi(x) computed exactly by a sieve. The smooth soaring curve is the RH envelope \sqrt{x}\,\ln x. Notice how the real error hugs the axis — it stays microscopic compared with the ceiling the hypothesis guarantees. RH does not promise the error is close to \sqrt{x}\,\ln x; it promises it never exceeds a constant multiple of it, no matter how far right you go.

Worked example — x=10^6. The exact prime count is \pi(10^6)=78{,}498 and \operatorname{Li}(10^6)\approx 78{,}627.5, so the true error is only about

The RH ceiling for the same x is \sqrt{10^6}\,\ln(10^6) = 1000\times 13.8 \approx 13{,}800 — a factor of roughly 100 of headroom. And the best unconditional bound anyone has proved (without assuming RH) has no power saving at all: it is only of the shape x\,\exp\!\left(-c\sqrt{\ln x}\right), which for x=10^6 is larger still by orders of magnitude. RH would replace that feeble unconditional estimate with the tight \sqrt{x}\,\ln x ceiling — for every x, forever.

Is \sqrt{x} really the best you can do?

Yes — and provably so, no hypothesis required. The error cannot be squeezed below \sqrt{x} by any polylog trick, because it genuinely reaches that size infinitely often, swinging both positive and negative:

The notation \Omega_{\pm} means the error exceeds that size (with both signs) for arbitrarily large x — the exact opposite of an O upper bound. Since the guaranteed lower oscillation is already \sqrt{x} up to a whisper of \ln\ln\ln x, no theorem — RH or otherwise — can ever push the error below \sqrt{x}. The Koch bound is therefore essentially best possible: RH pins the error into the razor-thin band between \sqrt{x}\,\ln\ln\ln x and \sqrt{x}\,\ln^2 x.

Why \sqrt{x}? The fair-coin picture

The \sqrt{x} is not arbitrary — it is the signature of square-root cancellation, the same \sqrt{N} that governs a random walk. Flip a fair coin N times; the running total of heads-minus-tails does not stay near zero (that would be too tidy) nor drift off like N (that would be biased) — it wanders a typical distance of \sqrt{N}. Each zero x^{\rho}/\rho = x^{1/2}e^{i\gamma\ln x}/\rho is a little rotating vector of length x^{1/2}/|\rho|; RH lines them all up at the same radius \tfrac12 so they interfere like independent random phases, and their sum has exactly the \sqrt{x} spread of a random walk.

That is the deep content of the slogan "the primes are as regularly distributed as a fair coin allows." A zero off the line — say at \beta=0.6 — would be a biased coin: a persistent drift of size x^{0.6} that overwhelms the honest \sqrt{x} fluctuation. RH says no such bias exists. The primes are random-looking in the strongest precise sense a deterministic sequence can be.