Доказательство гипотезы 3x+1.

[grizzly]

(Оффтоп)

Volik в сообщении #1252765 писал(а):

И как дальше разбираться, если и дальше будет, пишется одно, а подразумевается наоборот?

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

[Мастак]

Линки линков какие-то наверно надо в топике отметить, а ТС что-то не упомянул, что гипотезе Коллатца и сиракузским последовательностям уже скоро 100 лет, а в поп-математике эта задача известна как Чи́сла-гра́дины.

https://wiki2.org/ru/%D0%93%D0%B8%D0%BF ... 1%86%D0%B0
https://oeis.org/A006577
https://oeis.org/A161021
...

_________________
График сиракузской последовательности для числа 27:

На графиках подозревалась некоторая периодичность => попытки аппроксимировать функцией, которую представить как разложение в ряд, и т.п.
Также пытались строить разные формулы функции Коллатца (см., например, линки в https://oeis.org/A014682).
И т.д.

_____
Числа-градины известный хит поп-математки.

[Tot]

Вариант второй, исправленный и переработанный.

Доказательство гипотезы $3x+1$.

План.
1] Формулировка гипотезы.
2] Схема доказательства.
3] Правило $3\frac{z+1}{2^{\gamma}}$.
4] Сведение любого нечётного числа к трём.
5] Вывод.

1] Формулировка гипотезы.
Для натурального числа $x$ задана процедура получения нового значения из старого по схеме:
$x_{new}=\frac{3x_{old}+1}{2}$, если $x_{old}$ нечётно или $x_{new}=\frac{x_{old}}{2}$ в противном случае.
Доказать, что для любого $x$ такая процедура после некоторого числа шагов всегда заканчивается $1$.

2] Схема доказательства.
$x$ всегда можно представить в виде $x=2^{\beta}y$, где $y\in\mathbb N, y\mod 2\equiv 1, \beta\in\{\mathbb N; 0\}$. Причём иксы с произвольным $\beta$ эквивалентны в смысле конечного результата процедуры.
Если конечный результат многократного применения процедуры к $y$ равен $1$, то $y$ можно представить в следующем виде.

$$y=\frac{\frac{\frac{\frac{\frac{2^{\alpha_1}-1}{3}2^{\alpha_2}-1}{3}2^{\alpha_3}-1}{3}...}{3}2^{\alpha_n}-1}{3}$$

$n,\alpha_1,...,\alpha_n\in\mathbb N$
Самую нижнюю степень перенесём влево, справа же приведём к общему знаменателю и разобъём на отдельные степени двойки.

$$3y=\frac{2^{\sum_{i=1}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=2}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=3}^{n}\alpha_i}}{3^{n-2}}-...-\frac{2^{\alpha_n}}{3}-1 (1)$$

Гипотеза $3x+1$ сводится к гипотезе о том, что в форме $(1)$ представим любой $3y$.
Доказательство проведём по схеме:
1) рассмотрим правило перехода от одного нечётного зет к другому нечётному зет без потери формы $(1)$ и найдём условие его применения в обе стороны;
2) покажем, что из существования в форме $(1)$ нечётного зет следует существование в той же форме тройки и наоборот.
Суть схемы доказательства заключается в следующем. Пусть есть правило, при преобразовании нечётного зет по которому сохраняется форма $(1)$.
При этом условие существования в этой форме начального и конечного зетов по правилу взаимны.
Тогда если для $\forall y\in\mathbb N, y\mod 2\equiv 1$ можно построить цепочку применения этого правила, которая гарантированно уменьшает тройной игрек с сохранением формы $(1)$ до трёх, то есть из несуществования начального тройного игрека в форме $(1)$ следует несуществование тройки в той же форме, что заведомо даёт противоречие и доказывает утверждение о представимости любого тройного игрека в форме $(1)$.
При этом исключением может стать только заведомо бесконечно большое число, так как гипотеза $3x+1$ говорит лишь о всех конечных числах натурального ряда.

3] Правило $3\frac{z+1}{2^{\gamma}} (2)$.
Пусть дан $z_0$ в форме $(1)$. При этом $z_0\mod 2\equiv 1$.
Применим $(2)$ для получения $z_1$. $\gamma=\alpha_n,z_1\in\mathbb N, z_1\mod 2\equiv 1$.

$$z_1=\frac{2^{\sum_{i=1}^{n-1}\alpha_i}}{3^{n-2}}-\frac{2^{\sum_{i=2}^{n-1}\alpha_i}}{3^{n-2}}-\frac{2^{\sum_{i=3}^{n-1}\alpha_i}}{3^{n-3}}-...-\frac{2^{\alpha_{n-1}}}{3}-1$$

Получили $z_1$ в форме $(2)$.
Теперь рассмотрим обратное преобразование. Ограничения на $z_1$ и $z_0$ прежние. Пусть дан $z_1$ в форме $(1)$.
Тогда умножим на $2^{\gamma}$, разделим на три и вычтем единицу, это всегда можно сделать, и получим $z_0$ в форме $(1)$.
Следовательно, правило $(2)$ обратимо, начальное и конечное значения взаимно представимы в форме $(1)$.

4] Сведение любого нечётного числа к трём.
Пусть произвольное нечётное число $z$ представимо в виде конечного ряда формы $(1)$. При этом существует ряд представления наименьшей длины, все альфы которого однозначно находятся применением обратного правила $(2)$. Пусть наименьшее представление $z$ имеет $n$ коэффициентов.

$$z=\frac{2^{\sum_{i=1}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=2}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=3}^{n}\alpha_i}}{3^{n-2}}-...-\frac{2^{\alpha_n}}{3}-1$$

Если применить к нему обратное правило $(2)$ $n$ раз, то получим нечётное число, которое отличается от $z$ приблизительно в $\delta=\frac{3^{n}}{2^{\sum_{i=1}^{n}\alpha_i}}$ раз.
Заметим, что если один из коэффициентов альфа равен двойкe, то соответствующее ему преобразование по обратному правилу $(2)$ увеличивает дельту в полтора раза, при всех же других возможных значениях данной альфы дельта лишь заведомо уменьшается.
Теперь рассмотрим способ удлинения наименьшего представления $z$.

$$z=\frac{2+2^{\sum_{i=1}^{n}\alpha_i}}{3^{n}}-\frac{2^{\sum_{i=1}^{n}\alpha_i}}{3^{n}}-\frac{2^{\sum_{i=2}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=3}^{n}\alpha_i}}{3^{n-2}}-...-\frac{2^{\alpha_n}}{3}-1$$

$$z=\frac{2^{2\varepsilon+\sum_{i=1}^{n}\alpha_i}}{3^{n+\varepsilon-1}}-\frac{2^{2\varepsilon-2+\sum_{i=1}^{n}\alpha_i}}{3^{n+\varepsilon-1}}-\frac{2^{2\varepsilon-4+\sum_{i=1}^{n}\alpha_i}}{3^{n+\varepsilon-2}}-...-\frac{2^{\sum_{i=2}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=3}^{n}\alpha_i}}{3^{n-2}}-...-\frac{2^{\alpha_n}}{3}-1$$

Применим к нему обратное правило $(2)$ $n+\varepsilon$ раз, то получим нечётное число, которое отличается от $z$ приблизительно в $\delta \frac{3^{\varepsilon}}{4^{\varepsilon}}$ раз.
Но обратное преобразование по правилу $(2)$ переводит тройку саму в себя. Поэтому при достаточно большом эпсилон, а мы можем взять его таким, каким нужно, зет всегда переходит в тройку цепочкой обратимых преобразований.

5] Вывод.
Для $\forall 3y\in\mathbb N, y\mod 2\equiv 1$, кроме бесконечно больших, существует цепочка преобразований, которая приводит к трём и каждый элемент которой представим в форме $(1)$ при условии существования представления в форме $(1)$ тройки. Но ведь $3=\frac{16}{3}-\frac{4}{3}-1$. Поэтому $\forall 3y\in\mathbb N, y\mod 2\equiv 1$ представим в форме $(1)$. А это значит, что гипотеза $3x+1$ верна.

[grizzly]

По привычке начинаю читать с конца:

Tot в сообщении #1257329 писал(а):

Для $\forall 3y\in\mathbb N, y\mod 2\equiv 1$, кроме бесконечно больших, существует цепочка преобразований, которая приводит к трём

Следите за руками (делю на максимальную степень двойки):
$9\to 7\to 11\to 17\to 13\to 5\to 1$.
В конце нет тройки. Поправьте вывод или рассуждения.

[Tot]

Нет, тройной игрек изменяется по правилу $(2)$ преобразования формы $(1)$, которое не является правилом преобразования гипотезы $3x+1$.

[Sender]

Tot в сообщении #1257329 писал(а):

Пусть произвольное нечётное число $z$ представимо в виде конечного ряда формы $(1)$.

А что, если нам попался $z$, который нельзя представить в такой форме?

[Tot]

Правило $(2)$ применимо к любому нечётному числу. И обратное преобразование правила однозначно вычисляет все альфы, кроме$\alpha_1$, которая находится по остаточному принципу.
Если нечётный $z$ нельзя представить в форме $(1)$, то он представим в бесконечном варианте этой формы. Но форма $(1)$ состоит из одного уменьшаемого и кучи вычитаемых, значит в бесконечном варианте представления будет натуральный $z$ записываться бесконечным рядом отрицательных чисел, что даёт противоречие.

[Tot]

Tot в сообщении #1257536 писал(а):

И обратное преобразование правила однозначно вычисляет все альфы, кроме$\alpha_1$, которая находится по остаточному принципу.

Прямое преобразование, а не обратное.

[mihaild]

Tot в сообщении #1257536 писал(а):

то он представим в бесконечном варианте этой формы

Что такое "бесконечный вариант этой формы"? Какой-то ряд? (какой?) И почему если нечетное число не представимо в виде $(1)$, то оно представимо в виде этого ряда?

Tot в сообщении #1257329 писал(а):

Применим к нему обратное правило $(2)$ $n+\varepsilon$ раз, то получим нечётное число, которое отличается от $z$ приблизительно в $\delta \frac{3^{\varepsilon}}{4^{\varepsilon}}$ раз.

Обратное правило $(2)$ применимо только к числам, делящимся на $3$.

[Tot]

mihaild в сообщении #1257818 писал(а):

Обратное правило $(2)$ применимо только к числам, делящимся на $3$.

Согласен, что-то меня переклинило на обратном преобразовании, здесь тоже применяется прямое правило $(2)$.

mihaild в сообщении #1257818 писал(а):

Что такое "бесконечный вариант этой формы"? Какой-то ряд? (какой?) И почему если нечетное число не представимо в виде $(1)$, то оно представимо в виде этого ряда?

Но ведь правило $(2)$ применимо к любому нечётному числу по определению. Берёте нужное Вам число, прибавляете единицу, избавляетесь от чётности делением на нужную степень двойки (альфа последняя), умножаете на три, получается число, повторяете эту процедуру прямого правила $(2)$ и получаете число и альфу предпоследнюю, как степень двойки, по определению формы $(1)$. Многократное применение правила либо приводит к $\alpha_1$, тогда число представимо в форме $(1)$, либо не приводит, в этом случае наше положительное число представимо в виде бесконечного ряда, все элементы которого отрицательны.

[Sender]

Tot в сообщении #1257830 писал(а):

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

Либо не приводит, порождая неограниченно возрастающую последовательность.

[Tot]

Не-а. Эта неограниченно возрастающая последовательность ограничена сверху такой же последовательностью со всеми единичными альфами по определению, а такая последовательность есть бесконечная геометрическая прогрессия со знаменателем две третьих, начинающаяся с единицы. Её сумма равна трём, поэтому бесконечно возрастающая последовательность может представлять только бесконечно большое число, а у нас все числа конечны.

[grizzly]

Не смог понять это доказательство. Не какой-то отдельный шаг, а само рассуждение. Я его воспринимаю примерно как стандартную "вероятностную эвристику" в пользу ограниченности последовательности Коллатца. Но даже "вероятностная эвристика" не позволяет убедиться в отсутствии других циклов, кроме тривиального. А это доказательство на него претендует, как я понял (но и про это не понял в каком именно месте).

[Tot]

Sender в сообщении #1257874 писал(а):

Либо не приводит, порождая неограниченно возрастающую последовательность.

Это белое пятно пока остаётся, моё рассуждение по его закрытию как минимум не является полным.

[Tot]

Вариант третий, исправленный и дополненный.

Доказательство гипотезы $3x+1$.

План.
1] Формулировка гипотезы.
2] Схема доказательства.
3] Правило $3\frac{z+1}{2^{\gamma}}$.
4] Нечётные числа, имеющие конечное разложение.
5] Нечётные числа, имеющие только бесконечное разложение.
6] Вывод.

1] Формулировка гипотезы.
Для натурального числа $x$ задана процедура получения нового значения из старого по схеме:
$x_{new}=\frac{3x_{old}+1}{2}$, если $x_{old}$ нечётно или $x_{new}=\frac{x_{old}}{2}$ в противном случае.
Доказать, что для любого конечного $x$ такая процедура после некоторого числа шагов всегда заканчивается $1$.

2] Схема доказательства.
$x$ всегда можно представить в виде $x=2^{\beta}y$, где $y\in\mathbb N, y\mod 2\equiv 1, \beta\in\{\mathbb N; 0\}$. Причём иксы с произвольным $\beta$ эквивалентны в смысле конечного результата процедуры.
Если конечный результат многократного применения процедуры к $y$ равен $1$, то $y$ можно представить в следующем виде.

$$y=\frac{\frac{\frac{\frac{\frac{2^{\alpha_1}-1}{3}2^{\alpha_2}-1}{3}2^{\alpha_3}-1}{3}...}{3}2^{\alpha_n}-1}{3}$$

$n,\alpha_1,...,\alpha_n\in\mathbb N$
Самую нижнюю степень перенесём влево, справа же приведём к общему знаменателю и разобъём на отдельные степени двойки.

$$3y=\frac{2^{\sum_{i=1}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=2}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=3}^{n}\alpha_i}}{3^{n-2}}-...-\frac{2^{\alpha_n}}{3}-1\eqno(1)$$

Гипотеза $3x+1$ сводится к гипотезе о том, что в форме (1) представим любой $3y$.
Доказывать будем более сильное утверждение о том, что в форме (1) представим любой $z\in\mathbb N, z\mod 2\equiv 1$
Доказательство проведём по схеме:
1) рассмотрим в разделе 3] правило перехода от одного нечётного зет к другому нечётному зет без потери формы $(1)$ и найдём условие его применения в обе стороны;
2) покажем в разделе 4], что из существования в конечной форме (1) нечётного зет следует существование в той же форме тройки и наоборот;
3) убедимся в разделе 5], что зет, имеющих только бесконечное представление в форме (1) не существует.
Суть схемы доказательства заключается в следующем. Пусть есть правило, при преобразовании нечётного зет по которому сохраняется форма $(1)$.
При этом условие существования в этой форме начального и конечного зетов по правилу взаимны.
При этом данное правило применимо к любому нечётному зет. Цепочка последовательного применения правила даёт всегда форму (1) в конечном или бесконечном варианте.
Тогда если для $\forall y\in\mathbb N, y\mod 2\equiv 1$ можно построить конечную цепочку применения этого правила, которая гарантированно уменьшает тройной игрек с сохранением формы (1) до трёх, то есть из несуществования начального тройного игрека в форме (1) следует несуществование тройки в той же форме, что заведомо даёт противоречие и доказывает утверждение о представимости любого тройного игрека в форме (1).
Отдельно рассматриваем случаи, когда зет имеет только бесконечное представление в форме (1) в виде сходящегося или расходящегося рядов, с нахождением логического противоречия в таких конструкциях.
При этом исключением из всех вариантов может стать только заведомо бесконечно большое число, так как гипотеза $3x+1$ говорит лишь о всех конечных числах натурального ряда.

3] Правило

$$3\frac{z+1}{2^{\gamma}} \eqno(2)$$

Пусть дан $z_0$ в форме (1). При этом $z_0\mod 2\equiv 1$.

$$z_0=\frac{2^{\sum_{i=1}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=2}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=3}^{n}\alpha_i}}{3^{n-2}}-...-\frac{2^{\alpha_n}}{3}-1$$

Применим (2) для получения $z_1$. $\gamma=\alpha_n,z_1\in\mathbb N, z_1\mod 2\equiv 1$.

$$z_0\stackrel{3\frac{z+1}{2^{\alpha_n}}}{\longrightarrow}z_1$$

$$z_1=\frac{2^{\sum_{i=1}^{n-1}\alpha_i}}{3^{n-2}}-\frac{2^{\sum_{i=2}^{n-1}\alpha_i}}{3^{n-2}}-\frac{2^{\sum_{i=3}^{n-1}\alpha_i}}{3^{n-3}}-...-\frac{2^{\alpha_{n-1}}}{3}-1$$

Получили $z_1$ в форме (1).
Теперь рассмотрим обратное преобразование. Ограничения на $z_1$ и $z_0$ прежние. Пусть дан $z_1$ в форме (1).

$$z_1=\frac{2^{\sum_{i=1}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=2}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=3}^{n}\alpha_i}}{3^{n-2}}-...-\frac{2^{\alpha_n}}{3}-1$$

Тогда умножим на $2^{\gamma}$, разделим на три и вычтем единицу, это всегда можно сделать, и получим $z_0$ в форме (1) при $\forall\gamma\in\mathbb N$.

$$z_1\stackrel{3\frac{z+1}{2^{\gamma}}}{\longleftarrow}z_0$$

Движение от входа к выходу против стрелочки задаёт обратное преобразование.

$$z_0=\frac{2^{\gamma+\sum_{i=1}^{n}\alpha_i}}{3^{n}}-\frac{2^{\gamma+\sum_{i=2}^{n}\alpha_i}}{3^{n}}-\frac{2^{\gamma+\sum_{i=3}^{n}\alpha_i}}{3^{n-1}}-...-\frac{2^{\gamma+\alpha_n}}{9}-\frac{2^{\gamma}}{3}-1$$

Следовательно, правило (2) обратимо, начальное и конечное значения взаимно представимы в форме (1).

4] Нечётные числа, имеющие конечное разложение.
Пусть произвольное нечётное число $z_0$ представимо в виде конечного ряда формы (1). При этом существует ряд представления наименьшей длины, все альфы которого однозначно находятся применением правила (2). Пусть наименьшее представление $z_0$ имеет $n$ коэффициентов.

$$z_0=\frac{2^{\sum_{i=1}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=2}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=3}^{n}\alpha_i}}{3^{n-2}}-...-\frac{2^{\alpha_n}}{3}-1$$

Рассмотрим способ удлинения наименьшего представления $z_0$.

$$z_0=\frac{2^{2+\sum_{i=1}^{n}\alpha_i}}{3^{n}}-\frac{2^{\sum_{i=1}^{n}\alpha_i}}{3^{n}}-\frac{2^{\sum_{i=2}^{n}\alpha_i}}{3^{n-1}}-\frac{2^{\sum_{i=3}^{n}\alpha_i}}{3^{n-2}}-...-\frac{2^{\alpha_n}}{3}-1$$

$$z_0=\frac{2^{4+\sum_{i=1}^{n}\alpha_i}}{3^{n+1}}-\frac{2^{2+\sum_{i=1}^{n}\alpha_i}}{3^{n+1}}-\frac{2^{\sum_{i=1}^{n}\alpha_i}}{3^{n}}-\frac{2^{\sum_{i=2}^{n}\alpha_i}}{3^{n-1}}-...-\frac{2^{\alpha_n}}{3}-1$$

Осуществим преобразования по следующей схеме.

$$z_0\stackrel{3\frac{z+1}{2^{\alpha_n}}}{\longrightarrow}z_1\stackrel{3\frac{z+1}{2^{\alpha_{n-1}}}}{\longrightarrow}z_2\stackrel{3\frac{z+1}{2^{\alpha_{n-2}}}}{\longrightarrow}z_3...\stackrel{3\frac{z+1}{2^{\alpha_{1}}}}{\longrightarrow}z_n$$

Получим

$$z_n=\frac{16}{3}-\frac{4}{3}-1=3$$

При этом преобразование по правилу (2) переводит тройку саму в себя.
Поэтому любой нечётный зет с конечным разложением по форме (1) существует одновременно с существованием конечного представления тройки в этой форме.

5] Нечётные числа, имеющие только бесконечное разложение.
Докажем, что конечных $z\in\mathbb N, z\mod 2\equiv 1$ , имеющих лишь бесконечное разложение по форме (1) не существует.
Доказывать будем от противного. Пусть такие зет существуют. Тогда среди них есть минимальный, который обозначим $z_0$. Очевидно, что $z_0>3$, это проверяется подбором.
Для удобства записи бесконечного случая в форме (1) переобозначим индексы у альф в обратном порядке.

$$z_0=-1-\sum_{j=1}^{\infty}\frac{2^{\sum_{i=1}^{j}\alpha_i}}{3^j}$$

Введём параметр сходимости ряда $p$.

$$p=\prod_{j=1}^{\infty}\frac{2^{\alpha_j}}{3^j}$$

При $p<1$ ряд сходится, при $p>1$ ряд рассходится.
Введём $k$ое приближение к параметру $p$, $k\in\mathbb N$.

$$p_k=\prod_{j=1}^{k}\frac{2^{\alpha_j}}{3^j}$$

Рассмотрим случай сходящегося ряда. Тогда имеем логическое противоречие, так как $z_0\in\mathbb N$ оказывается отрицательным числом.
Теперь рассмотрим случай рассходящегося ряда.
Так как ряд рассходится, то $\exists l\in\mathbb N$ такое, что $\forall m\in\mathbb N, m<l$ имеем $p_m<1$, но при этом $p_l>1$.
Тогда произведём преобразования по следующей схеме.

$$z_0\stackrel{3\frac{z+1}{2^{\alpha_1}}}{\longrightarrow}z_1\stackrel{3\frac{z+1}{2^{\alpha_{2}}}}{\longrightarrow}z_2\stackrel{3\frac{z+1}{2^{\alpha_{3}}}}{\longrightarrow}z_3...\stackrel{3\frac{z+1}{2^{\alpha_{l}}}}{\longrightarrow}z_l$$

Имеем $z_l<z_0$, так как $p_l>1$.
Получили противоречие из-за того, что у нас $z_0$ является минимальным зетом, не имеющим конечного разложения.
Из-за конечности цепочки преобразований число $z_l$ также должно иметь только бесконечный вариант разложения по форме (1).
Отсюда следует, что конечных зет, имеющих только бесконечное разложение по форме (1), не существует.

6] Вывод.
Было показано, что $\forall z\in\mathbb N, z\mod 2\equiv 1$, кроме бесконечно больших, существует цепочка преобразований, которая приводит к трём и каждый элемент которой представим в форме (1) при условии существования представления в форме (1) тройки.
Но ведь $3=\frac{16}{3}-\frac{4}{3}-1$. Поэтому $\forall 3y\in\mathbb N, y\mod 2\equiv 1$, кроме бесконечных, представим в конечном варианте формы (1).
А это значит, что гипотеза $3x+1$ верна.