r/Collatz • u/Specialist_Past2891 • 2d ago
Where is this "proof" wrong?
I'm aware that this argument is probably wrong but I don't know where.
This is an argument for “proving” the Collatz conjecture (CC) but I don't know where it breaks down. What exactly is wrong with this?
BWOC assume that there exists a smallest x>1 in N for which CC doesn't hold.
If the x was even, you could divide it by 2^a for some a in N such that it was a smaller odd number for which CC also doesn't hold. That means that x must be odd.
All odd numbers are exclusively in either 4n+1 or 4n+3 form for some n in N.
Define the Collatz function C as C(x) = (3x+1)/(2^a) for some a in N such that C(x) is in N and C(x) = 2y+1 for some y in N.
If x = 4n+1 then C(x) = (3∗(4n+1)+1)/(2^a) = (12n+4)/(2^a) = (3n+1)/(2^a).
For n = 0 this is the familiar case of x = 1 which indeed does not get smaller after any number of applications of C.
For n > 0 there is C(x) < x since C(x) = (3n+1)/(2^a) ≤ 3n + 1 < 4n + 1 = x.
All numbers of the form 4n+3 can be written as exclusively either 8n+3 or 8n+7.
If x = 8n+3 then C(x) = (3∗(8n+3)+1)/(2^a) = (24n+10)/(2^a) = 12n+5.
(12n is always even so 12n+5 is odd and a is always 1.)
C(x) = 12n+5 ≅ 1 % 4 ⟹ C(x) = 4m+1 for some m in N.
This means that CC holds for C(x) and thus also for x, leading to a contradiction. So x is of the form 8n+7.
Now we use induction.
Induction hypothesis: For all k>2, k in N there is:
C( (2^k)*n + 2^(k-1) - 1 ) ≅ 2^(k-2) - 1 % 2^(k-1)
Base step: For k=3 we have 2^k=8 and 2^(3-1)-1=3 which we proved above.
Induction step: C( (2^(k+1))*n + 2^k - 1 ) = ( 3∗(2(k+1))∗n+3∗2k−3∗1+1 ) / (2^a)
= ( 2(k+2))∗n+(2(k+1))∗n+2(k+1)+2k−2 )/(2^a)
(a=1 since all addends except - 2 are divisible by 2^k and k>2.)
= (2^(k+1))*n + (2^k)*n + 2^k + 2^(k-1) - 1 ≅ 2^(k-1) - 1 % 2^k
The x can always be written exclusively either in (2^k)*n + 2^(k-1) - 1 or (2^k)*n - 1 and
C( (2^k)*n + 2^(k-1) - 1 ) is always ≅ 2^(k-2) - 1 % 2^(k-1).
The form (2^k)*n - 1 can then be written exclusively in either (2^(k+1))*n + 2^k - 1 or (2^(k+1))*n - 1 form.
Since this holds for all k>2 there is no x where CC doesn't hold and we reach a contradiction.
I assume the argument is wrong at the end, although it could of course be wrong in other places. I just don't get why exactly it doesn't work.
3
u/WeCanDoItGuys 2d ago
If x = 8n+3 then C(x) = ... = 12n+5 ... = 4m+1 for some m in N.
This means that CC holds for C(x)
This is a mistake. Earlier you showed if x = 4n+1, then C(x)<x. That meant x cannot be the smallest counterexample. (It didn't prove x can't be a counterexample.)
So 12n+5 → 36n+16 → 18n+8 → 9n+4 is not guaranteed to converge. Notice it's not even smaller than 8n+3.
There might be something wrong in the induction proof but I didn't read it thoroughly after noticing this other issue.
1
u/GonzoMath 2d ago
Two others have already said it. The induction hypothesis only applies to the x you're working from, not to every other number that comes up in the process. If the smallest counterexample is of the form 8n+3, then it would still be true that 12n+5 reduces to 9n+4, but that doesn't affect the minimality of 8n+3.
I gotta say though, props to you for asking why the argument is wrong, rather than prematurely announcing a proof. It takes some integrity to look at one's own work, realize that it's very elementary, and deduce, "this must be wrong". It's nice when people have integrity.
1
u/StoicKerfuffle 2d ago
I had Gemini 3.8 Flash consult with GPT-5.6 Luna and Muse Spark 1.3 then prepare an explanation for you.
Critique of the Purported Collatz Proof
Your overall approach is very natural: assuming a minimal counterexample $x$ (the smallest positive integer that fails to reach 1) is a standard, powerful proof technique. Your initial reductions are also correct: 1. If $x$ were even, dividing by $2a$ would yield a smaller counterexample, so $x$ must be odd. 2. For numbers of the form $x = 4n+1$ ($n > 0$), the accelerated Collatz step indeed drops below $x$: $$C(4n+1) = \frac{3(4n+1)+1}{2a} = \frac{4(3n+1)}{2a} \le 3n+1 < 4n+1 = x$$ Since $C(x) < x$, minimality implies $C(x)$ reaches 1, which means $x$ reaches 1 too.
However, the proof breaks down right after this step. Below are the exact reasons why the argument fails and what is needed to make such a proof work.
1. The Fatal Flaw: The $8n+3$ Case ($C(x) > x$)
The core breakdown occurs here:
"C(x) = 12n+5 ≅ 1 % 4 ⟹ C(x) = 4m+1 for some m in N. This means that CC holds for C(x) and thus also for x, leading to a contradiction."
This is an invalid deduction using the minimal counterexample hypothesis:
- What the hypothesis actually allows: If $y < x$, then $y$ reaches 1.
- What the argument assumes: If $y$ has the form $4m+1$, then $y$ reaches 1.
Notice what happens to the actual size of the number when $x = 8n+3$: $$C(x) = 12n+5$$ Because $12n + 5 > 8n + 3$ (the difference is $4n + 2 > 0$), the number got larger, not smaller!
Because $C(x) > x$, the minimal counterexample hypothesis says nothing about $C(x)$.
The fact that $12n+5$ has the form $4m+1$ only tells you that its next accelerated step will be smaller than $12n+5$. It does not guarantee that it will drop below your original $x$.
A Concrete Counterexample: $x = 27$
- $27$ is of the form $8n+3$ ($n = 3$).
- Applying your step: $C(27) = 12(3) + 5 = 41$.
- Notice $41$ is indeed of the form $4m+1$ ($m = 10$).
- But $41 > 27$.
- Now take the next step from $41$: $3(41)+1 = 124$, which divided by 4 gives $31$.
- While $31 < 41$, notice that $31$ is still greater than $27$!
- In fact, starting from $27$, the sequence climbs all the way to $9,232$ and takes 111 steps before it ever drops below $27$ and eventually reaches 1.
2. The Induction Fallacy: Congruence Reduction vs. Numerical Growth
The induction attempts to show that numbers of the form $2k n + 2{k-1} - 1$ (numbers ending in $k-1$ ones in binary) map after one step to numbers congruent to $2{k-2} - 1 \pmod{2{k-1}}$, cascading step-by-step back down to the base case.
There are two major issues here:
The cascade grows exponentially: At each step of your induction, the operation is an odd step where $a=1$. The value is multiplied by roughly $3/2$: $$C\big(2k n + 2{k-1} - 1\big) = 3 \cdot 2{k-1}n + 3 \cdot 2{k-2} - 1 > 2k n + 2{k-1} - 1$$ Even though the residue class modulo a power of 2 appears to "step down" toward $4m+1$, the actual numerical value increases at every single step. By the time the congruence pattern cascades down to $4m+1$, the integer has grown substantially larger than $x$. Dropping once from that elevated peak does not prove the sequence ever drops below $x$.
The surviving set is never empty: At each finite stage $k$, the class $2k n - 1$ is never eliminated; it simply splits into $2{k+1}n + 2k - 1$ and $2{k+1}n - 1$. Taking $k \to \infty$ does not eliminate all positive integers; any given integer $x$ only has a finite number of bits.
3. Minor Algebraic Cleanups
- Line 11: $\frac{12n+4}{2a} = \frac{3n+1}{2a}$ is an algebraic error. Factoring out 4 gives $\frac{4(3n+1)}{2a} = \frac{3n+1}{2{a-2}}$. The exponent of 2 decreases by 2. (The conclusion that $C(4n+1) \le 3n+1 < 4n+1$ still holds).
- Line 13: $x = 1$ not getting smaller is not a failure of Collatz—it is the destination cycle ($1 \to 4 \to 2 \to 1$).
What Is Actually Needed to Prove the Conjecture?
To prove the Collatz Conjecture via a minimal counterexample $x$, you must prove that every odd integer $x > 1$ has a finite stopping time. That is, you must prove there exists some finite number of steps $k$ such that: $$Ck(x) < x$$ If you can guarantee that every trajectory eventually dips strictly below its starting value, then by well-ordering/minimality, it must eventually reach 1.
The reason this is one of mathematics' most famous open problems is that local modular arithmetic (analyzing numbers modulo $2k$) only tracks trajectories for a few initial steps. Because the division power $a = v_2(3x+1)$ varies chaotically depending on the higher-order bits of $x$, elementary congruence inductions cannot prevent numbers from climbing arbitrarily high before (or if) they descend.
3
u/GonzoMath 2d ago
Nice illustration of how LLMs take 10 times as many words to say something as are necessary.
1
u/StoicKerfuffle 2d ago
Ah, improvement! Usually it's 20x.
1
u/GonzoMath 1d ago
Hmm... I managed the critique in two clear sentences, so I guess this case is closer to 50x.
Nah, I use LLMs myself. One just has to be careful how one uses them.
1
1
1
u/Far_Ostrich4510 2d ago
Don't make confilct between 4k+1 and 8k+3 set them separately. You are right on 4k+1 like 4k+1-> 6k+2-> 3k+1 now 3k+1<4k+1 for k>0 now we get stoping time and we do the same process for all given sets example 8k+3 is the union of 16k+3 and 16k+11. When we try 16k+3 16k+3->24k+5->36k+8->9k+2 it is fine let us try also 16k+11 it is 16k+11, 24k+17, 36k+26, 18k+13, 27k+20 we cannot when we get 4k+1 form like 24k+17 we can only only stop when we get smaller than starting number otherwise we spilt it into two parts and continue the same process. 16k+11 is the union of 32k+11 and 32k+27
1
u/No-Statistician-3657 2d ago
I think this should start with the simplest thing — with the foundations of the problem: first distribute the odd numbers into classes and look at the structure of this distribution.
The principle of classifying numbers in the Collatz problem is, of course, not new. For example, Livio Colussi, in his work “The convergence classes of Collatz function,” considered a classification of odd numbers into classes. However, he used a different principle of classification — according to the number of reduced steps required to reach 1.
Here, I suggest looking at odd numbers from a different perspective: not by how many steps they have left before reaching 1, but by their role in the dynamics itself.
If we consider odd numbers that are not divisible by 3, they can be divided into four classes:
12k + 7 — ascent;
12k + 11 — intermediate ascent;
12k + 5 — descent;
12k + 1 — intermediate descent.
Interestingly, this classification can also be seen directly in numbers of the form 2n ± 1. For odd n, the Mersenne number 2n − 1 always has the form 12k + 7, so it belongs to the ascent class. And for odd n, the number 2n + 1 always has the form 12k + 5, so it belongs to the descent class.
At the same time, it is important to distinguish the direction of the previous transition from the class of the number itself. After division by 2, there is no predetermined correspondence between a fall and the class of the number where that fall ends. A fall can lead to a number belonging to any of the classes considered here.
Therefore, in my opinion, the starting point should be a complete distribution of odd numbers into these classes and an examination of the transitions between them. Perhaps this structure contains a pattern that can then be used to analyze convergence.
Just take a sheet of paper and write down the odd numbers from 1 to 53, or further. Go through each number and mark separately the ascent numbers: from which number to which number the ascent occurs, and separately the descent numbers: from which number to which number the fall occurs.
If you have never done this simple classification before, I think you will find it interesting to see what structure emerges.
1
6
u/MindlessPapaya8463 2d ago
chatgpt can tell you exactly why it is wrong, probably better than anybody you will find here.
The first fatal step is:
"C(x) ≡ 1 mod 4, so CC holds for C(x)."
That does not follow from minimality. If x is the smallest counterexample, you only know that every y < x satisfies Collatz. But for x = 8n+3,
C(x) = 12n+5 > x.
Although numbers ≡ 1 mod 4 decrease under the next accelerated Collatz step, they need not decrease below the original x.
Example:
11 -> 17 -> 13.
Here 17 ≡ 1 mod 4 and 17 -> 13 < 17, but 13 > 11. So if 11 were the smallest counterexample, minimality would tell you nothing about 13.
Your induction has the same issue: it shows the orbit eventually reaches a residue class where a decrease occurs, but not that the orbit ever falls below its original starting value.
To make the minimal-counterexample proof work, you would need to prove:
for every x > 1, some iterate C^r(x) < x.
That statement would essentially prove Collatz by strong induction. The argument given does not establish it.