Математики решили задачу Рональда Грэма, которой 55 лет
Математики завершили доказательство 55-летней гипотезы Рональда Грэма для всех достаточно больших простых чисел. Последний незакрытый диапазон разобрали Лиза Зауэрманн и Хюи Туан Фам: их новая работа объясняет, как правильно упорядочить числа, чтобы последовательное сложение никогда не возвращало уже полученный результат. Вместе с тремя предыдущими работами доказательство охватывает наборы любого размера.
Сама задача появилась в 1971 году и формулируется вокруг арифметики по модулю. Проще всего представить циферблат. На обычной числовой прямой после 6 идёт 7, затем 8 и так далее, а на циферблате после 11 снова появляется 0. В математической задаче размер такого условного циферблата задаёт простое число p. Например, при p = 7 используются остатки 0, 1, 2, 3, 4, 5 и 6, после чего счёт снова начинается с нуля. Поэтому 3 + 4 при вычислениях по модулю 7 даёт 0, а 5 + 4 даёт 2: обычная сумма равна 9, но после полного круга остаётся остаток 2. Такая система и создаёт проблему, которой нет при сложении обычных положительных чисел.
Грэм предложил взять любой набор разных ненулевых остатков и расставить их в некотором порядке. Затем нужно последовательно считать частичные суммы: сначала первое число, потом первое плюс второе, затем первые три числа, первые четыре и так далее. Гипотеза утверждает, что элементы всегда можно переставить так, чтобы ни одна из полученных сумм не встретилась дважды.
На маленьком примере условие видно сразу. Возьмём числа 1, 2 и 5 по модулю 7 и расположим их как 1, 2, 5. Первая частичная сумма равна 1, вторая равна 3, а третья снова равна 1, потому что 1 + 2 + 5 = 8, а остаток от деления 8 на 7 равен 1. Получилось повторение, значит такой порядок не подходит. Теперь поменяем расположение на 2, 1, 5. Частичные суммы будут равны 2, 3 и 1. Все три значения различаются, поэтому новый порядок удовлетворяет условию Грэма. В маленьком наборе нужную перестановку легко подобрать вручную. Гипотеза же требует доказать, что подходящий порядок существует для любого допустимого набора, каким бы большим и неудобным тот ни оказался.
У задачи есть ещё один способ взглянуть на проблему, и именно он помогает понять доказательства. Если две частичные суммы совпали, значит числа между ними вместе дали 0 по модулю p. Поэтому вместо отслеживания огромного количества накопленных сумм можно искать внутри последовательности непрерывные участки, сумма которых равна нулю. Если таких участков нет, частичные суммы не повторяются.
Представим длинную перестановку чисел. Где-то внутри неё обнаруживается несколько соседних элементов, которые вместе дают 0. Всё, что было накоплено до начала такого участка, после его завершения возвращается к тому же значению. Значит, задача сводится к следующему: расположить числа так, чтобы нигде внутри всей последовательности не возник ни один такой нулевой отрезок.
Именно здесь простая формулировка превращается в сложную комбинаторную задачу. Чем больше набор, тем больше возможных отрезков приходится учитывать. При этом размеры самого набора тоже сильно меняют характер проблемы. Если чисел совсем мало по сравнению с p, вариантов размещения относительно немного, но случайные совпадения трудно контролировать напрямую. Если набор занимает почти весь доступный круг остатков, появляется другая структура, которой можно воспользоваться. Для промежуточных размеров ни один из этих подходов долго не работал.
Первый большой кусок удалось закрыть со стороны очень крупных наборов. Альп Мюэссер и Алексей Покровский показали, что случайная перестановка уже обычно находится недалеко от нужного результата. Они временно откладывали несколько специально выбранных чисел, перемешивали остальные, а затем использовали запасные элементы для исправления найденных нулевых участков. Метод появился внутри более общей работы по комбинаторике.
С противоположной стороны продвинулись Бенджамин Бедерт и Ноа Кравиц. В 2024 году они доказали гипотезу для наборов, которые очень малы по сравнению с p, значительно расширив предыдущую известную границу. Их результат использовал другую структуру задачи и не мог просто продолжаться до наборов среднего размера.
В 2025 году группа математиков продвинула границу со стороны больших множеств ещё дальше. Они доказали существование нужного порядка для наборов размером не меньше некоторой степени от общего числа возможных остатков. Но между областью, которую покрывали методы для малых множеств, и областью больших множеств всё равно оставался широкий промежуток. Особенно неудобными были наборы среднего размера, например содержащие заметную долю всех возможных чисел.
Зауэрманн и Фам выбрали другой путь. Вместо попытки сразу построить идеальную последовательность математики берут случайный порядок и постепенно его исправляют. Если внутри обнаруживается участок с нулевой суммой, последний элемент такого участка меняют местами с другим числом, расположенным дальше. Перестановка разрушает проблемный отрезок и позволяет продолжить проверку.
Само исправление придумать несложно. Намного труднее доказать, что процесс не застрянет. Авторы выделили три основных способа, которыми алгоритм может потерпеть неудачу. Нулевой участок способен появиться слишком близко к концу последовательности, когда подходящего числа для обмена уже не останется. Несколько проблемных участков могут скопиться рядом и начать мешать друг другу. Наконец, исправление одного участка способно случайно создать новый нулевой отрезок дальше по цепочке.
Чтобы справиться со всеми тремя случаями одновременно, математикам понадобилась антиконцентрация. Смысл метода можно объяснить без формул. Представим, что из большого набора случайно выбирают несколько чисел и складывают их по модулю p. Для доказательства важно показать, что результат такой случайной суммы не слишком часто попадает в одно заранее выбранное значение, например в 0.
Если бы огромное количество разных наборов постоянно давало одну и ту же сумму, нулевые участки возникали бы слишком часто и процедура исправления могла бы развалиться. Зауэрманн и Фам доказали обратное: случайные суммы достаточно хорошо распределены по возможным значениям. Ни один отдельный результат не получает настолько большую вероятность, чтобы опасные совпадения стали неизбежными.
Для такой оценки авторы применили анализ Фурье. В данном случае метод нужен не для обработки звука или изображения, а как математический инструмент для изучения распределения сумм. Он позволяет разложить сложное распределение на более простые составляющие и оценить, насколько сильно случайные суммы могут скапливаться около одного значения.
После этого авторы отдельно рассчитали вероятность каждого сценария, способного остановить исправления. Все оценки вместе показали, что вероятность провала остаётся меньше 100%. Для вероятностного доказательства такой границы достаточно: если случайный процесс терпит неудачу не всегда, значит существует хотя бы одна перестановка, для которой все исправления сработают и повторяющихся частичных сумм не останется.
Результат оказался даже сильнее простого доказательства существования. По оценке авторов, их процедура успешно превращает случайную перестановку в подходящую как минимум в 90% случаев в рассматриваемом диапазоне размеров. Иными словами, нужные последовательности не спрятаны среди исключительно редких комбинаций, а встречаются достаточно часто.
Работа Зауэрманн и Фама закрыла именно тот средний диапазон, который не поддавался прежним методам. Если объединить новое доказательство с результатами для малых и больших наборов, гипотеза Грэма оказывается доказанной для наборов любого размера при всех достаточно больших простых p.
Одна формальная оговорка всё же остаётся. Грэм сформулировал гипотезу для каждого простого числа, без требования, чтобы p было огромным. Современная цепочка доказательств гарантирует результат только начиная с некоторого достаточно большого значения. Точную нижнюю границу авторы не вычисляли. Поэтому конечное количество меньших простых чисел формально остаётся за пределами общего доказательства, хотя основная 55-летняя проблема для больших p теперь решена.
История задачи перекликается с ещё одним увлечением Рональда Грэма. Математик серьёзно занимался жонглированием и позже публиковал работы о его математических закономерностях. Есть предположение, что идея гипотезы могла возникнуть из похожего вопроса о порядке бросков: если разные предметы проводят в воздухе разное время, можно ли выстроить последовательность так, чтобы два из них не возвращались одновременно. Спустя 55 лет ответ на математическую версию такого вопроса удалось получить с помощью случайности, которая сначала создаёт беспорядок, а затем помогает доказать существование строгого порядка.