Betrand Postulate : Erdos( 1932)

Bertrand’s postulate states that for every integer $n\ge1$ , there is a prime $p$ satisfying

$\displaystyle n<p\le2n.$

The statement is elementary, but it is remarkably strong: no matter how far one goes along the number line, one never encounters a multiplicative gap as large as a factor of $2$ containing no primes.

Erdős’s proof (1932) of this fact is centered on a careful analysis of the prime factors of the central binomial coefficient, $M = \binom{2n}{n}$ . Why should this coefficient know anything about primes between $n$ and $2n$ ? The reason is simple but powerful. If $p$ is prime and $\displaystyle n<p\le2n,$ then $p$ occurs once in the numerator $(2n)!$ and does not occur at all in either copy of $n!$ in the denominator. Thus $\displaystyle p\mid\binom{2n}{n}.$

The central binomial coefficient is therefore a detector for primes in the interval $(n,2n]$ .

Click to access 1932-01.pdf

The proof proceeds by contradiction. Suppose that, for some integer $n$ , there is no prime in that interval. We shall show that this forces $\binom{2n}{n}$ to be much smaller than it actually is. So 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 $\displaystyle \binom{2n}{n}$

The binomial theorem gives $\displaystyle \sum_{k=0}^{2n}\binom{2n}{k}=4^n.$ Among these $2n+1$ nonnegative terms, the largest is the central term $\displaystyle \binom{2n}{n}$ . Hence

$\displaystyle \binom{2n}{n}\ge\frac{4^n}{2n+1}.$

This lower bound is crude, but it already has the crucial feature: it grows exponentially in $n$ .

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$ . This is the key restriction. The contradiction hypothesis says that a very large integer, roughly of size $4^n$ , must be assembled entirely from relatively small primes.

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:

Legendre’s formula gives

$\displaystyle v_p\left(\binom{2n}{n}\right)=\sum_{k\ge1}\left(\left\lfloor\frac{2n}{p^k}\right\rfloor-2\left\lfloor\frac{n}{p^k}\right\rfloor\right).$

Each summand is either $0$ or $1$ . Moreover, it vanishes once $p^k>2n$ . Thus $\displaystyle v_p\left(\binom{2n}{n}\right)\le\left\lfloor\log_p(2n)\right\rfloor,$ and consequently $\displaystyle p^{v_p(\binom{2n}{n})}\le2n.$

Small Primes ( $p \le \sqrt{2n}$ ): For primes satisfying $p\le\sqrt{2n},$ we may therefore bound their total contribution by

$\displaystyle \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}}$ .

This bound is deliberately rough. Its purpose is only to show that the small-prime part grows subexponentially compared with $4^n$ .

Other Primes ( $\sqrt{2n} < p \le 2n/3$ ): For these primes, $p^2>2n,$ so their exponent in $M$ is at most $1$ . Their total contribution is therefore bounded by

$\displaystyle \prod_{\sqrt{2n}<p\le2n/3}p\le\prod_{p\le2n/3}p.$

Combining these results gives our upper bound on $\binom{2n}{n}$ under the hypothesis:

$\displaystyle \binom{2n}{n}\le(2n)^{\sqrt{2n}}\prod_{p\le2n/3}p.$

The Contradiction

To handle the remaining product of primes, we use the elementary Chebyshev-type estimate $\displaystyle \prod_{p\le x}p\le4^x,\qquad x\ge1.$ This estimate can be obtained by comparing products of primes in dyadic intervals with binomial coefficients. It is far from sharp, but it is more than adequate here. Applying it with $\displaystyle x=\frac{2n}{3}$ gives

$\displaystyle \binom{2n}{n}\le(2n)^{\sqrt{2n}}4^{2n/3}.$

We now confront our universal lower bound with this new, restrictive upper bound:

$\displaystyle \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 $\displaystyle n<p\le2n.$ . This proves Betrand’s 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 $\displaystyle 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.