Memorial Day: Conway and Collatz

Do you know what the Collatz Conjecture is?

John Horton Conway died recently, as I briefly reported in my post Weekend Update. He worked on many aspects of mathematics: "number theory, game theory, coding theory, group theory, knot theory, topology, probability theory, algebra, analysis, combinatorics and more" as the New York Times put it. He also worked on the Collatz Conjecture.

Since it is coming up to a holiday I thought I'd write about the Collatz Conjecture. Cadence is off on both this Friday and Memorial Day itself, so this is the day before a break, the traditional time for me to go totally off-topic. Breakfast Bytes will be dark until Tuesday. Today's regularly scheduled Telecom Thursday post will be next Thursday.

But before I get to the Collatz Conjecture, how about a couple of other interesting areas of math that are similar. By "similar" I mean that they are trivially easy to explain and understand, but either remain unproven or required a huge amount of very deep math to prove.

Fermat's Last Theorem

Fermat's Last Theorem (often called Fermat's Last Conjecture until recently) was described by Pierre de Fermat in 1637. He jotted a note in the margin of a copy of the ancient Greek text Arithmetica. Tantalizingly, he also said that he had discovered a marvelous proof but that the margin was too small to contain it. Since it was not proved until 1994, it is generally assumed he had no valid proof. Fermat's Last Theorem says:

No three positive integers a, b, and c satisfy the equation aⁿ + bⁿ = cⁿ for any integer value of n greater than 2.

The "n>2" condition is important, since the case of n=1 is trivial, and for n=2 it has been known since antiquity (hello, Pythagoras!) that there are infinitely many solutions. For example: 3, 4, 5.

The theorem was eventually proved in 1994 by Andrew Wiles at Princeton. The proof is 129 pages long. In a coincidence, John Conway was a colleague. He was hired away from Cambridge and relocated to the US to take up a position at Princeton.

Here's a short video of Simon Singh talking, not about his book Fermat's Last Theorem, but about it showing up on the Simpsons (8 minutes):

The Four-Color Theorem

The Four-Colour Theorem (or Four-Color Problem as it used to be called casually) says that any map can be colored with just four colors so that no two adjacent regions have the same color. In this context, "adjacent" means touching along an edge, not just corner-to-corner. It was proved in 1976 by Kenneth Appel and Wolfgang Haken. It was the first theorem in mathematics to require the use of a computer.

The formal mathematical exposition of the problem is usually expressed in terms of graph theory: every planar graph is four-colorable. But the basic theorem can be understood by any child.

The basic idea of the proof is by counterexample: if the theorem is false, then there must be a smallest map that requires five colors. Appel and Haken proved that any such graph would need to have one of certain sub-patterns within it that required five colors. Their list contained 1834 of them. Then, using a computer, they showed that all 1834 patterns could be four-colored and so the conjecture was false. The fact that a computer was required was controversial at the time. Now, doing math with computers is routine.

The Collatz Conjecture

Finally, the Collatz Conjecture. Unlike the two theorems above, it is unproven. Like with the Four-Color Theorem, there is a mathematical way of expressing it. But it is easy to explain.

Take any number N
If N is even, then the next number is N/2
If N is odd, then the next number is 3N+1
Repeat
The Collatz Conjecture is that you will eventually end up at 1.

I first came across this when I was an undergraduate studying math at Cambridge. It would be perfect for this blog post if I had learned it from Conway, which is possible, but I don't think that's true. However, he had been studying it just before I got there. In 1972, he published a paper, Unpredictable Iterations (seemingly not online), that proved that a natural generalization of the conjecture is algorithmically undecidable.

This conjecture is quite recent compared to the other ones, dating back only to 1937 when it was introduced by Luthar Collatz. Paul Erdős, perhaps the most famous mathematician of the 20th Century, said of the problem:

Mathematics may not be ready for such problems.

If you try it, you will find that usually it doesn't take long to get to 1. There are some well-known numbers that seem to explode before they submit: 27 takes 111 steps, rising as high as 9232. But even going up to very large numbers, the maximum number of steps is always less than about 2000. For small numbers, you can graph out the various paths, as in the image at the top of this post. Or in the XKCD at the start of this section.

The conjecture is considered to be true by most mathematicians. But math is famous for having some theorems where it's clearly true until a counterexample is found but is extraordinarily large. For example, the Pólya Conjecture has a counterexample estimated to be around 1.8 × 10³⁶¹.This is an extraordinarily large number — the number of particles in the universe is estimated at 10⁸⁰. So it is certainly possible for the Collatz Conjecture to be false with an enormous counterexample.

John Conway Again

I pulled a quote above from the New York Times obituary of John Conway. Later in the obituary, it says:

At the University of Cambridge Dr. Conway rose to become a professor in mathematics as well as a supernumerary fellow at Gonville and Caius College, his alma mater there.

There's actually more of a story there than meets the eye. Conway did indeed study math at Caius (pronounced "keys" by the way). After he got his doctorate in 1964, he became a Fellow (and lecturer in math) at Sidney Sussex College, my alma mater. However, in 1970, he left Sidney in protest over some skullduggery in the election of the new college Master where his preferred candidate was "persuaded" to withdraw before the actual election. Soon after, he got a fellowship back at Caius. It was "supernumerary" because a gentlemen's agreement meant that no college could hire a lecturer from another college, so he had a fellowship but no teaching duties. Although he was my first-year lecturer in linear algebra, he was not one of my tutors since he had left Sidney by the time I was an undergraduate. In 1986, he left Cambridge and was appointed to the John von Neumann Chair of Mathematics at Princeton. Where we came in with Fermat's Last Theorem.

And here's a piece of Sidney trivia. The head of Oliver Cromwell is buried somewhere in the college chapel, but it is a secret exactly where. Sidney was his alma mater, too. To the right is the plaque "nearby". Conway used to tell a story about being present at some secret late-night ceremony where all the Fellows present were sworn to secrecy — but as you can see from the plaque, the head was re-interred in 1960, four years before Conway became a Fellow of the college. As he admitted to a journalist long after he'd decamped to Princeton:

Yeeesss. That is a great story, isn’t it? And I often tell that story, with myself playing a supporting role. As if I had actually been there.

Memorial Day

Breakfast Bytes is off on Friday for a special company holiday and on Monday for Memorial Day (although all days seem the same these days). Back on Tuesday.

Sign up for Sunday Brunch, the weekly Breakfast Bytes email.