Порядок скрывается внутри хаоса. Именно это и есть главная задача теории Рамсея.
Десять лет математики пытались найти этот порядок. Прогресс был леденящим.
Они хотели понять, когда перестает работать случайность. Когда структура становится обязательной.
О чем речь? О графах.
Не о диаграммах с гистограммами. О сетях. Точки, соединенные линиями.
Представьте себе авиамаршруты. Или дружеские связи. Или молекулы.
Любой достаточно большой граф содержит две вещи.
Клику. Группу, где все знают всех.
Или независимое множество. Шайку людей, которые знают никого.
R(3,10). Вот вопрос. Насколько большим должен быть социальный граф, чтобы гарантировать наличие трех общих друзей или десяти незнакомцев?
Мы не знаем ответа.
Точные значения известны менее чем для тридцати чисел Рамсея. Остальные остаются загадкой.
Поэтому математики используют границы. Это ловушка.
Представьте себе мусоропресс из «Звездных войн». 🤖
Нижняя граница — это одна стена. Верхняя граница — другая.
Десялетиями разрыв между ними был огромным.
Здесь появился Домагож Брадач.
Он работает в Швейцарской высшей технической школе Цюриха (ETH Zurich). В прошлом месяце он опубликовал доказательство, которое разрушило барьер.
Стены сомкнулись. Близко. Восхитительно близко.
Вот как ему это удалось.
«Геометрию мы понимаем гораздо лучше, чем теорию графов», — Марсело Кампос.
Брадач не начинал с хаоса. Он начал с геометрии.
Сначала он построил гигантский граф. Жесткий. Алгебраический. Структурированный.
Зачем?
Потому что геометрия дает вам свойства бесплатно.
Затем он добавил хаос.
Он произвольно разрезал свой большой геометрический граф. Взял кусок. Удалил несколько «плохих» узлов.
Результат?
Графы, которые разрослись до огромных размеров. Но избежали паттернов.
Ни клик. Ни крупных независимых множеств.
Лишь балансируя на грани.
Лучшая верхняя граница? Застывшая с 1930-х годов. Брадач почти коснулся её.
«В идеальном мире я бы просто сказал: вот граф. И было бы дело сделано», — Домагож Брадач.
К сожалению, мир не идеален.
Он доказал, что такие графы могут существовать. Но не предоставил их в явном виде. Это вероятностный метод. Изобретенный Паулем Эрдёшем. Доказательство существования через случайность.
Доказательство Брадача было хорошим. Но это был не конец истории.
На сцену выходит ИИ.
OpenAI увидели статью. Скармли её своей модели для рассуждений.
ИИ нашел нюанс.
Не замену. А шлифовку.
Он устранил крошечную долю неопределенности, оставшуюся в границах Брадача.
Теперь нижняя и верхняя границы совпадают с точностью до полилогарифмических разрывов.
Практически ничто.
Игра окончена?
Еще нет.
«Мы систематически не пытаемся исправлять статьи с arXiv. Нам просто повезло», — Мехтааб Сахней (OpenAI).
ИИ не решил всё. Он лишь подкрутил гайки в работе Брадача.
Марсело Кампос любит напоминать нам, кто выполнил основную работу. Идея принадлежит человеку. ИИ просто подчистил края.
Тем не менее.
ИИ улучшил решение математической проблемы, которой почти сто лет. В течение нескольких недель.
Кто бы мог подумать?
Мы стоим вплотную к истине чисел Рамсея.
Разрыв тонкий. Как лед в апреле.
Наступите на него и посмотрите, что сломается.
