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

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

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

В докладе Гильберта постановка десятой задачи самая короткая из всех:

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

Оригинальный текст (нем.)

Eine Diophantische Gleichung mit irgend welchen Unbekannten und mit ganzen rationalen Zahlencoefficienten sei vorgelegt: man soll ein Verfahren angeben, nach welchem sich mittelst einer endlichen Anzahl von Operationen entscheiden läßt, ob die Gleichung in ganzen rationalen Zahlen lösbar ist.

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

$P(x_{1},x_{2},\ldots ,x_{n})=0,$

где $P$ — многочлен с целыми коэффициентами и целыми показателями степеней. Степень уравнения равна степени многочлена $P$.

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

Предпосылки

Целочисленное решение алгебраических уравнений интересовало математиков ещё с античных времён. Например, много внимания уделялось уравнению $x^{2}+y^{2}=z^{2}$: если его решением был набор из натуральных чисел $x_{0},y_{0},z_{0}$, то по теореме, обратной к теореме Пифагора, из отрезков длиной $x_{0},y_{0},z_{0}$ можно было получить прямоугольный треугольник. Евклид привёл формулы для нахождения всех целочисленных решений этого уравнения. Некоторые виды уравнений второй степени и их системы рассмотрел Диофант Александрийский, его работы позднее использовали Леонард Эйлер, Пьер Ферма, Жозеф Луи Лагранж, Карл Фридрих Гаусс и другие математики, занимавшиеся теорией чисел. В частности, Ферма выдвинул свою знаменитую гипотезу. К 1768 году Лагранж полностью исследовал вопрос о целочисленных решениях любого уравнения второй степени с двумя неизвестными.

В течение XIX века многие математики, решая Великую теорему Ферма, предпринимали попытки исследования диофантовых уравнений степени выше второй. Тем не менее проблема решения таких уравнений оставалась открытой: какого-либо общего метода получено не было, находились лишь специальные приёмы для уравнений определённых типов. Скорее всего, Гильберт подозревал, что дальнейшее исследование этой области привело бы к созданию подробных и глубоких теорий, не ограниченных диофантовыми уравнениями, и это побудило его внести задачу в список для своего доклада.

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

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

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

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

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

Слова Поста вдохновили студента Мартина Дэвиса на поиск доказательства неразрешимости десятой проблемы. Дэвис перешёл от её формулировки в целых числах к более естественной для теории алгоритмов формулировке в натуральных числах. Это две разные задачи, однако каждая из них сводится к другой. В 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$-ки), при которых уравнение имеет решение:

$\{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.$

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

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

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

$\{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.$

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

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

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

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

причём:

• если $\{u,v\}\in R$, то $u<v^{v},$
• для любого $k$ существуют $u$ и $v$ такие, что $\{u,v\}\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 году этот пробел смогла восполнить Джулия Робинсон. В их совместной работе было получено экспоненциально-диофантово представление для любого перечислимого множества:

$\{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}).$

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

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

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

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

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

Влияние

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

Литература

• Ю. В. Матиясевич. Десятая проблема Гильберта. — М.: Наука, 1993. — ISBN 502014326X. (недоступная ссылка)
• Ф. П. Варпаховский, А. Н. Колмогоров. О решении десятой проблемы Гильберта // Квант. — 1970. — № 7. — С. 38—44.
• Ю. И. Хмелевский. К десятой проблеме Гильберта // Проблемы Гильберта / под ред. П. С. Александрова. — М.: Наука, 1969. — С. 141—153. — 240 с. — 10 700 экз. Архивная копия от 17 октября 2011 на Wayback Machine
• К. М. Подниекс. Глава 4. Десятая проблема Гильберта // Вокруг теоремы Геделя. — Рига: Зинатне, 1992. — 191 с.
• Yu. V. Matiyasevich. Hilbert’s Tenth Problem: Diophantine Equations in Twentieth Century // Mathematical Events of the Twentieth Century = Математические события XX века / ed. A. A. Bolibruch, Yu. S. Osipov, Ya. G. Sinai. — Berlin: Springer, 2006. — С. 185—214. — 545 с. — ISBN 3-540-23235-4. (англ.)
• Hilbert’s tenth problem: relations with arithmetic and algebraic geometry. Workshop on Hilbert’s tenth problem: relations with arithmetic and algebraic geometry, november 2—5, 1999, Ghent University, Belgium / ed. Jan Denef, Leonard Lipshitz, Thanases Pheidas, Jan Van Geel. — Contemporary Mathematics. — 2000. — Т. 270. — 367 с. — ISBN 0-8218-2622-0. (англ.)

Ссылки

• Maxim Vsemirnov, Yuri Matiyasevich. Hilbert’s Tenth Problem page (англ.). Дата обращения: 27 августа 2009. Архивировано 10 апреля 2012 года.
• 10-я проблема Гильберта: история математического открытия  (неопр.). Дата обращения: 27 августа 2009. Архивировано из оригинала 16 декабря 2010 года.
• Yuri Matiyasevich. Hilbert’s Tenth Problem: What can we do with Diophantine equations (англ.). Дата обращения: 27 августа 2009. Архивировано 10 апреля 2012 года.
• Zhi-Wei Sun. On Hilbert’s tenth problem and related topics (англ.) (14 апреля 2000). Дата обращения: 29 августа 2009. Архивировано 10 апреля 2012 года.
• Panu Raatikainen. The problem of the simplest diophantine representation (англ.). Дата обращения: 29 августа 2009. Архивировано 10 апреля 2012 года.