Wednesday, November 18, 2009

Bertrand's Postulate (Theorem)

In today's blog, I will present a proof for Bertrand's Postulate which is really a theorem.

The content is taken primarily from an excellent Wikipedia article.

Lemma 1:

If n is greater than 5, then 2n/3 is greater than 2n

Proof:

(1) For n ≥ 5, 2n(2n-9) is greater than 0 since 2n ≥ 10 and 2n-9 ≥ 1.

(2) 2n(2n - 9) = 4n2 - 18n.

(3) Since 4n2 - 18n is greater than 0, 4n2 is greater than 18n.

(4) Dividing both sides by 9 gives us 4n2/9 is greater than 2n.

(5) Taking the square root of both sides gives us 2n/3 is greater than 2n

QED

Lemma 2:

Let p be a prime number that is greater than 2n

Let x be the highest nonnegative integer such that px divides 2n!/[(n!)(n!)]

then:

Proof:

(1) We know that in general, the maximum power of p that divides n! is (see Theorem, here):

(2) So the highest power of p that divides (2n)!/[(n!)(n!)] is:

(3) Since p is greater than 2n, it follows that p2 is greater than 2n. So we only need to consider the case where i=1.

(4) This leaves us with:

QED

Lemma 3:

Bertrand's Posulate is true for n less than 2048

Proof:

Between any n less than 2048 and its double, one will find one of the following primes:

3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 and 2503

since:

n = 2 --> 3

n between 3 and 4 --> 5

n between 5 and 6 --> 7

n between 7 and 12 --> 13

n between 13 and 22 --> 23

n between 23 and 42 --> 43

n between 43 and 82 --> 83

n between 83 and 162 --> 163

n between 163 and 316 --> 317

n between 317 and 630 --> 631

n between 631 and 1258 --> 1259

n between 1259 and 2047 --> 2503

QED

Definition 1: R(p,n): maximum divisor of 2n!/(n!)(n!)

Let R(p,n) be the function that returns the maximum power of a given prime that divides 2n!/(n!)(n!)

For any prime p, pR(p,n) divides 2n!/(n!)(n!) but pR(p,n)+1 does not.

Example 1: R(3,5)

(2*5)!/(5!)(5!) = 10*9*8*7*6/5*4*3*2 = 2*9*2*7*2*2 = 24*32*7.

R(3,5) = 2 since 32 divides 24*32*7 but 33 = 27 does not.

Lemma 4:

For all p, pR(p,n) ≤ 2n

Proof:

(1) The multiplicity m of p in a factorial n! (see Theorem 1, here) is:

so that pm divides n! but pm+1 does not.

(2) Based on this, the formula for R(p,n) is:

which is equivalent to:

(3) We can see that if pi is greater than 2n, then:

floor(2n/pi) = 0 and floor(n/pi) = 0 so that we have:

floor(2n/pi) - 2*(n/pi) = 0

so that we have:

(4) Using the Division Algorithm (see Theorem 1, here), there exists q,r such that:

n = qpi + r

where r is less than pi

(5) From this, we can see that:

since:

Case 1: r = 0

In this case, floor(2n/pi) = 2q and 2*floor(n/pi) = 2*q so that:

floor(2n/pi) - 2*floor(2n/pi) = 0

Case 2: r is less than (1/2)pi

In this case, floor(2n/pi) = 2q and 2*floor(n/pi) = 2*q so that:

floor(2n/pi) - 2*floor(2n/pi) = 0

Case 3: r ≥ (1/2)pi

In this case, floor(2n/pi) = 2q+1 and 2*floor(n/pi) = 2*q so that:

floor(2n/pi) - 2*floor(2n/pi) = 1

(5) So that we have:

pi ≤ plogp(2n) = 2n.

QED

Lemma 5:

For all i:

0 ≤ i ≤ 2n → (2n!)/(n!)(n!) ≥ (2n!)/(i!)(2n-i)!

Proof:

(1) We know that (see Definition 3, here for review of C(n,r) if needed):

C(2n,i-1) = (2n!)/(i-1)!(2n-i+1)!

C(2n,i) = (2n!)/(i!)(2n-i)!

(2) So, we see that:

C(2n,i) = (2n-i+1)/(i)*C(2n,i-1)

and

C(2n,i-1) = (i)/(2n-i+1)*C(2n,i)

(3) If i ≤ n, it follows that:

2n - i + 1 is greater than i since 2n - i + 1 ≥ n+1

So up to i=n, C(2n,i) is greater than C(2n,i-1)

(5) If i ≥ n+1, it follows that:

i is greater than 2n - i + 1 since 2n - i + 1 ≤ n

So down to i=n+1, C(2n,i-1) is greater than C(2n,i)

(6) So, we have shown that C(2n,n) is greater than C(2n,i) for i less than n and C(2n,n) is greater than C(2n,i) for i greater than n.

QED

Corollary 5.1:

Proof:

(1) Using the Binomial Theorem (see Theorem, here):

(2) Using Lemma 5 above, we know that:

(3) So that we have:

(4) And dividing both sides by (2n+1) finishes the proof.

QED

Lemma 6:

If 2t is less than 8t, then t is less than 6

Proof:

(1) If t=6, then 2t is greater than 8t since:

26 = 64

8(6) = 48

(2) Assume it is true up to some t ≥ 6 so that: 2t is greater than 8t.

(3) Then 2*(2t)=2t+1 is greater than 2*8t = 16t

(4) 16t is greater than 8t+8 since 16=8t + 8t and for t ≥ 6, 8t is greater than 8.

(5) So that we have 2t+1 is greater than 8t+8 = 8(t+1).

QED

Lemma 7:

If:

Then:

n is less than 2048.

Proof:

(1) Let n = 22t-1

(2) So 2n = 22t

(3) 22t = 2t

(4) So 2nln(2) = 2tln(2)

(5) (4)ln(2n) = 4ln(22t) = 2t*4*ln(2)

(6) Dividing both sides by ln(2) gives us:

2t is less than 8t

(7) Using Lemma 6 above, we conclude that t is less than 6.

(8) So, it follows that n is less than 22(6)-1 = 211 = 2048.

QED

Theorem: Bertrand's Postulate

For any n, there exists a prime p such that p is greater than n and less than 2n.

Proof:

(1) We know that Bertrand's Postulate is true for n less than 2048 [see Lemma 3 above]

(2) Assume for some n ≥ 2048, there is no prime between n and 2n.

(3) Let p be the largest prime factor of (2n!)/[(n!)(n!)] that is less than or equal to n.

(4) Using Lemma 1 above, we know that p ≤ 2n/3 since:

(a) Assume that that p is greater than 2n/3.

(b) Since n ≥ 2048, using Lemma 1 above, p is also greater than 2n

(c) This means that the highest power of x is given by (see Lemma 2 above):

(d) Since 2n/3 is less than p, it follows that 2n is less than 3p, and further that 2n/p is less than 3 so that 2n/p ≤ 2.

(e) But from step #3 above, we know that n ≥ p so that we have n/p ≥ 1.

(f) This gives us that 2n/p ≤ 2 and n/p ≥ 1 so that we have:

x = floor(2n/p) - 2*floor(n/p) ≤ 2 - 2*1 = 0.

(g) So, under these circumstances, the highest power of x is 0 which means that there is no such p and we can conclude that p ≤ 2n/3.

(5) From step #4, we have:

(2n!)/(n!n!) = ∏ (p ≤ 2n/3) pR(p,n)

where R(p,n) is a function on p,n such that pR(p,n) divides (2n!)/(n!n!) but pR(p,n)+1 does not. [see Definition 1 above]

(6) From Lemma 2 above, we know that if p is greater than 2n, then R(p,n)=1 so that we have:

(7) Since there are less than 2n primes less than 2n, using Lemma 4 above, we have:

(8) If we use a limit for primorials (see Theorem, here), we have:

(9) Using Corollary 5.1 above, we also have:

(10) So, putting it all together, we have:

(11) If we multiply 4(-2n/3) to both sides we get:

(12) Now, since n ≥ 1, we note that 4n2 is greater than 2n+1

(a) For n=1, 4(1)2 is greater than 2(1)+1

(b) Assume that 4n2 is greater than 2n+1

(c) Since n ≥ 1, 4n2 + 8n is greater than 2n+1+2

(d) 4n2 + 8n + 1 is greater than 2(n+1) + 1

(e) And:

4(n+1)2 is greater than 2(n+1)+1

(13) So it follows that:

(14) Since n is greater than 18, it follows that (4/3)√2n is greater than 2 + √2n since:

(a) 2(n) is greater than 6

(b) (4/3)√2n = (1/3)√2n + √2n

(c) And (1/3)√2n is greater than (1/3)*6 = 2.

(15) This gives us:

(16) Putting it all together gives us:

(17) Taking the logarithm of both sides, gives us:

(18) We can simplify this further by multiplying 3 to both sides and noting that 4=22 so that we get:

(19) We can further simplify it by dividing both sides by 2n to get:

(20) But now we use Lemma 7 above to reach a contradiction.

QED

References

1 comment :

Seth said...

Larry,

This isn't relevant to this post; I hope you'll indulge me.

I'm beginning to study abstract algebra for recreational purposes and I'm having trouble establishing whether a group is associative.

Clearly, a counterexample shows when non-associativity. But how would I establish associativity? Right now, I'm looking at dihedral groups of symmetry and addition and multipliction modulo n.

One idea I had for both of these is:
I make a Cayley table and each element shows up once in each column and row.

take three elements x, y, z

and begin with
(xy)z=x(yz)

now xy = some product A
yz = some product B
xz= some product C

this is three equations with three unknowns, x, y, and z, which can be solved based on the evidence from teh Cayley table

Does this establish associativity?