Самая простая нерешённая задача — гипотеза Коллатца [Veritasium]
[музыка] Когда об этой задаче рассказывают молодым математикам, их сразу предупреждают: не стоит за неё браться. Вы только зря потратите время. Простую навид гипотезу не смогли доказать лучшие умы человечества.
Знаменитый математик Пол Эрди как-то сказал: "Математика ещё не созрела для таких вопросов". Её суть: выберите любое число.
У нас есть два правила. Если число нечётное, умножаем его на 3 и добавляем 1. 3 на 7 — 21 + 1, 22. Если же число чётное, делим его на 2. 22 делить на 2 — 11. Продолжаем действовать по тем же правилам.
11 нечётно, значит, умножаем на 3 + 1 — 34. 34 делим на 2, 17. Нечётное, умножаем на 3, 51 + 1 — 52. Чётное, делим на 2 — 26. Снова чётное, делим на 2 — 13. Нечётное, умножаем на 3, 39 + 1 — 40. Чётное, значит, делим на 2 — 20, делим на 2 — 10, делим на 2 — 5.
Нечётное, умножаем на 3 + 1 — 16, делим на 2 — 8, ещё на 2 — 4, 2 делим на 2 — 1. Один нечётный, значит, умножаем на 3 и прибавляем 1, получаем 4. Из четырёх получаем двойку, затем снова единицу. Получается цикл с минимальным значением один.
Гипотеза звучит так: любое положительное целое число, если следовать алгоритму, обязательно попадает в цикл 4-2-1. Гипотеза носит имя Лотара Колласа, немецкого математика, который, как считается, пришёл к этой идее в 30-х годах прошлого века. Но эта задача им также известна как гипотеза Улама, теорема Катани, гипотеза ту, алгоритм Хаса.
Серая последовательность просто 3N + 1. Как эта гипотеза обрела такую славу в профессиональной среде? Надо уточнить: слава — это весьма дурная. Так что стоит кому-то публично признать, что над ней работает, все покрутят пальцем у виска.
Числа, которые получаются в ходе преобразований, тяжело предсказать, потому что подобно граду в облаках, значения то опускаются, то поднимаются. Но рано или поздно все падают до единицы, по крайней мере, мы так считаем для удобства.
Представьте, что числа обозначают высоту над землёй. Так, число 26 находится на высоте 26 м. Если подставить его в 3X + 1, оно сначала поднимется до 40, а потом за 10 шагов опустится до единицы.
10 можно назвать полным временем остановки. Но если взять соседнее число 27, оно будет скакать по самым разным высотам, добравшись аж до отметки 9232, что, продолжая аналогию, выше горы Эверест. Но даже этому числу суждено рухнуть на землю. Правда, ему потребуется уже 111 шагов, чтобы дойти до единицы и застрять в 4-2-1.
Когда путь одного числа отличается даже от соседнего, как вообще подступиться к доказательству подобной гипотезы? Математики были в растерянности: думали, что это разработка советских учёных, призванная застопорить американскую науку. И у них это получилось, потому что никто не мог добиться успеха в решении задачи, хотя она и ребенку понятна.
Мировой эксперт по этой проблеме, познакомившись, как-то болтали, и он мне говорит: "Даже не думай, не суйся туда, если хочешь построить карьеру. Не надо с этого начинать, не пиши никаких статей на эту тему, займись сперва нормальной математикой". Пожалей себя.
Алекс Канторович не послушался. Они с Яковом Синайем стали искать закономерности, поведения и пути, которые они проделывают. То, что он случаен. Вот путь случайно выбранного большого числа. Сначала взлёт вверх, а затем столь сильный спад, что значение числа просто не рассмотреть.
Если сделать график логарифмическим, в его колебаниях прослеживается нисходящий тренд, как рынок акций в день обвала. Это не случайно. И то и другое — примеры геометрического броуновского движения.
То есть если взять логарифм, вычесть колебания, окажутся случайными, как если бы на каждом шаге бросали монетку: орёл — линия идет вверх, решка — вниз. У 3X + 1 тоже поведение, что у случайных скачков на бирже. Только в долгосрочной перспективе рынки акций обычно всё-таки растут, а 3X + 1 падает.
Ещё можно посмотреть на старший разряд чисел Градин. Вот последовательность, которая получается, если начать с тройки: потом начинается с единицы, с двойки, тройки и так далее. И представим всё в виде гистограммы.
Проделаем то же самое для последовательности, которая начинается с четырёх. Она короткая для той, что начинается с пяти, шести и семи. Каждый раз мы просто считаем, сколько чисел в последовательности, с какой цифры начинаются, и добавляем результат в гистограмму.
По мере того, как мы получаем всё больше и больше данных, соотношение высоты столбиков становится более упорядоченным. Для первого миллиарда последовательностей самой частой первой цифрой оказывается единица: почти 30% всех случаев, 17,5% — двойка, 12% — тройка.
И чем цифра больше, тем реже она оказывается впереди. Девятка, например, менее чем в 5% случаев. Такой расклад характерен не только для чисел Градин. Примеров много: это и население стран, и стоимость компаний, все физические константы, числа Фибоначчи и много чего ещё.
Такое распределение известно как закон Бенфорда. С его помощью даже ловят мошенников: если цифры налоговых деклараций подчиняются закону Бенфорда, скорее всего, всё честно. Если нет — возможно, вы что-то скрываете. Этот закон также помогает заметить аномалии при подсчёте голосов. Главное — знать, как им пользоваться.
Лучше всего он работает, когда массив чисел включает величины с разбросом в несколько порядков, как в случае 3X + 1. Но закон Бенфорда не расскажет, все ли числа попадают в цикл 4-2-1. Для этого нужен другой метод.
На первый взгляд странно, что 3X + 1 приводит все числа к единице, учитывая, что чётных и нечётных чисел поровну. И тогда, как нечётные возрастают более чем в три раза, чётные уменьшаются всего вдвое. Напрашивается вывод, что все последовательности должны идти вверх, а не вниз.
Но есть один нюанс: каждый раз, когда вы умножаете нечётное число на три и прибавляете один, оно превращается в чётное. А значит, следующим шагом мы всегда будем делить его на два. Так что в итоге нечётные числа не утраивают, а умножаются примерно на 3/4.
Можно игнорировать +1 для больших чисел, она роли не играет. 3/2 — это максимальный рост, который может получить нечётное число за один шаг. Представим путь одного нечётного числа к следующему нечётному. Умножаем на три, прибавляем один — получается чётное число.
В половине случаев деление на два тут же вернёт нас к нечётному, но каждое четвёртое число делить придётся дважды. То есть, значит, следующее нечётное число — это 3/4 от предыдущего. Придётся делить на 8, чтобы получить следующее, каждая раз на 16 и так далее.
Взяв среднее геометрическое, мы увидим, что в среднем, чтобы добраться от одного нечётного числа к другому, нужно умножить его на 3/4, что меньше единицы. Выходит, чисто статистически последовательности 3X + 1 уменьшаются чаще, чем растут.
Возьмём число 341. Умножим на 3, получим 24, делим на два, и снова на два, и снова, и снова, и снова — 10 раз подряд, пока не дойдём до единицы. Пути, которые проходят числа Градин, удобно визуализировать, показав, как каждое число связано с соседним в своей последовательности. Это называется ориентированный граф.
Он похож на дерево или на множество сливающихся вместе ручьев. Если гипотеза верна, значит, в любом этом графе бесконечное количество ручейков сойдутся вместе, образуя мощный зацикленный поток 4-2-1.
Существует модификация этого способа визуализации. Граф слегка поворачивается на каждом шаге против часовой на нечётных числах и по часовой на чётных. В итоге получается структура, напоминающая кораллы или водоросли. Меняя угол поворота, можно создавать вот такие прекрасные формы, похожие на что-то, порождённое природой.
Гипотеза окажется неверной в двух случаях. Во-первых, если мы вдруг найдём число, подставив которое в алгоритм, мы получим бесконечность. По какой-то причине на него просто не будет действовать та же сила притяжения, что на другие числа.
Второй вариант — где-то есть последовательность, которая образует собственный замкнутый цикл, числа в нём окажутся вне основного графа. Но пока что ни такого цикла, ни бесконечной последовательности никто не нашёл. И не сказать, что плохо старались математики. Простым перебором проверили все числа вплоть до 2 в 68 степени: это 295 квинтиллионов, 147 квадриллионов, 905 триллионов, 179 миллиардов, 352 миллиона, 8256 чисел.
Мы точно знаем, что каждая из них в конце концов приходит к единице. Проверено уже почти 300 квинтиллионов чисел, и ни одно из них не опровергает гипотезу. Более того, на основе этих данных математики рассчитали: если и существует какой-то цикл помимо 4-2-1, он состоит из как минимум 186 миллиардов чисел.
Всё указывает на то, что гипотеза верна, но всё ещё не доказано. Математики пытались подтвердить её следующим образом: они построили диаграмму рассеивания со всеми начальными числами по оси X и числами из последовательности по оси Y.
Если мы сможем доказать, что в любой последовательности 3X + 1 есть число меньше исходного, мы подтвердим гипотезу: любое исходное число приведёт нас к числу поменьше, которое, выступая исходным для собственной последовательности, приведёт нас к числу ещё меньше и так далее, вплоть до единицы.
То есть единственный возможный исход для любой последовательности — это 4. Доказать этого до сих пор не удалось, но в 1976 Риха Терес показал, что почти все последовательности включают в себя значение ниже исходного X.
В 7-м измерении определили, насколько ниже: до X в степени 0.869. Позднее степень уточнили до 0.7925. Здесь "почти все числа" означает, что при X, стремящемся к бесконечности, доля значений X последовательности, у которых есть число меньше значения ограничивающей функции, стремится к единице.
Недавно, в 2019, один из выдающихся математиков современности, Тери Тау, смог доказать, что 3X + 1 подчиняется ещё более строгим ограничениям. Он показал, что почти все числа будут меньше, чем значение любой функции F(X), при условии, что функция стремится бесконечности при X, стремящемся к бесконечности.
При этом функция может расти сколь угодно медленно: скажем, логарифм X или логарифм логарифма, или логарифм логарифма логарифма. Это позволяет утверждать, что сколь угодно малые числа есть в последовательности почти любого исходного числа.
На выступлении в 2020 Рита сказал: "Лучше этого может быть разве что прямое доказательство гипотезы". Его достижение впечатляет, но это всё ещё не доказательство. Почему мы не можем подтвердить эту гипотезу? Может, потому что она неверна? Математики вечно ищут доказательства. Но что насчёт опровержения?
Пару лет назад была такая же ситуация: изо всех сил искал одно доказательство, на тот момент уже года три ничего не получалось. А затем я нашёл контрпример и понял, что переформулировать. И буквально через месяц у меня всё сошлось. Возможно, нам стоит больше внимания уделять поиску контрпримеров.
Помните, как число 27 взлетело до точки 9232? Вот график исходных чисел до 10,000, где по оси Y отмечены максимальные значения для каждого из них. Ось Y заканчивается на 100,000, но этот график далеко не полный. Исходное достигает 27.
Никто не доказал, почему какое-нибудь другое число не может вдруг устремиться в бесконечность. Чтобы опровергнуть гипотезу, нужно всего одно такое число или какое-то множество чисел, которые образуют собственный цикл, не связанный с основным графом. Пока мы знаем только про петлю 4-2-1, но стоит подключить отрицательные числа, происходит кое-что любопытное.
Пользуясь тем же алгоритмом, мы получаем не один, не два, а целых три независимых друг от друга цикла. И появляются они очень рано: на значении -1 и -5. Если среди отрицательных чисел встречаются отдельные циклы, почему их не может быть среди положительных?
Один из самых убедительных аргументов в пользу гипотезы — это доказательство Рита о том, что почти все числа имеют в своих последовательностях сколь угодно малые. Однако это не значит доказать, что так делают все числа.
Сколько полных квадратов встречается в промежутке от одного до 100? Ответ: 10. То есть 10% от заданного множества — полные квадраты. А если взять промежуток от одного до тысячи? Полных квадратов 31, то есть из этого множества лишь 3.1% полные квадраты.
И чем больше мы берём промежуток, тем ниже будет этот процент. Можно утверждать, что в пределе большинство чисел не являются полными квадратами. Это значит, что их доля стремится к единице при N, стремящемся к бесконечности.
Но мы знаем, что полных квадратов бесконечно много и точно знаем, где их искать. Вручную удалось проверить все числа до 2 в 68 и все они согласуются с гипотезой. Кажется, что мы бы уже нашли контрпример, если бы он был.
Но в масштабах всех чисел 2 в 68 — это ничто. Гипотеза, выдвинутая в 1919 году Эрди, утверждала, что почти любое натуральное число, сколь угодно большое, можно разложить на нечётное количество простых множителей. Это о проверке Брайна Хейзела в 1958, когда он нашёл контрпример.
Контрпримером оказалась 1.45 на 10 в степени 361. Это в 10 в 340 степени больше, чем все числа, проверенные по гипотезе Колласа. Можно также представить эту задачу в виде простой программы, запущенной на машине Тьюринга.
Исходное число — это входные данные, то есть 2 в 68 — это просто входная лента длиной 68 квадратов. Там могут быть нули, единицы или белые и чёрные ячейки. То, что машина привела все значения на ленте к единице, ещё не значит, что тоже самое она проделает с любой другой лентой.
Найти число, которое ведёт себя в алгоритме нужным нам образом, совсем несложно, при условии, что оно конечное. Если хотите, чтобы оно возрастало в полтора раза пять раз подряд, никаких проблем.
Нужно число, которое делает так 10 раз подряд, или 100, или 1,000 — любое можно легко вычислить. Но это всё ограничивается конечными величинами, и каждое число из тех, что проверяли, всегда обращается в единицу. Если контрпример существует, то подобрать его просто нереально.
Бесконечное множество — это слишком много, чтобы искать перебором. Просчитать 2 в тысячной степени чисел невозможно. Если искать, то каким-нибудь более разумным способом, нежели вручную.
Я 20 лет занимаюсь этой проблемой и начал задумываться, а так ли мы в ней уверены? Сложно доказать теорему, если в ней ошибка. Что если мы так долго бьёмся над этой гипотезой, потому что она не верна?
2 в 68 — это ещё не доказательство. То есть расчёты все верные, просто они не означают, что где-то там не может быть числа, ветвь которого стремится в бесконечность. Конечно, есть вариант узнать невозможно: задача просто нерешаемая.
В 1987 Джон Конвой создал обобщение задачи 3X + 1 — математическую машину под названием Транс и смог доказать, что она полна по Тьюрингу, то есть имеет функционал современного компьютера. Но это также значит, что она подвержена проблеме остановки, когда машина производит бесконечные вычисления, не выдавая никакого результата.
3X + 1 не имеет решения. Но учитывая имеющиеся данные, возможно, мы так и не сможем подтвердить или опровергнуть гипотезу Колласа. В школе нам рассказывают, как много всего мы знаем. Всё это враньё, неправда.
Вот у нас есть простенькая задачка и что, мы не можем её решить? Вы чего? А всё просто — математика сложная штука. Задачи, которые удалось решить, но нам просто повезло. Странно, что мы с ними не застряли, так же как с этой.
Всю жизнь числа казались мне чем-то очень последовательным, закономерным, симметричным, повторяющимся. И только сейчас я понимаю, что всё куда сложнее. Это хорошо видно на примере коралловой визуализации: из простой математической операции получается нечто сложное, будто рожденное самой природой.
И до сих пор непокорно человеку. Содержит числа, или где-то обнаружится отдельная самостоятельная ветвь, существующая независимо от всего остального, или уходящая в бесконечность.
Почему мы до сих пор этого не знаем? Не потому ли, что Эрди был прав и математика ещё не созрела для таких вопросов?