Математики до сих пор пытаются понять фундаментальные свойства преобразования Фурье, одного из самых распространённых и мощных инструментов в математике. Новый результат стал важным шагом к достижению этой цели.
Два столетия назад Жозеф Фурье подарил математикам волшебный метод. Он предположил, что почти любую функцию можно представить в виде суммы простых волн — этот приём теперь называется преобразованием Фурье. В наши дни преобразование Фурье используется для понимания всего, от химического состава далёких звёзд до процессов, происходящих глубоко под земной корой.
«Ряды Фурье встречаются повсюду в математике, — сказал Мехтааб Сауни из Колумбийского университета. — Это часть убеждения математиков в важности рядов Фурье».
Однако некоторые фундаментальные вопросы, касающиеся преобразования Фурье, по-прежнему остаются без ответа.
В 1965 году математик Сарвадаман Чоула задал один из таких вопросов. Он хотел узнать, насколько малым числом может быть сумма косинусов — чрезвычайно простой тип преобразования Фурье. Его задача казалась простой. Но почему-то это было не так.
«Этот вопрос — своего рода провокация, — сказал Сауни; — он должен был показать, как мало математики знают. Раз мы не можем разобраться в нём — значит, мы вообще не понимаем структуру таких сумм».
На протяжении десятилетий математики боролись с задачей о косинусах Чоулы. Задача стала испытательным полигоном для методов анализа Фурье: на ней проверяют, насколько хорошо эти методы умеют находить скрытую структуру в последовательностях чисел.. Результаты были неутешительными. «Прогресс почти стоял на месте», — сказал Том Сандерс из Оксфордского университета.
В сентябре 2025 года ситуация внезапно изменилась. Четыре математика — Чжихан Цзинь, Алекса Милоевич, Иштван Томон и Шэнтун Чжан впервые за 20 лет добились значительного прогресса в решении этой проблемы. Их подход почти не пересекался с традиционным анализом Фурье.
До прошлого лета они вообще не знали о задаче косинусов Чоулы.
Всё меньше и меньше
В начале 1950-х годов Чоула и его коллега, специалист по теории чисел Несмит Анкени, хотели использовать преобразование Фурье для лучшего понимания закономерностей в наборах чисел. Рассмотрим набор, состоящий из чисел 2, 3 и 8. Сначала используем каждое число в наборе для определения косинусоидальной волны — например, 2 даёт cos(2x). Затем сложим все волны, чтобы получить cos(2x) + cos(3x) + cos(8x). Это ещё один способ записи исходного набора в виде ряда Фурье. Ряд имеет сложную структуру: все волны — это косинусы, и поскольку перед косинусами нет чисел, все волны имеют одинаковую величину. «Это самый простой из возможных типов рядов Фурье», — сказал Бенджамин Бедерт из Кембриджского университета. «И в целом, мы довольно много знаем о рядах Фурье».
Новая волна, определяемая выражением cos(2x) + cos(3x) + cos(8x), имеет пики и впадины, которые раскрывают интересные свойства исходного набора чисел. Поэтому Анкени и Чоула решили проверить, насколько хорошо они понимают такие ряды. Они задались вопросом: для любого набора из N целых чисел, какое наименьшее значение может принять их сумма?
Легко определить максимум суммы. Когда x равно нулю, любая косинусоидальная волна достигает своего максимума в 1. Таким образом, сумма трёх косинусоидальных волн даёт нам 1 + 1 + 1 = 3. Аналогично, сумма 10 миллионов косинусоидальных волн имеет максимум в 10 миллионов. Для любого набора из N целых чисел максимум суммы просто равен N.
Однако найти минимум суммы косинусов на удивление сложно. Хотя все волны достигают своего максимума одновременно хотя бы один раз (когда x равно нулю), с минимумом такого не происходит. Возможно, самые низкие точки разных волн всё же окажутся достаточно близко, чтобы получить очень малую сумму. Или, возможно, волны будут интерферировать друг с другом, так что очень малая сумма станет невозможной.
В 1952 году Анкени и Чоула предположили, что, подобно тому как максимум становится всё больше и больше по мере увеличения числа целых чисел в исходном множестве, минимум должен становиться все меньше и меньше. Это было доказано несколько лет спустя, что побудило Чоулу уточнить вопрос в 1965 году. Он хотел точно узнать, как быстро падает минимум по мере роста N.
Ему были известны множества из N целых чисел, сумма косинусов которых имела минимальное значение около 
. Все остальные множества, которые он мог вспомнить, имели ещё более малые значения, что привело его к предположению, что для любого множества из N положительных целых чисел минимум соответствующей суммы косинусов должен быть меньше 
.
В последующие десятилетия несколько математиков постепенно продвигались в решении этой задачи. Но к середине 2000-х годов между тем, что им удалось доказать, и тем, что предсказывал Чоула, всё ещё оставалась огромная пропасть. Согласно последней оценке, доказанной в 2004 году Имре Ружей из Института Математики имени Альфреда Реньи в Венгрии, сумма 10²⁰ косинусов — это единица с 20 двадцатью нулями, примерно равная числу молекул в кубическом дюйме воздуха — должна иметь минимальное значение меньше примерно −7. Для сравнения, Чоула предсказал, что минимум должен быть меньше −10¹⁰.
И все же, на протяжении последних 20 лет результат Ружи оставался лучшим результатом в решении задачи о косинусах Чоулы.
Прорыв пришёл оттуда, где его не ждали.
Максимальный разрез
А именно из теории графов.
Прошлым летом две группы специалистов по теории графов — Цзинь, Милоевич и Томон в Европе, а также Чжан из Стэнфордского университета — активно продвигались в решении одного из главных вопросов теории графов. Задача о максимальном разрезе (MaxCut) касается оптимального способа разрезать граф на две части таким образом, чтобы между ними было как можно больше рёбер. Это базовый вопрос о структуре графа — и у него есть реальные приложения: максимальный разрез графа может представлять собой, например, эффективную электронную схему или состояние с наименьшей энергией системы частиц.
Однако универсального способа найти максимальный разрез не существует, по крайней мере, на данный момент. (Это так называемая NP задача.) Поэтому математики вместо этого оценивают максимальный разрез для отдельных классов графов.
В 2003 году Бенджамин Судаков, математик из Швейцарской Высшей Технологической Школе в Цюрихе, который позже станет наставником Цзиня, Милоевича и Томона, вместе с тремя коллегами выдвинул гипотезу о максимальном разрезе для графов определённого типа. В этом графе отсутствовали клики — кластеры узлов, соединённых между собой.
В июле прошлого года, спустя более чем два десятилетия, Чжан доказал новую границу максимального разреза для таких графов. Несколько дней спустя Цзинь, Милоевич и Томон улучшили его результат.
Для этого исследователи изучили важные величины, называемые собственными значениями. Собственные значения многое говорят о структуре графа. Например, наибольшее собственное значение измеряет количество рёбер в графе; второе по величине значение измеряет связность графа. Цзинь, Милоевич, Томон и Чжан сосредоточились на отрицательных собственных значениях. Это направление возникло недавно: в нём отрицательные собственные значения связали с максимальным разрезом графа. Именно анализ этих значений и привёл к новым результатам.
Математики решили объединить свои результаты в совместной статье. Но прежде чем они смогли её закончить, они получили неожиданное электронное письмо о задаче косинусов Чоулы.
Графы Кэли
Письмо было от Ильи Шкредова, математика из Университета Пердью в Индиане. Шкредов, специалист по теории чисел, указал, что задачу о косинусах Чоулы можно переформулировать в терминах графов. Не тех общих типов графов, которые изучала группа, а особого типа графов, изобретённого в 1878 году математиком Артуром Кэли.
Чтобы построить граф Кэли, представьте, что вы снова работаете с множеством {2, 3, 8}. Начните с набора узлов — их количество не имеет значения, главное, чтобы число узлов было больше наибольшего целого числа в этом множестве. (В зависимости от того, как вы хотите использовать граф, вы можете добавить дополнительные ограничения на это число; в данном случае оно также должно быть простым.) Затем расположите узлы по кругу и обозначьте каждый из них целым числом. Затем проложите ребро между двумя узлами, если разница между ними находится в исходном множестве. Таким образом, узлы с номерами 1 и 3 будут соединены ребром, потому что разница между ними равна 2, а число 2 находится в множестве {2, 3, 8}.
К 1970-м годам математики поняли: структура графов Кэли хранит информацию о ряде Фурье из задачи Чоулы. Собственные значения графа Кэли в точности соответствуют различным значениям суммы косинусов. Следовательно, наименьшее собственное значение показывает, насколько малой может быть сумма косинусов.
«Это общеизвестный факт, — сказал Милоевич . — Связь чисто классическая».
Это позволило математикам переформулировать проблему. Если бы они смогли показать, что наименьшее собственное значение графа Кэли становится очень малым, это означало бы, что сумма косинусов также должна становиться очень малой — именно в этом и заключается суть задачи косинусов Чоулы.
Но никто не мог понять, как применить эту связь.
«Вы пытаетесь забить гвоздь молотком только тогда, когда у вас есть молоток», — сказал Судаков. У математиков не было способа достаточно точно проанализировать наименьшее собственное значение графа, чтобы выяснить то, что им нужно было знать о минимуме суммы косинусов.
Но в своей работе над задачей о максимальном разрезе графов Цзинь, Милоевич, Томон и Чжан случайно наткнулись на нечто неожиданное. Они изучали, как собственные значения графа связаны с его структурой, и обнаружили: если у графа нет малого собственного значения, он обязательно полон клик. Шкредов прочитал доказательство и понял: команда фактически переформулировала задачу косинусов Чоулы. Больше не было необходимости анализировать собственные значения напрямую. Вместо этого им оставалось лишь доказать, что их графы Кэли не имеют больших клик. Тогда у каждого из графов нашлось бы очень малое собственное значение — а это наконец дало бы возможность задействовать связь между гипотезой Чоулы и теорией графов.
По словам Томона, «главное было поверить, что нам это вообще по силам».
Клики приходят на помощь
Когда Шкредов отправил своё электронное письмо, все математики были в отпуске. Но Томон, который гостил в своём родном городе Будапеште, выкроил время поработать с графом Кэли.
«Меня осенило», — рассказывает Томон.
Чтобы понять идею, Томона, вернёмся к нашему графу Кэли для множества {2, 3, 8}. Напомним: доказать гипотезу Чоулы — значит показать, что наименьшее собственное значение графа становится очень малым. Поэтому сначала предположим обратное: что ни одно из собственных значений не является малым. Вам нужно будет показать, что это предположение в конечном итоге приведёт к противоречию.
В ходе работы над задачей о максимальном разрезе команда установила, что если граф Кэли не имеет малых собственных значений, то он должен иметь большую клику — скажем, пять узлов, соединённых между собой. Значит, если взять любые два из этих узлов, разница между их целочисленными метками будет равна 2, 3 или 8.
Теперь добавим по 1 к каждому узлу, чтобы получить новый набор из пяти узлов. Узлы будут отличаться на те же величины, что и первый набор — значит, и они образуют клику. Продолжайте — и клик становится всё больше. Но есть проблема: у клик много рёбер, в то время как граф Кэли по определению имеет относительно мало рёбер, которые подчиняются очень специфической структуре. В какой-то момент клик станет так много, что рёбер окажется больше, чем может быть в графе Кэли. Значит, исходное предположение о большой клике было неверным. А значит, наименьшее собственное значение всё-таки малое.
Как только Томон это выяснил, остальное доказательство сложилось относительно легко. В сентябре он, Цзинь, Милоевич и Чжан опубликовали свою совместную статью в интернете. Она была посвящена главным образом анализу наименьших собственных значений графов — эта работа, в частности, позволила уточнить границы, полученные несколькими месяцами ранее для максимального разреза графов без клик.
Но их главный результат касался проблемы косинусов Чоулы. Они доказали, что для любого набора из N целых чисел соответствующая сумма косинусов принимает значение меньше −N1/10. Для любого реалистичного значения N значение −N1/10 не сильно отличается от оценки Ружи, сделанной несколько десятилетий назад. Но для огромных значений N, таких как 10²⁰, разница становится заметной: Цзинь, Милоевич, Томон и Чжан показали, что сумма 10²⁰ косинусов опускается ниже −100 по сравнению с оценкой Ружи, равной −7.
«Для меня это очень неожиданно», — сказал Судаков. Группа отталкивалась от результата по теории графов, и внезапно получила новые знания по проблеме, которая казалась совершенно посторонней.
Всего через два дня после публикации статьи исследователей, математик из Кембриджа Бедерт представил свой результат по этой проблеме, используя более привычный подход из анализа Фурье. Его результат немного превосходит оценку команды: он утверждает, что для любого набора из N целых чисел сумма косинусов принимает значение меньше −N1/7. Для 10²⁰ это снижает минимум, определённый Цзинем, Милоевичем, Томоном и Чжаном, с −100 до примерно −720.
Но что наиболее примечательно для математиков, так это то, что оба этих результата впервые показывают, что доказанная оценка имеет ту же форму, что и предполагаемая оценка Чоулы. То есть новые оценки, как и оценки Чоулы, могут быть записаны как степень N. (Оценка Чоулы 
эквивалентна −N 1/2 .) Предыдущая оценка Ружи не может быть записана в такой форме.
Туман, окружающий преобразование Фурье, по-прежнему очень плотный. Но новые методы пробивают его чуть глубже.
Хотя ни одно из доказательств пока не закрывает гипотезу Чоулы полностью, математики полны энтузиазма. Пока что, по словам Сандерса, «это немного похоже на высадку на Луну или достижение результата в 4 минуты на милю» (выдающийся профессиональный результат, эквивалентный скорости 24 км/ч). «Пока неясно, какие возможности это откроет».
Роль, которую сыграли графы в этой истории, особенно интригует. Это не первый случай встречи теории графов и анализа Фурье. Но до сих пор связи между этими двумя областями оставались редкими. Теперь Цзинь надеется, что конкретная связь между задачей о косинусах Чоулы и задачей о максимальном разрезе указывает на более общее явление. «Что бы ни предсказывалось в задаче Чоулы, это явление носит более общий характер», — сказал он. «Это работает и в графах».
«Теперь у нас больше проблем, которые затрагивают одни и те же сферы, — сказал Сауни. — Понимание того, что эти явления живут в одном мире, — очень полезная информация. Это очень мощный инструмент».
Автор перевода @arielf
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
— 15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.
Автор: FirstJohn
