Questions: Prime Counting Function and Chebyshev Bounds

Question 1

The prime number theorem states π(x) ~ x/ln(x). What does Chebyshev's earlier work establish, and how does it differ?

• A. π(x) = x/ln(x) exactly for all sufficiently large x
• B. π(x) is bounded between two positive constants times x/ln(x), establishing the correct order of magnitude without the exact asymptotic
• C. π(x) grows faster than x/ln(x) by a logarithmic correction factor
• D. π(x) ≈ x/ln(x) − x/ln²(x), giving the first two terms of the asymptotic expansion

Answer: (B)

Chebyshev proved that 0.92x/ln(x) < π(x) < 1.1x/ln(x) for large x — the right *order of magnitude* — using only elementary binomial coefficient bounds. The prime number theorem (π(x)/[x/ln(x)] → 1 exactly) required completely different analytic tools (Riemann zeta function) and wasn't proved until 1896, 40+ years later. Bounding between constants times x/ln(x) and proving the constant is exactly 1 are genuinely different achievements.

Question 2

Chebyshev's proof of Bertrand's postulate uses the binomial coefficient (2n choose n). What is the key role of primes in the interval (n, 2n) in the argument?

• A. Primes in (n, 2n) are the only primes that divide (2n choose n), so their existence follows from a lower bound on the coefficient
• B. If no prime exists in (n, 2n), then (2n choose n) would be forced below its known lower bound — a contradiction proving at least one prime must exist there
• C. Primes in (n, 2n) contribute exactly one factor each to (2n choose n), allowing us to count them directly
• D. The largest prime factor of (2n choose n) always lies in (n, 2n), which directly counts primes in that range

Answer: (B)

The proof works by contradiction. (2n choose n) is bounded below (it's at least 4^n / (2n+1)) and bounded above by a product excluding primes in (n, 2n). If no primes existed in (n, 2n), those primes would contribute nothing to (2n choose n), making the upper bound too small to accommodate the lower bound. The contradiction forces at least one prime to exist in that interval — Bertrand's postulate.

Question 3

Chebyshev studied auxiliary functions θ(x) = Σ ln(p) and ψ(x) = Σ ln(p^k) over primes and prime powers ≤ x, rather than π(x) directly, because these functions are smoother and more tractable.

• T. True
• F. False

Answer: True

The prime-counting function π(x) is a jagged step function that jumps by 1 at each prime — analytically difficult to work with directly. The weighted sums θ(x) and ψ(x) are better behaved as analytic objects and can be related to π(x) through summation by parts. Showing θ(x) ~ x or ψ(x) ~ x is essentially equivalent to the prime number theorem, but the smoother objects are more amenable to the binomial coefficient bounding technique Chebyshev used.

Question 4

Chebyshev's bounds directly imply the prime number theorem, because proving π(x) lies between constants times x/ln(x) is the same as proving π(x)/(x/ln(x)) → 1.

• T. True
• F. False

Answer: False

This is a common conflation. Sandwiching π(x) between 0.92x/ln(x) and 1.1x/ln(x) proves the correct order of magnitude — the ratio π(x)/(x/ln(x)) is bounded between 0.92 and 1.1 — but this is strictly weaker than the prime number theorem, which asserts the ratio converges to exactly 1. Closing the gap between 'bounded by constants' and 'exact asymptotics' required the analytic theory of ζ(s), developed by Riemann and proved complete by Hadamard and de la Vallée Poussin in 1896.

Question 5

Why did Chebyshev study θ(x) and ψ(x) instead of directly bounding π(x), and what is the relationship between these functions?

Model answer: θ(x) and ψ(x) are weighted sums (logarithmic weights on primes and prime powers) that are analytically smoother than the step function π(x). The connection is that θ(x) ~ x implies π(x) ~ x/ln(x), via summation by parts (or Abel summation). Chebyshev could bound (2n choose n) using products involving primes, which translates naturally into bounds on ψ(x) rather than on π(x) directly. Working with the smoother auxiliary functions made the binomial coefficient approach tractable, while direct bounds on the jagged π(x) would have been much harder to obtain.

The substitution of smoother functions for harder ones is a recurring strategy in analytic number theory. The functions θ and ψ encode the same information as π but in a form that interacts more naturally with multiplicative structure (products of primes) and analytic tools. Understanding this substitution — rather than memorizing Chebyshev's constants — is the key takeaway: the art is in choosing the right object to study.