Введение

О разрешимости диофантовых уравнений
Десятая проблема Гильберта – десятая в списке математических проблем, сформулированных немецким математиком Давидом Гильбертом в 1900 году. Она заключается в создании общего алгоритма, который для любого заданного диофантового уравнения (полиномиального уравнения с целочисленными коэффициентами и конечным числом неизвестных) определяет, имеет ли уравнение решение, в котором все неизвестные принимают целые значения. Например, диофантово уравнение имеет целое решение: в то же время, диофантово уравнение решений в целых числах не имеет. Десятая проблема Гильберта решена, и ответ отрицательный: такого общего алгоритма не существует. Этот результат был получен в результате совместной работы Мартина Дэвиса, Юрия Матиясевича, Хилари Путнэма и Джулии Робинсон, продолжавшейся 21 год, причём Матиясевич завершил доказательство теоремы в 1970 году. Теорема известна как теорема Матиясевича или теорема MRDP (аббревиатура, образованная из фамилий четырёх основных участников её решения). Если все коэффициенты и переменные ограничены положительными целыми числами, то связанная задача проверки тождества полиномов становится разрешимой (без использования возведения в степень) вариацией задачи Тарского по алгебре школьного курса, иногда обозначаемой как.

Дальнейшие результаты

Можно говорить о степени диофантового множества как о наименьшей степени многочлена в уравнении, определяющем это множество. Аналогичным образом, размерность такого множества можно назвать наименьшим числом неизвестных в определяющем уравнении. В силу существования универсального диофантового уравнения, очевидно, что существуют абсолютные верхние границы для обеих этих величин, и определение этих границ вызывало большой интерес. Еще в 1920-х годах Торальф Сколем показал, что любое диофантово уравнение эквивалентно уравнению степени 4 или меньше. Его прием заключался во введении новых неизвестных посредством уравнений, приравнивающих их к квадрату неизвестного или произведению двух неизвестных. Повторение этого процесса приводит к системе уравнений второй степени, а затем, путем суммирования квадратов, получается уравнение 4-й степени. Таким образом, каждое диофантово множество тривиально имеет степень 4 или меньше. Неизвестно, является ли этот результат оптимальным. Джулия Робинсон и Юрий Матиясевич показали, что размерность каждого диофантового множества не превышает 13. Позже Матиясевич уточнил их методы, показав, что достаточно 9 неизвестных. Хотя вполне возможно, что этот результат не является оптимальным, дальнейшего прогресса достигнуто не было. Следовательно, в частности, не существует алгоритма для проверки диофантовых уравнений с 9 или менее неизвестными на разрешимость в натуральных числах. Для случая рациональных целочисленных решений (как первоначально сформулировал Гильберт), прием с четырьмя квадратами показывает, что не существует алгоритма для уравнений с не более чем 36 неизвестными. Однако Чжи Вэй Сун показал, что задача для целых чисел неразрешима даже для уравнений с не более чем 11 неизвестными. Мартин Дэвис изучал алгоритмические вопросы, связанные с числом решений диофантового уравнения. Десятая проблема Гильберта спрашивает, равно ли это число 0. Пусть и пусть – собственное непустое подмножество. Дэвис доказал, что не существует алгоритма для проверки данного диофантового уравнения, чтобы определить, является ли число его решений элементом этого множества. Таким образом, не существует алгоритма для определения того, является ли число решений диофантового уравнения конечным, нечетным, полным квадратом, простым и т. д. Доказательство теоремы MRDP было формализовано в Coq.

Расширения десятой задачи Гильберта

Хотя Гильберт сформулировал задачу для рациональных целых чисел, её можно задать и для многих колец (в частности, для любого кольца, число элементов которого счетно). Очевидными примерами служат кольца целых чисел алгебраических числовых полей, а также рациональные числа. Десятой проблеме Гильберта для колец целых чисел алгебраических числовых полей посвящено множество работ. Основываясь на более ранних работах Яна Денефа и Леонарда Липшица и используя теорию полей классов, Гарольд Н. Шапиро и Александра Шлапенток доказали:
Десятая проблема Гильберта неразрешима для кольца целых чисел любого алгебраического числового поля, группа Галуа которого над рациональными числами абелева. Шлапенток и Танасес Фидес (независимо друг от друга) получили тот же результат для алгебраических числовых полей, допускающих ровно одну пару комплексно сопряженных вложений. Проблема для кольца целых чисел алгебраических числовых полей, не охваченных вышеуказанными результатами, остаётся открытой. Также, несмотря на значительный интерес, проблема для уравнений над рациональными числами остаётся нерешённой. Барри Мазур предположил, что для любого многообразия над рациональными числами топологическое замыкание над действительными числами множества решений имеет лишь конечное число компонент. Эта гипотеза влечёт за собой, что целые числа не являются диофантовыми над рациональными, и, следовательно, если эта гипотеза верна, отрицательный ответ на десятую проблему Гильберта потребует подхода, отличного от используемого для других колец.