From: veritasium
The Collatz Conjecture, also known as the Ulam conjecture, Kakutani’s problem, Thwaites conjecture, Hasse’s algorithm, the Syracuse problem, or simply 3N+1, is considered “the most dangerous problem in mathematics” [00:00:00]. Young mathematicians are often warned not to spend time on it, as even the world’s best mathematicians have been unable to solve it [00:00:03]. Paul Erdos, a famous mathematician, stated, “Mathematics is not yet ripe enough for such questions” [00:00:16]. Jeffrey Lagarias, considered the world authority on 3x+1, advises against working on it for career progression [00:03:47].
The conjecture states that if you take any positive integer and repeatedly apply two rules – if the number is odd, multiply by three and add one; if the number is even, divide by two – it will eventually reach the “four, two, one loop” (4 → 2 → 1 → 4) [00:01:33]. The numbers generated by this process are called hailstone numbers because they rise and fall like hailstones before eventually “falling down to one” [00:02:17].
Evidence Supporting the Conjecture
Brute Force Testing
Vast computational efforts have been made to test the conjecture. Every single number up to two to the 68 (approximately 295 quintillion numbers) has been tested, and all of them have been confirmed to eventually reach the four, two, one loop [00:10:31]. Based on this, mathematicians estimate that any other potential loop would need to be at least 186 billion numbers long [00:11:03].
Statistical Tendency to Shrink
Despite odd numbers being more than tripled and even numbers only halved, the sequence statistically tends to shrink [00:07:07]. This is because every time an odd number is multiplied by three and one is added, the result is always an even number, which then must be divided by two [00:07:30]. This effectively means odd numbers are increased by a factor of about 3/2 [00:07:40].
When considering the path from one odd number to the next odd number in the sequence:
- 50% of the time, the next odd number is reached after dividing by 2 (factor of 3/2) [00:08:05].
- 25% of the time, it divides by 4 (factor of 3/4) [00:08:10].
- 12.5% of the time, it divides by 8 (factor of 3/8) [00:08:21].
- And so on [00:08:25].
Taking the geometric mean of these factors (3/2, 3/4, 3/8, etc.), it averages out to 3/4, which is less than one [00:08:29]. This statistical analysis suggests that sequences are more likely to shrink than grow [00:08:39].
Benford’s Law
Analyzing the leading digits of numbers in Collatz sequences reveals a pattern consistent with Benford’s Law [00:05:16]. For instance, across the first billion sequences, approximately 30% of numbers start with one, and the frequency decreases for higher digits [00:05:53]. This law appears in many natural datasets where numbers span several orders of magnitude [00:06:15]. While interesting, Benford’s law cannot prove whether all numbers eventually reach the loop [00:06:57].
Terry Tao’s Proof
In 2019, renowned mathematician Terry Tao demonstrated that “almost all numbers” in Collatz sequences will eventually become smaller than any arbitrarily slowly rising function (e.g., log x or log log x) [00:12:35]. This means that for almost all numbers, there’s a guarantee of finding an arbitrarily small number somewhere in its sequence [00:13:04]. Tao stated that this is “about as close as one can get to the Collatz conjecture without actually solving it” [00:13:13].
Potential Counterexamples or Reasons It Might Be False
The conjecture could be false in two ways [00:09:58]:
- Divergent sequence: A number’s sequence grows indefinitely to infinity, never returning to one [00:10:01].
- Undiscovered loop: A sequence of numbers forms a closed loop other than the four, two, one loop, remaining unconnected to the main graph [00:10:14].
To date, no such divergent sequence or alternative loop has been found [00:10:25].
Arguments for its Falsity
Some mathematicians suggest that the sheer difficulty in proving the conjecture might indicate it’s not true [00:13:27]. If everyone is trying to prove it true, few are actively searching for counterexamples, which sometimes leads to breakthroughs [00:13:34].
Analogy to Polya Conjecture
The Polya conjecture, proposed in 1919, stated that the majority of natural numbers up to any given number have an odd number of prime factors [00:16:24]. This conjecture was proven false in 1958 by C. Brian Haselgrove, who found a counterexample at 1.845 x 10^361 [00:16:34]. This counterexample is astronomically larger (10^340 times) than the numbers tested for the Collatz conjecture (up to 2^68) [00:16:48]. This suggests that even extensive brute-force testing doesn’t guarantee a conjecture’s truth across all numbers.
Turing Machine Analogy
Thinking of the Collatz Conjecture as a simple program running on a Turing machine where the seed number is the input, testing inputs up to 68 bits long does not provide strong confidence that it will work for all inputs [00:16:54]. It’s possible to calculate numbers that will exhibit specific, finite behaviors (e.g., increase by 3/2 for a hundred consecutive times), but control is lost after that specified section [00:17:24].
Behavior with Negative Numbers
When the same 3x+1 rules are applied to negative numbers, three independent loops have been identified, starting at low values like -17 and -5 [00:14:44]. The existence of disconnected loops on the negative side of the number line raises questions about why they wouldn’t exist on the positive side [00:15:03].
”Almost All” vs. “All”
Terry Tao’s proof applies to “almost all numbers,” which has a precise mathematical definition: as the numbers being considered go to infinity, the fraction that obeys the criteria goes to one [00:15:19]. However, proving “almost all” numbers obey a criterion is not the same as proving “all” numbers do [00:15:22]. For example, “almost all numbers are not perfect squares” (because the percentage of perfect squares approaches zero as numbers go to infinity), yet there are infinitely many perfect squares [00:15:58]. This highlights that a statistical tendency does not rule out the existence of rare, specific counterexamples.
Undecidability
Another possibility is that the Collatz Conjecture is undecidable, meaning it can never be proven true or false within our current mathematical framework [00:18:50]. In 1987, John Conway created a generalization of 3x+1 called FRACTRAN, a Turing-complete mathematical machine [00:18:55]. Because FRACTRAN is Turing-complete, it is subject to the halting problem, meaning it’s impossible to determine if the machine will ever stop running for an arbitrary input [00:19:11]. While this doesn’t directly prove that 3x+1 is also subject to the halting problem, it suggests the possibility that the conjecture might be inherently unprovable [00:19:21].
The difficulty in solving the Collatz conjecture underscores the complexity of mathematics, showing that simple-looking problems can be profoundly intractable [00:19:36]. It highlights the peculiar and intricate nature of numbers, where a basic operation can lead to organic-looking, complex structures, and the question of whether all numbers connect to this structure or if a unique thread runs off to infinity remains unanswered [00:20:04].