Too Good To Miss: Terry Tao Almost Proves Collatz Conjecture 
Written by Mike James  
Tuesday, 31 December 2019  
There are some news items from the past year that deserve a second chance. Here we have one such  although not as well known as the long standing P=NP conjecture, Collatz has fascinated people for the past eight decades and produced almost as many flawed proofs. Now mathematician Terence Tao seems to be close to a proof. (20190913) If you don't know what the Collatz conjecture is then you haven't missed out on anything really important  with the possible exception of the excellent xkcd cartoon reproduced below: The cartoon is accurate, but let's make the conjecture, which was proposed in 1937 by German mathematician Lothar Collatz, clear:
If you try it you will discover that you eventually reach a result of 1. For example, 10, 5,16, 8, 4, 2, 1. At first you think it must be an accident and so you try a few more tests. Then you become obsessed and write a program  and you always end up at 1. So far it has been verified for values up to 5.76x10^18. The Collatz conjecture is that this is indeed always true, but can you prove it? If you think it should be easy then it is worth knowning that Paul Erdős proclaimed: "Mathematics may not be ready for such problems" Terence Tao at the University of Califonia is closer to a proof than we have ever been. Why isn't it a proof? Because it's a probability argument: Almost all orbits of the Collatz map attain almost bounded values. Why is this important? The reason is that if you can show that the minimum of the Collatz sequence for N is always smaller N for all N>1 then you have proved the Collatz conjecture. The reason is simple. If you get a value m which is smaller than N then the rest of the sequence for N is the same as that as if you had started from m and so we now have that the minimum for the sequence is less than m. You can repeat this and work back to prove the the minimum has to be 1. Tao hasn't quite proved this but he has proved (rewritten to be closer to English): Theorem 2 Let f be any function defined on the integers, excluding zero, and f(N) goes to infinity with N then the minimum of the Collatz sequence for N is less than f(N) for almost all N. If you take f to be the identity than we have the minimum Collatz value for N is smaller than N. So problem solved? Not quite. The weasel word in the theorem is "for almost all". This is a signal that the theorem is probablistic. What this means is that the set of N for which this is true is dense (in the sense of logarithmic density). What this means, in a nontechnical sense is that we have proved that the theorem is true for all but an insignificant number of cases. An insignificant nubmer of cases also includes no cases at all, so the theorem might apply to all N or there might a few examples where it doesn't apply and the Collatz conjecture is wrong after all. So which is it? As Tao writes in an answer to a comment to his blog post: "...but this is one of these situations where there seems to be an enormous gap in difficulty between “almost all” results and “all” results." It looks as if the Collatz conjecture is going to hold out for a while longer. Armed with this probablistic argument it might be possible to see new reasons why it is true.
More InformationAlmost all Collatz orbits attain almost bounded values (blog post) Almost all orbits of the Collatz map attain almost bounded values (paper pdf) Related ArticlesThe Computer Science Breakthrough Of The Decade Now Reinstated! Travelling Salesman  A Movie About P=NP To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
Comments
or email your comment to: comments@iprogrammer.info


Last Updated ( Tuesday, 31 December 2019 ) 