11 ms·

One of the comments was "the Collatz conjecture feels like we're missing a branch of mathematics", or something to that effect. I followed that rabbit hole a bi

One of the comments was "the Collatz conjecture feels like we're missing a branch of mathematics", or something to that effect. I followed that rabbit hole a bit and found the Plya conjecture[0], which was disproven when a counter example was found at approximately 10^361. Here I was naively thinking that if no counter examples were found in the first, say, 10^10 numbers, no counter examples should exist. If only it were so easy. [0]: https://en.wikipedia.org/wiki/P%C3%B3lya_conjecture https://en.wikipedia.org/wiki/P%C3%B3lya_conjecture

messe 3y ago
That's just the first counterexample that was proven to exist. The smallest counter example is less than 10^10 (in fact smaller than 10^9). > The Pólya conjecture was disproved by C. Brian Haselgrove in 1958. He showed that the conjecture has a counterexample, which he estimated to be around 1.845 × 10^361.[3] > An explicit counterexample, of n = 906,180,359 was given by R. Sherman Lehman in 1960;[4] the smallest counterexample is n = 906,150,257, found by Minoru Tanaka in 1980.[5] EDIT: rephrased because despite having a maths degree I can't count.
- klysm 3y ago
  I believe inability to do arithmetic correctly is more common in folks with maths and other STEM degrees
  - messe 3y ago
    I do like to joke that I studied maths because I don't like numbers.
    - at_a_remove 3y ago
      I recall the end of a science fiction novel, wherein we finally meet aliens. It turns out that, as a trend, the species that are good at counting are bad at math and especially counting things at a glance. The species that is best at math have a hard time telling the difference between two things and three things just looking.
    - hinkley 3y ago
      I know a young man with dyscalculia and we were hoping when he got to symbolic math that his problems would diminish. That has not born fruit so far.
    - anthomtb 3y ago
      I pursued and achieved an EE degree plus a couple extra math courses largely because I was "not good at math" as a youth. Nothing like hearing "I don't think math is your subject" from a key adult to light a fire under ones fanny. In hindsight I could have had the same career path with a straight CS degree and much less stress during my college years. No regrets though, math really is fun! Even more so when the classroom setting is removed.
      - BrandoElFollito 3y ago
        When I was about 12yo, I went to the eye doctor with my father (in France). The doctor realized that I had daltonism and told my father in front of me that I would never be an engineer because of that. At school, we had tests to show what we were good at. The guy who came to comment on our tests told me that I should definitely go for something like literature or history. And here I am, an engineer with an extra PhD in physics who dreams about meeting these idiots and explaining to them that what they do is revolting. They are probably dead by now though (it was in the 80's)
        tocs3 3y ago
        daltonism : color blindness Had to look it up.
  - DavidSJ 3y ago
    It's one of the prerequisites in fact.
  - susam 3y ago
    > I believe inability to do arithmetic correctly is more common in folks with maths and other STEM degrees Reminds me of a story from <https://www.ams.org/notices/200410/fea-grothendieck-part2.pdf https://www.ams.org/notices/200410/fea-grothendieck-part2.pd...>. Quoting it below: One striking characteristic of Grothendieck’s mode of thinking is that it seemed to rely so little on examples. This can be seen in the legend of the so-called “Grothendieck prime”. In a mathematical conversation, someone suggested to Grothendieck that they should consider a particular prime number. “You mean an actual number?” Grothendieck asked. The other person replied, yes, an actual prime number. Grothendieck suggested, “All right, take 57.”
    - 1propionyl 3y ago
      This is absolutely my personal experience. I am absolutely awful at arithmetic, but I think pretty competent at decently advanced mathematics. It's like they say: the only numbers a mathematician needs are 0, 1, and 2 (and just because it's not 1).
      - eru 3y ago
        In number theory, 2 is often a special case in a lot of theorems. There's something odd about the even prime.
        xeonmc 3y ago
        i.e. the first information-encoding base.
        eru 3y ago
        I'm not sure. The Fibonacci numbering system has a smaller effective base. (And there's always unary.) See https://en.wikipedia.org/wiki/Fibonacci_coding https://en.wikipedia.org/wiki/Fibonacci_coding
        1propionyl 3y ago
        In analysis and its applications, the L^2 norm is also rather special.
  - jl6 3y ago
    “I’m a mathematician, not an arithmetician!”
  - keithalewis 3y ago
    There are three kinds of mathematicians...
    - globalnode 3y ago
      just looked that up, i like.
- cubefox 3y ago
  > He showed that the conjecture has a counterexample, which he estimated to be around 1.845 × 10361 1.845 × 10361 = 19116.045
  - messe 3y ago
    Thanks, it should be 10^361. I've fixed it.
- eru 3y ago
  > EDIT: rephrased because despite having a maths degree I can't count. You would probably enjoy Tom Körner's book 'The Pleasures of Counting'. See eg https://maa.org/press/maa-reviews/the-pleasures-of-counting https://maa.org/press/maa-reviews/the-pleasures-of-counting
senderista 3y ago
See also https://mathoverflow.net/questions/95865/examples-of-conjectures-that-were-widely-believed-to-be-true-but-later-proved-fa https://mathoverflow.net/questions/95865/examples-of-conject...
Shawnecy 3y ago
That reminds me of a parody song from 3Blue1Brown[0] about how certain numerical patterns don't quite hold and can fool you if you don't look far enough out. [0]: https://www.youtube.com/watch?v=NOCsdhzo6Jg https://www.youtube.com/watch?v=NOCsdhzo6Jg
SilasX 3y ago
Okay but the Collatz conjecture is a little different in that there can't just be a one-off counterexample: it's a statement about a sequence. The counterexample would have to be either a cycle (that excludes 4/2/1), or a sequence of numbers that keep spiraling up indefinitely. And they've proven that any cycle would have to be very long[1]. Either way, it would mean trivially unlocking a sequence of numbers that happens to satisfy a very specific criterion. [1] https://en.wikipedia.org/wiki/Collatz_conjecture?useskin=vector#Cycles https://en.wikipedia.org/wiki/Collatz_conjecture?useskin=vec...
- timeagain 3y ago
  Right. So there might be some set of numbers way out there that are like the “sporadic simple group(s)” of the collatz conjecture. Following the same rules as everyone else, you end up with something otherwise unclassifiable.
eutectic 3y ago
John Conway showed that if you generalise the coefficients of the Collatz conjecture then some instances are undecidable. So maybe there is no proof.
- cubefox 3y ago
  If it is "undecidable" this means there is no counterexample to the Collatz conjecture, since any counterexample would disprove it. But the Collatz conjecture does exactly state that there are no counterexamples. Which means: If it is undecidable, it is true. Which seems a bit paradoxical. If you can prove that the Collatz conjecture is undecidable, you would also prove that it has no counterexamples, and thus that it is true. Which would make it decidable -- contradiction. So this seems to prove that if the Collatz conjecture is undecidable, this fact is itself also undecidable.
  - dooglius 3y ago
    You missed the key part > if you generalise the coefficients The result appears to be https://gwern.net/doc/cs/computable/1972-conway.pdf https://gwern.net/doc/cs/computable/1972-conway.pdf if you want to read in detail
  - nickdrozd 3y ago
    > If it is undecidable, it is true. That is the case for something like Goldbach's Conjecture, which says that every even number > 2 is the sum of two primes. If it's false, then there is a counterexample, and it is easy to prove whether or not a given number is a counterexample (just loop over all pairs of smaller primes). But that is not the case for the Collatz Conjecture. A Collatz counterexample could be a number whose orbit loops back around. That would be a provable counterexample. Another kind of Collatz counterexample would be a number whose orbit never terminates or repeats, it just keeps going forever. If such an infinite sequence existed, it might not be possible to prove that it's infinite. And if it isn't provable, then the conjecture would both undecidable and false.
    - cubefox 3y ago
permo-w 3y ago
>Here I was naively thinking that if no counter examples were found in the first, say, 10^10 numbers, no counter examples should exist why on earth would you ever think that
- zimpenfish 3y ago
  > naively I think that answers your question?
  - permo-w 3y ago
    it's clear that the thought is naive, but that doesn't explain why it was come to
- deleted 3y ago
  [deleted]
- xanderlewis 3y ago
  Why do you assume the sun will rise tomorrow?
  - bryanrasmussen 3y ago
    I don't just assume, I have my bottom dollar riding on it!
  - permo-w 3y ago
    this analogy illustrates the opposite of what I think you intend it to. if we could artificially iterate the sun rising infinite times, somewhere very high up, maybe after 10^10, it eventually would no longer rise
    - xanderlewis 3y ago
      True, and that did occur to me as I was writing it. The point was more that any length of time greater than a few thousand years is as good as infinite for a human, so (for, you know, everyday purposes) we might as well assume that the sun will keep on rising forever.
pulisse 3y ago
There's a great Mathoverflow thread collecting examples of this sort of phenomenon (called "eventual counterexamples" in the thread), together with some interesting analysis (see Joel Hamkins' answer): https://mathoverflow.net/questions/15444/examples-of-eventual-counterexamples https://mathoverflow.net/questions/15444/examples-of-eventua...
Paul-Craft 3y ago
One of my favorite mathematical tangents involves a theorem of Littlewood. The prime number theorem states that the prime counting function $\pi(x)$ is well approximated by the integral $\int_0^x \frac{dt} {\log t},$ which is a function that's become named $\mathrm{li}(x).$ Littlewood proved that the sign of $\pi(x) - \li(x)$ changes infinitely often, but his proof didn't produce a specific value where such a sign change occurs. In 1933, one of Littlewood's students showed that, assuming the Riemann hypothesis, at least one sign change occurs below the number $e^e^e^79$, which is approximately $10^10^10^34.$ In 1955, he was able to show unconditionally that such a sign change occurs below the number $e^e^e^e^7.705$, which is approximately $10^10^10^964$. Both of those numbers absolutely dwarf the estimated number of elementary particles in the observable universe, so it's utterly impossible to either compute or write them down, even if you used the entire universe as your computer or your writing surface. https://en.wikipedia.org/wiki/Skewes%27s_number https://en.wikipedia.org/wiki/Skewes%27s_number That upper bound has since been lowered in 1999 to 1.38922 * 10^316 here: https://www.ams.org/journals/mcom/2000-69-231/S0025-5718-99-01104-7/S0025-5718-99-01104-7.pdf https://www.ams.org/journals/mcom/2000-69-231/S0025-5718-99-... I imagine it there might have been a bit more progress in the last 25 years, but I have no idea if it's possible to actually write down all the digits of the current best upper bound.
- BHSPitMonkey 3y ago
  > That upper bound has since been lowered in 1999 to 1.38922 * 10^316 here: ... > > but I have no idea if it's possible to actually write down all the digits of the current best upper bound. I'm probably missing something that should be obvious, but why wouldn't it be possible to write down 317 digits?
  - Paul-Craft 3y ago
    Lol, no, I had a brain fart. I was thinking it was 10^10^316. There might be a problem with actually calculating the 317 digits though. ¯\\\_(ツ)\_/¯ The wiki article on Skewes number also notes that the bound has been lowered to 1.397162×10^316 in 2011.
dclowd9901 3y ago
But that is true. According to the article you posted, a counter example _was_ found in less than 10^10
ozyschmozy 3y ago
Well in this case you weren't wrong about the first 10^10 numbers: > the smallest counterexample is n = 906,150,257, found by Minoru Tanaka in 1980.[5]

messe 3y ago

That's just the first counterexample that was proven to exist. The smallest counter example is less than 10^10 (in fact smaller than 10^9). > The Pólya conjecture was disproved by C. Brian Haselgrove in 1958. He showed that the conjecture has a counterexample, which he estimated to be around 1.845 × 10^361.[3] > An explicit counterexample, of n = 906,180,359 was given by R. Sherman Lehman in 1960;[4] the smallest counterexample is n = 906,150,257, found by Minoru Tanaka in 1980.[5] EDIT: rephrased because despite having a maths degree I can't count.

klysm 3y ago
I believe inability to do arithmetic correctly is more common in folks with maths and other STEM degrees
- messe 3y ago
  I do like to joke that I studied maths because I don't like numbers.
  - at_a_remove 3y ago
    I recall the end of a science fiction novel, wherein we finally meet aliens. It turns out that, as a trend, the species that are good at counting are bad at math and especially counting things at a glance. The species that is best at math have a hard time telling the difference between two things and three things just looking.
  - hinkley 3y ago
    I know a young man with dyscalculia and we were hoping when he got to symbolic math that his problems would diminish. That has not born fruit so far.
  - anthomtb 3y ago
    I pursued and achieved an EE degree plus a couple extra math courses largely because I was "not good at math" as a youth. Nothing like hearing "I don't think math is your subject" from a key adult to light a fire under ones fanny. In hindsight I could have had the same career path with a straight CS degree and much less stress during my college years. No regrets though, math really is fun! Even more so when the classroom setting is removed.
    - BrandoElFollito 3y ago
      When I was about 12yo, I went to the eye doctor with my father (in France). The doctor realized that I had daltonism and told my father in front of me that I would never be an engineer because of that. At school, we had tests to show what we were good at. The guy who came to comment on our tests told me that I should definitely go for something like literature or history. And here I am, an engineer with an extra PhD in physics who dreams about meeting these idiots and explaining to them that what they do is revolting. They are probably dead by now though (it was in the 80's)
      - tocs3 3y ago
        daltonism : color blindness Had to look it up.
- DavidSJ 3y ago
  It's one of the prerequisites in fact.
- susam 3y ago
  > I believe inability to do arithmetic correctly is more common in folks with maths and other STEM degrees Reminds me of a story from <https://www.ams.org/notices/200410/fea-grothendieck-part2.pdf https://www.ams.org/notices/200410/fea-grothendieck-part2.pd...>. Quoting it below: One striking characteristic of Grothendieck’s mode of thinking is that it seemed to rely so little on examples. This can be seen in the legend of the so-called “Grothendieck prime”. In a mathematical conversation, someone suggested to Grothendieck that they should consider a particular prime number. “You mean an actual number?” Grothendieck asked. The other person replied, yes, an actual prime number. Grothendieck suggested, “All right, take 57.”
  - 1propionyl 3y ago
    This is absolutely my personal experience. I am absolutely awful at arithmetic, but I think pretty competent at decently advanced mathematics. It's like they say: the only numbers a mathematician needs are 0, 1, and 2 (and just because it's not 1).
    - eru 3y ago
      In number theory, 2 is often a special case in a lot of theorems. There's something odd about the even prime.
      - xeonmc 3y ago
        i.e. the first information-encoding base.
        eru 3y ago
        I'm not sure. The Fibonacci numbering system has a smaller effective base. (And there's always unary.) See https://en.wikipedia.org/wiki/Fibonacci_coding https://en.wikipedia.org/wiki/Fibonacci_coding
      - 1propionyl 3y ago
        In analysis and its applications, the L^2 norm is also rather special.
- jl6 3y ago
  “I’m a mathematician, not an arithmetician!”
- keithalewis 3y ago
  There are three kinds of mathematicians...
  - globalnode 3y ago
    just looked that up, i like.
cubefox 3y ago
> He showed that the conjecture has a counterexample, which he estimated to be around 1.845 × 10361 1.845 × 10361 = 19116.045
- messe 3y ago
  Thanks, it should be 10^361. I've fixed it.
eru 3y ago
> EDIT: rephrased because despite having a maths degree I can't count. You would probably enjoy Tom Körner's book 'The Pleasures of Counting'. See eg https://maa.org/press/maa-reviews/the-pleasures-of-counting https://maa.org/press/maa-reviews/the-pleasures-of-counting

senderista 3y ago

See also https://mathoverflow.net/questions/95865/examples-of-conjectures-that-were-widely-believed-to-be-true-but-later-proved-fa https://mathoverflow.net/questions/95865/examples-of-conject...

Shawnecy 3y ago

That reminds me of a parody song from 3Blue1Brown[0] about how certain numerical patterns don't quite hold and can fool you if you don't look far enough out. [0]: https://www.youtube.com/watch?v=NOCsdhzo6Jg https://www.youtube.com/watch?v=NOCsdhzo6Jg

SilasX 3y ago

Okay but the Collatz conjecture is a little different in that there can't just be a one-off counterexample: it's a statement about a sequence. The counterexample would have to be either a cycle (that excludes 4/2/1), or a sequence of numbers that keep spiraling up indefinitely. And they've proven that any cycle would have to be very long[1]. Either way, it would mean trivially unlocking a sequence of numbers that happens to satisfy a very specific criterion. [1] https://en.wikipedia.org/wiki/Collatz_conjecture?useskin=vector#Cycles https://en.wikipedia.org/wiki/Collatz_conjecture?useskin=vec...

timeagain 3y ago
Right. So there might be some set of numbers way out there that are like the “sporadic simple group(s)” of the collatz conjecture. Following the same rules as everyone else, you end up with something otherwise unclassifiable.

eutectic 3y ago

John Conway showed that if you generalise the coefficients of the Collatz conjecture then some instances are undecidable. So maybe there is no proof.

cubefox 3y ago
If it is "undecidable" this means there is no counterexample to the Collatz conjecture, since any counterexample would disprove it. But the Collatz conjecture does exactly state that there are no counterexamples. Which means: If it is undecidable, it is true. Which seems a bit paradoxical. If you can prove that the Collatz conjecture is undecidable, you would also prove that it has no counterexamples, and thus that it is true. Which would make it decidable -- contradiction. So this seems to prove that if the Collatz conjecture is undecidable, this fact is itself also undecidable.
- dooglius 3y ago
  You missed the key part > if you generalise the coefficients The result appears to be https://gwern.net/doc/cs/computable/1972-conway.pdf https://gwern.net/doc/cs/computable/1972-conway.pdf if you want to read in detail
- nickdrozd 3y ago
  > If it is undecidable, it is true. That is the case for something like Goldbach's Conjecture, which says that every even number > 2 is the sum of two primes. If it's false, then there is a counterexample, and it is easy to prove whether or not a given number is a counterexample (just loop over all pairs of smaller primes). But that is not the case for the Collatz Conjecture. A Collatz counterexample could be a number whose orbit loops back around. That would be a provable counterexample. Another kind of Collatz counterexample would be a number whose orbit never terminates or repeats, it just keeps going forever. If such an infinite sequence existed, it might not be possible to prove that it's infinite. And if it isn't provable, then the conjecture would both undecidable and false.
  - cubefox 3y ago

permo-w 3y ago

>Here I was naively thinking that if no counter examples were found in the first, say, 10^10 numbers, no counter examples should exist why on earth would you ever think that

zimpenfish 3y ago
> naively I think that answers your question?
- permo-w 3y ago
  it's clear that the thought is naive, but that doesn't explain why it was come to
deleted 3y ago
[deleted]
xanderlewis 3y ago
Why do you assume the sun will rise tomorrow?
- bryanrasmussen 3y ago
  I don't just assume, I have my bottom dollar riding on it!
- permo-w 3y ago
  this analogy illustrates the opposite of what I think you intend it to. if we could artificially iterate the sun rising infinite times, somewhere very high up, maybe after 10^10, it eventually would no longer rise
  - xanderlewis 3y ago
    True, and that did occur to me as I was writing it. The point was more that any length of time greater than a few thousand years is as good as infinite for a human, so (for, you know, everyday purposes) we might as well assume that the sun will keep on rising forever.

pulisse 3y ago

There's a great Mathoverflow thread collecting examples of this sort of phenomenon (called "eventual counterexamples" in the thread), together with some interesting analysis (see Joel Hamkins' answer): https://mathoverflow.net/questions/15444/examples-of-eventual-counterexamples https://mathoverflow.net/questions/15444/examples-of-eventua...

Paul-Craft 3y ago

One of my favorite mathematical tangents involves a theorem of Littlewood. The prime number theorem states that the prime counting function $\pi(x)$ is well approximated by the integral $\int_0^x \frac{dt} {\log t},$ which is a function that's become named $\mathrm{li}(x).$ Littlewood proved that the sign of $\pi(x) - \li(x)$ changes infinitely often, but his proof didn't produce a specific value where such a sign change occurs. In 1933, one of Littlewood's students showed that, assuming the Riemann hypothesis, at least one sign change occurs below the number $e^e^e^79$, which is approximately $10^10^10^34.$ In 1955, he was able to show unconditionally that such a sign change occurs below the number $e^e^e^e^7.705$, which is approximately $10^10^10^964$. Both of those numbers absolutely dwarf the estimated number of elementary particles in the observable universe, so it's utterly impossible to either compute or write them down, even if you used the entire universe as your computer or your writing surface. https://en.wikipedia.org/wiki/Skewes%27s_number https://en.wikipedia.org/wiki/Skewes%27s_number That upper bound has since been lowered in 1999 to 1.38922 * 10^316 here: https://www.ams.org/journals/mcom/2000-69-231/S0025-5718-99-01104-7/S0025-5718-99-01104-7.pdf https://www.ams.org/journals/mcom/2000-69-231/S0025-5718-99-... I imagine it there might have been a bit more progress in the last 25 years, but I have no idea if it's possible to actually write down all the digits of the current best upper bound.

BHSPitMonkey 3y ago
> That upper bound has since been lowered in 1999 to 1.38922 * 10^316 here: ... > > but I have no idea if it's possible to actually write down all the digits of the current best upper bound. I'm probably missing something that should be obvious, but why wouldn't it be possible to write down 317 digits?
- Paul-Craft 3y ago
  Lol, no, I had a brain fart. I was thinking it was 10^10^316. There might be a problem with actually calculating the 317 digits though. ¯\\\_(ツ)\_/¯ The wiki article on Skewes number also notes that the bound has been lowered to 1.397162×10^316 in 2011.

dclowd9901 3y ago

But that is true. According to the article you posted, a counter example _was_ found in less than 10^10

ozyschmozy 3y ago

Well in this case you weren't wrong about the first 10^10 numbers: > the smallest counterexample is n = 906,150,257, found by Minoru Tanaka in 1980.[5]