Blog

Введение

Пост про гипотезу Диница — Гарга — Гёманса я закончил словами “А что ещё дальше, коллеги?..”. Сегодня могу отчитаться, что было дальше: три недели, три препринта, один merged pull request от внешнего контрибьютора и мои первые сабмиты на VibeMathed.

Если коротко, то из твита Дмитрия Рыбина выросла целая исследовательская программа. Сначала мы с моделями опускали планку снизу:

• Часть I, “A Planar Lower Bound 1.1397… > 9/8 for Cost-Preserving Single-Source Unsplittable Flows”, подняла нижнюю оценку с до ,
• Часть II, “Deletion-Star Ceilings and a 1.28249 Lower Bound for Cost-Preserving Single-Source Unsplittable Flows” — до ; потом сообщество в лице Альфредо де ла Фуэнте докрутило её до прямым pull request’ом в мой репозиторий.

А потом произошёл поворот, ради которого я и пишу этот пост:

• в Части III, “Exact-Mean Decompositions for Cost-Preserving Single-Source Unsplittable Flows: Demand Scales and Local Interaction Structure” появились первые положительные результаты — точные константы и первые конечные оценки для неограниченных классов задач.

При этом константы наших же контрпримеров из первых двух частей оказались не просто какими-то случайными контрпримерами, а точными значениями для соответствующих классов задач.

Здесь, правда, речь уже не про один гигачад-промпт “you should do a breakthrough”. Это была долгая совместная работа с LLM, с десятками промптов, неудачных попыток, провалившихся экспериментов и так далее. Ошибки тоже регулярно встречались, хотя честно скажу, что хоть я и проверил всё, что происходит в финальном тексте, но лично я не нашёл ни одной дырки — все ошибки, которые были в доказательствах, находились на этапе перекрёстной проверки другими LLM.

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

Напоминание: гипотеза и треугольник

Кратко напомню постановку задачи; подробности есть в прошлом посте.

Рассмотрим ориентированный граф с источником , терминалами и заказами ; на дугах могут быть неотрицательные цены . Дан дробный поток , который можно делить по путям как угодно. Мы хотим получить неделимый поток : один путь на терминал, так что весь заказ идёт целиком по этому пути. Теорема Диница — Гарга — Гёманса (1999) говорит, что всегда можно добиться на каждой дуге выполнения условия

   

а гипотеза Гёманса утверждала, что одновременно можно сохранить и цену, .

22 июля 2026 года GPT 5.6 Pro по запросу Дмитрия Рыбина построила контрпример с семью вершинами: любой неделимый поток, укладывающийся в добавку , имеет здесь цену минимум 60 при дробной цене 58.

Мы подробно обсуждали этот пример в прошлом посте. Внутренний механизм этого контрпримера — треугольник попарных конфликтов: три “бесплатных” пути, любые два из которых вместе перегружают какую-то дугу. Дробный поток набирает по бесплатным путям суммарную массу , а неделимый может позволить себе не больше одного бесплатного выбора.

В том же посте мы видели, что параметрическое семейство на той же схеме из 7 вершин доводит нижнюю оценку до любого : если разрешать перегрузку и требовать сохранения цены, то должно выполняться . Сверху же для планарных графов известна константа 2 (Traub, Vargas Koch, Zenklusen, 2023). Так что в начале пути у нас был зазор между и для планарных графов, а для произвольных верхней оценки не было вовсе.

Первый естественный вопрос: может быть, тот же треугольник, но с другими числами, даст больше ?

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

Хребты и терминалы с парой выходов

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

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

Контрпример из части I был основан на четырёх терминалах с интервалами , , , :

Оптимизация по заказам и долям даёт нижнюю оценку

   

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

Важная техническая деталь: у каждого терминала в этих конструкциях ровно два простых пути, так что верификацию можно вести буквально полным перебором, и проверяющая программа не может ничего пропустить или забыть. Ту же константу независимо и раньше получил Matthew Protti (23 July 2026); тогда я об этом не знал, но потом во введении Части III расставил все известные мне ссылки.

Число больше , но это не всё, что о нём можно сказать; оно ещё вернётся в этой истории с совершенно другой стороны.

Часть II. Семнадцать терминалов с общим ребром

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

И действительно, обобщить удалось: в Part II мы предъявляем пример, в котором уже сразу 17 терминалов, поздние пути которых все проходят через одно общее ребро.

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

Оптимизация (уже довольно нетривиальная) дала рекорд

   

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

В Части II появились и первые верхние оценки: на классе таких вот конструкций (два пути на терминал, пересекающиеся по одному ребру интервалы) метод не может дать оценку больше . Это, конечно, верхняя оценка только на очень конкретный класс графов, то есть ограничение метода, а не какая-то интересная теорема сама по себе.

Потом случилось очень крутое событие, которое меня изрядно вдохновило продолжать. Я выложил репозиторий с сертификатами и верификаторами, и Альфредо де ла Фуэнте (Alfredo De la Fuente) прислал pull request: транспонировать правые концы двух интервалов и переоптимизировать заказы. Его сертификат прошёл все наши проверки, и текущий рекорд теперь community-contributed:

   

Мне очень понравилось, что задача вызвала интерес у сообщества. На Vibemathed мой пост с этими результатами тоже получил довольно много по меркам этого сайта комментариев. В частности, конечно, меня ткнули носом в том, что Matthew Protti был первым с оценкой, близкой к .)

Лестница рекордов по числу терминалов выглядела так: : , : , : , : , : , : .

Запомните и её — к ней мы тоже вернёмся.

А нельзя ли чего-нибудь доказать?

К этому моменту у константы было уже довольно много нижних оценок и удручающе мало верхних. Хуже того: для общих графов и произвольных заказов было неизвестно, существует ли вообще конечная константа , то есть неизвестно, конечна ли она в принципе. С этого вопроса и началась Часть III.

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

Вот главный принцип, на котором стоит вся Часть III: раскладываем ошибку на множители, сохраняя среднее. Иначе говоря, мы ищем не один поток (маршрутизацию, routing), а распределение на потоках, у которого

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

Если такое распределение есть, то сохранение цены получается автоматически: средняя цена равна , значит, какой-то атом стоит не дороже. После этого цены рёбер вообще исчезают из задачи, и остаётся чистая “геометрия” (ну, не настоящая геометрия, конечно): какого размера нужен “ящик”, чтобы смог стать точным средним целых маршрутизаций?

Это нехитрая интуиция, и так люди уже думали о потоках. Первым интересным (и, насколько я могу судить, новым) результатом Части III стало то, что это не просто удобный приём, а приём достаточный. Для любого класса графов, замкнутого относительно удаления дуг (а это все естественные классы: планарные, последовательно-параллельные, деревья…), выполняется равенство: оптимальная константа сохранения цены в точности равна минимальному радиусу ящика для точных средних.

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

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

Арифметика: делимость бесплатно, несравнимость нет

В этой науке есть классический результат Skutella (2002): если заказы образуют цепочку делимости (каждый делит следующий), гипотеза Гёманса верна как есть, с константой 1. На языке точных средних это “локальный закон”: внутри цепочки делимости мы можем явно построить нужное распределение.

Часть III превращает это в общий принцип факторизации:

• разобьём множество значений заказов на цепочки делимости,
• построим распределение в каждой цепочке независимо,
• перемножим полученные распределения.

При этом точные средние складываются, радиусы складываются, и каждая цепочка платит один раз своим максимумом. И получается, что

   

где — максимальное значение одного заказа, а оптимальное покрытие цепочками считается за полиномиальное время через паросочетание максимального веса.

Если быть точным, то результат говорит, что ключевым объектом для нас является разбиение мультимножества заказов (множества терминалов) на цепочки делимости . Мы сможем построить нужный “ящик” радиуса

   

то есть любой дробный поток будет выпуклой комбинацией “опорных маршрутизаций” (support routings) с точно совпадающим средним и радиусом :

   

Например, можно разбить заказы на множества по значениям, т.е. если именно как множество, без повторов, и если , то

   

а значит, в частности, аддитивная константа на этом примере не превышает (константу ещё на максимальное значение заказа нужно разделить).

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

Именно поэтому в контрпримерах всё время появляются попарно не делящие друг друга заказы в узкой полосе. Теперь это не эмпирическое наблюдение, а теорема о том, где метод работает, а где не очень.

Немедленные следствия:

• если значений всего два, , то (это константа Морелла — Скутеллы, теперь доказанная для всех примеров с двумя значениями);
• если в каждой диадической полосе не больше одного значения, то (достаточно их все просуммировать как );
• если в примере конечное множество значений, то у него будет конечная константа.

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

Давайте разберём ещё чуть более содержательный пример, чтобы увидеть, как это суммирование оценок работает. Вот он:

Здесь терминал (спрос ) использует общую дугу с весом , терминал (спрос ) с весом , так что нагрузка получается .

В этом примере четыре целочисленных маршрутизации; назовём их 00, 01, 10, 11: первый бит показывает, идёт ли через путь в , а второй — в . И если рассмотреть веса как независимые вероятности, то получатся вероятности как на картинке и ожидание

   

то есть при таком разложении сохраняется точное среднее. А радиусы просто складываются и получается .

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

А вот округление вниз работает, если срезанная часть заказа сначала удаляется из самых дорогих путей. Здесь тоже вдаваться в детали не буду, но, в общем, получается целое семейство оценок, параметризованное основанием и глубиной сетки . Две первые его точки давно известны — это оценки Скутеллы

   

а дальше кривая продолжается на все , с пределом в чистом сдвиге и полезным следствием для потоков ограниченной нагрузки:

Вся задача свелась к одному окну

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

   

Иными словами, универсальная конечная константа существует тогда и только тогда, когда конечна , и вся общность задачи по сути свелась к вопросу об одном окне значений .

Например, все заказы рекорда с сами лежат в одной такой полосе , и более точное рассуждение о выпуклых оболочках показывает, что этот пример даёт

   

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

Геометрия: пары бесплатны, первый враг — треугольник

Теперь вторая ось частичных результатов. На арифметической оси мы ограничивали значения заказов, а граф и взаимодействие путей оставляли произвольными; здесь всё наоборот: заказы любые, но ограничена геометрия взаимодействия путей. Отправная точка — общее свойство всех наших контрпримеров: в них к каждому терминалу ведут ровно два простых пути. Назовём такие примеры двухпутевыми (two-path instances) и посмотрим, во что превращается задача.

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

   

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

Число ненулевых элементов строки назовём её арностью: это число терминалов, чьё переключение вообще затрагивает данную дугу.

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

Но есть и неприятный сюрприз: на абстрактном уровне уже пары, то есть строки арности 2, могут стоить больше . Пример из статьи: два терминала с единичными заказами, доли и две строки со знаками и . У первой строки состояние имеет ошибку , так что радиус требует ; у второй за ящик вылезает состояние с ошибкой , то есть нужно ещё и . Вместе с маргиналами это несовместно: обозначив , получаем и , и первое условие требует , а второе — . Лучший достижимый радиус здесь .

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

Первая структурная теорема Части III: они не реализуются. Начнём с самого простого случая: у двухпутевого потока для любой пары терминалов произведение знаков одинаково на всех дугах, где оба сомножителя ненулевые. Доказательство — симпатичная графовая склейка, которую я здесь не буду объяснять в деталях:

На самом деле верно гораздо больше: вся матрица (после удаления нулевых строк) — это сетевая матрица (network matrix), матрица знаковых инциденций путей в некотором дереве, и в частности она вполне унимодулярна. Идея доказательства: в носителе двухпутевого потока в каждую вершину можно прийти из источника не более чем двумя способами — третий способ немедленно дал бы третий путь какому-нибудь терминалу.

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

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

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

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

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

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

   

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

Теорема. У двухпутевого примера, все строки которого имеют арность не выше 2, точный радиус равен ровно — при любой цикличности взаимодействий.

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

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

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

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

Дальше — четыре колонки. Существует ровно пять максимальных носителей взаимодействия четырёх терминалов (с точностью до перестановок; эта классификация тоже нетривиальная и тоже доказывается в статье):

Форма 0 — это интервальное ядро Части I, и её точная локальная константа равна

   

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

Его мы, конечно, пропустим, зато теперь можно показать всю лестницу целиком:

Синие квадраты — теоремы с точными оценками: , , . Оранжевые кружки — рекорды из Части II, которые мы теперь считаем гипотетическими следующими ступенями той же лестницы. Пунктир — гипотеза Части II о супремуме для этого класса. Первые две нетривиальные ступени лестницы совпали с константами контрпримеров: нижние оценки Частей I–II, найденные задолго до всей этой теории, оказались точными значениями экстремальных задач, о существовании которых мы тогда не подозревали. По-моему, это крутой сюжетный поворот.

Раскраски, Property B и первый ответ для неограниченного класса

Локальные ядра — это хорошо, но что делать с глобальной системой, где троек много и они переплетены? Здесь помогает классическая комбинаторика.

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

И теперь можно вспомнить гиперграфы из предыдущего раздела: их мы как раз и раскрашиваем. Оказывается, свойство “гиперграф двураскрашиваем без одноцветных рёбер” — это классическое Property B (в честь Бернштейна, название Миллера, 1937). Сам я о таких комбинаторных понятиях, разумеется, ни разу не слышал, пока мы с LLM не занялись этой задачей.

В общем случае Property B может не выполняться. Минимальный контрпример арности 3 — плоскость Фано, семь точек и семь прямых.

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

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

Теорема. В двухпутевых графах, если арность взаимодействия не превышает 3, то радиус не превышает .

У нас получилась первая конечная константа для класса, в котором ограничена только локальная арность, а всё остальное произвольное: и число терминалов, и цикличность, и значения заказов.

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

Классы графов и новый планарный рекорд

Теперь можно свести результаты о классах графов в единую таблицу:

• исходящие деревья: (всё тривиально маршрутизируется);
• двухслойные “хабы” (источник — склады — клиенты): , это известный результат; а мы ещё подпёрли его нижней границей , которую получили из классического семейства “m+1 работ”;
• последовательно-параллельные графы (series-parallel): (Almoghrabi, Skutella, Warode, 2026);
• внешнепланарные двухвыходные интервальные хребты: ровно, и константа 1 здесь достигается уже одним терминалом.

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

У него

   

и мы знаем классическую верхнюю оценку 2. Забавно, что дальше по лестнице рекордов планарность немедленно заканчивается: уже пятитерминальная рекордная геометрия непланарна.

Как проверяли и как шёл процесс

Стандарт проверки во всех работах был один и тот же: каждое числовое утверждение проверяется в точной рациональной арифметике программой, которая пересобирает пример из списка дуг: заново находит все простые пути поиском в глубину, заново перечисляет маршрутизации, заново решает задачи линейного программирования. У каждого сертификата есть вторая, независимо написанная реализация проверки. Финальные доказательства классов и локальных констант все solver-free, то есть численный поиск разрешён только на стадии открытия новых примеров, и ни одно решение солвера не входит в доказательство как посылка. Все 37 новых сертификатов Части III лежат в репозитории, и приложение статьи объясняет по пунктам, что именно проверяет каждый файл.

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

В общем, доказательства от LLM безусловно нужно проверять, но конкретно в этом исследовании оказалось достаточно проверять их другой LLM: Claude ловил ошибки GPT и наоборот, и после пары таких раундов я уже никаких ошибок больше не находил (но всё равно искал! это важно!).

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

Работали три модели в разных ролях. GPT 5.6 Sol гоняла экспериментальные “кампании”: я (вместе с Claude) писал подробный бриф — какие гипотезы проверить, какие сертификаты сгенерировать, в каком формате отчитаться, — а Sol возвращалась с результатами, часто неожиданными. Claude Fable 5 и Claude Opus 5 занимались теорией, проверкой и текстом: верифицировали каждый раунд, доказывали, что доказывается вручную, ловили ошибки (свои, мои и чужие) и собирали статью.

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

В отличие от истории Рыбина, это не был one-shot tour de force; это был именно длинный совместный проект, и, кстати, чертовски интересный! Присоединяйтесь!

Что осталось открытым

Разумеется, мы не вполне всё закончили.

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

Заключение

Месяц назад эта история начиналась с семи вершин и твита. Сейчас у неё три препринта, большая таблица рекордов с внешними контрибьюторами, репозиторий с машинно-проверяемыми сертификатами и ряд интересных верхних оценок для разных классов графов, причём константы контрпримеров оказались точными значениями в новой теории.

В постах про двойное покрытие циклами, якобиан и Диница — Гарга — Гёманса я писал про молниеносные результаты: одна гипотеза — один промпт — один документ. Этот пост — про другой, более прозаический и наверняка куда более массовый жанр: LLM как полноценные соавторы в долгом проекте, с разделением ролей, взаимной проверкой и накоплением результатов.

А что дальше, коллеги?

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

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

Введение

В прошлый раз, рассказывая про контрпример к проблеме якобиана, я закончил пост вопросом: “Что дальше, коллеги?”

Ответ занял два дня.

22 июля Дмитрий Рыбин написал в X, что GPT 5.6 Pro опровергла гипотезу Диница — Гарга — Гёманса (Dinitz–Garg–Goemans conjecture) из теории потоков в графах. Гипотеза простояла с конца 1990-х; в статье 2025 года Swamy et al. всё ещё называли её “a famous conjecture” и писали, что даже существенно ослабленный вариант был бы прорывом.

Как и в случае проблемы якобиана, здесь пока нет ни журнальной статьи, ни формального рецензирования, но они и не нужны, потому что проверить контрпример очень легко. У нас есть пост Рыбина, выложенный им полный диалог с моделью и четырёхстраничный арифметический сертификат, но в графе всего семь вершин, девять дуг и восемь возможных неделимых потоков. Мы с GPT независимо проверили все восемь программой, которая перебирает буквально все пути в графе, и никаких ошибок здесь нет.

Более того, контрпример оказался не просто верным, а очень интересно устроенным. Внутри него прячется известный в комбинаторной оптимизации объект — треугольник попарных конфликтов.

Давайте разберёмся, что такое делимые и неделимые потоки и в чём состояла гипотеза. Потом обсудим, почему она казалась естественной и почему её было так трудно доказать. Затем проверим контрпример, вытащим из него структурную идею и попробуем его уменьшить. А в конце, разумеется, посмотрим на промпты. Спойлер: там буквально написано “you should do a breakthrough”.

Потоки, которые можно и нельзя делить

Начнём с обычной транспортной сети. Есть ориентированный граф : вершины — перекрёстки или маршрутизаторы, дуги — дороги или каналы связи. У нас есть один общий источник , например склад, и несколько терминалов , куда надо доставить грузы объёмов .

У каждой дуги есть пропускная способность : больше этого количества груза одновременно по ней отправлять нельзя. Может быть и неотрицательная цена за перевозку одной единицы груза.

В более простой постановке задачи грузы можно делить, то есть, например, заказ объёма 10 разрешается разрезать на части: пять единиц поехали по одному пути, три по другому, две по третьему. Такой поток называется делимым или дробным (splittable, fractional flow). В каждой внутренней вершине выполняется закон сохранения: сколько потока вошло, столько и вышло; источник выпускает сумму всех заказов, а терминал поглощает ровно .

С дробными потоками работать легко и приятно, их можно искать линейным программированием, а для классического максимального потока есть ещё более быстрые специализированные алгоритмы.

Но во многих задачах груз делить нельзя. Контейнер должен ехать целиком, сетевое соединение должно выбрать один маршрут, задачу на вычислительном кластере нельзя на 37% выполнить на одном сервере и на 63% на другом. Тогда для каждого терминала надо выбрать один путь из в и отправить по нему все единиц. Это неделимый поток (unsplittable flow).

Если через дугу проходят пути терминалов из множества , нагрузка на неё равна

   

А полная стоимость маршрутизации равна

   

Очевидно, что разница между двумя постановками есть, и немалая. Представьте один заказ объёма 10 и две дороги, по которым дробный поток отправляет по пять единиц. После запрета деления придётся выбрать одну дорогу и положить на неё все десять. Нагрузка на выбранную дорогу вырастет скачком на пять.

Такое неизбежно происходит и в общем случае. Поэтому разумный вопрос здесь в том, насколько сильно придётся перегружать дуги. Обозначим максимальный размер заказа (demand, ещё переводят как “потребность” или “запрос”) через

   

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

Теорема Диница — Гарга — Гёманса

Задачу о неделимом потоке из одного источника ввёл Джон Клейнберг в работе 1996 года. Даже решить, существует ли неделимая маршрутизация, соблюдающая все ёмкости, NP-трудно; как отмечают авторы современного обзора, уже на графе из двух вершин с параллельными дугами сюда сводятся Subset Sum и Bin Packing.

Но Ефим Диниц, Навин Гарг и Мишель Гёманс в работе “On the Single-Source Unsplittable Flow Problem” доказали важную теорему.

Теорема (Dinitz–Garg–Goemans, 1999). Пусть — любой допустимый дробный поток. Тогда за полиномиальное время можно найти неделимый поток , для которого на каждой дуге

   

Если исходный поток соблюдает ёмкости, , то, следовательно,

   

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

Это верная и интересная теорема, но она про частный случай нашей задачи, без стоимостей дуг. Вскоре Гёманс предложил естественное усиление.

Гипотеза Гёманса. Если на дугах заданы неотрицательные цены , то неделимый поток можно выбрать так, чтобы одновременно не слишком перегружались дуги,

   

и не увеличивалась общая цена,

   

Иногда её называют гипотезой Диница — Гарга — Гёманса по имени исходной теоремы, а иногда просто Goemans’ conjecture; важно, что теорема трёх авторов без стоимостей остаётся в силе, опровергнуто именно стоимостное усиление.

Почему в гипотезу верили и почему она была сложной

У гипотезы была очень убедительная вероятностная интуиция.

Разложим дробный поток каждого терминала по путям. Долю потока на пути можно воспринимать как вероятность выбрать этот путь целиком. Если независимо выбрать по одному пути для каждого терминала, то в среднем нагрузка на каждой дуге будет ровно , а средняя стоимость — ровно .

Значит, среди всех исходов точно есть хотя бы один со стоимостью не выше средней. С другой стороны, теорема Диница — Гарга — Гёманса гарантирует, что есть исход, в котором все нагрузки не превосходят .

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

Конечно, здесь нет формального доказательства: из “существует дешёвый поток” и “существует поток без большой перегрузки” не следует, что существует поток одновременно дешёвый и без большой перегрузки. Именно так устроен новый контрпример.

Но до него эта надежда выглядела вполне разумной. Многие классические методы зависимого округления умеют сохранять линейную целевую функцию и одновременно контролировать ошибки в ограничениях. Для специальных случаев получались положительные результаты: например, Skutella (2002) доказал гипотезу, когда все заказы кратны друг другу, точнее, образуют цепочку делимости (см. также Morell, Skutella, 2022).

При этом прогресса в общем случае почти не было. В 2023 году Traub, Koch, Zenklusen писали, что не известно практически ни одного нетривиального класса графов, где точная гипотеза была бы доказана. Они получили важный результат для планарных графов, но только с вдвое большим запасом:

   

Даже в работе октября 2025 года вопрос, можно ли сохранять стоимость хотя бы с добавочной перегрузкой в общих графах, назывался “широко открытым”, а его решение — потенциальным прорывом. Я нашёл только один (совсем недавний, 29 июня 2026!) результат Almoghrabi, Skutella & Warode, где гипотеза Гёманса доказывается для нетривиального класса: последовательно-параллельных ориентированных графов, причём даже в более общей многоисточниковой постановке.

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

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

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

Тем любопытнее, что итоговый контрпример можно нарисовать на салфетке.

Семь вершин и девять дуг

Вот весь граф. Число на дуге — нагрузка дробного потока, — цена одной единицы; у непомеченных цен значение нулевое. Двойными кружками отмечены терминалы.

Заказы трёх терминалов равны

   

поэтому .

Сначала проверим, что нарисованные числа действительно задают дробный поток. Из источника выходит

   

В трёх внутренних вершинах поток сохраняется:

   

Наконец, в терминалы приходит ровно столько, сколько требуется:

   

Стоимость положительна только на трёх оранжевых дугах:

   

Можно посмотреть на тот же поток отдельно для каждого терминала. У каждого груза есть ровно два пути — дорогой и бесплатный :

   

Обратите внимание, что тоже проходит по бесплатной дуге , но платит на дуге .

Дробный поток раскладывается так:

Каждый дорогой путь, если отправить по нему соответствующий груз целиком, стоит ровно 30:

   

Поэтому стоимость 58 можно пересчитать ещё одним способом:

   

А теперь запретим делить грузы. Для каждого терминала надо выбрать либо , либо . Всего получается вариантов. И 58 превращается в 60 из-за трёх арифметических конфликтов.

Конфликт и . Если второй и третий грузы одновременно идут по бесплатным путям, на дугу ложится

   

Но гипотеза разрешает там не больше

   

Перегрузка — одна единица.

Конфликт и . Эти два пути вместе дают на дуге

   

Снова не хватает ровно одной единицы.

Конфликт и . Тут надо вспомнить, что третий груз проходит по дуге на обоих своих путях, и дорогом, и бесплатном. Поэтому вместе с и нагрузка на неизбежно равна

   

И опять разность равна единице.

Итак, любые два бесплатных пути несовместимы с ограничениями гипотезы. Значит, бесплатно может поехать не больше одного груза, а как минимум два обязаны выбрать дорогие пути. Каждый стоит 30, поэтому вся допустимая неделимая маршрутизация стоит не меньше

   

Вот и всё опровержение.

Для полноты выпишем все восемь вариантов. Слово bad означает, что после разрешённой добавки какая-то дуга всё равно перегружена:

E1 E2 E3   cost 90   good
E1 E2 Z3   cost 60   good
E1 Z2 E3   cost 60   good
Z1 E2 E3   cost 60   good
E1 Z2 Z3   cost 30   bad: v→w by 1
Z1 E2 Z3   cost 30   bad: u→v by 1
Z1 Z2 E3   cost 30   bad: s→u by 1
Z1 Z2 Z3   cost  0   bad: s→u by 1, u→v by 11, v→w by 1

Все четыре маршрутизации стоимостью меньше 60 нарушают ограничения, а все четыре, которые ограничения соблюдают, стоят 60 или 90.

Я уже два раза написал разными словами одно и то же простое рассуждение, чтобы подчеркнуть, что как и в случае проблемы якобиана, проверка здесь вообще не представляет никакого труда, так что ждать рецензирования смысла нет.

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

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

Что там происходит на самом деле

Теперь выкинем почти все детали графа и оставим его комбинаторный скелет.

Введём переменную , равную 1, если терминал выбирает бесплатный путь , и 0, если дорогой . Три конфликта говорят:

   

Для нулей и единиц отсюда следует

   

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

А какие значения соответствуют дробному потоку? Это доли грузов, отправленные по бесплатным путям:

   

Каждое попарное неравенство выполнено. Но сумма равна

   

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

А цены на дугах — просто разделяющая гиперплоскость. Поскольку каждый дорогой выбор стоит 30, стоимость равна

   

У дробной точки получается 58, а у любой целой точки с — не меньше 60.

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

Это заодно объясняет, почему двух терминалов для этого механизма недостаточно. У одного конфликтного ребра неравенство уже полностью описывает выпуклую оболочку допустимых точек. Первое недостающее ограничение возникает именно на треугольнике, то есть нужны три бесплатных варианта. Я не утверждаю, что семь вершин абсолютно минимальны среди всех мыслимых контрпримеров (для этого нужен отдельный перебор топологий, и его ещё никто вроде бы не сделал), но структурное ядро здесь действительно самое маленькое возможное.

Проверка, уменьшение контрпримера и граница

Проверка. Главная опасность в проверке подобных конструкций — перебрать только заранее задуманные пути и забыть, что их куски можно склеить в новый маршрут. Судя по опубликованному диалогу, несколько ранних попыток GPT 5.6 именно на этом и сломались.

Поэтому в проверочном скрипте мы с тем же GPT 5.6 не задавали шесть путей руками, а перебирали все простые пути из в каждый терминал. Впрочем, здесь всё-таки негде ошибиться, получится именно шесть путей:

t1: s→t1
t1: s→u→v→t1
t2: s→t2
t2: s→u→v→w→t2
t3: s→u→t3
t3: s→u→v→w→t3

После этого декартово произведение трёх двухэлементных списков даёт восемь маршрутизаций из таблицы выше.

Можно ли уменьшить числа? Да. На последней странице сертификата выписано целое параметрическое семейство. Я перебрал его рациональные и целочисленные варианты и нашёл меньший целочисленный экземпляр на том же графе:

• заказы , так что ;
• по бесплатным путям дробно идут единицы;
• единичные цены трёх платных дуг равны .

Тогда каждый дорогой путь целиком стоит 63, дробная стоимость равна

   

а любая допустимая неделимая маршрутизация стоит хотя бы

   

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

Исходные числа 58 и 60 для рассказа всё равно красивее, поэтому главным примером я оставил их. Но уменьшенный вариант даёт ещё один результат.

Рассмотрим ослабленную гипотезу, где разрешается

   

В исходном примере любая маршрутизация стоимостью не больше 58 должна выбрать хотя бы два бесплатных пути. Для каждого такого выбора на конфликтной дуге нагрузка превосходит на 16, то есть требуется

   

В уменьшенном примере требуется уже

   

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

   

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

   

Беря положительное рациональное сколь угодно малым, получаем контрпример для любого универсального коэффициента .

Иными словами, для планарных графов естественный вопрос теперь звучит так: какой будет оптимальный “коэффициент невязки” между и 2? Верхняя граница 2 известна из работы 2023 года, нижняя получается уже из этой маленькой планарной конструкции.

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

Четыре промпта

Ну и наконец — как это было найдено.

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

You should do a breakthrough.

Модель долго исследовала разные конструкции, выдавала частичные результаты и несколько раз не доходила до корректного ответа. Рыбин отвечал коротко и не пытался даже разобраться в том, что модель писала, по существу. После “Research conclusion” идут несколько страниц текста, но дальше диалог продолжается так:

Двух промптов не хватило, и GPT 5.6 опять сдался (через полтора часа размышлений), но третий промпт всё ещё прямолинеен:

И даже трёх промптов и пяти часов размышлений — о ужас! — не хватило. Так что Дмитрий Рыбин потерял терпение и написал коротко и прямо:

Как видите, на четвёртый раз невод, pardon the pun, пришёл с золотою рыбкой. Всего четыре коротких сообщения, никакого “искусства промптинга”. Опять же, я так

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

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

Заключение

Итак, гипотеза Диница — Гарга — Гёманса утверждала, что любой дробный поток можно округлить до неделимого, одновременно сохранив стоимость и увеличив нагрузку каждой дуги не более чем на один максимальный заказ.

GPT 5.6 Pro нашла планарный ациклический граф с тремя терминалами, где дробный поток стоит 58, а любой неделимый поток в разрешённых границах стоит не меньше 60. Сертификат состоит из девяти дуг и восьми строк полного перебора; я независимо проверил и арифметику, и отсутствие дополнительных путей.

Главная идея контрпримера — не сами числа, а треугольник конфликтов. Дробный поток использует три бесплатных выбора с суммарной массой , хотя целиком можно выбрать не больше одного. Цены лишь переводят недостающее неравенство в разрыв между 58 и 60.

Теорема Диница, Гарга и Гёманса без стоимостей остаётся верна. Планарный результат с запасом тоже остаётся верен. И теперь появляется некоторый зазор, который можно пытаться сокращать: как мы тут увидели, та же конструкция показывает, что любой новый универсальный коэффициент должен быть не меньше , то есть теперь можно сокращать расстояние между и .

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

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

А что ещё дальше, коллеги?..

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

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

Введение

Мы живём в дивном новом мире для математики. В мае внутренняя модель OpenAI опровергла гипотезу Эрдёша о единичных расстояниях, неделю назад GPT 5.6 доказала гипотезу о двойном покрытии циклами.

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

На этот раз отличилась модель от Anthropic: 19 июля, пока человечество смотрело финал чемпионата мира по футболу, Claude Fable 5 построил контрпример к проблеме якобиана (Jacobian conjecture) — одной из самых знаменитых открытых проблем алгебраической геометрии, номеру 16 в списке Смейла, простоявшей с 1939 года.

Если в прошлых сериях мы обсуждали хотя бы двухстраничные препринты, то здесь научная коммуникация стала ещё ближе к сингулярности; весь результат целиком существует в виде твита математика Левента Алпёге (Levent Alpöge):

И в общем-то этим твитом всё сказано, дальше можно не читать, а пойти проверить (ниже будет код на десять строк). Но я, конечно, не могу этим ограничиться, так что кое-какой контекст вам всё-таки расскажу. Тем более что это (опять!) тот редкий случай, когда про решение знаменитой проблемы можно рассказать всё до последней формулы.

Что такое проблема якобиана

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

   

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

Гипотеза (Keller, 1939). Если — ненулевая константа, то обратимо (и обратное отображение автоматически полиномиально).

Отт-Генрих Келлер сформулировал её в 1939 году (изначально для многочленов с целыми коэффициентами); с тех пор она стала, пожалуй, главным открытым вопросом о многочленах от нескольких переменных, который можно рассказать любому студенту.

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

• линейные отображения (якобиан — определитель числовой матрицы) и
• “треугольные” отображения вида — тут якобиан равен 1, а обратное выписывается сразу как .

Композиции таких отображений дают массу нелинейных примеров с константным якобианом, и все они обратимы. Гипотеза, по сути, говорила, что ничего другого и не бывает.

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

Во-вторых, в размерности 1 всё тривиально: означает, что линейна.

В-третьих, давно известно, что вся проблема только в инъективности: по теореме Акса–Гротендика инъективное полиномиальное отображение автоматически сюръективно. Более того, его обратное обязательно будет полиномиальным; это называется теоремой Бялыницкого-Бирули — Розенлихта.

Упомянутые выше результаты я вам с ходу не объясню, но для нас сейчас они значат, что контрпример — это обязательно отображение с константным якобианом, склеивающее какие-то две точки (нарушающее инъективность).

Стоит сразу оговориться, что над полями положительной характеристики гипотеза неверна тривиальным образом: у отображения над производная равна 1, но оно склеивает в ноль всё простое подполе. Так что это вопрос исключительно про характеристику 0 (вещественные числа, комплексные числа), и у гипотезы не может быть никакого доказательства “грубой алгебраической силой”.

Предыдущие попытки и частичные результаты

Фабрика ложных доказательств. Отдельный жанр — история попыток. Гипотеза якобиана, конечно, была не так популярна, как великая теорема Ферма, но к 1982 году Басс, Коннелл и Райт в классическом обзоре насчитывали в литературе не менее пяти опубликованных ошибочных доказательств. И это именно в литературе, то есть прошедших рецензирование.

Среди отметившихся принято называть вполне серьёзных математиков — например, Бениамино Сегре и Вольфганга Грёбнера (того самого, в честь которого названы базисы Грёбнера, к которым мы ещё вернёмся ниже). В 2004 году Мел Хохстер анонсировал доказательство двумерного случая, найденное Кэролин Дин, — и в нём тоже вскоре обнаружилась ошибка. Ну а в эпоху arXiv “доказательства” гипотезы о якобиане (в обе стороны, разумеется) выходили практически ежегодно.

Об уровне задачи говорит, например, то, что диссертация Итана Чжана (Yitang Zhang), который потом совершил прорыв в задаче об ограниченных промежутках между простыми числами, была посвящена именно гипотезе о якобиане.

Что уже было действительно доказано. Wang (1980) доказал гипотезу для отображений степени 2 в любой размерности. Moh (1983) — для и степени до 100 включительно. Ягжев (1980) и Bass, Connell, Wright (1982) показали интересную редукцию степени: достаточно доказать гипотезу для отображений вида , где — однородное кубическое, правда, ценой роста размерности. Позже Дружковский (1983) сузил ещё сильнее, до с линейными .

Наконец, известна целая сеть эквивалентностей: гипотеза о якобиане стабильно эквивалентна гипотезе Диксмье о том, что всякий эндоморфизм алгебры Вейля — автоморфизм (Tsuchimoto, 2005; Канель-Белов и Концевич, 2007) и связанной гипотезе Пуассона (Adjamagbo, van den Essen, 2006); из гипотезы Матье (1995) об интегралах по компактным группам гипотеза о якобиане тоже следует.

Был и предупредительный выстрел. В 1994 году Сергей Пинчук построил знаменитый контрпример к вещественной версии: полиномиальное отображение , у которого якобиан не обращается в ноль нигде, но которое не инъективно. У Пинчука якобиан не был константой (он всюду положителен, но принимает сколь угодно малые значения), так что комплексную гипотезу это не опровергало. Но при этом стало окончательно ясно, что “локальная обратимость всюду” глобальную не гарантирует, и закрылись многие возможные пути для доказательства гипотезы.

И ещё стоит отметить, что размерность 2 в этой науке — особая: там автоморфизмы полиномиального кольца устроены просто (теорема Юнга – ван дер Кулка), и гипотеза о якобиане там проверена до степени 100. А вот в размерности 3 регулярно ломается всё, что можно: например, автоморфизм Нагаты оказался “диким” именно в (Шестаков, Умирбаев, 2004), а гипотеза Маркуса–Ямабе о глобальной устойчивости пала на полиномиальном контрпримере именно в (Cima et al., 1997).

Но большинство этих результатов, особенно положительных, довольно сложные. А вот контрпример к гипотезе о якобиане оказался очень даже простым: это три многочлена над степени не больше 7. Давайте к нему и перейдём.

Контрпример и его проверка

Выпишем героя дня в человеческом виде. Отображение задаётся формулами

   

То есть это три многочлена степени 7, 6 и 4 соответственно. Утверждается, что:

• тождественно (константа!), но при этом
• .

Первое означает, что — так называемое отображение Келлера, то есть в точности объект гипотезы; второе — что оно не инъективно. (Если вас смущает вместо , просто разделите любую из компонент на .)

Проверить это может кто угодно; вот буквально весь код:

import sympy as sp

x, y, z = sp.symbols('x y z')
F = sp.Matrix([(1+x*y)**3*z + y**2*(1+x*y)*(4+3*x*y),
               y + 3*x*(1+x*y)**2*z + 3*x*y**2*(4+3*x*y),
               2*x - 3*x**2*y - x**3*z])

print(sp.expand(F.jacobian([x, y, z]).det()))    # -2
for p in [(0, 0, sp.Rational(-1,4)),
          (1, sp.Rational(-3,2), sp.Rational(13,2)),
          (-1, sp.Rational(3,2), sp.Rational(13,2))]:
    print(F.subs(dict(zip((x, y, z), p))).T)     # трижды [-1/4, 0, 0]

Да можно и руками тут подсчитать определитель, получится без проблем. Более того, базис Грёбнера идеала говорит, что других прообразов у точки нет: слой состоит ровно из этих трёх точек, и в твите приведён он целиком.

Заметьте: и коэффициенты отображения, и склеивающиеся точки вещественные и даже рациональные. Так что заодно закрыт и вещественный вопрос: найдено полиномиальное отображение с якобианом , не являющееся инъективным.

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

Как оно устроено: кубика вместо обратной функции

Раскрывать скобки в можно долго и без большого просветления. Ключ к устройству контрпримера — вот такое тождество (проверяется, опять же, в лоб):

   

Иными словами, координата алгебраична степени 3 (является корнем кубического многочлена) над образом: если , то — корень явно выписанной кубики

   

А по восстанавливается всё остальное: прямая проверка даёт тождество

   

откуда на слое

   

а находится из первого уравнения (оно линейно по ). Итого слой над точкой при — это в точности корни кубики (кроме тех, где , там убегает на бесконечность).

Вот и вся анатомия. Отображение — трёхлистное: у общей точки ровно три комплексных прообраза, и обратное “отображение”— это формула Кардано, применённая к . Никаким многочленом (и даже однозначной функцией) обратное, конечно, не является (и по теореме Акса–Гротендика иначе и быть не могло).

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

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

Рассмотрим прямую , на которой собственно найденный контрпример. Кубика вырождается в , и при у неё три вещественных корня, дающих три прообраза:

   

При получаются в точности три точки из твита. А если слева, то два боковых прообраза улетают на бесконечность вдоль гиперболы .

При они возвращаются из бесконечности уже комплексными, и вещественный прообраз остаётся один:

Слева — -координаты вещественных прообразов точки как функции ; в точке отмечен слой из твита. Справа — те же прообразы на плоскости : неподвижный прообраз в нуле и два убегающих по гиперболе.

Фазовая диаграмма. В общем положении число вещественных прообразов диктуется знаком дискриминанта кубики. Дискриминант и результант пары считаются явно, и оба, с точностью до множителей , пропорциональны одному и тому же многочлену

   

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

Поверхность (вместе с плоскостью ) — это и есть стены: пересекая их, цель теряет или приобретает пару вещественных прообразов. Вот так это выглядит в проекциях и :

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

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

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

Кстати, именно непустота этого множества разрешает топологический “парадокс”: трёхлистных накрытий у односвязного не бывает, как же многочлен выкрутился? Вот так и выкрутился: — накрытие не над всем , там не хватает поверхности и плоскости . Объединение называется множеством Елонека отображения , т.е. множеством точек, в которых не является собственным. А у дополнения к гиперповерхности фундаментальная группа уже нетривиальна, и глобально пронумеровать прообразы — а значит, склеить из локальных обратных глобальное — невозможно. Так что никакого топологического парадокса тоже не возникает.

Что ещё опровергает этот пример

Контрпример в автоматически даёт контрпримеры во всех размерностях : достаточно приписать тождественные координаты, . Двумерный случай — исходный вопрос Келлера — остаётся открытым, и все положительные результаты (начиная с Moh, 1983), конечно, тоже всё ещё верны. Не исключено, что в размерности 2 гипотеза верна, и было бы даже красиво, если бы было так.

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

Наконец, по редукции Басса–Коннелла–Райта–Ягжева мы теперь знаем, что в какой-то размерности существует контрпример вида с однородным кубическим ; найти его явно (и минимальную размерность) — ещё одна открытая задача. Как и вопрос о минимальной степени: в размерности 3 контрпример есть в степени 7, а степень 2 невозможна по теореме Вана; что происходит между — неизвестно.

Задача Смейла номер 16, таким образом, решена. Из восемнадцати задач списка это уже не первый случай, когда с ответом помогли компьютеры: например, в решении проблемы Смейла номер 14 (про аттрактор Лоренца) ключевую роль сыграло строгое computer-assisted доказательство. Но здесь, конечно, у LLM уже совсем другой уровень самостоятельности.

Как это было найдено, и что говорят люди

В отличие от истории с CDC, где OpenAI опубликовала препринт и полный промпт, здесь пока нет ни статьи, ни логов рассуждений, ни даже промпта — только твит, из которого мы знаем, что вопрос задал “друг Ахил” (по-видимому, Akhil Mathew). Левент Алпёге — серьёзный теоретико-числовик, ныне работающий в Anthropic. Если верить твиту, контрпример нашёл именно Claude Fable, хотя на промпт всё равно было бы интересно посмотреть.

Но, конечно, к истинности и важности результата всё это не имеет отношения. Проверка — минутное дело, и на GitHub уже лежит репозиторий jacobian-anatomy с проверками на sympy, Singular и PARI/GP и даже с сертификатом на Lean 4. MathWorld и Wikipedia обновились за сутки. Это, конечно, не то чтобы “новый ритм математики”, а свойство конкретного результата: когда проверка сводится к тому, чтобы подсчитать определитель , действительно не нужно долгое рецензирование.

А насчёт разных [по]следствий из этого яркого результата прямо сейчас могу дать только одну ссылку: Zihan Zhang начал выписывать разные следствия из найденного контрпримера. Думаю, этот список ещё не раз пополнится.

Кстати, этот пост тоже написан вместе с Claude Fable 5 — той самой моделью, которая нашла контрпример. В моём случае она независимо перепроверила все выкладки, посчитала базисы Грёбнера, на которые я ссылался, и нарисовала картинки выше. Предлагаю считать это не конфликтом интересов, а воспроизводимостью.

Заключение

Математика меняется. Три знаменитых открытых проблемы закрылись в последние пару месяцев. Опровержение, доказательство и снова опровержение; OpenAI, опять OpenAI и вот теперь Anthropic. Причём кажется, что это становится всё более обыденным: от “закрытой экспериментальной модели” мы перешли к обычному промпту для Fable.

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

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

Что дальше, коллеги?

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

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