Motivation
Euclid proves that primes never end, but that leaves their abundance almost entirely open. Are there only a handful below a huge bound, or a substantial fraction of all integers? Elementary estimates already identify the correct scale: the number of primes up to is bounded above and below by positive constant multiples of .
The proof counts prime powers inside a central binomial coefficient. Its size is roughly exponential in its index, so its prime factorization must contain enough total logarithmic weight. We first estimate that weight, remove the extra contribution from higher prime powers, and only then translate it into a count of primes. A separate finite-product argument proves that the reciprocals of primes have divergent sum. None of this assumes the prime number theorem.
Use unique factorization, factorials, binomial coefficients and basic logarithm properties. All logarithms are natural. Some final asymptotic comparisons use the elementary fact that logarithms grow more slowly than positive powers; this is a real-variable estimate, not an unproved assertion about primes.
Definitions
Definition 9.2.1
(Prime counts and logarithmic prime weights)
Let be the set of positive primes. For real , define
The last sum counts each prime once for every positive power not exceeding . Thus it is finite and . Both weighted sums are zero below two. Their values at nonintegers equal their values at the corresponding floor.
Concept lensAlgebraic
Prime-power weight as the logarithm of a least common multiple
The same function has a closed multiplicative description:
The exponent of a prime in that least common multiple is the largest with , and adds exactly that many times. For example, and . This explains why counting prime powers is useful even though the eventual question concerns primes themselves.
Why the prime-power weight also belongs to arithmetic functions
Definition 9.2.2
(The prime-power weight )
Define when for a prime and a positive integer , and otherwise, including at . Then .
This packages the same weighted counting problem as a summatory arithmetic function, connecting it to the divisor-sum unit.
If , the divisors of on which is nonzero are exactly for each prime factor. Their contributions sum to . Thus , and the already proved Möbius inversion formula gives . No limit or analytic continuation is involved in either identity. Prime powers appear because a logarithm counts every copy of a prime in a factorization; omitting higher powers would lose those copies. The binomial proof below uses exactly this bookkeeping through factorial valuations.
Theorems
Theorem 9.2.3
(A central binomial coefficient controls prime-power weight)
For every integer ,
and
Consequently, for every real ,
These intentionally loose constants keep the estimates elementary and explicit.
Theorem 9.2.4
(The elementary scale of prime counting)
For every real ,
If is the th prime, then is bounded above and below by positive constant multiples of for all sufficiently large . Also diverges. These conclusions do not assert , its exact limiting constant, or a uniform prime-gap bound.
Proof sketch or proof idea
Find the exact exponent before estimating the coefficient
Proof
(Valuations and size of the central coefficient)
For a prime , counting multiples of in a factorial gives
Every integer factor divisible by contributes one to each of the first counts, exactly its exponent. Therefore
For any real , is or : write as its integer part plus a fractional part. Thus each prime-power position contributes at most one copy of to the logarithm, and positions with contribute nothing to the coefficient, proving the upper bound by . If , the displayed difference is exactly , proving the lower bound by . Additional smaller prime powers may contribute too; the lower bound is generally not an equality.
The binomial theorem gives . The central coefficient is the largest: the ratio of consecutive coefficients is , greater than before the middle and at most after it. Hence the largest is at least the average , and no coefficient exceeds the whole sum . Taking logarithms proves both size estimates.
Sum dyadic increments for an upper bound, use one large coefficient for a lower bound
Proof
(Linear bounds for )
At powers of two, with , the first inequality and the binomial upper estimate give
Sum from upward, using . Then . For real choose the least power ; it is less than . Monotonicity gives .
For the lower bound put . Then , , and the coefficient lower estimate gives
For this is at least . To check that last numerical comparison rigorously, its difference is . At it is , positive since . Its derivative is there and afterwards. Thus no hidden large- exception remains in the stated bound.
Higher prime powers contribute less than the main linear weight
Proof
(From to and to )
Only primes can contribute more than their first . For any such , all its contributions together are , so its additional contributions total less than . There are at most such primes, even using the crude bound by all integers. Therefore
For , . Indeed this ratio decreases for , and at it equals , smaller than the claimed bound. Combining this with the estimates yields
Every prime has , so . This proves the lower prime-count bound. For an upper bound, at most primes lie below the square root, and every remaining prime contributes more than to . Hence
Here for this range, and . Splitting off the small primes is necessary: assigning to every prime would give the wrong direction for an upper bound.
Proof X-ray
Weighted counting needs two different inequalities
The passage from to uses two weight comparisons that point in opposite directions. The lower count divides by the largest possible weight: every is at most , so . The upper count needs the smallest possible weight instead, and that is where the one non-obvious move, the split at , enters. Without it, the smallest weight is , and the only conclusion is , which has the wrong order. Above each weight exceeds , and the primes below are counted crudely, which costs only .
The threshold is used once on each side. On the lower side, the higher-power error must be at most , half of the lower constant, so that a positive multiple of survives in . On the upper side, it guarantees , and the constants close because .
Invert the scale for the nth prime
Proof
(Bounds for the th prime)
Write and . For sufficiently large , take with . Then , so and . Conversely put . Eventually and , so and . These give the claimed two constant multiples. The qualifiers follow from elementary logarithm comparisons; the explicit threshold for the earlier theorem is not being silently reused as a threshold for the index .
A finite Euler product forces reciprocal-prime divergence
Proof
(Divergence of )
For a fixed real , expand the finite product
Each factor is a convergent geometric series. Because the number of factors is finite and all terms are nonnegative, their product sums reciprocals of precisely the positive integers whose prime factors are at most . Unique factorization gives each such integer exactly once. In particular it includes every integer , so the product is at least , and this harmonic sum tends to infinity with .
If converged, however, the product logarithm would be bounded: for , , as follows by integrating from to ; every lies in that range. Thus its logarithm is at most , bounded under that assumption. Exponentiating contradicts the unbounded harmonic lower bound. This proves divergence without manipulating an unjustified infinite product or assuming a prime-density limit.
Worked examples
Worked example 9.2.5
(A small coefficient shows why the prime-power bounds are inequalities)
For the central coefficient is , with prime factorization . Meanwhile , since the prime powers up to are , and . Thus the theorem reads . The interval supplies the forced prime-power positions and . The extra copy of comes from the smaller position , where ; the prime contributes nothing to the coefficient, since , despite being counted in . The valuation formula explains both discrepancies exactly.
Worked example 9.2.6
(Explicit constants are certificates, not close predictions)
At the lower count bound is , so there are at least primes up to that point. The upper bound is . This interval is deliberately broad. Its value is that both endpoints follow from a proof using only elementary estimates, and the same constants work for every larger real . The theorem identifies a growth scale; it is not a numerical approximation with a small relative error.
Worked example 9.2.7
(A finite Euler product includes integers beyond its cutoff)
For the primes the product is . The harmonic sum is , strictly smaller. The product also includes reciprocals of and every other integer composed only of , even when it exceeds . Thus it dominates the truncated harmonic sum rather than equaling it. This extra positive mass is harmless and is exactly why a lower bound is sufficient for the divergence proof.
Counterexample mode
Infinitely many positive terms need not have divergent sum
The prime squares give an infinite series, but converges: it is bounded above by . The last series telescopes. Euclid's infinitude alone therefore cannot justify divergence of reciprocal primes; the finite-product argument supplies real additional information.
Common mistakes
Common mistake
(Weighting a prime power by its own logarithm)
The function gives each prime power the weight , not . At the correct value is , the logarithm of ; the wrong weighting gives . The same care applies to valuations: a prime power can contribute at more than one level of the factorial count, so keep the exact floor formula before estimating.
Common mistake
(Dropping the small-prime correction in the upper count)
Dividing by gives only a lower bound for . An upper count needs a lower bound on each weight, which holds only for . The term for the remaining small primes has a definite role and cannot be discarded without replacement.
Common mistake
(Reading constant-multiple bounds as an asymptotic law)
Bounds by two constant multiples of do not establish , nor any limit. The proof also does not say that every interval of a fixed length contains a prime. Likewise, the finite Euler product contains arbitrarily large integers built from the primes up to , so it should not be identified with the harmonic sum having the same cutoff.
Summary
Central binomial coefficients convert factorial valuations into linear bounds for . Higher prime powers contribute only a smaller error, giving linear bounds for and the scale for prime counting. Inverting those bounds gives the scale of the th prime. Finite geometric products and unique factorization independently prove reciprocal-prime divergence.
Exercises
Quick check
(Verify the prime-power interpretation of at by computing .)
Solution · Answer
The maximal prime powers at most are , so the least common multiple is . Its logarithm equals , which is . The value has only one copy of each of these four prime logarithms, leaving extra weight .
Quick check
(Prove that from the stated elementary error estimate. Explain why this alone does not prove the prime number theorem.)
Solution · Answer
Divide the error estimate by to obtain a bound by , which tends to zero. Thus the two weighted functions differ by a sublinear amount. But their proven main bounds have different constants: neither has been shown to have ratio to . A small difference between two unknown linear-scale functions does not determine their common limiting coefficient.
Quick check
(Show that the finite products tend to zero, and interpret their reciprocals in the divergence proof.)
Solution · Answer
Their reciprocals dominate the harmonic sums and therefore tend to infinity. Every factor is positive, so taking reciprocals shows the products tend to zero. This does not assert that any one finite product is zero; each is a strictly positive rational number. The limit expresses increasingly many reciprocal-prime contributions.
Quick check
(Why does give a lower bound on pi rather than an upper bound? Repair the false upper-bound argument using the square-root split.)
Solution · Answer
Dividing the inequality by positive log yields . To bound above, at most primes lie below the square root, while each larger prime has . Thus their number is at most , giving the proved upper estimate after adding the small-prime allowance. The same weighted sum supplies opposite count directions only after these distinct maximum/minimum weight comparisons.