5 ms·

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

empath75 7y ago
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 https://www.youtube.com/watch?v=5mFpVDpKX70
- lisper 7y ago
  Wikipedia also has an excellent overview: https://en.wikipedia.org/wiki/Collatz_conjecture https://en.wikipedia.org/wiki/Collatz_conjecture
  - HarryHirsch 7y ago
    The article cites Erdős, saying "Mathematics may not be ready for such problems"
    - colorincorrect 7y ago
      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?
      - dannyking 7y ago
        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.
      - taejo 7y ago
        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.
      - lidHanteyk 7y ago
        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.
mgraczyk 7y ago
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.
- paulddraper 7y ago
  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) }
remus 7y ago
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.
deleted 7y ago
[deleted]
zawerf 7y ago
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-orbits-attain-almost-bounded-values/#comment-521820 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)

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 https://www.youtube.com/watch?v=5mFpVDpKX70

lisper 7y ago
Wikipedia also has an excellent overview: https://en.wikipedia.org/wiki/Collatz_conjecture https://en.wikipedia.org/wiki/Collatz_conjecture
- HarryHirsch 7y ago
  The article cites Erdős, saying "Mathematics may not be ready for such problems"
  - colorincorrect 7y ago
    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?
    - dannyking 7y ago
      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.
    - taejo 7y ago
      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.
    - lidHanteyk 7y ago
      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.

mgraczyk 7y ago

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.

paulddraper 7y ago
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) }

remus 7y ago

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.

deleted 7y ago

[deleted]

zawerf 7y ago

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-orbits-attain-almost-bounded-values/#comment-521820 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)