chapter 02

Counting primes

Irregular one by one; remarkably predictable in the large.

A staircase called $\pi(x)$

Primes do not arrive at a steady rhythm. Sometimes they are close—like 11 and 13—and sometimes long gaps contain none. To study the overall pattern, mathematicians count rather than predict the next prime.

The prime-counting function $\pi(x)$ is the number of primes at most $x$. Thus $\pi(10)=4$ and $\pi(100)=25$.

Prime counts compared with the approximation $x/\log x$.

$\pi(x)$$x/\log x$

$x=10$

4 vs 4.3

$x=100$

25 vs 21.7

$x=1{,}000$

168 vs 144.8

$x=10{,}000$

1,229 vs 1,085.7

The density thins out

Among the first ten numbers, four are prime. Farther out, primes are rarer. Near a large number $x$, the rough chance of encountering a prime is about $1/\log x$. Accumulating that density suggests that

$$\pi(x)\sim\frac{x}{\log x}.$$

The symbol $\sim$ does not mean the two sides become equal. It means their ratio approaches 1 as $x$ grows. This is the prime number theorem: locally unpredictable primes obey a smooth global law.

The interesting part is the error

A smooth curve cannot land perfectly on a jagged staircase. Define the discrepancy

$$E(x)=\pi(x)-\operatorname{Li}(x),$$

where $\operatorname{Li}(x)$ is a refined smooth estimate. How wildly can $E(x)$ fluctuate? That question is much closer to the Riemann hypothesis than simply knowing the average number of primes.