4 ms·

> Tao used this weighting technique to prove that almost all Collatz starting values — 99% or more — eventually reach a value that is quite close to 1. This all

> Tao used this weighting technique to prove that almost all Collatz starting values — 99% or more — eventually reach a value that is quite close to 1. This allowed him to draw conclusions along the lines of 99% of starting values greater than 1 quadrillion eventually reach a value below 200. If they reach a value below 200 then they surely will reach 1 (since all sub 200 sequences have been brute forced). What am I missing?

pclmulqdq 4y ago
What you're missing is that "99% or more" is not 100%. Tao's technique does not preclude the existence of a small cycle of large numbers that never get below 200 (or rather, below 2^64, since we have tried all of those).
- drexlspivey 4y ago
  I am commenting on the fact that these two statements are equivalent: * This allowed him to draw conclusions along the lines of 99% of starting values greater than 1 quadrillion eventually reach a value below 200. * This allowed him to draw conclusions along the lines of 99% of starting values greater than 1 quadrillion eventually reach 1. yet the author used the first which seems weird
  - pclmulqdq 4y ago
    The paper's "200" comes from plugging "1 quadrillion" into Terence Tao's new theorem directly, and not applying any other results. I think they wanted to communicate only the meaning of the theorem, not the context around it.
- FartyMcFarter 4y ago
  At some point I considered doing a computational search for cycles (perhaps using a SAT solver or something similar), but then I found this on Wikipedia: > The length of a non-trivial cycle is known to be at least 186265759595. This probably makes it very hard to find a cycle unless we know of some properties of the numbers involved in the cycle.
  - pclmulqdq 4y ago
    I went down the same line of thought as you when this problem nerd sniped me 5 years ago (and periodically over the last 5 years). I actually now think you may be able to do a computer proof that there are no trivial cycles other than 1 with a clever construction of large integers that lets you consider them in chunks, but I don't think there's any chance of finding a cycle with computation absent some weird number theory. Edit: The cycle length seems to have gotten longer since I last checked.
    - jiggawatts 4y ago
      The last time I wasted some time on this I had a similar notion: "start big" with numbers on the order of 1 million bits and try and demonstrate that different sections of those bits (prefix,middle,suffix) change according to some pattern that can then be generalised "down" to just 64 bits, which has been manually tested.
  - resource0x 4y ago
    Common sense suggests that the length of the cycle can be greater than any chosen N. The algorithm alternates between 2 steps: multiplication by 3 +1 followed by division by a power of 2 (equal to the number of trailing 0 bits; on average it divides by 4), etc. (So on average you multiply by 3, but divide by 4.) This argument simultanesouly 1) motivates the claim of the conjecture 2) predicts that the cycle length is unlimited (but always finite).
    - kccqzy 4y ago
      That's neither common sense nor mathematically correct.
      - feoren 4y ago
        Take a random[1] odd[2] number and represent it in binary. Its lowest bit is 1. Multiply by 3. The first bit is 1, but the rest have a 50% chance of being 0 and a 50% chance of being 1[3]. Adding 1 (the rest of the 3n+1 step) will flip a sequence like [0111] to [1000]. The number will then be divided by 2^k, where k is the number of trailing zeroes. How many trailing zeroes do we expect? We always start with one. There's a 50% chance the next one will be 0, and if it is, another 50% chance the next one will be, etc. So the average is 1 + 1/2 + 1/4 + 1/8 + 1/16 + ... = 2 trailing zeroes. Dividing off two zeroes in binary is the same as dividing the number by 4. So on average, we multiply a "random" odd number by 3, but divide it by 4. So yes, it is "mathematically correct" in a very real sense. It's a bit weird that you felt the need to claim it's incorrect, without explaining why. [1] Think of grouping the integers based on how many bits they take up. We're looking at patterns like [1----1] where each "-" has a 50/50 chance of being 0 or 1. For any given window size, this analysis holds, except for a small number of very pathological edge cases that become vanishingly unlikely for even modest window sizes. [2] It's common to consider each step only applying to odd numbers, and always dividing until the result is odd again. It's clear that any analysis on this "simplified" version trivially extends to the evens as well. [3] This shouldn't actually be taken as a given, since we've modified our original bit distribution by multiplying by 3, but it is true, which you'd probably agree with if you played around for a bit with multiplying random bits by 3. You can figure out the distributions of the resulting bits (include the carry bit as well). The highest bit can be wonky, but the probability that the run of zeroes reaches the highest bit vanishes as the window size grows.
tmhn2 4y ago
I don't think it's correct as stated in the article. Looking at the paper, it basically says: the orbit starting with N dips to f(N) for "most" N, where f is a function that goes to infinity. So, you can't pick f(N) = 200, but you can at least pick an f(N) that goes to infinity really slowly--a lot more slowly than previous results (f(N) = ~N^0.7924 is mentioned as a previous result).

pclmulqdq 4y ago

What you're missing is that "99% or more" is not 100%. Tao's technique does not preclude the existence of a small cycle of large numbers that never get below 200 (or rather, below 2^64, since we have tried all of those).

drexlspivey 4y ago
I am commenting on the fact that these two statements are equivalent: * This allowed him to draw conclusions along the lines of 99% of starting values greater than 1 quadrillion eventually reach a value below 200. * This allowed him to draw conclusions along the lines of 99% of starting values greater than 1 quadrillion eventually reach 1. yet the author used the first which seems weird
- pclmulqdq 4y ago
  The paper's "200" comes from plugging "1 quadrillion" into Terence Tao's new theorem directly, and not applying any other results. I think they wanted to communicate only the meaning of the theorem, not the context around it.
FartyMcFarter 4y ago
At some point I considered doing a computational search for cycles (perhaps using a SAT solver or something similar), but then I found this on Wikipedia: > The length of a non-trivial cycle is known to be at least 186265759595. This probably makes it very hard to find a cycle unless we know of some properties of the numbers involved in the cycle.
- pclmulqdq 4y ago
  I went down the same line of thought as you when this problem nerd sniped me 5 years ago (and periodically over the last 5 years). I actually now think you may be able to do a computer proof that there are no trivial cycles other than 1 with a clever construction of large integers that lets you consider them in chunks, but I don't think there's any chance of finding a cycle with computation absent some weird number theory. Edit: The cycle length seems to have gotten longer since I last checked.
  - jiggawatts 4y ago
    The last time I wasted some time on this I had a similar notion: "start big" with numbers on the order of 1 million bits and try and demonstrate that different sections of those bits (prefix,middle,suffix) change according to some pattern that can then be generalised "down" to just 64 bits, which has been manually tested.
- resource0x 4y ago
  Common sense suggests that the length of the cycle can be greater than any chosen N. The algorithm alternates between 2 steps: multiplication by 3 +1 followed by division by a power of 2 (equal to the number of trailing 0 bits; on average it divides by 4), etc. (So on average you multiply by 3, but divide by 4.) This argument simultanesouly 1) motivates the claim of the conjecture 2) predicts that the cycle length is unlimited (but always finite).
  - kccqzy 4y ago
    That's neither common sense nor mathematically correct.
    - feoren 4y ago
      Take a random[1] odd[2] number and represent it in binary. Its lowest bit is 1. Multiply by 3. The first bit is 1, but the rest have a 50% chance of being 0 and a 50% chance of being 1[3]. Adding 1 (the rest of the 3n+1 step) will flip a sequence like [0111] to [1000]. The number will then be divided by 2^k, where k is the number of trailing zeroes. How many trailing zeroes do we expect? We always start with one. There's a 50% chance the next one will be 0, and if it is, another 50% chance the next one will be, etc. So the average is 1 + 1/2 + 1/4 + 1/8 + 1/16 + ... = 2 trailing zeroes. Dividing off two zeroes in binary is the same as dividing the number by 4. So on average, we multiply a "random" odd number by 3, but divide it by 4. So yes, it is "mathematically correct" in a very real sense. It's a bit weird that you felt the need to claim it's incorrect, without explaining why. [1] Think of grouping the integers based on how many bits they take up. We're looking at patterns like [1----1] where each "-" has a 50/50 chance of being 0 or 1. For any given window size, this analysis holds, except for a small number of very pathological edge cases that become vanishingly unlikely for even modest window sizes. [2] It's common to consider each step only applying to odd numbers, and always dividing until the result is odd again. It's clear that any analysis on this "simplified" version trivially extends to the evens as well. [3] This shouldn't actually be taken as a given, since we've modified our original bit distribution by multiplying by 3, but it is true, which you'd probably agree with if you played around for a bit with multiplying random bits by 3. You can figure out the distributions of the resulting bits (include the carry bit as well). The highest bit can be wonky, but the probability that the run of zeroes reaches the highest bit vanishes as the window size grows.

tmhn2 4y ago

I don't think it's correct as stated in the article. Looking at the paper, it basically says: the orbit starting with N dips to f(N) for "most" N, where f is a function that goes to infinity. So, you can't pick f(N) = 200, but you can at least pick an f(N) that goes to infinity really slowly--a lot more slowly than previous results (f(N) = ~N^0.7924 is mentioned as a previous result).