Модель OpenAI опровергла ключевую гипотезу в дискретной геометрии

Почти 80 лет математики изучают обманчиво простой вопрос: если разместить $n$ точек на плоскости, сколько пар точек могут находиться ровно на расстоянии $1$ друг от друга?

Это задача о единичных расстояниях на плоскости, впервые поставленная Полом Эрдёшем в 1946 году. Это один из самых известных вопросов комбинаторной геометрии: его легко сформулировать и удивительно трудно решить. В книге 2005 года «Открытые проблемы дискретной геометрии» (Research Problems in Discrete Geometry) Брасса, Мозера и Паха она названа «возможно, самой известной (и самой простой для объяснения) задачей комбинаторной геометрии». Нога Алон, ведущий специалист по комбинаторике из Принстонского университета, называет её «одной из любимых задач Эрдёша». Эрдёш даже предложил денежную премию за решение этой задачи.

Сегодня мы делимся прорывом в задаче о единичных расстояниях. Со времен исходной работы Эрдёша преобладало мнение, что конструкции «квадратной решетки», показанные ниже, по сути оптимальны для максимизации числа пар на единичном расстоянии. Внутренняя модель OpenAI опровергла эту давнюю гипотезу, предложив бесконечное семейство примеров, дающих полиномиальное улучшение. Доказательство было проверено группой внешних математиков. Они также написали сопроводительную статью, объясняющую ход доказательства и дающую дополнительный контекст о значимости результата.

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

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

Лауреат Филдсовской премии Тим Гауэрс в сопроводительной статье называет этот результат «вехой в математике ИИ». По словам ведущего специалиста по теории чисел Арула Шанкара, «по моему мнению, эта статья показывает, что современные модели ИИ уже не просто помогают математикам — они способны выдвигать оригинальные и изобретательные идеи, а затем доводить их до результата».

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

Пусть $u(n)$ — наибольшее возможное число пар на единичном расстоянии среди $n$ точек на плоскости. Примеры с линейным темпом роста легко построить: если расположить $n$ точек на прямой, получится $n-1$ пар, а квадратная решетка дает около $2n$ пар. Однако ранее лучшая известная конструкция, получаемая из масштабированной квадратной решетки, дает еще больше: $n^{1 + C / \log \log(n)}$ для некоторой константы $C$. Поскольку $\log \log(n)$ стремится к бесконечности при росте $n$, дополнительный член в показателе стремится к $0$, а значит, эти конструкции обеспечивают рост лишь немного быстрее линейного. Десятилетиями широко считалось, что этот темп по сути является наилучшим возможным и что никакая конструкция не может существенно улучшить квадратную решетку. Технически Эрдёш предположил верхнюю границу $n^{1+o(1)}$, где дополнительный член $o(1)$ обозначает величину, стремящуюся к $0$ при росте $n$.

Наш новый результат опровергает эту гипотезу. Точнее, для бесконечно многих значений $n$ доказательство строит конфигурации из $n$ точек как минимум с $n^{1+\delta}$ парами на единичном расстоянии для некоторого фиксированного показателя $\delta > 0$. (Исходное доказательство ИИ не дает явного значения $\delta$, но готовящееся уточнение профессора математики Принстона Уилла Соуина показало, что можно взять $\delta=0.014$.)

История этой задачи помогает понять, почему результат оказывается неожиданным. Лучшая известная нижняя граница оставалась по существу неизменной со времени исходной конструкции Эрдёша 1946 года. Лучшая верхняя граница, $O(n^{4/3})$, восходит к работе Спенсера, Семереди и Троттера 1984 года, и несмотря на последующие уточнения и связанную структурную работу Секеи, Каца и Силье, Паха, Раза и Шоймоши и других, верхняя граница по существу не изменилась. В пользу гипотезы Матушек и Алон-Буцич-Зауэрман изучали задачу с неевклидовыми расстояниями на плоскости и доказали, что «большинство» таких неевклидовых расстояний в некотором смысле подчиняются этой гипотезе.

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

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

Исходную нижнюю границу Эрдёша можно понять через гауссовы целые: числа вида $a+bi$, где $a$ и $b$ — целые числа, а $i$ — квадратный корень из $-1$. Гауссовы целые расширяют обычные целые числа и, как и они, обладают свойствами вроде единственности разложения на простые множители. Такие расширения обычных целых или рациональных чисел известны как алгебраические числовые поля. Новое доказательство заменяет гауссовы целые более сложными обобщениями из алгебраической теории чисел с более богатыми симметриями, которые могут создавать гораздо больше разностей единичной длины.

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

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

Как пишет Томас Блум в сопроводительной заметке:

«Оценивая важность и влияние доказательства, созданного ИИ, я задаю себе вопрос: научило ли оно нас чему-то новому о задаче? Лучше ли мы теперь понимаем дискретную геометрию? Думаю, ответ — сдержанное да: это показывает, что конструкции из теории чисел могут сказать об этих вопросах гораздо больше, чем мы предполагали; более того, требуемая теория чисел может быть очень глубокой. Несомненно, многие специалисты по алгебраической теории чисел в ближайшие месяцы внимательно посмотрят на другие открытые задачи дискретной геометрии.»

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

Блум также указывает на более широкую возможность:

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

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

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

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

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

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