Like any mathematician, when first exposed to the Collatz Conjecture, my first inclination was “how hard can this be”? So, after a couple of weeks of doing virtually nothing else, I can honestly report that it is a very difficult problem.
I think I can solve it, given enough time, perhaps an eternity. Given it is such a deceptively simple problem to state, but has been notoriously difficult to solve, if indeed it is solvable, which, personally, I am quite convinced that it is, I feel inclined to post a brief introduction to this fascinating, and time consuming, problem.
Formulation:
The conjecture is generally attributed to German mathematician Lothar Collatz, who is said to have first proposed it in 1937. His interest was in the behaviour of iterated functions. The problem was circulated among mathematicians over the following decades, gaining various names like the 3n + 1 problem, Syracuse problem, Hasse's algorithm, Kakutani's problem, and Ulam's problem. The rule is remarkably simple:
If a positive integer n is even, the next number in the sequence is n / 2.
If n is odd, the next number is 3n + 1. The conjecture states that starting with any positive integer, this sequence will always eventually reach the number 1.
Previous Attempts at Solving It:
Despite its apparent simplicity, the Collatz conjecture has resisted numerous attempts at a solution. Early work involved testing the conjecture for increasing ranges of numbers using computation. Indeed, the ever increasing computational support for the conjecture is truly astonishing, currently establishing convergence for all numbers below 2075 × 260 << ∞ (that is still a very big number). Alas, this approach is not a proof, and never can be. Convergence verification of the Collatz problem
Mathematicians have approached the problem from various angles, including:
Analyzing the properties of the sequences: Studying the "stopping time" (steps to reach 1) and the maximum values reached.
Using concepts from dynamical systems: Viewing the Collatz process as a simple, albeit complex, dynamical system.
Applying tools from number theory: Investigating the problem using modular arithmetic and p-adic analysis.
Exploring connections to computation theory: Showing the equivalence of the Collatz conjecture to problems in tag systems, which hints at its potential undecidability within certain formal systems.
Despite these efforts, no definitive proof of the conjecture or a single counterexample (which would suffice to prove the conjecture to be false) has been found. The difficulty lies in the unpredictable "hailstone" nature of the sequences, which can increase significantly before decreasing, making it hard to prove that they will always eventually reach 1.
Paul Erdős, who occasionally haunted the halls in the math department at the University of Calgary when I was engaged in undergraduate and graduate studies there back in the late 1970’s and early 1980’s, famously commented on the problem, saying, "Mathematics is not yet ready for such problems."
Significant partial results have been achieved, such as Terence Tao's 2019 work showing that "almost all" Collatz orbits attain "almost bounded" values, suggesting that divergence is extremely rare. However, this is not a full proof for all numbers. It is, however, as Professor Tao has noted, perhaps as close to a proof as one can come without having actually proved it.
Almost all orbits of the Collatz map attain almost bounded values
There are lots of youtube videos on the topic, and I’ve probably watched most of them by now. Here are a few, in increasing order of detail:
A very short introduction:
Sorry William, this is not a proof. It is just a few instantiations:
NJ Wildberger’s cogent introduction:
I think this is AI generated (who converses like this?), but it is informative:
The background music drives me crazy (but nice photos). Fortunately it is short:
For those who have persevered, I saved the best for last:
If you’re really keen on this problem, here are a few papers to read at your leisure:
The 3x+1 problem: An annotated bibliography (1963--1999)
The 3x+1 Problem: An Annotated Bibliography, II (2000-2009)
Some nice computational renderings of the problem can be found here:
https://en.wikipedia.org/wiki/Collatz_conjecture
More to come, stay tuned, but don’t hold your breath. Happy computing!
Here is a nice article on Terence Tao’s “almost all…” result with some cool links:
mathematician-proves-huge-result-on-dangerous-problem
And here is a lecture of Professor Tao’s on the problem: