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

Прочитайте доказательство (откроется в новом окне) Прочитайте сопроводительные замечания (откроется в новом окне)

На протяжении почти 80 лет математики изучают обманчиво простой вопрос: если вы разместите $Сколько$ пар точек на плоскости могут находиться на расстоянии ровно 11 друг от друга? На расстоянии $1$ друг от друга?

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

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

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

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

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

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

1 из 4

• Нога Алон
• Тим Гоуэрс
• Арул Шанкар
• Якоб Цимерман

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

Ранее известное построение множества единичных расстояний на основе масштабированной квадратной сетки.

Проблема единичного расстояния

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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