The Collatz conjecture is for computer science what until recently Fermat’s last theorem was for mathematics: a famous unsolved problem that is very simple to state.
The Collatz conjecture, also known as the 3n+1 problem, asks whether the following function terminates for all positive integer arguments n.
def collatz(n):
if n == 1:
return 1
elif n % 2 == 0:
return collatz(n/2)
else:
return collatz(3*n+1)
In words, this says to start with a positive integer. Repeatedly either divide it by 2 if it’s even, or multiply it by 3 and add 1 if it’s odd. Will this sequence always reach 1?
The Collatz conjecture is a great example of how hard it can be to thoroughly understand even a few lines of code.
Terence Tao announced today that he has new partial results toward proving the Collatz conjecture. His blog post and arXiv paper are both entitled “Almost all Collatz orbits attain almost bounded values.”
When someone like Tao uses the word “almost,” it is a term of art, a common word used as a technical term. He is using “almost” as it is used as a technical term in number theory, which is different from the way the word is used technically in measure theory.
I get email routinely from people who believe they have a proof of the Collatz conjecture. These emails are inevitably from amateurs. The proofs are always short, elementary, and self-contained.
The contrasts with Tao’s result are stark. Tao has won the Fields Medal, arguably the highest prize in mathematics [1], and a couple dozen other awards. Amateurs can and do solve open problems, but it’s uncommon.
Tao’s proof is 48 pages of dense, advanced mathematics, building on the work of other researchers. Even so, he doesn’t claim to have a complete proof, but partial results. That is how big conjectures typically fall: by numerous people chipping away at them, building on each other’s work.
Related posts
[1] Some say the Abel prize is more prestigious because it’s more of a lifetime achievement award. Surely Tao will win that one too when he’s older.
I hope Pro.Tao win Abel prize in 2020
I think he’s too young. He has accomplished a lot, but I think the prize is usually given to mathematicians approaching retirement.
Thank you Dr Cook for a terse and very readable explanation of the Collatz conjecture. It’s very enjoyable to read about the context of problems like these.