Collatz Conjecture: No Cycle: A One-Page Proof
Update Aug 2, 2010: Step #7 is wrong. I have found an error in my argument which invalidates the proof.
This is meant to be a one-page proof based on my longer argument that I posted before. This one-pager attempts to show that there cannot be a cycle in a Collatz Sequence that does not include 1.
Claim: A Collatz Sequence does not have cycles that do not include 1.
1. Assume that a Collatz sequence has a cycle of length n.
2. If we only consider the odd integers in this sequence, we can characterize this sequence by two sets of positive integers:
x0, x1, ..., xn
p1, p2, ..., pn
where for each xi:
xi = (1/2pi)*(3xi-1 + 1)
so, from the above, we can see the following:
(a) Each xi is odd
(b) x0 = xn [since it is a cycle of length n]
Further, we can also see that x1 = xn+1, ..., xn-1 = x2n-1
(c) Each pi ≥ 1 [since xi-1 is odd, it follows that 3xi-1 + 1 is even.]
3. Since the purpose is to show that all cycles must include 1, I will assume that each xi ≥ 3 and show that this leads to a contradiction.
4. I can show that p1 + ... + pn is less than 2n. [see Corollary 9.2, here for the argument]
5. This gives us an interesting relationship, it means that:
This follows directly from step #4. Assume that this wasn't true.
Let a = # of 1's
Let b = # of 2's
Let c = # of pi that are greater than 2.
Let d = sum of (pi - 2) for all pi ≥ 3
So, we have: 2n = 2a + 2b + 2c
If we assume the relationship above is not true, then d ≥ a.
Now, using our definitions above:
p1 + p2 + ... + pn = a + 2b + 2c + d
But if d ≥ a, then it follows that p1 + p2 + ... + pn = 2n which goes against step #4.
6. I can also show that for each pi = 1, a value in the cycle that corresponds to pi+n-1 which for purposes of this proof, I will call "pi+n-1" [each pi must repeat since each xi after x0 will itself form a cycle of length n].
7. For every pi = 1, pj = 1 where i ≠ j, it follows that abs(pi+n-1 - pj+n-1) ≥ 3. [See Corollary 12.3, Theorem 13, and Corollary 13.1, here]
8. The result in step #7 gives us the following relationship:
Let a = the number of pi that are equal to 1
sum(pi ≥ 3 - 2) = (1 - 1) + (1 + 3 - 2) + (1 + 3 + 3 - 2) + ... + (1 + [a-1]*3 - [a-1]*2)
where each term in the parentheses is one of the pi+n-1 values that must be 3 greater than all others pj+n-1 values. The first term is (1-1) because 1 of these values can be 1 and we are not counting it since it is not greater than 2.
Using the summation formula, where: 1 + 2 + 3 + ... + (a-1) = (1/2)(a-1)(a), we get the following value for the sum:
sum(pi ≥3 - 2) = (a-1)*1 + (1/2)(a-1)(a)*3 - (a-1)*2
9. Combining step #5 and step #8, gives us:
Let a = the number of pi that are equal to 1
Then:
(a-1) ≥ (a-1)*1 + (1/2)(a-1)(a)*3 - (a-1)*2
But this is only true if a ≤ 1. [See Theorem 16, here, for my reasoning about the above equation]
10. Here lies the contradiction because I can further show that there are at least two pi that are equal to 1. [see Corollary 11.1, here]
QED
This is meant to be a one-page proof based on my longer argument that I posted before. This one-pager attempts to show that there cannot be a cycle in a Collatz Sequence that does not include 1.
Claim: A Collatz Sequence does not have cycles that do not include 1.
1. Assume that a Collatz sequence has a cycle of length n.
2. If we only consider the odd integers in this sequence, we can characterize this sequence by two sets of positive integers:
x0, x1, ..., xn
p1, p2, ..., pn
where for each xi:
xi = (1/2pi)*(3xi-1 + 1)
so, from the above, we can see the following:
(a) Each xi is odd
(b) x0 = xn [since it is a cycle of length n]
Further, we can also see that x1 = xn+1, ..., xn-1 = x2n-1
(c) Each pi ≥ 1 [since xi-1 is odd, it follows that 3xi-1 + 1 is even.]
3. Since the purpose is to show that all cycles must include 1, I will assume that each xi ≥ 3 and show that this leads to a contradiction.
4. I can show that p1 + ... + pn is less than 2n. [see Corollary 9.2, here for the argument]
5. This gives us an interesting relationship, it means that:
This follows directly from step #4. Assume that this wasn't true.
Let a = # of 1's
Let b = # of 2's
Let c = # of pi that are greater than 2.
Let d = sum of (pi - 2) for all pi ≥ 3
So, we have: 2n = 2a + 2b + 2c
If we assume the relationship above is not true, then d ≥ a.
Now, using our definitions above:
p1 + p2 + ... + pn = a + 2b + 2c + d
But if d ≥ a, then it follows that p1 + p2 + ... + pn = 2n which goes against step #4.
6. I can also show that for each pi = 1, a value in the cycle that corresponds to pi+n-1 which for purposes of this proof, I will call "pi+n-1" [each pi must repeat since each xi after x0 will itself form a cycle of length n].
7. For every pi = 1, pj = 1 where i ≠ j, it follows that abs(pi+n-1 - pj+n-1) ≥ 3. [See Corollary 12.3, Theorem 13, and Corollary 13.1, here]
8. The result in step #7 gives us the following relationship:
Let a = the number of pi that are equal to 1
sum(pi ≥ 3 - 2) = (1 - 1) + (1 + 3 - 2) + (1 + 3 + 3 - 2) + ... + (1 + [a-1]*3 - [a-1]*2)
where each term in the parentheses is one of the pi+n-1 values that must be 3 greater than all others pj+n-1 values. The first term is (1-1) because 1 of these values can be 1 and we are not counting it since it is not greater than 2.
Using the summation formula, where: 1 + 2 + 3 + ... + (a-1) = (1/2)(a-1)(a), we get the following value for the sum:
sum(pi ≥3 - 2) = (a-1)*1 + (1/2)(a-1)(a)*3 - (a-1)*2
9. Combining step #5 and step #8, gives us:
Let a = the number of pi that are equal to 1
Then:
(a-1) ≥ (a-1)*1 + (1/2)(a-1)(a)*3 - (a-1)*2
But this is only true if a ≤ 1. [See Theorem 16, here, for my reasoning about the above equation]
10. Here lies the contradiction because I can further show that there are at least two pi that are equal to 1. [see Corollary 11.1, here]
QED
posted by Larry Freeman at 10:54 PM
0 comments
