Jump to content

Proof of Bertrand's postulate

From Wikipedia, the free encyclopedia

In mathematics, Bertrand's postulate (now a theorem) states that, for each , there is a prime such that . First conjectured in 1845 by Joseph Bertrand,[1] it was first proven by Chebyshev, and a shorter but also advanced proof was given by Ramanujan.[2]

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

The main steps of the proof are as follows. First, one shows that the contribution of every prime power factor in the prime decomposition of the central binomial coefficient is at most ; then, one shows 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 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 verified by direct inspection, which completes the proof.

Lemmas in the proof

[edit]

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

Lemma 1

[edit]

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

[edit]

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

[edit]

If is an odd prime 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

[edit]

An upper bound is supplied for the primorial function,

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

For all , .

Proof: We use complete induction.

For we have and .

Let us assume that the inequality holds for all . Since is composite, we have

Now let us assume that the inequality holds for all . Since is an integer and all the primes appear only in the numerator, we have

Therefore,

Proof of Bertrand's Postulate

[edit]

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

If 2 ≤ n < 427, 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 ≥ 427.

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 < pn: 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, and since 1 is neither prime nor composite. Then, starting with Lemma 1 and decomposing the right-hand side into its prime factorization, and finally using Lemma 4, these bounds give:

Therefore

, which simplifies to

Taking logarithms yields

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 and it does not for , we obtain

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

Addendum to proof

[edit]

It is possible to reduce the bound to .

For we get , so we can say that the product is at most , which gives

which is true for and false for .

References

[edit]
  1. ^ Bertrand, Joseph (1845), "Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme.", Journal de l'École Royale Polytechnique (in French), 18 (Cahier 30): 123–140.
  2. ^ Ramanujan, S. (1919), "A proof of Bertrand's postulate", Journal of the Indian Mathematical Society, 11: 181–182
  3. ^ Erdős, Pál (1932), "Beweis eines Satzes von Tschebyschef" [Proof of a theorem of Chebyshev] (PDF), Acta Scientarium Mathematicarum (Szeged), 5 (3–4): 194–198, Zbl 004.10103
[edit]