Imagine you are given the following mathematical function: If the input number is odd, multiply it by 3 and add 1. If the input number is even, divide it by 2. Now, apply this function repeatedly to itself. Do you think that every natural number input will eventually reach 1? If you try to prove that every number will not eventually reach 1 by counter example, you will have to start above one sextillion. Mathematicians have tested this function on over a sextillion different values with computers, and every series has been found to lead to 1. Yet, no one has been able to mathematically prove that every number will, when the function is applied indefinitely, eventually reach 1. Why is it so difficult to solve such a seemingly simple problem?
To answer this question, look to the opinion of Paul Erdős, one of the most prolific mathematicians of the 20th century. Erdös argued that "Mathematics may not be ready for such problems". To understand the reasons why the Collatz conjecture is so difficult to prove, we must dig deeper. A similar conjecture exists named the “Nollatz” conjecture, but we could also call it the n + 1 conjecture, as the only difference between it and the Collatz conjecture is that there is no multiplication. The Nollatz conjecture can actually be proved, because the value of the number every two iterations is always smaller than the original value as (n + 1)/2 is always smaller than n for all values of n greater than 1. Unfortunately, this method of proof cannot be extended to the Collatz conjecture, as (3n + 1)/2 is never smaller than n for any natural number n. A simplified version of the Collatz conjecture is to return (3n + 1)/2 when the input is odd, and returning n/2 when the input is even. This simplification can be made because we know that the result of (3n + 1) for all odd numbers n is always even. With this simplification made, we can now analyze another facet through which the conjecture could be proven.
A cycle is a sequence (a0, a1, ..., aq) of distinct positive integers where f(a0) = a1, f(a1) = a2, ..., and f(aq) = a0. The only known cycle is (1, 2) of period 2, called the trivial cycle. If a cycle were to be found other than the nontrivial cycle, it would disprove the Collatz conjecture as the numbers would cycle back to each other and never reach one. Unfortunately though, the length of a non-trivial cycle is known to be at least 186,265,759,595. And if it could be shown that for all positive integers less than 1.5 * 2^70 the Collatz sequences reach 1, then this lower bound of cycle length would rise to 355,504,839,929. This result is based on the continued fraction expansion of ln(3) / ln(2).
So, if no one has been able to prove the Collatz conjecture so far, what progress has been made? Two researchers, Krasikov and Lagarias, demonstrated in a computer-aided proof that the amount of numbers in the range [1, x] that reach 1 is greater than or equal to x^0.84, for all sufficiently large x. In 2019, Terence Tao improved this result by showing that in the sense of logarithmic density, almost all Collatz orbits descend below any given function of the starting point, provided that this function diverges to infinity. Quanta Magazine wrote that this was "one of the most significant results on the Collatz conjecture in decades". Although searching for counterexamples with computers may seem like misguided hope, other conjectures such as the Pólya conjecture have been disproven by counterexample only when looking at large numbers.
Our Results:
When we tried solving the Collatz Conjecture, we immediately ran into our first problem: how would we be able to create a function such that it could be manipulated to be able to repeatedly apply itself, as the current known function of the Collatz conjecture was a piecewise function, making it exceedingly difficult to apply to itself. Thankfully, Pierre already had experience combining piecewise functions into a singular function and we were able to produce a new Collatz function that was not piecewise:
After finding the Collatz function in non-piecewise form, we decided to graph it on Desmos, and to our amazement, it was able to output the proper values.
From here we could repeatedly apply the function to itself by first defining f(x) to be the function shown above, and then asking desmos to graph f(f(x)), f(f(f(x))) etc. The problem was, this method would not be able to find the Collatz function applied at infinite iterations, which is what we would need to be able to solve the Collatz conjecture. We then tried a new approach, where we instead tried to graph the inverse Collatz relation, with the idea that if we apply the inverse to itself infinite times and have it lead back to all the natural numbers, the Collatz Conjecture would be proven, however we faced similar difficulty of being unable to apply the relation an infinite number of times to itself.
While we were unable to prove the Collatz Conjecture, we did find interesting empirical data of the equations of lines where all the values of the Collatz function lie.
What is interesting is that every two iterations there seem to be new slopes created, and while some of these slopes seem to converge to 0, others seem to diverge to infinity.
Overall, the Collatz Conjecture is such a notable problem in mathematics for its seemingly simple nature, yet being extremely difficult to solve. If you would like to delve further into this problem, you can read a full book that has been written about it: The Ultimate Challenge: The 3x + 1 problem.
Comments