# Пол Эрдёш о гипотезе Коллатца: «Математика еще не созрела для таких вопросов»

Источник: https://www.youtube.com/watch?v=094y1Z2wpJg
Канал: Veritasium
Опубликовано: 30.07.2021

---

В мире математики существует простая задача, способная разрушить карьеру любого молодого ученого. Гипотеза Коллатца, также известная как «проблема 3n+1», формулируется настолько легко, что ее поймет даже школьник, но лучшие умы планеты десятилетиями не могут ее доказать. Создатель канала Veritasium Дерек Мюллер вместе с ведущими мировыми математиками разбирается, почему эта обманчивая простота скрывает одну из глубочайших тайн теории чисел и почему некоторые считают ее абсолютно нерешаемой.

## 🔢 Суть гипотезы: Простые правила и бесконечные циклы
[[JUMP:0:00]]

Гипотеза Коллатца строится всего на двух элементарных правилах, которые применяются к любому выбранному положительному целому числу [0:27]:

*   Если число нечетное, его нужно умножить на 3 и прибавить 1 ($3n+1$) [0:27].
*   Если число четное, его нужно разделить на 2 ($n/2$) [0:41].

Возьмем для примера число 7 [0:27]. Применяя правила последовательно, мы получаем цепочку: 7 переходит в 22 [0:27], затем в 11, 34, 17, 52, 26, 13, 40 [0:54], 20, 10, 5 [1:06], 16, 8, 4, 2 и, наконец, в 1 [1:20]. 

Достигнув единицы, которая является нечетным числом, мы снова применяем правило «умножить на 3 и прибавить 1», получая 4, которое снова делится на 2 и переходит в 1 [1:20]. Таким образом, число попадает в бесконечный цикл «4–2–1» [1:20]. 

Суть гипотезы заключается в утверждении: абсолютно любое положительное целое число, к какому бы мы ни применили эти правила, в конечном итоге придет к циклу «4–2–1» [1:33]. 

Эта задача известна под множеством разных названий [1:47]:

*   Гипотеза Коллатца — в честь немецкого математика Лотара Коллатца, который, как считается, предложил ее в 1930-х годах [1:47].
*   Гипотеза Улама [2:00].
*   Проблема Какутани [2:00].
*   Гипотеза Твейтса [2:00].
*   Алгоритм Хассе [2:00].
*   Сиракузская проблема [2:00].
*   Проблема 3n+1 [2:00].

Великий венгерский математик Пол Эрдёш однажды признал, что современная математика «еще просто не созрела для таких вопросов» [0:13].

## 🏔️ «Числа-градины» и хаотичные траектории
[[JUMP:2:12]]

Числа, получаемые в процессе применения алгоритма $3n+1$, математики называют «числами-градинами» (hailstone numbers) [2:12]. Это связано с тем, что их значения резко взлетают и падают, подобно кусочкам льда в грозовом облаке, прежде чем неизбежно упасть на землю — то есть прийти к единице [2:26]. 

Поведение соседних чисел может кардинально отличаться, что лишает исследователей очевидной логики:

*   Число 26 начинает свой путь с «высоты» 26 метров, поднимается максимум до 40 и достигает единицы всего за 10 шагов (это время называют полным временем остановки) [2:40].
*   Следующее за ним число 27 совершает невероятное путешествие: оно хаотично скачет по числовой оси, взлетая до пикового значения 9 232 (что выше горы Эверест), и тратит ровно 111 шагов, прежде чем упасть в цикл «4–2–1» [2:52-3:05].

Такая непредсказуемость ставит ученых в тупик. По словам Дерека Мюллера, в разгар Холодной войны в академических кругах США даже ходила шутка, что эта задача была придумана советскими спецслужбами с целью затормозить развитие американской науки, поскольку каждый, кто начинал над ней думать, полностью выпадал из реальной работы [3:33]. 

Авторитетный специалист по проблеме $3n+1$ Джеффри Лагариас вспоминает, как во время его учебы в колледже наставники строго запрещали ему тратить время на эту тему, советуя сначала «заняться настоящей математикой», чтобы построить карьеру [3:47-4:01].

## 📊 В поисках закономерностей: Броуновское движение и Закон Бенфорда
[[JUMP:4:15]]

Несмотря на предостережения, некоторые математики пытались найти структуру в этом хаосе. Алекс Конторович и Яков Синай проанализировали траектории «чисел-градин» и обнаружили, что в их поведении скрыты строгие статистические законы [4:15].

Если построить график изменения логарифма значений случайного крупного числа в последовательности Коллатца, то после удаления линейного тренда оставшиеся колебания будут выглядеть абсолютно случайно [4:40]. Поведение графика напоминает динамику фондового рынка в неудачный день [4:40]. 

Математически это описывается как геометрическое броуновское движение [4:40]. На каждом шаге процесс похож на подбрасывание монеты: орел — значение идет вверх, решка — вниз [4:53]. Разница лишь в том, что если фондовый рынок в долгосрочной перспективе имеет тенденцию к росту, то последовательности $3n+1$ неуклонно стремятся вниз [5:08].

Еще одно удивительное открытие связано с распределением первых цифр в последовательностях Коллатца. Если проанализировать миллиарды таких рядов, частота появления первой цифры в числах строго подчиняется закону Бенфорда [5:45-6:24]:

*   Цифра 1 является первой почти в 30% случаев [5:59].
*   Цифра 2 начинает числа примерно в 17,5% случаев [5:59].
*   Цифра 3 встречается на первом месте в 12% случаев [5:59].
*   Цифра 9 оказывается первой менее чем в 5% случаев [6:12].

Закон Бенфорда широко применяется на практике, например, для выявления мошенничества в налоговых декларациях или при проверке результатов выборов [6:36-6:49]. Тем не менее, этот статистический закон не дает ответа на главный вопрос: гарантирует ли он, что абсолютно все числа достигнут единицы [7:02].

## 📉 Математическая гравитация: Почему числа стремятся к единице
[[JUMP:7:02]]

На первый взгляд утверждение, что все числа уменьшаются до единицы, кажется нелогичным. В числовом ряду поровну четных и нечетных чисел [7:15]. При этом нечетные числа при операции $3n+1$ увеличиваются более чем в три раза, а четные при делении на 2 уменьшаются лишь вдвое [7:15]. Логично предположить, что в среднем последовательность должна расти, а не сжиматься [7:29]. 

Однако здесь кроется важная математическая закономерность:

*   Любое нечетное число после умножения на 3 и прибавления 1 обязательно становится четным [7:29-7:43].
*   Это значит, что следующим шагом всегда будет деление на 2 [7:43].
*   Следовательно, реальный рост нечетного числа за один цикл составляет не 3, а примерно 3/2 (1,5) [7:43].

Если рассмотреть цепочку переходов от одного нечетного числа к другому, то в половине случаев после деления на 2 мы снова получим нечетное число [7:57]. Однако в четверти случаев число разделится на 4, в одной восьмой — на 8, в одной шестнадцатой — на 16 и так далее [8:10-8:23]. 

Если рассчитать среднее геометрическое этих вероятностей, выяснится, что при переходе от одного нечетного числа к следующему значение в среднем умножается на 3/4 [8:38]. Поскольку 3/4 меньше единицы, последовательности имеют сильную статистическую тенденцию к уменьшению [8:38].

Наглядным примером служит число 341. После применения формулы ($341 \times 3 + 1$) получается 1024 [8:51]. Это число является степенью двойки ($2^{10}$), и последовательное деление на 2 за 10 шагов опускает его до 1 [8:51-9:03].

Эти переходы можно визуализировать в виде направленного графа [9:03]. Он напоминает гигантскую речную систему, где ручьи и реки со всей бесконечной числовой оси впадают в один общий поток, ведущий к циклу 4–2–1 [9:16-9:30]. Если при визуализации поворачивать ветви графа (налево для нечетных, направо для четных чисел), получаются удивительные органические структуры, напоминающие кораллы или водоросли [9:30-9:57].

## 🔎 Границы вычислений и великий прорыв Терри Тао
[[JUMP:9:57]]

Теоретически существует всего два сценария, при которых гипотеза Коллатца может оказаться неверной [9:57]:

1.  Наличие числа, последовательность которого уходит в бесконечность, преодолевая «гравитацию» алгоритма [9:57-10:10].
2.  Существование замкнутого цикла чисел, который изолирован от основного графа и не пересекается с циклом 4–2–1 [10:10-10:23].

Ученые проверили с помощью суперкомпьютеров колоссальный массив данных — все числа вплоть до $2^{68}$ (это более 295 квинтиллионов) [10:36-10:55]. Ни одного исключения найдено не было [10:55]. Более того, расчеты показывают, что если альтернативный цикл и существует, то его длина должна составлять не менее 186 миллиардов чисел [10:55-11:10].

В попытках найти строгое доказательство математики пытались показать, что для любого стартового числа в его последовательности обязательно найдется значение, которое меньше исходного [11:22-11:34]. Если это так, то по принципу бесконечного спуска любое число рано или поздно дойдет до минимального цикла [11:34-11:47].

История этого направления полна важных вех:

*   В 1976 году Рихо Террас доказал, что «почти все» последовательности Коллатца достигают значения ниже своего стартового числа [11:47-12:00].
*   В 1979 году этот предел был улучшен: почти все числа опускаются ниже значения $x^{0.869}$ [12:00-12:12].
*   В 1994 году планка опустилась еще ниже — до $x^{0.7925}$ [12:12].

Понятие «почти все» в математике имеет строгое определение: доля чисел, не удовлетворяющих этому условию, стремится к нулю по мере того, как рассматриваемый диапазон стремится к бесконечности [12:26].

В 2019 году один из величайших математиков современности Теренс Тао совершил прорыв [12:38]. Он доказал, что для почти всех чисел значение в последовательности гарантированно опустится ниже любой произвольной функции $f(x)$, при условии, что сама функция стремится к бесконечности (это может быть даже крайне медленно растущая функция вроде $\log \log \log x$) [12:38-13:03]. 

Сам Теренс Тао охарактеризовал свой результат как максимальное приближение к гипотезе Коллатца, которого можно достичь без ее фактического полного доказательства [13:16].

## ⚠️ Ловушка бесконечности: Почему $2^{68}$ — это «ничто»
[[JUMP:13:28]]

Несмотря на успехи Терри Тао и проверку огромного массива чисел, радоваться рано. Математики предупреждают, что отсутствие контрпримера на малых масштабах не доказывает истинность гипотезы. Алекс Конторович делится личным опытом: он три года безуспешно пытался доказать одну теорему, пока не нашел опровергающий контрпример, что позволило ему переформулировать задачу и решить ее за месяц [13:40-13:53]. По его мнению, научному сообществу следует выделять больше ресурсов на поиск контрпримеров для проблемы 3n+1 [13:53].

Для сомнений есть веские основания:

*   Существование отрицательных циклов. Если мы применим те же правила 3n+1 к отрицательным числам, то обнаружим не один, а целых три независимых изолированных цикла (начинающихся с -5, -17 и -1) [14:45-14:58]. Объяснения, почему на положительной стороне оси цикл один, а на отрицательной их несколько, до сих пор нет [14:58].
*   Магия понятия «почти все». Математический факт: доля идеальных квадратов (1, 4, 9, 16...) стремится к нулю при приближении к бесконечности [15:11-15:51]. То есть «почти все» числа на свете не являются квадратами [15:51-16:05]. Тем не менее, квадратов существует бесконечно много [16:05].
*   Иллюзия надежности малых чисел. Проверенное компьютерами число $2^{68}$ кажется гигантским, но в масштабах математической бесконечности это ничтожно малая величина [16:18].

В истории науки уже были подобные прецеденты. В 1919 году Джордж Пойя выдвинул гипотезу (гипотеза Пойи), утверждавшую, что у большинства натуральных чисел до любого заданного предела количество простых делителей нечетно [16:18-16:31]. Гипотеза казалась незыблемой, пока в 1958 году Брайан Хазелгрув не опроверг ее [16:31-16:43]. Найденный им первый контрпример равнялся примерно $1,845 \times 10^{361}$ [16:43]. Это число в $10^{340}$ раз больше, чем весь объем чисел, проверенных для гипотезы Коллатца к сегодняшнему дню [16:43].

## 💻 Нерешаемая задача? Фрактальный код и теорема Гёделя
[[JUMP:18:17]]

Последовательность Коллатца можно представить как простейшую программу для машины Тьюринга, где начальное число — это входная лента [16:56-17:09]. Нам легко сконструировать число, которое будет вести себя строго определенным образом на протяжении любого конечного числа шагов (например, расти 100 или 1000 раз подряд) [17:21-17:47]. Но как только этот заданный интервал заканчивается, мы теряем контроль, и число неизбежно скатывается к единице [17:47]. 

По мнению специалистов, если контрпример существует, найти его методом случайного перебора на компьютерах невозможно — пространство поиска $2^{1000}$ физически недоступно для лобового анализа [17:47-18:00]. Его можно открыть только с помощью принципиально новых аналитических методов [18:00].

Существует и третий, наиболее интригующий вариант развития событий: гипотеза Коллатца может оказаться принципиально недоказуемой (неразрешимой) в рамках современной аксиоматики математики.

В 1987 году легендарный математик Джон Конвей создал обобщенную версию задачи 3n+1 — математическую систему под названием Fractran [18:56]. Конвей доказал, что Fractran является Тьюринг-полным языком, способным моделировать любые вычисления [19:09]. Это означает, что он напрямую сталкивается с классической проблемой остановки Тьюринга — принципиальной невозможностью предсказать, завершит ли программа свою работу или будет выполняться вечно [19:09-19:21].

Хотя это напрямую не доказывает неразрешимость оригинальной гипотезы Коллатца, работа Конвея наглядно демонстрирует: подобные системы легко могут уходить в область абсолютной математической неопределенности [19:21]. Возможно, человечество действительно столкнулось с задачей, ответ на которую мы не узнаем никогда.