Учёные подтвердили неразрешимость одной из ключевых проблем математики

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

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

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

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

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

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

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

Некоторые диофантовы уравнения, например x² + y² = 3, не имеют целочисленных решений. Десятая проблема Гильберта ставит вопрос: всегда ли возможно определить, имеет ли данное диофантово уравнение целочисленные решения? То есть существует ли алгоритм, который способен решать это для любого уравнения, или же задача неразрешима? Пусть надежда на «полную» и систематическую теорию всей математики (и даже всех 23 задач Гильберта) оказалась несбыточной, но возможно, что в контексте диофантовых уравнений такая всеохватывающая система существует, представляя собой микромир первоначальной программы Гильберта. «Эта проблема — очень естественная версия той мечты», — говорит Питер Койманс из Университета Утрехта.

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

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

Тем не менее математики захотели исследовать границы, до которых простирается вывод Матиясевича. Предположим, мы разрешим диофантовым уравнениям иметь решения в комплексных числах (числах вида a + bi, где a и b — действительные числа). Тогда каждое диофантово уравнение обязательно будет иметь решение, и ответ на десятую проблему Гильберта в таком случае звучит как уверенное «да». Но существует целый спектр диофантовых уравнений между теми, что имеют только целочисленные решения, и теми, что допускают решения в комплексе.

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

За последние полвека, прошедшие после решения исходной формы десятой проблемы Гильберта, математики стремились отыскать эту «черту». И вот недавно Койманс и его давний соавтор Карло Пагано из Университета Конкордии в Монреале — а также другая независимая исследовательская группа — сделали существенный шаг в этом направлении. Обе команды доказали, что для обширного и важного класса числовых систем , выходящего далеко за рамки целых чисел, также не существует универсального алгоритма , способного определить, имеет ли то или иное диофантово уравнение решение. Эта работа не только помогает точнее понять, что мы можем — а что не можем — узнать, но и дает новый уровень контроля над одним из важнейших объектов математики.

Расширение за пределы целых чисел

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

Если у нас есть числа 1 и −1, мы можем складывать их с разными коэффициентами и получать все остальные целые числа. Но представим, что исходный набор чисел другой — например, 1, −1 и √2. Комбинируя их различными способами, получаем новую числовую систему, которую и называют «кольцом целых» (хотя она и не обязательно состоит исключительно из целых чисел). Аналогичным образом можно построить кольцо целых, в которое войдут, скажем, мнимая единица i или кубический корень из 2. И возникает вопрос: существует ли алгоритм, который способен однозначно определить, имеет ли произвольное диофантово уравнение решения в таком кольце целых?

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

Предполагалось, что удастся повторить «план атаки», примененный в исходном доказательстве для целых чисел.

В общих чертах доказательства «неразрешимости» имеют общий рецепт: они показывают, что изучаемая задача эквивалентна знаменитой в компьютерных науках «задаче остановки» (halting problem). Эта задача формулируется так: если у нас есть абстрактная вычислительная машина (машина Тьюринга) и некоторая программа (входные данные), то сможет ли машина определить, остановится программа когда-нибудь или будет работать вечно? Известно, что алгоритма, который решал бы эту задачу для любой машины Тьюринга, не существует.

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

Иными словами, другие диофантовы уравнения могут кодировать и другие виды вычислительных процессов.

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

Кроме того, было достигнуто элегантное соответствие: если программа (машина Тьюринга) останавливалась на определенном входе, то у сопоставленного ей диофантова уравнения оказывалось целочисленное решение. Если программа зацикливалась навечно — тогда решения не было. Но это значит, что десятая проблема Гильберта фактически «закодировала» задачу остановки. Если бы существовал алгоритм, который однозначно классифицирует все диофантовы уравнения по признаку наличия целочисленных решений, он автоматически позволил бы решать и задачу остановки для любой программы.

Иными словами, десятая проблема Гильберта неразрешима.

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

Проблема «засорения» уравнений

Выстроенная аналогия между диофантовыми уравнениями и машинами Тьюринга нарушается, когда мы разрешаем уравнениям иметь решения, выходящие за пределы обычных целых чисел. Например, рассмотрим снова y = x². Если в кольцо целых входит √2, появляются новые решения, например x = √2, y = 2. Такое уравнение уже не соответствует задаче «сгенерировать все квадраты целых чисел» — оно кодирует что-то другое. И в более общем смысле, диофантовы уравнения теряют «правильную» связь с задачей остановки.

Однако в 1988 году аспирант Нью-Йоркского университета Саша Шлапентокх начал размышлять, как обойти это затруднение. К 2000 году он и другие ученые выработали стратегию. Например, можно «усилить» уравнение y = x² добавочными членами таким образом, чтобы x неизбежно оставался целым числом даже в расширенных кольцах. Тогда возвращается возможность кодировать в уравнениях машину Тьюринга. Если это удастся сделать для любых уравнений, то, по сути, мы «восстановим» задачу остановки — и докажем неразрешимость.

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

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

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

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

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

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

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

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

Летом 2024 года, занимаясь другой задачей, где тоже требовался квадратичный твист, Койманс однажды ночью не мог уснуть — мысли снова вернулись к десятой проблеме Гильберта.

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

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

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

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

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

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

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

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