This problem was first posed in the early 1600s and was the subject of intense public interest. Mathematics is full of open problems that...
 |
| This problem was first posed in the early 1600s and was the subject of intense public interest. |
Take Fermat’s Last Theorem for example. This problem was first posed in the early 1600s and was the subject of intense public interest. Cash prizes were offered for its solution, and reportedly thousands of incorrect proofs were submitted by amateur mathematicians. It was only solved by Andrew Wiles in 1994, over 300 since it was first posed.
(Note: Friend and fellow science writer Harlan Brothers and I have started a new publication called “Science Spectrum” here on Medium where we will now be publishing our content. Please consider following our new pub to support our efforts!)
With n, x, y, z ∈ N (meaning that n, x, y, z are all positive whole numbers) and n > 2, the equation xⁿ + yⁿ = zⁿ has no solutions. — Fermat’s Last Theorem
In the centuries of work dedicated to solving Fermat’s Last Theorem, an entirely new field called algebraic number theory was created to try and tackle this proof. While it took a lot of painstaking effort, the influence of this challenge was immensely important to get modern mathematics to its current state. Number theory would not be where it it today with Fermat’s Last Theorem serving as a goal.
Fermat’s Last Theorem is solved now, and it thus has less to contribute to future developments in math. Most of the present work on it involves finding simpler proofs; the one published by Wiles is over 100 pages long. Perhaps an easier, more intuitive proof exists? However, there are many other unsolved problems in mathematics that continue to get a lot of attention from the public. This includes the infamous Collatz Conjecture.
In this article, I’m going to explain what the Collatz Conjecture is. Like Fermat’s Last Theorem, it’s pretty simple to understand. I’ll explain some of the efforts that have been made to solve it along with why it remains so troublesome for mathematicians. There’s a lot to cover here, so let’s dive in!
The Collatz Conjecture
Lother Collatz was an influential German mathematician in the 20th century. While he is most famous today for posing the Collatz Conjecture, he was also influential in the founding of spectral graph theory. This field forms a link between mathematical graphs and their characteristic polynomials. To see how the Collatz Conjecture works, first pick any random integer n. You then perform one of two actions on it.
- If n is even, then divide n by two
- If n is odd, then multiply it by 3 and add 1
The Collatz Conjecture is quite simple, it states that every positive integer will eventually reach this loop. More specifically, every positive integer will eventually lead to the number one. The math here is so simple that an elementary student could do it. Yet, proving it for all positive numbers remains elusive. So if one of the numbers you tried did not end up in the 1 -> 4 -> 2 loop, stop what you are doing immediately and publish your results!
When I first heard about the Collatz Conjecture, I decided to take a stab at it. Like many mathematicians, it seemed so simple I thought I could make a breakthrough. Most of my work involved working backward from 1, and seeing what numbers could be created by performing to opposite of the two actions. If I could prove that every number was formed this way, then the problem would be solved. Obviously, this did not work out for me, but I had a lot of fun messing around with it.
Stopping Time
One of the primary tools mathematicians use to tackle this problem is a concept called stopping time. This number measures how many steps you have to take to eventually get to the number one. As expected, the numbers generally take longer to reach 1 the larger they are. There are some really cool patterns in this graph, it’s fun to try and make sense of it.
When you tried this for yourself, hopefully, you did not pick the number 27 as a starting point which takes 111 steps to reach 1! During this sequence, the values climb as high as 9232 before eventually settling back to 1. You can see that with larger numbers, clusters will form around certain stopping times.
The smallest values are always powers of 2. For example, the numbers 1, 2, 4, 8, 16, etc. have much smaller stopping times than their neighbors. In the above chart, you can see really low stopping times at 1024, 2048, 4096, and similarly other powers of 2. This is because these values are only ever divided by two in their chain, they never get larger because they will always be even during this process. Compare the chains of 1024 and its neighbor 1023. The sequence for 1023 must increase in size several times before falling back down to 1. In contrast, 1024 falls right down to 1 with several divisions of 2.
Solutions
Most mathematicians believe that the Collatz Conjecture is true. It makes intuitive sense for it to hold for all positive integers. Additionally, for it not to be true, some very strange things would have to happen. Some number n would have to exist that either creates a new loop similar to 1 -> 4 -> 2, or it would go on forever in a chain that never ends. Neither of these two options seems very likely.
Using modern computational power, we know that all numbers less than 3 * 10²⁰ end in the 1 -> 4 -> 2 loop. This is an absolutely massive number! Because of this and the heuristic argument above, the Collatz Conjecture is likely true. However, proving it is an entirely different story.
Some view the Collatz Conjecture as being out of reach given our modern tools. It’s amazing how little progress has been made on it. The fundamental difficulty lies with prime factorizations. If you aren’t familiar with this concept, it’s a landmark fact that has been proven using number theory. Every integer can be written as a unique product of prime numbers. For example, 10 = 2*5 and 27 = 3³. This fact is so important it has been named the Fundamental Theorem of Arithmetic.
The Collatz Conjecture process works by checking if a number is even, and doing a step based on the answer. Another way to look at this is it checks if a number has 2 in its factorization or not. Since 10 = 2*5 which contains 2, it is even. In contrast, 27 = 3³ does not contain 2, so it is not even. Which step you take next in the Collatz Conjecture process is determined by this check.
Say we have the prime factorization of a number n. It is very easy to predict the prime factorization of n / 2. You just remove the 2. 10 = 2*5 becomes 5 = 5. It’s also easy to multiply it by 3. 27 = 3³ becomes 81 = 3⁴. In general, multiplication and division are both easy to represent in prime factorizations, because you are already multiplying a set of numbers together. However, adding 1 is extremely difficult to represent this way.
We have very little theory telling us how a prime factorization of n informs the prime factorization of n + 1. Mathematics is sorely lacking in this area. The closest we can get is that if n has a 2 in its prime factorization, then n +1 will not, and vice-versa. This is the same as saying adding one to a number switches it from even to odd, or the opposite. And because the prime factorization is essential to determining which step comes next, we aren’t left with much to work with.
For example, consider the steps from 27 to (3 * 27) + 1. The prime factorization changes from 27 = 3³ to 82 = 2 * 41 with 41 being a prime number. We do know that if n is odd, 3n + 1 will be even so we expect a 2 in the resulting prime factorization. But there is no theory out there predicting the appearance of the 41. This hole in our current understanding of prime numbers is what limits us from making progress on the Collatz Conjecture. “Mathematics may not be ready for such problems.” — Paul Erdős. It may be a long time before tools are developed to handle such questions as the Collatz Conjecture.
Going Further
I hope you learned something! Unsolved problems in mathematics are fascinating and can generate a lot of creativity in people trying to solve them. Especially interesting are the problems that are simple to understand. If you want to learn more about the Collatz Conjecture, I’ve included some links below for you to check out.
- If you want to learn about the theory behind this problem and why it is so hard to solve, I have a free online textbook on Number Theory linked here. I used this book to supplement material during college and found it very easy to understand.
- Veritasium has an amazing video about the Collatz Conjecture that I highly recommend.
- For more videos, check out this playlist of ideas that dive deep into methods used to try and solve the conjecture.