Back to the on-screen lesson ·
How many primes lie below a bound, the logarithmic estimate that sizes the count, and how slowly the limit it describes actually arrives.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to state the prime number theorem as a statement about a ratio and say why that permits an unbounded difference, compute the estimate $x/\ln x$ and compare it with an exact count, use the density $1/\ln x$ to estimate how many primes lie in a range, and say why the logarithmic integral is preferred in practice although the theorem does not distinguish the two.
Lesson 24 established that the primes never stop and that they can be absent for arbitrarily long stretches. Both facts are about extremes, and neither says anything about the ordinary behaviour in between.
The sieve produces $\pi(x)$ — the number of primes up to $x$ — and it produces it by counting. There is no formula. What this lesson supplies is the next best thing: a simple function that $\pi(x)$ agrees with to within a factor that tends to one, which is enough to answer almost every practical question about how many primes there are.
$\pi(x)$ counts the primes at most $x$: $\pi(10) = 4$, $\pi(100) = 25$, $\pi(10^{6}) = 78\,498$.
Two functions are asymptotic, written $f \sim g$, when $f(x)/g(x) \to 1$. It is a statement about the ratio and permits the difference to grow without bound.
The density of the primes near $x$ is $1/\ln x$: the chance that a number chosen near $x$ is prime.
The logarithmic integral $\operatorname{li}(x) = \int_{2}^{x} dt/\ln t$ is a much better estimate of $\pi(x)$ than $x/\ln x$, and satisfies the same asymptotic statement.
The prime number theorem. $$\pi(x) \sim \frac{x}{\ln x}, \qquad\text{that is}\qquad \lim_{x \to \infty}\frac{\pi(x)}{x/\ln x} = 1.$$
Conjectured by Gauss at fifteen from a table of primes, and proved independently by Hadamard and de la Vallée Poussin in 1896, a century later, using complex analysis and the Riemann zeta function. An elementary proof was found by Selberg and Erdős in 1949 — elementary meaning without complex analysis, not short.
Read it as a density. Rearranged, $\pi(x)/x \approx 1/\ln x$: the proportion of numbers up to $x$ that are prime is about one over the natural logarithm. So near $10^{6}$ roughly one number in $14$ is prime, and near $10^{100}$ roughly one in $230$. The primes thin out, and they thin out logarithmically — which is very slowly.
That is the form the theorem is used in. To find a $2048$-bit prime, test random odd numbers of that size: the density says about one in $\ln(2^{2048})/2 \approx 710$ of the odd ones is prime, so a few hundred tests suffice. Without this estimate there would be no way to know that key generation terminates quickly.
What it does not say. The difference $\pi(x) - x/\ln x$ does not tend to zero — it grows without bound. At $10^{6}$ the count is $78\,498$ and the estimate about $72\,382$, a gap of over six thousand. A ratio tending to $1$ tolerates an unbounded difference, and confusing the two is the standing misreading of every asymptotic statement.
A better estimate. $\operatorname{li}(x)$ beats $x/\ln x$ at every size checked: at $10^{6}$ it gives $78\,628$ against the true $78\,498$ — an error of $130$ rather than six thousand. Both are asymptotic to $\pi(x)$; the theorem does not distinguish them, and the error term does. The Riemann hypothesis is equivalent to the statement that $\operatorname{li}(x)$ approximates $\pi(x)$ with error at most about $\sqrt x \ln x$, which is why it is a statement about the primes at all.
Another way: steps
Another way: example
How many primes between $10^{6}$ and $10^{6} + 1000$? The density near a million is $1/\ln(10^{6}) \approx 1/13.8 \approx 0.072$, so about $72$ — and the true count is $75$. Now the same at $10^{9}$: density $1/20.7 \approx 0.048$, so about $48$ in a thousand. The primes have thinned by a third over three orders of magnitude.
The prime number theorem is a statement about a limit, and it is worth seeing how far a limit can be from any number you will ever compute with.
The ratio $\pi(x)\ln x / x$ tends to $1$. Here is how it actually behaves:
| $x$ | $\pi(x)$ | $x/\ln x$ | ratio |
|---|---|---|---|
| $10^{2}$ | $25$ | $21.7$ | $1.151$ |
| $10^{4}$ | $1\,229$ | $1\,086$ | $1.132$ |
| $10^{6}$ | $78\,498$ | $72\,382$ | $1.084$ |
| $10^{10}$ | $455\,052\,511$ | $434\,294\,482$ | $1.048$ |
| $10^{20}$ | $2.2 \times 10^{18}$ | $2.2 \times 10^{18}$ | $1.024$ |
Still two and a half per cent out at $10^{20}$, and falling roughly like $1/\ln x$. To get within one per cent takes about $10^{50}$. The limit is real and the convergence is glacial, and an estimate that is asymptotically correct can be useless for error bars at any size that matters.
That is why $\operatorname{li}(x)$ is used instead. It has the same limit and a far smaller error, because it integrates the density rather than assuming it constant across the whole range — $x/\ln x$ effectively uses the density at $x$ for every number below $x$, and the density was larger further down.
There is a famous cautionary tale attached. Every computed value has $\pi(x) < \operatorname{li}(x)$, and it was believed for a long time that this always held. Littlewood proved in 1914 that the inequality reverses infinitely often, and Skewes gave the first bound on where — originally an unimaginably large number, since reduced to somewhere below $10^{316}$. No crossing has ever been exhibited.
The moral is exact: a pattern holding for every computable case is not a theorem, and in analytic number theory the first counterexample can lie far beyond anything that will ever be checked.
Reading asymptotic as approximately equal with small error. The ratio tends to $1$; the difference grows without bound. At $10^{6}$ the gap is over six thousand.
Using base-ten logarithms. $\ln$ means the natural logarithm. Using $\log_{10}$ overestimates $\pi(x)$ by a factor of about $2.3$.
Expecting a formula for the $n$-th prime. The theorem sizes the count, not the location. It does give $p_n \sim n\ln n$, again asymptotically, and again with unbounded error.
Assuming the estimate is an upper bound. $x/\ln x$ undershoots throughout the computable range, and the comparison with $\operatorname{li}(x)$ reverses infinitely often. Neither inequality is a theorem.
Treating the density as a probability of a specific number. A specific number is prime or is not. The density describes a proportion over a range, and using it as a probability for one number is a way of speaking, not a fact.
Estimate $\pi(1000)$. $\ln 1000 \approx 6.908$, so $1000/6.908 \approx 144.8$.
Natural logarithm throughout.
The true value is $168$, so the estimate undershoots by about $14$ per cent — and the ratio $168/144.8 \approx 1.160$ is what the theorem says tends to $1$.
At this size the limit is nowhere near reached.
The logarithmic integral gives $\operatorname{li}(1000) \approx 177.6$, which overshoots by about six per cent. Closer, and in the other direction — which is the usual pattern.
Two asymptotic estimates can differ substantially at any finite size.
How many odd numbers of $2048$ bits must be tested before a prime is found? A number near $2^{2048}$ is prime with probability about $1/\ln(2^{2048}) = 1/(2048 \ln 2) \approx 1/1420$.
The density, straight from the theorem.
Testing only odd numbers doubles the chance to about $1/710$.
Half the candidates are ruled out for free.
So about $710$ primality tests on average, each a few exponentiations — under a second. This calculation is why RSA key generation is known to terminate quickly, and there is no other source for it.
An asymptotic statement, doing engineering work.
The density near $10^{9}$ is $1/\ln(10^{9}) = 1/(9 \ln 10) \approx 1/20.72$.
The interval is narrow, so one density value serves for all of it.
Multiply by the width: $10^{4}/20.72 \approx 483$.
Width times density.
So about $480$ primes, and the true count is $487$. The estimate is good here because the interval is short — over a long range the density changes and the integral is needed instead.
For the bound $120$, give the exact number of primes up to it, the estimate $120$ divided by its natural logarithm to one decimal place, and the count as a percentage of that estimate to one decimal place.
| Value | |
|---|---|
| Primes up to the bound | |
| The bound over its natural logarithm | |
| The count as a percentage of the estimate |
How many primes are there up to $100$?
Answer:
Is this true: the logarithmic integral estimates the count better than the bound over its logarithm?
Match each bound to the number of primes up to it.
| $8$ | $35$ | $30$ | |
|---|---|---|---|
| up to $20$ | |||
| up to $150$ | |||
| up to $120$ |
For the bound $200$, give the exact number of primes and the estimate $200$ divided by its natural logarithm, to one decimal place.
exact count a, estimate c
For the bound $200$, mark the exact prime count as a percentage of the estimate $200$ over its natural logarithm. The line runs from $110$ to $125$.
110 |——————————| 125
Mark the position with a cross, then write the value:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
For the bound $20$, give the exact number of primes up to it, the estimate $20$ divided by its natural logarithm to one decimal place, and the count as a percentage of that estimate to one decimal place.
| Value | |
|---|---|
| Primes up to the bound | |
| The bound over its natural logarithm | |
| The count as a percentage of the estimate |
You can estimate how many primes lie below a bound or inside a range, and say how far the estimate is from the truth. Say in your own words the difference between a ratio tending to one and a difference tending to zero. Next: the primes inside a single arithmetic progression.
9. Your turn: estimate how many primes lie between $10^{9}$ and $10^{9} + 10^{4}$, step 3