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?

Thank you for your help.