Гипотеза Коллатца: в чем проблема с этим простым аргументом, показывающим отсутствие циклов?

Aug 18 2020

Я наткнулся на этот аргумент, связанный с гипотезой Коллатца .

Мне ясно, что этот аргумент не может быть верным. Это слишком просто, и если бы это было правдой, это было бы широко известно.

Я сделал все возможное, чтобы убрать аргумент. Если какой-либо момент неясен или есть более простой способ привести тот же аргумент, дайте мне знать, и я буду рад пересмотреть.

Какой недостаток?

Позволять:

  • $C(x)$ быть такой операцией Коллатца, что $C(x) = \dfrac{3x+1}{2^n}$ где $n$ это высшая сила $2$ что разделяет $3x+1$.
  • $x>1, y\ge 1$ быть различными, нечетными целыми числами, такими что $C(C(C(\dots C(x)\dots) = y$.
  • $u_0, u_1, \dots, u_n$ быть промежуточным результатом между $x$ и $y$ так что:

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

Запрос:

Для любых двух различных положительных нечетных целых чисел $x>1, y\ge 1$ где $C(C(C(\dots C(x)\dots) = y$, в последовательности до $y$. То есть для всех$i,j$:

  • $u_i = u_j$ если только $i=j$
  • $u_i \ne x$
  • $u_i \ne y$

Аргумент:

(1) Можно считать, что $x$ и $y$не будут отображаться как промежуточные значения. То есть для$i$, $u_i \ne x$ и $u_i \ne y$. Если$x$ были промежуточным значением до $y$, тогда $y$ никогда не мог быть достигнут с тех пор $C(x)$- это функция, и один и тот же ввод приведет к такому же выводу. Если$y$ были промежуточным значением, тогда мы могли бы закончить последовательность в этой точке.

Примечание: претензия не в том, что $y$ не повторяется, но повторений нет до $y$. Например, в случае, когда$y=1$, $C(y)=y$. Хотя могут быть повторения после$y$, утверждается, что перед $y$.

(2) Ясно, что $y$ не может делиться на $3$ и далее, что $C(y)=y$ только если $y=1$

Ясно, $3 \nmid \dfrac{3x+1}{2^n}$ и $y \ne \dfrac{3y+1}{2^n}$ когда $y \ne 1$

(3) Можно считать, что $C(x) \ne y$. Если$C(x)=y$, то рассуждение завершено, так как $x$ и $y$ различны.

(4) Существует натуральное число $w > 1$ в отличие от $x,y$ где $C(w) = y$

(5) Кроме того, существует бесконечное количество таких $w_i$ где $C(w_i)=y$:

  • Позволять $w_{i+1} = 4w_i + 1$
  • Ясно, $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}}$
  • Ясно, что ни один из этих $w_i = x$ поскольку мы предположили, что $C(x) \ne y$ и $C(w_i) = y$ По нашему предположению в (1), ни один из этих $w_i = y$

(6) Предположим, что $C(x) \ne w$. Если$C(x)=w$, то рассуждение завершено, так как $x, w, y$ различны.

(7) Существует натуральное число $v > 1$ в отличие от $x, w$ такой, что $C(v) = w$. (Отлично от всех$w_i$ выше с $C(w) = y \ne w$)

Примечание: другие наблюдения:

  • Есть бесконечное $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.

Ответы

8 DoctorWho Aug 19 2020 at 05:05

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.