Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Erdos' Proof of Bertrand's Postulate


Date: Sun, 23 Mar 1997 23:59:43 -0500 (EST)
From: Liz Biermann
Subject: Bertrand's Postulate

I am looking for a proof of Bertrand's Postulate (there exists a prime 
number between n and 2n (n>2)), a.k.a. Chebychev's Theorem (since he 
is the one who actually proved it).  

I have read numerous times that Erdos came up with a very simple 
proof, but I have not been able to find it.

Thanks in advance for any help you can provide!
--Liz Biermann, Cornell College


From: Anonymous
Date: Thu, 27 Mar 1997 11:17:47 -0800
Subject: Re: Bertrand's Postulate

Here's Erdos's proof of Bertrand's Postulate, paraphrased from Hardy 
and Wright, "An Introduction to the Theory of Numbers."

The proof of Bertand's Postulate uses some simple properties of
the function theta(x), defined for x >= 0 by

   theta(x) = sum(log p: p is prime and 0 < p <= x)

We show that

   theta(x) < 2x log(2)

(I use log(x) always to mean the natural log of x.)

It is enough to show this when x is an integer.  We're going to
prove this by induction.

The trick is to look at the binomial coefficient C(2m+1, m), which is

   (2m+1)!/m!(m+1)!

Call this M for short.

Let p be a prime such that m+1 < p <= 2m+1.  Then p divides the
numerator of M but not the denominator, so p divides M.  So the
product of all such primes divides M, and

   sum (log p: m+1 < p <= 2m+1) < log M

or in terms of the function theta(x)

   theta(2m+1) - theta(m+1) < log M.

On the other hand, the binomial expansion of (1 + 1)^(2m+1)
has two terms equal to M, so

   2M < 2^(2m+1)

   M < 2^2m

   log M < 2m log(2)

so

   theta(2m+1) - theta(m+1) < 2m log(2)

We're going to use this formula in the induction step of our proof
that 

   theta(x) < 2x log(2)

For x = 1, we have

   theta(1) = 0 < 2 log(2)

and for x = 2, we have

   theta(2) = log 2 < 4 log(2)

Suppose the inequality is true for x < n.  Let us prove it for x = n.

If n is even and > 2, then it is certainly not prime, so

   theta(n) = theta(n-1) < 2(n-1) log(2) < 2n log(2).

If n is odd, let n = 2m + 1.  Then by what we proved above, we have

   theta(2m+1) - theta(m+1) < 2m log(2)

      heta(2m+1) < theta(m+1) + 2m log(2)

      < 2(m+1) log(2) + 2m log(2)

          = (3m + 1) log(2)

          < (4m + 2) log(2)

          = 2n log(2).

This completes the proof that

   theta(x) < 2x log(2).

Let's catch our breath.

The next thing we're going to do is to look at the highest power of
p that divides n!, where p is any prime.  We call this number j(n, p).

We use the notation [x] for the largest integer <= x.

Every p'th number is a multiple of p, so we get [n/p] factors of p
in n!.  But every p^2'th number is a multiple not just of p but of
p squares, and [n/p] doesn't count these, so we need to add [n/p^2}
for these extra factors of p.  Similarly every p^3'th number is a
multiple of p^3 which we have not counted yet.  So the highest
power of p that divides n! is the sum of all the

   [n/p^m]

for m >= 1.  Of course [n/p^m] = 0 as soon as p^m > n:  that is,
for m > log(n)/log(p).

Now we're going to suppose that Bertrand's Postulate is false, and 
that there is no prime p such that n < p < 2n, for some n.  

We're going to look at another binomial coefficient.  This one is

   C(2n,n) = (2n!)/(n!)^2

which we'll call N for short.

By our assumption, all the primes that divide N are <= n.  Now
using the notation above, we have

   N = (2n)!/(n!)^2 =

       product(p^j(2n, p): p <= 2n)
       ----------------------------
       product(p^2j(n, p): p <= n)

but there aren't any primes between n and 2n by assumption, so the
"p <= 2n" in the numerator can be replaced by "p < = n" and we get

   N = product (p^(j(2n, p) - 2j(n, p)): p <= n).

Let's call j(2n, p) - 2j(n, p) k(p) for short.  Taking logs on both
sides, we get

   log N = sum(k(p) log(p): p <= n).

Notice that k(p) is a sum of terms of the form [2x] - 2[x}.
[2x] - 2[x] is always either 0 or 1.  If [2x] is even, [2x] - 2[x]
is 0; otherwise it is 1.

We show first that k(p) = 0 for p > 2n/3.  For in that case,

   2n/3 < p <= n

or   2 <= 2n/p < 3

and [2n/p] = 2, so [2n/p] - 2[n/p] = 0.

   p^2 > (4/9)n^2 > 2n as long as n > 4,

and we can certainly assume n is > 4, since we are assuming there
is no prime between n and 2n, and 5, for example, is between 4 and 8.

So there are no terms involving higher powers of p.

Next we show that terms with k(p) >= 2 don't contribute very much.

To get such a term we have to have p^2 < 2n or p < sqrt(2n), so
the number of such terms is at most sqrt(2n).  k(p), on the other
hand, is a sum of terms [2n/p^m] - 2[n/p^m], which is certainly
0 if p^m > 2n, or m > log(2n)/log(p), so k(p) is at most log(2n)/
log(p), and k(p) log(p) <= log(2n), so

  sum(k(p) log(p) : k(p) >= 2) <= sqrt(2n) log(2n), taking the maximum
possible number of such primes p and a number bigger than any of the
k(p) log(p).

For the terms with k(p) = 1, we have at most

   sum(log(p): p <= 2n/3) = theta(2n/3) < (4n/3) log(2)

by what we proved way back when.

Putting together what we've got so far gives us

   log N < (4n/3) log(2) + sqrt(2n) log(2n).

Time for another breather before we close in for the kill.

Looking back at the definition of N, we have

   2^(2n) = 2 + C(2n, 1) + C(2n, 2) + ... + C(2n, 2n-1)

(Binomial Theorem with first and last terms combined).

This is a sum of 2n terms, the largest of which is C(2n, n) or N.

So

   2^(2n) < 2nN

or

   2n log(2) < log(2n) + log(N)
        <= log(2n) + (4n/3) log(2) + sqrt(2n) log(2n)

by what we proved just before the breather.

Now for large values of n, the only term that counts on the right
side is the 4n/3 log(2), which is smaller than the 2n log(2).  So
what we're going to do is figure out how big n needs to be to make
this inequality false, and then just prove the postulate directly
for smaller values of n.

Take n >= 2^9 and note that log(2n) = log(2^10) = 10 log(2).  Divide
the inequality by log(2) to get

   2^10 < 10 + 2^10(2/3) + (2^5) 10

or
   2^10 (1 - 2/3) < 10 (2^5 + 1)

   2^10 (1/3) < 10 (2^5 + 1)

   2^10 < 30 (2^5 + 1) < 31 (2^5 + 1) = (2^5 - 1) (2^5 + 1)

                  = 2^10 - 1

which is false!!

So the assumptions that Bertrand's Postulate is false for n and that
n >= 2^9 lead to a contradiction.  All that remains is to verify
the postulate for n < 2^9 = 512.

Here we can just look at the sequence of primes

   2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631

each of which is less that twice the one before.

- Dr. Wilkinson,  The Math Forum
  Check out our web site!  http://mathforum.org/dr.math/   

    
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/