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

Доказав более широкую версию знаменитой 10-й проблемы Гильберта, две группы математиков расширили область математической непознаваемости. Комментарий Сохранить статью Прочитать позже

Введение

Мир математики полон недостижимых уголков, где живут неразрешимые проблемы. Теперь обнаружилась еще одна.

В 1900 году выдающийся математик Дэвид Гильберт объявил список из 23 ключевых проблем, которые должны были направлять следующее столетие математических исследований. Его проблемы не только предоставили дорожную карту для этой области, но и отразили более амбициозное видение — построить прочный фундамент, из которого можно было бы вывести все математические истины.

Ключевой частью этого видения было то, что математика должна быть «полной». То есть все ее утверждения должны быть доказуемо истинными или ложными.

В 1930-х годах Курт Гёдель продемонстрировал, что это невозможно: в любой математической системе есть утверждения, которые нельзя ни доказать, ни опровергнуть. Несколько лет спустя Алан Тьюринг и другие развили его работу, показав, что математика пронизана «неразрешимыми» утверждениями — проблемами, которые не могут быть решены никаким компьютерным алгоритмом.

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

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

Главной из них была его 10-я проблема. Она касается диофантовых уравнений: многочленов с целыми коэффициентами, таких как x2 + y2 = 5. Эти знакомые уравнения являются одним из самых центральных объектов изучения в математике. На протяжении тысячелетий математики искали для них целочисленные решения. В этом примере, например, одно решение — x = 1, y = 2 (так как 12 + 22 = 5). Другое — x = 2, y = −1.

Другие диофантовы уравнения, такие как x2 + y2 = 3, не имеют целочисленных решений. Десятая проблема Гильберта спрашивала, всегда ли можно сказать, имеет ли данное диофантово уравнение целочисленные решения. Существует ли алгоритм, позволяющий определить это для каждого уравнения, или проблема неразрешима? Возможно, нет надежды на полный и систематический подход ко всей математике — или даже ко всем 23 проблемам Гильберта — но он все еще может существовать, когда дело касается диофантовых уравнений, образуя микрокосм его первоначальной программы. «Эта проблема — очень естественная версия этой мечты», — сказал Питер Койманс из Утрехтского университета.

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

Даже в этой самой простой разновидности математики таится непостижимость.

Математики хотели проверить досягаемость вывода Матиясевича. Допустим, вы допускаете, что ваши диофантовы уравнения имеют комплексные решения (числа, которые можно записать с действительной и мнимой частями, и которые не ограничиваются целыми числами). В этом случае каждое диофантово уравнение имеет решение, и ответ на 10-ю проблему Гильберта — решительное «да». Но есть целый ряд диофантовых уравнений между теми, решения которых должны быть целыми числами, и теми, решения которых могут быть комплексными.

«Она неразрешима для целых чисел, а когда вы переходите к гораздо большим системам чисел, вы внезапно получаете разрешимость», — сказал Барри Мазур из Гарвардского университета. «Где же граница?»

За 50 лет с тех пор, как была решена 10-я проблема Гильберта, математики искали эту границу. Теперь Койманс и его давний соратник Карло Пагано из Университета Конкордия в Монреале, а также другая группа исследователей, работавших независимо, сделали большой шаг к этой цели. Обе группы доказали, что для обширного и важного набора настроек за пределами целых чисел также не существует общего алгоритма для определения того, имеет ли решение любое заданное диофантово уравнение. Работа не только позволяет математикам получить более точное представление о том, что они могут и не могут знать, но и дает им совершенно новый уровень контроля над одним из самых центральных объектов в математике.

Расширение от целых чисел

Новые доказательства были сосредоточены на естественном расширении 10-й проблемы Гильберта. Расширение касается диофантовых уравнений, решения которых принадлежат числовым системам, которые являются близкими родственниками целых чисел.

Если вы начинаете с чисел 1 и −1, вы можете складывать их в разных комбинациях, чтобы получить все остальные целые числа. Но, скажем, вы начинаете с другого конечного набора чисел — например, 1, −1 и $latex sqrt{2}$. Вы можете складывать эти числа в разных комбинациях, чтобы получить новую числовую систему, называемую кольцом целых чисел (названную так, хотя кольцо не обязательно должно содержать только целые числа). Другие кольца целых чисел могут быть построены из наборов чисел, которые включают, скажем, квадратный корень из −1 (мнимое число, которое математики называют i) или кубический корень из 2. Существует ли алгоритм, который всегда может определить, имеет ли заданное диофантово уравнение решения, которые попадают в одно из этих колец целых чисел?

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

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

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

Можно также рассматривать диофантовы уравнения как вычислительные устройства. Рассмотрим уравнение y = x2. Оно имеет бесконечно много целочисленных решений. Если вы подставите различные целые числа вместо x и решите относительно y, все полученные вами значения будут принадлежать известному набору целых чисел: полным квадратам. Легко представить себе компьютерную программу (то есть машину Тьюринга), которая выполняет эквивалентную задачу: «Вычислить последовательность полных квадратов».

Другие диофантовы уравнения могут кодировать другие виды вычислений.

Чтобы решить исходную 10-ю проблему Гильберта, математики развили эту идею. В работе, которая началась с Джулии Робинсон и других около 1950 года и достигла кульминации в результате Матиясевича 1970 года, было показано, что для каждой машины Тьюринга существует соответствующее диофантово уравнение. «Это было совершенно неожиданно», — сказал Гектор Пастен из Папского католического университета Чили в Сантьяго. «Диофантовы уравнения над целыми числами достаточны для определения, по сути, всего, что вы можете себе представить».

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

Другими словами, 10-я проблема Гильберта неразрешима.

Математики надеялись использовать тот же подход, чтобы доказать расширенную версию проблемы с кольцами целых чисел, но они столкнулись с препятствием.

Засорение работ

Полезное соответствие между машинами Тьюринга и диофантовыми уравнениями разваливается, когда уравнениям разрешено иметь нецелочисленные решения. Например, снова рассмотрим уравнение y = x2. Если вы работаете в кольце целых чисел, которое включает $latex sqrt{2}$, то вы получите некоторые новые решения, такие как x = $latex sqrt{2}$, y = 2. Уравнение больше не соответствует машине Тьюринга, которая вычисляет полные квадраты, — и, в более общем смысле, диофантовы уравнения больше не могут кодировать проблему остановки.

Но в 1988 году аспирантка Нью-Йоркского университета по имени Саша Шляпентох начала экспериментировать с идеями, как обойти эту проблему. К 2000 году она и другие сформулировали план. Допустим, вы добавили кучу дополнительных членов в уравнение типа y = x2, которые магическим образом заставили бы x снова стать целым числом, даже в другой системе счисления. Затем вы могли бы спасти соответствие с машиной Тьюринга. Можно ли сделать то же самое для всех диофантовых уравнений? Если так, то это означало бы, что проблема Гильберта могла бы закодировать проблему остановки в новой системе счисления.

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

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

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

Бессонные ночи

Еще со времен студенчества Койманс думал о 10-й проблеме Гильберта. На протяжении всей аспирантуры и сотрудничества с Пагано она манила его. «Я проводил несколько дней каждый год, думая об этом, и ужасно застревал», — сказал Койманс. «Я пробовал три вещи, и все они взрывались у меня на глазах».

В 2022 году на конференции в Банфе (Канада) он и Пагано в итоге обсудили эту проблему. Они надеялись, что вместе смогут построить специальную эллиптическую кривую, необходимую для решения проблемы. Закончив несколько других проектов, они принялись за работу.

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

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

Они застряли. «У меня было это темное чувство», — сказал Койманс. «Я начал подозревать, что мы что-то упускаем».

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

Койманс понял, что эта другая работа дала им важную подсказку, одно из тех странных и удивительных математических соответствий, которые иногда появляются: если число, которое они использовали в квадратичном повороте, было произведением ровно трех простых чисел, то они получили бы контроль, необходимый для гарантии второго свойства. Но поскольку их эллиптическая кривая должна была быть построена так тщательно и соответствовать стольким спецификациям, существовало множество дополнительных ограничений на то, какими могли быть эти три простых числа. Смогли бы Койманс и Пагано найти те, которые работали — независимо от того, какое кольцо они использовали?

Пагано случайно запланировал визит в Швейцарский федеральный технологический институт Цюриха, где в то время работал Койманс, через несколько дней. Они провели следующую неделю, сражаясь вместе у доски, пытаясь найти простые числа, которые соответствовали бы всем ограничениям. Наконец, они поняли, что им нужно использовать четыре простых числа, а не три, чтобы построить свой квадратичный поворот. Это позволило им применить метод из совершенно отдельной области математики, называемой аддитивной комбинаторикой, чтобы гарантировать, что правильная комбинация простых чисел существует для каждого кольца.

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

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

Обе группы надеются использовать свои методы — которые дают им беспрецедентный контроль над эллиптическими кривыми и связанными с ними уравнениями — для достижения прогресса и в других задачах. «Есть вероятность, что эти два метода можно будет использовать вместе, чтобы сделать еще больше», — сказал Манджул Бхаргава, математик из Принстонского университета и один из авторов второго доказательства.

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

По словам Эндрю Грэнвилла из Монреальского университета, это лишь один из многих вопросов, которые «отражают философскую сторону того, что в мире является истиной».

Все знания имеют пределы. «Это напоминает нам, что есть вещи, которые просто невыполнимы», — сказал Грэнвилл. «Неважно, кто ты или что ты».

Источник: www.quantamagazine.org