Mathematicians Are So Close to Cracking This 82-Year-Old Riddle
This week, we’ve celebrated the long-awaited answer to a decades-old math problem, and now we’re one step closer to an even older numbers puzzle that has stumped the world’s brightest minds. But many mathematicians, including the one responsible for this newest breakthrough, think a complete answer to the 82-year-old riddle is still far away.
Terence Tao is one of the greatest mathematicians of our time. At age 21, he got his Ph.D. at Princeton. At 24, he became the youngest math professor at UCLA—ever. And in 2006 he won the Fields Medal, known as the Nobel Prize of math, at the age of 31.
One of the best things about Tao is that he really delivers on content, and openly shares it with the world. His blog is like a modern-day da Vinci’s notebook. Name a subject in advanced math, and he’s written about it.
So this week, Tao takes us to the Collatz Conjecture. Proposed in 1937 by German mathematician Lothar Collatz, the Collatz Conjecture is fairly easy to describe, so here we go.
Take any natural number. There is a rule, or function, which we apply to that number, to get the next number. We then apply that rule over and over, and see where it takes us. The rule is this: If the number is even, then divide it by 2, and if the number is odd, then multiply by 3 and add 1.
In closed form that looks like this:
For example, let’s use 10. It’s even, so the rule says to divide by 2, taking us to 5. Now that’s odd, so we multiply 5 by 3 and then add 1, landing us on 16. Now 16 is even, so we cut it in half to get 8. Even again, so halving gets us 4. Now 4 is even, so we take half, getting 2, which is even, and cuts in half to 1.
Start with numbers other than 10, and you’ll still inevitably end at 1 … we think. That’s the Collatz Conjecture.
It’s definitely true for all numbers with less than 19 digits, so that covers whatever you probably had in mind. But even if computers check up to 100 or 1,000 digits, that’s far from a proof for all natural numbers.
Tao’s breakthrough post is titled “Almost All Collatz Orbits Attain Almost Bounded Values.” Let’s break that down slightly. Collatz Orbits are just the little sequences you get with the process we just did. So the Collatz Orbit of 10 is (10, 5, 16, 8, 4, 2, 1, 4, 2, 1, …). Since half of 4 is 2, half of 2 is 1, and 3*1+1 is 4, Collatz Orbits cycle through 4, 2, and 1 forever.
The big detail in Tao’s proclamation is that first “Almost.” That word is the last barrier to a full solution, and it takes different meanings in different math contexts. So what does it mean here?
The technical term in this case is logarithmic density. It’s describing how rare the counterexamples to the Collatz Conjecture are, if they exist at all. They could exist, but their frequency approaches 0 as you go farther down the number line. The goal remains to prove they don’t exist whatsoever.
In essence, Tao’s results says that any counterexamples to the Collatz Conjecture are going to be incredibly rare. There’s a deep meaning to how rare we’re talking here, but it’s still very different from nonexistent.
So, now that we know its counterexamples are rarer than ever, where does that leave the problem? Are we one step away from a complete solution? Well, even Tao says no.
In the comments to the blog post, he says, “one usually cannot rigorously convert positive average case results to positive worst case results, and when the worst case result is eventually proved, it is often by a quite different set of techniques.” In other words, this cool new method may give us a near-solution, but the full solution might take an entirely different approach.
So mathematicians will use Tao’s newest innovations to solve (or nearly solve) other major problems, but it looks like the Collatz Conjecture itself still remains unfinished. For all we know it will take decades, and completely new branches of math, to finally be put to rest. But at least some impossible math problems were eventually solved.
You Might Also Like
