Решена 31-летняя математическая задача — гипотеза КЛС

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

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

С 1995 года математики находили свидетельства в пользу гипотезы, но полного доказательства не было. Теперь два исследователя, в том числе Синьчжи Чжан из группы машинного обучения и оптимизации Microsoft Research, доказали её. Они показали, что соотношение выполняется с фиксированной границей при любом числе измерений. В предыдущем лучшем результате, опубликованном в июле 2026 года, эта граница медленно росла вместе с размерностью. Новая работа устанавливает, что пространства высоких размерностей устроены лучше, чем было известно ранее: трудности их исследования не растут безгранично с увеличением числа измерений.

Упрощённая иллюстрация гипотезы KLS на правильном тетраэдре

Источник: microsoft.com

Почему гипотеза важна

Значение гипотезы КЛС признавали задолго до её доказательства. В годовом отчёте за 2017–2018 годы Математический институт наук (MSRI) назвал её одной из центральных нерешённых задач выпуклой геометрии высоких размерностей. Институт Саймонса охарактеризовал её как одну из важнейших открытых проблем выпуклой геометрии. В материалах Международного конгресса математиков 2022 года Ронен Элдан отметил её широкое значение для выпуклой геометрии высоких размерностей и вычислительной геометрии. Журнал Quanta писал, что гипотеза КЛС лежит в основе многих вопросов статистики и информатики.

Как строили доказательство

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

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

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

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

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

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

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

Как исследователи направляли ИИ

Работа над гипотезой КЛС показала, как исследователи могут направлять ИИ, вместо того чтобы поручать сложную задачу одной передовой модели или агенту в едином автономном запуске. Авторы использовали итеративный поиск с участием человека: несколько агентов параллельно исследовали варианты идеи, исследователь проверял промежуточные результаты, отбрасывал бесперспективные направления и передавал наиболее удачные варианты в следующий раунд. До ключевого прорыва команда изучила около ста исследовательских траекторий.

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

Вывод

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

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

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

Авторы поблагодарили соавтора Чжао Суна за вклад в работу, а также Виктора Рейса и Ишая Менаше — за полезные обсуждения на протяжении проекта.

Связанная публикация

Авторы

Области исследований