Пятница у меня традиционно посвящена обзорам игр, но, как писал Лев Николаевич, не любил и не трудился не могу молчать. Обзор игры я напишу чуть позже, а сегодня опять про математику.
Оговорка "на этой неделе (в первой половине этой недели...)" оказалась пророческой, и вот у нас через два дня опять громкий результат. Опять пала широко известная гипотеза, на этот раз с чрезвычайно чистым примером полного отсутствия дополнительных harness'ов или хитрого промптинга.
Ниже только введение и оглавление, читать как всегда по ссылке (и очень рекомендую прочитать хотя бы часть про четыре промпта):
Всё течёт, всё опровергается: гипотеза Диница — Гарга — Гёманса
1. Введение
В прошлый раз, рассказывая про контрпример к проблеме якобиана, я закончил пост вопросом: "Что дальше, коллеги?"
Ответ занял два дня.
22 июля Дмитрий Рыбин написал в X, что GPT 5.6 Pro опровергла гипотезу Диница — Гарга — Гёманса (Dinitz–Garg–Goemans conjecture) из теории потоков в графах. Гипотеза простояла с конца 1990-х; в 2025 году Swamy et al. всё ещё называли её “a famous conjecture” и писали, что даже существенно ослабленный вариант был бы прорывом.
Как и в случае проблемы якобиана, здесь пока нет ни журнальной статьи, ни формального рецензирования, но они и не нужны, потому что проверить контрпример очень легко. У нас есть пост Рыбина, выложенный им полный диалог с моделью и четырёхстраничный арифметический сертификат, но в графе всего семь вершин, девять дуг и восемь возможных неделимых потоков. Мы с GPT независимо проверили все восемь программой, которая перебирает буквально все пути в графе, и никаких ошибок здесь нет.
Более того, контрпример оказался весьма интересно устроенным. Внутри него прячется известный в комбинаторной оптимизации объект — треугольник попарных конфликтов.
Давайте разберёмся, что такое делимые и неделимые потоки и в чём состояла гипотеза. Потом обсудим, почему она казалась естественной и почему её было так трудно доказать. Затем проверим контрпример, вытащим из него структурную идею и попробуем его уменьшить. А в конце, разумеется, посмотрим на промпты. Спойлер: там буквально написано "you should do a breakthrough".
2. Потоки, которые можно и нельзя делить
3. Теорема Диница — Гарга — Гёманса
4. Почему в гипотезу верили и почему она была сложной
5. Семь вершин и девять дуг
6. Что там происходит на самом деле
7. Проверка, уменьшение контрпримера и граница 9/8
(в этом разделе у меня даже получилось немножко продолжить рассуждение GPT и сформулировать то, как теперь выглядит открытый вопрос)
8. Четыре промпта
9. Заключение
[...]
За три последних поста мы увидели сначала двухстраничное доказательство гипотезы о двойном покрытии циклами, потом многочлен, помещающийся в твит, а теперь — контрпример в виде стандартного треугольника целочисленной оптимизации. Но каждый из этих кажущихся простыми результатов закрыл гипотезу, над которой действительно думало много живых математиков.
У меня нет сомнений, что если бы любой из этих результатов получил человек, он стал бы широко известен в узких кругах и всегда имел бы гарантированную профессорскую позицию в хорошем месте, даже если бы больше ничего великого не сделал и продолжал бы всю жизнь изучать следствия и расширения своего прорывного результата (таких примеров в науке много, это не что-то плохое). Так что вопрос о том, достигли ли AI-модели человеческого уровня в математике, кажется мне уже закрытым.
А что ещё дальше, коллеги?..
#ai #math #blog #longreads
Оговорка "на этой неделе (в первой половине этой недели...)" оказалась пророческой, и вот у нас через два дня опять громкий результат. Опять пала широко известная гипотеза, на этот раз с чрезвычайно чистым примером полного отсутствия дополнительных harness'ов или хитрого промптинга.
Ниже только введение и оглавление, читать как всегда по ссылке (и очень рекомендую прочитать хотя бы часть про четыре промпта):
Всё течёт, всё опровергается: гипотеза Диница — Гарга — Гёманса
1. Введение
В прошлый раз, рассказывая про контрпример к проблеме якобиана, я закончил пост вопросом: "Что дальше, коллеги?"
Ответ занял два дня.
22 июля Дмитрий Рыбин написал в X, что GPT 5.6 Pro опровергла гипотезу Диница — Гарга — Гёманса (Dinitz–Garg–Goemans conjecture) из теории потоков в графах. Гипотеза простояла с конца 1990-х; в 2025 году Swamy et al. всё ещё называли её “a famous conjecture” и писали, что даже существенно ослабленный вариант был бы прорывом.
Как и в случае проблемы якобиана, здесь пока нет ни журнальной статьи, ни формального рецензирования, но они и не нужны, потому что проверить контрпример очень легко. У нас есть пост Рыбина, выложенный им полный диалог с моделью и четырёхстраничный арифметический сертификат, но в графе всего семь вершин, девять дуг и восемь возможных неделимых потоков. Мы с GPT независимо проверили все восемь программой, которая перебирает буквально все пути в графе, и никаких ошибок здесь нет.
Более того, контрпример оказался весьма интересно устроенным. Внутри него прячется известный в комбинаторной оптимизации объект — треугольник попарных конфликтов.
Давайте разберёмся, что такое делимые и неделимые потоки и в чём состояла гипотеза. Потом обсудим, почему она казалась естественной и почему её было так трудно доказать. Затем проверим контрпример, вытащим из него структурную идею и попробуем его уменьшить. А в конце, разумеется, посмотрим на промпты. Спойлер: там буквально написано "you should do a breakthrough".
2. Потоки, которые можно и нельзя делить
3. Теорема Диница — Гарга — Гёманса
4. Почему в гипотезу верили и почему она была сложной
5. Семь вершин и девять дуг
6. Что там происходит на самом деле
7. Проверка, уменьшение контрпримера и граница 9/8
(в этом разделе у меня даже получилось немножко продолжить рассуждение GPT и сформулировать то, как теперь выглядит открытый вопрос)
8. Четыре промпта
9. Заключение
[...]
За три последних поста мы увидели сначала двухстраничное доказательство гипотезы о двойном покрытии циклами, потом многочлен, помещающийся в твит, а теперь — контрпример в виде стандартного треугольника целочисленной оптимизации. Но каждый из этих кажущихся простыми результатов закрыл гипотезу, над которой действительно думало много живых математиков.
У меня нет сомнений, что если бы любой из этих результатов получил человек, он стал бы широко известен в узких кругах и всегда имел бы гарантированную профессорскую позицию в хорошем месте, даже если бы больше ничего великого не сделал и продолжал бы всю жизнь изучать следствия и расширения своего прорывного результата (таких примеров в науке много, это не что-то плохое). Так что вопрос о том, достигли ли AI-модели человеческого уровня в математике, кажется мне уже закрытым.
А что ещё дальше, коллеги?..
#ai #math #blog #longreads