Processing math: 20%

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

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

Постановказадачи


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

 Формально речь идёт о целочисленном решении уравнений вида

P(x1,x2,,xn)=0,
 где P — многочлен с целыми коэффициентами и целыми показателямистепеней. Степень уравнения равна степени многочлена P.
 Из всех 23 задач она единственная является проблемой разрешимости.По-видимому, Гильберт считал, что искомый метод существует и рано илипоздно будет найден. Вопроса о том, что такого метода может в принципене быть, во времена Гильберта не стояло.

Предпосылки


 Целочисленное решение алгебраических уравнений интересовало математиковещё с античных времён. Например, много внимания уделялось уравнениюx2+y2=z2: если его решением был набор из натуральных чиселx0,y0,z0, то по теореме, обратной к теореме Пифагора, из отрезковдлиной x0,y0,z0 можно было получить прямоугольный треугольник.Евклид привёл формулы для нахождения всех целочисленных решений этогоуравнения. Некоторые виды уравнений второй степени и их системырассмотрел Диофант Александрийский, его работы позднее использовалиЛеонард Эйлер, Пьер Ферма, Жозеф Луи Лагранж, Карл Фридрих Гаусс идругие математики, занимавшиеся теорией чисел. В частности, Фермавыдвинул свою знаменитую гипотезу. К 1768 году Лагранж полностьюисследовал вопрос о целочисленных решениях любого уравнения второйстепени с двумя неизвестными.
 В течение XIX века многие математики, решая Великую теорему Ферма,предпринимали попытки исследования диофантовых уравнений степени вышевторой. Тем не менее, проблема решения таких уравнений оставаласьоткрытой: какого-либо общего метода получено не было, находились лишьспециальные приёмы для уравнений определённых типов. Скорее всего,Гильберт подозревал, что дальнейшее исследование этой области привело бык созданию подробных и глубоких теорий, не ограниченных диофантовымиуравнениями, и это побудило его внести задачу в список для своегодоклада.

Историярешения


Поискиалгоритма


 До 1940-х годов исследования по десятой проблеме велись в направлениипоиска требуемого алгоритма хотя бы для некоторых классов диофантовыхуравнений. Через несколько лет после доклада Гильберта, в 1908 году,Аксель Туэ показал, что уравнение P(x,y)=C, где C — целое число,а P — неприводимый многочлен с одинаковой степенью ()всех членов не может иметь бесконечно много целых решений. В 1938 годуТуральф Скулем опубликовал метод исследования диофантовых уравнений видаP(x_1, x_2, \ldots, x_n) = 0, где P — неполная разложимая форма(неприводимый многочлен, разлагающийся в расширении поля рациональныхчисел на произведение m линейных множителей, m>n), удовлетворяющаянекоторым условиям. Несмотря на результат Туэ, даже уравнения с двумянеизвестными не поддавались никаким усилиям математиков (алгоритм длярешения уравнений с одним неизвестным следует из теоремы Безу).
 В середине 1930-х годов формализуется понятие алгоритма, а такжепоявляются первые примеры алгоритмически неразрешимых множеств вматематической логике. Важным моментом стало доказательство АндреемМарковым и Эмилем Постом (независимо друг от друга) неразрешимостизадачи Туэ в 1947 году. Это было первое доказательство неразрешимостиалгебраической задачи. Оно, а также трудности, с которыми столкнулисьисследователи диофантовых уравнений, вызвали предположение, чтотребуемого Гильбертом алгоритма не существует. Чуть ранее, в 1944 году,Эмиль Пост в одной из своих работ уже писал, что десятая проблема «молито доказательстве неразрешимости» .

ГипотезаДэвиса


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

P (a_1, \ldots, a_n, x_1, \ldots, x_m) = 0,
 где многочлен P с целыми коэффициентами можно разделить на двечасти — параметры a_1, \ldots, a_n и переменные x_1, \ldots, x_m.При одном наборе значений параметров уравнение может иметь решение, придругом решений может не существовать. Дэвис выделил множество M,которое содержит все наборы значений параметров (n-ки), при которыхуравнение имеет решение:

\mathcal {h} a_1, \ldots, a_n \mathcal {i} \in M \Longleftrightarrow \exists x_1, \ldots, x_m \mathcal {f} P(a_1, \ldots, a_n, x_1, \ldots, x_m) = 0\mathcal {g}.
 Такую запись он назвал диофантовым представлением множества, а самомножество также назвал диофантовым. Для доказательства неразрешимостидесятой проблемы нужно было лишь показать диофантовость любогоперечислимого множества, то есть показать возможность построенияуравнения, которое имело бы натуральные корни x_1, \ldots, x_m толькопри всех \mathcal {h}a_1, \ldots, a_n\mathcal {i}, принадлежащих этомуперечислимому множеству: поскольку среди перечислимых множествсодержатся неразрешимые, то, взяв неразрешимое множество M за основу,невозможно было бы получить общий метод, который бы по n-ке определял,имеет ли на этом наборе уравнение натуральные корни. Всё это привелоДэвиса к следующей гипотезе: Дэвис также сделал первый шаг — доказал,что любое перечислимое множество M можно представить в виде:

 $\mathcal {h} a_1, \ldots, a_n \mathcal {i} \in M \Longleftrightarrow \exists z \forall y Это представление получило название «нормальная форма Дэвиса». Доказатьсвою гипотезу, избавившись от квантора всеобщности, ему на тот момент неудалось.

ГипотезаРобинсон


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

\mathcal{h} u, v \mathcal{i} \in R \Longleftrightarrow \exist x_1, \ldots, x_m \mathcal {f} P(u, v, x_1, \ldots, x_m) = 0\mathcal {g},
 причём:

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

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

Объединениеусилий


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

E_L(x_1, \ldots, x_m) = E_R(x_1, \ldots, x_m),
 где E_L и E_R — экспоненциальные многочлены, то есть выражения,полученные из переменных и рациональных чисел с применением операцийсложения, умножения и возведения в степень, а также показали диофантовопредставление для таких уравнений. Однако доказательство Дэвиса иПатнема содержало пробел — они использовали гипотезу о существованиипроизвольно длинных арифметических прогрессий, состоящих только изпростых чисел (теорема Грина — Тао), которая была доказана только в2004 году.
 В 1961 году этот пробел смогла восполнить Джулия Робинсон. В ихсовместной работе было получено экспоненциально-диофантово представлениедля любого перечислимого множества:

\mathcal {h} a_1, \ldots, a_n \mathcal {i} \in M \Longleftrightarrow \exist x_1, \ldots, x_m E_L(a_1, \ldots, a_n, x_1, \ldots, x_m) = E_R(a_1, \ldots, a_n, x_1, \ldots, x_m).
 Одним из следствий работы стала возможность сведения любогопоказательно-диофантова уравнения к экспоненциально-диофантову уравнениюс фиксированным числом переменных (как минимум, с тремя).
 Чтобы перенести результат Дэвиса, Патнема и Робинсон на «обычные»диофантовы уравнения, нужно было доказать, что множество, состоящее изтроек \mathcal {h} a, b, c = a^b\mathcal {i}, является диофантовым.Тогда стало бы возможным ценой введения дополнительных неизвестныхперевести экспоненциально-диофантово представление в диофантовопредставление:

a, b, c = a^b \Longleftrightarrow \exist x_1, \ldots, x_m \mathcal {f} P(a, b, c, x_1, \ldots, x_m) = 0\mathcal {g}.
 Другими словами, для полного доказательства гипотезы Дэвиса необходимобыло лишь доказать один её частный случай, а ещё точнее — доказатьгипотезу Робинсон (найти многочлен P(u, v, x_1, \ldots, x_m),удовлетворяющий всем условиям).
 Несмотря на глубокое изучение двухпараметрических диофантовых уравненийсо времён самого Диофанта, на тот момент не было известно уравнения,выражающего зависимость экспоненциального роста. Попытки егоискусственно сконструировать также потерпели неудачу.

Влияние



  • В 2008 году состоялась премьера часового документального фильма режиссёра Джорджа Чичери «Julia Robinson and Hilbert's Tenth Problem». Фильм посвящён Джулии Робинсон и её вкладу в решение десятой проблемы. Фильм получил отзывы и обзоры от американских математических журналов и сообществ.