Неразрешимость проблемы существования решения диофантова уравнения в целых числах

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

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

Содержание

Диофантовы уравнения [ править ]

Ниже приведены примеры наиболее известных частных случаев диофантовых уравнений:

• [math]x^n + y^n = z^n[/math] ,

• при [math]n=2[/math] решениями этого уравнения (обобщенного уравнения Пифагора) являются пифагоровы тройки,
• согласно Великой теореме Ферма это уравнение не имеет ненулевых целых решений при [math]n\gt 2[/math] .

• уравнение Пелля;

• уравнение Каталана:

• уравнение Туэ:

Диофант искал решение этих уравнений в рациональных числах, Гильберт спрашивал про решение диофантовых уравнений в целых числах.

В современной терминологии десятая проблема Гильберта является примером массовой проблемы [1] . Массовая проблема состоит из счетного количества вопросов на каждый из которых нужно дать ответ — да или нет. В данном случае эти вопросы параметризуются диофантовыми уравнениями и нужно сказать: да, данное диофантово уравнение имеет решение или нет, данное уравнение не имеет решения. И суть массовой проблемы состоит в том, что нужно найти единый универсальный метод, который позволял бы ответить на любой из этих вопросов. Среди двадцати трех «Математических проблем» Гильберта десятая является единственной массовой проблемой и она может рассматриваться, как проблема информатики. Сегодня мы знаем, что десятая проблема Гильберта решения не имеет. Это означает, что она не разрешима, как массовая проблема.

Теорема о неразрешимости десятой проблемы Гильберта [ править ]

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

Аббревиатура в названии последней теоремы образована из первых букв фамилий математиков Мартина Девиса (англ. Martin Davis), Хилари Патнэма (англ. Hilary Putnam), Джулии Робинсон (англ. Julia Robinson) и Юрия Матиясевича. Подробное доказательство неразрешимости десятой проблемы Гильберта можно прочитать здесь [3] [4] .

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

Пусть дано множество [math]M[/math] натуральных чисел и нужно найти алгоритм, который по каждому натуральному [math]n[/math] определяет, принадлежит это [math]n[/math] множеству [math]M[/math] или нет. В соответствии с тезисом Черча, такой алгоритм существует тогда и только тогда, когда множество [math]M[/math] разрешимо. Для отрицательного решения десятой проблемы Гильберта достаточно доказать диофантовость каждого перечислимого множества, то есть по каждому перечислимому множеству [math]M[/math] уметь строить такое диофантово уравнение, [math]P(y,x_1\ldots x_k)=0[/math] , которое имело бы натуральные решения [math]x_1\ldots x_k[/math] для всех [math]y[/math] , принадлежащих [math]M[/math] и только для таких [math]y[/math] . Тогда, взяв в качестве [math]M[/math] перечислимое, но неразрешимое множество, можно было бы получить, что для соответствующего уравнения [math]P(y,x_1\ldots x_k)=0[/math] нет общего алгоритма, который по каждому натуральному [math]y[/math] давал бы ответ на вопрос о существовании у этого уравнения натуральных решений. Если бы этот алгоритм существовал, то можно было бы за конечное число шагов узнать, имеет ли уравнение [math]P(0,x_1\ldots x_k)=0[/math] решение, то есть принадлежит ли число [math]0[/math] множеству [math]M[/math] , имеет ли уравнение [math]P(1,x_1\ldots x_k)=0[/math] решение и так далее. Получилось бы, что существует алгоритм, который по каждому натуральному [math]y[/math] за конечное число шагов определяет, принадлежит [math]y[/math] множеству [math]M[/math] или нет. Тогда, в соответствии с тезисом Черча, множество [math]M[/math] было бы разрешимым вопреки выбору этого множества.

Этапы доказательства DPRM-теоремы [ править ]

М. Дэвис перешёл от формулировки десятой проблемы Гильберта в целых числах к естественной для теории алгоритмов формулировке в целых неотрицательных числах. Для конкретного диофантова уравнения задача о нахождении целочисленных решений и задача о нахождении решений в целых неотрицательных числах — разные задачи. Однако если мы интересуемся сразу всеми уравнениями (как, например, в 10-й проблеме Гильберта), то эти две задачи совпадают. Действительно, если рассмотреть систему уравнений [math](2)[/math]

то станет понятно, что:

• любое решение системы [math](2)[/math] в произвольных целых числах содержит решение уравнения [math](1)[/math] в неотрицательных целых числах;

• для любого решения уравнения [math](1)[/math] в неотрицательных целых числах [math]x_1,x_2,\ldots , x_n[/math] найдутся целочисленные значения [math]y_,\ldots , y_[/math] , дающие решение системы [math](2)[/math] , так как, согласно известной теореме Лагранжа, каждое неотрицательное целое число представимо в виде суммы квадратов четырёх целых чисел.

Система уравнений [math](2)[/math] может быть свёрнута в одно уравнение : [math]E(x_1, x_2, \ldots , x_n, y_, \ldots , y_)[/math] , разрешимое в целых числах тогда и только тогда, когда исходное уравнение [math](1)[/math] разрешимо в неотрицательных целых числах.

Наряду с отдельными диофантовыми уравнениями, Дэвис рассмотрел семейства диофантовых уравнений вида: [math]P(a_1, a_2, \ldots , a_m, x_1, x_2, \ldots , x_n)=0[/math] , где [math]P[/math] – многочлен с целыми коэффициентами, [math]a_1, a_2, \ldots , a_m\in\mathbb[/math] — параметры, [math]x_1, x_2,\ldots , x_n\in\mathbb[/math] — переменные. Каждое такое семейство определяет некоторое множество [math]M[/math] тех значений параметров, при которых уравнение разрешимо относительно переменных [math]x_1, x_2,\ldots , x_n[/math]  :

[math]\left \langle a_1, a_2, \ldots , a_m\right \rangle\in\mathbb\Leftrightarrow x_1, x_2,\ldots , x_n\[/math]

Такие множества называются диофантовыми.

Исследования Мартина Дэвиса, направленные на доказательство неразрешимости десятой проблемы Гильберта, привели его к постановке задачи, когда описано некоторое множество и требуется узнать, является ли оно диофантовым. В простейших случаях диофантовость множества очевидна — ясно, например, что диофантовым является множество всех положительных нечетных чисел. Однако совсем нелегко ответить на такие вопросы, как: «диофантово ли множество всех степеней числа [math]2[/math] ?», «диофантово ли множество всех простых чисел?», «диофантово ли множество всех совершенных чисел?» С первого взгляда кажется, что на эти вопросы следует дать отрицательный ответ. Тем не менее все эти множества являются диофантовыми. Приведем примеры диофантовых множеств:

• множество всех полных квадратов, представлено уравнением [math]a-x^2=0[/math] ;
• множество всех составных чисел, представлено уравнением [math]a-(x_1+2)(x_2+2)=0[/math] ;
• множество всех нестепеней числа [math]2[/math] , представлено уравнеием [math]a-(2x_1+3)x_2=0[/math] .

Для доказательства неразрешимости десятой проблемы Гильберта нужно было лишь показать диофантовость любого перечислимого множества, то есть нужно показать возможность построения уравнения, которое имело бы натуральные корни [math]x_1,x_2,\ldots , x_n[/math] только при всех [math]\left \langle a_1, a_2, \ldots , a_m\right \rangle[/math] , принадлежащих этому перечислимому множеству. Исходя из этого, Дэвис сформулировал следующую гипотезу:

Гипотеза (Мартина Дэвиса): Понятия диофантового и перечислимого множества совпадают. Это значит, что множество диофантово тогда и только тогда, когда оно перечислимо.

Доказать гипотезу Дэвису не удалось, но он получил близкий к доказательству результат, показав [5] , что любое перечислимое множество можно представить в виде, названном нормальной формой Дэвиса:

[math]\left \langle a_1, a_2, \ldots , a_m\right \rangle\in\mathbb\Leftrightarrow \exists z \quad \forall y \lt z \quad \exists x_1, x_2,\ldots , x_n\[/math]

Джулия Робинсон исследовала вопрос о том, является ли диофантовым множество, состоящее из троек :

[math]\left \langle a, b, c= a^b\right \rangle[/math]

Найти диофантово представление для операции возведения в степень ей не удалось, но она нашла достаточное условие для его существования:

[math]\left \langle a, b \right \rangle\in\mathbb\Leftrightarrow \exists x_1, x_2,\ldots , x_n\[/math]

Его определяет отношение [math]J(a,b)[/math] со следующими свойствами:

• для любых [math]a[/math] и [math]b[/math] из [math]J(a,b)[/math] следует, что [math]a \lt b^b[/math] ;
• для любого [math]k[/math] существуют [math]a[/math] и [math]b[/math] , удовлетворяющие [math]J(a,b)[/math] и такие, что [math]a \gt b^k[/math] .

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

В 1958 году М. Дэвис и Х. Патнем опубликовали работу, в которой они рассмотрели класс так называемых экспоненциально-диофантовых уравнений.Такие уравнения имеют вид:

[math]E_1(x_1,x_2,\ldots ,x_n) = E_2(x_1,x_2,\ldots ,x_n)[/math] ,

где [math]E_1[/math] и [math]E_2[/math] — выражения, построенные из [math]x_1, x_2,\ldots , x_m[/math] и конкретных натуральных чисел с помощью сложения, умножения и возведения в степень.

В 1961 году в совместной работе Робинсон, Дэвиса и Патмена [6] было получено экспоненциально - диофантово представление для любого перечислимого множества:

[math]\left \langle a_1, a_2, \ldots , a_m\right \rangle\in\mathbb\Leftrightarrow \exists x_1, x_2,\ldots , x_n\[/math]

Одним из следствий работы стала возможность сведения любого показательно-диофантова уравнения к экспоненциально-диофантову уравнению с фиксированным числом переменных. Чтобы перенести результат Дэвиса, Патнема и Робинсон на обычные диофантовы уравнения, нужно было доказать, что множество, состоящее из троек [math]\left \langle a, b, c= a^b\right \rangle[/math] , является диофантовым. Тогда стало бы возможным ценой введения дополнительных неизвестных перевести экпоненциально-диофантово представление в диофантово представление: [math]a, b, c= a^b\Leftrightarrow \exists x_1,x_2,\ldots ,x_n \left \ < P(a, b,c, x_1, x_2, \ldots , x_n)=0\right \>[/math]

Джулия Робинсон показала, что для этого достаточно построить конкретное уравнение

[math]P(a, b, x_1, x_2, \ldots , x_n)=0 [/math] ,

• недопускающее решение с [math]a\gt b^b[/math] ;
• для каждого [math]k[/math] имеющее решение с [math]a\gt b^k[/math] .

Такого рода уравнение удалось построить Ю.В. Матеясевичу в 1970 году. Обратившись к рассмотрению последовательности Фибоначчи, Матиясевич заметил, что если за [math]b[/math] взять половину номера четного члена последовательности Фибоначчи, а за [math]a[/math] — сам член, то неравенство [math]a\gt b^b[/math] будет всегда неверно; для любого [math]k[/math] можно найти такой четный член последовательности, что неравенство [math]a\gt b^k[/math] будет верно. Это обстоятельство иллюстрируется приведенной ниже таблицей (в ней выделены те клетки, в которых числа [math]b^k[/math] оказываются меньше соответствующих чисел [math]a[/math] ).

Номер члена последовательности Фибоначчи 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Член последовательности Фибоначчи [math]a[/math] [math]0[/math] [math]1[/math] [math]1[/math] [math]2[/math] [math]3[/math] [math]5[/math] [math]8[/math] [math]13[/math] [math]21[/math] [math]34[/math] [math]55[/math] [math]89[/math] [math]144[/math] [math]233[/math] [math]377[/math] Половина номера четного члена последовательности [math]b[/math] [math]0[/math] [math]1[/math] [math]2[/math] [math]3[/math] [math]4[/math] [math]5[/math] [math]6[/math] [math]7[/math] [math]b^b[/math] [math]1[/math] [math]1[/math] [math]4[/math] [math]27[/math] [math]64[/math] [math]3125[/math] [math]47256[/math] [math]823649[/math] [math]b^0[/math] [math]1[/math] [math]1[/math] [math]1[/math] [math]1[/math] [math]1[/math] [math]1[/math] [math]1[/math] [math]1[/math] [math]b^1[/math] [math]0[/math] [math]1[/math] [math]2[/math] [math]3[/math] [math]4[/math] [math]5[/math] [math]6[/math] [math]7[/math] [math]b^2[/math] [math]0[/math] [math]1[/math] [math]4[/math] [math]9[/math] [math]16[/math] [math]25[/math] [math]36[/math] [math]49[/math] [math]b^3[/math] [math]0[/math] [math]1[/math] [math]8[/math] [math]27[/math] [math]64[/math] [math]125[/math] [math]216[/math] [math]343[/math]

Далее Матеясевич рассмотрел последовательность, состоящую из четных членов первоначальной последовательности. Оставалось построить уравнение, такое, что [math]P(a,b,x_1,\ldots ,x_k)=0[/math] , которое имело бы натуральное решение тогда и только тогда, когда [math]b=\varphi_a[/math] , далее сослаться на описанный выше результат Джулии Робинсон. Для этого достаточно было построить систему диофантовых уравнений [math]P_1=0,\ldots,P_n=0[/math] в переменных [math]a,b,x_1,\ldots ,x_k[/math] , имеющую решение тогда и только тогда, когда [math]b=\varphi_a[/math] . Такая система имеет в точнсти те же решения, что и единственное уравнение [math]P_1^2+\ldots +P_n^2=0[/math] . Матиясевич получил требуемую систему в виде:

[math]3) \quad l^2-lk-k^2=1[/math]

[math]5) \quad l^2c=g[/math]

[math]6) \quad ld=r-2[/math]

[math]7) \quad (2h+g)e=r-3[/math]

[math]8) \quad x^2-rxy+y^2=1[/math]

[math]9) \quad lp=x-b[/math]

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

В результате совместной работы Дэвиса, Робинсон, Патнема, Матиясевича было доказано, что по заданию перечислимого множества в любой стандартной форме можно построить его диофантово представление:

• построить арифметическую формулу со многими ограниченными кванторами общности;
• преобразовать эту формулу в нормальную форму Дейвиса с одним ограниченным квантором общности;

• устранить этот ограниченный квантор общности ценой перехода к экспоненциально-диофантовым уравнениям;
• устранить возведение в степень.

Таким образом, была доказана правильность гипотезы Мартина Дэвиса, которая стала называться DPRM-теоремой. Из этой теоремы следует, что десятая проблема Гиль­берта является неразрешимой.