Section 1.2 Erdős’s proof of Bertrand’s postulate
Proof.
Observe
\begin{equation}
4^n = (1+1)^{2n} = \sum_{k=0}^{2n} \binom{2n}{k}
= 2 + \sum_{k=1}^{2n-1} \binom{2n}{k} \text{,}\tag{1.2.1}
\end{equation}
first using the Binomial Theorem and then grouping the first and last terms \(\binom{2n}{0} + \binom{2n}{2n} = 1+1 = 2\text{.}\) This sum has \(2n\) terms (including the term \(2\) and the \(2n-1\) terms in the summation). The largest term is the central binomial coefficient \(\binom{2n}{n}\text{.}\) Since the largest term is at least as great as the average value of the terms, we have
\begin{equation}
\binom{2n}{n} \geq \frac{1}{2n} \left( 2 + \sum_{k=1}^{2n-1} \binom{2n}{k} \right)
= \frac{4^n}{2n} \text{.}\tag{1.2.2}
\end{equation}
For a prime \(p\) and integer \(m\) let \(\nu_p(m)\) be the largest exponent of a power of \(p\) that divides \(m\text{,}\) i.e.,
\begin{equation}
\nu_p(m) = k \text{ where } p^k \mid m \text{ and } p^{k+1} \nmid m \text{.}\tag{1.2.3}
\end{equation}
Observe that \(\nu_p(ab) = \nu_p(a) + \nu_p(b)\) and \(\nu_p(a/b) = \nu_p(a) - \nu_p(b)\) (assuming, of course, that \(a/b\) is an integer).
Claim 1.2.2.
\(\nu_p(n!) = \sum_{k \geq 1} \lfloor \frac{n}{p^k} \rfloor = \lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + \lfloor \frac{n}{p^3} \rfloor + \dotsb\text{.}\)Proof.
There are \(\lfloor \frac{n}{p} \rfloor\) multiples of \(p\) less than or equal to \(n\text{,}\) and they each contribute a factor of \(p\) to \(n!\text{.}\) There are \(\lfloor \frac{n}{p^2} \rfloor\) multiples of \(p^2\text{,}\) and they each contribute an additional factor of \(p\) to \(n!\text{.}\) And so on.
Claim 1.2.3.
Let \(k = \nu_p(\binom{2n}{n})\text{.}\) Then \(p^k \leq 2n\text{.}\)Proof.
First, let \(r\) be an integer such that \(p^r \leq 2n \lt p^{r+1} \text{.}\) Now
\begin{align*}
\nu_p(\binom{2n}{n}) \amp = \nu_p( (2n)! ) - 2 \nu_p(n!) \\
\amp = \sum_{i \geq 1} \lfloor \frac{2n}{p^i} - 2 \sum_{i \geq 1} \lfloor \frac{n}{p^i} \rfloor \\
\amp = \sum_{i=1}^r \left( \lfloor \frac{2n}{p^i} \rfloor - 2 \lfloor \frac{n}{p^i} \rfloor \right)
\end{align*}
where we can drop terms with \(i > r\text{,}\) since then \(p^i > 2n\text{,}\) so \(\frac{2n}{p^i} \lt 1\text{,}\) meaning \(\lfloor \frac{2n}{p^i} \rfloor = 0\text{.}\)
Exercise: For all real \(x\text{,}\) \(0 \leq \lfloor 2x \rfloor - 2 \lfloor x \rfloor \leq 1\text{.}\)
Using this, \(k = \nu_p(\binom{2n}{n}) \leq r \text{.}\) So \(p^k \leq p^r \leq 2n \text{.}\)
Definition 1.2.4.
For a real number \(x\text{,}\) the primorial \(x\#\) is the product of the primes less than or equal to \(x\text{,}\) \(x\# = \prod_{p \leq x} p\text{,}\) where the product is over primes \(p\text{.}\) For example, \(2\# = 2\text{,}\) \(3\# = 2 \cdot 3 = 6\text{,}\) and \(10\# = 2 \cdot 3 \cdot 5 \cdot 7 = 210\text{.}\)
Claim 1.2.5.
For all \(n \geq 2\text{,}\) \(n\# \leq 4^n\text{.}\)Proof.
By induction on \(n\text{.}\) First, for \(n = 2\text{,}\) \(2\# = 2\) while \(4^2 = 16\text{.}\) For \(n = 3\text{,}\) \(3\# = 6\) while \(4^3 = 64\text{.}\)
For the inductive step, if \(n \geq 4\) is even, then \(n\) is not prime, so
\begin{equation*}
n\# = \prod_{p \leq n} p = \prod_{p \leq n-1} p = (n-1)\# \leq 4^{n-1} \leq 4^n \text{.}
\end{equation*}
If \(n \geq 5\) is odd, say \(n = 2m+1\text{,}\) then
\begin{equation*}
n\# = \prod_{p \leq n} p = \left( \prod_{p \leq m+1} p \right)
\left( \prod_{m+2 \leq p \leq 2m+1} p \right) \text{.}
\end{equation*}
By induction this is less than or equal to
\begin{equation*}
4^{m+1} \left( \prod_{m+2 \leq p \leq 2m+1} p \right) \text{.}
\end{equation*}
Observe that if \(m+2 \leq p \leq 2m+1 \) then \(p\) is a factor in \((2m+1)!\) but not in \(m!\) or \((m+1)!\text{.}\) So \(\binom{2m+1}{m+1}\) is divisible by \(p\text{.}\) In fact \(\binom{2m+1}{m+1}\) is divisible by each prime in this range, hence it is divisible by the product of these primes (why?). Therefore the binomial coefficient is greater than or equal this product of primes,
\begin{equation*}
\prod_{m+2 \leq p \leq 2m+1} p \leq \binom{2m+1}{m+1} \text{.}
\end{equation*}
Finally, \(\sum_{k=0}^{2m+1} \binom{2m+1}{k} = 2^{2m+1}\text{.}\) In this sum the two largest terms are \(\binom{2m+1}{m} = \binom{2m+1}{m+1}\text{.}\) Hence
\begin{equation}
\binom{2m+1}{m+1} \leq \frac{1}{2} 2^{2m+1} = 2^{2m} = 4^m \text{.}\tag{1.2.4}
\end{equation}
Putting it all together,
\begin{align*}
n\# = \prod_{p \leq n} p \amp= \left( \prod_{p \leq m+1} p \right)
\left( \prod_{m+2 \leq p \leq 2m+1} p \right) \\
\amp \leq 4^{m+1} \cdot 4^m
= 4^{2m+1} = 4^n \text{.}
\end{align*}
In a sense there are “not too many” primes less than or equal to \(n\) (their product is “small”) and each one contributes a “small” amount to \(\binom{2n}{n}\) (a factor of at most \(2n\)), yet \(\binom{2n}{n}\) is “large”. This tension will lead to a contradiction, but first we must raise the tension even higher.
Claim 1.2.6.
If \(n \geq 3\) and \(\frac{2n}{3} \lt p \leq n\) then \(\nu_p \binom{2n}{n} = 0\text{,}\) that is, \(p \nmid \binom{2n}{n}\text{.}\)Proof.
Since \(p \leq n\text{,}\) then \(2p \leq 2n\text{,}\) but \(3p > 2n\text{.}\) Since \(n \geq 3\) and \(p > \frac{2n}{3}\text{,}\) then \(p \gt 2\text{.}\) So \((2n)!\) is divisible by \(p^2\) but not \(p^3\text{.}\) (We need \(p \gt 2\) in order to say that \(2p\) only contributes one factor of \(p\text{,}\) not two.)
However \(p \leq n\text{,}\) so \(p \mid n!\text{.}\) Then \(p^2 \mid (n!)^2\text{.}\) So the \(p^2\) factors in the numerator and denominator of \(\binom{2n}{n} = \frac{(2n)!}{(n!)^2}\) cancel out.
Now, we can put these claims together.
Erdős’s proof of Bertrand’s postulate.
Let \(n \geq 3\) and suppose there is no prime \(p\) with \(n \lt p \leq 2n\text{.}\) Then
\begin{equation}
\binom{2n}{n} = \left( \prod_{p \leq \sqrt{2n}} p^{\nu_p(\binom{2n}{n})} \right)
\left( \prod_{\sqrt{2n} \lt p \leq \frac{2n}{3}} p^{\nu_p(\binom{2n}{n})} \right) \text{.}\tag{1.2.5}
\end{equation}
We can omit primes \(\frac{2n}{3} \lt p \leq 2n\text{,}\) as well as primes \(p \gt 2n\) (why?).
We know every \(p^{\nu_p(\binom{2n}{n})} \leq 2n\text{.}\) There are at most \(\sqrt{2n}\) primes \(p\) such that \(p \leq \sqrt{2n}\text{.}\) Hence
\begin{equation}
\prod_{p \leq \sqrt{2n}} p^{\nu_p(\binom{2n}{n})} \leq \prod_{p \leq \sqrt{2n}} 2n \leq (2n)^{\sqrt{2n}}\text{.}\tag{1.2.6}
\end{equation}
On the other hand, if \(p \gt \sqrt{2n}\text{,}\) then \(p^2 \gt 2n\text{.}\) Since we have \(p^{\nu_p(\binom{2n}{n})} \leq 2n\text{,}\) it must be \(\nu_p(\binom{2n}{n}) \leq 1\text{.}\) Thus
\begin{equation}
\prod_{\sqrt{2n} \lt p \leq \frac{2n}{3}} p^{\nu_p(\binom{2n}{n})}
\leq \prod_{\sqrt{2n} \lt p \leq \frac{2n}{3}} p
\leq \prod_{p \leq \frac{2n}{3}} p
= \left(\frac{2n}{3}\right)\# \leq 4^{2n/3}\text{.}\tag{1.2.7}
\end{equation}
Exercise: We proved \(\prod_{p \leq m} p \leq 4^m\) for integers \(m\text{.}\) What if \(m = \frac{2n}{3}\) is not an integer? Justify this step.
Putting it together, \(\binom{2n}{n} \leq (2n)^{\sqrt{2n}} 4^{\frac{2n}{3}}\text{.}\) And since \(\binom{2n}{n} \geq \frac{4^n}{2n}\) we get
\begin{equation}
\frac{4^n}{2n} \leq (2n)^{\sqrt{2n}} 4^{\frac{2n}{3}} \text{.}\tag{1.2.8}
\end{equation}
That is,
\begin{equation}
4^{\frac{1}{3}n} \leq (2n)^{\sqrt{2n}+1} \text{.}\tag{1.2.9}
\end{equation}
Taking the logarithm of each side gives
\begin{equation}
\frac{\log 4}{3} n \leq (\sqrt{2n}+1) \log(2n) \text{.}\tag{1.2.10}
\end{equation}
We know \(\log(2n)\) grows more slowly than \(\sqrt{n}\text{,}\) so the whole right side grows more slowly than \(n\text{.}\) Therefore the left side grows more quickly than the right side. And yet the left side is supposed to be less than or equal to the right side! This shows that our assumption, that there is no prime \(p\) such that \(n \lt p \leq 2n\text{,}\) leads to a contradiction.
In more detail: the function \(f(x) = (\sqrt{2x}+1)\log(2x)\) is concave down. (Exercise: Check that \(f''(x) \lt 0\text{.}\)) So for any linear function the inequality \(ax+b \leq f(x)\) is valid on an interval (why?).
In this case, \(\frac{4^n}{2n} \leq (2n)^{\sqrt{2n}} 4^{\frac{2n}{3}}\) is valid for \(n = 467\) but not for \(n = 468\text{.}\) (We can check this on a calculator. To find these numbers, we try different values of \(n\) and narrow down on the largest value of \(n\) where the inequality is valid, or the smallest value where it is not valid.)
This shows: If there is no prime \(p\) with \(n \lt p \leq 2n\text{,}\) then \(n \leq 467\text{.}\) Equivalently: If \(n \geq 468\text{,}\) then there is a prime \(p\) such that \(n \lt p \leq 2n\text{.}\)
Finally, to take care of \(n \leq 467\) consider the sequence of primes
\begin{equation}
2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631 \text{.}\tag{1.2.11}
\end{equation}
These satisfy \(p_{k-1} \lt p_k \lt 2p_{k-1}\text{.}\) For any \(n \leq 467\text{,}\) choose \(p_{k-1} \leq n \lt p_k\text{.}\) Then we get
\begin{equation*}
n \lt p_k \lt 2p_{k-1} \leq 2n \text{,}
\end{equation*}
so \(p_k\) is a prime in the interval \((n,2n]\text{.}\)
