Proof of Bertrand's postulate

In mathematics, Bertrand's postulate (actually a theorem) states that for each ${\displaystyle n\geq 1}$ there is a prime ${\displaystyle p}$ such that ${\displaystyle n<p\leq 2n}$. It was first proven by Pafnuty Chebyshev, and a short but advanced proof was given by Srinivasa Ramanujan.[1] The gist of the following elementary proof is due to Paul Erdős. The basic idea of the proof is to show that a certain central binomial coefficient needs to have a prime factor within the desired interval in order to be large enough. This is made possible by a careful analysis of the prime factorization of central binomial coefficients.

The main steps of the proof are as follows. First, one shows that every prime power factor ${\displaystyle p^{r}}$ that enters into the prime decomposition of the central binomial coefficient ${\displaystyle {\tbinom {2n}{n}}:={\frac {(2n)!}{(n!)^{2}}}}$ is at most ${\displaystyle 2n}$. In particular, every prime larger than ${\displaystyle {\sqrt {2n}}}$ can enter at most once into this decomposition; that is, its exponent ${\displaystyle r}$ is at most one. The next step is to prove that ${\displaystyle {\tbinom {2n}{n}}}$ has no prime factors at all in the gap interval ${\displaystyle \left({\tfrac {2n}{3}},n\right)}$. As a consequence of these two bounds, the contribution to the size of ${\displaystyle {\tbinom {2n}{n}}}$ coming from all the prime factors that are at most ${\displaystyle n}$ grows asymptotically as ${\displaystyle O(\theta ^{n})}$ for some ${\displaystyle \theta <4}$. Since the asymptotic growth of the central binomial coefficient is at least ${\displaystyle 4^{n}/2n}$, one concludes that for ${\displaystyle n}$ large enough the binomial coefficient must have another prime factor, which can only lie between ${\displaystyle n}$ and ${\displaystyle 2n}$. Indeed, making these estimates quantitative, one obtains that this argument is valid for all ${\displaystyle n\geq 468}$. The remaining smaller values of ${\displaystyle n}$ are easily settled by direct inspection, completing the proof of Bertrand's postulate. This proof is so short and elegant that it is considered to be one of the Proofs from THE BOOK.

Lemmas and computation

Lemma 1: A lower bound on the central binomial coefficients

Lemma: For any integer ${\displaystyle n>0}$, we have

${\displaystyle {\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}.}$

Proof: Applying the binomial theorem,

${\displaystyle 4^{n}=(1+1)^{2n}=\sum _{k=0}^{2n}{\binom {2n}{k}}=2+\sum _{k=1}^{2n-1}{\binom {2n}{k}}\leq 2n{\binom {2n}{n}},}$

since ${\displaystyle {\tbinom {2n}{n}}}$ is the largest term in the sum in the right-hand side, and the sum has ${\displaystyle 2n}$ terms (including the initial ${\displaystyle 2}$ outside the summation).

Lemma 2: An upper bound on prime powers dividing central binomial coefficients

For a fixed prime ${\displaystyle p}$, define ${\displaystyle R:=R(p,n)}$ to be the largest natural number ${\displaystyle r}$ such that ${\displaystyle p^{r}}$ divides ${\displaystyle {\tbinom {2n}{n}}}$.

Lemma: For any prime ${\displaystyle p}$, ${\displaystyle p^{R}\leq 2n}$.

Proof: The exponent of ${\displaystyle p}$ in ${\displaystyle n!}$ is (see Factorial#Number theory):

${\displaystyle \sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor ,}$

so

${\displaystyle R=\sum _{j=1}^{\infty }\left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor =\sum _{j=1}^{\infty }\left(\left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\left\lfloor {\frac {n}{p^{j}}}\right\rfloor \right).}$

But each term of the last summation can either be zero (if ${\displaystyle n/p^{j}{\bmod {1}}<1/2}$) or 1 (if ${\displaystyle n/p^{j}{\bmod {1}}\geq 1/2}$) and all terms with ${\displaystyle j>\log _{p}(2n)}$ are zero. Therefore,

${\displaystyle R\leq \log _{p}(2n),}$

and

${\displaystyle p^{R}\leq p^{\log _{p}{2n}}=2n.}$

This completes the proof of the lemma.

Lemma 3: Central binomial coefficients have no prime factor in a large interval

Claim: If ${\displaystyle p}$ is odd and ${\displaystyle {\frac {2n}{3}}<p\leq n}$, then ${\displaystyle R(p,n)=0.}$

Proof: There are exactly two factors of ${\displaystyle p}$ in the numerator of the expression ${\displaystyle {\tbinom {2n}{n}}={\frac {(2n)!}{(n!)^{2}}}}$, coming from the two terms ${\displaystyle p}$ and ${\displaystyle 2p}$ in ${\displaystyle (2n)!}$, and also two factors of ${\displaystyle p}$ in the denominator from two copies of the term ${\displaystyle p}$ in ${\displaystyle n!}$. These factors all cancel, leaving no factors of ${\displaystyle p}$ in ${\displaystyle {\tbinom {2n}{n}}}$. (The bound on ${\displaystyle p}$ in the preconditions of the lemma ensures that ${\displaystyle 3p}$ is too large to be a term of the numerator, and the assumption that ${\displaystyle p}$ is odd is needed to ensure that ${\displaystyle 2p}$ contributes only one factor of ${\displaystyle p}$ to the numerator).

Lemma 4: An upper bound on the primorial

We estimate the primorial function,

${\displaystyle x\#=\prod _{p\leq x}p,}$

where the product is taken over all prime numbers ${\displaystyle p}$ less than or equal to the real number ${\displaystyle x.}$

Lemma: For all real numbers ${\displaystyle x\geq 3}$, ${\displaystyle x\#<2^{2x-3}.}$

Proof: Since ${\displaystyle x\#=\lfloor x\rfloor \#}$ and ${\displaystyle 2^{2\lfloor x\rfloor -3}\leq 2^{2x-3}}$, it suffices to prove the result under the assumption that ${\displaystyle x=m}$ is an integer, ${\displaystyle m\geq 3.}$ Since ${\displaystyle {\binom {2m-1}{m}}}$ is an integer and all the primes ${\displaystyle m+1\leq p\leq 2m-1}$ appear in its numerator but not in its denominator, we have

${\displaystyle {\frac {(2m-1)\#}{m\#}}\leq {\binom {2m-1}{m}}={\frac {1}{2}}\left({\binom {2m-1}{m-1}}+{\binom {2m-1}{m}}\right)<{\frac {1}{2}}(1+1)^{2m-1}=2^{2m-2}.}$

The proof proceeds by complete induction on ${\displaystyle n.}$

• If ${\displaystyle n=3}$, then ${\displaystyle n\#=6<8=2^{2n-3}.}$
• If ${\displaystyle n=4}$, then ${\displaystyle n\#=6<32=2^{2n-3}.}$
• If ${\displaystyle n\geq 5}$ is odd, ${\displaystyle n=2m-1}$, then by the above estimate and the induction assumption, since ${\displaystyle m\geq 3}$ and ${\displaystyle m<n}$ it is

${\displaystyle n\#=(2m-1)\#<m\#\cdot 2^{2m-2}<2^{2m-3}2^{2m-2}=2^{4m-5}=2^{2n-3}.}$

• If ${\displaystyle n=2m}$ is even and ${\displaystyle n\geq 6,}$ then by the above estimate and the induction assumption, since ${\displaystyle m\geq 3}$ and ${\displaystyle n-1<n}$ it is

${\displaystyle n\#=(2m)\#=(2m-1)\#=(n-1)\#<2^{2(n-1)-3}<2^{2n-3}.}$

Thus the lemma is proven.

Proof of Bertrand's Postulate

Assume there is a counterexample: an integer n ≥ 2 such that there is no prime p with n < p < 2n.

If 2 ≤ n < 468, then p can be chosen from among the prime numbers 3, 5, 7, 13, 23, 43, 83, 163, 317, 631 (each being less than twice its predecessor) such that n < p < 2n. Therefore, n ≥ 468.

There are no prime factors p of ${\displaystyle \textstyle {\binom {2n}{n}}}$ such that:

• 2n < p, because every factor must divide (2n)!;
• p = 2n, because 2n is not prime;
• n < p < 2n, because we assumed there is no such prime number;
• 2n / 3 < p ≤ n: by Lemma 3.

Therefore, every prime factor p satisfies p ≤ 2n/3.

When ${\displaystyle p>{\sqrt {2n}},}$ the number ${\displaystyle \textstyle {2n \choose n}}$ has at most one factor of p. By Lemma 2, for any prime p we have p^R(p,n) ≤ 2n, so the product of the p^R(p,n) over the primes less than or equal to ${\displaystyle {\sqrt {2n}}}$ is at most ${\displaystyle (2n)^{\sqrt {2n}}}$. Then, starting with Lemma 1 and decomposing the right-hand side into its prime factorization, and finally using Lemma 4, these bounds give:

${\displaystyle {\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}=\left(\prod _{p\leq {\sqrt {2n}}}p^{R(p,n)}\right)\left(\prod _{{\sqrt {2n}}<p\leq {\frac {2n}{3}}}p^{R(p,n)}\right)<(2n)^{\sqrt {2n}}\prod _{1<p\leq {\frac {2n}{3}}}p=(2n)^{\sqrt {2n}}{\Big (}{\frac {2n}{3}}{\Big )}\#\leq (2n)^{\sqrt {2n}}4^{2n/3}.}$

Taking logarithms yields to

${\displaystyle {\frac {\log 4}{3}}n\leq ({\sqrt {2n}}+1)\log 2n\;.}$

By concavity of the right-hand side as a function of n, the last inequality is necessarily verified on an interval. Since it holds true for n=467 and it does not for n=468, we obtain

${\displaystyle n<468.}$

But these cases have already been settled, and we conclude that no counterexample to the postulate is possible.

References

1. Ramanujan, S. (1919), "A proof of Bertrand's postulate", Journal of the Indian Mathematical Society, 11: 181–182

• Aigner, Martin, G., Günter M. Ziegler, Karl H. Hofmann, Proofs from THE BOOK, Fourth edition, Springer, 2009. ISBN 978-3-642-00855-9.

External links

• Proof in the Mizar system: http://mizar.org/version/current/html/nat_4.html#T56