С новыми идеями и ИИ под управлением человека исследователи решили математическую загадку 31-летней давности

Исследователь Microsoft и его коллега объединили новые математические идеи с ИИ под управлением человека для решения фундаментальной проблемы в многомерной геометрии и теории вероятностей

Краткий обзор

• Фундаментальный научный прорыв: исследователи разрешили гипотезу Каннана — Ловаса — Симоновица (KLS) — проблему 31-летней давности, которая широко считается одним из центральных нерешенных вопросов в многомерной геометрии и имеет значение для статистики, оптимизации, алгоритмов и компьютерных наук.
• Универсальный геометрический принцип: результат устанавливает универсальный геометрический принцип для лог-вогнутых распределений, показывая, что простые плоские сечения могут захватывать их самые узкие места с фиксированным коэффициентом независимо от размерности.
• Сотрудничество человека и ИИ: прорыв стал результатом исследовательского процесса на базе агентов под управлением человека, в ходе которого системы ИИ изучали математические возможности, а исследователи оценивали, отсеивали и перенаправляли поиск.
• Независимое подтверждение: множество независимых исследователей проверили это исследование, назвав его центральный критерий ключевым прорывом, за которым последовала машинная формальная верификация.

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

Гипотеза Каннана — Ловаса — Симоновица (KLS) была выдвинута в 1995 году. В ней ставится вопрос о том, является ли для широкого класса многомерных распределений вероятностей лучшее плоское или гиперплоскостное сечение всегда почти столь же эффективным, как и лучшее сечение любой формы. Точнее, KLS предсказывает, что эти два сечения отличаются не более чем на универсальную константу, независимо от количества измерений. Это установило бы не зависящий от размерности геометрический принцип с важными последствиями для многомерной геометрии, теории вероятностей и теоретической информатики. Поскольку геометрия этих сечений определяет, насколько быстро случайные блуждания могут исследовать распределение, гипотеза KLS также играет центральную роль в теории многомерной выборки.

С 1995 года математики накопили свидетельства в пользу истинности этой гипотезы, однако полное доказательство оставалось недоступным. Теперь два исследователя, включая Синьчжи Чжана (Xinzhi Zhang) из группы машинного обучения и оптимизации в Microsoft Research, доказали гипотезу KLS (opens in new tab). Они показали, что это соотношение выполняется с фиксированной границей независимо от количества измерений фигуры. До этой работы лучший из известных результатов (opens in new tab), полученный в июле 2026 года, допускал медленный рост этой границы по мере увеличения количества измерений. Эта работа устанавливает фундаментальный геометрический принцип: многомерные пространства устроены лучше, чем считалось ранее, а препятствия для навигации по ним не растут без ограничений по мере увеличения размерности.

Microsoft Research на BUILD 2026

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

Важность гипотезы KLS признавалась в научном сообществе задолго до ее разрешения. В своем годовом отчете за 2017–2018 годы Mathematical Sciences Research Institute (MSRI) (opens in new tab) назвали ее «центральной нерешенной задачей многомерной выпуклой геометрии». В Институте Саймонса (opens in new tab) ее охарактеризовали как «одну из важнейших нерешенных задач выпуклой геометрии». В материалах 2022 International Congress of Mathematicians (ICM) (opens in new tab) Ронен Элдан (Ronen Eldan) отметил ее широкие последствия для многомерной выпуклой и вычислительной геометрии. Издание Quanta Magazine (opens in new tab) писало, что KLS «лежит в основе многих вопросов статистики и информатики».

Технические детали

Авторы начали с усовершенствования результата июля 2026 года, чтобы сделать математическую границу более точной. Работая с агентами ИИ в рамках структурированного процесса под управлением человека, они изучили более 100 возможных подходов, многие из которых требовали длительных вычислений с тензорами высших порядков. В результате был получен новый математический критерий, который лег в основу окончательного доказательства.

Затем авторы обнаружили, что новый критерий можно применять рекурсивно. Каждую улучшенную границу можно было подставить обратно в то же рассуждение, чтобы получить еще более жесткую оценку. В версии статьи от 1 октября 2026 года это позволило уменьшить зависимость от размерности до итерированного логарифма. Эта функция растет чрезвычайно медленно, однако она все же растет с ростом размерности и поэтому еще не полностью разрешала гипотезу.

Заключительным этапом стало повторение всего рекурсивного уточнения, а не его однократное применение. Эта идея была навеяна более ранней работой авторов по быстрым алгоритмам линейного программирования. Авторы доказали, что малые погрешности, возникающие на каждом этапе, уменьшаются достаточно быстро, так что их общая сумма остается ограниченной универсальной константой, не зависящей от размерности. Это позволило избавиться от зависимости от количества измерений и завершить доказательство в версии статьи от 4 октября 2026 года.

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

Независимое подтверждение

В тот же день, когда авторы опубликовали свое полное доказательство, другая группа ведущих экспертов опубликовала полное доказательство (opens in new tab), над которым они работали параллельно. Их работа опиралась на выводы из первой версии (opens in new tab) статьи Microsoft, которую они назвали «решающим шагом в доказательстве». Третье доказательство (opens in new tab), появившееся отдельно в тот же день, основано на тесно связанной идее. Кроме того, впоследствии была выпущена Lean 4 formalization (opens in new tab), в которой ключевой критерий из первой статьи Microsoft сочетается с дополнительными исследованиями.

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

Руководство в процессе взаимодействия человека и ИИ

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

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

Заключение

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

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

Благодарности

Спасибо нашему соавтору Чжао Сюну (Zhao Song) за его вклад в эту работу, а также Виктору Рейсу (открывается в новой вкладке) и Ишаю Менахе за ценные обсуждения на протяжении всего проекта.