5 ms·

I have a proof, would love HN’s perspective. A cycle means the product of all of the increases (each of which is a scaling factor of 3x+1 / x) equal the produc

I have a proof, would love HN’s perspective. A cycle means the product of all of the increases (each of which is a scaling factor of 3x+1 / x) equal the product of the decreases (a power of 2). 3x+1 / x = 3 + 1/x, so except for trivially small x, each increase is just a bit larger than 3. The product of those increases is a small amount larger than a power of 3, and has to exactly equal a power of 2. Larger cycles allow that little error above a power of 3 to compound, but larger cycles also necessitate larger values of x, which shrink the error.

eru 4y ago
That sounds like a heuristic, probabilistic argument for why we expect the conjecture to hold, but it doesn't seem like an airtight proof. (Not even a sketch of a proof.)
- dankearney 4y ago
  It’s not probabilistic — for any cycle length, you can compute the minimum possible x value that could possibly be the lowest odd number in the cycle. That value trends smaller as the cycle length grows.
  - eru 4y ago
    Sorry, I still don't get it. Could you explain it with fewer steps left out? To be honest, I doubt that you will have come up with something that Terrence Tao and other geniuses haven't, but it's interesting to figure out exactly where you went wrong. (Or, on the off chance, seeing how you might be right after all.)
    - dankearney 4y ago
      Yes and thanks for giving me the time of day! 1: Derive that, for a cycle with o odds and e evens, that the product of the increases due to odds (3 + 1/x) must exactly equal the product of the decreases by halving, which comes out to 2^e. The trivial cycle meets this, since (3+1/1) = 2^2. As another example, for the alternative rule where odd numbers go up by 3*n + 5, there are some cycles, like 19 => 62 => 31 => 98 => 49 => 152 => 76 => 38 => 19. The increases here come out to approximately 3.26, 3.16, and 3.10, the product of which is exactly 32, or 2^5. 2: Observe that each (3 + 1/x) term (except for trivially small x) is greater than 3, but near it. For x=101, (3+1/x) is about 3.01. As a result, the product of the increases is going to be larger than a product of 3, but somewhat close to one. 3: Observe that we need the little error above the power of 3 to be large enough that the LHS exactly equals a power of 2. This is challenging because as the numbers in the cycle get larger, (3 + 1/x) gets closer to 3.0, which makes it harder for the product to be much larger than a power of 3. And, for large powers of 3, the nearest power of 2 is never particularly close — we actually need this error to compound to a product substantially larger than the power of 3. We can attempt to achieve this with longer cycles for more compounding error, or smaller values of x. 4: Observe that, for a given number of odd numbers in a cycle, we can find an upper bound for the lowest value in the cycle. For example, let’s use o=5. We need (3+1/x1)(3+1/x2)(3+1/x3)(3+1/x4)(3+1/x5) = 2^e. 3^5 is 243, so the easiest e value is 8, making the RHS 256. If we define x1 as the smallest number in the cycle, we can see that x1 can’t be too large. x1=1001 implies that x2, x3 etc are at least 1003 and 1005 etc. Plugging these in, the LHS is 243.4 — not near 256. And making x2, x3 etc larger only makes it worse. Okay, so try a smaller x1 - you can compute that the largest possible x1 that can possibly make the LHS equal 256 is 31. However we know that 31 and every number below it does not have a cycle, so we know there are no cycles of length 5. We can actually define the RHS as the next power of 2 above 3^o, which is floor(log2(3^o))+1. 5: Repeat this process for larger cycle lengths and you see that the largest viable value does not trend larger, it trends smaller.
      - topaz0 4y ago
        > harder for the product to be much larger than a power of 3 Unfortunately plenty of things that are hard to do still exist. Take primes for example: every time you pass another prime there are more primes that could be factors of larger numbers, so it must be harder and harder for large numbers to be prime. Somehow they still manage. Edit: I just quickly ran your prod(3 + 1/x) for x in {1001,1003,...,1001 + 2n} for various values of n, and empirically they are indistinguishable from uniformly distributed between powers of two on a log scale. You're going to need a better argument than "it's hard to hit a power of two with a product of (3 + 1/x)". Edit 2: (re your point 4) your floor(log2(3^n)) + 1 also seems to be an incorrect upper bound: many of the products I calculated for my first edit are above it. Edit 3: Even if that upper bound did hold, your point 5 doesn't stand up to a quick test: I followed your method for loop lengths up to 1000, and the upper bounds on x_1 bounce around a lot but tend to grow.
        dankearney 4y ago
        Poor choice of words perhaps, but the further parts explain
        topaz0 4y ago
        See my edits for more substantive points, but more generally it is really useful to formalize your argument. Once you do that, it is much easier to see what parts of the argument are on a firm footing, and which ones are inadequately justified. Lots of plausible-sounding sentences about math turn out to be wrong.
        dankearney 4y ago
        Wow, thanks for the deep dive! This is so fascinating that someone would be willing to dive into my ideas. HN rules. I clearly need a much more clear explanation of things — for example the floor(log2(( part is being misinterpreted here. Thanks for diving in and giving me pointers
justinpombrio 4y ago
That doesn't sound complete, are there steps you haven't written out? You've given some true facts about cycles. Why does your observation about Collatz cycles imply the Collatz conjecture, which is that every sequence is part of a cycle?
- dankearney 4y ago
  I’m proving that there are no cycles above the trivial cycle with this, and yeah this post is just a quick summary
  - deleted 4y ago
    [deleted]
  - justinpombrio 4y ago
    It wasn't enough detail to spot the error in the proof.
    - dankearney 4y ago
      I’m going to polish it up and will share with you, I explained to it eru in more detail
deleted 4y ago
[deleted]
LegionMammal978 4y ago
Looking at the alleged proof on your GitHub page (https://github.com/dankearney/collatz/blob/2dd21babd5fbced73565cf1fba24db8198ae5099/Finding_Cycles.md https://github.com/dankearney/collatz/blob/2dd21babd5fbced73...): > As the cycles get longer, the nearest power of 2 actually trends further away. Why? https://mathoverflow.net/a/116960 https://mathoverflow.net/a/116960 explains this nicely -- powers of 2 and 3 cannot be close to one another as powers get larger. We need a power of 2 to be close to a power of 3, but that is not possible. You misinterpreted the MathOverflow answer. Quoting its result, "At least half of the powers of 2, in a density sense, have a distance from the powers of three of at least one fifth of their size." Notice that it does not set any bound that applies to all powers of 2. Therefore, your assertion remains unproven. For an explicit counterexample, let's take your n = 1000000001. Let e = 10439860591 and o = 6586818670. Then, 2^e ≈ 3^o + 2.796·10^3142711177, but (3 + 1/n)^o ≈ 3^o + 2.206·10^3142711189. Therefore, 3^o ≤ 2^e ≤ (3 + 1/n)^o, contrary to the strong form of your assertion. Also, you have not proven the nonexistence of sequences which diverge to infinity.
- kevinwang 4y ago
  Right. The theory that the parent came up with does seem like a good idea. However, you can't really expect to have been the first one to come up with this for a problem with as many iq-eyeball-hours as the collatz. Indeed, some googling suggests that this approach of matching powers of 2s and powers of 3s is one existing path for collatz adventurers: https://terrytao.wordpress.com/2011/08/25/the-collatz-conjecture-littlewood-offord-theory-and-powers-of-2-and-3/ https://terrytao.wordpress.com/2011/08/25/the-collatz-conjec... Although I don't understand it, a skim of that Terry Tao post suggests that if the statement about powers of 2 and 3 getting getting farther apart is actually true, it would be a big step towards proving the (weak) collatz.
  - LegionMammal978 4y ago
    Unfortunately, the true property of getting farther apart would have to be more sophisticated than the version the parent used. You can easily find powers of 2 and 3 arbitrarily close on the logarithmic scale by generating the convergents of log 2/log 3.

eru 4y ago

That sounds like a heuristic, probabilistic argument for why we expect the conjecture to hold, but it doesn't seem like an airtight proof. (Not even a sketch of a proof.)

dankearney 4y ago
It’s not probabilistic — for any cycle length, you can compute the minimum possible x value that could possibly be the lowest odd number in the cycle. That value trends smaller as the cycle length grows.
- eru 4y ago
  Sorry, I still don't get it. Could you explain it with fewer steps left out? To be honest, I doubt that you will have come up with something that Terrence Tao and other geniuses haven't, but it's interesting to figure out exactly where you went wrong. (Or, on the off chance, seeing how you might be right after all.)
  - dankearney 4y ago
    Yes and thanks for giving me the time of day! 1: Derive that, for a cycle with o odds and e evens, that the product of the increases due to odds (3 + 1/x) must exactly equal the product of the decreases by halving, which comes out to 2^e. The trivial cycle meets this, since (3+1/1) = 2^2. As another example, for the alternative rule where odd numbers go up by 3*n + 5, there are some cycles, like 19 => 62 => 31 => 98 => 49 => 152 => 76 => 38 => 19. The increases here come out to approximately 3.26, 3.16, and 3.10, the product of which is exactly 32, or 2^5. 2: Observe that each (3 + 1/x) term (except for trivially small x) is greater than 3, but near it. For x=101, (3+1/x) is about 3.01. As a result, the product of the increases is going to be larger than a product of 3, but somewhat close to one. 3: Observe that we need the little error above the power of 3 to be large enough that the LHS exactly equals a power of 2. This is challenging because as the numbers in the cycle get larger, (3 + 1/x) gets closer to 3.0, which makes it harder for the product to be much larger than a power of 3. And, for large powers of 3, the nearest power of 2 is never particularly close — we actually need this error to compound to a product substantially larger than the power of 3. We can attempt to achieve this with longer cycles for more compounding error, or smaller values of x. 4: Observe that, for a given number of odd numbers in a cycle, we can find an upper bound for the lowest value in the cycle. For example, let’s use o=5. We need (3+1/x1)(3+1/x2)(3+1/x3)(3+1/x4)(3+1/x5) = 2^e. 3^5 is 243, so the easiest e value is 8, making the RHS 256. If we define x1 as the smallest number in the cycle, we can see that x1 can’t be too large. x1=1001 implies that x2, x3 etc are at least 1003 and 1005 etc. Plugging these in, the LHS is 243.4 — not near 256. And making x2, x3 etc larger only makes it worse. Okay, so try a smaller x1 - you can compute that the largest possible x1 that can possibly make the LHS equal 256 is 31. However we know that 31 and every number below it does not have a cycle, so we know there are no cycles of length 5. We can actually define the RHS as the next power of 2 above 3^o, which is floor(log2(3^o))+1. 5: Repeat this process for larger cycle lengths and you see that the largest viable value does not trend larger, it trends smaller.
    - topaz0 4y ago
      > harder for the product to be much larger than a power of 3 Unfortunately plenty of things that are hard to do still exist. Take primes for example: every time you pass another prime there are more primes that could be factors of larger numbers, so it must be harder and harder for large numbers to be prime. Somehow they still manage. Edit: I just quickly ran your prod(3 + 1/x) for x in {1001,1003,...,1001 + 2n} for various values of n, and empirically they are indistinguishable from uniformly distributed between powers of two on a log scale. You're going to need a better argument than "it's hard to hit a power of two with a product of (3 + 1/x)". Edit 2: (re your point 4) your floor(log2(3^n)) + 1 also seems to be an incorrect upper bound: many of the products I calculated for my first edit are above it. Edit 3: Even if that upper bound did hold, your point 5 doesn't stand up to a quick test: I followed your method for loop lengths up to 1000, and the upper bounds on x_1 bounce around a lot but tend to grow.
      - dankearney 4y ago
        Poor choice of words perhaps, but the further parts explain
        topaz0 4y ago
        See my edits for more substantive points, but more generally it is really useful to formalize your argument. Once you do that, it is much easier to see what parts of the argument are on a firm footing, and which ones are inadequately justified. Lots of plausible-sounding sentences about math turn out to be wrong.
        dankearney 4y ago
        Wow, thanks for the deep dive! This is so fascinating that someone would be willing to dive into my ideas. HN rules. I clearly need a much more clear explanation of things — for example the floor(log2(( part is being misinterpreted here. Thanks for diving in and giving me pointers

justinpombrio 4y ago

That doesn't sound complete, are there steps you haven't written out? You've given some true facts about cycles. Why does your observation about Collatz cycles imply the Collatz conjecture, which is that every sequence is part of a cycle?

dankearney 4y ago
I’m proving that there are no cycles above the trivial cycle with this, and yeah this post is just a quick summary
- deleted 4y ago
  [deleted]
- justinpombrio 4y ago
  It wasn't enough detail to spot the error in the proof.
  - dankearney 4y ago
    I’m going to polish it up and will share with you, I explained to it eru in more detail

deleted 4y ago

[deleted]

LegionMammal978 4y ago

Looking at the alleged proof on your GitHub page (https://github.com/dankearney/collatz/blob/2dd21babd5fbced73565cf1fba24db8198ae5099/Finding_Cycles.md https://github.com/dankearney/collatz/blob/2dd21babd5fbced73...): > As the cycles get longer, the nearest power of 2 actually trends further away. Why? https://mathoverflow.net/a/116960 https://mathoverflow.net/a/116960 explains this nicely -- powers of 2 and 3 cannot be close to one another as powers get larger. We need a power of 2 to be close to a power of 3, but that is not possible. You misinterpreted the MathOverflow answer. Quoting its result, "At least half of the powers of 2, in a density sense, have a distance from the powers of three of at least one fifth of their size." Notice that it does not set any bound that applies to all powers of 2. Therefore, your assertion remains unproven. For an explicit counterexample, let's take your n = 1000000001. Let e = 10439860591 and o = 6586818670. Then, 2^e ≈ 3^o + 2.796·10^3142711177, but (3 + 1/n)^o ≈ 3^o + 2.206·10^3142711189. Therefore, 3^o ≤ 2^e ≤ (3 + 1/n)^o, contrary to the strong form of your assertion. Also, you have not proven the nonexistence of sequences which diverge to infinity.

kevinwang 4y ago
Right. The theory that the parent came up with does seem like a good idea. However, you can't really expect to have been the first one to come up with this for a problem with as many iq-eyeball-hours as the collatz. Indeed, some googling suggests that this approach of matching powers of 2s and powers of 3s is one existing path for collatz adventurers: https://terrytao.wordpress.com/2011/08/25/the-collatz-conjecture-littlewood-offord-theory-and-powers-of-2-and-3/ https://terrytao.wordpress.com/2011/08/25/the-collatz-conjec... Although I don't understand it, a skim of that Terry Tao post suggests that if the statement about powers of 2 and 3 getting getting farther apart is actually true, it would be a big step towards proving the (weak) collatz.
- LegionMammal978 4y ago
  Unfortunately, the true property of getting farther apart would have to be more sophisticated than the version the parent used. You can easily find powers of 2 and 3 arbitrarily close on the logarithmic scale by generating the convergents of log 2/log 3.