Pick any positive whole number k and define the Collatz Map
f(k) = k/2 if k is even,
f(k) = 3k+1 if k is odd.
and repeat ad infinitum
The Collatz Conjecture is that whatever number you start from you will always reach 1 and than be trapped in the cycle 1,4,2,1….
True, False or Undecidable?
Most mathematicians think the conjecture is true. Recent research by Terence Tao shows that the conjecture is likely to be true for “almost all” numbers.
A single example of a cycle that does not end in 1 would show the conjecture is false. It is of course impossible to confirm experimentally that a trajectory exists that drifts off to infinity and not to 1.
The interesting case is if the Collatz Conjecture is mathematically undecidable, that is, given the axioms on which current mathematics is based (ZFC) it can’t be proven true or false without extending mathematics. A cycle that does not hit 1 would be of interest since it would show that the existing axioms of mathematics are not sufficient to “capture” the hypothesis.
The Late John Horton Conway proved that a natural extension of the Collatz conjecture is algorithmically undecidable, that is there is no program that can resolve the conjecture, suggesting.
There are two notions of undecidability involved here. Mathematical undecidability means that the truth or falsity of the conjecture cannot be deduced from the basic axioms of mathematics. Computational undecidability means there is no program that can say yes or no to the question “Does the repeated Collatz map send this number to 1”
In principle a programmed search might find a cycle that does not hit 1, which would show that current mathematics is incomplete. A proof that such a cycle could not exist would, together with proof the conjecture is not decidable, mean the conjecture is absolutely undecidable, that is its truth value can never be known. Philosophers are currently undecided whether there are any absolutely undecidable statements, so take this statement at your own risk.
On its own the Collatz conjecture seems insignificant, at least for everyday mathematics. Some mathematicians believe new mathematical tools will be needed to turn the conjecture into a theorem or disprove it and my gut feeling is these tools will be significant in other areas of mathematics.
A proof the conjecture is undecidable in mathematics, and a related proof that no cycle exists which does not hit 1 would strongly imply the conjecture is absolutely undecidable, since we have no computers that can check an infinite set of numbers in a finite time.
I quickly implemented a calculator of my own in Java using the BigInteger class and it checked a 100+ digit number taking about 7 milliseconds and over 2,000 arithmetic operations to reach 1. Clearly systematic search to reach hundred digit numbers is likely to take longer than the life of the universe. This would be true even if the time to check a single number were to be reduced to picoseconds.
If you want to test some numbers yourself here is the best calculator I found on the web
The Collatz conjecture is a seductive siren luring working mathematicians away from meaningful research. It seems unlikely it will have implications for other areas of everyday mathematics and may be undecidable mathematically but is, in principle, computationally refutable unless someone proves there is no cycle that ends in 1, which may make it absolutely undecidable.
Investigating the Collatz conjecture has, for me, been a fun trip involving Gödel’s theorems, The halting problem, and a number of other areas of everyday mathematics. It showed how little I know and hopefully reminded me to beware of Dunning Kruger.
Now it’s time for something else, maybe Mythology and Folklore again.
© 2022 AlexK2009