With the foundation of \prod_{p\leq n}p < 4^{n-1} from the previous article, we are actually very close to the proof of Bertrand’s Postulate. The proof of Bertrand’s Postulate is based on a detailed examination of the prime factor exponents of the binomial coefficient \binom{2n}{n}. In this article, we first derive a lower bound formula for the product of primes, then prove a proposition slightly weaker than Bertrand’s Postulate. Finally, through a simple technique, we push our proof to Bertrand’s Postulate.
Prime Factors of Binomial Coefficients
First, we examine the exponent of a prime factor p in n!. The result is the formula known as Legendre’s Theorem:
The exponent of the prime factor p in n! is exactly \sum_{k\geq 1}\left\lfloor\frac{n}{p^k}\right\rfloor.
The proof is simple: since n!=1\times 2\times 3\times 4\times \dots \times n, there is a multiple of p every p terms, a multiple of p^2 every p^2 terms, and so on. Each increase in power contributes an additional factor of p, so we simply sum the counts of these intervals. Note that although the sum is written in an infinite form, the number of non-zero terms is finite.
Next, we use the above formula to examine the number of prime factors p in \binom{2n}{n}=\frac{(2n)!}{n! n!}. Since this is just division of factorials, the exponent of the prime factor p in \binom{2n}{n} is: \sum_{k\geq 1}\left(\left\lfloor\frac{2n}{p^k}\right\rfloor-2\left\lfloor\frac{n}{p^k}\right\rfloor\right) Notice that the term in the parentheses is at most 1, because \left\lfloor\frac{2n}{p^k}\right\rfloor-2\left\lfloor\frac{n}{p^k}\right\rfloor < \frac{2n}{p^k}-2\left(\frac{n}{p^k}-1\right)=2. Therefore, if we let \nu_p be the exponent of p in \binom{2n}{n}, then: \nu_p \leq \max \{r \mid p^r \leq 2n\}
From this, we know that in \binom{2n}{n}, the exponent of prime factors greater than \sqrt{2n} is at most 1, while the exponent of prime factors less than or equal to \sqrt{2n} is such that p^{\nu_p} \leq 2n. At the same time, there are at most \sqrt{2n} primes less than or equal to \sqrt{2n}. Thus, we have the formula: \binom{2n}{n} \leq (2n)^{\sqrt{2n}}\prod_{\sqrt{2n} < p\leq 2n}p
Next, we prove \binom{2n}{n} > \frac{4^n}{2n}. In fact, this inequality is quite weak, as from Stirling’s formula we have \binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}. The proof of this inequality is not difficult and is left to the reader. Using this inequality, we further obtain: 4^n \leq (2n)^{1+\sqrt{2n}}\prod_{\sqrt{2n} < p\leq 2n}p If the goal were only to prove Bertrand’s Postulate, one could skip directly to the "Bertrand’s Postulate" section below. Here, we simply obtain: \prod_{p\leq 2n}p > \frac{4^n}{(2n)^{1+\sqrt{2n}}} Note that the denominator (2n)^{1+\sqrt{2n}} grows slower than any a^n for a>1. This is a (relatively weak) estimate for the lower bound of the product of primes.
Weak Bertrand’s Postulate
A proposition slightly weaker than Bertrand’s Postulate is:
For any \varepsilon > 0, there exists N(\varepsilon) > 0 such that for any n > N(\varepsilon), there exists a prime between (1-\varepsilon)n and 2n.
What we have discussed above is sufficient to prove this proposition. Suppose there is no prime between (1-\varepsilon)n and 2n. Then: \prod_{p\leq 2n}p = \prod_{p\leq (1-\varepsilon)n}p According to \prod_{p\leq n}p < 4^{n-1}, we would have: \prod_{p\leq 2n}p < 4^{(1-\varepsilon)n-1} Combining this with our results: 4^{(1-\varepsilon)n-1} > \frac{4^n}{(2n)^{1+\sqrt{2n}}} which is: (2n)^{1+\sqrt{2n}} > 4^{\varepsilon n+1} As mentioned earlier, (2n)^{1+\sqrt{2n}} grows slower than any a^n for a>1. Therefore, for sufficiently large n, the above inequality leads to a contradiction. Thus, for sufficiently large n, there is at least one prime between (1-\varepsilon)n and 2n.
Bertrand’s Postulate
We are now only one step away from the proof of Bertrand’s Postulate. We need to consider the prime factors of \binom{2n}{n} more carefully. We find that \binom{2n}{n} has no prime factors p such that \frac{2n}{3} < p \leq n! The proof is quite simple: since \binom{2n}{n}=\frac{(2n)!}{n! n!}, the condition 3p > 2n implies that the numerator (2n)! contains only the factors p and 2p, while p \leq n implies that the denominator (n!)^2 contains the prime factor p^2. After cancellation, the exponent of p is 0. Thus, we have: \binom{2n}{n} \leq (2n)^{\sqrt{2n}}\prod_{\sqrt{2n} < p\leq \frac{2n}{3}}p \times \prod_{n < p\leq 2n}p Substituting \binom{2n}{n} > \frac{4^n}{2n} and \prod_{p\leq n}p < 4^{n-1} into the above, we get: 4^n \leq (2n)^{1+\sqrt{2n}} 4^{\frac{2n}{3}} \times \prod_{n < p\leq 2n}p If there were no prime between n and 2n, the last term would be 1, leading to: 4^{\frac{n}{3}} \leq (2n)^{1+\sqrt{2n}} This inequality results in a contradiction for n > 4000. Therefore, for n > 4000, Bertrand’s Postulate holds.
For the remaining part, we list a sequence of primes:
2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259, 2503, 4001
For any n not greater than 4000, it must fall between two adjacent numbers in the above prime sequence or be one of the terms itself. Thus, there is always a prime from this sequence between n and 2n. Therefore, Bertrand’s Postulate also holds for n \leq 4000.
The above proof is included in Proofs from THE BOOK. It is a purely elementary technique for proving the upper bound of prime intervals. In fact, this bound can be further improved, but the techniques involved are more complex. An unsolved conjecture is whether there is always a prime between n^2 and (n+1)^2 for any n; this has not yet been proven or disproven.
When reposting, please include the original address: https://kexue.fm/archives/2800
For more details on reposting, please refer to: Scientific Space FAQ