Collatz Conjecture/Failed Proof
Conjecture
Let $f: \N \to \N$ be the mapping defined on the natural numbers as follows:
- $\forall n \in \N: \map f n = \begin{cases}
n / 2 & : n \text { even} \\ 3 n + 1 & : n \text { odd} \end{cases}$
For any given value of $n$, let the sequence $\sequence {S_k}$ be defined:
- $\forall k \in \N: S_k = \begin{cases}
n & : k = 0 \\ \map f {S_{k - 1} } & : k > 0 \end{cases}$
The Collatz conjecture is:
- For all $n \in N$, there exists some $i \in \N$ such that sequence $S_i = 1$.
Failed Proof
 | This article needs to be tidied. In particular: minor Please fix formatting and $\LaTeX$ errors and inconsistencies. It may also need to be brought up to our standard house style. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Tidy}} from the code. |
Aiming for a contradiction, suppose that for some $n \in N$, there does NOT exist any $i \in \N$ such that the sequence $S_i = 1$.
From the Well-Ordering Principle, this hypothetical sequence $\sequence {S_k}$ must have a smallest element.
Let $a = S_k$ be the smallest element of this hypothetical sequence.
We know that $a$ can not be even because:
| \(\ds S_k\) | \(=\) | \(\ds 2 r\) | ||||||||||||
| \(\ds S_{k + 1}\) | \(=\) | \(\ds r\) |
which contradicts our assertion that $a$ was the smallest element in the sequence.
We also know that $a \not \equiv 1\pmod 4$ because:
| \(\ds S_k\) | \(=\) | \(\ds 4 r + 1\) | ||||||||||||
| \(\ds S_{k + 1}\) | \(=\) | \(\ds 3 \paren {4 r + 1} + 1\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds 12 r + 4\) | ||||||||||||
| \(\ds S_{k + 2}\) | \(=\) | \(\ds 6 r + 2\) | ||||||||||||
| \(\ds S_{k + 3}\) | \(=\) | \(\ds 3 r + 1\) | ||||||||||||
| \(\ds \) | \(<\) | \(\ds S_k\) |
Because $S_{k + 3} < S_k$, this contradicts our assertion that $a$ was the smallest element in the sequence.
When $a \equiv 3 \pmod 4$, we obtain
| \(\ds S_k\) | \(=\) | \(\ds 4 r + 3\) | ||||||||||||
| \(\ds S_{k + 1}\) | \(=\) | \(\ds 3 \paren {4 r + 3} + 1\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds 12 r + 10\) | ||||||||||||
| \(\ds S_{k + 2}\) | \(=\) | \(\ds 6 r + 5\) | ||||||||||||
| \(\ds S_{k + 3}\) | \(=\) | \(\ds 3 \paren {6 r + 5} + 1\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds 18 r + 16\) | ||||||||||||
| \(\ds S_{k + 4}\) | \(=\) | \(\ds 9 r + 8\) |
- but we can go no further because the parity of $S_{k + 4}$ depends on $r$.
The results here are inconclusive.
We now have that if $a = S_k$ is the smallest element of our hypothetical sequence, then $a$ must reside in the residue class of $3$ (modulo $4$).
Let us now see if we can improve our filter for $a$ by removing additional residue classes from contention.
Inspecting the set of residue classes modulo $16$, we focus our attention on $3$ (modulo $16$), $7$ (modulo $16$), $11$ (modulo $16$) and $15$ (modulo $16$).
We know that $a \not \equiv 3 \pmod {16}$ because:
| \(\ds S_k\) | \(=\) | \(\ds 16 r + 3\) | ||||||||||||
| \(\ds S_{k + 1}\) | \(=\) | \(\ds 3 \paren {16 r + 3} + 1\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds 48 r + 10\) | ||||||||||||
| \(\ds S_{k + 2}\) | \(=\) | \(\ds 24 r + 5\) | ||||||||||||
| \(\ds S_{k + 3}\) | \(=\) | \(\ds 3 \paren {24 r + 5} + 1\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds 72 r + 16\) | ||||||||||||
| \(\ds S_{k + 4}\) | \(=\) | \(\ds 36 r + 8\) | ||||||||||||
| \(\ds S_{k + 5}\) | \(=\) | \(\ds 18 r + 4\) | ||||||||||||
| \(\ds S_{k + 6}\) | \(=\) | \(\ds 9 r + 2\) | ||||||||||||
| \(\ds \) | \(<\) | \(\ds S_k\) |
Because $S_{k + 6} < S_k$, this contradicts our assertion that $a$ was the smallest element in the sequence.
Just like $3$ (modulo $4$) shown above, the results for $7$ (modulo $16$), $11$ (modulo $16$) and $15$ (modulo $16$) are inconclusive.
We now have the following:
If a counterexample to the Collatz Conjecture exists, then such a counterexample would require a sequence with a smallest element.
This smallest element could only reside in the following residue classes:
(modulo $4$): $3$
(modulo $16$): $7$, $11$, $15$
(modulo $64$): $7$, $15$, $27$, $31$, $39$, $47$, $59$, $63$
(modulo $256$): $27$, $31$, $47$, $63$, $71$, $91$, $103$, $111$, $127$, $155$, $159$, $167$, $191$, $207$, $223$, $231$, $239$, $251$, $255$
As we can see, (modulo $4^n$), there are $\approx 2^{1.5 \paren{n - 1} }$ residue classes where $a$ could reside.
This means we have a Cantor set-esque filter which allows our hypothetical smallest element $a$ to reside in an ever dwindling proportion of the possible residue classes (that is, $\dfrac {2^ {1.5 \paren {n - 1} } } {4^n}$).
Just like the Cantor set and just like prime numbers, at increasing values of $n$, we get an ever increasing set of something (what remains of the Cantor set, prime numbers and in this case, candidate residue classes where $a$ could reside).
However, the proportion of the item of interest relative to all possible values heads towards zero.
And we've proved nothing.
Math is hard.