Proving theorems and special cases (Part 9): The Riemann hypothesis

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}$ 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.

4. The Riemann hypothesis (see here, here, and here for more information) is perhaps the outstanding unsolved problem in pure mathematics, and a prize of $1 million has been offered for its proof.

The Riemann zeta function is defined by

$\zeta(s) = \displaystyle \sum_{n=1}^\infty \frac{1}{n^s}$

for complex numbers $s$ with real part greater than 1. For example,

$\zeta(2) = \displaystyle \frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \dots = \displaystyle \frac{\pi^2}{6}$

and

$\zeta(4) = \displaystyle \frac{1}{1^4} + \frac{1}{2^4} + \frac{1}{3^4} + \dots = \displaystyle \frac{\pi^4}{90}$

The definition of the Riemann zeta function can be extended to all complex numbers (except a pole at $s = 1$ ) by the integral

$\zeta(s) = \displaystyle \frac{1}{\Gamma(s)} \int_0^\infty \frac{x^{s-1}}{e^s - 1} dx$

and also analytic continuation.

The Riemann hypothesis conjectures to all solutions of the equation $\zeta(s) = 0$ other than negative even integers occur on the line $s = \frac{1}{2} + i t$ . At present, it is known that the first 10 trillion solutions are on this line, so that every solution with $t < 2.4 \times 10^{12}$ is on this line. Of course, that’s not a proof that all solutions are on this line.

A full description of known results concerning the Riemann hypothesis requires much more than a single post. I’ll refer the interested reader to the links above from MathWorld, Wikipedia, and Claymath and the references embedded in those links. An excellent book for the layman concerning the Riemann hypothesis is Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics, by John Derbyshire.

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.

https://www.youtube.com/watch?v=bUwbO73q0iA

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 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.

Talking about math to Congress

From MAA Focus:

If you think it’s hard to distill research results into a 15-minute conference presentation, try this: Choose a subject like matrix factorizations or recent progress on the twin prime conjecture. Figure out how to make a nonexpert audience—members of Congress, say—if not fully understand the chosen topic, at least appreciate its significance. Do this in a minute. The clock is ticking.

Jerry McNerney of California’s ninth congressional district has risen to such a challenge more than 10 times in the U.S. House of Representatives, where he has served since 2007. The only current member of the House or Senate to hold a doctorate in mathematics (University of New Mexico, 1981), McNerney has read into the congressional record one-minute expositions of such abstruse subjects as vector bundles, synesthesia, and the Large Synoptic Survey Telescope…

Boiling down complex material into a minute of talking is tricky, McNerney concedes, but he has been pleased with the results. As a member of the Public Face of Mathematics panel at the 2014 Joint Mathematics Meetings, McNerney told listeners that being coaxed into thinking about math has a positive effect on his congressional fellows.

“Instead of all the usual bickering that you get on the House floor, everyone smiles,” he reported. “They say, ‘This is really fun.’”

Source: http://mcnerney.house.gov/media-center/in-the-news/math-by-the-minute-on-capitol-hill

2014 MacArthur “Genius” grant winner and the twin prime conjecture

From http://www.macfound.org/fellows/927/:

Prime numbers have inspired great intrigue over the last centuries, and one of the most basic unanswered questions has been the spacing between two consecutive prime numbers, or the twin prime conjecture, which states that there are infinitely many pairs of primes that differ by two. Despite many efforts at proving this conjecture, mathematicians were not able to rule out the possibility that the gaps between primes continue to expand, eventually exceeding any particular bound. Zhang’s work shows that there are infinitely many consecutive primes, or pairs of primes, closer than 70 million. In other words, as you go to larger and larger numbers, the primes will not become further and further apart—you will keep finding prime pairs that differ by less than 70 million.

His work has generated significant collaborations across the community to expand on his effort, and within months of his discovery that number was reduced from 70 million to less than 5,000.

Engaging students: Prime Factorizations

In my capstone class for future secondary math teachers, I ask my students to come up with ideas for engaging their students with different topics in the secondary mathematics curriculum. In other words, the point of the assignment was not to devise a full-blown lesson plan on this topic. Instead, I asked my students to think about three different ways of getting their students interested in the topic in the first place.

I plan to share some of the best of these ideas on this blog (after asking my students’ permission, of course).

This student submission again comes from my former student Michael Dixon. His topic, from Pre-Algebra: prime factorizations.

A1. What word problems can your students do now?

One word problem that is easily relatable would be something involving food!

For instance: “Don loves peanut butter and jelly sandwiches. One day he noticed a jumbo jar of peanut butter has 72 servings and a jar of jam only has 40 servings. If he opened the [first] jars on the same day and used exactly one serving each day, how many days until he emptied a peanut butter jar and a jam jar on the same day? Use prime factorization to solve.”

Obviously, this involves finding the least common multiple of 72 and 40. I would introduce this problem at the beginning of class, after my students have already been introduced to the idea of prime factorizations. I do not expect that my students would know how to calculate the lcm using prime factorizations, rather I would want to strike up a class discussion asking students to explore what they know about factorizations and see if they can find any patterns that would lead to the solution. I want to lead them to the idea that prime factorizations make finding the lcm far easier than listing the multiples of each number, especially when large numbers are involved.

B1. Future Curriculum

As mentioned in the previous paragraph, students can learn to use prime factorizations to calculate the greatest common factor or the least common multiple of numbers easily. To take this quite a bit further, we can introduce students to the idea of using factorizations, gcd, and lcm in formal abstract proofs. We would ask them to actually prove anything, just think about the ideas. Ask students how they know that the math that they use everyday actually works. Why does every number have a unique factorization? Why can I calculate the gcd and lcm of any two numbers, and know that that answer is the only answer? Then explain that later on, in higher level math classes, we actually flawlessly prove why our number system works, and how and why primes are important, such as in the Euler Phi function. Without prime factorizations, we would be unable to prove quite a lot of the math that we take for granted.

E1. How can technology be used to engage students?

After your students have been working with prime factorizations for a while and they are getting more proficient, what’s an obvious escalation? Make the numbers larger! Ask your students to factor numbers like 198 and 456. See how long it takes them to work through these. Then, ask them how long it would take to factor numbers like 2756 or even 12857. How could they do these? Is it even reasonable to try? What about 51,234,587 (this is actually prime)?

Here we can introduce using a computer, and using a computer to do the calculations for us. Just a simple website is adequate to show them just how useful computers are when doing large calculations. A website such as Math is Fun is an excellent tool to demonstrate the magnitude of some prime numbers and composite numbers, and show that even as numbers get very, very large, they are not divisible by any numbers other than themselves and one.

References

www.mathsisfun.com/numbers/prime-factorization-tool.html

http://tulyn.com/wordproblems/prime_factorization-word_problem-7928.html