Охота на снарка: доказательство гипотезы о двойном покрытии циклами

Введение

Полтора месяца назад я писал о том, как внутренняя модель OpenAI опровергла гипотезу Эрдёша о единичных расстояниях — задачу, которой было уже лет семьдесят и над которой (в отличие от многих других задач Эрдёша) реально думало много профессиональных математиков. Тогда я закончил пост вопросом “что дальше, коллеги?”, и вот сегодня мы обсуждаем очередной ответ на этот вопрос.

10 июля 2026 года OpenAI выложила двухстраничный препринт со скромным названием “A proof of the cycle double cover conjecture“. Гипотеза о двойном покрытии циклами (cycle double cover conjecture, CDC) — одна из самых знаменитых открытых проблем теории графов, стоявшая с начала 1970-х. В разделе “Statement of AI use” написано коротко:

The proof in this note is entirely due to GPT 5.6 Sol Ultra and the writeup with Codex (with GPT 5.6 Sol).

Вместе с препринтом OpenAI опубликовала и полный промпт, которым модель запускали, — к нему мы ещё вернёмся, он сам по себе занятный документ.

Здесь сразу две новости; начну с плохой. В отличие от истории с единичными расстояниями, здесь (пока) нет сборника комментариев от ведущих математиков: препринту три дня, рецензирования не было, а у гипотезы CDC богатая история неудачных “доказательств”, в том числе выложенных на arXiv. Так что формальный статус пока в том, что это лишь заявка на результат, и моя “проверка” в этом посте вряд ли может официально считаться таковой, я всё-таки не совсем специалист.

Но есть и хорошая новость: доказательство двухстраничное и совершенно элементарное. Его может проверить любой человек, знающий линейную алгебру, — там нет ни компьютерного перебора, ни ссылок на глубокую теорию, только два классических результата из учебников, а дальше прямое доказательство голыми руками.

Поэтому этот пост устроен не так, как прошлый: гипотезу Эрдёша я пересказывал по чужим комментариям, а здесь мы разберём всё доказательство целиком, до последней строчки. А поскольку доказательство ещё и конструктивное — оно не просто утверждает, что покрытие существует, а объясняет, как его построить, — мы с автором доказательства (то бишь GPT 5.6 Sol) и Claude Fable его дополнительно проверили кодом: реализовали конструкцию и прогнали на десятках тысяч примеров, включая разные сложные конструкции заковыристых семейств графов. Спойлер: ошибок я не нашёл, всё работает; подробности и картинки будут ниже.

План такой: сначала разберёмся, что такое двойное покрытие циклами и почему это было так трудно; потом введём два главных языка этой области — рёберные раскраски и потоки; потом пройдём по самому доказательству; а в конце поговорим о том, как это было получено, что говорят математики и что теперь остаётся от теории снарков.

Что такое двойное покрытие циклами

Постановка задачи. Все графы у нас будут конечными и неориентированными; разрешены кратные рёбра (два ребра между одной и той же парой вершин), и циклом мы называем связный подграф, в котором у каждой вершины ровно два инцидентных ребра: треугольник, четырёхугольник, пятиугольник и так далее; пара параллельных рёбер тоже считается циклом (длины 2). Двойное покрытие циклами графа $G$ — это набор циклов (возможно, с повторениями), в котором каждое ребро графа встречается суммарно ровно два раза.

То, что один раз не получится, было известно давно: разбить граф на рёберно-непересекающиеся циклы можно только если все степени чётные. Это классическая теорема Веблена, близкая родственница эйлеровых обходов. А вот про два раза можно надеяться всегда: у каждого ребра появляется “две стороны”, и, как мы сейчас увидим, это не случайная метафора.

Пример, с которого всё начинается. Возьмём планарный граф, нарисованный на плоскости без пересечений, например полный граф $K_4$ :

Рисунок делит плоскость на грани — здесь три треугольника внутри и одна внешняя грань. Граница каждой грани — цикл, и каждое ребро лежит на границе ровно двух граней: с одной стороны от ребра одна грань, с другой — другая. Значит, граничные циклы граней образуют двойное покрытие! На правой картинке это видно буквально: обведём каждую грань замкнутой линией вдоль её границы, и вдоль каждого ребра пройдут ровно две линии.

Так что для планарных графов (без мостов, о них ниже) гипотеза тривиальна. Уже отсюда видно, что задача глубоко связана с топологией: двойное покрытие циклами — это что-то вроде “набора граней” для графа, который, может быть, ни в какую плоскость и не вкладывается.

Есть и точная версия этой интуиции, гипотеза о круговых вложениях (circular embedding conjecture): всякий двусвязный граф можно вложить в какую-нибудь замкнутую поверхность — сферу, тор или что-нибудь с ещё большим числом ручек — так, чтобы каждая грань была ограничена простым циклом. Из неё CDC следует немедленно, тем же рассуждением о рёбрах на краю граней.

Единственное препятствие. Когда двойного покрытия точно нет? Когда в графе есть мост — ребро, при удалении которого граф распадается:

Мост не может лежать ни на одном цикле вообще (цикл, пройдя по мосту в одну сторону, не сможет вернуться обратно по другим рёбрам). Значит, никакой набор циклов его не покроет даже один раз. Гипотеза утверждает, что это препятствие — единственное:

Гипотеза (Szekeres, 1973; Itai–Rodeh, 1978; Seymour, 1979). Каждый граф без мостов имеет двойное покрытие циклами.

Гипотезу связывают и с именем классика теории графов Татта — в списке литературы препринта в качестве источника стоит даже “personal correspondence with H. Fleischner, July 22, 1987”.

Почему в неё верили. Гипотеза CDC — редкий пример утверждения, в которое верили практически все. Контрпример обязан быть непланарным, а минимальный контрпример, как мы увидим ниже, обязан быть так называемым снарком; снарки же — вещь редкая и хорошо изученная, и на всех известных снарках гипотеза была проверена.

Более того, Brinkmann, Goedgebeur, Hägglund и Markström (2013) сгенерировали все снарки до 36 вершин включительно (их там миллионы) и проверили на них даже усиленные версии гипотезы. А Alspach, Goddyn и Zhang ещё в 1994 году доказали CDC для всех графов, не содержащих граф Петерсена в качестве подграфа.

Проблема была в том, что все эти результаты обходили стороной “ядро” задачи, и общий случай не поддавался никому больше полувека. В обзоре открытых проблем CDC всегда была в статусе “outstanding open problem”, а Франсуа Джегер в обзоре 1985 года называл её одной из главных открытых задач теории графов. Так что здесь, как и в случае единичных расстояний, нет сомнений, что умные люди над этой задачей действительно думали, и немало.

Почему достаточно кубических графов, или охота на снарка

Начну с классических результатов; они одновременно позволят существенно сузить условие задачи и дадут некоторую интуицию происходящего.

Первое стандартное рассуждение в этой области — свести всё к кубическим графам, то есть графам, где у каждой вершины ровно три инцидентных ребра.

Рассуждение такое. Возьмём минимальный (по числу вершин, потом рёбер) контрпример к гипотезе. Вершин степени 0 и 1 в нём нет (изолированная вершина не мешает, а висячее ребро — это мост).

Вершину степени 2 можно “разгладить”: заменить два её ребра одним (то есть удалить вершину), найти двойное покрытие меньшего графа (он меньше минимального контрпримера, значит, покрытие у него есть) и вернуть вершину на место, удлинив проходящие циклы. Значит, вершин степени 2 в минимальном контрпримере быть не может.

А вершину степени 4 и больше можно расщепить — раздуть в маленький цикл из вершин степени 3:

При этом каждый цикл нового графа проецируется в замкнутый маршрут старого (достаточно стянуть раздутый цикл обратно в точку), и из двойного покрытия нового графа получается двойное покрытие старого.

Единственная тонкость здесь в том, что расщеплять надо аккуратно, чтобы не создать мост. То, что это всегда возможно, — стандартная лемма о расщеплении вершин (vertex splitting lemma), известная уже очень давно (Fleischner, 1992). Так что получается, что если гипотеза верна для кубических графов без мостов, она верна вообще для всех графов без мостов.

Петли в кубическом графе тоже невозможны: вершина с петлёй занимает ею две из своих трёх “валентностей”, и третье ребро автоматически оказывается мостом.

Кубические графы и три цвета. А для кубических графов есть свой отдельный инструмент — рёберные раскраски. Правильная рёберная 3-раскраска — это раскраска рёбер в три цвета так, чтобы в каждой вершине сходились три ребра трёх разных цветов. По классической теореме Визинга хроматический индекс простого кубического графа равен 3 или 4, то есть все кубические графы делятся на трёхцветные и четырёхцветные.

Ещё Секереш в той самой статье 1973 года заметил: если кубический граф без мостов рёберно 3-раскрашиваем, то двойное покрытие у него есть. Конструкция очень простая: возьмём два цветовых класса, скажем красный и синий. В каждой вершине есть ровно одно красное и ровно одно синее ребро, поэтому красно-синее объединение — это подграф, в котором все степени равны 2, то есть дизъюнктное объединение циклов (чётной длины, цвета чередуются). Вот как это выглядит на призме:

Таких двуцветных объединений три: красный+синий, красный+зелёный, синий+зелёный. Каждое ребро, будучи, скажем, красным, попадает ровно в два из них. Вот и двойное покрытие!

Снарки. Значит, минимальный контрпример к CDC — это кубический граф без мостов, который нельзя рёберно раскрасить в 3 цвета. Такие графы (с дополнительными условиями невырожденности: обхват не меньше 5 и цикловая 4-связность, чтобы не считать тривиальные модификации) называются снарками — в честь того самого неуловимого зверя из поэмы Льюиса Кэрролла.

Название предложил, кстати, известный популяризатор математики Мартин Гарднер в 1976 году, и оно тогда хорошо подходило: снарки действительно долгое время были почти неуловимы.

Первый и главный снарк человечество нашло ещё в 1898 году — это граф Петерсена из десяти вершин и пятнадцати рёбер, главный контрпример всея теории графов.

Проверить, что он не 3-раскрашиваем по рёбрам, — хорошее упражнение (подсказка: рёбра, не попавшие в один цветовой класс, образуют объединение циклов чётной длины, а все 2-факторы графа Петерсена — это пары пятиугольников).

Второй снарк нашёлся только в 1946 году (Blanuša, 1946), а бесконечные семейства снарков построил Isaacs (1975); вот, например, его “цветок” $J_5$ :

Здесь синий внутренний пятиугольник и длинный красный десятиугольник соединены пятью “тройниками”-звёздочками, и такая конструкция работает для любого нечётного числа лепестков, начиная с пяти.

Но здесь важно отметить, что снарки являются контрпримерами к раскрашиваемости, а не к двойному покрытию. У графа Петерсена двойное покрытие есть, симметричное и красивое — шесть пятиугольников:

(Это, кстати, как раз грани вложения графа Петерсена в проективную плоскость, так что здесь снова появляется топология.)

Но конструкция Секереша для снарков не работает, и нужно было придумать что-то другое.

За полвека в теории графов сложился целый небольшой жанр: свести какую-нибудь гипотезу к снаркам и убедиться, что на всех известных снарках она верна. Так устроены CDC, гипотеза Фулкерсона о совершенных паросочетаниях, гипотеза Татта о 5-потоках… все дороги ведут к графу Петерсена, но дальше обычно не двигаются.

Язык потоков

Второй язык, на котором написано доказательство, — это потоки Татта. Это куда более классический объект, и с ним вы, вероятно, знакомы, но на всякий случай поясню. Идея пришла из физики: представьте, что по рёбрам графа течёт ток, и давайте введём там правила Кирхгофа. Вы наверняка слышали о потоках в контексте задачи о максимальном потоке:

Но нам сейчас нужно чуть более общее определение.

Определение. Зафиксируем на каждом ребре произвольное направление (стрелочку) и абелеву группу $A$ . $A$ -поток — это функция $f$ , приписывающая каждому ребру элемент группы $A$ так, что в каждой вершине выполняется закон Кирхгофа: сумма значений на входящих рёбрах равна сумме на исходящих. Поток называется нигде не нулевым (nowhere-zero, NZ-flow), если $f(e) \neq 0$ на каждом ребре. Чтобы перевернуть стрелочку на ребре, достаточно заменить $f(e)$ на $-f(e)$ , поэтому существование нигде не нулевого потока от выбора стрелочек не зависит.

Татт в 1954 году доказал классический, но всё равно довольно удивительный факт: количество нигде не нулевых $A$ -потоков зависит не от структуры группы $A$ , а только от её размера $|A|$ (и является многочленом от $|A|$ — “потоковым многочленом”). Поэтому говорят просто о $k$ -потоках: есть нигде не нулевой поток в какой-нибудь группе размера $k$ — значит, есть в любой другой того же размера (а значит, и целочисленный поток со значениями $0 < |f(e)| < k$ , это тоже эквивалентная формулировка). На практике это развязывает руки: группу можно выбирать поудобнее.

Зачем всё это нужно? Затем, что для планарных графов нигде не нулевые потоки — это в точности раскраски: граф без мостов, нарисованный на плоскости, имеет правильную раскраску граней в $k$ цветов тогда и только тогда, когда у него есть нигде не нулевой $k$ -поток (цвета — элементы $\mathbb{Z}_k$ , поток на ребре — разность цветов слева и справа).

Знаменитая теорема о четырёх красках на этом языке звучит так: у всякого планарного графа без мостов есть нигде не нулевой 4-поток. Но при этом потоки определены для любых графов, не только планарных!

Татт предположил, что от планарности можно почти избавиться: его гипотеза о 5-потоках (“у всякого графа без мостов есть нигде не нулевой 5-поток”) известна с 1954 года и остаётся открытой проблемой до сих пор.

Зато известны два важных безусловных результата:

теорема о 8-потоках (Kilpatrick, 1975; Jaeger, 1976): у всякого графа без мостов есть нигде не нулевой 8-поток;
теорема о 6-потоках (Seymour, 1981): и даже 6-поток тоже есть.

Потоки над $\mathbb{F}_2^k$ — это чётные подграфы. Теперь выберем группу поудобнее. Пусть $\Gamma = \mathbb{F}_2^3$ — векторы из трёх бит со сложением по модулю 2 (XOR); их восемь: от $000$ до $111$ . В этой группе $-a = a$ , так что стрелочки вообще не нужны: условие Кирхгофа в вершине просто говорит, что XOR значений на инцидентных рёбрах равен нулю.

Теорема о 8-потоках говорит, что рёбра любого графа без мостов можно пометить ненулевыми трёхбитовыми векторами так, чтобы в каждой вершине XOR сходился в ноль. Именно в таком виде мы её и будем использовать.

У потоков над $\mathbb{F}_2^k$ есть наглядная интерпретация. Посмотрим на один бит потока, скажем, первый: рёбра, где он равен 1, образуют подграф, в котором каждая вершина имеет чётную степень (иначе XOR не сойдётся) — так называемый чётный подграф. А чётный подграф — это всегда объединение рёберно-непересекающихся циклов. То есть $\mathbb{F}_2^k$ -поток — это система из $k$ чётных подграфов, а условие “нигде не нулевой” значит, что они вместе покрывают все рёбра.

Для кубических графов случай $k=2$ особенно нагляден: нигде не нулевой $\mathbb{F}_2^2$ -поток — это то же самое, что рёберная 3-раскраска. Ненулевых значений три: $01$ , $10$ , $11$ ; в каждой вершине они обязаны встретиться по одному разу (единственный способ получить нулевой XOR из трёх ненулевых значений — взять все три разных). Вот наша призма ещё раз, теперь через потоки:

Конструкция Секереша тоже переводится на язык потоков и обобщается с кубических графов на любые: если у графа есть нигде не нулевой 4-поток $f$ со значениями в $\mathbb{F}_2^2$ , рассмотрим три подграфа:

первый бит $f$ равен 1,
второй бит $f$ равен 1,
XOR битов равен 1.

Каждый из них чётный, а каждое ребро попадает ровно в два: из трёх вариантов “первый бит”, “второй бит”, “их XOR” на любом ненулевом значении ровно два истинны.

Получается, что нигде не нулевой 4-поток влечёт двойное покрытие циклами — это классический результат, известный с 1970-х годов. Но проблема остаётся всё та же: у снарков как раз 4-потока и нет (для кубических графов это эквивалентно 3-раскрашиваемости).

От четырёх к двум. А что даёт гарантированный теоремой Джегера–Килпатрика 8-поток $f$ со значениями в $\mathbb{F}_2^3$ ?

Повторим тот же трюк: у $\mathbb{F}_2^3$ есть 7 ненулевых линейных функционалов $\theta$ (способов “свернуть” три бита в один: первый бит, второй, XOR первого и третьего и так далее), и каждый из них даёт чётный подграф $\{e : \theta(f(e)) = 1\}$ .

Но теперь каждое ребро попадает не в два, а ровно в четыре подграфа из семи: значение $f(e) \neq 0$ фиксировано, и из 8 функционалов (включая нулевой) на нём не зануляется ровно половина. Получается покрытие циклами, где каждое ребро покрыто ровно четыре раза. Вот как это выглядит на графе Петерсена:

В первой панели — нигде не нулевой поток $f$ (именно этот поток ещё появится в конце поста), в остальных семи — носители семи функционалов $\theta$ . Каждая панель — чётный подграф, то есть объединение непересекающихся циклов. А кружком во всех панелях отмечено одно и то же ребро, со значением потока $f(e) = 101$ : оно выделено ровно в четырёх панелях, при $\theta \in \{001, 011, 100, 110\}$ — ровно для тех $\theta$ , для которых $\theta(101) = 1$ . И так с каждым ребром.

Такие конструкции подробно изучали Bermond, Jackson, Jaeger(1983) — покрытия чётными подграфами с предписанными кратностями; с этими учёными мы ещё встретимся ниже.

Итак, мы можем покрыть каждое ребро четыре раза. А надо — дважды. Так что вся гипотеза CDC, по сути, состоит в том, чтобы сделать этот шаг от четырёхкратного покрытия к двукратному.

Первый шаг: у каждого ребра два цвета

Теперь сам препринт. Его конструкцию я изложу полностью, со всеми доказательствами, но своими словами; сверяться можно с оригиналом — там всё уместилось в две страницы.

Благодаря тому, что мы обсудили выше, мы уже понимаем, что достаточно разобраться с кубическими графами без петель (с кратными рёбрами), у которых есть нигде не нулевой поток со значениями в группе $\mathbb{F}_2^3$ .

Ключевая идея — новая переформулировка того, что мы ищем. Будем считать восемь элементов $\mathbb{F}_2^3$ цветами. В конструкции Секереша каждое ребро получало один цвет из трёх; теперь каждое ребро $e$ получит пару $P_e = \{s_1, s_2\}$ из двух различных цветов; цвета по-прежнему являются элементами $\mathbb{F}_2^3$ .

То есть у каждого ребра теперь два цвета. Потребуем выполнения одного локального условия:

Вокруг каждой вершины каждый цвет $s \in \Gamma$ встречается в парах инцидентных рёбер 0 или 2 раза.

Представьте, что каждый цвет $s$ — это нитка своего цвета, и ребро $e$ несёт на себе две нитки: цветов $s_1$ и $s_2$ из его пары. Тогда условие говорит, что в каждой вершине нитку любого цвета можно “пропустить насквозь”: цвет либо вообще не заходит в вершину, либо заходит по одному ребру и выходит по другому. А нитка, которая нигде не обрывается, обязана замыкаться в циклы:

Лемма 1 (лемма 2.1 препринта). Если такая расстановка пар существует, то у графа есть двойное покрытие циклами.

Доказательство. Для каждого цвета $s \in \Gamma$ соберём подграф $M_s$ из всех рёбер, у которых в паре найдётся $s$ . Локальное условие говорит, что у каждой вершины в $M_s$ степень 0 или 2. Значит, $M_s$ — дизъюнктное объединение циклов. А каждое ребро лежит ровно в двух подграфах $M_s$ , потому что в паре $P_e$ два элемента. Теперь соберём циклы всех восьми подграфов вместе, и готово: каждое ребро покрыто дважды. $\blacksquare$

Это можно увидеть на конструкции Секереша: если у нас есть рёберная 3-раскраска, давайте зафиксируем два ненулевых элемента $e_1 \neq e_2$ и выдадим красным рёбрам пару $\{0, e_1\}$ , синим — $\{0, e_2\}$ , зелёным — $\{e_1, e_2\}$ . Вокруг каждой вершины (где по одному ребру каждого цвета) элемент $0$ встречается дважды (красное и синее ребро), $e_1$ дважды (красное и зелёное), $e_2$ дважды (синее и зелёное).

Так что лемма 1 — это “ослабленная 3-раскраска”: цветов теперь восемь, у каждого ребра их два, и правило согласования вокруг вершины более слабое (более гибкое).

Весь вопрос в том, как построить такую расстановку пар для снарков, где честной раскраски нет.

Второй шаг: строим пары из потока

Первый шаг, хотя и содержал уже ключевую идею, но по сути был переформулировкой классических результатов. А теперь начинается собственно новизна в доказательстве GPT 5.6.

Пусть $f$ — нигде не нулевой $\mathbb{F}_2^3$ -поток; он есть по теореме о 8-потоках. Посмотрим на произвольную вершину $v$ . У неё три ребра; обозначим их $a, b, c$ (порядок выберем произвольно и зафиксируем), а значения потока на них обозначим через $x = f(a)$ , $y = f(b)$ , $z = f(c)$ .

Условие Кирхгофа говорит, что $x + y + z = 0$ , то есть

$z = x + y$

(напомню, что мы в $\mathbb{F}_2^3$ , где плюс — это XOR, и минусов нет).

Все три значения ненулевые, и легко видеть, что они попарно различны: если бы, скажем, было верно, что $x = y$ , то мы бы получили $z = x + y = 0$ . Кстати, отсюда же видно, что множество $W = \{0, x, y, z\}$ замкнуто относительно сложения, то есть это двумерное подпространство в $\mathbb{F}_2^3$ ; эта деталь ещё сыграет ниже.

Теперь выберем элемент $t \in \mathbb{F}_2^3$ — “базовый цвет” вершины $v$ — и раздадим трём рёбрам вокруг $v$ следующие пары:

$a \mapsto \{t,\; t+x\}, \qquad b \mapsto \{t+x,\; t+z\}, \qquad c \mapsto \{t,\; t+z\}.$

Проверим локальное условие: цвет $t$ встречается в парах рёбер $a$ и $c$ (дважды), цвет $t+x$ — в парах $a$ и $b$ (дважды), цвет $t+z$ — в парах $b$ и $c$ (дважды), а больше никакие цвета не встречаются вовсе. Все три цвета $t$ , $t+x$ , $t+z$ различны (поскольку $x \neq z$ и оба ненулевые), так что всё честно: вокруг $v$ каждый цвет встречается 0 или 2 раза. Итого получаем, что локальное условие выполнено.

Полезно записать эти пары единообразно. Введём сдвиги $g_{v,e}$ — по одному на каждую пару (вершина, инцидентное ребро):

$g_{v,a} = 0, \qquad g_{v,b} = x, \qquad g_{v,c} = 0,$

и тогда все три пары выше — это пары вида

${\,t + g_{v,e},\; t + g_{v,e} + f(e)\,}.$

Действительно: для $a$ получаем ${t, t+x}$ ; для $b$ — ${t+x, t+x+y} = {t+x, t+z}$ ; для $c$ — ${t, t+z}$ . То есть пара ребра — это “базовый цвет вершины, сдвинутый на $g$ , плюс тот же цвет, сдвинутый ещё и на значение потока”.

Вот иллюстрация, слева в общем виде, справа с конкретными числами:

Заметьте, что вся конструкция локальная, и в каждой вершине свой произвольный базовый цвет $t = t_v$ . Это богатое семейство потенциальных раскрасок: в каждой вершине 8 вариантов $t_v$ , плюс ещё свобода в выборе порядка рёбер $a,b,c$ , который определяет сдвиги $g$ .

Проблема склейки. Но у ребра $e = uv$ два конца! Вершина $u$ предлагает ему пару ${t_u + g_{u,e},\; t_u + g_{u,e} + f(e)}$ , вершина $v$ — пару ${t_v + g_{v,e},\; t_v + g_{v,e} + f(e)}$ . Чтобы расстановка пар была определена корректно, эти две пары должны совпасть на каждом ребре графа одновременно:

Обе пары имеют вид ${A, A+p}$ и ${B, B+p}$ с одинаковым “шагом” $p = f(e) \neq 0$ .

Когда такие пары совпадают как множества? Либо $A = B$ , либо $A = B + p$ (тогда множества совпадают “крест-накрест”); одной формулой это можно записать как $A + B \in \{0, p\}$ .

Подставляя наши $A$ и $B$ и обозначая $d_e = g_{u,e} + g_{v,e}$ , получаем, что пары на ребре $e = uv$ согласованы тогда и только тогда, когда для какого-нибудь $\varepsilon_e \in \{0, 1\}$ выполняется равенство

$t_u + t_v + \varepsilon_e f(e) = d_e.$

И вот мы пришли к ключевому шагу доказательства.

Сдвиги $g$ и “невязки” $d_e$ — известные величины, они вычисляются по потоку $f$ и выбранным порядкам рёбер. А базовые цвета $t_v$ (по три бита на вершину) и переключатели $\varepsilon_e$ (по биту на ребро) — неизвестные.

Всё написанное выше — это система линейных уравнений над полем $\mathbb{F}_2$ , по три битовых уравнения на каждое ребро. Осталось доказать, что она всегда имеет решение.

Лемма 2 (лемма 2.2 препринта). Система склейки разрешима для любого кубического графа без петель, любого нигде не нулевого $\mathbb{F}_2^3$ -потока $f$ и любого выбора порядков рёбер (то есть сдвигов $g$ ).

Интермедия: вся конструкция на примере

Прежде чем доказывать разрешимость в общем виде, давайте посмотрим на все наши объекты на конкретном примере, а именно на самом маленьком кубическом графе, полном графе $K_4$ . Он, конечно, не снарк, и для него всё можно было бы сделать по Секерешу, но механика конструкции здесь видна хорошо. Берём нигде не нулевой поток:

На картинке сверху поток изображён слева: в каждой вершине XOR трёх значений равен $000$ (проверьте!). Справа — сдвиги $g$ и невязки $d$ . Скажем, в вершине $0$ мы упорядочили рёбра как $a = \{0,1\}$ , $b = \{0,2\}$ , $c = \{0,3\}$ , поэтому по определению сдвигов $g_{0,\{0,2\}} = f(\{0,1\}) = 001$ , а два других сдвига в этой вершине нулевые; и так возле каждой вершины появляется ровно по одному ненулевому сдвигу. Невязка ребра — это XOR сдвигов с двух его концов: например, у ребра $\{1,2\}$ получается $d = 001 + 010 = 011$ (сдвиг $001$ со стороны вершины $1$ и сдвиг $010$ со стороны вершины $2$ ), а у ребра $\{0,1\}$ оба сдвига нулевые, и $d = 000$ .

Теперь выписываем систему склейки — шесть уравнений, по одному на ребро — и решаем её (хоть методом Гаусса, хоть просто подбором):

Наше решение выдаёт вершинам $0$ и $1$ базовый цвет $000$ , вершинам $2$ и $3$ — цвет $011$ , а на рёбрах $\{0,2\}$ и $\{0,3\}$ добавляет переключатель $\varepsilon = 1$ (это те рёбра, где пары с двух концов совпадают “крест-накрест”).

Подставляя найденные $t_v$ в формулу для пар, получаем расстановку, в которой вокруг каждой вершины каждый цвет встречается 0 или 2 раза; теперь можно собирать подграфы $M_s$ . Непустых получается четыре:

Узнаёте? Это в точности четыре треугольные грани планарного рисунка $K_4$ , с картинки, с которой начинался этот пост. Наша конструкция, начав с потока, сама пришла к вложению графа в плоскость. Конечно, для планарного графа в этом ничего нового или интересного нет, но подчеркну ещё раз: самой конструкции всё равно, планарен граф или нет — для графа Петерсена она точно так же выдаст двойное покрытие, и мы его ещё увидим ниже.

А теперь вернёмся к самой лемме, но прежде чем её доказывать, оценим ситуацию. Неизвестных у нас $3n + m$ битов, где $n$ — число вершин, $m$ — число рёбер; уравнений $3m$ . Для кубического графа $m = 3n/2$ , поэтому $3n + m = 3n + 3n/2 = 3m$ : система квадратная! Но радоваться рано, потому что она очевидно вырожденная; например, прибавить ко всем $t_v$ одну и ту же константу эквивалентно тому, чтобы ничего не изменить, ведь все уравнения зависят только от сумм $t_u + t_v$ .

Значит, у однородной системы есть нетривиальное ядро, а значит, отображение “неизвестные $\to$ левые части” не сюръективно, и не всякая правая часть достижима.

Лемма утверждает, что конкретная правая часть $d$ , происходящая из потока, достижима всегда. Здесь, очевидно, должно сыграть какое-то специальное свойство $d$ ; и этим свойством окажется чётность.

Шаг 3: чудо чётности

Когда система линейных уравнений $Lw = d$ (где $w$ — вектор из всех наших неизвестных) неразрешима? Когда из уравнений выводится противоречие: можно так скомбинировать уравнения (над $\mathbb{F}_2$ — просто выбрать подмножество и сложить), чтобы слева всё сократилось в тождественный ноль, а справа остался не ноль.

Классическая линейная алгебра (в функциональном анализе это называют альтернативой Фредгольма, в конечномерном случае это просто утверждение $\mathrm{im}\, L = (\ker L^{\top})^{\perp}$ ) говорит, что это единственная возможная причина неразрешимости:

Система разрешима $\Longleftrightarrow$ всякая комбинация уравнений, зануляющая левую часть, зануляет и правую.

Разберёмся, как выглядят “комбинации уравнений”. Это единственная действительно техническая часть доказательства, и в целом её можно пропустить. Но я бы рекомендовал всё-таки разобраться, потому что хоть она и техническая, но на удивление простая для доказательства знаменитой открытой проблемы.

На каждое ребро $e$ приходится три битовых уравнения (по числу бит в $\mathbb{F}_2^3$ ), и выбрать их подмножество с последующим сложением — это то же самое, что применить к обеим частям векторного уравнения ребра линейную функцию $\eta_e : \mathbb{F}_2^3 \to \mathbb{F}_2$ .

Так что комбинация уравнений всей системы — это набор функций $\eta = (\eta_e)$ , по одной на ребро (в том числе здесь может быть тождественно нулевая функция, которая значит “уравнения этого ребра не берём”).

Комбинация зануляет левую часть, если после сложения исчезают все неизвестные:

коэффициент при $t_v$ : в левых частях $t_v$ входит в уравнения всех трёх рёбер вокруг $v$ , поэтому нужно, чтобы $\sum_{e \ni v} \eta_e = 0$ (как функция) для каждой вершины $v$ ;
коэффициент при $\varepsilon_e$ : этот бит входит только в уравнение своего ребра с коэффициентом $f(e)$ , поэтому нужно, чтобы $\eta_e(f(e)) = 0$ для каждого ребра $e$ .

Назовём набор функций $\eta$ , удовлетворяющий этим двум условиям, препятствием. По альтернативе Фредгольма лемма 2 сводится к следующему: для всякого препятствия $\eta$ выполнено

$\sum_{e} \eta_e(d_e) = 0.$

То есть любое препятствие, занулив левую часть, обязано занулить и правую; если это так, то противоречия не выведешь, и система разрешима.

Локальный анализ. Зафиксируем вершину $v$ с рёбрами $a, b, c$ и потоками $x, y, z = x+y$ и посмотрим, что условия препятствия говорят локально. Во-первых,

$\eta_a + \eta_b + \eta_c = 0.$

Во-вторых,

$\eta_a(x) = \eta_b(y) = \eta_c(z) = 0.$

Обозначим $\lambda_v = \eta_b(x)$ и вычислим:

$0 = \eta_c(z) = (\eta_a + \eta_b)(x + y) = \underbrace{\eta_a(x)}_{=0} + \eta_a(y) + \eta_b(x) + \underbrace{\eta_b(y)}_{=0},$

откуда $\eta_a(y) = \eta_b(x)$ ; обозначим это значение через $\lambda_v = \eta_a(y) = \eta_b(x)$ .

Теперь заметим, что вклад вершины $v$ в интересующую нас сумму легко выражается через $\lambda_v$ . Мы ведь знаем, что $d_e = g_{u,e} + g_{v,e}$ , поэтому $\sum_e \eta_e(d_e) = \sum_v \sum_{e \ni v} \eta_e(g_{v,e})$ — это просто перегруппировка слагаемых по концам рёбер (здесь используется, что петель нет: у каждого ребра два разных конца).

А вокруг $v$ сдвиги почти все нулевые: $g_{v,a} = g_{v,c} = 0$ , $g_{v,b} = x$ , так что

$\sum_{e \ni v} \eta_e(g_{v,e}) = \eta_b(x) = \lambda_v.$

Ключевое наблюдение. Утверждается, что $\lambda_v$ — это чётность числа ненулевых функционалов среди $\eta_a, \eta_b, \eta_c$ . Проверим оба случая.

Случай $\lambda_v = 0$ . Тогда $\eta_a$ зануляется и на $x$ , и на $y$ (мы только что доказали, что $\eta_a(y) = \lambda_v = 0$ ), то есть зануляется на всём подпространстве $W = \langle x, y \rangle = \{0, x, y, z\}$ — помните, я обещал, что мы его ещё встретим?

Аналогично, $\eta_b$ зануляется на $W$ (на $x$ по определению $\lambda_v$ , на $y$ по условию препятствия), и $\eta_c = \eta_a + \eta_b$ тогда тоже.

Но $W$ — двумерное подпространство трёхмерного пространства $\Gamma$ , и функционалы, зануляющиеся на нём, образуют одномерное пространство: нулевой и ровно один ненулевой; назовём его $\theta$ . Значит, каждый из $\eta_a, \eta_b, \eta_c$ — это либо $0$ , либо $\theta$ ; а поскольку их сумма равна нулю, $\theta$ встречается среди них чётное число раз: ноль или два. Итого получили, что чётность ненулевых равна 0, и это совпадает с $\lambda_v$ .

Случай $\lambda_v = 1$ . Выпишем значения функционалов на базисе $(x, y)$ подпространства $W$ : у $\eta_a$ это $(0, 1)$ , у $\eta_b$ — $(1, 0)$ , у $\eta_c = \eta_a + \eta_b$ — $(1, 1)$ . Все три ненулевые (что бы функционалы ни делали на третьей координате). Ненулевых три, чётность 1, то есть опять всё сходится.

Финальный аккорд. Складываем по всем вершинам:

$\sum_e \eta_e(d_e) = \sum_v \lambda_v = \sum_v \#\{e \ni v : \eta_e \neq 0\} \bmod 2.$

Но в последней сумме каждое ребро $e$ с $\eta_e \neq 0$ посчитано ровно два раза — по разу на каждом конце! Это тот же самый двойной подсчёт, которым первокурсникам доказывают “лемму о рукопожатиях” о том, что сумма степеней вершин в графе чётна.

Значит, сумма чётна, то есть равна нулю в $\mathbb{F}_2$ . Это значит, что любое препятствие зануляет правую часть, то есть система склейки разрешима, расстановка пар существует, и по лемме 1 двойное покрытие циклами есть. $\blacksquare$

Вот и всё доказательство. Давайте перечислим, что мы использовали:

сведение к кубическим графам — стандартный факт из середины 1980-х;
теорема о 8-потоках Килпатрика–Джегера — оттуда же;
собственно новые конструкции — переформулировка с парами цветов, локальный анализ из потока и лемма о разрешимости системы, где нет ничего, кроме линейной алгебры над $\mathbb{F}_2$ и подсчёта чётности.

Ни перебора случаев, ни ста страниц выкладок, ни теории, выходящей за пределы обычного курса теории графов. Конечно, я мог что-то пропустить, но кажется, что ошибке тут прятаться особо негде.

Проверяем руками и кодом

Думаю, многие сядут разбирать препринт с мыслью “где-то здесь должна быть ошибка”: у CDC длинная история ложных доказательств, а тут двухстраничное решение полувековой открытой проблемы. Мы с вами прошли по каждому переходу, и я честно не нашёл, к чему придраться. Использованные внешние результаты (сведение к кубическим графам и 8-поток) общеизвестны и многократно передоказаны в учебниках.

Но у этого доказательства есть свойство, которое сильно упрощает если не его проверку, то уж точно перебор примеров: оно конструктивное. По графу и потоку строится конкретная система линейных уравнений; её можно решить хоть бы и методом Гаусса, получая пары, из пар — подграфы $M_s$ , из них — циклы.

Каждый шаг доказательства выше можно запрограммировать, а каждое промежуточное утверждение — проверить assert’ом: что пары с двух концов ребра совпали, что вокруг каждой вершины каждый цвет встречается 0 или 2 раза, что $M_s$ распадаются в циклы, что каждое ребро покрыто ровно дважды. Если бы в доказательстве леммы 2 был изъян, то на каком-нибудь графе с каким-нибудь потоком система оказалась бы неразрешимой, и мы бы смогли обнаружить.

Мы с Claude Code попробовали перебрать кое-какие классические примеры. Что проверялось:

граф Петерсена: у него ровно 28 560 нигде не нулевых $\mathbb{F}_2^3$ -потоков, и мы перебрали все (плюс случайные перестановки локальных порядков рёбер); система разрешима всегда, покрытие корректно всегда;
снарки: цветки Айзекса $J_5, J_7, \ldots, J_{13}$ , граф Титце, граф Петерсена с раздутыми в треугольники вершинами (это стандартный способ плодить нераскрашиваемые кубические графы) — проверили десятки случайных потоков на каждом;
мультиграфы с кратными рёбрами: тета-граф (две вершины, три параллельных ребра), кольца из двойных рёбер и случайные кубические мультиграфы; тем самым мы проверили, что у леммы всё в порядке и с циклами длины 2;
классические примеры: куб, графы Хивуда, Паппа, Дезарга, додекаэдр — проверили по полсотни случайных потоков; а на совсем маленьких графах ( $K_4$ , $K_{3,3}$ , призма, мультиграфы выше) снова запустили полный перебор всех нигде не нулевых потоков;
случайные кубические графы до 200 вершин, порядка двухсот штук;
и отдельно на маленьких графах мы брутфорсом перечислили все линейные зависимости системы и убедились, что они ровно те, что описаны в доказательстве (условия-“препятствия”), и что все они зануляют правую часть.

Итого мы сделали более тридцати пяти тысяч запусков конструкции, и не нашли ни единого сбоя. Вот как результат выглядит на графе Петерсена; слева нигде не нулевой поток (тот самый 8-поток, помеченный битовыми строками), справа — пары, которые выдало решение системы склейки:

А вот восемь подграфов $M_s$ — двойное покрытие, построенное по этим парам:

Каждое ребро выделено ровно на двух панелях из восьми; три подграфа оказались пустыми. В этом примере покрытие состоит всего из пяти циклов: два пятиугольника, внутренняя пентаграмма, шестиугольник и один длинный цикл длины 9.

А вот пример побольше, цветок Айзекса $J_{13}$ ; слева его покрытие, а справа уже совершенно нечитаемый случайный кубический граф:

И вот покрытие для цветка Айзекса в читаемом виде:

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

Промпт как исторический документ

Теперь о том, как доказательство было получено и что происходило вокруг.

OpenAI опубликовала полный промпт, которым запускали GPT 5.6 Sol Ultra, и это довольно любопытное чтение. Модели было доступно до 64 параллельных субагентов, и промпт в основном состоит из инструкций, как управлять этим роем. Например (перевод мой):

Начните с по-настоящему разнообразного портфеля подходов. <…> Не сообщайте большинству агентов текущий предпочтительный подход. Сохраняйте независимость в ранних раундах, чтобы агенты не сошлись все к одной и той же привлекательной, но неполной редукции. < … >

Используйте конкурентных агентов (adversarial agents) на всём протяжении доказательства: каждый кандидат в доказательство должен проверяться на точную двукратность покрытия, на замкнутые маршруты с повторными рёбрами, маскирующиеся под циклы, на двуциклы из параллельных рёбер, на несвязные графы, на точки сочленения, на мосты, привнесённые редукциями, и на циклическое использование утверждения, эквивалентного самой CDC.

Отклоняйте отчёты о статусе, расплывчатый оптимизм и заявления, что недоказанное глобальное утверждение о согласованности — это “рутина”.

Последний пункт особенно хорош: “глобальное утверждение о согласованности” — это как раз лемма 2, и промпт заранее запрещает модели объявить её очевидной. Очевидно, такой failure mode авторы промпта видели на практике.

Отмечу ещё пару строк. Промпт прямо инструктирует модель: “Assume for purposes of this task that a complete affirmative proof exists” — “считайте, что полное доказательство существует”. Кроме того, он отдельно запрещает модели лезть в интернет проверять статус задачи и отвечать “это открытая проблема”.

То есть авторы промпта целенаправленно запрещали модели использовать её (уже наверняка имеющееся) знание о том, что CDC не решена, — иначе она, как любая хорошо выдрессированная LLM, вежливо отказалась бы её решать.

И вот ещё один крутой штрих: “Spend at least 8 hours on this before even thinking of returning or giving up” — “потратьте хотя бы 8 часов, прежде чем даже думать о том, чтобы сдаться”. Говорят, что модель управилась меньше чем за час.

В треде на Hacker News прикинули стоимость такого запуска — оценки примерно от $300 до$ 13000 в зависимости от предположений о железе. Согласитесь, что за решение полувековой важной проблемы это в любом случае недорого.

И ещё одно наблюдение оттуда же: удивительно, насколько большая часть промпта уходит на то, чтобы просто заставить модель действительно решать задачу, а не отчитываться о трудностях. Это довольно любопытный эффект, и хотя с моим личным опытом он пока не сходится, как знать, что нас ждёт в ближайшем будущем…

Реакции: “could have been discovered in the 1980s”

Первым из известных математиков подробно отреагировал Томас Блум — тот самый хранитель erdosproblems.com, которого мы встречали и в истории с единичными расстояниями. В треде на X он пишет, что это “a very nice proof” — короткое, элементарное и такое, которое “могло быть найдено в 1980-х”. Он пишет, что никакой новой техники в нём нет, есть “небольшой контринтуитивный поворот” поверх хорошо известных идей.

Вся критика Блума сводится к оформлению: препринт не цитирует работы, из которых выросли его ключевые идеи, в первую очередь ту самую статью Бермона, Джексона и Джегера 1983 года (о ней мы говорили выше: именно там развита техника покрытий чётными подграфами, дающая, в частности, то самое четырёхкратное покрытие каждого ребра, которое новое доказательство наконец “делит пополам”). Как пишет the-decoder:

This is a frequent issue with AI-generated proofs and papers: they use ideas and proof strategies taken from the literature without proper citation.

Это действительно известный недостаток, и дословно ту же претензию Мелани Мэтчетт Вуд предъявляла к работе про единичные расстояния (я подробно писал об этом тогда): модель “знает” большой объём литературы, и ей трудно отличить выученную идею от порождённой. Полностью корректная расстановка ссылок — пока не до конца решённая проблема AI-математики. Впрочем, как вы понимаете, это не то чтобы серьёзная критика.

А ещё, разумеется, на HackerNews тут же высказались о характере доказательства: это ловкий трюк, который каким-то образом ускользнул от всех экспертов, а не построение новой теории. Настоящей вехой, как пишет один из комментаторов, будет момент, когда AI-модель решит проблему, требующую создания новой теории на десятки страниц.

Ну что тут скажешь… Я много раз уже писал и рассказывал про moving the goalposts в AI. В науке с этим даже хуже, чем в более прикладных областях.

Почему же люди это пропустили? Дальше моя личная гипотеза, я на ней не настаиваю. Но мне кажется, что всё дело в направлении атаки.

Классический путь от 8-потока к покрытиям — через носители функционалов: семь чётных подграфов, каждое ребро в четырёх, и эту четвёрку действительно никак не сократить вдвое. Здесь стена, и логично, что это направление считалось тупиковым.

Новый ход от GPT состоял в том, чтобы отдать каждому ребру не значения функционалов, а пару элементов группы, причём пару, определённую с точностью до локального сдвига $\varepsilon_e$ . И вся проблема согласования раскраски сводится к одной глобальной линейной системе уравнений.

После этого остаётся ещё “чудо чётности” из леммы 2; его, пока не выпишешь систему, просто неоткуда увидеть.

Это очень похоже по духу на доказательства самих теорем о 6- и 8-потоках: короткое прямое применение линейной алгебры, которая непонятно почему должна была сработать, но сработала.

Такие доказательства легко ~~потерять~~ проверить и очень сложно найти. Человек-эксперт скорее будет заниматься более многообещающими направлениями, а модель с 64 субагентами и восемью часами машинного времени может позволить себе копать там, где эксперт даже не остановился бы.

Как заметил Якоб Цимерман по поводу прошлого результата, AI-системы “may play for longer and in more treacherous waters than mathematicians without getting overwhelmed”. Похоже, это и есть новая суперспособность текущих AI-систем: не гениальность, а невозмутимость и последовательность.

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

Итак, GPT решил важную открытую проблему. Но это не значит, что теория графов лишилась своего святого Грааля и теперь станет мёртвой наукой. CDC была узлом в целой сети гипотез о кубических графах и снарках, и большинство узлов этой сети всё ещё остаются открытыми.

Гипотеза Татта о 5-потоках (1954): у всякого графа без мостов есть нигде не нулевой 5-поток. Новое доказательство её не задевает: между 5-потоками и CDC нет известных импликаций ни в одну сторону, это соседние, но независимые вершины в сети гипотез.
Berge–Fulkerson conjecture (1971): в каждом кубическом графе без мостов найдутся шесть совершенных паросочетаний, покрывающих каждое ребро ровно дважды. Это родная сестра CDC (тоже “каждое ребро ровно дважды”, только теперь паросочетаниями), и она по-прежнему открыта.
Гипотеза Джегера о петерсеновской раскраске: рёбра любого кубического графа без мостов можно “покрасить рёбрами графа Петерсена” с сохранением смежности. Это утверждение влечёт и CDC, и гипотезу Фалкерсона, так что теперь оно стало чуть менее недосягаемым по последствиям, но само по себе всё ещё не доказано.
Ориентируемая CDC: можно ли всегда найти двойное покрытие, циклам которого можно придать направления так, чтобы каждое ребро проходилось два раза в противоположных направлениях? (Для покрытий из граней вложения в ориентируемую поверхность это так.)
Малые покрытия: гипотеза о том, что всегда достаточно покрытия, циклы которого группируются в 5 чётных подграфов. Конструкция из препринта даёт 8 подграфов $M_s$ , но от восьми до пяти может быть ещё очень далеко.
Круговые вложения: та самая топологическая гипотеза, из которой CDC следовала; теперь следствие доказано, а причина — нет, и это отдельный интересный вопрос.

Так что у специалистов по снаркам работы не убавилось, скорее наоборот: интересно будет посмотреть, какие из “соседних” утверждений окажутся принципиально сложнее, а какие тоже падут в ближайшем будущем.

Заключение

Итого получается вот какая картина. Гипотеза о двойном покрытии циклами имела 50-летнюю историю и статус “одной из главных открытых проблем теории графов”. И вот на днях она получила короткое, элементарное, конструктивное доказательство, которое, по утверждению OpenAI, полностью придумала модель GPT 5.6 Sol Ultra за час работы 64 параллельных агентов.

Препринту три дня, формальной верификации сообществом пока нет, но доказательство настолько короткое и простое, что проверить его может каждый — я проверил и вручную, и кодом на примерах (не без помощи AI-ассистентов, разумеется, куда уж теперь без них).

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

Я не знаю, сколько ещё знаменитых задач имеют решения такого типа — короткие, но контринтуитивные. Судя по скорости прогресса, мы скоро узнаем: похоже, тот самый систематический поиск “низко висящих фруктов” в математике, о котором я говорил в последний год, уже идёт полным ходом.

Если у вас есть любимая гипотеза, в которую вы верите, самое время написать про неё хороший промпт.

Сергей Николенко

P.S. Прокомментировать и обсудить пост можно в канале «Sineкура»: присоединяйтесь!

Охота на снарка: доказательство гипотезы о двойном покрытии циклами

Введение

Что такое двойное покрытие циклами

Почему достаточно кубических графов, или охота на снарка

Язык потоков

Первый шаг: у каждого ребра два цвета

Второй шаг: строим пары из потока

Интермедия: вся конструкция на примере

Шаг 3: чудо чётности

Проверяем руками и кодом

Промпт как исторический документ

Реакции: “could have been discovered in the 1980s”

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

Заключение

Comments

Leave a Reply Cancel reply

More posts

PEPPERED: An Existential Platformer

Охота на снарка: доказательство гипотезы о двойном покрытии циклами

Train Valley Origins

Curyeux