Proving theorems and special cases (Part 7): The twin prime conjecture

In a recent class with my future secondary math teachers, we had a fascinating discussion concerning how a teacher should respond to the following question from a student:

Is it ever possible to prove a statement or theorem by proving a special case of the statement or theorem?

Usually, the answer is no. In this series of posts, we’ve already seen that a conjecture could be true for the first 40 cases or even the first $10^{316}$ cases yet ultimately prove false for all cases.

For the next few posts, I thought I’d share a few of the most famous unsolved problems in mathematics… and just how much computational work has been done to check for a counterexample.

2. The twin prime conjecture (see here and here for more information) asserts that there are infinitely many primes that have a difference of 2. For example:

3 and 5 are twin primes;

5 and 7 are twin primes;

11 and 13 are twin primes;

17 and 19 are twin primes;

29 and 31 are twin primes; etc.

While most mathematicians believe the twin prime conjecture is correct, an explicit proof has not been found. The largest known twin primes are

$3,756,801,695,685 \times 2^{666,669} \pm 1$ ,

numbers which have 200,700 decimal digits. Also, there are 808,675,888,577,436 twin prime pairs less than $10^{18}$ .

Most mathematicians also believe that there are infinitely many cousin primes, which differ by 4:

3 and 7 are cousin primes;

7 and 11 are cousin primes;

13 and 17 are cousin primes;

19 and 23 are cousin primes;

37 and 41 are cousin primes; etc.

Most mathematicians also believe that there are infinitely many sexy primes (no, I did not make that name up), which differ by 6:

5 and 11 are sexy primes;

7 and 13 are sexy primes;

11 and 17 are sexy primes;

13 and 19 are sexy primes;

17 and 23 are sexy primes; etc.

(Parenthetically, a “sexy” prime is probably the most unfortunate name in mathematics ever since Paul Dirac divided a bracket into a “bra” and a “ket,” thereby forever linking women’s underwear to quantum mechanics.)

While it is unknown if there are infinitely many twin primes, it was recently shown — in 2013 — that, for some integer $N$ that is less than 70 million, there are infinitely many pairs of primes that differ by $N$ . In 2014, this upper bound was reduced to 246. Furthermore, if a certain other conjecture is true, the bound has been reduced to 6. In other words, there are infinitely many twin primes or cousin primes or sexy primes… but, at this moment, we don’t know which one (or ones) is infinite.

In November 2014, Dr. Terence Tao of the UCLA Department of Mathematics was interviewed on the Colbert Report to discuss the twin prime conjecture… and he does a good job explaining to Stephen Colbert how we can know one of the three categories is infinite without knowing which category it is.

From the Colbert Report: http://thecolbertreport.cc.com/videos/6wtwlg/terence-tao

Proving theorems and special cases (Part 6): The Goldbach conjecture

In a recent class with my future secondary math teachers, we had a fascinating discussion concerning how a teacher should respond to the following question from a student:

Is it ever possible to prove a statement or theorem by proving a special case of the statement or theorem?

For the next few posts, I thought I’d share a few of the most famous unsolved problems in mathematics… and just how much computational work has been done to check for a counterexample.

1. The Goldbach conjecture (see here and here for more information) claims that every even integer greater than 4 can be written as the sum of two prime numbers. For example,

4 = 2 + 2,

6 = 3 + 3,

8 = 3 + 5,

10 = 3 + 7,

12 = 5 + 7,

14 = 3 + 11, etc.

This has been verified for all even numbers less than $4 \times 10^{18} = 4,000,000,000,000,000,000$ . A proof for all even numbers, however, has not been found yet.

Here are some results related to the Goldbach conjecture that are known:

1. Any integer greater than 4 is the sum of at most six primes.

2. Every sufficiently large even number can be written as the sum or two primes or the sum of a prime and the product of two primes.

3. Every sufficiently large even number can be written as the sum of two primes and at most 8 powers of 2.

4. Every sufficiently large odd number can be written as the sum of three primes.

Proving theorems and special cases (Part 5): Mathematical induction

Today’s post is a little bit off the main topic of this series of posts… but I wanted to give some pedagogical thoughts on yesterday’s post concerning the following proof by induction.

Theorem: If $n \ge 1$ is a positive integer, then $5^n - 1$ is a multiple of 4.

Proof. By induction on $n$ .

$n = 1$ : $5^1 - 1 = 4$ , which is clearly a multiple of 4.

$n$ : Assume that $5^n - 1$ is a multiple of 4, so that $5^n - 1 = 4q$ , where $q$ is an integer. We can also write this as $5^n = 4q + 1$ .

$n+1$ . We wish to show that $5^{n+1} - 1$ is equal to $4Q$ for some (different) integer $Q$ . To do this, notice that

$5^{n+1} - 1 = 5^1 5^n - 1$

$= 5 \times 5^n - 1$

$= 5 \times (4q + 1) - 1$ by the induction hypothesis

$= 20q + 5 - 1$

$= 20q + 4$

$= 4(5q + 1)$ .

So if we let $Q = 5q +1$ , then $5^{n+1} - 1 = 4Q$ , where $Q$ is an integer because $q$ is also an integer.

My primary observation is that even very strong math students tend to have a weak spot when it comes to simplifying exponential expressions (as opposed to polynomial expressions). For example, I find that even very good math students can struggle through the logic of this sequence of equalities:

$2^n + 2^n = 2 \times 2^n = 2^1 \times 2^n = 2^{n+1}$ .

The first step is using the main stumbling block. Students who are completely comfortable with simplifying $x + x$ as $2x$ can be perplexed by simplifying $2^n + 2^n$ as $2 \times 2^n$ . I attribute this to lack of practice with this kind of simplification in lower grade levels.

Here’s another algoebraic stumbling block that I’ve often seen: at the beginning of the $n+1$ case, some students will make the following mistake:

$5^{n+1} - 1 = 5^1 5^n - 1 = 5 (4q) = 4 (5q) = 4Q$ .

Because these students end with a multiple of 4, they fail to notice that the second equality is incorrect since

$5^1 5^n - 1 \ne 5^1 (5^n - 1)$ .

Again, I attribute this to lack of practice with simplifying exponential expressions in lower grade levels… as well as being a little bit over-excited upon seeing $5^n - 1$ and wishing to use the induction hypothesis as soon as possible.

Proving theorems and special cases (Part 4): Mathematical induction

In a recent class with my future secondary math teachers, we had a fascinating discussion concerning how a teacher should respond to the following question from a student:

Is it ever possible to prove a statement or theorem by proving a special case of the statement or theorem?

Usually, the answer is no… even checking many special cases of a conjecture does not mean that the conjecture is correct. In the previous two posts, we saw that a statement that’s true for the first 40 cases or even the first $10^{316}$ cases may not be true for all cases.

This is the reason that mathematical induction is important, as it provides a way to build from previous cases to prove that the next case is still correct, thus proving that all cases are correct.

Theorem: If $n \ge 1$ is a positive integer, then $5^n - 1$ is a multiple of 4.

Proof. By induction on $n$ .

$n = 1$ : $5^1 - 1 = 4$ , which is clearly a multiple of 4.

$n$ : Assume that $5^n - 1$ is a multiple of 4, so that $5^n - 1 = 4q$ , where $q$ is an integer. We can also write this as $5^n = 4q + 1$ .

$n+1$ . We wish to show that $5^{n+1} - 1$ is equal to $4Q$ for some (different) integer $Q$ . To do this, notice that

$5^{n+1} - 1 = 5^n 5^1 - 1$

$= 5 \times 5^n - 1$

$= 5 \times (4q + 1) - 1$ by the induction hypothesis

$= 20q + 5 - 1$

$= 20q + 4$

$= 4(5q + 1)$ .

So if we let $Q = 5q +1$ , then $5^{n+1} - 1 = 4Q$ , where $Q$ is an integer because $q$ is also an integer.

QED

In the above proof, we were able to build from the $n$ case to reach the $n +1$ case. In this sense, to answer the student’s question, it is possible to prove a theorem by first proving a special case of the theorem.

By contrast, when trying to “prove” that $n^2 - n + 41$ is prime for all integers $n$ , the proposition is true for $1 \le n \le 40$ , but it’s just a coincidence… there was no string of logic that connected these first 40 cases other than the coincidence that they all were correct.

Proving theorems and special cases (Part 3): Skewes’ number

In a recent class with my future secondary math teachers, we had a fascinating discussion concerning how a teacher should respond to the following question from a student:

Is it ever possible to prove a statement or theorem by proving a special case of the statement or theorem?

Usually, the answer is no… even checking many special cases of a conjecture does not mean that the conjecture is correct.

In the first two posts of this series, we showed conjectures could be true for the first 40 cases or even the first 900 million odd cases but fail on the next case. In today’s post, I’ll describe a conjecture that, for hundreds of years, was thought to be true for all integers $n$ and has since been shown to be true for all $n \le 10^{316}$ . However, despite being true for so many special cases, the conjecture is false.

Let’s absorb the above paragraph again. The conjecture “ $n^2 - n + 41$ is always prime” was true for the first 40 cases before failing. By contrast, the conjecture I’m about the describe is true for the first (approximately) 10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000 cases before failing.

The conjecture in question concerns the number of prime numbers $\pi(n)$ that are less than or equal to $n$ . For example:

There are four prime numbers less than 10 (namely 2, 3, 5, 7), and so $\pi(10) = 4$ .

There are eight prime numbers less than 10 (namely 2, 3, 5, 7, 11, 13, 17, 19), and so $\pi(20) = 8$ .

One of the classic problems in mathematics, often called the Prime Number Theorem, is estimating the value of $\pi(n)$ when $n$ is large. It turns out that one way of approximating $\pi(n)$ is through the logarithmic integral

$\hbox{Li}(n) = \displaystyle \int_2^n \frac{dx}{\ln x}$

Indeed, the Prime Number Theorem states that

$\pi(n) \sim \hbox{Li}(n)$ ,

$\displaystyle \lim_{n \to \infty} \frac{\pi(n)}{\hbox{Li}(n)} = 1$ .

This asymptotic relationship was proven by the eminent mathematician Karl Friedrich Gauss.

With that as prelude, here’s the false conjecture. For decades, luminaries of mathematics, including Gauss and Bernhard Riemann, conjectured that

$\pi(n) < \hbox{Li}(n)$ for all integers $n$

based on the available numerical evidence at the time. However, this conjecture was proven false in the 20th century by the British mathematician John Littlewood. No only did Littlewood show that there is a value of $n$ so that $\pi(n) > \hbox{Li}(n)$ , but he also showed that the graphs of $\pi(n)$ and $\hbox{Li}(n)$ cross over each other infinitely many times!

Littlewood proved his theorem over 100 years ago in 1914. Today, even with modern computing power, we still do not precisely know the first value of $n$ for which $\pi(n) > \hbox{Li}(n)$ . This number is called Skewes’ number, in honor of the mathematician who first found (in 1955) an upper bound on this first crossing point. The bound that he found was absolutely enormous: he showed that $\pi(n) > \hbox{Li}(n)$ for some $n$ less than

$\displaystyle 10^{\displaystyle 10^{10^{34}}}$

More recent work has established that the first crossover likely occurs in the vicinity of $n \approx 1.397 \times 10^{316}$ .

Whoever first evaluates Skewes’ number exactly will surely have a nice feather in his/her cap for completing a task that mystified both Gauss and Riemann.

References:

http://mathworld.wolfram.com/PrimeNumberTheorem.html

http://mathworld.wolfram.com/SkewesNumber.html

http://mathworld.wolfram.com/PrimeCountingFunction.html

http://mathworld.wolfram.com/LogarithmicIntegral.html

Proving theorems and special cases (Part 2): The Pólya conjecture

In a recent class with my future secondary math teachers, we had a fascinating discussion concerning how a teacher should respond to the following question from a student:

Is it ever possible to prove a statement or theorem by proving a special case of the statement or theorem?

Usually, the answer is no… even checking many special cases of a conjecture does not mean that the conjecture is correct.

In yesterday’s post, we showed that the conjecture “ $n^2 - n + 41$ is a prime number for all positive integers $n$ ” is true for $1 \le n \le 40$ but fails for $n = 41$ . In today’s post, I’ll describe a conjecture that is true for plenty more special cases before becoming false.

The Pólya conjecture (see here and here for more information) stated that 50% or more of the natural numbers less than or equal to any given number have an odd number of prime factors (counting multiplicity). For example:

$2$ has one prime factor: odd

$3$ has one prime factor: odd

$4 = 2 \times 2$ has two prime factors: even

$5$ has one prime factor: odd

$6 = 2 \times 3$ has two prime factors: even

$7$ has one prime factor: odd

$8 = 2 \times 2 \times 2$ has three prime factors: odd

$9 = 3 \times 3$ has two prime factors: even

$10 = 2 \times 5$ has two prime factors: even

So of the numbers less than or equal to 10, five have an odd number of prime factors, and only four have an even number of prime factors.

The Pólya conjecture was first proven false by producing a counterexample in the vicinity of $1.845 \times 10^{361}$ . It turns out that the smallest counterexample is 906,150,257. In other words, the Pólya conjecture is true for the first 906,150,256 cases but fails on the next case.

Proving theorems and special cases (Part 1): Is n^2-n+41 always prime?

In a recent class with my future secondary math teachers, we had a fascinating discussion concerning how a teacher should respond to the following question from a student:

Is it ever possible to prove a statement or theorem by proving a special case of the statement or theorem?

Usually, the answer is no… even checking many special cases of a conjecture does not mean that the conjecture is correct.

The following example probably appears in every textbook that I’ve seen that handles mathematical induction to convince students that checking even many special cases of a conjecture is not sufficient for proving the conjecture.

Conjecture: If $n \ge 1$ is a positive integer, then $n^2 - n + 41$ is a prime number.

Is this true? Well, let’s start checking:

If $n = 1$ , then $n^2 - n + 41 = 1^2 - 1 + 41 = 41$ , which is a prime number.

If $n = 2$ , then $n^2 - n + 41 = 2^2 - 2 + 41 = 43$ , which is a prime number.

If $n = 3$ , then $n^2 - n + 41 = 3^2 - 3 + 41 = 47$ , which is a prime number.

If $n = 4$ , then $n^2 - n + 41 = 4^2 - 4 + 41 = 53$ , which is a prime number.

If $n = 5$ , then $n^2 - n + 41 = 5^2 - 5 + 41 = 61$ , which is a prime number.

If $n = 6$ , then $n^2 - n + 41 = 6^2 - 6 + 41 = 71$ , which is a prime number.

If $n = 7$ , then $n^2 - n + 41 = 7^2 - 7 + 41 = 83$ , which is a prime number.

If $n = 8$ , then $n^2 - n + 41 = 8^2 - 8 + 41 = 97$ , which is a prime number.

If $n = 9$ , then $n^2 - n + 41 = 9^2 - 9 + 41 = 113$ , which is a prime number.

If $n = 10$ , then $n^2 - n + 41 = 10^2 - 10 + 41 = 131$ , which is a prime number.

If $n = 11$ , then $n^2 - n + 41 = 11^2 - 11 + 41 = 151$ , which is a prime number.

If $n = 12$ , then $n^2 - n + 41 = 12^2 - 12 + 41 = 173$ , which is a prime number.

If $n = 13$ , then $n^2 - n + 41 = 13^2 - 13 + 41 = 197$ , which is a prime number.

If $n = 14$ , then $n^2 - n + 41 = 14^2 - 14 + 41 = 223$ , which is a prime number.

If $n = 15$ , then $n^2 - n + 41 = 15^2 - 15 + 41 = 251$ , which is a prime number.

If $n = 16$ , then $n^2 - n + 41 = 16^2 - 16 + 41 = 281$ , which is a prime number.

If $n = 17$ , then $n^2 - n + 41 = 17^2 - 17 + 41 = 313$ , which is a prime number.

If $n = 18$ , then $n^2 - n + 41 = 18^2 - 18 + 41 = 347$ , which is a prime number.

If $n = 19$ , then $n^2 - n + 41 = 19^2 - 19 + 41 = 383$ , which is a prime number.

If $n = 20$ , then $n^2 - n + 41 = 20^2 - 20 + 41 = 421$ , which is a prime number.

If $n = 21$ , then $n^2 - n + 41 = 21^2 - 21 + 41 = 461$ , which is a prime number.

If $n = 22$ , then $n^2 - n + 41 = 22^2 - 22 + 41 = 503$ , which is a prime number.

If $n = 23$ , then $n^2 - n + 41 = 23^2 - 23 + 41 = 547$ , which is a prime number.

If $n = 24$ , then $n^2 - n + 41 = 24^2 - 24 + 41 = 593$ , which is a prime number.

If $n = 25$ , then $n^2 - n + 41 = 25^2 - 25 + 41 = 641$ , which is a prime number.

If $n = 26$ , then $n^2 - n + 41 = 26^2 - 26 + 41 = 691$ , which is a prime number.

If $n = 27$ , then $n^2 - n + 41 = 27^2 - 27 + 41 = 743$ , which is a prime number.

If $n = 28$ , then $n^2 - n + 41 = 28^2 - 28 + 41 = 797$ , which is a prime number.

If $n = 29$ , then $n^2 - n + 41 = 29^2 - 29 + 41 = 853$ , which is a prime number.

If $n = 30$ , then $n^2 - n + 41 = 30^2 - 30 + 41 = 911$ , which is a prime number.

If $n = 31$ , then $n^2 - n + 41 = 31^2 - 31 + 41 = 971$ , which is a prime number.

If $n = 32$ , then $n^2 - n + 41 = 32^2 - 32 + 41 = 1033$ , which is a prime number.

If $n = 33$ , then $n^2 - n + 41 = 33^2 - 33 + 41 = 1097$ , which is a prime number.

If $n = 34$ , then $n^2 - n + 41 = 34^2 - 34 + 41 = 1163$ , which is a prime number.

If $n = 35$ , then $n^2 - n + 41 = 35^2 - 35 + 41 = 1231$ , which is a prime number.

If $n = 36$ , then $n^2 - n + 41 = 36^2 - 36 + 41 = 1301$ , which is a prime number.

If $n = 37$ , then $n^2 - n + 41 = 37^2 - 37 + 41 = 1373$ , which is a prime number.

If $n = 38$ , then $n^2 - n + 41 = 38^2 - 38 + 41 = 1447$ , which is a prime number.

If $n = 39$ , then $n^2 - n + 41 = 39^2 - 39 + 41 = 1523$ , which is a prime number.

If $n = 40$ , then $n^2 - n + 41 = 40^2 - 40 + 41 = 1601$ , which is a prime number.

Okay, a show of hands… did anyone actually carefully read and check the above 40 lines? I didn’t think so. The point is that the proposition works for $n = 1, 2, 3, \dots, 40$ . By about $n = 4$ , or so, a student (who didn’t already know the answer) actually did the above work would begin thinking, “Wow, this probably is correct for any value of $n$ .”

Of course, the catch happens at $n = 41$ :

If latex n = 41, then $n^2 - n + 41 = 41^2 - 41 + 41 = 41^2 = 41 \times 41$ ,

which is not a prime number.

All this to say, seeing a trend for the first few special cases… or the first few dozen special cases… does not necessarily mean that the trend will continue.

To prove that two things are equal, show that the difference is zero

The title of this post, “To prove that two things are equal, show that the difference is zero,” is surprisingly handy in the secondary mathematics curriculum. For example, it is the basis for the proof of the Mean Value Theorem, one of the most important theorems in calculus that serves as the basis for curve sketching and the uniqueness of antiderivatives (up to a constant).

And I have a great story that goes along with this principle, from 30 years ago.

I forget the exact question out of Apostol’s calculus, but there was some equation that I had to prove on my weekly homework assignment that, for the life of me, I just couldn’t get. And for no good reason, I had a flash of insight: subtract the left- and right-hand sides. While it was very difficult to turn the left side into the right side, it turned out that, for this particular problem, was very easy to show that the difference was zero. (Again, I wish I could remember exactly which question this was so that I could show this technique and this particular example to my own students.)

So I finished my homework, and I went outside to a local basketball court and worked on my jump shot.

Later that week, I went to class, and there was a great buzz in the air. It took ten seconds to realize that everyone was up in arms about how to do this particular problem. Despite the intervening 30 years, I remember the scene as clear as a bell. I can still hear one of my classmates ask me, “Quintanilla, did you get that one?”

I said with great pride, “Yeah, I got it.” And I showed them my work.

And, either before then or since then, I’ve never heard the intensity of the cussing that followed.

Truth be told, probably the only reason that I remember this story from my adolescence is that I usually was the one who had to ask for help on the hardest homework problems in that Honors Calculus class. This may have been the one time in that entire two-year calculus sequence that I actually figured out a homework problem that had stumped everybody else.