Almost all Collatz orbits attain almost bounded values | Hacker News Reader

Almost all Collatz orbits attain almost bounded values

terrytao.wordpress.com

84 pointsweinzierl17 comments

Those who are upvoting: Why is this interesting / important?

The Collatz Conjecture, which the paper described in the blog works toward proving, is taught in introductory computer science and discrete math courses. Many people on this site who have gone through a university CS program will have heard of this problem and its notorious difficulty, so progress would be familiar and potentially exciting.

It's a particularly good example of memoization: both simple and without a suitable DP solution.

   int collatz(int n) {
     return n == 1 ? 0 : 1 + collatz(n % 2 ? 3 * n + 1 : n / 2)
   }

The Collatz Conjecture is a very well known problem, partly because it is very easy to understand. It's also a very difficult problem.

Terry Tao (the author) is one of the top mathematicians in the world and this appears to be a significant step towards proving the full conjecture.

Collatz Conjecture is one of those frustrating conjectures that a middle schooler can understand, but no one has proved, despite some of the best minds in math taking a crack at it.

https://www.youtube.com/watch?v=5mFpVDpKX70

Wikipedia also has an excellent overview:

https://en.wikipedia.org/wiki/Collatz_conjecture

The article cites Erdős, saying "Mathematics may not be ready for such problems"

I've read this sentiment before, but could never understand why. Is something about this question that is fundamentally different from normal questions in number theory?

The Collatz map itself gives a discrete dynamical system, which we can't tackle in general. Conway showed that a generalization of Collatz, where 3 is generalized to any odd prime, is Turing-undecideable.

I'm not a number-theory expert, but I think that non-primitive-recursive functions (iteration/recursion that isn't bounded ahead of time) don't really show up in number theory at all.

Not that we know of, and yet the proof is still illusive despite many great minds attempting to solve it. That's what makes it so alluring.

I upvoted for Terry's very insightful meta-commentary on when partial results can or cannot help with the full proof: https://terrytao.wordpress.com/2019/09/10/almost-all-collatz...

I thought it was interesting how mathematician have techniques to easily prove something for the 99% case but still have the general problem be completely unapproachable.

(and because collatz is famous, terry is a fields medalist, etc)

Is there any special significance to the Collatz function, besides the sportive aspect of the Collatz conjecture being difficult to prove?

I'm not a mathematician, but I'd say that it's one of the simplest and most elegant instances of its kind, and that in general we don't seem to have good ways of dealing with iterative processes that can both lengthen and shorten (or increase and decrease) the size of the output in relation to the input. A generalization of the proof of this might be quite illuminating for a lot of hard problems in number or complexity theory.

A recent “Full stack engineering” interview duo presented me with a prompt related to a bounded version of the Collatz conjecture.

Proving something, or coding something?

Coding, bounded to 1M. ‘Twas the first time I heard of Collatz. This article is the second in as many weeks

Reply on news.ycombinator.com