Terry Tao Almost Proves Collatz Conjecture
Written by Mike James   
Friday, 13 September 2019

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.

 

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:

Collatz Conjecture

 The cartoon is accurate, but let's make the conjecture, which was proposed in 1937 by German mathematician Lothar Collatz, clear:

  • Pick a number, a positive integer
  • If even divide by 2
  • If odd multiply by 3 and add one
  • Repeat above two steps with new value

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 non-technical 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 Information

Almost all Collatz orbits attain almost bounded values (blog post)

Almost all orbits of the Collatz map attain almost bounded values (paper pdf)

Related Articles

The Computer Science Breakthrough Of The Decade Now Reinstated!

Erdos Conjecture Proven

Travelling Salesman - A Movie About P=NP

Collatz conjecture proved?

Update on the Proof of P≠NP?

NP-Complete - Why So Hard?

Computational Complexity

Computability

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.

 

Banner


Waltz Write Ahead Log Open Sourced
23/09/2019

A distributed write-ahead log has been open sourced by WePay. Waltz was originally designed to be the ledger of money transactions on the WePay system and has since been generalized to be suitable for [ ... ]



Microsoft Drags Its Feet On C++ for .NET Core
04/10/2019

A recent blog post promises that C++/CLI will be available in the next version of .NET Core. but this begs the question of why it isn't available in this version of .NET Core. Does C++ love .NET?


More News

graphics

 



 

Comments




or email your comment to: comments@i-programmer.info

 

Last Updated ( Friday, 13 September 2019 )