ИИ РАЗГАДЫВАЕТ ГОЛОВОЛОМКУ О РАСКРАСКЕ

Возьмите сеть точек, соединённых линиями, — то, что математики называют графом. Теперь раскрасьте точки так, чтобы две точки, соединённые линией, никогда не были одного цвета. Наименьшее число цветов, которого для этого достаточно, — хроматическое число графа. Знаменитый частный случай — теорема о четырёх красках, доказанная в 1977 году, название которой говорит само за себя: «Every planar map is four colorable» («Любую плоскую карту можно раскрасить в четыре цвета»).

Ставка Хадвигера 1943 года

В 1943 году Хадвигер предложил всеобъемлющее правило для всех графов. Уменьшайте граф, удаляя точки или линии и сливая две соединённые точки в одну. Результат называется минором. Хадвигер рассмотрел наибольший полный граф — скопление, в котором каждая точка соединена со всеми остальными, — который можно получить таким способом, и предположил, что необходимое число цветов никогда не превышает размера этого скопления.

Статья называет это «одной из старейших и фундаментальнейших проблем теории графов». Гипотеза доказана только для малых случаев: для скоплений размером до пяти, где она оказывается равносильной теореме о четырёх красках или сводится к ней. Начиная с шести, она открыта.

Всё ближе, логарифм за логарифмом

Раз точная формулировка не поддаётся, исследователи пытались ограничить число цветов некоторой функцией размера скопления, растущей как можно медленнее. Статья пересказывает историю продвижения. Десятилетиями лучшая оценка росла чуть быстрее, чем пропорционально, — на множитель, содержащий квадратный корень из логарифма. Несколько лет назад Норин, Постл и Сонг преодолели этот барьер. Делькур и Постл затем улучшили оценку ещё и, что особенно важно, показали, что достаточно разобраться с довольно маленькими графами. Лю и Ло снизили дополнительный множитель до тройного логарифма.

Естественная конечная точка — линейная гипотеза Хадвигера: фиксированного кратного размера скопления всегда достаточно. Именно это теперь заявляют, что доказали, Сергей Норин из Университета Макгилла в Монреале и Рафаэль Штайнер из Швейцарской высшей технической школы Цюриха (ETH).

Роль машины

Авторы говорят прямо: доказательство нашла GPT-6 Astra, модель OpenAI, следуя их указаниям. Сначала они попросили её доказать случай очень плотных графов, который считали недостающим фрагментом. Ей это удалось, пишут они, «всего через пару часов и после некоторого ободрения». Когда её попросили сделать одну зависимость явной, она охватила графы до определённого размера — но не совсем в нужном диапазоне. Тогда они попросили у неё оригинальную идею, чтобы закрыть пробел, и так появился «бутстрэп»-шаг окончательного доказательства. Почти ни одна из собственных конкретных идей авторов не уцелела, говорят они, кроме одного предложения о стягиваниях.

Текст написан людьми. Другая модель OpenAI помогла с вычиткой и библиографией. Авторы сообщают, что Codex от OpenAI создал формальную, проверяемую машиной версию всего доказательства в системе доказательств Lean, выложенную в сеть вместе с ранним черновиком, написанным ИИ. Полную ответственность за математику они берут на себя.

Внутри доказательства

Рассуждение состоит из двух половин:

1. Маленькие графы, мало цветов. Для графов, ненамного превышающих предел скопления, авторы показывают, что достаточно примерно вчетверо большего числа цветов, чем размер скопления. Отправная точка — результат Рида и Сеймура 1998 года: ослабленная, «дробная» форма раскраски уже подчиняется линейному правилу с множителем два. Новая работа превращает дробные раскраски в настоящие, добавляя в граф несколько лишних линий и находя огромные паросочетания во вспомогательной структуре.
2. Бутстрэп. Второе рассуждение на каждом шаге расширяет диапазон охваченных размеров графов на множитель четыре третьих в показателе степени ценой увеличения константы. Десять шагов доводят диапазон от одной трети примерно до 5,92, за порог 5, требуемый редукцией Делькура — Постла. Эта половина использует старый приём Дьярфаша, который, по словам авторов, никогда не применялся к этой задаче.

Авторы описывают доказательство как собранное из известных инструментов — «содержащееся в выпуклой оболочке существующих результатов», но не на её очевидном краю.

Что остаётся открытым

Константа огромна: грубая оценка даёт около 10¹⁰⁰. Авторы видят возможность опустить её ниже 10¹⁰, но считают, что для достижения, скажем, 100 потребуются новые идеи. Точная гипотеза Хадвигера осталась нетронутой: «Мы не определились», — пишут они. Статья — препринт; 41 странице новой математики теперь предстоит проверка другими специалистами.