[Перевод] Математики достигли прорыва в изучении «опасной» задачи
Математики считают гипотезу Коллатца «болотом», и предупреждают друг друга, что от неё стоит оставаться подальше. Однако теперь Теренс Тао достиг большего прогресса, чем кто бы то ни было за несколько десятилетий.
Возьмите любое число. Если оно чётное, поделите его на два. Если нечётное, умножьте на три, прибавьте один. Повторите. Любое ли число в итоге приходит к 1?
Опытные математики советуют новичкам держаться подальше от гипотезы Коллатца. Они называют её песней сирен: попади под её влияние, и можешь уже никогда не добраться до осмысленной работы.
Гипотеза Коллатца, возможно, простейшая из нерешённых задач математики — именно это и делает её такой предательски притягательной.
«Это очень опасная задача. Люди становятся одержимыми ею, при том, что она совершенно невозможна», — сказал Джеффри Лагариас, математик из Мичиганского университета, эксперт по гипотезе Коллатца.
Но в 2019 году один из лучших математиков мира осмелился подступиться к ней, и получил самый значимый из всех результатов, что были достигнуты за несколько десятилетий.
8 сентября 2019 Теренс Тао опубликовал доказательство, где показано, что гипотеза Коллатца, по меньшей мере, «почти» верна «почти» для всех чисел. И хотя результат Тао не является полным доказательством гипотезы, это очень серьёзный прорыв для задачи, не так-то легко раскрывающей все свои секреты.
«Я не ожидал решить задачу полностью, — сказал Тао, математик из Калифорнийского университета в Лос-Анджелесе. — Но у меня получилось сделать больше, чем я ожидал».
Головоломка Коллатца
Лотар Коллатц, вероятно, высказал одноимённую гипотезу в 1930-х годах. Задача звучит, как фокус для вечеринок. Возьмите любое число. Если оно чётное, поделите его на два. Если нечётное, умножьте на три, прибавьте один. Получится новое число. Примените те же правила для него. Гипотеза говорит о том, что произойдёт, если настойчиво повторять этот процесс.
Интуиция подсказывает, что начальный номер влияет на конечный результат. Возможно, некоторые числа в итоге будут уменьшаться до 1. Возможно, другие числа будут увеличиваться до бесконечности.
Однако Коллатц предсказал, что это не так. Он предположил, что если вы начнёте с положительного целого числа, и достаточно долго будете повторять указанную последовательность, то с любого начального числа придёте к 1. А придя к единице, правила гипотезы поймают вас в бесконечную петлю: 1, 4, 2, 1, 4, 2, 1, и так далее, до бесконечности.
С годами многих любителей задач притягивала привлекательная простота гипотезы Коллатца, или «задачи 3х+1», как её ещё называют. Математики проверили уже квинтиллион примеров (это число с 18 нулями), не найдя ни единого исключения из предсказания Коллатца. Вы и сами можете попытаться проверить несколько примеров с любым из множества имеющихся в интернете «калькуляторов Коллатца». В интернете полно необоснованных любительских доказательств гипотезы, авторы которых утверждают, что им удалось её доказать или опровергнуть.
«Вам нужно только уметь умножать на 3 и делить на 2, и вы уже можете начать играться с ней. И это очень заманчиво», — сказал Марк Чамберленд, математик из Колледжа Гриннела, записавший популярное на YouTube видео об этой задаче под названием «Простейшая из невозможных задач».
А вот истинных доказательств немного.
В 1970-х математики показали, что почти все последовательности Коллатца — список чисел, которые вы получаете при повторении процесса — в итоге приходят к числу меньшему, чем начальное. Это было слабое свидетельство того, что почти все последовательности Коллатца приводят к 1, но тем не менее, оно было. И с 1994 года до полученного в 2019 году результата Тао, рекорд по демонстрации минимального значения удерживал Иван Корец. Другие работы сходным образом пытались атаковать задачу, не приближаясь к её главной цели.
«Мы, на самом деле, не понимаем вопроса Коллатца достаточно хорошо, поэтому значительных работ по этому вопросу не было», — сказал Каннан Саундарараджан, математик из Стэнфордского университета, работавший над этой гипотезой.
Тщетность этих попыток привела многих математиков к заключению, что эта гипотеза просто недоступна при текущем уровне знаний, и что им лучше тратить своё время на другие исследования.
«Задача Коллатца известна своей сложностью — настолько, что математики обычно предваряют каждое её обсуждение предупреждением не тратить на неё время», — сказал Джошуа Купер из университета Южной Каролины.
Неожиданный совет
Впервые Лагариас заинтересовался этой гипотезой, будучи студентом, не менее 40 лет назад. Десятилетиями он был неофициальным куратором всего, что с ней связано. Он набрал целую библиотеку связанных с нею работ, и в 2010 опубликовал некоторые из них в виде книги под названием: «Решающий вызов: задача 3х +1».
«Теперь я гораздо больше знаю об этой задаче, и всё равно могу сказать, что решить её невозможно», — сказал Лагариас.
Обычно Тао не тратит своё время на невозможные задачи. В 2006 году он получил Филдсовскую премию, высшую награду по математике, и считается одним из лучших математиков своего поколения. Он привык решать задачи, а не гоняться за воздушными замками.
«Это риски, связанные с профессией математика, — сказал он. — Можно стать одержимым одной из больших известных задач, находящихся за пределами возможностей любого человека, и потерять кучу времени».
Однако у Тао не всегда получается противостоять искушениям из этой области. Каждый год он тратит один-два дня на самые известные из нерешённых задач по математике. С годами он делал несколько подходов и к гипотезе Коллатца, но безуспешно.
Затем в августе анонимный читатель оставил в блоге Тао комментарий. Он предложил попробовать решить гипотезу Коллатца «почти для всех» чисел, не пытаясь полностью доказать её.
«Я не ответил, однако это заставило меня снова задуматься об этой задаче», — сказал Тао.
И он понял, что гипотеза Коллатца была в некотором роде похожа на особые типы уравнений — дифференциальные уравнения в частных производных — появлявшихся в наиболее значительных результатах, полученных им за время его карьеры.
Входы и выходы
Дифференциальные уравнения в частных производных (ДУЧП) можно использовать для моделирования многих из наиболее фундаментальных физических процессов во Вселенной, вроде эволюции жидкостей или прохождении гравитационных волн сквозь пространство-время. Они появляются в ситуациях, когда будущее положение системы — например, состояние пруда через пять секунд после броска в него камня — зависит от вкладов двух или более факторов, типа вязкости и скорости воды.
Казалось бы, у сложных ДУЧП есть мало что общего с таким простым арифметическим вопросом, как гипотеза Коллатца.
Но Тао понял, что у них есть нечто общее. В ДУЧП можно подставить значения, получить другие значения, повторить процесс — и всё это для понимания будущего состояния системы. Для каждого заданного ДУЧП математикам нужно знать, приведут ли начальные значения на входе к бесконечным значениям на выходе, или же уравнения всегда будут выдавать конечные значения, вне зависимости от начальных.
Теренс Тао, вдохновлённый комментарием в своём блоге, достиг крупнейшего за десятилетия прогресса в изучении гипотезы Коллатца
Для Тао эта цель была того же порядка, как и то, всегда ли вы получите одно и то же значение (1) из процесса Коллатца, вне зависимости от начального значения. В результате он понял, что техники изучения ДУЧП могут подойти для изучения гипотезы Коллатца.
Одна особенно полезная техника использует статистический способ изучения долговременного поведения небольшого количества начальных значений (что-то типа небольшого количества начальных конфигураций воды в пруду) и экстраполирует результат на долгосрочное поведение всех возможных начальных конфигураций пруда.
В контексте гипотезы Коллатца представим, что мы начали с большой выборки чисел. Наша цель — изучить, как эти числа ведут себя, когда мы применяем к ним процесс Коллатца. Если почти 100% чисел в выборке приходят к 1 или очень близко к 1, можно заключить, что почти все числа будут вести себя так же.
Но чтобы это заключение было обоснованным, нужно очень тщательно составить выборку. Эта задача похожа на составление выборки участников голосования на выборах президента США. Для тщательного составления выборки из всей популяции нужно использовать взвешенные пропорции для республиканцев и демократов, мужчин и женщин, и так далее.
У чисел есть собственные «демографические» параметры. Нечётные и чётные числа, числа, делящиеся на 3, и числа, отличающиеся друг от друга ещё более хитрыми способами. Создав выборку чисел, можно сделать так, чтобы в неё входили определённые тип чисел, и не входили другие, по взвешенному принципу — и чем лучше вы выберете веса, тем точнее будут ваши умозаключения по поводу всех чисел в целом.
Взвешенный выбор
Задача Тао была гораздо сложнее, чем просто понять, как нужно создавать изначальную выборку чисел с нужными весами. На каждом шагу процесса Коллатца числа, с которыми вы работаете, меняются. Одно очевидное изменение состоит в том, что почти все числа из выборки уменьшаются.
Другое, возможно, менее очевидное изменение состоит в том, что числа могут начать скапливаться в группы. К примеру, можно начать с красивого равномерного распределения чисел от одного до миллиона. Но через пять итераций числа, скорее всего, сконцентрируются на нескольких небольших интервалах числовой прямой. Иначе говоря, можно начать с хорошей выборки, которая через пять шагов будет безнадёжно искажена.
«Обычно можно ожидать, что распределение после итерации будет полностью отличаться от начального», — сказал Тао. Однако ключевой его идеей было то, как можно создать выборку чисел, по большей части сохраняющих свои оригинальные веса в процессе Коллатца.
К примеру, начальная выборка Тао взвешена так, чтобы в ней не было чисел, делящихся на три, поскольку процесс Коллатца всё равно довольно быстро устраняет такие числа. Некоторые другие веса, выбранные Тао, оказываются сложнее. Он отдаёт предпочтение числам, остаток которых от деления на 3 составляет 1, и отходит от чисел, остаток которых от деления на 3 составляет 2.
В итоге выборка, с которой начинает Тао, сохраняет свой характер даже после начала процесса Коллатца.
«Он обнаружил способ продолжить этот процесс так, чтобы после нескольких шагов всё ещё было понятно, что происходит, — сказал Саундарараджан. — Когда я впервые увидел эту работу, я очень обрадовался и решил, что она потрясающая».
Тао использовал свою технику назначения весов, чтобы доказать, что почти все начальные значения — не менее 99% — в итоге приходят к величине, очень близкой к 1. Это позволило ему сделать вывод о том, Что 99% начальных значений, больших, чем квадриллион, в итоге приходят к величинам, меньшим 200.
Это, возможно, самый сильный результат в долгой истории этой гипотезы.
«Это великолепный прорыв в наших знаниях о том, что происходит с этой задачей, — сказал Лагариас. — Это определённо лучший результат за очень долгое время».
Метод Тао почти наверняка не способен добраться до полного доказательства гипотезы Коллатца. Причина в том, что его начальная выборка всё же немного искажается после каждого шага. Искажение будет минимальным, пока в выборке всё ещё содержатся множество разных значений, далёких от 1. Но в процессе Коллатца все числа в выборке начинают стремиться к одному, и небольшое искажение становится всё больше — так же, как небольшая ошибка в подсчётах результата голосования не имеет большого значения в случае крупной выборки, но сильно влияет на результат, когда выборка мала.
Любое доказательство полной гипотезы, скорее всего, будет основано на другом подходе. В итоге, работа Тао одновременно является и триумфом, и предостережением всем интересующимся: как только вам кажется, что вы загнали задачу в угол, она ускользает.
«К гипотезе Коллатца можно подобраться сколь угодно близко, но она всё равно остаётся недостижимой», — сказал Тао.
