Новое доказательство открывает скрытые закономерности, возникающие, когда сложение становится невозможным.
Самые простые идеи в математике одновременно могут быть и самыми сложными.
Возьмём, к примеру, сложение. Это простая операция: одна из первых математических истин, которую мы узнаем, гласит, что 1 плюс 1 равно 2. Но у математиков до сих пор остаётся много вопросов о том, к каким закономерностям может привести сложение. «Это одна из самых простых вещей, которые можно сделать, — говорит Бенджамин Бедерт, аспирант Оксфордского университета. — Но почему-то она до сих пор остаётся во многом загадочной».
Исследуя эту загадку, математики также надеются понять пределы возможностей сложения. С начала XX века они изучают природу «свободных от сумм» множеств — наборов чисел, в которых сумма никаких двух чисел не окажется равным третьему числу из этого множества. Например, сложите любые два нечётных числа и получите чётное число. Таким образом, множество нечётных чисел свободно от сумм.
В своей работе 1965 года плодовитый математик Пал Эрдёш задал простой вопрос о том, насколько распространены множества свободных от сумм. Но в течение десятилетий прогресс в решении этой проблемы был незначительным.
«Это очень простая вещь, о которой мы имели удивительно мало представления», — говорит Джулиан Сахасрабудхе, математик из Кембриджского университета.
До февраля этого года. Спустя 60 лет после того, как Эрдёш поставил свою задачу, Бедерт решил её. Он показал, что в любом множестве, состоящем из целых чисел — положительных и отрицательных счётных чисел, — есть большое подмножество чисел, свободных от сумм. Его доказательство проникает в глубины математики, оттачивая методы из разных областей, чтобы обнаружить скрытую структуру не только в множествах свободных от сумм, но и во всех других.
«Это фантастическое достижение», — говорит Сахасрабудхе.
Ни туда, ни сюда
Эрдёш знал, что любое множество целых чисел должно содержать меньшее подмножество, не содержащее сумм. Рассмотрим множество {1, 2, 3}, которое не является свободным от сумм. Оно содержит пять различных свободных от сумм подмножеств – к примеру, {1} и {2, 3}.
Эрдёш хотел узнать, насколько далеко простирается это явление. Если у вас есть множество с миллионом целых чисел, насколько велико его самое большое подмножество свободных от сумм?
Во многих случаях оно огромно. Если выбрать миллион целых чисел наугад, то примерно половина из них окажется нечётной, что даёт подмножество свободных от сумм, содержащее около 500 000 элементов.
В своей работе 1965 года Эрдёш показал в доказательстве длиной всего в несколько строк, которое другие математики назвали блестящим, что любое множество из N целых чисел имеет свободное от сумм подмножество, состоящее по крайней мере из N/3 элементов.
Тем не менее, он не был удовлетворён. Его доказательство касалось средних величин: он нашёл коллекцию свободных от сумм подмножеств, и вычислил, что их средний размер равен N/3. Но обычно считается, что в такой коллекции самые большие подмножества намного больше среднего.
Эрдёш захотел измерить размер этих сверхбольших свободных от сумм подмножеств.
Вскоре математики предположили, что по мере увеличения множества самые большие свободные от сумм подмножества будут значительно больше, чем N/3. Фактически, эта разница будет расти бесконечно. Это предсказание — что размер самого большого подмножества свободных от сумм равен N/3 плюс некоторое отклонение, которое растёт до бесконечности с увеличением N, — теперь известно как гипотеза о свободных от сумм множествах.
«Удивительно, что этот простой вопрос, кажется, представляет значительные трудности, — писал Эрдёш в своей оригинальной статье, — но, возможно, мы упускаем из виду очевидное».
В течение десятилетий ничего очевидного не обнаруживалось. Никто не мог улучшить доказательство Эрдёша. «Чем дольше люди не могли улучшить это простое ограничение, тем большую известность приобретала эта проблема», — говорит Бен Грин, консультант Бедерта по докторской диссертации в Оксфорде. И, добавил он, это именно та проблема, где «очень, очень трудно сделать что-то лучше».
Противостояние норме
После 25 лет, в течение которых Эрдёш не улучшал свой первоначальный результат, математики наконец-то начали продвигаться вперёд. В 1990 году двое исследователей доказали, что любое множество из N целых чисел имеет свободное от сумм подмножество, содержащее не менее N/3 + 1/3 элементов, что чаще всего записывается как (N + 1)/3.
Но поскольку размер множества всегда является целым числом, увеличение на 1/3 часто не имеет значения. Например, если вы знаете, что свободное от сумм подмножество должно содержать не менее 5/3 элементов, это означает, что его размер гарантированно равен 2 или более. Если вы добавите 1/3 к 5/3, ваш ответ всё равно будет 2. «Забавно, но это означает, что на самом деле это не всегда улучшает ситуацию, — говорит Дэвид Конлон из Калифорнийского технологического института. — Это его улучшает, только когда N кратно 3,».
В 1997 году легенда математики Жан Бургейн довёл это ограничение до (N + 2)/3. Казалось бы, этот результат вряд ли стоит упоминания, но в статье Бургейна был скрыт поразительный прорыв. Он описал идею, как доказать, что самые большие свободные от сумм подмножества будут произвольно больше этой суммы. Он просто не смог описать некоторые детали, чтобы превратить её в полноценное доказательство.
«В статье говорится что-то вроде: вот как я пытался решить проблему и почему это не сработало», — говорит Сахасрабудхе.
Бургейн опирался на величину, называемую нормой Литтлвуда, которая измеряет структуру данного множества. Эта величина, пришедшая из области математики под названием анализ Фурье, имеет тенденцию быть большой, если множество в целом случайно, и малой, если множество обладает какой-то структурой.
Бургейн показал, что если множество с N элементами имеет большую норму Литтлвуда, то у него должно быть и свободное от сумм множество, которое намного больше N/3. Но он не смог добиться прогресса в случае, когда множество имеет малую норму Литтлвуда.
«Бургейн — известный специалист, — говорит Шон Эберхард из Университета Уорика. — Это очень яркий показатель того, насколько сложна эта проблема».
В конечном итоге Бургейну пришлось использовать другой аргумент, чтобы получить ограничение (N + 2)/3. Но математики уже поняли: возможно, они смогут использовать норму Литтлвуда, чтобы полностью разрешить эту гипотезу. Нужно было только понять, как работать с множествами с малой нормой Литтлвуда.
Повод для оптимизма был: математикам уже были известны множества с малой нормой Литтлвуда, которые имеют массивные подмножества свободных от сумм. Эти множества, называемые арифметическими прогрессиями, состоят из равномерно расположенных чисел, например {5, 10, 15, 20}. Математики подозревали, что любое множество с малой нормой Литтлвуда имеет очень специфическую структуру — оно более или менее представляет собой набор множества различных арифметических прогрессий (с некоторыми изменениями). Они надеялись, что если им удастся это показать, то они смогут использовать это свойство для доказательства того, что любое множество с малой нормой Литтлвуда имеет большое подмножество свободных от сумм.
Но эта задача оказалась нелёгкой. «Я, конечно, пытался доказать гипотезу о свободном от сумм подмножестве, используя идеи [Бургейна], — говорит Грин, — но мы всё ещё мало что понимаем в структуре множеств с малой нормой Литтлвуда. Всё, что связано с Литтлвудом, очень сложно».
И вот, хотя математики продолжали верить в стратегию Бургейна, основанную на Литтлвуде, это ни к чему не привело.
Прошло более двух десятилетий. Затем, осенью 2021 года, Бенджамин Бедерт поступил в аспирантуру.
Пресловутые проблемы
Поскольку его научным руководителем был Грин, Бедерт неизбежно должен был наткнуться на гипотезу о множествах свободных от сумм. На сайте Грина есть список 100 открытых проблем, и эта проблема стоит на первом месте.
Бедерт ознакомился с этим списком вскоре после начала учёбы в аспирантуре. Поначалу он сторонился проблемы свободных от сумм множеств. Я подумал: «Это очень сложно, я не буду об этом думать, — вспоминает он. — Я оставлю это на будущее».
Будущее наступило довольно скоро. Летом 2024 года Бедерт решил, что готов к более рискованному проекту. «К тому моменту я уже получил достаточно хорошие результаты в своей кандидатской диссертации, и вроде как уже подготовил докторскую, — говорит он. — Я начал думать о более, что ли, известных проблемах».
Он прочитал статью Бургейна 1997 года и начал размышлять о том, как реализовать план Литтлвуда. Почти сразу же у него появилась идея, как можно подойти к проблеме множеств с малой нормой Литтлвуда.
До сих пор было слишком сложно показать, что множества с малой нормой Литтлвуда всегда похожи на коллекции арифметических прогрессий. Но Бедерт подумал, что было бы полезно доказать нечто более достижимое: что даже если эти множества не построены буквально из арифметических прогрессий, они обладают некоторыми ключевыми свойствами, делающими их похожими на прогрессии.
В ходе одного из недавних проектов Бедерт столкнулся с тем, что показалось ему хорошим кандидатом на свойство, на котором стоит сосредоточиться. В арифметической прогрессии есть много групп чисел, которые имеют одинаковую сумму. Например, в наборе чётных чисел (который является арифметической прогрессией) 4 + 8 имеет ту же сумму, что и 2 + 10 и 2 + 4 + 6. Бедерту показалось, что достаточно показать, что множества с малой нормой Литтлвуда всегда подчиняются этому свойству.
Через пару недель ему удалось доказать, что это свойство верно. Но даст ли этот результат ему такой уровень сходства с арифметическими прогрессиями, который нужен для доказательства гипотезы о свободных от сумм множествах?
«Я определённо обрадовался, — сказал он. — Но потом я понял, что предстоит ещё очень много работы».
Волнообразный прогресс
Во-первых, Бедерт показал, что любое множество с малой нормой Литтлвуда может быть «отображено» на второе множество, которое ещё больше напоминает арифметическую прогрессию. Он подозревал, что именно в этих новых множествах он сможет найти большие свободные от сумм подмножества.
Последняя задача заключалась в том, чтобы показать, каков размер такого свободного от сумм подмножества. «Во время рождественских каникул я навязчиво думал об этой проблеме, — говорит Бедерт. — До Нового года я не нашёл последний кусочек головоломки».
Затем, через несколько дней после возвращения в Оксфорд в январе, его осенило. «Я не знаю точно, откуда она взялась, — сказал он. — Может быть, эти идеи какое-то время крутятся в голове, а потом [вы] наконец-то получаете что-то рабочее».
Он представил структуру своих множеств с помощью инструмента, называемого преобразованием Фурье, а затем изменил доказательство 1981 года, чтобы показать, что некоторые из отдельных компонентов этого представления должны иметь большую норму Литтлвуда. Поскольку Бургейн уже показал, как работать с множествами с большими нормами Литтлвуда, доказательство было завершено.
В итоге Бедерт показал, что любое множество из N целых чисел имеет свободное от сумм подмножество, содержащее по крайней мере N/3 + log(log N) элементов. Для многих значений N это даёт свободное от сумм подмножество, которое лишь немного больше, чем среднее значение Эрдёша, равное N/3. Даже если N велико, например, до 10100, log(log N) составляет всего около 5. Но с увеличением N до бесконечности разница в границах Бедерта и Эрдёша стремится туда же, подтверждая гипотезу.
«Это действительно потрясающий результат», — сказал Ифань Цзин из Университета штата Огайо. Цзин, который также был наставником Грина, приписывает достижение Бедерту за его напряжённую сосредоточенность. «Бенджамин очень глубоко проработал доказательство Бургейна, чтобы заставить его работать, — сказал он. — Он тратит гораздо больше времени, чем другие люди, на решение одной и той же проблемы».
Нам предстоит ещё многое понять о подмножествах свободных от сумм — а значит, и о том, насколько сложение влияет на структуру целых чисел. Например, результат Бедерта решает вопрос о том, является ли наибольшее подмножество свободных от сумм бесконечно большим, чем N/3. Но математики не знают точно, как быстро может расти эта разница. Благодаря работе 2014 года, написанной Грином и двумя коллегами, они знают, что разница растёт медленнее, чем N. Но, по словам Грина, «остаётся огромный разрыв» между верхней границей N и нижней границей Бедерта, равной log(log N).
Работа также даёт новое представление о множествах, имеющих малую норму Литтлвуда. Такие множества являются фундаментальными объектами в области анализа, но их очень трудно изучать. Результат Бедерта помог математикам лучше понять их структуру, которую Грин и другие надеются продолжить исследовать. «Это красиво, это интересно, это кажется естественным, — говорит Эберхард. — Всем же хочется разгадать тайну, не так ли?»
Для Сахасрабудхе вывод прост. «Старая и сложная проблема решена гениальным пареньком, — сказал он. — Материал, на котором он строит своё доказательство, очень тонкий и сложный в работе. Но результат получился очень красивым».
