Is this a proof of the Collatz Conjecture?

In summary: The sequence we can then redefine as (3N+1)/2k.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)/21+1 = (3N+1)/
  • #1
elcaro
128
30
TL;DR Summary
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 2k. 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 2k
-- ---------
1 1
2 1/2
3 1/4
4 1/8

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

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

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)/21+1 = (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.
 
Last edited:
Mathematics news on Phys.org
  • #2
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.
 
  • Like
Likes topsquark
  • #3
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 2k has a chance of:

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

or, this chance can be expressed as 1/2k-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)/2k) converges to (3N+1)/4, which is smaller then the initial number N, so in the end the sequence will converge to 1.
 
  • #4
Mark44 said:
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 2k, and the chance of k being larger then 0 is 1, larger then 1 is 1/2, larger then 2 is 1/4, etc.
 
  • #5
elcaro said:
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 2k. 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 2k
-- ---------
1 1
2 1/2
3 1/4
4 1/8

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

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

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)/21+1 = (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.
 
  • Like
Likes topsquark
  • #6
fresh_42 said:
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.
 
  • #7
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.
 
  • Like
Likes topsquark
  • #8
fresh_42 said:
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.
 
  • #9
elcaro said:
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.
 
  • Like
Likes topsquark

FAQ: Is this a proof of the Collatz Conjecture?

1. Is there a definitive proof of the Collatz Conjecture?

No, as of now, there is no definitive proof of the Collatz Conjecture. It remains one of the most famous unsolved problems in mathematics.

2. What is the current progress on proving the Collatz Conjecture?

There have been numerous attempts to prove the Collatz Conjecture, but none have been successful so far. Some progress has been made in narrowing down the potential counterexamples, but a complete proof has not been found.

3. Why is the Collatz Conjecture so difficult to prove?

The Collatz Conjecture is difficult to prove because it involves a complex and unpredictable sequence of numbers. Additionally, it is a problem that has stumped mathematicians for centuries, indicating that it may require a completely new approach or mathematical concept to solve.

4. Are there any consequences if the Collatz Conjecture is proven true?

Yes, if the Collatz Conjecture is proven to be true, it would have significant implications in number theory and other areas of mathematics. It could also potentially lead to the discovery of new mathematical concepts and techniques.

5. What is the significance of the Collatz Conjecture in mathematics?

The Collatz Conjecture is significant because it is a simple problem with a seemingly straightforward solution, yet it has remained unsolved for decades. Its difficulty has sparked interest and research in number theory and has led to the development of new methods and techniques in attempting to solve it.

Back
Top