Десятая проблема Гильберта

До 1940-х годов исследования по десятой проблеме велись в направлении поиска требуемого алгоритма хотя бы для некоторых классов диофантовых уравнений. Через несколько лет после доклада Гильберта, в 1908 году, Аксель Туэ показал, что уравнение Туэ для двух неизвестных не может иметь бесконечно много целочисленных решений[15]. В 1938 году Туральф Скулем опубликовал метод исследования диофантовых уравнений вида ${\displaystyle P(x_{1},x_{2},\ldots ,x_{n})=0,}$ где ${\displaystyle P}$ — неполная разложимая форма (неприводимый многочлен, разлагающийся в расширении поля рациональных чисел на произведение ${\displaystyle m}$ линейных множителей, ${\displaystyle m>n}$), удовлетворяющая некоторым условиям[16]. Несмотря на результат Туэ, даже уравнения с двумя неизвестными не поддавались никаким усилиям математиков (алгоритм для решения уравнений с одним неизвестным следует из теоремы Безу).

В середине 1930-х годов формализуется понятие алгоритма, а также появляются первые примеры алгоритмически неразрешимых множеств в математической логике. Важным моментом стало доказательство Андреем Марковым и Эмилем Постом (независимо друг от друга) неразрешимости задачи Туэ в 1947 году[17][18]. Это было первое доказательство неразрешимости алгебраической задачи. Оно, а также трудности, с которыми столкнулись исследователи диофантовых уравнений, вызвали предположение, что требуемого Гильбертом алгоритма не существует. Чуть ранее, в 1944 году, Эмиль Пост в одной из своих работ уже писал, что десятая проблема «молит о доказательстве неразрешимости» (англ. «begs for an unsolvability proof»)[19].

Слова Поста вдохновили студента Мартина Дэвиса на поиск доказательства неразрешимости десятой проблемы. Дэвис перешёл от её формулировки в целых числах к более естественной для теории алгоритмов формулировке в натуральных числах[20]. Это две разные задачи, однако каждая из них сводится к другой. В 1953 году он опубликовал работу, в которой наметил путь решения десятой проблемы в натуральных числах[21].

Дэвис, наряду с классическими диофантовыми уравнениями рассмотрел их параметрическую версию:

${\displaystyle P(a_{1},\ldots ,a_{n},x_{1},\ldots ,x_{m})=0,}$

где многочлен ${\displaystyle P}$ с целыми коэффициентами можно разделить на две части — параметры ${\displaystyle a_{1},\ldots ,a_{n}}$ и переменные ${\displaystyle x_{1},\ldots ,x_{m}.}$ При одном наборе значений параметров уравнение может иметь решение, при другом решений может не существовать. Дэвис выделил множество ${\displaystyle M}$, которое содержит все наборы значений параметров (${\displaystyle n}$-ки), при которых уравнение имеет решение:

${\displaystyle \{a_{1},\ldots ,a_{n}\}\in M\Longleftrightarrow \exists x_{1},\ldots ,x_{m}\colon P(a_{1},\ldots ,a_{n},x_{1},\ldots ,x_{m})=0.}$

Такую запись он назвал диофантовым представлением множества, а само множество также назвал диофантовым. Для доказательства неразрешимости десятой проблемы нужно было лишь показать диофантовость любого перечислимого множества, то есть показать возможность построения уравнения, которое имело бы натуральные корни ${\displaystyle x_{1},\ldots ,x_{m}}$ только при всех ${\displaystyle \{a_{1},\ldots ,a_{n}\}}$, принадлежащих этому перечислимому множеству: поскольку среди перечислимых множеств содержатся неразрешимые, то, взяв неразрешимое множество ${\displaystyle M}$ за основу, невозможно было бы получить общий метод, который бы по ${\displaystyle n}$-ке определял, имеет ли на этом наборе уравнение натуральные корни. Всё это привело Дэвиса к следующей гипотезе:

Дэвис также сделал первый шаг — доказал, что любое перечислимое множество ${\displaystyle M}$ можно представить в виде:

${\displaystyle \{a_{1},\ldots ,a_{n}\}\in M\Longleftrightarrow \exists z\forall y<z\exists x_{1},\ldots ,x_{m}\colon P(a_{1},\ldots ,a_{n},x_{1},\ldots ,x_{m},y,z)=0.}$

Это представление получило название «нормальная форма Дэвиса». Доказать свою гипотезу, избавившись от квантора всеобщности, ему на тот момент не удалось.

Независимо от Дэвиса над десятой проблемой в те же года начала работать Джулия Робинсон. Первоначально она пыталась доказать гипотезу Альфреда Тарского о том, что множество всех степеней двойки не диофантово, но успеха не достигла[22]. После этого Робинсон перешла к исследованию вопроса о том, является ли диофантовым множество, состоящее из троек ${\displaystyle \{a,b,c=a^{b}\}}$. Найти диофантово представление для операции возведения в степень ей не удалось, но тем не менее в своей работе[23] она показала достаточное условие для его существования:

${\displaystyle \{u,v\}\in R\Longleftrightarrow \exists x_{1},\ldots ,x_{m}\colon P(u,v,x_{1},\ldots ,x_{m})=0,}$

причём:

• если ${\displaystyle \{u,v\}\in R}$, то ${\displaystyle u<v^{v},}$
• для любого ${\displaystyle k}$ существуют ${\displaystyle u}$ и ${\displaystyle v}$ такие, что ${\displaystyle \{u,v\}\in R}$ и ${\displaystyle u>v^{k}.}$

Связь между ${\displaystyle u}$ и ${\displaystyle v}$ Робинсон назвала «зависимостью экспоненциального роста», однако позднее эту зависимость стали называть в её честь — «зависимость Робинсон», «предикаты Робинсон» или просто «J. R.».

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

${\displaystyle E_{L}(x_{1},\ldots ,x_{m})=E_{R}(x_{1},\ldots ,x_{m}),}$

где ${\displaystyle E_{L}}$ и ${\displaystyle E_{R}}$ — экспоненциальные многочлены, то есть выражения, полученные из переменных и рациональных чисел с применением операций сложения, умножения и возведения в степень, а также показали диофантово представление для таких уравнений. Однако доказательство Дэвиса и Патнема содержало пробел — они использовали гипотезу о существовании произвольно длинных арифметических прогрессий, состоящих только из простых чисел (теорема Грина — Тао), которая была доказана только в 2004 году.

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

${\displaystyle \{a_{1},\ldots ,a_{n}\}\in M\Longleftrightarrow \exists x_{1},\ldots ,x_{m}\colon E_{L}(a_{1},\ldots ,a_{n},x_{1},\ldots ,x_{m})=E_{R}(a_{1},\ldots ,a_{n},x_{1},\ldots ,x_{m}).}$

Одним из следствий работы стала возможность сведения любого показательно-диофантова уравнения к экспоненциально-диофантову уравнению с фиксированным числом переменных (как минимум, с тремя[26]).

Чтобы перенести результат Дэвиса, Патнема и Робинсон на «обычные» диофантовы уравнения, нужно было доказать, что множество, состоящее из троек ${\displaystyle \{a,b,c=a^{b}\}}$, является диофантовым. Тогда стало бы возможным ценой введения дополнительных неизвестных перевести экспоненциально-диофантово представление в диофантово представление:

${\displaystyle c=a^{b}\Longleftrightarrow \exists x_{1},\ldots ,x_{m}\colon P(a,b,c,x_{1},\ldots ,x_{m})=0.}$

Другими словами, для полного доказательства гипотезы Дэвиса необходимо было лишь доказать один её частный случай, а ещё точнее — доказать гипотезу Робинсон (найти многочлен ${\displaystyle P(u,v,x_{1},\ldots ,x_{m})}$, удовлетворяющий всем условиям).

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