Counting primes
The is equivalent to a bound on the error in the standard estimate for the number of up to . This chapter defines the count, the estimate, and the error.
The staircase and its smooth guess
Write for the number of primes up to . 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 , about one number in every is prime. Around a thousand that is one in 7; around a million, one in 14.
If the chance of being prime near is , then adding up those chances for every from 2 to should estimate how many primes there are up to . That running total is called the , written . A cruder estimate, , has the right shape but runs low.
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 the weight , and every other number weight zero. This weight is called , the , and its running total is 's function, written : add up the weights of all whole numbers up to .
The weights exactly cancel the thinning-out. Primes near are rarer by a factor of , but each one counts for , so the weighted total should grow like itself. The says that it does: divided by gets closer and closer to 1.
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 would be about in size. The Hypothesis is equivalent to saying the primes do essentially that well:
The Riemann Hypothesis is true exactly when the gap between and is never more than about . Precisely: the gap is at most for some fixed number . What has actually been proved so far is much weaker: the gap is known to be smaller than , but not smaller than any fixed root of .
Things to try
- In Lab 1.1, look for a place past the first few primes where is above . You will not find one: a crossing is known to exist, but it lies beyond .
- 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 , because . The jump at 27 is , because . 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
- Compute by hand.
Solution
The prime powers up to 10 are 2, 3, 4, 5, 7, 8, 9. The weights are three times (for 2, 4, 8), twice (for 3, 9), and . The total is .
- Show that is the logarithm of the least common multiple of .
Solution
The least common multiple contains each prime to the highest power . Its logarithm is therefore summed over primes, and adds once for each of , which is the same total. Exercise 1 is the case .
- Use Gauss's density to estimate how many primes lie between 1,000,000 and 1,001,000.
Solution
, so about one number in 13.8 is prime there: roughly primes.
Check your understanding
Why does give a prime the weight instead of counting it as 1?
- So that the sum is always a whole number
- Near about one number in is prime, so weights of make the total grow like 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 is then simply , where for it is the integral . Note the weight makes large primes count more.
The prime number theorem says is "close to" . Which reading is correct?
- stays below some fixed number
- eventually becomes 0
- The ratio tends to 1, while the difference can still grow
The theorem controls the error only relative to . The difference is unbounded; how fast it can grow is exactly what the Riemann Hypothesis is about.
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 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.