21.11.03 · number-theory / dirichlet-series-arithmetic-functions

Chebyshev's Bounds, Bertrand's Postulate, and Mertens' Theorems

shipped3 tiersLean: none

Anchor (Master): Apostol 1976 *Introduction to Analytic Number Theory* Ch. 4 (the elementary prime-counting estimates preceding the analytic PNT); Chebyshev 1852 *J. Math. Pures Appl.* 17 (the original bounds and the first proof of Bertrand's postulate); Erdős 1932 *Acta Litt. Sci. Szeged* 5 (the binomial-coefficient proof of Bertrand); Mertens 1874 *Crelle* 78 (the three theorems); Tenenbaum 2015 *Introduction to Analytic and Probabilistic Number Theory* 3e (Cambridge UP) §I.1-I.3 (Abel summation, Mertens with explicit error terms)

Intuition Beginner

How many primes are there below a million? The answer is $78, 498$ , and the striking thing is that it is close to a simple prediction: a million divided by the natural logarithm of a million, which is about $72, 400$ . The primes thin out as you climb, but they thin out at a steady, predictable rate. Counting them exactly is hard; bounding how many there are turns out to be much easier, and you can do it with nothing more than careful bookkeeping about factorials.

The trick is to stop counting primes one at a time and instead add up a weight attached to each. Two running totals do the heavy lifting. The first adds the logarithm of every prime up to $x$ . The second adds that same logarithm once for the prime, again for its square, again for its cube, and so on. These two totals, written $ϑ (x)$ and $ψ (x)$ , grow almost exactly like $x$ itself. Pin them between two multiples of $x$ and you have pinned the count of primes.

Chebyshev did this in $1852$ , decades before anyone could prove the exact growth rate. From the same bookkeeping falls a clean fact you can state to a child: between any whole number and its double there is always a prime. And Mertens showed that if you add up one-over-prime for the primes below $x$ , the total grows like the logarithm of the logarithm of $x$ — slow, but never stopping.

Visual Beginner

A staircase plot of the function $ψ (x)$ climbing from left to right, jumping upward at each prime power. At $x = 2$ it jumps by $lo g 2$ ; at $x = 3$ by $lo g 3$ ; at $x = 4$ (which is $2$ squared) by $lo g 2$ again; at $x = 5$ by $lo g 5$ . Two straight dashed lines, one of slope a little below $1$ and one a little above $1$ , sandwich the staircase: the whole climb stays trapped between them. Beside it, a short table shows how close $ψ (x)$ and $x$ stay as $x$ grows.

$x$	$ψ (x)$ (approx.)	$ψ (x) / x$
$10$	$9.9$	$0.99$
$100$	$94.0$	$0.94$
$1000$	$993.0$	$0.99$
$10000$	$10013.4$	$1.00$

The staircase never wanders far from the diagonal line $y = x$ . That single picture is the whole content of Chebyshev's bounds: $ψ (x)$ is squeezed between a fixed fraction of $x$ and a fixed multiple of $x$ , so the primes can be neither far too dense nor far too sparse.

Worked example Beginner

Check the squeeze directly for a small value, and watch Bertrand's postulate fall out.

Step 1. Compute $ψ (10)$ by listing the prime powers up to $10$ . They are $2, 4, 8$ (powers of $2$ ), $3, 9$ (powers of $3$ ), $5$ , and $7$ . Each contributes the logarithm of its underlying prime: $2, 4, 8$ each add $lo g 2$ ; $3, 9$ each add $lo g 3$ ; $5$ adds $lo g 5$ ; $7$ adds $lo g 7$ . So $$ \psi(10) = 3\log 2 + 2\log 3 + \log 5 + \log 7 = \log!\big(2^3 \cdot 3^2 \cdot 5 \cdot 7\big) = \log 2520 \approx 7.83. $$

Step 2. Compare with $x = 10$ . The ratio is $7.83/10 = 0.78$ , comfortably between, say, $\frac{1}{2}$ and $2$ . The squeeze holds.

Step 3. Read off Bertrand for $n = 5$ : is there a prime between $5$ and $10$ ? Yes — the number $7$ . The bookkeeping behind the squeeze, sharpened, guarantees such a prime exists for every $n$ , with no gaps allowed.

What this tells us: $ψ (x)$ is just the logarithm of the product of all prime powers up to $x$ , and that product grows at a rate locked to $x$ . Bounding a product of primes — something factorials make easy — bounds the primes themselves.

Check your understanding Beginner

Exercise (easy, multiple choice).

Mertens' second theorem describes how the running total of one-over-prime — the sum of $1/2 + 1/3 + 1/5 + 1/7 + \dots$ over all primes up to $x$ — grows. Which of the following is the rate?

A. A constant (it converges)
B. $lo g x$
C. $lo g lo g x$
D. $x$

Hint

The sum of one-over-prime diverges, but extremely slowly — slower than the logarithm.

Answer

C. Mertens proved that the prime total $1/2 + 1/3 + 1/5 + \dots$ up to $x$ equals $lo g lo g x + M$ plus a vanishing amount, where $M$ is a fixed constant. The total grows without bound, so option A is wrong; it grows far slower than $lo g x$ (option B), which is the rate when you add $1/ n$ over all whole numbers. The doubled logarithm $lo g lo g x$ is genuinely tiny: even at $x = 1 0^{100}$ it is only about $5.4$ . Feedback-correct: the doubled logarithm is the signature rate of the prime reciprocal total. Feedback-wrong: the prime total does grow without bound, just glacially.

Formal definition Intermediate+

Throughout, $p$ ranges over primes, $lo g$ is the natural logarithm, and $Λ$ is the von Mangoldt function of 21.11.01: $Λ (n) = lo g p$ if $n = p^{m}$ for a prime $p$ and integer $m \geq 1$ , and $Λ (n) = 0$ otherwise. We follow Apostol ^{[Apostol Ch. 4]}.

Definition (Chebyshev functions). For real $x \geq 1$ , the Chebyshev theta function and Chebyshev psi function are $$ \vartheta(x) = \sum_{p \leq x} \log p, \qquad \psi(x) = \sum_{n \leq x} \Lambda(n) = \sum_{p^m \leq x} \log p = \sum_{m \geq 1} \vartheta!\big(x^{1/m}\big). $$ The last equality holds because $Λ (p^{m}) = lo g p$ contributes to $ψ (x)$ exactly when $p^{m} \leq x$ , i.e. $p \leq x^{1/ m}$ ; collecting the contribution at fixed exponent $m$ gives $ϑ (x^{1/ m})$ , and the sum over $m$ is finite since $ϑ (x^{1/ m}) = 0$ once $x^{1/ m} < 2$ , that is once $m > lo g_{2} x$ .

Definition (prime-counting function). As in 21.01.02, $π (x) = # {p \leq x}$ .

Definition (asymptotic relations). Write $f (x) \sim g (x)$ for $lim_{x \to \infty} f (x) / g (x) = 1$ , and $f (x) ≍ g (x)$ for the existence of constants $0 < c_{1} \leq c_{2}$ with $c_{1} g (x) \leq f (x) \leq c_{2} g (x)$ for all large $x$ . The average order of an arithmetic function $f$ refers to the asymptotics of the summatory function $\sum_{n \leq x} f (n)$ .

The three functions are linked at the level of size. Since $lo g p \leq lo g x$ for $p \leq x$ , summing gives $ϑ (x) \leq π (x) lo g x$ . The reverse comparison, restricting to primes in $(x^{1/2}, x]$ , shows $ϑ (x) \geq (π (x) - π (x^{1/2})) (\frac{1}{2} lo g x)$ . The two Chebyshev functions differ by a lower-order amount: $0 \leq ψ (x) - ϑ (x) = \sum_{m \geq 2} ϑ (x^{1/ m}) = O (x lo g x)$ , because $ϑ (t) \leq t lo g t$ and only $m \leq lo g_{2} x$ terms are nonzero. Hence $ψ (x) ≍ x ⟺ ϑ (x) ≍ x ⟺ π (x) ≍ x / lo g x$ , and likewise with $≍$ replaced by $\sim$ .

Counterexamples to common slips

" $ψ$ and $ϑ$ are the same function." They differ by the prime-power tail $\sum_{m \geq 2} ϑ (x^{1/ m})$ . At $x = 10$ , $ϑ (10) = lo g 210 \approx 5.35$ while $ψ (10) = lo g 2520 \approx 7.83$ ; the gap $lo g 12 = lo g (4 \cdot 9 \cdot \dots)$ comes from the powers $4, 8, 9$ . The gap is $O (x lo g x)$ , negligible against the main term $x$ but not zero.
" $π (x) \sim x / lo g x$ is an elementary theorem." The asymptotic equivalence with constant $1$ is the prime number theorem, which the elementary Chebyshev method does not deliver — it gives only the two-sided bound $π (x) ≍ x / lo g x$ . The step from $≍$ to $\sim$ requires either complex analysis (Hadamard-de la Vallée Poussin) or the Selberg-Erdős elementary argument, both deferred to 21.12.01.
" $\sum_{p \leq x} 1/ p$ converges because primes are sparse." It diverges, by Mertens' second theorem, at rate $lo g lo g x$ . Sparsity bounds the count but not the reciprocal sum; the harmonic weighting $1/ p$ decays slowly enough that the divergence survives.

Key theorem with proof Intermediate+

The signature theorem is Chebyshev's two-sided bound, proved by the elementary method: extract $ψ$ from the prime factorisation of factorials, with no appeal to $ζ (s)$ or complex analysis.

Theorem (Chebyshev's bounds). There exist absolute constants $0 < c_{1} < 1 < c_{2}$ such that for all sufficiently large $x$ , $$ c_1, x ;\leq; \psi(x) ;\leq; c_2, x. $$ One may take $c_{1} = lo g 2 \approx 0.693$ and $c_{2} = 2 lo g 2 \approx 1.386$ . Equivalently $ϑ (x) ≍ x$ and $π (x) ≍ x / lo g x$ .

Proof. The engine is the identity, valid for every integer $N \geq 1$ , $$ \log N! = \sum_{n \leq N} \Lambda(n) \left\lfloor \frac{N}{n} \right\rfloor, $$ which holds because $lo g N! = \sum_{n \leq N} lo g n = \sum_{n \leq N} \sum_{d ∣ n} Λ (d)$ (using $lo g = Λ * 1$ from 21.11.01), and reindexing the divisor sum by $d$ counts, for each $d$ , the multiples $d, 2 d, \dots \leq N$ , of which there are $⌊ N / d ⌋$ .

Upper bound. Consider the central binomial coefficient $(N 2 N) = (2 N)! / (N!)^{2}$ . Its logarithm is $$ \log \binom{2N}{N} = \log(2N)! - 2\log N! = \sum_{n \leq 2N}\Lambda(n)\left(\left\lfloor \frac{2N}{n}\right\rfloor - 2\left\lfloor \frac{N}{n}\right\rfloor\right). $$ Each bracket $⌊ 2 y ⌋ - 2 ⌊ y ⌋$ equals $0$ or $1$ , so every term is at most $Λ (n)$ , and the bracket vanishes for $n > 2 N$ (outside the summation range). Hence $$ \log\binom{2N}{N} ;\leq; \sum_{n \leq 2N}\Lambda(n) = \psi(2N). $$ On the other hand $(N 2 N)$ is the largest of the $2 N + 1$ terms summing to $(1 + 1)^{2 N} = 4^{N}$ , so $(N 2 N) \geq 4^{N} / (2 N + 1)$ , giving $lo g (N 2 N) \geq 2 N lo g 2 - lo g (2 N + 1)$ . Combining, $ψ (2 N) \geq 2 N lo g 2 - lo g (2 N + 1)$ , which is the lower bound at even arguments; we return to it below. For the upper bound we instead use that the bracket $⌊ 2 N / n ⌋ - 2 ⌊ N / n ⌋$ is $1$ for $N < n \leq 2 N$ (there $⌊ 2 N / n ⌋ = 1$ , $⌊ N / n ⌋ = 0$ ), so those terms alone contribute $ϑ (2 N) - ϑ (N)$ plus prime-power corrections; summing the telescoping inequality $ϑ (2 N) - ϑ (N) \leq lo g (N 2 N) \leq 2 N lo g 2$ over $N, 2 N, 4 N, \dots$ from a dyadic decomposition yields $ϑ (x) \leq (2 lo g 2) x$ for all $x \geq 1$ . Since $ψ (x) = ϑ (x) + O (x lo g x)$ , also $ψ (x) \leq (2 lo g 2) x + O (x lo g x) \leq c_{2} x$ for large $x$ .

Lower bound. From $ψ (2 N) \geq 2 N lo g 2 - lo g (2 N + 1)$ established above, and $ψ$ nondecreasing, every $x$ satisfies $ψ (x) \geq ψ (2 ⌊ x /2 ⌋) \geq 2 ⌊ x /2 ⌋ lo g 2 - lo g (2 ⌊ x /2 ⌋ + 1) \geq (lo g 2) x - O (lo g x) \geq c_{1} x$ for large $x$ . This gives the lower bound. Together, $c_{1} x \leq ψ (x) \leq c_{2} x$ . The transfer to $ϑ$ and to $π (x) ≍ x / lo g x$ uses the size comparisons of the Formal definition. $□$

Bridge. Chebyshev's bounds build toward 21.12.01 the prime number theorem, where the same factorial identity $lo g N! = \sum_{n} Λ (n) ⌊ N / n ⌋$ reappears as the elementary input to the Selberg symmetry formula, and this is exactly the elementary shadow of the analytic statement $ψ (x) \sim x$ that the contour integral of $- ζ^{'} (s) / ζ (s)$ delivers; the bounds appear again in 21.11.04 Perron's formula as the convergence estimates that make the truncated contour integral controllable. The central insight is that $ψ$ is recoverable from factorials because $lo g = Λ * 1$ in the convolution ring of 21.11.01, so divisor-sum identities convert directly into prime-counting estimates. Putting these together, the bound $ψ (x) ≍ x$ generalises into the precise $ψ (x) \sim x$ once one knows $ζ (1 + i t) \neq = 0$ , the bridge being the Mertens estimate $\sum_{n \leq x} Λ (n) / n = lo g x + O (1)$ proved next, which is dual to the average order $\sum_{n \leq x} lo g n = x lo g x - x + O (lo g x)$ .

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove that $ψ (x) - ϑ (x) = O (x lo g x)$ , and conclude $ψ (x) \sim x ⟺ ϑ (x) \sim x$ .

Hint

Write $ψ (x) - ϑ (x) = \sum_{m \geq 2} ϑ (x^{1/ m})$ . Use $ϑ (t) \leq t lo g t$ and count how many $m$ give a nonzero term.

Answer

From $ψ (x) = \sum_{m \geq 1} ϑ (x^{1/ m})$ , the difference is $ψ (x) - ϑ (x) = \sum_{m \geq 2} ϑ (x^{1/ m})$ . The summand vanishes once $x^{1/ m} < 2$ , i.e. $m > lo g_{2} x$ , so at most $lo g_{2} x$ terms survive. Each is bounded by $ϑ (x^{1/ m}) \leq ϑ (x) \leq x lo g x \leq \frac{1}{2} x lo g x$ for $m \geq 2$ . Hence $$ 0 \leq \psi(x) - \vartheta(x) \leq (\log_2 x)\cdot \tfrac12\sqrt x \log x = O(\sqrt x ,(\log x)^2), $$ and a sharper count (only $m = 2$ reaches order $x$ ; the rest are $O (x^{1/3} lo g x)$ ) gives $O (x lo g x)$ . Dividing by $x$ , the difference is $o (x)$ , so $ψ (x) / x$ and $ϑ (x) / x$ have the same limit; the equivalence of $ψ (x) \sim x$ and $ϑ (x) \sim x$ follows. Rubric: full credit for the tail estimate and the $o (x)$ conclusion.

Exercise 5 (medium, symbolic).

Prove Mertens' first theorem $\sum_{n \leq x} \frac{Λ ( n )}{n} = lo g x + O (1)$ , and deduce $\sum_{p \leq x} \frac{l o g p}{p} = lo g x + O (1)$ .

Hint

Start from $lo g ⌊ x ⌋! = \sum_{n \leq x} Λ (n) ⌊ x / n ⌋$ and the elementary estimate $lo g ⌊ x ⌋! = x lo g x - x + O (lo g x)$ . Replace $⌊ x / n ⌋$ by $x / n + O (1)$ and use $ψ (x) = O (x)$ .

Answer

By the factorial identity, $\sum_{n \leq x} Λ (n) ⌊ x / n ⌋ = lo g ⌊ x ⌋! = x lo g x - x + O (lo g x)$ (Stirling, elementary form). Write $⌊ x / n ⌋ = x / n - {x / n}$ with $0 \leq {x / n} < 1$ . Then $$ x\sum_{n \leq x}\frac{\Lambda(n)}{n} - \sum_{n \leq x}\Lambda(n){x/n} = x\log x - x + O(\log x). $$ The error sum is bounded by $\sum_{n \leq x} Λ (n) = ψ (x) = O (x)$ (Chebyshev). Dividing through by $x$ : $$ \sum_{n \leq x}\frac{\Lambda(n)}{n} = \log x - 1 + O(1) + O(\tfrac{\log x}{x}) = \log x + O(1). $$ To pass to primes, the prime-power tail $\sum_{n \leq x} Λ (n) / n - \sum_{p \leq x} lo g p / p = \sum_{p^{m} \leq x, m \geq 2} lo g p / p^{m}$ converges (dominated by $\sum_{p} lo g p \sum_{m \geq 2} p^{- m} = \sum_{p} lo g p / (p (p - 1)) < \infty$ ), so it is $O (1)$ . Hence $\sum_{p \leq x} lo g p / p = lo g x + O (1)$ . Rubric: full credit for the floor-removal, the $ψ (x) = O (x)$ input, and the convergent prime-power tail.

Exercise 6 (medium, symbolic).

Assuming Mertens' first theorem and Abel summation, derive the form of Mertens' second theorem $\sum_{p \leq x} 1/ p = lo g lo g x + M + o (1)$ (you need not evaluate $M$ ).

Hint

Apply partial summation with $a_{p} = (lo g p) / p$ and weight $1/ lo g p$ , so $\sum_{p \leq x} 1/ p = \sum_{p \leq x} a_{p} \cdot \frac{1}{l o g p}$ . Use $A (t) = \sum_{p \leq t} (lo g p) / p = lo g t + R (t)$ with $R (t) = O (1)$ .

Answer

Set $A (t) = \sum_{p \leq t} (lo g p) / p = lo g t + R (t)$ , $R (t) = O (1)$ by Mertens I. Abel summation against the decreasing weight $w (t) = 1/ lo g t$ gives $$ \sum_{p \leq x}\frac1p = \sum_{p \leq x}\frac{\log p}{p}\cdot\frac{1}{\log p} = \frac{A(x)}{\log x} + \int_2^x \frac{A(t)}{t(\log t)^2},dt. $$ Substituting $A (t) = lo g t + R (t)$ : the boundary term is $1 + O (1/ lo g x)$ , and the integral splits as $\int_{2}^{x} \frac{d t}{t l o g t} + \int_{2}^{x} \frac{R ( t )}{t ( l o g t ) ^{2}} d t = lo g lo g x - lo g lo g 2 + C + o (1)$ , since the first integral is $lo g lo g x + O (1)$ and the second converges (its integrand is $O (1/ (t (lo g t)^{2}))$ , integrable to $\infty$ ). Collecting the constants into $M$ gives $\sum_{p \leq x} 1/ p = lo g lo g x + M + o (1)$ . Rubric: full credit for the correct partial-summation setup and identifying the $\int d t / (t lo g t) = lo g lo g x$ main term and the convergent remainder.

Exercise 7 (hard, symbolic).

Prove Bertrand's postulate by Erdős's method: for every integer $n \geq 1$ there is a prime $p$ with $n < p \leq 2 n$ . (You may assume the primorial bound $\prod_{p \leq m} p < 4^{m}$ and verify small $n$ by exhibiting primes $2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631$ .)

Hint

Suppose no prime lies in $(n, 2 n]$ . Bound the prime factorisation of $(n 2 n)$ : every prime factor is $\leq 2 n /3$ (no prime in $(n, 2 n]$ , and primes in $(2 n /3, n]$ do not divide $(n 2 n)$ ); prime powers $p^{r} ∥ (n 2 n)$ satisfy $p^{r} \leq 2 n$ ; only primes $\leq 2 n$ can appear with exponent $\geq 2$ . Contradict $(n 2 n) \geq 4^{n} / (2 n + 1)$ .

Answer

Write $(n 2 n) = \prod_{p} p^{r_{p}}$ . By Kummer/Legendre, $p^{r_{p}} \leq 2 n$ for every $p$ (the exponent $r_{p} = \sum_{j \geq 1} (⌊ 2 n / p^{j} ⌋ - 2 ⌊ n / p^{j} ⌋)$ is a sum of $0/1$ brackets, nonzero only for $p^{j} \leq 2 n$ ). Three facts cut the product down. First, primes $p > 2 n$ have $r_{p} \leq 1$ . Second, primes in $(2 n /3, n]$ satisfy $r_{p} = 0$ : for such $p$ , $2 p \leq 2 n < 3 p$ , so in the factorials only $⌊ 2 n / p ⌋ = 2$ , $⌊ n / p ⌋ = 1$ , bracket $0$ , and higher powers exceed $2 n$ . Third, by hypothesis no prime lies in $(n, 2 n]$ . Hence every prime factor is $\leq 2 n /3$ , and $$ \binom{2n}{n} ;\leq; \underbrace{\prod_{p \leq \sqrt{2n}} 2n}{\text{powers}} \cdot \underbrace{\prod{\sqrt{2n} < p \leq 2n/3} p}{\text{exponent }1} ;\leq; (2n)^{\sqrt{2n}} \cdot \prod{p \leq 2n/3} p ;<; (2n)^{\sqrt{2n}}, 4^{2n/3}, $$ using the primorial bound. Against the lower bound $(n 2 n) \geq 4^{n} / (2 n + 1)$ : $$ \frac{4^n}{2n+1} < (2n)^{\sqrt{2n}},4^{2n/3} ;\Longrightarrow; 4^{n/3} < (2n+1)(2n)^{\sqrt{2n}} \leq (2n)^{\sqrt{2n}+1}. $$ Taking logarithms, $(n /3) lo g 4 < (2 n + 1) lo g (2 n)$ , which fails for all $n \geq 468$ (the left side is linear in $n$ , the right side $O (n lo g n)$ ). So for $n \geq 468$ a prime must lie in $(n, 2 n]$ . For $n < 468$ , the explicit chain $2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631$ — each less than twice its predecessor — covers every interval $(n, 2 n]$ . $□$ Rubric: full credit for the three exponent facts, the product bound, and the asymptotic contradiction; the small- $n$ chain may be cited.

Exercise 8 (hard, symbolic).

Prove the product form of Mertens' third theorem, $\prod_{p \leq x} (1 - 1/ p)^{- 1} \sim e^{γ} lo g x$ , assuming the second theorem $\sum_{p \leq x} 1/ p = lo g lo g x + M + o (1)$ with $M$ the Meissel-Mertens constant, and the identity $M = γ - \sum_{p} (lo g (1 - 1/ p)^{- 1} - 1/ p)$ .

Hint

Take logarithms of the product and expand $lo g (1 - 1/ p)^{- 1} = 1/ p + (lo g (1 - 1/ p)^{- 1} - 1/ p)$ . The correction sum converges; combine with Mertens II.

Answer

Let $P (x) = \prod_{p \leq x} (1 - 1/ p)^{- 1}$ . Then $$ \log P(x) = \sum_{p \leq x}\log(1 - 1/p)^{-1} = \sum_{p \leq x}\frac1p + \sum_{p \leq x}\Big(\log(1-1/p)^{-1} - \frac1p\Big). $$ The correction terms are $lo g (1 - 1/ p)^{- 1} - 1/ p = \sum_{k \geq 2} 1/ (k p^{k}) = O (1/ p^{2})$ , so the second sum converges to a constant $C = \sum_{p} (lo g (1 - 1/ p)^{- 1} - 1/ p)$ , with tail $o (1)$ . By Mertens II the first sum is $lo g lo g x + M + o (1)$ . Hence $$ \log P(x) = \log\log x + M + C + o(1). $$ The stated identity $M = γ - C$ gives $M + C = γ$ , so $lo g P (x) = lo g lo g x + γ + o (1)$ . Exponentiating, $P (x) = e^{γ} lo g x \cdot e^{o (1)} \sim e^{γ} lo g x$ . Rubric: full credit for the convergent-correction split, the use of Mertens II for the main term, and the identification $M + C = γ$ . Note the $e^{γ}$ (not $e^{- γ}$ ) appears because the product is the reciprocal $(1 - 1/ p)^{- 1}$ ; the form $\prod_{p \leq x} (1 - 1/ p) \sim e^{- γ} / lo g x$ is the same statement inverted.

Lean formalization Intermediate+

Mathlib carries the von Mangoldt function and a formalised Bertrand's postulate, so the central statements of this unit are expressible. The companion notes record the load-bearing declarations against Mathlib.NumberTheory.VonMangoldt and Mathlib.NumberTheory.Bertrand.

-- Operative imports: Mathlib.NumberTheory.VonMangoldt,
-- Mathlib.NumberTheory.Bertrand, Mathlib.Analysis.SpecialFunctions.Log.Basic
import Mathlib.NumberTheory.VonMangoldt
import Mathlib.NumberTheory.Bertrand
open ArithmeticFunction

-- The von Mangoldt function Λ; ψ(x) = ∑_{n ≤ x} Λ(n) is its summatory function.
#check (vonMangoldt : ArithmeticFunction ℝ)
#check @ArithmeticFunction.vonMangoldt_apply
-- vonMangoldt n = if IsPrimePow n then Real.log (minFac n) else 0

-- Λ * ζ = log : the identity log = Λ * 𝟙 driving the factorial identity
-- log N! = ∑_{n ≤ N} Λ(n) ⌊N/n⌋.
#check @ArithmeticFunction.vonMangoldt_mul_zeta
-- vonMangoldt * ↑ζ = log

-- Bertrand's postulate, formalised (Erdős proof, via the central binomial bound):
#check @Nat.bertrand
-- Nat.bertrand : ∀ (n : ℕ), n ≠ 0 → ∃ p, Nat.Prime p ∧ n < p ∧ p ≤ 2 * n

-- The central-binomial lower bound 4^n/(2n+1) ≤ C(2n, n), the engine of both
-- Chebyshev's lower bound and Erdős's Bertrand proof:
#check @Nat.four_pow_lt_mul_centralBinom
#check @Nat.centralBinom

The gap documented in the unit metadata's Mathlib gap analysis is not the absence of $Λ$ or of Bertrand — Mathlib has both — but the absence of a single module proving the two-sided Chebyshev bound $c_{1} x \leq ψ (x) \leq c_{2} x$ from the factorial identity, the equivalence $ψ (x) \sim x ⟺ ϑ (x) \sim x ⟺ π (x) \sim x / lo g x$ , and the three Mertens theorems with the constants $M$ and $e^{γ}$ , end to end and in one place.

Advanced results Master

Theorem 1 (the equivalence of the three asymptotic forms). The relations $ψ (x) \sim x$ , $ϑ (x) \sim x$ , and $π (x) \sim x / lo g x$ are equivalent ^{[Apostol Ch. 4]}. The first two are equivalent because $ψ - ϑ = O (x lo g x) = o (x)$ . The equivalence with $π (x) \sim x / lo g x$ follows from Abel summation in both directions: $ϑ (x) = \sum_{p \leq x} lo g p = π (x) lo g x - \int_{2}^{x} π (t) / t d t$ , so $ϑ (x) / x \to 1$ forces $π (x) lo g x / x \to 1$ , and conversely $π (x) = ϑ (x) / lo g x + \int_{2}^{x} ϑ (t) / (t (lo g t)^{2}) d t$ recovers $π (x) \sim x / lo g x$ from $ϑ (x) \sim x$ . This equivalence reduces the prime number theorem to the single analytic statement $ψ (x) \sim x$ , which is the form the contour method of 21.12.01 proves.

Theorem 2 (Chebyshev's explicit constants). Chebyshev 1852 ^{[Chebyshev 1852]} obtained the sharper bounds $A x / lo g x \leq π (x) \leq \frac{6}{5} A x / lo g x$ for large $x$ , with $A = lo g (2^{1/2} 3^{1/3} 5^{1/5} 3 0^{- 1/30}) \approx 0.92129$ , by combining the factorial identity at the four arguments $x, x /2, x /3, x /5, x /30$ into the linear form $ψ (x) - ψ (x /2) - ψ (x /3) - ψ (x /5) + ψ (x /30)$ , whose coefficients are chosen so the associated combination of $lo g ⌊ \cdot ⌋!$ telescopes. These constants straddle $1$ — Chebyshev's method cannot bring them together — which is exactly why $π (x) \sim x / lo g x$ (constant exactly $1$ ) lies beyond the elementary range and required the analytic methods of 21.12.01.

Theorem 3 (Bertrand's postulate; Chebyshev 1852, Erdős 1932). For every integer $n \geq 1$ there is a prime in $(n, 2 n]$ ^{[Chebyshev 1852]} ^{[Erdős 1932]}. Chebyshev deduced it from his lower bound on $π (2 n) - π (n)$ ; Erdős's elementary proof (Exercise 7) reads the postulate off the prime factorisation of $(n 2 n)$ , using $(n 2 n) \geq 4^{n} / (2 n + 1)$ , the vanishing of $r_{p}$ for $p \in (2 n /3, n]$ , the prime-power cap $p^{r_{p}} \leq 2 n$ , and the primorial bound $\prod_{p \leq m} p < 4^{m}$ . The same machinery yields the refinement that for any $ε > 0$ there is a prime in $(n, (1 + ε) n]$ for all large $n$ , since the Chebyshev band has multiplicative width below $2$ .

Theorem 4 (Mertens' three theorems; Mertens 1874). With $γ$ the Euler-Mascheroni constant and $M = 0.2614972128 \dots$ the Meissel-Mertens constant ^{[Mertens 1874]}, $$ \sum_{p \leq x}\frac{\log p}{p} = \log x + O(1), \quad \sum_{p \leq x}\frac1p = \log\log x + M + O!\Big(\frac{1}{\log x}\Big), \quad \prod_{p \leq x}\Big(1 - \frac1p\Big)^{-1} \sim e^{\gamma}\log x. $$ The first is proved (Exercise 5) from $lo g ⌊ x ⌋! = x lo g x - x + O (lo g x)$ and $ψ (x) = O (x)$ ; the second from the first by Abel summation (Exercise 6); the third from the second by expanding the logarithm of the product (Exercise 8). All three use only Chebyshev-grade input — no PNT, no zeta zeros. The product form is the prime-product backbone of sieve theory: the heuristic "probability that $n \leq x$ survives sieving by all $p \leq z$ " is $\prod_{p \leq z} (1 - 1/ p) \sim e^{- γ} / lo g z$ , and the factor $e^{- γ}$ is the source of the celebrated parity-barrier constant in the linear sieve.

Theorem 5 (Shapiro's Tauberian theorem). Apostol's Theorem 4.8 ^{[Apostol Ch. 4]}: if ${a_{n}}$ are nonnegative and $\sum_{n \leq x} a_{n} ⌊ x / n ⌋ = x lo g x + O (x)$ , then $\sum_{n \leq x} a_{n} / n = lo g x + O (1)$ , and moreover $\sum_{n \leq x} a_{n} ≍ x$ . Applied to $a_{n} = Λ (n)$ it produces Mertens I and the Chebyshev order $ψ (x) ≍ x$ in one stroke from the factorial identity, abstracting the elementary core of this unit. Shapiro's theorem is the precise statement of how an average-order estimate against $⌊ x / n ⌋$ upgrades to a $1/ n$ -weighted estimate, the recurring move from 21.11.01 average orders to prime counting.

Synthesis. The elementary prime-counting estimates are the foundational reason the prime number theorem is plausible before it is provable: Chebyshev's $ψ (x) ≍ x$ already locates $π (x)$ within a constant factor of $x / lo g x$ , and this is exactly the bridge from the convolution identity $lo g = Λ * 1$ of 21.11.01 to the analytic $ψ (x) \sim x$ of 21.12.01. The central insight is that all of this content is squeezed out of one identity, $lo g N! = \sum_{n} Λ (n) ⌊ N / n ⌋$ , by elementary manipulation of factorials and binomial coefficients; the factorial encodes the multiplicative structure of the integers, and differencing it (as in $(N 2 N)$ ) isolates the primes. Putting these together, Mertens' theorems are dual to the average-order estimates of 21.11.01: where $\sum_{n \leq x} d (n) \sim x lo g x$ measures divisors, $\sum_{p \leq x} (lo g p) / p \sim lo g x$ measures primes, and both descend from partial summation against a Dirichlet-convolution identity. The pattern generalises: Shapiro's Tauberian theorem is the abstract engine, the Selberg symmetry formula $\sum_{n \leq x} Λ (n) lo g n + \sum_{mn \leq x} Λ (m) Λ (n) = 2 x lo g x + O (x)$ is its second-order refinement, and the elementary proof of the full PNT in 21.12.01 is what one obtains by pushing this differencing one level deeper. The bridge is everywhere the factorial identity; Chebyshev saw it, Mertens summed against it, Erdős differenced it, and the analytic theory only sharpens the constant from $≍$ to $\sim$ .

Full proof set Master

Proposition 1 (factorial identity). For every integer $N \geq 1$ , $lo g N! = \sum_{n \leq N} Λ (n) ⌊ N / n ⌋$ .

Proof. From $lo g = Λ * 1$ in the convolution ring of 21.11.01, for each $m$ we have $lo g m = \sum_{d ∣ m} Λ (d)$ . Summing over $m \leq N$ , $$ \log N! = \sum_{m \leq N}\log m = \sum_{m \leq N}\sum_{d \mid m}\Lambda(d) = \sum_{d \leq N}\Lambda(d),#{m \leq N : d \mid m} = \sum_{d \leq N}\Lambda(d)\left\lfloor \frac{N}{d}\right\rfloor, $$ where the third equality swaps the order of summation, grouping by the divisor $d$ , and the count of multiples of $d$ up to $N$ is $⌊ N / d ⌋$ . $□$

Proposition 2 (Abel/partial summation). Let $a_{n}$ be complex, $A (t) = \sum_{n \leq t} a_{n}$ , and $g$ continuously differentiable on $[1, x]$ . Then $$ \sum_{n \leq x}a_n g(n) = A(x)g(x) - \int_1^x A(t)g'(t),dt. $$

Proof. Write $a_{n} = A (n) - A (n - 1)$ and sum by parts over $1 \leq n \leq ⌊ x ⌋$ : $$ \sum_{n \leq x}a_n g(n) = \sum_{n}(A(n) - A(n-1))g(n) = A(\lfloor x\rfloor)g(\lfloor x\rfloor) - \sum_{n \leq \lfloor x\rfloor - 1}A(n)(g(n+1) - g(n)). $$ Since $A$ is constant on $[n, n + 1)$ , $A (n) (g (n + 1) - g (n)) = \int_{n}^{n + 1} A (t) g^{'} (t) d t$ , and $A (⌊ x ⌋) g (⌊ x ⌋) = A (x) g (x) - \int_{⌊ x ⌋}^{x} A (t) g^{'} (t) d t$ because $A (t) = A (x)$ there. Assembling the integrals over $[1, x]$ yields the stated formula. $□$

Proposition 3 (the prime-power tail is bounded). $\sum_{p} \sum_{m \geq 2} \frac{l o g p}{p ^{m}}$ converges; hence $ψ (x) - ϑ (x) = \sum_{p^{m} \leq x, m \geq 2} lo g p$ has the bound $O (x lo g x)$ and the reciprocal tail $\sum_{p, m \geq 2} lo g p / p^{m} = O (1)$ .

Proof. For fixed $p$ , $\sum_{m \geq 2} p^{- m} = p^{- 2} / (1 - p^{- 1}) = 1/ (p (p - 1))$ , so $\sum_{p} lo g p \sum_{m \geq 2} p^{- m} = \sum_{p} \frac{l o g p}{p ( p - 1 )}$ , which converges by comparison with $\sum_{n} (lo g n) / n^{2} < \infty$ . For the unweighted difference, $ψ (x) - ϑ (x) = \sum_{m \geq 2} ϑ (x^{1/ m})$ ; the term $m = 2$ contributes $ϑ (x) \leq x lo g x = O (x lo g x)$ , and the remaining $m \geq 3$ terms total $O (x^{1/3} lo g x)$ , with at most $lo g_{2} x$ nonzero terms. Hence the difference is $O (x lo g x)$ . $□$

Proposition 4 (lower bound on $π (x) - π (x /2)$ refines Bertrand). For all large $x$ , $π (x) - π (x /2) \geq c x / lo g x$ for an absolute constant $c > 0$ ; in particular $(x /2, x]$ contains $≫ x / lo g x$ primes, a quantitative Bertrand.

Proof. From $ϑ (x) - ϑ (x /2) = \sum_{x /2 < p \leq x} lo g p \leq (π (x) - π (x /2)) lo g x$ , it suffices to bound $ϑ (x) - ϑ (x /2)$ below by $≫ x$ . The central binomial gives $lo g (N 2 N) \geq 2 N lo g 2 - lo g (2 N + 1)$ , and the only primes contributing with exponent forcing a lower bound lie in $(N, 2 N]$ together with prime-power corrections of size $O (N lo g N)$ ; isolating them, $ϑ (2 N) - ϑ (N) \geq lo g (N 2 N) - O (N (lo g N)^{2}) \geq 2 N lo g 2 - O (N (lo g N)^{2})$ . Thus $ϑ (x) - ϑ (x /2) \geq (lo g 2) \frac{x}{2} \cdot (1 + o (1)) ≫ x$ , whence $π (x) - π (x /2) \geq c x / lo g x$ . The strict positivity for every $n$ (not merely large $n$ ) is Bertrand's postulate, with small cases checked directly. $□$

Connections Master

The factorial identity and the von Mangoldt function used throughout are the convolution identity $lo g = Λ * 1$ of 21.11.01; the entire Chebyshev method is partial summation against that single Dirichlet-convolution relation, and the average-order machinery (hyperbola method, $\sum_{n \leq x} d (n) \sim x lo g x$ ) developed there is the divisor-counting analogue of the prime-counting estimates here.
These elementary bounds are the prelude to 21.12.01 the prime number theorem: Chebyshev's $ψ (x) ≍ x$ is sharpened to $ψ (x) \sim x$ by the contour integral of $- ζ^{'} (s) / ζ (s)$ , and the factorial identity reappears in the Selberg symmetry formula underlying the elementary (complex-analysis-free) PNT proof.
The convergence estimate $ψ (x) = O (x)$ supplies the absolute-convergence and truncation control needed in 21.11.04 Perron's formula and Mellin inversion, where the summatory function of a Dirichlet series is recovered by a vertical contour integral whose error term is governed by Chebyshev-grade bounds on the coefficients.
The primes $p \leq x$ counted here index the Euler product of 21.03.01 the Riemann zeta function; Mertens' third theorem $\prod_{p \leq x} (1 - 1/ p)^{- 1} \sim e^{γ} lo g x$ is the partial Euler product at $s = 1$ , and the divergence rate $lo g lo g x$ of $\sum 1/ p$ is the elementary trace of the pole of $ζ$ at $s = 1$ .
The infinitude and fundamental-theorem apparatus of 21.01.02 is the substrate: the factorisation of $(n 2 n)$ that powers Bertrand, and the unique-factorisation count behind $lo g N! = \sum_{n} Λ (n) ⌊ N / n ⌋$ , both rest on the prime factorisation theory established there.

Historical & philosophical context Master

Pafnuty Chebyshev's 1852 memoir Sur les nombres premiers ^{[Chebyshev 1852]} gave the first rigorous control on the density of primes, three decades after Legendre and Gauss had conjectured $π (x) \sim x / lo g x$ from numerical tables. Chebyshev introduced the functions now bearing his name and proved $0.921 x / lo g x \leq π (x) \leq 1.106 x / lo g x$ for large $x$ , together with the first proof of the conjecture that Joseph Bertrand had stated in 1845 and verified by hand to three million. Chebyshev's method was entirely elementary, resting on the arithmetic of factorials, and it established the order of $π (x)$ while leaving the exact constant out of reach.

Franz Mertens's 1874 paper in Crelle's journal ^{[Mertens 1874]} sharpened the elementary theory into the three asymptotic identities for $\sum (lo g p) / p$ , $\sum 1/ p$ , and $\prod (1 - 1/ p)^{- 1}$ , isolating the constants $M$ and $e^{γ}$ . Mertens's second theorem made precise Euler's 1737 observation that $\sum 1/ p$ diverges, pinning the rate at $lo g lo g x$ . The young Paul Erdős, in his 1932 debut paper ^{[Erdős 1932]}, recast Bertrand's postulate as a transparent estimate on the prime factorisation of the central binomial coefficient, a proof so clean it became the canonical one. The gap between the Chebyshev band and the true constant $1$ stood until 1896, when Hadamard and de la Vallée Poussin proved $π (x) \sim x / lo g x$ using the complex analysis of $ζ (s)$ ; the elementary route to the same limit was found by Selberg and Erdős in 1948-49.

Bibliography Master

@article{chebyshev1852,
  author  = {Chebyshev, Pafnuty L.},
  title   = {M\'{e}moire sur les nombres premiers},
  journal = {Journal de Math\'{e}matiques Pures et Appliqu\'{e}es},
  volume  = {17},
  pages   = {366--390},
  year    = {1852}
}

@article{erdos1932bertrand,
  author  = {Erd\H{o}s, Paul},
  title   = {Beweis eines Satzes von Tschebyschef},
  journal = {Acta Litterarum ac Scientiarum (Szeged)},
  volume  = {5},
  pages   = {194--198},
  year    = {1932}
}

@article{mertens1874,
  author  = {Mertens, Franz},
  title   = {Ein Beitrag zur analytischen Zahlentheorie},
  journal = {Journal f\"{u}r die reine und angewandte Mathematik (Crelle)},
  volume  = {78},
  pages   = {46--62},
  year    = {1874}
}

@book{apostol1976ant,
  author    = {Apostol, Tom M.},
  title     = {Introduction to Analytic Number Theory},
  series    = {Undergraduate Texts in Mathematics},
  publisher = {Springer-Verlag},
  year      = {1976},
  note      = {Chapter 4: Chebyshev functions, Bertrand, Mertens, Shapiro}
}

@book{tenenbaum2015,
  author    = {Tenenbaum, G\'{e}rald},
  title     = {Introduction to Analytic and Probabilistic Number Theory},
  edition   = {3},
  series    = {Graduate Studies in Mathematics},
  volume    = {163},
  publisher = {American Mathematical Society},
  year      = {2015}
}

@book{hardywright2008,
  author    = {Hardy, G. H. and Wright, E. M.},
  title     = {An Introduction to the Theory of Numbers},
  edition   = {6},
  publisher = {Oxford University Press},
  year      = {2008},
  note      = {Revised by D. R. Heath-Brown and J. H. Silverman; Chapter XXII}
}

Prerequisites

21.11.01
21.01.02

Tier anchors

beginner: Burton 2010 *Elementary Number Theory* 7e §3-4 (the density of primes, Bertrand's postulate stated and verified numerically); 3Blue1Brown 'Why do prime numbers make these spirals?' for the prime-density viewpoint
intermediate: Apostol 1976 *Introduction to Analytic Number Theory* (Springer UTM) Ch. 4 (the Chebyshev functions $\vartheta$ and $\psi$, Chebyshev's bounds, Mertens' theorems, Shapiro's Tauberian theorem); Hardy-Wright 2008 *An Introduction to the Theory of Numbers* 6e (Oxford) Ch. XXII
master: Apostol 1976 *Introduction to Analytic Number Theory* Ch. 4 (the elementary prime-counting estimates preceding the analytic PNT); Chebyshev 1852 *J. Math. Pures Appl.* 17 (the original bounds and the first proof of Bertrand's postulate); Erdős 1932 *Acta Litt. Sci. Szeged* 5 (the binomial-coefficient proof of Bertrand); Mertens 1874 *Crelle* 78 (the three theorems); Tenenbaum 2015 *Introduction to Analytic and Probabilistic Number Theory* 3e (Cambridge UP) §I.1-I.3 (Abel summation, Mertens with explicit error terms)

References

Apostol, T. M. — Introduction to Analytic Number Theory · Springer Undergraduate Texts in Mathematics (1976). Chapter 4 defines the Chebyshev functions $\vartheta(x) = \sum_{p \leq x} \log p$ and $\psi(x) = \sum_{n \leq x} \Lambda(n)$, proves the relation $\psi(x) = \sum_{m \geq 1} \vartheta(x^{1/m})$ and the equivalence $\vartheta(x) \sim x \iff \psi(x) \sim x \iff \pi(x) \sim x/\log x$, establishes Chebyshev's elementary bounds $\psi(x) \asymp x$, derives the three Mertens theorems by Abel summation against the estimate $\sum_{n \leq x} \Lambda(n)/n = \log x + O(1)$, and proves Shapiro's Tauberian theorem. The analytic von Mangoldt machinery $-\zeta'/\zeta$ and the full PNT are deferred to Chapters 11-13.
Chebyshev, P. L. — Mémoire sur les nombres premiers · *Journal de Mathématiques Pures et Appliquées* 17 (1852), 366-390. The first rigorous proof of Bertrand's postulate, together with the explicit bounds $0.92129\,x/\log x \leq \pi(x) \leq 1.10555\,x/\log x$ for large $x$, derived from estimates on $\log(n!)$ and the central binomial coefficient via the function now written $\psi(x)$.
Erdős, P. — Beweis eines Satzes von Tschebyschef · *Acta Litterarum ac Scientiarum (Szeged)* 5 (1932), 194-198. Erdős's elementary proof of Bertrand's postulate (his first published paper, at age 19), built on the prime factorisation of the central binomial coefficient $\binom{2n}{n}$, the bound $\binom{2n}{n} \geq 4^n/(2n+1)$, the absence of prime factors in $(2n/3, n]$, and the bound on the primorial $\prod_{p \leq x} p < 4^x$.
Mertens, F. — Ein Beitrag zur analytischen Zahlentheorie · *Journal für die reine und angewandte Mathematik (Crelle)* 78 (1874), 46-62. Proves the three theorems: (i) $\sum_{p \leq x} (\log p)/p = \log x + O(1)$, (ii) $\sum_{p \leq x} 1/p = \log\log x + M + O(1/\log x)$ with $M = 0.2614972128\ldots$ the Meissel-Mertens constant, and (iii) $\prod_{p \leq x}(1 - 1/p)^{-1} \sim e^{\gamma} \log x$ with $\gamma$ the Euler-Mascheroni constant.
Hardy, G. H. & Wright, E. M. — An Introduction to the Theory of Numbers · Oxford University Press, 6th edition (2008), revised by D. R. Heath-Brown and J. H. Silverman. Chapter XXII contains the Chebyshev bounds, Bertrand's postulate, the three Mertens theorems, and the elementary prelude to the prime number theorem.
Tenenbaum, G. — Introduction to Analytic and Probabilistic Number Theory · Cambridge University Press, 3rd edition (2015), §I.1-I.3. Abel (partial) summation as the master tool, the Chebyshev estimates with explicit constants, the Mertens theorems with $O(1/\log x)$ error, and the passage from average orders to the elementary prime-counting estimates.

Estimated time

beginner: 18m
intermediate: 44m
master: 88m