Proof of Bertrand's postulate

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, Bertrand's postulate (actually a theorem) states that for each n\ge 1 there is a prime p such that n<p\le 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 p^r that enters into the prime decomposition of the central binomial coefficient \tbinom{2n}{n}:=\frac{(2n)!}{(n!)^2} is at most 2n. In particular, every prime larger than \sqrt{2n} can enter at most once into this decomposition; that is, its exponent r is at most one. The next step is to prove that \tbinom{2n}{n} has no prime factors at all in the gap interval \left(\tfrac{2n}{3}, n\right). As a consequence of these two bounds, the contribution to the size of \tbinom{2n}{n} coming from all the prime factors that are at most n grows asymptotically as O(\theta^n) for some \theta<4. Since the asymptotic growth of the central binomial coefficient is at least 4^n/2n, one concludes that for n large enough the binomial coefficient must have another prime factor, which can only lie between n and 2n. Indeed, making these estimates quantitative, one obtains that this argument is valid for all n>468. The remaining smaller values of n are easily settled by direct inspection, completing the proof of Bertrand's postulate.

Lemmas and computation[edit]

Lemma 1: A lower bound on the central binomial coefficients[edit]

Lemma: For any integer n>0, we have

 \frac{4^n}{2n} \le \binom{2n}{n}.\

Proof: Applying the binomial theorem,

4^n = (1 + 1)^{2n} = \sum_{k = 0}^{2n} \binom{2n}{k}=2+\sum_{k = 1}^{2n-1} \binom{2n}{k} \le 2n\binom{2n}{n},\

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

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

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

Lemma: For any prime p, p^{R(p,n)}\le 2n.

Proof: The exponent of p in n! is (see Factorial#Number theory):

\sum_{j = 1}^\infty \left\lfloor \frac{n}{p^j} \right\rfloor,\

so

 R(p,n)
        =\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 n/p^j \bmod 1< 1/2) or 1 (if n/p^j \bmod 1\ge  1/2) and all terms with j>\log_p(2n) are zero. Therefore

R(p,n) \leq \log_p(2n),\

and

p^{R(p,n)} \leq p^{\log_p{2n}} = 2n.\

This completes the proof of the lemma.

Lemma 3: The exact power of a large prime in a central binomial coefficient[edit]

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

Proof: The factors of p in the numerator come from the terms p and 2p, and in the denominator from two factors of p. These cancel since p is odd.

Lemma 4: An upper bound on the primorial[edit]

We estimate the primorial function,

x\# = \prod_{p \leq x} p,\

where the product is taken over all prime numbers p less than or equal to the real number x.

Lemma: For all real numbers x\ge 3, x\#<2^{2x-3}[2]

Proof: Since   x \# =  \lfloor x \rfloor \#, it suffices to prove the result under the assumption that  x = n is an integer. Since \binom{2n}{n} is an integer and all the primes  n+1 \le p \le 2n-1   appear in its numerator, (2n-1)\#/(n)\#  \le  \binom{2n}{n} <2^{2n-2} must hold. The proof proceeds by mathematical induction.

  • n = 3:  n\# = 6 < 8.
  • n = 4:  n\# =6 < 32.
  • If  n odd, n = (2m-1)\# < 2^{2(2m-1)-3}
  • If  n even, n = (2m)\# < 2^{2(2m-3)}
  • n\# < 2^{2n-3}

Thus the lemma is proven.

Proof of Bertrand's Postulate[edit]

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 \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 < pn: by Lemma 3.

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

When  p > \sqrt{2n}, the number \textstyle {2n \choose n} has at most one factor of p. By Lemma 2, for any prime p we have pR(p,n) ≤ 2n, so the product of the pR(p,n) over the primes less than or equal to \sqrt{2n} is at most (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:

\frac{4^n}{2n }
       \le \binom{2n}{n}
       = \left(\prod_{p \le \sqrt{2n}} p^{R(p,n)}\right) \left(\prod_{\sqrt{2n} < p \le \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)\# \le (2n)^{\sqrt{2n}} 4^{2n/3}.\

Taking logarithms yields to

{\frac{\log 4}{3}}n  \le (\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

n  <  468.\

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

Proof by Shigenori Tochiori[edit]

Using Lemma 4, Tochiori refined Erdos's method and proved if there exists a positive integer n \ge 5  
 such that there is no prime number n<p \le 2n  then n < 64 . [3]

First, refine lemma 1 to:

Lemma 1': For any integer n\ge 4, we have

 \frac{4^n}n < \binom{2n}{n}.\

Proof: By induction:  \frac{4^4}4 = 64 < 70 = \binom{8}{4}, and assuming the truth of the lemma for n-1,

 \binom{2n}{n} = 2\,\frac{2n-1}{n}\binom{2(n-1)}{n-1} > 2\,\frac{2n-1}{n}\frac{4^{n-1}}{n-1} > 2\cdot 2\,\frac{4^{n-1}}{n} = \frac{4^n}{n}.

Then, refine the estimate of the product of all small primes via a better estimate on \pi(x) (the number of primes at most n):

Lemma 5: For any natural number n, we have

\pi(n)\le\frac13n+2.

Proof: Except for p=2,3, every prime number has p\equiv 1 or p\equiv 5 \pmod 6. Thus \pi(n) is upper bounded by the number of numbers with k\equiv 1 or k\equiv 5 \pmod 6, plus one (since this counts 1 and misses 2,3). Thus

\pi(n)\le\left\lfloor\frac{n+5}6\right\rfloor+\left\lfloor\frac{n+1}6\right\rfloor+1\le\frac{n+5}6+\frac{n+1}6+1=\frac13n+2.

Now, calculating the binomial coefficient as in the previous section, we can use the improved bounds to get (for n\ge5, which implies \sqrt{2n}\ge3 so that \sqrt{2n}\#\ge3\#=6):

\begin{align}
\frac{4^n}{n}&\le \binom{2n}{n} \\
&= \prod_{p \le \sqrt{2n}} p^{R(p,n)}\cdot\prod_{\sqrt{2n} < p \le \frac{2n}{3}} p^{R(p,n)}\\
&< (2n)^{\pi(\sqrt{2n})}  \prod_{\sqrt{2n} < p \leq \frac{2n}{3}} p = (2n)^{\frac13\sqrt{2n}+2} \frac{(2n/3)\#}{\sqrt{2n}\#}\\
&<(2n)^{\frac13\sqrt{2n}+2}\frac{2^{2\cdot2n/3-3}}6<(2n)^{\frac13\sqrt{2n}+2}2^{4n/3-5}.
\end{align}

Taking logarithms to get

\frac23n\log 2< \frac13\sqrt{2n}\log 2n+3\log \frac n2

and dividing both sides by \frac23n:

\log 2<\sqrt{2}\cdot\frac{\log\sqrt{n}}{\sqrt{n}}+\frac94\frac{\log \frac n2}{\frac n2}+\frac{\log 2}{\sqrt{2n}}\equiv f(n)\; .

Now the function g(x)=\frac{\log x}x is decreasing for x\ge e, so f(n) is decreasing when n\ge e^2>2e. But

\frac{f(2^6)}{\log 2}=\sqrt{2}\cdot\frac{3}{8}+\frac94\cdot\frac{5}{32}+\frac{\sqrt{2}}{16}=0.97\dots<1<\frac{f(n)}{\log 2},

so n<2^6=64. The remaining cases are proven by an explicit list of primes, as above.

References[edit]