Bertrand's Postulate Part 2: Restricting the Factor Domain

Click here to see part one of this four week series.



This is week two of a four week series on the proof to Bertrand's Postulate. Last week, I went over some history and definitions pertaining to the problem, as well as introducing some facts about Pascal's triangle that come into play in the proof. This week, we can begin the actual process of proving that there is always a prime between n and 2n.

The proof utilizes the central binomial coefficients that I explained last week, each one being written in the form "2n choose n." The final conclusion actually states that every number of the form "2n choose n" has a prime factor between n and 2n. By determining this, we will then be able to say that there must always then be a prime between n and 2n. But how do we prove that?

This week, we will look at how to limit the range of possible prime factors of "2n choose n." If there are fewer possibilities of where these factors can exist on the number line, then it will be tougher (and eventually impossible) to find a number of this form without a prime factor between n and 2n. Next week, we will set a lower and upper bound on the size of "2n choose n," which will provide an inequality to work with. And in the last post, we will show that because of all of these restraints, there must be a prime between n and 2n. So let's get to it!

The first step is to prove that none of the prime factors of “2n choose n” are between ⅔n and n. By proving this, it will restrict the amount of spots for the prime factor to exist, and hopefully at some point restricting it to between n and 2n.

To prove this, we first need to go over the definition of factorials.

The number n factorial (written n!) is the product of all of the positive integers less than or equal to n.

For example, 4! = 4 • 3 • 2 • 1 = 24. 7! = 7 • 6 • 5 • 4 • 3 • 2 • 1 = 5040.

How do factorials play into this proof? Well, assuming that the prime p is between ⅔n and n, p will only appear once in the prime factorization of n!. This is because n! only has prime factors that are less than n. For p to have been multiplied in twice, that means 2p also must be less than n. But, what happens when we multiply the inequality by two?

⅔n < p < n
2(⅔n) < 2p < 2n
1⅓n < 2p < 2n

This means that 2p is at least 1⅓n, which cannot be a factor of n!. So, a factor of p can only appear once. By similar logic, there are two factors of p in (2n)!.

A simpler way to write “number of times a prime factor appears in a number” would be to use the following notation:

v_p(x)

Assume that p is the prime number and x is the number that the prime is a factor of. For example:

v₂(24) = 3
v₅(50) = 2
v_p((2n)!) = 1
v_p((2n)!) = 2

There exists a formula that enables one to find the number of times a certain prime factor appears in the factorization of a quantity like “2n choose n.” For that example, the formula goes:

v_p(“2n choose n”) = v_p((2n)!) - 2v_p(n!)

The values of p or n are not defined (aside from the fact that p is between ⅔n and n), but we just determined the number of times p appeared in n! and (2n)! nonetheless. It appeared in n! once and (2n)! twice. So, those values can be substituted in to see how many p’s can be in “2n choose n.”

v_p(“2n choose n”) = v_p((2n)!) - 2v_p(n!)
v_p(“2n choose n”) = 2 - 2(1)
v_p(“2n choose n”) = 2 - 2
v_p(“2n choose n”) = 0

So, p appears zero times when it is between ⅔n and n. In other words, “2n choose n” has no prime factors between ⅔n and n, thus completing this part of the proof.

The second step is to prove that there are no prime factors of “2n choose n” that are greater than 2n. Furthermore, this step will also demonstrate that there are no powers of prime factors of “2n choose n” greater than 2n. This will continue the process of restricting possible prime factors of step one, which will later make it impossible to have no prime factors between n and 2n.

This step will require another definition, but this one is extremely simple. The name of it makes it sound much more complicated than it is.

A number’s floor function is the greatest integer less than or equal to that number. For example:

floor(7.5) = 7
floor(18) = 18
floor(π) = 3

These floor functions play a role in Legendre’s Theorem (created by Adrien-Marie Legendre), which is used in the proof of step two. Legendre’s Theorem states that to find the prime factorization of n!, one simply plugs prime numbers into the following formula, which will find their exponent.

v_p(n!) = floor(n/p) + floor(n/p²) + floor(n/p³) + floor(n/p⁴) + ...

For example, let’s find the exponent of 2 in the number 4! = 24.

v_p(n!) = floor(n/p) + floor(n/p²) + floor(n/p³) + floor(n/p⁴) + ...
v₂(4!) = floor(4/2) + floor(4/2²) + floor(4/2³) + floor(4/2⁴) + ...
v₂(4!) = floor(4/2) + floor(4/4) + floor(4/8) + floor(4/16) + ...
v₂(4!) = floor(2) + floor(1) + floor(0.5) + floor(0.25) + ...
v₂(4!) = 2 + 1 + 0 + 0 + ...
v₂(4!) = 3

Let’s return to the formula we used in the last step to find the exponent on a prime factor of “2n choose n.”

v_p(“2n choose n”) = v_p((2n)!) - 2v_p(n!)

It is impossible to use logic to define the exponent on primes greater than 2n for the terms in this formula. However, we can use Legendre’s Theorem to determine the exponent on prime factors of n! and (2n)!.

v_p(“2n choose n”) = v_p((2n)!) - 2v_p(n!)
v_p(“2n choose n”) = [floor(2n/p) + floor(2n/p²) + ...] - 2[floor(n/p) + floor(n/p²) + ...]

Though 2n cannot be plugged in for p (2n is even, and therefore is not prime), but any number larger than 2n can be plugged in to see if it has a non-zero exponent. But, the first term in each of the two infinite series will end up as zero (2n divided by a number larger than 2n is less than one, and thus, will have a floor function of zero). Since each term in each series is shrinking, they will all end up with a floor function of zero. So, both infinite sums will simplify to zero.

v_p(“2n choose n”) = 0 - 2(0)
v_p(“2n choose n”) = 0 - 0
v_p(“2n choose n”) = 0

So, all p values greater than 2n will have an exponent of zero, meaning that there are no prime factors of “2n choose n” greater than 2n. This completes the second step.

Make sure to return next week so we can start to restrain the size of the number "2n choose n," and then we will be just inches away from the proof of Bertrand's Postulate.

Bertrand's Postulate Part 1: Definitions, History, and an Introduction

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 = 2³ • 3² • 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 a^p • a^q can be simplified to a^p+q, or similarly, the expression a^p ÷ a^q can be simplified to a^p–q, or the expression (a^p)^q can be simplified to a^pq

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.

Happy End Problem

As this is the last post of the year, I thought it would be appropriate to end with a post on the "Happy End Problem." I will explain the problem, which is pretty cool in itself, and then talk a little bit about the history behind it.

The initial question was if any five points were placed on a plane with no three of them in a straight line, will four of those points always form a convex quadrilateral? For example, in the following image:

The following convex quadrilateral can be formed:

Will this always work? As usual, I encourage you to grab a scrap piece of paper and try out a few examples. Have fun with it. Get creative! You will end up finding that no matter how you position the five points, you cannot get a combination without a convex quadrilateral.

Why is this true? In fact, there is a very easy way to prove it. Let's analyze three cases.

The first case is the top left one in the red, where the five points form a convex pentagon. In this instance, connecting any four of the points will form a convex quadrilateral by nature.

The second case is the top right one in the blue, where one point is located in between the four outside points. The illustration shows the inside point being included in the quadrilateral, but it could have just as easily been made as just the four outside points. This will continue to work for any combination of this nature by logic.

The third case is the bottom one in the yellow, where two points are enclosed in a triangle. When you draw a line between the two center points, two of the outside points will end up on one side and one will be on the other. Using the two outside points as your third and fourth vertices will form a quadrilateral without flaw.

Now, you might be wondering if one can prove a similar case with a convex pentagon. Could it be done with six? Seven? Eight? Turns out, nine points are required for it to work every time. As you can see below, eight points is just one too few.

What about convex hexagons? Or heptagons? Or octagons? Or chiliagons (1000-sided polygons)? Well, what many mathematicians will do from here is look for a formula to figure out how many points are required for a given n-gon. We know that for a triangle (n = 3), just 3 points are needed (all triangles are convex). For a quadrilateral (n = 4), we proved that 5 points are needed. For a pentagon (n = 5), I mentioned that 9 points are needed. Do you see the pattern?

3, 5, 9, ...

It is not easy to spot at first, but what if I subtract one from each of those terms:

2, 4, 8, ...

They are all now powers of two! This pattern seems to fit the formula A_n = 2^n-2 + 1. Plugging six in for n would give:

A₆ = 2^6-2 + 1
A₆ = 16 + 1
A₆ = 17

This formula predicts that seventeen points would be required for a hexagon. Mathematicians would then work to try to prove that this is the case. Further, they would try to prove that for any value of n, the A_n formula holds true.

George Szekeres (1911-2005; a Hungarian-Austrailian mathematician and analytical chemist) and Esther Klein (1910-2005, another Hungarian-Austrailian mathematician) worked together to prove that all values of n will have a finite A_n output (there will be a number of points that creates the ability for a convex n-gon to be formed), but they could not get this bound down to the formula above. Soon after this proof was published, Szekeres and Klein married each other, which inspired the name "Happy End Problem."

Paul Erdös (1913-1996; a Hungarian mathematician), possibly one of the most influential of the twentieth century), was able to prove successfully that with 71 points, a hexagon can always be drawn.

Sixty years later, Ronald Graham (born 1935; a Californian mathematician) and his wife, Fan Chung, decided to take a swing at the problem. While on a plane ride to a math conference in New Zealand, they were able to lower Erdös's bound to 70 points, which doesn't sound like much, but it brought the problem back into the minds of mathematicians. It was also ironic that another achievement pertaining to the Happy End Problem was from a couple.

Daniel Kleitman (born 1934; an applied mathematician at MIT) and Lior Pachter (born 1972; an Israeli mathematician and molecular biologist at Berkeley College) worked together to lower the upper bound to 65 points. The number was then lowered to 37 points, and has yet to be lowered further.

Although lots of progress has been made on this problem, the overarching proof still has not yet been found. There has been no counterexample to the A_n formula, and there has certainly been no guaranteed formula to generate the future values. People often wonder what a mathematician actually does for his/her job. A big part of it is trying to figure out the answers to these unsolved problems, which can often be understood by the average person. Try playing around with it and you might make a discovery too.

Figure Out The Number Of Digits In Gigantic Numbers

In science and math, you often run across numbers that are too big to be written in standard form. They are usually written in scientific notation, but they are also sometimes written as a number to a certain power. For instance, one might say that there are 2²⁰ outcomes of the flipping of twenty coins rather than saying 1.049x10⁶ ways.

By using that power, your information is likely more accurate. However, this power does not tell you much about the number. Most of us would have no idea if 2²⁰ is in the thousands, millions, billions, etc. at the first glance.

First, lets ask a question. What is the common logarithm of a number, or what can you gather from it? Well, the common logarithm is the power that ten has to be raised to to obtain that number. For instance:

log(100) = 2

log(5000) = 3.69897

log(6283185) = 6.79818

What do you notice about these numbers? It's not clear at first, but count the number of digits in each of the inputs. You will find that the common log is always just a little bit below that number. In fact, to figure out the number of digits in a number, all you have to do is take the common log and round up to the nearest integer.

How can this be used to find the number of digits in a power? Interestingly enough, there is a logarithmic identity stating that the log of a number raised to the power is equal to the power times the log of the number. For example,

log(27) = 3log(3)

ln(32) = 5ln(2)

log(2²⁰) = 20log(2)

Look at the last example there. We just simplified the gigantic 2²⁰ to a reasonable looking 20log(2), which is the formula to figure out the number of digits it has. In other words, the number of digits in 2²⁰ is just 20log(2) rounded to the nearest integer. Plugging this into a calculator tells you that the log is 6.0206, meaning that there are seven digits in the number. If you multiply it out, you will find that 2²⁰ = 1048576, which does indeed have seven digits. 

So whenever a type of problem pops up with a power of this sort, try to determine how many digits it is. Chances are you will gain a much better understanding of the statistic when you perform this quick calculation.

Math in the News: The Influences of Politics

Though mathematics is normally a pretty concrete subject, people's intuition for it is not. Probability and statistics in particular is a very difficult area for us to grasp, as you've seen with the Monty Hall Problem I talked about a few weeks ago.

Here is another example of mathematical aptitude being influenced by an outside source, but this time, it is not just a matter of lack of skill or desire to be correct. It is also influenced sometimes by political views, as Kevin Drum shows in this news article. Check it out!

http://m.motherjones.com/kevin-drum/2013/09/politics-destroys-math-ability