My Favorite One-Liners: Part 35

In this series, I’m compiling some of the quips and one-liners that I’ll use with my students to hopefully make my lessons more memorable for them.

Every once in a while, I’ll discuss something in class which is at least tangentially related to an unsolved problems in mathematics. For example, when discussing infinite series, I’ll ask my students to debate whether or not this series converges:

1 + \frac{1}{10} + \frac{1}{100} + \frac{1}{1000} + \dots

Of course, this one converges since it’s an infinite geometric series. Then we’ll move on to an infinite series that is not geometric:

1 + \frac{1}{4} + \frac{1}{9} + \frac{1}{16} + \dots,

where the denominators are all perfect squares. I’ll have my students guess about whether or not this one converges. It turns out that it does, and the answer is exactly what my students should expect the answer to be, \pi^2/6.

Then I tell my students, that was a joke (usually to relieved laughter).

Next, I’ll put up the series

1 + \frac{1}{8} + \frac{1}{27} + \frac{1}{64} + \dots,

where the denominators are all perfect cubes. I’ll have my students guess about whether or not this one converges. Usually someone will see that this one has to converge since the previous one converged and the terms of this one are pairwise smaller than the previous series — an intuitive use of the Dominated Convergence Test. Then, I’ll ask, what does this converge to?

The answer is, nobody knows. It can be calculated to very high precision with modern computers, of course, but it’s unknown whether there’s a simple expression for this sum.

So, concluding the story whenever I present an unsolved problem, I’ll tell my students,

If you figure out the answer, call me, and call me collect.

What I Learned by Reading “Gamma: Exploring Euler’s Constant” by Julian Havil: Index

I’m doing something that I should have done a long time ago: collecting a series of posts into one single post.

When I was researching for my series of posts on conditional convergence, especially examples related to the constant \gamma, the reference Gamma: Exploring Euler’s Constant by Julian Havil kept popping up. Finally, I decided to splurge for the book, expecting a decent popular account of this number. After all, I’m a professional mathematician, and I took a graduate level class in analytic number theory. In short, I don’t expect to learn a whole lot when reading a popular science book other than perhaps some new pedagogical insights.

Boy, was I wrong. As I turned every page, it seemed I hit a new factoid that I had not known before.

In this series, I’d like to compile some of my favorites along with the page numbers in the book — while giving the book a very high recommendation.

Part 1: The smallest value of n so that 1 + \frac{1}{2} + \dots + \frac{1}{n} > 100 (page 23).

Part 2: Except for a couple select values of m<n, the sum \frac{1}{m} + \frac{1}{m+1} + \dots + \frac{1}{n} is never an integer (pages 24-25).

Part 3: The sum of the reciprocals of the twin primes converges (page 30).

Part 4: Euler somehow calculated \zeta(26) without a calculator (page 41).

Part 5: The integral called the Sophomore’s Dream (page 44).

Part 6: St. Augustine’s thoughts on mathematicians — in context, astrologers (page 65).

Part 7: The probability that two randomly selected integers have no common factors is 6/\pi^2 (page 68).

Part 8: The series for quickly computing \gamma to high precision (page 89).

Part 9: An observation about the formulas for 1^k + 2^k + \dots + n^k (page 81).

Part 10: A lower bound for the gap between successive primes (page 115).

Part 11: Two generalizations of \gamma (page 117).

Part 12: Relating the harmonic series to meteorological records (page 125).

Part 13: The crossing-the-desert problem (page 127).

Part 14: The worm-on-a-rope problem (page 133).

Part 15: An amazingly nasty formula for the nth prime number (page 168).

Part 16: A heuristic argument for the form of the prime number theorem (page 172).

Part 17: Oops.

Part 18: The Riemann Hypothesis can be stated in a form that can be understood by high school students (page 207).

 

 

What I Learned from Reading “Gamma: Exploring Euler’s Constant” by Julian Havil: Part 18

The Riemann Hypothesis (see here, here, and here) is perhaps the most famous (and also most important) unsolved problems in mathematics. Gamma (page 207) provides a way of writing down this conjecture in a form that only uses notation that is commonly taught in high school:

If \displaystyle \sum_{r=1}^\infty \frac{(-1)^r}{r^a} \cos(b \ln r) = 0 and \displaystyle \sum_{r=1}^\infty \frac{(-1)^r}{r^a} \sin(b \ln r) = 0 for some pair of real numbers a and b, then a = \frac{1}{2}.

As noted in the book, “It seems extraordinary that the most famous unsolved problem in the whole of mathematics can be phrased so that it involves the simplest of mathematical ideas: summation, trigonometry, logarithms, and [square roots].”

green line

When I researching for my series of posts on conditional convergence, especially examples related to the constant \gamma, the reference Gamma: Exploring Euler’s Constant by Julian Havil kept popping up. Finally, I decided to splurge for the book, expecting a decent popular account of this number. After all, I’m a professional mathematician, and I took a graduate level class in analytic number theory. In short, I don’t expect to learn a whole lot when reading a popular science book other than perhaps some new pedagogical insights.

Boy, was I wrong. As I turned every page, it seemed I hit a new factoid that I had not known before.

In this series, I’d like to compile some of my favorites — while giving the book a very high recommendation.

Win $1,000,000 by Playing Minesweeper!

Yes, you read that headline correctly: it is possible for a mathematician to win $1,000,000 by playing Minesweeper. Here’s how:

First, the source of the $1,000,000. In 2000, the Clay Mathematics Institute created a list of important unsolved problems in mathematics (see also Wikipedia), offering each one a prize of $1,000,000 for a solution. Specifically, according to the rules,

[A] proposed solution must be published in a refereed mathematics publication of worldwide repute… and it must also have general acceptance in the mathematics community two years after.

Of the eight problems on the list, one (the Poincare conjecture) has been solved so far. Incredibly, the mathematician who produced the proof turned down the $1,000,000. He was also awarded the Fields Medal, considered the Nobel Prize of mathematics, but he refused that as well.

The Millennium Problems parallel the famous 23 Hilbert problems posed by eminent mathematician David Hilbert in 1900. The Hilbert problems were unsolved at the time and were posed as a challenge to the mathematicians of the 20th century. These problems certainly generated a lot of buzz in the mathematical community, and most have been solved since 1900. (Sadly, none of the solvers won $1,000,000 for their work!)

What does this have to do with Minesweeper?

One of the problems is the famed P vs. NP problem. From Clay Mathematics:

Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker’s list also appears on the list from the Dean’s office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

In 2000, Richard Kaye (University of Birmingham, UK) made connected Minesweeper to the P vs. NP problem. Famed mathematical journalist Ian Stewart did a very nice job of describing the connection between the two, so I’ll simply refer to his post for a detailed description. Dr. Kaye’s website also gives a lot of information about the connection.

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 8): The Collatz 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.

3. The Collatz conjecture (see here and here for more information) is an easily stated unsolved problem that can be understood by most fourth and fifth graders. Restated from a previous post:

Here’s the statement of the problem.

  • Start with any positive integer.
  • If the integer is even, divide it by 2. If it’s odd, multiply it by 3 and then add 1.
  • Repeat until (and if) you reach 1.

Here’s the question: Does this sequence eventually reach 1 no matter the starting value? Or is there a number out there that you could use as a starting value that has a sequence that never reaches 1?

For every integer less than 5 \times 2^{60} = 5,764,607,523,034,234,880, this sequence returns to 1. Of course, this is not a proof that the conjecture will hold for every integer.

 

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?

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.

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.

green line

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.

 

 

 

 

Non-geometric infinite series (Part 12)

I conclude this series of posts with thoughts about infinite series which use reciprocals of positive integers. I offer this post for the enrichment of talented Precalculus students who have exhibited mastery of geometric series.

Geometric. As we’ve discussed at length, the series

1 + \displaystyle \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \dots

converges and is in fact equal to 2.

Harmonic. Including the reciprocals of all positive integers is called a harmonic series:

1 + \displaystyle \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \dots

As shown in the link to the MathWorld website, this series actually diverges, even though the terms get smaller and smaller.

So we’ve made an observation: if too many reciprocals are included, the series diverges. But if we take enough of them away, then we can still end up with a series that is infinite but converges.

Squares. Let’s now consider the reciprocals of perfect squares:

1 + \displaystyle \frac{1}{4} + \frac{1}{9} + \frac{1}{16} + \frac{1}{25} + \dots

Clearly, we’ve taken away a lot of the terms of the harmonic series? Have we taken enough away so that the series converges? It turns out that the answer is yes. And the answer is precisely what you’d think it should be (not): \pi^2/6. This is just another way that the circumference of a circle has an odd way of appearing in the most unexpected of places.

The proof that this series equals \pi^2/6 requires the clever use of Parseval’s theorem from Fourier analysis.

Fourth Powers. Let’s now turn to the reciprocals of fourth powers:

1 + \displaystyle \frac{1}{16} + \frac{1}{81} + \frac{1}{256} + \frac{1}{625} + \dots

By the Direct Comparison Test and the series for reciprocals of squares, this series converges. Using Parseval’s theorem, it can be shown that the answer is \pi^4/90.

Cubes. Now let’s investigate the reciprocals of cubes:

1 + \displaystyle \frac{1}{8} + \frac{1}{27} + \frac{1}{64} + \frac{1}{125} + \dots

Again by the Direct Comparison Test and the series for reciprocals for squares, this series must converge. This sum is called Apéry’s constant.  However, and amazingly, no one knows what the answer is. Of course, a computer can be programmed to evaluate this series to as many decimal places as desired. According to Wikipedia, this sum was evaluated to over 100 billion decimal places in 2010. However, to the best of my knowledge, no one has figured out if there’s a simple way of writing the answer, like \pi^2/6 or \pi^4/90.

So if you figure out a simple way to evaluate Apéry’s constant, feel free to call me collect.

The previous four series are example of Riemann’s zeta function, which is of central importance in number theory and is the focus of the celebrated Riemann Hypothesis, for which a solution is worth a cool $1 million.

Primes. Now let’s consider the reciprocals of primes:

\displaystyle \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \frac{1}{11} + \dots

As noted above, the harmonic series diverges, but if we remove enough terms from the harmonic series, then it’s possible to make an infinite series that converges. So the central question is, did we remove enough fractions (by taking away all of the composite denominators) so that the series converges?

Surprisingly, the answer is no: the sum of the reciprocals of the primes actually diverges. The proof actually requires a graduate-level class in analytic number theory.

green line

By no means would I expect high school students to master all of the above facts. As noted above, the subject of this post is mostly for the enrichment of high school students who have mastered infinite geometric series.

That said, students who know the following facts from Precalculus will be well-served when they reach calculus and other university-level mathematics courses.

  • They should either know the formula for an infinite geometric series or else be able to quickly derive it.
  • They should know that not every infinite geometric series is geometric.
  • They should know that not every infinite series converges.
  • They should be familiar with the meaning of the terms converge and diverge.

Unsolved problems: the Collatz conjecture

Students at all levels — elementary, middle, secondary, and college — tend to think that either (1) all the problems in mathematics have already been solved, or else (2) some unsolved problems remain but only an expert can understand even the statement of the problem.

There are plenty of famous unsolved problems in mathematics. And the Collatz conjecture is an easily stated unsolved problem that can be understood by most fourth and fifth graders.

Here’s the statement of the problem.

  • Start with any positive integer.
  • If the integer is even, divide it by 2. If it’s odd, multiply it by 3 and then add 1.
  • Repeat until (and if) you reach 1.

That’s it. From Wikipedia:

For instance, starting with 6, one gets the sequence 6, 3, 10, 5, 16, 8, 4, 2, 1.

Starting with 11, for example, takes longer to reach 1: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

The sequence for 27 takes 111 steps, climbing to 9232 before descending to 1: 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

The longest progression for any initial starting number less than 100 million is 63,728,127, which has 949 steps. For starting numbers less than 1 billion it is 670,617,279, with 986 steps, and for numbers less than 10 billion it is 9,780,657,630, with 1132 steps.

Here’s the question: Does this sequence eventually reach 1 no matter the starting value? Or is there a number out there that you could use as a starting value that has a sequence that never reaches 1?

Like I said, this is an easily stated problem that most fourth graders could understand. And no one knows the answer. Every number that’s been tried by computer has produced a sequence that eventually reaches 1. But that doesn’t mean that there isn’t a bigger number out there that doesn’t reach 1.

I’ll refer to the above Wikipedia page (and references therein) for further reading about the Collatz conjecture. Pedagogically, I suggest that casually mentioning this unsolved problem in class might inspire students to play with mathematics on their own, rather than think that all of mathematics has already been solved by somebody.

xkcdcollatz_conjecture

Source: http://www.xkcd.com/710/