Tracking the hailstones

One of the most shocking results from mathematics -- or even scholarship as a whole -- is Kurt Gödel's Incompleteness Theorem.

Like (I suspect) many of us, I first ran into this startling idea in Douglas Hofstadter's wonderful book Gödel, Escher, Bach: An Eternal Golden Braid, which I read when I was an undergraduate at the University of Louisiana.  I've since reread the whole thing twice, but I'm afraid the parts about formal logic and Gödel's proof are still a real challenge to my understanding.  The gist of it is that Gödel responded to a call by German mathematician David Hilbert to come up with a finite, consistent set of axioms from which all other true statements in mathematics could be derived (and, significantly, which excluded all false or paradoxical ones).  Gödel picked up the gauntlet, but not in the way Hilbert expected (or wanted).

He showed that what Hilbert was asking for was fundamentally impossible.

Put succinctly, Gödel proved that if you come up with an axiomatic system that can generate all true statements of mathematics, it will also generate some untrue ones; if you come up with a system that generates only true statements, there will always be true statements that cannot be proven from within it.  In other words, if a mathematical system is complete, it's inconsistent; if it is consistent, it's incomplete.

The result is kind of staggering, and the more you think about it, the weirder it gets.  Math is supposed to be cut and dried, black-and-white, where things are either provable (and therefore true) or they're simply wrong.  What Gödel showed was that this is not the case -- and worse, there's no way to fix it.  If you simply take any true (but unprovable) mathematical statements you find, and add them to the system as axioms, the new expanded system still falls prey to Gödel's proof.

It's the ultimate catch-22.

The problem is, there's no way to tell the difference between a true-but-thus-far-unproven statement and a true-but-unprovable statement.  There have been a number of conjectures that have baffled mathematicians for ages, and finally been proven -- the four-color map theorem and Fermat's last theorem come to mind.  But one that has resisted all attempts at a proof is the strange Collatz conjecture, also known as the hailstone sequence, proposed in 1937 by the German mathematician Lothar Collatz.

What's wild about the Collatz conjecture is that it's simple enough a grade-school student could understand it.  It says: start with any natural number.  If it's even, divide it by two.  If it's odd, multiply it by three and then add one.  Repeat the process until you reach 1.  Here's how it would work, starting with 7:

7 - 22 - 11 - 34 - 17 - 52 - 26 - 13 - 40 - 20 - 10 - 5 - 16 - 8 - 4 - 2 - 1.

You can see why it's called a "hailstone sequence;" like hailstones, the numbers rise and fall, sometimes buffeted far upwards before finally "falling to Earth."  And what Collatz said was that, subject to this procedure, every natural number will finally fall to 1.

Simple enough, right?  Wrong.  The best minds in mathematics have been stumped as to how to prove it.  The brilliant Hungarian mathematician Paul Erdös said, "Mathematics may not be ready for such a problem."  American mathematician Jeffrey Lagarias was even bleaker, saying, "[The Collatz conjecture] is completely out of reach of present-day mathematics."

What's weirdest is that there does seem to be a pattern -- a relationship between the number you start with and the number of steps it takes to reach 1.  Here's what the graph looks like, if you plot the number of steps as a function of the number you start with, for every number from 1 to 9,999:

[Image is in the Public Domain]

It certainly doesn't appear to be random, but this doesn't get us any closer to proving that all numbers descend to 1 in a finite number of steps.

The reason all this comes up is a recent paper in The Journal of Supercomputing showing that every number between 1 and 2 to the 71st power obeys the Collatz conjecture.  That's a bit over twenty quintillion.  Of course, this still isn't proof; all it'd take is one single number in the octillions that either (1) keeps rising higher and higher forever, or (2) leads to an infinite loop, to disprove it.  So until a formal proof (or disproof) is found, all mathematicians can do is keep extending the list of numbers tested.

But is the Collatz conjecture one of Gödel's inevitable true-but-unprovable statements?  No way to know, even if it never does get proven.  That's the brilliance -- and the frustration -- of Gödel's proof.  Such statements are forever outside the axiomatic system, so there's no way to get at them.

So much for mathematics being firm ground.

Anyhow, that's our mind-blowing bit of news for this morning.  A simple conjecture that has baffled mathematicians for almost ninety years, and is no closer to being solved now than it was when it was first proposed.  It's indicative of how weird and non-intuitive mathematics can be.  As Douglas Hofstadter put it, "It turns out that an eerie type of chaos can lurk just behind a facade of order -- and yet, deep inside the chaos lurks an even eerier type of order."

****************************************

The halting problem

A couple of months ago, I wrote a post about the brilliant and tragic British mathematician, cryptographer, and computer scientist Alan Turing, in which I mentioned in passing the halting problem.  The idea of the halting problem is simple enough; it's the question of whether a computer program designed to determine the truth or falsity of a mathematical theorem will always be able to reach a definitive answer in a finite number of steps.  The answer, surprisingly, is a resounding no.  You can't guarantee that a truth-testing program will ever reach an answer, even about matters as seemingly cut-and-dried as math.  But it took someone of Turing's caliber to prove it -- in a paper mathematician Avi Wigderson called "easily the most influential math paper in history."

What's the most curious about this result is that you don't even need to understand fancy mathematics to find problems that have defied attempts at proof.  There are dozens of relatively simple conjectures for which the truth or falsity is not known, and what's more, Turing's result showed that for at least some of them, there may be no way to know.

One of these is the Collatz conjecture, named after German mathematician Lothar Collatz, who proposed it in 1937.  It's so simple to state that a bright sixth-grader could understand it.  It goes like this:

Start with any positive integer you want.  If it's even, divide it by two.  If it's odd, multiply it by three and add one.  Repeat.  Here's a Collatz sequence, starting with the number seven:

7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Collatz's conjecture is that if you do this for every positive integer, eventually you'll always reach one.

The problem is, the procedure involves a rule that reduces the number you've got (n/2) and one that grows it (3n + 1).  The sequence rises and falls in an apparently unpredictable way.  For some numbers, the sequence soars into the stratosphere; starting with n = 27, you end up at 9,232 before it finally hits a number that allows it to descend to one.  But the weirdness doesn't end there.  Mathematicians studying this maddening problem have made a graph of all the numbers between one and ten million (on the x axis) against the number of steps it takes to reach one (on the y axis), and the following bizarre pattern emerged:

[Image licensed under the Creative Commons Kunashmilovich, Collatz-10Million, CC BY-SA 4.0]

So it sure as hell looks like there's a pattern to it, that it isn't simply random.  But it hasn't gotten them any closer to figuring out if all numbers eventually descend to one -- or if, perhaps, there's some number out there that just keeps rising forever.  All the numbers tested eventually descend, but attempts to figure out if there are any exceptions have failed.

Despite the fact that in order to understand it, all you have to be able to do is add, multiply, and divide, American mathematician Jeffrey Lagarias lamented that the Collatz conjecture "is an extraordinarily difficult problem, completely out of reach of present-day mathematics."

Another theorem that has defied solution is the Goldbach conjecture, named after German mathematician Christian Goldbach, who proposed it to none other than mathematical great Leonhard Euler.  The Goldbach conjecture is even easier to state:

All positive integers greater than two can be expressed as the sum of two prime numbers.

It's easy enough to see that the first few work:

3 = 1 + 2
4 = 1 + 3
5 = 2 + 3
6 = 3 + 3 (or 1 + 5)
7 = 2 + 5
8 = 3 + 5

and so on.

But as with Collatz, showing that it works for the first few numbers doesn't prove that it works for every number, and despite nearly three centuries of efforts (Goldbach came up with it in 1742), no one's been able to prove or disprove it.  They've actually brute-force tested all numbers between 3 and 4,000,000,000,000,000,000 -- I'm not making that up -- and they've all worked.

But a general proof has eluded the best mathematical minds for close to three hundred years.

The bigger problem, of course, is that Turing's result shows that not only do we not know the answer to problems like these, there may be no way to know.  Somehow, this flies in the face of how we usually think about math, doesn't it?  The way most of us are taught to think about the subject, it seems like the ultimate realm in which there are always definitive answers.

But here, even two simple-to-state conjectures have proven impossible to solve.  At least so far.  We've seen hitherto intractable problems finally reach closure -- the four-color map theorem comes to mind -- so it may be that someone will eventually solve Collatz and Goldbach.

Or maybe -- as Turing suggested -- the search for a proof will never halt.

****************************************