Proof of Bertrand's postulate


Contributors to Wikimedia projects

Article Images

In mathematics, Bertrand's postulate (actually a theorem) states that for each there is a prime such that . It was first proven by Chebyshev, and a short but advanced proof was given by Ramanujan.[1]

The following elementary proof was published by Paul Erdős in 1932, as one of his earliest mathematical publications.[2] The basic idea is to show that the central binomial coefficients need to have a prime factor within the interval in order to be large enough. This is achieved through analysis of the factorization of the central binomial coefficients.

The main steps of the proof are as follows. First, show that the contribution of every prime power factor in the prime decomposition of the central binomial coefficient is at most . Then show that every prime larger than appears at most once.

The next step is to prove that has no prime factors in the interval . As a consequence of these bounds, the contribution to the size of coming from all the prime factors that are at most grows asymptotically as for some . Since the asymptotic growth of the central binomial coefficient is at least , the conclusion is that, by contradiction and for large enough , the binomial coefficient must have another prime factor, which can only lie between and .

The argument given is valid for all . The remaining values of  are by direct inspection, which completes the proof. This is a very good point.

Lemmas in the proof

The proof uses the following four lemmas to establish facts about the primes present in the central binomial coefficients.

Lemma 1

For any integer  , we have

 

Proof: Applying the binomial theorem,

 

since   is the largest term in the sum in the right-hand side, and the sum has   terms (including the initial   outside the summation).

Lemma 2

For a fixed prime  , define   to be the p-adic order of  , that is, the largest natural number   such that   divides  .

For any prime  ,  .

Proof: The exponent of   in   is given by Legendre's formula

 

so

 

But each term of the last summation must be either zero (if  ) or one (if  ), and all terms with   are zero. Therefore,

 

and

 

Lemma 3

If   is odd and  , then  

Proof: There are exactly two factors of   in the numerator of the expression  , coming from the two terms   and   in  , and also two factors of   in the denominator from one copy of the term   in each of the two factors of  . These factors all cancel, leaving no factors of   in  . (The bound on   in the preconditions of the lemma ensures that   is too large to be a term of the numerator, and the assumption that   is odd is needed to ensure that   contributes only one factor of   to the numerator.)

Lemma 4

An upper bound is supplied for the primorial function,

 

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

For all real numbers  ,  .

Proof: Since   and  , it suffices to prove the result under the assumption that   is an integer,   Since   is an integer and all the primes   appear in its numerator but not in its denominator, we have

 

The proof proceeds by complete induction on  

  • If  , then  
  • If  , then  
  • If   is odd,  , then by the above estimate and the induction assumption, since   and   it is
 
  • If   is even and   then by the above estimate and the induction assumption, since   and   it is
 .

Only   is used in the proof.

Proof of Bertrand's Postulate

Assume that 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 the largest prime less than twice its predecessor) such that n < p < 2n. Therefore, n ≥ 468.

There are no prime factors p of   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   the number   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   is at most  . Then, starting with Lemma 1 and decomposing the right-hand side into its prime factorization, and finally using Lemma 4, these bounds give:

 

Taking logarithms yields to

 

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

 

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

Addendum to proof

It is possible to reduce the bound for n to  .

Lemma 1 can be expressed as

 

for  , and because   for  , we can say that the product   is at most  , which gives

 

which is true for   and false for  .

References

  1. ^ Ramanujan, S. (1919), "A proof of Bertrand's postulate", Journal of the Indian Mathematical Society, 11: 181–182
  2. ^ Erdős, Pál (1932), "Beweis eines Satzes von Tschebyschef" [Proof of a theorem of Chebyshev] (PDF), Acta Litt. Sci. Szeged (in German), 5: 194–198, Zbl 0004.10103