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

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

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

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

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

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

Обладатель Fields medal Тим Гауэрс в сопутствующей статье называет результат «вехой в AI-математике». По словам ведущего теоретика чисел Арлула Шанкара, «по моему мнению, эта работа показывает, что современные AI-модели выходят за рамки простых помощников для математиков-людей — они способны на оригинальные, изобретательные идеи и затем способны довести их до завершения».

Математики о результате

1 из 4

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

Задача о единичных расстояниях

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

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

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

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

$O \left(\right. n^{4 / 3} \left.\right)$, восходит к работе Спенсера, Шемереди и Троттера 1984 года, и, несмотря на последующие уточнения и связанные структурные результаты Секейя, Katz и Silier, Pach, Raz и Solymosi и других, верхняя оценка в целом оставалась той же. В качестве аргумента в пользу гипотезы Матуушек и Alon-Bucić-Sauermann изучали задачу для неевклидовых расстояний в плоскости и доказали, что «большинство» таких неевклидовых расстояний в некотором смысле подчиняются этой гипотезе.

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

После проверки первоначального доказательства мы исследовали, как меняется успешность наших моделей на этой задаче при разном объеме test-time compute. Результаты показаны здесь.

Новые методы из алгебраической теории чисел

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

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

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

Что это значит для математики

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

Как пишет Томас Блум в сопутствующей заметке:

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

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

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

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

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

Почему это важно

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

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

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

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

Материал — перевод статьи с английского.

Оригинал: An OpenAI model has disproved a central conjecture in discrete geometry