Почти сто лет математики пытаются определить, сколько беспорядка может сохраняться в большой системе, прежде чем внутри неё обязательно возникнет упорядоченная структура. Поиском ответа занимается теория Рамсея. Новое доказательство заметно сузило область неопределённости в одной из старейших задач этой области, а спустя несколько недель ИИ-модель улучшила оценку и почти свела вместе две границы, которые десятилетиями оставались далеко друг от друга.
Теория Рамсея работает с математическими графами, то есть сетями из вершин и соединяющих их рёбер. Вершины могут обозначать людей, города, атомы и любые другие объекты. Рёбра показывают отношения между парами элементов: дружбу, авиарейсы, химические связи или другой тип взаимодействия.
Чем больше становится граф, тем труднее сохранить в нём полный беспорядок. В какой-то момент обязательно появляется одна из двух противоположных структур. Первая называется кликой. Внутри клики каждая вершина соединена со всеми остальными. В социальной сети клика из трёх вершин означает трёх людей, каждый из которых знаком с двумя другими. Вторая структура называется независимым множеством. Между его вершинами нет ни одного ребра, поэтому в примере с людьми все участники остаются незнакомыми друг с другом.
Числа Рамсея показывают, насколько большим должен стать граф, чтобы при любом расположении рёбер в нём гарантированно появилась клика заданного размера или независимое множество заданного размера. Обозначение R(3, 10), например, задаёт минимальное число людей, при котором обязательно найдутся либо трое попарно знакомых, либо десять человек, среди которых никто ни с кем не знаком.
Вычислять числа Рамсея чрезвычайно трудно. За десятилетия математики смогли точно определить меньше 30 значений. Даже R(3, 10), сравнительно небольшой случай по меркам теории, до сих пор остаётся неизвестным. Поэтому исследователи чаще ищут две оценки. Нижняя граница показывает размер, при котором граф ещё может избегать обеих заданных структур. Верхняя указывает предел, после которого хотя бы одна из них появится при любом устройстве сети.
Новое доказательство касается внедиагональных чисел Рамсея. В подобных задачах размеры клики и независимого множества заметно различаются. Математики фиксируют одну величину, например трёх попарно связанных людей, а вторую постепенно увеличивают: R(3, 10), R(3, 100), R(3, 1000) и дальше. Исследователей интересует уже не отдельное значение, а скорость роста всей последовательности.
Нижняя и верхняя оценки ограничивают неизвестный ответ с двух сторон. Повышение нижней границы доказывает, что граф без малых клик и больших независимых множеств может быть крупнее, чем удавалось подтвердить раньше. Понижение верхней границы показывает, что после определённого размера избежать одной из двух структур уже нельзя. Совпадение оценок по скорости роста дало бы почти полное описание поведения внедиагональных чисел Рамсея.
Математикам удалось существенно поднять нижнюю границу. Они построили семейство графов, которые сохраняют нужный беспорядок при гораздо большем числе вершин, чем позволяли прежние методы. Внутри таких сетей по-прежнему нет ни малых клик заданного размера, ни крупных независимых множеств. Новая оценка приблизилась к лучшей известной верхней границе, почти не менявшейся с 1930-х годов.
Главным инструментом для поиска нижних оценок долгое время оставался вероятностный метод. Математик не строит конкретный подходящий граф, а рассматривает множество случайных вариантов. Если хотя бы часть случайно собранных сетей обладает нужными свойствами, значит, подходящий граф существует, даже когда никто не может предъявить его в явном виде.
Метод появился в 1940-х годах и поначалу вызывал споры из-за непривычной логики. Классическое доказательство обычно показывает готовый объект и проверяет его свойства. В задачах Рамсея подобную конструкцию часто невозможно записать напрямую, поэтому существование нужного графа подтверждают через вероятность.
Новая схема начинается не с полностью случайной сети, а с большого графа, чья геометрическая и алгебраическая структура заранее задаёт часть нужных свойств. Такой каркас помогает контролировать связи между вершинами без отдельного анализа каждого ребра.
Геометрическое происхождение графа даёт готовый набор закономерностей. Расположение точек, расстояния, пересечения и алгебраические соотношения ограничивают возможные связи между вершинами. Математики получают сеть с предсказуемым внутренним устройством, а затем используют её как основу для дальнейшего отбора.
После подготовки крупного графа в построение добавляют случайность. Из сети выбирают случайный подграф нужного размера, затем удаляют небольшое число вершин, из-за которых могли бы возникнуть нежелательные клики или слишком большие независимые множества. Основная часть графа сохраняется и продолжает избегать обеих структур.
Сочетание геометрического каркаса, случайного отбора и точечного удаления проблемных вершин оказалось эффективнее полностью случайных построений. Подход позволил получить значительно более крупные графы без заданных комбинаций связей и тем самым повысить нижнюю оценку.
Разрыв между новой нижней границей и давно известной верхней сократился до полилогарифмических множителей. Под этим термином понимают поправки, которые растут как степени логарифма от размера графа. По сравнению с основной величиной они увеличиваются медленно, поэтому математики уже получили почти точное описание общей скорости роста.
Через несколько недель после публикации препринта доказательство передали внутренней рассуждающей ИИ-модели OpenAI. Система обнаружила, как усилить один из этапов построения, и ещё немного повысила нижнюю границу. После уточнения обе оценки совпали с точностью до полилогарифмических поправок.
Полного решения в строгом смысле пока нет. Между верхней и нижней границами сохраняется небольшой множитель, зависящий от логарифма размера графа. Однако основная скорость роста теперь определена намного точнее, чем в любой момент за примерно 90 лет исследований.
ИИ-модель не создала новый метод с нуля. Система работала с уже построенной схемой, основанной на геометрическом графе, случайном выборе подграфа и удалении мешающих вершин. Алгоритм нашёл более точный способ провести один из этапов и тем самым улучшил конечную оценку.
Совпадение по времени оказалось случайным. Исследователи OpenAI проверяли, насколько хорошо модель справляется с внедиагональными числами Рамсея, вскоре после появления препринта. Система получила доступ к доказательству, разобрала его логику и обнаружила возможность для уточнения. Компания не ведёт постоянный автоматический поиск улучшений во всех новых математических публикациях.
В результате задача продвинулась за счёт двух последовательных шагов. Сначала математики нашли новый способ строить очень крупные графы без малых клик и больших независимых множеств. Затем ИИ точнее настроил часть расчёта. Нижняя и верхняя границы приблизились настолько, что от 90-летней неопределённости остались только медленно растущие логарифмические поправки.