Click here to see part 1 of this four week series.
Click here to see part 2 of this four week series.
Click here to see part 3 of this four week series.
This is the final post in my four week series on Bertrand's Postulate. Using the information we have discussed in the last three weeks, we will officially prove that there is always a prime between a number and its double.
This final step five is the step that will complete the upper bound and provide the proof. Since we have restricted the values of the prime factors so much over the last four steps, we will be able to utilize a technique called proof by contradiction. Last week, we did a proof by induction where we assumed the conclusion was true and did the math from there. With a proof by contradiction, one assumes that the conclusion is false and will later run into a problem.
To prove Bertrand’s Postulate, we will assume that there are no primes between n and 2n. So, this means that there are no prime factors that are:
Keep in mind that this does not include prime powers. We did prove that there are no prime powers greater than 2n, but they can exist below that. So, an upper bound on each prime power would be 2n.
We know that (√(2n))2 is 2n. So, any number greater than √(2n) cannot have a prime power factor. If it did, then the factor would be greater than 2n, which is impossible (see step two). This means that there are at most √(2n) values of 2n (the maximum of a prime power) in the prime factorization of “2n choose n.” So, we can set an upper bound on any prime factor below √(2n) as 2n√(2n).
But there can still be prime factors between √(2n) and ⅔n. They just will have an exponent of one. So, the product of all the primes between √(2n) and ⅔n will cover everything in that interval, since there are no exponents. To make the math simpler, we will just use (⅔n)╫. Multiplying these two quantities together will yield an upper bound on “2n choose n.”
“2n choose n” < 2n√(2n) • (⅔n)╫
In step 4, we set an upper bound on that primorial. (⅔n)╫ is definitely less than 4⅔n. So, we can plug that into the right-hand side to get:
“2n choose n” < 2n√(2n) • 4⅔n
Also, a lower bound was set on “2n choose n” in step 3. We know that it can’t be smaller than 4n/2n. Plug that into the left-hand side to get:
4n/2n < 2n√(2n) • 4⅔n
And now, we are at an equation that can be solved with algebra! Simplifying this takes a lot of logarithms and complicated graphing, but it will end up as:
n < 468
That means that any time n is bigger than 468, the bounds that were created after assuming that there are no primes between n and 2n will not work. This means that there must be a prime between n and 2n every time n is greater than 468 because any other possibility was proven impossible.
The only time where it is theoretically possible for an n value to have no prime between n and 2n is when n is less than 468. But, it was mentioned before that Joseph Bertrand himself found a prime for all n values up through three-million. So, there can’t be a number less than 468 that the postulate doesn’t work for. And thus, Bertrand’s Postulate is proven.
Personally, I do think this proof is really cool. However, it is difficult to be as engaged when it takes four fairly long posts to prove. But what I find more interesting than the actual mathematical side of it is that it is understandable to just someone with a couple years of high school mathematics. I did categorize these posts with the other advanced ones, but there is no need for calculus or even much precalculus to understand (the only precalculus is really the logarithms that I left out at the end). The real barrier in understanding them is the notation that mathematicians use. The actual paper used much more complex language as well as things like sigma notation that wouldn't make as much sense initially to a high school student. But after that language is translated into something simpler, the content itself is certainly understandable and even quite interesting. I am looking forward to making more of these series with other mathematical papers in the months to come.
- greater than 2n by step 2
- equal to 2n because 2n is even, and therefore, not prime
- between n and 2n because of our assumption
- between ⅔n and n by step 1
Personally, I do think this proof is really cool. However, it is difficult to be as engaged when it takes four fairly long posts to prove. But what I find more interesting than the actual mathematical side of it is that it is understandable to just someone with a couple years of high school mathematics. I did categorize these posts with the other advanced ones, but there is no need for calculus or even much precalculus to understand (the only precalculus is really the logarithms that I left out at the end). The real barrier in understanding them is the notation that mathematicians use. The actual paper used much more complex language as well as things like sigma notation that wouldn't make as much sense initially to a high school student. But after that language is translated into something simpler, the content itself is certainly understandable and even quite interesting. I am looking forward to making more of these series with other mathematical papers in the months to come.
No comments:
Post a Comment