Part I · Chapter 1

Counting primes

The is equivalent to a bound on the error in the standard estimate for the number of up to xx. This chapter defines the count, the estimate, and the error.

The staircase and its smooth guess

Write π(x)\pi(x) for the number of primes up to xx. It is a staircase: flat, then up by one at each prime. Primes thin out as numbers get bigger, and noticed the rule: near a large number xx, about one number in every ln⁡x\ln x is prime. Around a thousand that is one in 7; around a million, one in 14.

If the chance of being prime near tt is 1/ln⁡t1/\ln t, then adding up those chances for every tt from 2 to xx should estimate how many primes there are up to xx. That running total is called the , written li⁡(x)=∫2xdtln⁡t\operatorname{li}(x) = \int_{2}^{x} \frac{dt}{\ln t}. A cruder estimate, x/ln⁡xx/\ln x, has the right shape but runs low.

Lab 1.1 the prime staircase against its smooth guesses
π(x), the countli(x)x / x
At small scale the staircase is visibly jagged. Slide right and it melts into li⁡(x)\operatorname{li}(x); the gap in the readout stays tiny next to the count itself.

Weighing primes instead of counting them

Counting each prime as 1 turns out to give awkward formulas. Number theorists get cleaner ones from a . Give every pkp^{k} the weight ln⁡p\ln p, and every other number weight zero. This weight is called Λ(n)\Lambda(n), the , and its running total is 's function, written ψ(x)=∑n≤xΛ(n)\psi(x) = \sum_{n \le x} \Lambda(n): add up the weights of all whole numbers up to xx.

The weights exactly cancel the thinning-out. Primes near xx are rarer by a factor of ln⁡x\ln x, but each one counts for ln⁡x\ln x, so the weighted total should grow like xx itself. The says that it does: ψ(x)\psi(x) divided by xx gets closer and closer to 1.

Lab 1.2 the weighted staircase ψ(x) against the line y = x
ψ(x)x
The staircase jumps at every prime power, and the jumps have different heights: ln⁡2\ln 2 at 2, 4, 8, 16…, ln⁡3\ln 3 at 3, 9, 27…, and in general ln⁡p\ln p at each power of the prime pp. Hover to read ψ(x)\psi(x) on either side of a jump.

The error is the whole question

How far does the staircase stray from the line? If primes were placed by fair coin flips with the right density, the error up to xx would be about x\sqrt{x} in size. The Hypothesis is equivalent to saying the primes do essentially that well:

The Riemann Hypothesis is true exactly when the gap between ψ(x)\psi(x) and xx is never more than about x\sqrt{x}. Precisely: the gap is at most C⋅x⋅(ln⁡x)2C \cdot \sqrt{x} \cdot (\ln x)^{2} for some fixed number CC. What has actually been proved so far is much weaker: the gap is known to be smaller than xx, but not smaller than any fixed root of xx.

Lab 1.3 the error, measured in units of √x
(ψ(x) − x) / √x
The gap divided by x\sqrt{x}. If the Riemann Hypothesis is true this stays in a narrow band forever (apart from the slowly growing (ln⁡x)2(\ln x)^{2} allowance). From 10 up to 20,000 it stays inside ±1\pm 1.

Things to try

  • In Lab 1.1, look for a place past the first few primes where π(x)\pi(x) is above li⁡(x)\operatorname{li}(x). You will not find one: a crossing is known to exist, but it lies beyond 101910^{19}.
  • In Lab 1.2, set the slider to about 30 and compare the jump at 25 with the jump at 27. The jump at 25 is ln⁡5≈1.61\ln 5 \approx 1.61, because 25=5225 = 5^{2}. The jump at 27 is ln⁡3≈1.10\ln 3 \approx 1.10, because 27=3327 = 3^{3}. The height depends on which prime the number is a power of, not on how large the number is. At 26, which is not a prime power, there is no jump.
  • In Lab 1.3, hover near 110 to 130. The long flat run of the staircase (no primes from 113 to 127) shows up as a steady slide downward.

Exercises

  1. Compute ψ(10)\psi(10) by hand.
    Solution

    The prime powers up to 10 are 2, 3, 4, 5, 7, 8, 9. The weights are ln⁡2\ln 2 three times (for 2, 4, 8), ln⁡3\ln 3 twice (for 3, 9), ln⁡5\ln 5 and ln⁡7\ln 7. The total is ln⁡(23⋅32⋅5⋅7)=ln⁡2520≈7.83\ln(2^{3} \cdot 3^{2} \cdot 5 \cdot 7) = \ln 2520 \approx 7.83.

  2. Show that ψ(x)\psi(x) is the logarithm of the least common multiple of 1,2,…,⌊x⌋1, 2, \dots, \lfloor x\rfloor.
    Solution

    The least common multiple contains each prime pp to the highest power pk≤xp^{k} \le x. Its logarithm is therefore k⋅ln⁡pk \cdot \ln p summed over primes, and ψ\psi adds ln⁡p\ln p once for each of p,p2,…,pkp, p^{2}, \dots, p^{k}, which is the same total. Exercise 1 is the case lcm⁡(1,…,10)=2520\operatorname{lcm}(1, \dots, 10) = 2520.

  3. Use Gauss's density 1/ln⁡x1/\ln x to estimate how many primes lie between 1,000,000 and 1,001,000.
    Solution

    ln⁡1,000,000≈13.8\ln 1{,}000{,}000 \approx 13.8, so about one number in 13.8 is prime there: roughly 1000/13.8≈721000/13.8 \approx 72 primes.

Check your understanding

  1. Why does ψ\psi give a prime pp the weight ln⁡p\ln p instead of counting it as 1?

    • So that the sum is always a whole number
    • Near xx about one number in ln⁡x\ln x is prime, so weights of ln⁡p\ln p make the total grow like xx itself
    • Because large primes matter less than small ones
    • So that the sum converges

    The weight cancels the thinning-out of the primes. The comparison function for ψ\psi is then simply xx, where for π\pi it is the integral li⁡(x)\operatorname{li}(x). Note the weight makes large primes count more.

  2. The prime number theorem says ψ(x)\psi(x) is "close to" xx. Which reading is correct?

    • ψ(x)−x\psi(x) - x stays below some fixed number
    • ψ(x)−x\psi(x) - x eventually becomes 0
    • The ratio ψ(x)/x\psi(x)/x tends to 1, while the difference can still grow

    The theorem controls the error only relative to xx. The difference ψ(x)−x\psi(x) - x is unbounded; how fast it can grow is exactly what the Riemann Hypothesis is about.

  3. There are 78,498 primes below one million. Without computing, how many would you expect between one million and two million?

    • Somewhat fewer, because the density 1/ln⁡x1/\ln x keeps falling slowly
    • The same number, because the stretch has the same length
    • About half as many
    • More, because the numbers are larger

    The density falls from about 1/13.8 at one million to 1/14.5 at two million. The true count is 70,435, about 10% fewer.