3
$\begingroup$

I came across this argument related to the Collatz Conjecture.

It is clear to me that the argument cannot be valid. It is too simple and if it were true, it would be widely known.

I have done my best to clean up the argument. If any point is unclear or if there is a simpler way to make the same argument, let me know and I will be glad to revise.

What is the flaw?

Let:

  • $C(x)$ be the collatz operation such that $C(x) = \dfrac{3x+1}{2^n}$ where $n$ is the highest power of $2$ that divides $3x+1$.
  • $x>1, y\ge 1$ be distinct, odd integers such that $C(C(C(\dots C(x)\dots) = y$.
  • $u_0, u_1, \dots, u_n$ be the intermediate results between $x$ and $y$ so that:

$C(x) = u_n, C(u_n)=C(u_{n-1}), \dots, C(u_1) = u_0, C(u_0) = y$

Claim:

For any two distinct positive odd integers $x>1, y\ge 1$ where $C(C(C(\dots C(x)\dots) = y$, there are no repeated numbers in the sequence up to $y$. That is, for all $i,j$:

  • $u_i = u_j$ iff $i=j$
  • $u_i \ne x$
  • $u_i \ne y$

Argument:

(1) We can assume that $x$ and $y$ will not appear as intermediate values. That is, for $i$, $u_i \ne x$ and $u_i \ne y$. If $x$ were an intermediate value before $y$, then $y$ could never be reached since $C(x)$ is a function and the same input will result in the same output. If $y$ were an intermediate value, then we could end the sequence at that point.

Note: The claim is not that $y$ doesn't repeat but that there are no repeats up to $y$. For example, in the case where $y=1$, $C(y)=y$. While there may be repeats after $y$, the claim is that there are no repeats before $y$.

(2) It is clear that $y$ cannot be divisible by $3$ and further that $C(y)=y$ only if $y=1$

Clearly, $3 \nmid \dfrac{3x+1}{2^n}$ and $y \ne \dfrac{3y+1}{2^n}$ when $y \ne 1$

(3) We can assume that $C(x) \ne y$. If $C(x)=y$, then the argument is complete since $x$ and $y$ are distinct.

(4) There exists a positive integer $w > 1$ distinct from $x,y$ where $C(w) = y$

(5) Further, there are an infinite number of such $w_i$ where $C(w_i)=y$:

  • Let $w_{i+1} = 4w_i + 1$
  • Clearly, $C(w_{i+1}) = \dfrac{3w_{i+1} + 1}{2^n} = \dfrac{3(4w_i + 1) + 1}{2^n} = \dfrac{12w_i + 4}{2^n} = \dfrac{4(3w_i + 1)}{2^n} = \dfrac{3w_i + 1}{2^{n-2}}$
  • Clearly, none of these $w_i = x$ since we assumed that $C(x) \ne y$ and $C(w_i) = y$ From our assumption at (1), none of these $w_i = y$

(6) Assume that $C(x) \ne w$. If $C(x)=w$, then the argument is complete since $x, w, y$ are distinct.

(7) There exists a positive integer $v > 1$ distinct from $x, w$ such that $C(v) = w$. (Distinct from all $w_i$ above since $C(w) = y \ne w$)

Note: Other observations:

  • There are an infinite $v_i$ such that $C(v_i) = w_i$ for each $w_i$. This is the same argument as (6).
  • None of these $v_i = x$ and none of these $v_i = w_i$ and none of these $v_i = y$ since $C(y) \ne w$. When $y \ne 1$, it is impossible that $C(y) = w$ since $C(w) = y$. When $y=1$, it is not possible from the assumption in step(1).

$y = \dfrac{3w_0 + 1}{2^n}$ so, clearly, $\dfrac{3\frac{3w_0 + 1}{2^n}+1}{2^m} = \dfrac{9w_0 + 3 + 2^n}{2^{n+m}} \ne w_0$

(8) If we take $w,v,x,y$ as the base case, we can now assume that for any $x,y$ there exists a sequence of intermediate values $u_i$ such that $C(u_0) = y$, $C(u_1) = u_0$ and so on up until $u_n$ where $C(u_n) = C(u_{n-1})$. All values are distinct.

(9) To complete the argument, we need to show that there is necessarily $u_{n+1}$ that has the same properties.

(10) From our original assumption, there exists $u_{n+1}$ such that $C(u_{n+1}) = u_n$. We can further assume that $u_{n+1}$ is distinct from $x$. Otherwise, the argument is already proven.

(11) Because $C(u_{n+1}) = u_n$ and each $u_i$ is distinct from the others, it follows that $u_{n+1}$ is distinct from all $u_0, u_1, \dots u_n$. Otherwise, $C(u_{n+1})$ wouldn't equal $u_n$. To complete the argument, we just need to show that it is distinct from $y$ which is the case from our assumption in step(1).

Note: Assume that $u_{n+1} = u_j$ where $j < u_{n+1}$, then $C(u_{n+1}) = C(u_j) = u_{j-1}$ but $C(u_{n+1}) = u_n$ and by assumption $u_n \ne u_{j-1}$ so we have a contradiction and can reject the assumption.

$\endgroup$
  • 4
    $\begingroup$ Your point (1) can be reduced to "let the sequence $u_1,u_2,...,u_n$ be the shortest possible sequence with the described property". Otherwise that point looks like you are assuming something like your result. It would be a good idea to collect a couple sequences that do repeat and run them through your assumption mill and see where it breaks. $\endgroup$ – abiessu Aug 19 at 4:58
  • $\begingroup$ Great point. That sounds like the flaw. So, if a cycle exists, the argument shows that within the cycle, it is pssible to find a subset that doesn"t repeat. Now, I am clear. :-) $\endgroup$ – Larry Freeman Aug 19 at 5:04
8
$\begingroup$

The flaw is the statement

We can assume that x and y will not appear as intermediate values. That is, for i, ui≠x and ui≠y. If x were an intermediate value before y, then y could never be reached since C(x) is a function and the same input will result in the same output. If y were an intermediate value, then we could end the sequence at that point.

This is only valid if you're actually trying prove the following statement:

Suppose $y \neq x$ and that $n$ is the least $n \in \mathbb{N}$ s.t. $y = C^n(x)$ (where $C^n$ means applying $C$ $n$ times). Then there are no repeats in the sequence $x, C(x), C^2(x), ..., C^n(x)$.

This statement is always true (in fact, one doesn't even need to know anything about $C$ to prove that this is true). But it tells you absolutely nothing about the existence (or nonexistence) of cycles.

To illustrate this point, simply consider a "simplified version" where $C : \{0, 1\} \to \{0, 1\}$ is defined by $C(x) = 1 - x$. The statement above statement also holds when talking about this $C$, but clearly there is a $C$-cycle.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.