Betrand Postulate : Erdos( 1932)

The theorem, known as Bertrand’s Postulate, asserts that for any integer $n \ge 1$ , there is always a prime number $p$ satisfying $n < p \le 2n$ .

Erdős’s proof (1932) is centered on a careful analysis of the prime factors of the central binomial coefficient, $M = \binom{2n}{n}$ .

Click to access 1932-01.pdf

Contradiction Hypothesis: Assume there exists an integer $n$ for which no prime p exists in the interval $(n, 2n]$ .

The strategy is to derive a restrictive upper bound on $\binom{2n}{n}$ that flows from this hypothesis, and show that for sufficiently large n, this upper bound falls below a known, simple lower bound, leading to an contradiction.

The Lower Bound on $\binom{2n}{n}$

As the largest term in the sum $\sum_{k=0}^{2n}\binom{2n}{k} = 4^n$ , a simple lower bound is: $\binom{2n}{n} \ge \frac{4^n}{2n+1}$

An Upper Bound from the Hypothesis

We now analyze the prime factorization $\binom{2n}{n} = \prod_{p} p^{v_p(\binom{2n}{n})}$ , where $v_p(k)$ denotes the exponent of prime $p$ in the factorization of $k$ . Our hypothesis imposes severe constraints on this product.

Erdős’s Crucial Observations:

Large Primes ( $p > n$ ): By hypothesis, no primes exist in $(n, 2n]$ . Any prime $p > 2n$ is clearly not a factor.
Intermediate Primes ( $2n/3 < p \le n$ ): For a prime $p$ in this range, the only multiples of $p$ less than or equal to $2n$ are $p$ and $2p$ . The denominator $(n!)^2$ contains the factor $p$ exactly twice (once from each $n!$ ). Thus, the exponent of $p$ in the final expression is $v_p\left(\binom{2n}{n}\right) = v_p((2n)!) - 2v_p(n!) = 2 - 2(1) = 0$ .

These two observations together imply a powerful conclusion: all prime factors of $\binom{2n}{n}$ must be less than or equal to $2n/3$ .

Constructing the Upper Bound:

We now bound the size of $\binom{2n}{n}$ based on this restricted set of prime factors, which we analyze in two groups:

Small Primes ( $p \le \sqrt{2n}$ ): The bound $p^{v_p(\binom{2n}{n})} \le 2n$ follows directly from Legendre’s formula, which gives the exponent as $v_p(\binom{2n}{n}) = \sum_{k=1}^\infty \left( \lfloor 2n/p^k \rfloor - 2\lfloor n/p^k \rfloor \right)$ . The core of the argument is that each term in this sum is either 0 or 1, and the sum is non-zero only for the $\lfloor\log_p(2n)\rfloor$ terms where $p^k \le 2n$ . Because each of these terms is at most 1, the entire sum is bounded by the number of terms, leading immediately to the inequality $v_p(\binom{2n}{n}) \le \lfloor\log_p(2n)\rfloor \le \log_p(2n)$ . Exponentiating with base $p$ yields the desired result: $p^{v_p(\binom{2n}{n})} \le p^{\log_p(2n)} = 2n$ .
So the total contribution from this range is bounded by: $\prod_{p \le \sqrt{2n}} p^{v_p(\binom{2n}{n})} \le \prod_{p \le \sqrt{2n}} (2n) = (2n)^{\pi(\sqrt{2n})} < (2n)^{\sqrt{2n}}$
Other Primes ( $\sqrt{2n} < p \le 2n/3$ ): For these primes, $p^2 > 2n$ , which implies from $p^{v_p(\binom{2n}{n})} \le 2n$ that the exponent $v_p(\binom{2n}{n})$ is at most 1. Their contribution is therefore bounded by their product: $\prod_{\sqrt{2n} < p \le 2n/3} p \le \prod_{p \le 2n/3} p$

Combining these results gives our upper bound on $\binom{2n}{n}$ under the hypothesis: $\binom{2n}{n} \le (2n)^{\sqrt{2n}} \cdot \left(\prod_{p \le 2n/3} p\right)$

The Contradiction

To handle the remaining product of primes, we use an upper bound: $\prod_{p \le x} p \le 4^x$ for any $x \ge 1$ . This can be proved by using an upper bound on the binomial coefficient $\binom{2n}{n} \le 4^n$ , by applying it to upper bound product of primes in dyadic intervals $[x, 2x)]$ . Applying this with $x=2n/3$ : $\binom{2n}{n} \le (2n)^{\sqrt{2n}} \cdot 4^{2n/3}$

We now confront our universal lower bound with this new, restrictive upper bound: $\frac{4^n}{2n+1} \le \binom{2n}{n} \le (2n)^{\sqrt{2n}} \cdot 4^{2n/3}$

This inequality must hold if our initial hypothesis is true. Simplifying it by isolating the exponential terms yields: $4^{n/3} \le (2n+1)(2n)^{\sqrt{2n}}$

The left side grows exponentially in $n$ , while the right side grows sub-exponentially. Taking logarithms makes it clear: $\frac{n}{3}\log 4 \le \log(2n+1) + \sqrt{2n}\log(2n)$ .

Thus we get a contradiction assuming no primes in exist in the interval. This proves Betrand postulate for large n.

Instead of contradiction, one can phrase the whole argument as obtaining a lower bound on the number of primes. In fact, the argument gives linear upper and lower bounds $cx \le \sum_{x\le p \le 2x} 1 \le Cx$ on the sums of logarithms of primes.

Erdős’s argument, by analyzing $\log\binom{2n}{n}$ , is essentially a combinatorial method for establishing bounds on the sum of logarithms of primes, which is the Chebyshev theta function, $\theta(x) = \sum_{p \le x} \log p$ . In modern terms, the focus shifts to the closely related psi function, $\psi(x) = \sum_{n \le x} \Lambda(n)$ , which uses the Von Mangoldt function $\Lambda(n)$ as a “smoother” measure of primality that includes prime powers. The fundamental nature of $\Lambda(n)$ is revealed by the convolution identity $\sum_{d|n} \Lambda(d) = \log n$ , which shows it is the essential arithmetic component of the logarithm itself. The analysis of the binomial coefficient in Erdős’s proof is structurally similar to the modern technique of using identities for $\psi(x)$ that involve combinations of the function at different scales (e.g., $x, x/2, \dots$ ). Both approaches reduce the problem of prime distribution to an analysis of sums over integers and the distribution of the function $\log n$ . While these methods establish the correct order of magnitude, obtaining the more precise information required for the Prime Number Theorem ( $\psi(x) \sim x$ ) demands knowledge of the finer distribution of $\log n$ . This information is encoded in the Riemann zeta function, which is basically a transform of these logarithms, and whose deep analytic properties—particularly the location of its zeroes—govern the ultimate structure of the integers.