Engineering / Mathematics — The Distribution of Primes
Chebyshev's Theorem on the Density of Primes
Chebyshev's elementary bounds on the prime counting function, the binomial coefficient argument, and what they establish short of the prime number theorem.
Executive summary
Chebyshev proved that the number of primes below x is of the order x over log x, up to explicit constants, half a century before the prime number theorem was established.
The proof is elementary and rests on a single observation: the central binomial coefficient is large, but its prime factorisation cannot contain large prime powers, so many distinct primes must be involved.
Learning objectives
- State Chebyshev's bounds on the prime counting function.
- Follow the binomial coefficient argument.
- Explain what remained open after Chebyshev.
01The statement
Prime counting function
π(x) is the number of primes not exceeding x.
Chebyshev's theorem
There exist positive constants c₁ < 1 < c₂ such that for all sufficiently large x
c₁ · x/ln x < π(x) < c₂ · x/ln x.
This pins the order of growth exactly. What it does not do is show that the ratio π(x) ln x / x tends to a limit, let alone that the limit is 1 — that is the prime number theorem and it needed complex analysis.
02The binomial argument
The engine is the central binomial coefficient C(2n, n), which is large and whose prime factorisation is constrained.
- It is large. Since
C(2n,n)is the largest of the2n+1binomial coefficients summing to4^n, it is at least4^n/(2n+1). - Its prime powers are small. For any prime p, the exponent of p in
C(2n,n)is at mostlog_p(2n), so every prime power dividing it is at most2n. - Only primes below 2n appear. No prime exceeding
2ncan divide the coefficient.
Combining these gives 4^n/(2n+1) ≤ C(2n,n) ≤ (2n)^{π(2n)}. Taking logarithms and rearranging bounds π(2n) from below by a constant times n/log n.
4^n/(2n+1) ≤ C(2n,n) ≤ (2n)^{π(2n)} ⇒ π(2n) ≥ c · n/ln n03The Chebyshev functions
The proof is cleaner in terms of two auxiliary functions that weight primes by their logarithms, smoothing the irregularity of the counting function.
| Function | Definition | Asymptotic |
|---|---|---|
| θ(x) | Σ_{p ≤ x} ln p | θ(x) ~ x |
| ψ(x) | Σ_{p^k ≤ x} ln p | ψ(x) ~ x |
| π(x) | count of primes ≤ x | π(x) ~ x/ln x |
The three statements are equivalent, and ψ is the most tractable analytically because it arises naturally from the logarithmic derivative of the Riemann zeta function. Modern proofs of the prime number theorem work with ψ and transfer the result to π at the end.
04Frequently asked questions
Why does the argument use the central binomial coefficient specifically?
Because it is the one binomial coefficient whose size is easy to bound from below in terms of 4^n, and whose prime factorisation has the clean property that no prime power exceeds 2n. Other coefficients lack one or the other property.
Are Chebyshev's constants close to 1?
His original constants were roughly 0.92 and 1.11, which is remarkably tight for an elementary argument. Getting them to converge to 1 required a fundamentally different method.
Is the result useful computationally?
Very. It gives a rigorous estimate for the density of primes near a given size, which is what justifies the expected running time of random prime generation — the basis of RSA and Diffie-Hellman key generation.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 74-78.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.