Is this a proof of the Collatz Conjecture?

[elcaro]

TL;DR

The Collatz Conjecture is that for any integer N (N > 0) the sequence formed by:
- Multiplying by 3 and add 1, if N is odd
- Dividing by 2 if N is even
always converges to the sequence ... 4, 2, 1.

Note as soon as the term 3N+1 become divisible by a power of 2 we can repeatedly divide by 2.

For the proof below we rearrange the sequence so it becomes:

First step:
If N is odd, multiply by 3 and add 1.

Each next step:
- Repeatedly divide by 2, as many times as the number k, which is defined as the largest number for which N is divisable by 2^k. Note that k is at least 1, and the resulting number is always odd.
- Muliply by 3 and add 1

What is the chance for a value of k greater then 0?

k chance 3N+1 is divisable by 2^k
-- ---------
1 1
2 1/2
3 1/4
4 1/8

or for any k, the chance is 1/2^k-1

The sequence we can then redefine as (3N+1)/2^k.

If we calculate the average factor for each step defined above, as the sum of the series 1/2+1/4+1/8+... is 1, this factor converges to (3N+1)/2¹⁺¹ = (3N+1)/4, which is smaller then N. So on average, each step will yield a smaller number.

Hence, the sequence must always converge to 1.

 

[Mark44]

I don't think you have a proof. Certainly, for a given N > 0, once the sequence reaches some power of 2, then repeated division by 2 will eventually reduce to 1, but for some values of N, how can you guarantee that the "orbit" will eventually produce a power of 2? For example, N = 97 takes 118 steps to reach 1.

For more info, see https://en.wikipedia.org/wiki/Collatz_conjecture.

 

[elcaro]

Well first, the chance of 3N+1 being divisible by some power of 2 is exactly 1, as 3N+1 always yields an even number, or stated differently, the chance of 3N+1 being divisible by 2^k has a chance of:

k= 1: 1
k = 2: 1/2
k = 3: 1/4

or, this chance can be expressed as 1/2^k-1.

Note that the sequence does not necessarily reach a power of 2, it is stated only that 3N+1 will produce a number that is divisable by a power of 2, and that the expression 3N+1 does so on the basis of the chance distribution given above. What might be missing in my proof is the proof that 3N+1 indeed reaches a number divisible by a power of 2 with a distribution for k as given above. But I think that is easily proven.

The proof that the sequence will eventually reaches 1 is given by the fact that the average factor (this factor is the product of (3N+1)/2^k) converges to (3N+1)/4, which is smaller then the initial number N, so in the end the sequence will converge to 1.

 

[elcaro]

I don't think you have a proof. Certainly, for a given N > 0, once the sequence reaches some power of 2, then repeated division by 2 will eventually reduce to 1, but for some values of N, how can you guarantee that the "orbit" will eventually produce a power of 2? For example, N = 97 takes 118 steps to reach 1.
For more info, see https://en.wikipedia.org/wiki/Collatz_conjecture.

I see now that in my initial post I did mention that 3N+1 should become a power of 2, but that is a mistake, the original post has now been corrected for that. Instead, 3N+1 is divisible by 2^k, and the chance of k being larger then 0 is 1, larger then 1 is 1/2, larger then 2 is 1/4, etc.

 

[fresh_42]

Summary: The Collatz Conjecture is that for any integer N (N > 0) the sequence formed by:
- Multiplying N by 3 and add 1, if N is odd
- Dividing B by 2 if N is even
always converges to the sequence ... 4, 2, 1.

Note as soon as the term 3N+1 become divisible by a power of 2 we can repeatedly divide by 2.

For the proof below we rearrange the sequence so it becomes:

First step:
If N is odd, multiply by 3 and add 1.

Each next step:
- Repeatedly divide by 2, as many times as the number k, which is defined as the largest number for which N is divisable by 2^k. Note that k is at least 1, and the resulting number is always odd.
- Muliply by 3 and add 1

What is the chance for a value of k greater then 0?

k chance 3N+1 is divisable by 2^k
-- ---------
1 1
2 1/2
3 1/4
4 1/8

or for any k, the chance is 1/2^k-1

The sequence we can then redefine as (3N+1)/2^k.

If we calculate the average factor for each step defined above, as the sum of the series 1/2+1/4+1/8+... is 1, this factor converges to (3N+1)/2¹⁺¹ = (3N+1)/4, which is smaller then N. So on average, each step will yield a smaller number.

Hence, the sequence must always converge to 1.

The answer to your question is no. Probability considerations are irrelevant. A single counterexample at some point will not show up in the probabilities. Tao has proven a result with probability considerations:
https://arxiv.org/abs/1909.03562
Note that "almost all" means all but finite many. These finite many exceptions are the problem. If they existed, they had a probability measure of zero, i.e. cannot be detected with such an approach.

 

[elcaro]

The answer to your question is no. Probability considerations are irrelevant. A single counterexample at some point will not show up in the probabilities. Tao has proven a result with probability considerations:
https://arxiv.org/abs/1909.03562
Note that "almost all" means all but finite many. These finite many exceptions are the problem. If they existed, they had a probability measure of zero, i.e. cannot be detected with such an approach.

I see, but I'm not sure that the probability considerations mentioned in the paper have any bearing on my proof.

If it does, then maybe a proof by induction is necessary, ie. a proof that if the Collatz Conjecture holds for all integers up to some value of N, that for any value larger then N (say: N + 1) the sequence will always reach a value smaller or equal then N, for which it then is already proven the Collatz conjecture holds. So, if it is proven for all numbers up to N, it then is also proven for numbers up to N+1, and by indiction for all numbers.

If such numbers would exist, it would mean that the average factor (which is the next number in the sequence divided by the number itself) for the limit to infinity of iterations of the sequence, should be larger then 1, and I would guess this can be proven not to be the case, since we already proved that this factor converges to smaller then 1.

 

[fresh_42]

It is extremely difficult to prove the non-existence of, say a number with a certain property. We do not have many tools to tackle such questions. How can we ever be sure that there isn't a number with 10,000,000,000,000 digits that is a counterexample to Collatz? I haven't read Tao's paper but your approach requires a probability measure. However, the entire set of integers on the real number line has a probability measure of zero. You have no instrument to distinguish between example and counterexample except a brute force test. There was a distributed computing project on Collatz but the links that I have found are broken. This would be a better chance than your approach.

 

[elcaro]

It is extremely difficult to prove the non-existence of, say a number with a certain property. We do not have many tools to tackle such questions. How can we ever be sure that there isn't a number with 10,000,000,000,000 digits that is a counterexample to Collatz? I haven't read Tao's paper but your approach requires a probability measure. However, the entire set of integers on the real number line has a probability measure of zero. You have no instrument to distinguish between example and counterexample except a brute force test. There was a distributed computing project on Collatz but the links that I have found are broken. This would be a better chance than your approach.

In general, I would agree on that.
In the case of the Collatz sequence, I would think that it is possible to proof that such numbers can not exist.
Such as the proof by induction.

 

[fresh_42]

In general, I would agree on that.
In the case of the Collatz sequence, I would think that it is possible to proof that such numbers can not exist.
Such as the proof by induction.

It is pretty safe to say that if it was that easy we would already know by now.

It is part of our rules that we do not discuss personal theories. This thread is therefore closed.