The Structured Distribution of Prime Numbers — Epoche C2
What is actually being compared The number of primes not exceeding a bound $x$, written $\pi(x)$, agrees with the logarithmic integral $\mathrm{li}(x) = \int_0^x \frac{dt}{\log t}$ — the integral read as a Cauchy principal value across the singularity at $t=1$, with logarithms natural throughout — to about one part in a million at $x = 10^{12}$, and the small quantity by which the two disagree is not an unanalysed remainder but an object with an exact closed description as a sum of oscillations indexed by the zeros of the Riemann zeta function. That description is what turns the word "random", applied to the primes, into a claim that can be tested rather than a shrug. The primes are of course not random in any literal sense: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 are fixed for ever, and a sequence with no free parameters has no distribution. What can be asked is whether the statistics of that fixed sequence match the statistics a random model predicts, and, where they fail to match, what governs the failure. Three data points fix the scale of the problem. The values of $\pi$ are exact counts; the remaining columns are rounded. $x$ $\pi(x)$ $x/\log x$ $\mathrm{li}(x)$ $\mathrm{li}(x)-\pi(x)$ $10^{6}$ 78,498 72,382 78,628 130 $10^{9}$ 50,847,534 48,254,942 50,849,235 1,701 $10^{12}$ 37,607,912,018 36,191,207,000 37,607,950,281 38,263 Two features of this table matter. First, the elementary approximation $x/\log x$ is poor in relative terms and stays poor: at $x=10^{6}$ it falls short of the true count by 6,116, which is 8.45 per cent of its own value, and at $10^{12}$ it is still 3.91 per cent short. Second, that shortfall shrinks in a completely predictable way. The asymptotic expansion $\mathrm{li}(x) = \frac{x}{\log x}\left(1+\frac{1}{\log x}+\frac{2}{(\log x)^{2}}+\cdots\right)$ predicts a relative shortfall of about $\frac{1}{\log x}+\frac{2}{(\log x)^{2}}$. At $10^{6}$ that is $0.0724+0.0105=0.0829$ against an observed $0.0845$; at $10^{9}$, $0.0483+0.0047=0.0529$ against $0.0537$; at $10^{12}$, $0.0362+0.0026=0.0388$ against $0.0391$. The Prime Number Theorem, $\pi(x)\sim x/\log x$, conjectured by Gauss and by Legendre and proved independently by Hadamard and by de la Vallée Poussin in 1896, asserts only that the shortfall tends to zero. The table shows how slowly it does so, and shows that the quantity worth taking a difference against is $\mathrm{li}(x)$, not $x/\log x$. Where a smooth law comes from at all Nothing so far explains why a smooth analytic function should approximate a counting function of integers. The bridge is Euler's product, $$\zeta(s)=\sum_{n=1}^{\infty}\frac{1}{n^{s}}=\prod_{p}\left(1-p^{-s}\right)^{-1},\qquad \operatorname{Re}s>1,$$ which is nothing but unique factorisation written as a generating function: expanding each factor as a geometric series and multiplying produces each $n^{-s}$ exactly once. Taking logarithms converts the product into a sum over prime powers, $\log\zeta(s)=\sum_{p}\sum_{k\ge 1}\frac{1}{k}p^{-ks}$. The natural counting function for the right-hand side is therefore not $\pi$ but $$J(x)=\sum_{k\ge 1}\frac{1}{k}\,\pi\!\left(x^{1/k}\right),$$ a step function that jumps by $1/k$ at every $k$-th power of a prime — by $1$ at each prime, by $1/2$ at each square of a prime, and so on. With this weighting, $\log\zeta(s)=s\int_{1}^{\infty}J(x)x^{-s-1}\,dx$ for $\operatorname{Re}s>1$, so $\log\zeta(s)/s$ is a Mellin transform of $J$ and can be inverted: $$J(x)=\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty}\frac{\log\zeta(s)}{s}\,x^{s}\,ds,\qquad a>1.$$ Everything else follows from knowing $\log\zeta$ well enough to move the contour leftwards, and that is what the zeros supply. Riemann's device, supplied with a proof by Hadamard in 1893, is to work with the completed function $\xi(s)=\tfrac{1}{2}s(s-1)\pi^{-s/2}\Gamma(s/2)\zeta(s)$, which is entire and of order $1$ — that is, $|\xi(s)|$ grows no faster than $\exp(|s|^{1+\varepsilon})$ for every $\varepsilon>0$, and not as slowly as $\exp(|s|^{1-\varepsilon})$. Hadamard's factorisation theorem says that an entire function of finite order $\alpha$ is determined by its zeros up to an exponential factor $e^{g(s)}$ with $\deg g\le\alpha$, the product over zeros being taken with elementary factors of genus at most $\alpha$. Order $1$ is precisely the hypothesis that licenses the product form here, and the zeros of $\xi$ are exactly the zeros of $\zeta$ lying in the strip $0 Riemann's formula counts prime powers, not primes The result of that computation, the centrepiece of Riemann's 1859 paper Ueber die Anzahl der Primzahlen unter einer gegebenen Grösse , is an identity for $J$: $$J(x)=\mathrm{li}(x)-\sum_{\rho}\mathrm{li}\!\left(x^{\rho}\right)-\log 2+\int_{x}^{\infty}\frac{dt}{t\,(t^{2}-1)\log t}.$$ Each term has a source. The main term $\mathrm{li}(x)$ comes from the simple pole of $\zeta$ at $s=1$, the only pole the analytic continuation has. The sum runs over the zeros $\rho$ in the critical strip. The integral collects the trivial zeros at the negative even integers, and is smaller than $1$ for every $x\ge 2$. The constant $-\log 2$ is a fixed offset with no dependence on $x$. This formula is very often quoted with $\pi(x)$ in place of $J(x)$ on the left. That is a misstatement, and at the sizes anyone actually computes it is not a small one. Recovering $\pi$ from $J$ requires Möbius inversion of the definition of $J$, which gives $$\pi(x)=\sum_{k\ge 1}\frac{\mu(k)}{k}\,J\!\left(x^{1/k}\right)=J(x)-\tfrac{1}{2}J\!\left(x^{1/2}\right)-\tfrac{1}{3}J\!\left(x^{1/3}\right)-\tfrac{1}{5}J\!\left(x^{1/5}\right)+\tfrac{1}{6}J\!\left(x^{1/6}\right)-\cdots$$ The sum is finite for any given $x$, because $J(x^{1/k})=0$ as soon as $x^{1/k} \log_{2}x$; at $x=10^{9}$, where $\log_{2}10^{9}=29.90$, the terms stop at $k=29$. The terms with $\mu(k)=0$, beginning at $k=4$, are absent because $J$ already counts squares of primes with weight $1/2$. These correction terms are exactly what makes $\mathrm{li}(x)$ overshoot $\