Най-сложната „проста“ задача в историята: защо от половин век не сме виждали връзката между косинуса и графа?

Нова формула показа колко дълбоко са се заблуждавали математиците за простите вълни

Преди двеста години Жозеф Фурие предлага идея, която в крайна сметка се превръща в основа на съвременната математика и физика. Той предположил, че почти всяка функция може да бъде представена като сума от прости вълни. Днес принципът на преобразуването на Фурие се използва за анализ на спектрите на далечните звезди, за обработка на сигнали, за изследване на структурата на материята и за изучаване на процесите дълбоко под земната кора.Въпреки универсалността на метода, във връзка с него все още съществуват въпроси, които десетилетия наред не се поддават на строг математически анализ.

Един такъв проблем е формулиран през 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). Известните преди това оценки не притежаваха тази структура.

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