Самая сложная «простая» задача в истории: почему мы полвека не видели связи между косинусом и графом?

Двести лет назад Жозеф Фурье предложил идею, которая со временем стала фундаментом современной математики и физики. Он предположил, что почти любую функцию можно представить в виде суммы простых волн. Сегодня этот принцип, лежащий в основе преобразования Фурье, используется при анализе спектров далёких звёзд, обработке сигналов, исследовании структуры вещества и изучении процессов, происходящих глубоко под земной корой. При всей универсальности метода вокруг него до сих пор сохраняются вопросы, которые десятилетиями не поддавались строгому математическому анализу.

Одна из таких задач была сформулирована в 1965 году математиком Сарвадаманом Чоулой. Он заинтересовался крайне простым, но фундаментальным объектом: суммой косинусов без коэффициентов, где каждая функция имеет одинаковую амплитуду и отличается только частотой. Формально речь идёт о разложении вида cos(a₁x) + cos(a₂x) + ... + cos(aₙx), где a₁, a₂, …, aₙ — целые числа. С точки зрения теории Фурье это один из самых элементарных типов рядов, но именно он оказался неожиданно сложным для анализа.

Максимальное значение такой суммы определяется тривиально. При x = 0 каждая функция cos(ax) равна 1, поэтому сумма из N косинусов всегда достигает значения N. Минимум, напротив, устроен гораздо сложнее. Минимальные точки отдельных волн не совпадают во времени, и поведение суммы определяется сложной интерференцией разных частот. Возникает фундаментальный вопрос: насколько глубоко может опускаться график такой суммы в отрицательную область.

Чоуле были известны примеры множеств из N целых чисел, для которых минимум суммы приближался к величине порядка -√N. Он также наблюдал, что большинство других наборов давали ещё более отрицательные значения. Это привело его к гипотезе, что для любого множества из N положительных целых чисел соответствующая сумма косинусов обязательно принимает значение ниже -√N, а также к более точному вопросу о скорости убывания этой нижней границы при росте N.

Несмотря на простоту формулировки, задача десятилетиями оставалась практически неподвижной. В 2004 году Имре Ружа получил результат, который долгое время считался лучшим известным. Его оценка давала крайне слабую нижнюю границу на больших масштабах. Например, для суммы из 10²⁰ косинусов она гарантировала значение ниже примерно -7, тогда как гипотеза Чоулы предполагала уровень порядка -10¹⁰. На протяжении почти 20 лет именно эта оценка оставалась вершиной прогресса.

Сдвиг произошёл неожиданно и пришёл из совершенно другой области математики. Четверо исследователей — Чжихань Цзинь, Алекса Милоевич, Иштван Томон и Шэнтун Чжан — занимались задачами теории графов, в частности проблемой MaxCut. Она связана с оптимальным разбиением графа на две части так, чтобы число рёбер между ними было максимальным. Эта задача имеет как теоретическое значение, так и прикладные интерпретации в физике, информатике и инженерии, однако относится к NP-трудным и не имеет универсального алгоритмического решения.

В своих исследованиях команда анализировала спектральные характеристики графов, то есть собственные значения матриц, описывающих их структуру. Эти величины отражают фундаментальные свойства: плотность связей, связность, наличие кластеров. Особое внимание уделялось отрицательным собственным значениям, поскольку они оказались тесно связаны с оценками MaxCut. В ходе работы был получен общий результат: если у графа отсутствуют достаточно малые отрицательные собственные значения, его структура неизбежно доминируется кликами — плотными подграфами, где каждая вершина соединена со всеми остальными.

Дальнейший поворот произошёл после письма Ильи Шкредова, который указал на связь задачи Чоулы с особым классом объектов — графами Кэли. Эти графы строятся по множеству целых чисел и простому модулю, а их спектральные характеристики напрямую связаны со значениями соответствующих сумм косинусов. Минимальное собственное значение такого графа совпадает с наименьшим значением косинусной суммы.

Используя ранее полученные результаты по MaxCut, исследователи смогли переформулировать задачу. Вместо прямого анализа собственных значений стало достаточно доказать, что в соответствующих графах Кэли не могут существовать большие клики. Предположение об их наличии приводит к цепочке логических следствий, которые противоречат ограниченной плотности рёбер в этих графах. Тем самым автоматически следует существование достаточно малого отрицательного собственного значения, а значит и глубокого минимума косинусной суммы.

В опубликованной работе авторы доказали, что для любого множества из N целых чисел соответствующая сумма косинусов обязательно принимает значение ниже -N^(1/10). Для малых N эта оценка выглядит скромно, но на экстремальных масштабах становится принципиально значимой. Для N = 10²⁰ она даёт минимум ниже -100, что на порядки превосходит старую оценку Ружи.

Спустя всего 2 дня после публикации появился независимый результат Бенджамина Бедерта, полученный уже методами классического анализа Фурье. Его граница оказалась немного сильнее: минимум ниже -N^(1/7). Для N = 10²⁰ это соответствует величине порядка -720.

Главное значение этих работ связано не только с числовыми оценками. Впервые за десятилетия строгие результаты приняли степенную форму по N, как и в исходной гипотезе Чоулы, где граница имела вид -N^(1/2). Ранее известные оценки не обладали такой структурой.

Хотя до полного доказательства гипотезы Чоулы ещё далеко, новая связка между теорией графов и анализом Фурье изменила само поле задачи. Впервые разные области математики сошлись в единой логической конструкции, показав, что проблемы спектрального анализа, структуры графов и классические ряды Фурье могут описывать одни и те же фундаментальные явления с разных сторон.