На протяжении почти 80 лет математики изучали обманчиво простой вопрос: если на плоскости разместить n точек, то сколько пар точек будут находиться на расстоянии ровно 11 друг от друга?
Это задача о единичном расстоянии на плоскости, впервые сформулированная Полом Эрдёшем в 1946 году. Это один из самых известных вопросов в комбинаторной геометрии, простой по формулировке и невероятно сложный для решения. В книге 2005 года «Исследовательские задачи в дискретной геометрии» Брасса, Мозера и Паха она названа «возможно, самой известной (и самой простой для объяснения) задачей в комбинаторной геометрии». Нога Алон, ведущий специалист по комбинаторике из Принстонского университета, называет эту задачу «одной из любимых задач Эрдёша». Эрдёш даже предлагал денежное вознаграждение за ее решение.
Сегодня мы расскажем о прорыве в решении задачи о единичном расстоянии. Со времен оригинальной работы Эрдёша считалось, что конструкции в виде «квадратной сетки», изображенные ниже, по сути являются оптимальными для максимизации количества пар точек, находящихся на единичном расстоянии друг от друга. Внутренняя модель OpenAI опровергла эту давнюю гипотезу, предоставив бесконечное множество примеров, которые позволяют добиться полиномиального улучшения. Доказательство было проверено группой сторонних математиков. Они также написали сопроводительную статью, в которой объясняют ход рассуждений и дают дополнительные сведения о важности этого результата.
Этот результат примечателен еще и тем, как он был получен. Доказательство было получено с помощью новой модели логического вывода общего назначения, а не системы, обученной специально для работы с математикой, ориентированной на поиск стратегий доказательства или нацеленной на решение задачи о единичном расстоянии. В рамках более масштабной работы по проверке того, могут ли продвинутые модели внести свой вклад в передовые исследования, мы протестировали эту модель на наборе задач Эрдеша. В данном случае она нашла доказательство, решающее нерешенную задачу.
Это доказательство — важная веха для математического сообщества и специалистов в области искусственного интеллекта. Впервые сложная нерешенная задача, лежащая в основе целого раздела математики, была решена искусственным интеллектом самостоятельно. Это также демонстрирует глубину рассуждений, которые теперь поддерживают эти системы. Математика — особенно наглядный пример для проверки рассуждений: задачи сформулированы четко, потенциальные доказательства можно проверить, а длинная цепочка рассуждений работает только в том случае, если все звенья логической цепи верны. Примечателен и метод, с помощью которого была решена задача. В этом доказательстве неожиданные и сложные идеи из алгебраической теории чисел применяются для решения элементарного геометрического вопроса.
Доказательство доступно здесь. Сопутствующая статья, написанная ведущими математиками со стороны, доступна здесь. Сокращенную версию обоснования модели можно найти здесь.
Проблема с единичным расстоянием
Пусть u(n) — максимально возможное количество пар точек на расстоянии в единицу от друг друга среди nn точек на плоскости. Легко построить примеры с линейной скоростью роста: если расположить n точек на одной линии, получится n−1 пар, а на квадратной сетке — около 2n пар. Оказалось, что наиболее известная ранее конструкция, основанная на масштабированной квадратной сетке, дает еще больший результат: n^(1+C/loglog(n)) для константы C. Поскольку loglog(n) стремится к бесконечности при n, дополнительный член в показателе степени стремится к 0, то есть эти конструкции растут лишь немного быстрее, чем линейно. На протяжении десятилетий считалось, что этот показатель практически оптимален и ни одна конструкция не может значительно превзойти квадратную сетку. С технической точки зрения, Эрдёш предположил, что верхняя граница составляет n^(1+o(1)), где дополнительное o(1) указывает на член, стремящийся к 0 при n.
Наш новый результат опровергает эту гипотезу. Точнее говоря, для бесконечно большого числа значений n доказательство строится таким образом, что в конфигурации из n точек имеется не менее n^(1+δ) пар точек, находящихся на расстоянии в единицу от друг друга, для некоторого фиксированного показателя δ>0. (В исходном доказательстве, полученном с помощью искусственного интеллекта, не указано конкретное значение δ, но в уточненном варианте, предложенном профессором математики из Принстона Уиллом Сойном, показано, что можно взять δ=0.014)
История вопроса помогает понять, почему результат оказался таким неожиданным. Самая известная нижняя граница практически не менялась с тех пор, как в 1946 году Эрдёш предложил свою конструкцию. Наилучшая верхняя граница O(n^4/3)) была получена в работе Спенсера, Семереди и Троттера в 1984 году. Несмотря на последующие уточнения и связанные с ними структурные исследования Секели, Каца и Силиера, Пача, Раза, Солимоши и других, верхняя граница практически не изменилась. В качестве доказательства гипотезы Матушек и Алон-Бучич-Зауэрманн изучили задачу о неевклидовых расстояниях на плоскости и доказали, что «большинство» таких неевклидовых расстояний в некотором смысле подчиняются этой гипотезе.
Удивительно, но ключевые элементы этой конструкции взяты из совершенно другой области математики — алгебраической теории чисел, которая изучает такие понятия, как факторизация в расширениях целых чисел, известных как поля алгебраических чисел.
Новые методы алгебраической теории чисел
Если говорить в общих чертах, доказательство начинается со знакомой геометрической идеи и развивает ее в неожиданном направлении.
Исходную нижнюю границу, предложенную Эрдешем, можно объяснить с помощью гауссовых целых чисел: чисел вида a+bi, где a и b — целые числа, а i — квадратный корень из −1. Гауссовы целые числа являются расширением обычных целых чисел и, как и они, обладают такими свойствами, как разложение на простые множители. Такие расширения обычных целых чисел или рациональных чисел называются полями алгебраических чисел. В новом аргументе вместо гауссовых целых чисел используются более сложные обобщения из алгебраической теории чисел с более богатой симметрией, которые позволяют создавать гораздо больше различий в единичных отрезках.
В точном доказательстве используются такие инструменты, как башни бесконечных полей и теория Голода — Шафаревича, чтобы показать, что числовые поля, необходимые для доказательства, действительно существуют. Эти идеи были хорошо известны специалистам по алгебраической теории чисел, но тот факт, что они применимы к геометрическим вопросам на евклидовой плоскости, стал большим сюрпризом.
Этот результат знаменует собой важный этап во взаимодействии искусственного интеллекта и математики: система искусственного интеллекта самостоятельно решила давнюю нерешенную задачу, лежащую в основе целого направления исследований. Кроме того, это первый пример нового формата сотрудничества между искусственным интеллектом и математиками. В данном случае дополнительная работа сторонних математиков дает гораздо более полное представление о проблеме, чем само по себе решение.
Как пишет Томас Блум в сопроводительной заметке:
“Оценивая важность и влияние доказательства, сгенерированного искусственным интеллектом, я задаюсь вопросом: узнали ли мы что-то новое об этой проблеме? Стали ли мы лучше понимать дискретную геометрию? Думаю, ответ — сдержанное «да»: это показывает, что теоретико-числовые построения могут рассказать о подобных вопросах гораздо больше, чем мы предполагали. Более того, требуемая теория чисел может быть очень глубокой. Несомненно, в ближайшие месяцы многие специалисты по алгебраической теории чисел будут внимательно изучать другие нерешенные проблемы в области дискретной геометрии. ”
Неожиданная связь между теорией алгебраических чисел и дискретной геометрией, выявленная в ходе решения, — одна из причин, по которой этот результат заслуживает внимания. Он не просто подтверждает конкретную гипотезу, но и может стать отправной точкой для дальнейшего изучения смежных проблем.
Блум также указывает на более широкие возможности:
“Границы познания очень размыты, и, без сомнения, в ближайшие месяцы и годы мы увидим аналогичные успехи во многих других областях математики, где давние нерешенные проблемы будут решены с помощью искусственного интеллекта, который обнаружит неожиданные связи и доведет существующие технические средства до предела их возможностей. ИИ помогает нам полнее исследовать математический мир, который мы создавали веками. Какие еще невиданные чудеса ждут нас впереди?”
Этот результат — многообещающий пример того, как искусственный интеллект предлагает не просто решение, а математическое открытие, значение которого становится более понятным и глубоким благодаря последующему осмыслению человеком.
Искусственный интеллект вот-вот начнет играть очень важную роль в творческой составляющей научных исследований, и самое главное — в самих исследованиях в области искусственного интеллекта. Этот прогресс не стал неожиданностью, но он лишь подчеркивает важность понимания следующего этапа развития ИИ, проблем, связанных с согласованием работы очень интеллектуальных систем, а также будущего сотрудничества человека и искусственного интеллекта.
Это будущее по-прежнему зависит от человеческого суждения. Экспертиза становится все более ценной. ИИ может помочь в поиске, выдвижении предположений и их проверке. Люди выбирают важные для них проблемы, интерпретируют результаты и решают, какие вопросы следует изучить дальше.
- Много интересного - в телеграм "Математика не для всех"
- Взгляд на философию со стороны технаря - телеграм "Философия не для всех"