Задача без роду и племени
Задачи и модели в математике обычно не возникают ниоткуда. Они могут родиться из практики или из потребностей других наук. Могут прийти внутренних потребностей самой математики, -- так из простенькой задачи шаг за шагом вырастала гипотеза Римана.
Задача 3n+1 взялась ниоткуда. У нее нет предыстории, нет практической пользы, она не возникла как проявление какой-то внутренней математической проблемы. Нет надежных указаний на то, кто придумал эту задачу и зачем, до середины XX века она прозябала в статусе безродной сироты. Часто ее приписывают немецкому математику Лотару Коллатцу, но сам он отрицал свое авторство.
С. Какутани, впервые услышавший о проблеме «3n+1» в 1960 году, сообщил Джеффри Лагариасу:
Целый месяц весь Йельский университет безрезультатно трудился над этой задачей. Такая же участь постигла исследователей Чикагского университета, когда я им сообщил о ней. Ходила шутка, что эта задача использовалась для заговора, имеющего целью снизить интенсивность математических исследований в США.
Задачу не удалось решить даже с приходом мощных компьютеров, хотя постановку ее вполне по силам понять смышленому молодому человеку десяти лет от роду.
Сизифов труд
Корней играет в Сизифа. Он берет натуральное число и начинает толкать его вверх по натуральному ряду, надеясь затолкать повыше. Правила игры такие. Если камень попал на нечетное число n, то Корнею разрешается затолкать его на число (3n+1). Если же камень попал на четное число n, то скатывается вниз на n/2.
Это же правило можно записать формулой:
Стартовав с некоторого натурального числа n, находят значение функции, к нему применяют её же, и так далее. Получается последовательность чисел -- траектория числа n.
Траектории первых натуральных числах собраны на одном рисунке:
Численные эксперименты (Tomas Oliverira e Silva (2011)) показывают, что в единицу приходят траектории всех чисел до 5 · 2⁶⁰ ≈ 5.754 × 10¹⁸. Поэтому естественной кажется следующая гипотеза Коллатца:
с какого натурального числа ни начни строить траекторию, она не будет расти бесконечно, а со временем скатится в цикл 1→4→2→1.
Задача Коллатца (Сиракузская задача, проблема 3n+1) – доказать или опровергнуть эту гипотезу. До сих пор это никому не удалось, но в этом году получено существенное продвижение.
Модель 3n+1 описывает дискретную динамическую систему. Ее элементы -- натуральные числа; они "движутся" по своим траекториям по закону f(n). Траектории эти задаются очень просто и при том демонстрируют сложное поведение. Математики любят такие "игрушечные" модели -- на них очень удобно экспериментировать, выдвигать и проверять гипотезы. Дискретные динамические системы -- это передний край науки; здесь разрабатывают новые инструменты и методы и поставляют их в старые области, в том числе теорию чисел и в комбинаторику.
Есть серьезный обзор положения дел на 2010 год от Джеффри Лагариаса.
И тут пришел Тао
8 сентября 2019 года Теренс Тао доказал, что гипотеза Коллатца «почти» верна для «почти» всех чисел.
Тао использует вероятностный подход. Слова «почти для всех чисел» означают, что если выбрать натуральное число наугад (по некоторой вероятностной мере), то с вероятностью 1 оно окажется хорошим.
Это серьезный прогресс в почти вековой работе над этой задачей.
Журнал «Quanta» опубликовал внятный разбор статьи Тао. Он заканчивается так:
Окончательное доказательство гипотезы должно будет основываться на другом подходе. Результат Тао – это одновременно триумф и предупреждение любителям: когда вам кажется, что уже ухватили эту задачу за хвост, она все равно ускользает из рук.
«К гипотезе Коллатца можно подойти сколь угодно близко», -- говорит Теренс Тао, но она все еще недоступна.
Еще 9 знаменитых нерешаемых задач, которые формулируются довольно просто.