Today, I am beginning a four-post series on the proof to Bertrand's Postulate. This postulate asks the following question: is there always a prime number between a number and its double. For instance, the number 3 doubled is 6, and 5 is prime. The number 4 doubled is 8, and 7 is prime. Number theorists wondered if this would work forever.
The proof for this is written up on wikipedia in a pretty short text, but it has lots of advanced notating and vocabulary. I could tell when reading it that the proof itself was not above my head, but the article was still extremely difficult to understand. So, I made it a project for myself to decode that article, and I eventually figured it out. Since it is a pretty cool proof when explained in a simpler way, I decided to share it. It is a long one, which is why I am breaking it into four parts. I am also making sure that we have most of the necessary knowledge covered in this post so that we can continue on. Some of the information discussed in each post is also interesting on its own, so don't stress out if you can only follow pieces of the proof. I can barely follow parts of it as well.
First, here are some definitions to make sure you understand:
Integer: a number that can be defined as positive, negative, or zero (e.g. 3, -2, and 0 are integers; 2.4 and π are non-integers)
Even Number: a number that is a multiple of two (written as 2m)
Odd Number: one more than an even number (written as 2m + 1)
Sum: the answer to an addition problem (e.g. the sum of 2 and 7 is 9)
Product: the answer to a multiplication problem (e.g. the product of 3 and 5 is 15)
Prime Number: a number that is only divisible by one and itself
Prime Power: a number that is a positive integer power of a single prime number
Factor: a number that evenly divides into another number (e.g. 6 is a factor of 18; 3 is a prime factor of 12)
Prime Factorization: the decomposition of a number into a product of its prime factors (e.g. 4680 = 23 • 32 • 5 • 13)
Polynomial Expansion: a polynomial’s expansion is a way to write the polynomial such that it is a sum of products (e.g. 2(x - 7) has a polynomial expansion of 2x - 14)
Law of Exponents: the expression ap • aq can be simplified to ap+q, or similarly, the expression ap ÷ aq can be simplified to ap–q, or the expression (ap)q can be simplified to apq
Also, for some historical context, here are some of the mathematicians that had an influence on this postulate:
Joseph Louis François Bertrand - born March 11, 1822 in Paris, France; died April 5, 1900 in Paris, France. Bertrand was a professor at the École Polytechnique and Collège de France and was known for his contributions to number theory, differential geometry, probability theory, economics, and thermodynamics. He was the first to conjecture Bertrand’s Postulate, and confirmed by hand the first three-million values of n.
Pafnuty Lvovich Chebyshev - born May 16, 1821 in Okatovo, Russia (near Moscow); died December 8, 1894 in St. Petersburg, Russia. Chebyshev was a professor at St. Petersburg University, and was known for his contributions to probability, statistics, mechanics, and number theory. In 1850, he was the first to prove Bertrand’s Postulate, which gave the theorem nicknames such as the “Bertrand-Chebyshev Theorem” or “Chebyshev’s Theorem.”
Srinivasa Ramanujan - born December 22, 1887 in Erode, India (near Chennai); died April 26, 1920 in Chennai, India. Though an autodidact, Ramanujan is said to be one of the best mathematicians of all time, making a remarkable impact in mathematical analysis, number theory, infinite series, and continued fractions. Using properties of the Gamma Function (a function commonly used in statistics and combinatorics), Ramanujan was able to provide a simpler version of Chebyshev’s proof in 1919.
Paul Erdös - born March 26, 1913 in Budapest, Hungary; died September 20, 1996 in Warsaw, Poland. Erdös spent his life traveling from university to university collaborating with different professors on problems in fields such as combinatorics, graph theory, number theory, set theory, and probability theory. He was known for finding extremely elementary proofs for various conjectures, which he did with Bertrand’s Postulate in 1934.
Blaise Pascal - born June 19, 1623 in Clermont-Ferrand, France; died August 19, 1662 in Paris, France. In addition to his accomplishments in number theory, projective geometry, probability theory, and economics, Pascal was a physicist, philosopher, theologist, and the inventor of the first digital calculator. He is possibly best known for popularizing Pascal’s Triangle, which plays a role in Erdös’s proof of Bertrand’s Postulate.
Adrien-Marie Legendre - born September 18, 1752 in Paris, France; died January 10, 1833 in Paris, France. Legendre was a professor at the École Militaire and École Normale, and was known for his contribution to number theory, elliptic functions, calculus, and applied mathematics. He created the formula to find the frequency of prime factors in factorials, which is now often called Legendre’s Theorem.
I'm sure there are more, but those six were some of the most prominent. Now, let's begin to tell the tale of proving Bertrand's Postulate.
In 1845, Joseph Bertrand proposed the idea that there will always be a prime number between a number and its double, or n and 2n. Bertrand had already checked by hand every number between two and three-million and found that they all fit this hypothesis. But, numbers are infinite, and people can’t go checking every single one. This is why a mathematical proof would be needed to verify this conjecture and turn it into a theorem.
Pafnuty Chebyshev offered a full mathematical proof of this statement in 1850; he used logic and mathematics to prove that any value of n would have a prime between it and its double. A simpler proof was offered in 1919 by Srinivasa Ramanujan, and an even simpler one was demonstrated by Paul Erdös in 1934. A quote commonly attributed to Erdös is:
Chebyshev said it, but I’ll say it again
There is always a prime between n and 2n.
To understand Erdös’s proof, it is important to first know a few properties of Pascal’s Triangle, which was popularized by Blaise Pascal. Pascal’s triangle starts with a triangular formation of ones.
1
1 1
1 1
1 1
1 1
To fill in a blank space in this triangle, one then must add the two numbers above it. For instance, the space in the third row between the two ones would be filled in by adding the 1 above and to the left and the 1 above and to the right. 1 + 1 = 2, so this space would have a 2 in it.
1
1 1
1 2 1
1 1
1 1
Similarly, the square underneath the 1 and the 2 can be filled in with a 3.
1
1 1
1 2 1
1 3 1
1 1
By continuing this process, the triangle can be extended infinitely.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
With this triangle, each number can be defined by saying its row number and what position it is in in that row. Since the ones are the base of the triangle, and are not necessarily part of it, the top row is defined to be row zero and the left-most element in each row is element zero. By keeping this in mind, any number in Pascal’s Triangle can be quickly found. For example, the fifth element of row seven would be 21.
Rather than going through the process of saying “the kth element of row n in Pascal’s Triangle,” mathematicians will often use the notation “n choose k,” with n being the row number and k being the number’s position in the row. For instance, “6 choose 2” = 15.
In Pascal’s Triangle, there are some numbers that stick out because they are in the center of their row. For instance:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
These numbers have a very simple notation in the “n choose k” format because k is half of n. Since n and k can never be fractions (there is no 2.7th element in a row), the best way to write these numbers is “2n choose n.” Mathematicians call these numbers as central binomial coefficients. Note that the central binomial coefficient is the largest number in each row of the triangle.
These central binomial coefficients play a huge role in Erdös’s proof. What Erdös actually proved was that there is always a prime between n and 2n that is a prime factor of the corresponding central binomial coefficient: “2n choose n.”
Next week, I will continue on and show some of the first steps of the actual proof.
No comments:
Post a Comment