Математики до сих пор пытаются понять фундаментальные свойства преобразования Фурье, одного из самых распространенных и мощных инструментов. Новый результат знаменует собой важный шаг вперед в этом направлении. Комментарий Сохранить статью Прочитать позже
Введение
Два столетия назад Жозеф Фурье подарил математикам волшебный метод. Он предположил, что почти любую функцию можно представить в виде суммы простых волн — этот приём теперь называется преобразованием Фурье. Сегодня преобразование Фурье используется для понимания всего, от химического состава далёких звёзд до процессов, происходящих глубоко под земной корой.
«Ряды Фурье встречаются повсюду в математике, — сказал Мехтааб Сауни из Колумбийского университета. — Это часть убеждения математиков в важности рядов Фурье».
Однако некоторые фундаментальные вопросы, касающиеся преобразования Фурье, упорно и загадочно остаются без ответа.
В 1965 году математик Сарвадаман Чоула задал один из таких вопросов. Он хотел узнать, насколько малым может быть чрезвычайно простой тип преобразования Фурье — сумма косинусоидальных волн. Его задача казалась простой. Но почему-то это было не так.
«Этот вопрос — своего рода провокация, — сказал Сауни; — он был призван показать, насколько мало знают математики. Поскольку мы не можем это доказать, мы явно вообще не понимаем структуру этих [сумм]».
На протяжении десятилетий математики боролись с задачей о косинусах Чоулы. Она стала эталоном для методов анализа Фурье, используемых для изучения того, насколько хорошо они могут обнаруживать более глубокую структуру в последовательностях чисел. Результаты были неутешительными. «Прогресс был совершенно вялым», — сказал Том Сандерс из Оксфордского университета.
В сентябре ситуация внезапно изменилась. Четыре математика — Чжихань Цзинь, Алекса Милоевич, Иштван Томон и Шэнтун Чжан — впервые за 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 целых чисел, сумма косинусов которых имела минимальное значение около −$latex sqrt{textit{N}}$. Все остальные множества, которые он мог вспомнить, опускались еще ниже, что привело его к предположению, что для любого множества из N положительных целых чисел минимум соответствующей суммы косинусов должен быть ниже −$latex sqrt{textit{N}}$.
В последующие десятилетия несколько математиков постепенно решали эту проблему. Но к середине 2000-х годов между тем, что им удалось доказать, и тем, что предсказывал Чоула, всё ещё существовала огромная пропасть. Согласно последнему ограничению, доказанному в 2004 году Имре Ружей из Института математики им. Альфреда Реньи в Венгрии, сумма 10²⁰ косинусов — это единица с 20 нулями после неё, примерно равное числу молекул в кубическом дюйме воздуха — должна иметь минимальное значение меньше примерно −7. Для сравнения, Чоула предсказывал, что минимум должен опуститься ниже −10¹⁰.
И все же, на протяжении последних 20 лет результат Ружи представляет собой вершину прогресса в решении задачи о косинусах Чоулы.
Затем совершенно не связанная с этим исследовательская программа наконец преодолела этот барьер.
Преодоление разногласий
Программа работала с сетями узлов и ребер, называемыми графами.
Прошлым летом две группы теоретиков графов — Джин, Милоевич и Томон из Европы, а также Чжан из Стэнфордского университета — с энтузиазмом продвигались в решении одного из важнейших вопросов теории графов. Проблема «максимального разреза» (MaxCut) заключается в поиске оптимального способа разрезать граф на две части таким образом, чтобы между ними было как можно больше ребер. Это фундаментальный вопрос о структуре графа, имеющий реальные приложения: например, максимальный разрез графа может представлять собой эффективную схему или состояние с наименьшей энергией системы частиц.
Однако универсального подхода к определению максимального разреза графа не существует, по крайней мере, на данный момент. (Это так называемая NP-трудная задача.) Поэтому математики вместо этого пытаются оценить максимальный разрез для конкретных классов графов.
В 2003 году Бенджамин Судаков, математик из Швейцарского федерального технологического института в Цюрихе, который впоследствии стал наставником Джина, Милоевича и Томона, выдвинул вместе с тремя коллегами гипотезу о максимальном разрезе (MaxCut) определенного типа графов. В этом графе отсутствовали клики — кластеры узлов, соединенных между собой.
Группа взаимосвязанных узлов образует клику. На этом графе клика состоит из пяти узлов, выделенных красным цветом.
В июле прошлого года, спустя более чем два десятилетия, Чжан доказал новую границу для MaxCut для таких графов. Несколько дней спустя Цзинь, Милоевич и Томон улучшили его результат.
Для этого исследователи изучили важные величины, называемые собственными значениями. Собственные значения предоставляют информацию о структуре графа. Например, наибольшее собственное значение подсчитывает количество ребер в графе; второе по величине значение измеряет связность графа. Джин, Милоевич, Томон и Чжан сосредоточились на отрицательных собственных значениях, развивая недавнее направление исследований, которое связало их с максимальным разрезом графа (MaxCut). Их анализ этих собственных значений в конечном итоге позволил им доказать свои новые результаты.
Математики решили объединить свои отдельные результаты в совместную статью. Но прежде чем они смогли закончить, они получили неожиданное электронное письмо о задаче Чоулы о косинусах.
График Кейли
Письмо было от Ильи Шкредова, математика из Университета Пердью в Индиане. Шкредов, специалист по теории чисел, указал, что задачу о косинусах Чоулы можно переформулировать в терминах графов. Не тех общих типов графов, которые изучала группа, а особого типа графов, изобретенного в 1878 году математиком Артуром Кейли.
Чтобы построить граф Кэли, представьте, что вы снова работаете с множеством {2, 3, 8}. Начните с набора узлов — их количество не имеет значения, главное, чтобы число узлов было простым и больше наибольшего целого числа в множестве. Затем расположите узлы по кругу и обозначьте каждый из них целым числом. После этого проложите ребро между двумя узлами, если разница между ними находится в исходном множестве. Таким образом, узлы с номерами 1 и 3 будут соединены ребром, потому что разница между ними равна 2, а число 2 находится в множестве {2, 3, 8}.
К 1970-м годам математики выяснили, что в структуру графов Кэли заложена информация о ряде Фурье из задачи Чоулы. Оказалось, что собственные значения графа Кэли точно соответствуют различным значениям суммы косинусов. Следовательно, наименьшее собственное значение показывает, насколько низким может быть сумма косинусов.
«Это общеизвестный факт, — сказал Милоевич. — Связь носит чисто классический характер».
Это позволило математикам переформулировать проблему. Если бы они смогли показать, что наименьшее собственное значение графа Кэли становится очень малым, это означало бы, что сумма косинусов также должна становиться очень малой — именно в этом и заключается суть проблемы косинусов Чоулы.
Но никто не мог понять, как использовать эту связь в своих целях.
«Вы пытаетесь забить гвоздь молотком только тогда, когда у вас есть молоток», — сказал Судаков. У математиков не было способа достаточно точно проанализировать наименьшее собственное значение, чтобы выяснить то, что им нужно было знать о минимуме суммы косинусов.
Шэнтун Чжан добился значительных успехов в решении знаменитой проблемы «максимального разреза» (MaxCut), фундаментального вопроса о графах, имеющего множество практических применений.
Но в своей работе над MaxCut для графов Джин, Милоевич, Томон и Чжан невольно создали нечто неожиданное. Изучая взаимосвязь собственных значений графа с его структурой, они обнаружили, что любой граф, не имеющий низкого собственного значения, должен быть полон клик. Шкредов, прочитав их доказательство, понял, что это означает, что команда фактически переформулировала косинусную проблему Чоулы: больше не было необходимости анализировать собственные значения напрямую. Вместо этого им оставалось лишь доказать, что графы Кэли не имеют больших клик. Это означало бы, что каждый из графов имеет очень низкое собственное значение, что, наконец, позволило бы им использовать связь между гипотезой Чоулы и теорией графов.
С тех пор, по словам Томона, «главным препятствием, я думаю, была вера в то, что мы сможем это сделать».
Клики сближаются
Когда Шкредов отправил свое электронное письмо, все математики были в отпуске. Но Томон, который гостил в своем родном городе Будапеште, нашел время, чтобы поиграть с графом Кэли.
После недолгих раздумий «меня осенило», — сказал он.
Чтобы понять, как работает идея Томона, вернёмся к нашему графу Кэли для множества {2, 3, 8}. Помните, что доказательство гипотезы Чоулы означает доказательство того, что наименьшее собственное значение графа становится очень низким. Поэтому сначала предположим обратное: что ни одно из собственных значений не является низким. Вам нужно будет показать, что это предположение в конечном итоге приведёт к противоречию.
На основе работы команды над MaxCut было установлено, что если граф Кэли не имеет малых собственных значений, то он должен иметь большую клику — скажем, пять узлов, соединенных между собой. Это, в свою очередь, означает, что если взять любые два из этих узлов, разница между их целочисленными метками будет равна 2, 3 или 8.
Используя совершенно иной набор методов, Бенджамин Бедерт еще больше приблизился к решению задачи о косинусе Чоулы.
Теперь добавим по 1 к каждому узлу, чтобы получить новый набор из пяти узлов. Они будут отличаться на те же величины, что и первый набор, а это значит, что они тоже образуют клику. Продолжайте, и вы будете генерировать все больше и больше клик. Но есть проблема: у клик много ребер, в то время как у графа Кэли, исходя из его определения, относительно мало ребер, которые подчиняются очень специфической структуре. В конце концов, вы получите так много клик, что сгенерируете больше ребер, чем может вместить граф Кэли. Это означает, что предыдущее предположение о существовании большой клики должно было быть неверным. А это, в свою очередь, означает, что наименьшее собственное значение должно было быть низким.
Как только Томон это выяснил, остальная часть доказательства сложилась относительно легко. В сентябре он, Джин, Милоевич и Чжан опубликовали свою совместную статью в интернете. Она была в основном посвящена анализу наименьших собственных значений графов — работа, которая, в частности, позволила им усилить границы, найденные ими несколькими месяцами ранее для максимального разреза графов без клик.
Но их главный результат касался проблемы косинусов Чоулы. Они доказали, что для любого набора из N целых чисел соответствующая сумма косинусов принимает значение меньше −N1/10. Для любого реалистичного значения N значение −N1/10 не слишком отличается от оценки Ружи, сделанной несколько десятилетий назад. Но для огромных значений N, таких как 1020, разница начинает быть заметной: Джин, Милоевич, Томон и Чжан показали, что сумма 1020 косинусов опускается ниже −100 по сравнению с оценкой Ружи в −7.
«Для меня это очень неожиданно», — сказал Судаков. Группа начала с результата, касающегося графов, и совершенно неожиданно получила новые знания по, казалось бы, несвязанной проблеме.
Всего через два дня после публикации статьи исследователей, математик из Кембриджа Бедерт представил свой собственный вариант решения проблемы, используя более традиционный подход из анализа Фурье. Его результат немного превосходит оценку команды: он утверждает, что для любого набора из N целых чисел сумма косинусов принимает значение меньше −N1/7. Для 1020 это снижает минимум, определенный Джином, Милоевичем, Томоном и Чжаном, с −100 до примерно −720.
Но что наиболее примечательно для математиков, так это то, что оба этих результата впервые показывают, что доказанная оценка имеет ту же форму, что и предполагаемая оценка Чоулы. То есть новые оценки, как и оценки Чоулы, могут быть записаны как степень N. (Оценка Чоулы −$latex sqrt{textit{N}}$ эквивалентна −N1/2.) Предыдущая оценка Ружи не может быть записана в такой форме.
Туман, окружающий преобразование Фурье, по-прежнему очень плотный. Но новые методы немного лучше справляются с его преодолением.
Хотя ни одно из доказательств пока не заполнило полностью пробел, необходимый для подтверждения гипотезы Чоулы, математики полны энтузиазма. Пока что, по словам Сандерса, «это немного похоже на высадку на Луну или достижение результата в 4 минуты на милю». «Пока неясно, какие открытия это откроет».
Роль, которую сыграли графы в этой истории, особенно интригует. Это не первый случай встречи теории графов и анализа Фурье. Но до сих пор связи между этими двумя областями были единичными. Теперь Джин надеется, что конкретная связь между задачей о косинусах Чоулы и MaxCut намекает на нечто более широкое. «Что бы ни предсказывалось в задаче Чоулы, это явление носит более общий характер», — сказал он. «Это работает и в графах».
«Теперь у нас больше проблем, которые затрагивают одни и те же сферы влияния, — сказал Сауни. — Знание того, что эти явления существуют в одном мире, — очень полезная информация. Это очень мощный инструмент».
Исправление: 29 января 2026 г.
В более ранней версии текста подразумевалось, что Бенджамин Судаков был единственным автором гипотезы 2003 года о максимальном разрезе (MaxCut) некоторых графов. На самом деле он был одним из четырех авторов.
Источник: www.quantamagazine.org
