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

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

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

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

Пусть задано диофантово уравнение с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах[3]. Оригинальный текст  (нем.)   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[4].

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

$P(x_1, x_2, \ldots, x_n) = 0,$

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

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

Предпосылки

Целочисленное решение алгебраических уравнений интересовало математиков ещё с античных времён. Например, много внимания уделялось уравнению $x^2 + y^2 = z^2$: если его решением был набор из натуральных чисел $x_0, y_0, z_0$, то по теореме, обратной к теореме Пифагора, из отрезков длиной $x_0, y_0, z_0$ можно было получить прямоугольный треугольник^[11]. Евклид привёл формулы для нахождения всех целочисленных решений этого уравнения^[12]. Некоторые виды уравнений второй степени и их системы рассмотрел Диофант Александрийский^[13], его работы позднее использовали Леонард Эйлер, Пьер Ферма, Жозеф Луи Лагранж, Карл Фридрих Гаусс и другие математики, занимавшиеся теорией чисел. В частности, Ферма выдвинул свою знаменитую гипотезу. К 1768 году Лагранж полностью исследовал вопрос о целочисленных решениях любого уравнения второй степени с двумя неизвестными^[14].

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

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

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

До 40-х годов XX века исследования по десятой проблеме велись в направлении поиска требуемого алгоритма хотя бы для некоторых классов диофантовых уравнений. Через несколько лет после доклада Гильберта, в 1908 году, Аксель Туэ показал, что уравнение $P(x,y) = C$, где $C$ — целое число, а $P$ — неприводимый многочлен с одинаковой степенью ($\geqslant 3$) всех членов не может иметь бесконечно много целых решений^[15]. В 1938 году Туральф Сколем (англ.) опубликовал метод исследования диофантовых уравнений вида $P(x_1, x_2, \ldots, x_n) = 0,$ где $P$ — неполная разложимая форма (неприводимый многочлен, разлагающийся в расширении поля рациональных чисел на произведение $m$ линейных множителей, $m>n$), удовлетворяющая некоторым условиям^[16]. Несмотря на результат Туэ, даже уравнения с двумя неизвестными не поддавались никаким усилиям математиков (алгоритм для решения уравнений с одним неизвестным следует из теоремы Безу).

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

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

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

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

$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<z \exists x_1, \ldots, x_m \mathcal {f} P(a_1, \ldots, a_n, x_1, \ldots, x_m, y, z) = 0\mathcal {g}.$

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

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

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

$\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 году Мартин Дэвис и Хилари Патнем публикуют работу^[24], в которой они, опираясь на результат Робинсон, рассмотрели класс экспоненциально-диофантовых уравнений, имеющих вид:

$E_L(x_1, \ldots, x_m) = E_R(x_1, \ldots, x_m),$

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

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

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

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

Чтобы перенести результат Дэвиса, Патнема и Робинсон на «обычные» диофантовы уравнения, нужно было доказать, что множество, состоящее из троек $\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 году состоялась премьера часового документального фильма режиссёра Джорджа Чичери (англ. George Csicsery) «Julia Robinson and Hilbert’s Tenth Problem». Фильм посвящён Джулии Робинсон и её вкладу в решение десятой проблемы^[27]. Фильм получил отзывы и обзоры от американских математических журналов и сообществ^[28][29].

Примечания

1. ↑ Ю. В. Матиясевич Диофантовость перечислимых множеств // Доклады Академии наук СССР. — 1970. — Т. 191. — № 2. — С. 279—282.
2. ↑ Ю. В. Матиясевич Десятая проблема Гильберта. — М.: Наука: Физико-математическая литература, 1993. — 223 с. — (Математическая логика и основания математики; выпуск № 26). — ISBN 502014326X
3. ↑ Перевод доклада Гильберта с немецкого — М. Г. Шестопал и А. В. Дорофеева, опубликован в книге Проблемы Гильберта / под ред. П. С. Александрова. — М.: Наука, 1969. — С. 39. — 240 с. — 10 700 экз.
4. ↑ David Hilbert Vortrag, gehalten auf dem internationalen Mathematiker-Kongreß zu Paris 1900  (нем.). — Текст доклада, прочитанного Гильбертом 8 августа 1900 года на II Международном конгрессе математиков в Париже. Архивировано из первоисточника 8 апреля 2012. Проверено 27 августа 2009.
5. ↑ «Рациональное целое» является синонимом «целое», см. Weisstein, Eric W. Rational Integer (англ.) на сайте Wolfram MathWorld.
6. ↑ В. И. Игошин § 36. Неразрешимые алгоритмические проблемы // Математическая логика и теория алгоритмов. — М.: Академия, 2004. — С. 375. — 448 с. — 5100 экз. — ISBN 5-7695-1363-2
7. ↑ Yuri Matiyasevich Hilbert’s Tenth Problem: What can we do with Diophantine equations  (англ.). Архивировано из первоисточника 10 апреля 2012. Проверено 27 августа 2009.
8. ↑ Об этом свидетельствует также сама формулировка задачи в позитивном ключе: «man soll ein Verfahren angeben» («указать порядок действий», а не, например, «указать, существует ли порядок действий»).
9. ↑ ^{1 2} Ю. И. Хмелевский К десятой проблеме Гильберта // Проблемы Гильберта / под ред. П. С. Александрова. — М.: Наука, 1969. — С. 141—153. — 240 с. — 10 700 экз.
10. ↑ Ф. Варпаховский, А. Колмогоров О решении десятой проблемы Гильберта // Квант. — 1970. — № 7. — С. 38—44.
11. ↑ А. А. Болибрух Десятая проблема Гильберта: диофантовы уравнения // Проблемы Гильберта (100 лет спустя). — М.: МЦНМО, 1999. — 24 с. — (Библиотека «Математическое просвещение», выпуск № 2). — 3000 экз.
12. ↑ Саймон Сингх Приложение 5. Доказательство Евклида существования бесконечного числа пифагоровых троек // Великая теорема Ферма = Fermat’s last theorem / пер. с англ. Ю. А. Данилова. — МЦНМО, 2000.
13. ↑ Диофант Александрийский Арифметика и книга о многоугольных числах / пер. с др.-греч. Ю. Н. Веселовского. — М.: Наука, 1974. — 328 с. — 17 500 экз.
14. ↑ Leonard Eugene Dickson History of the Theory of Numbers. — 1920. — Т. II: Diophantine Analysis.  (англ.)
15. ↑ A. Thue Bemerkungen über gewisse Annäherungsbrüche algebraischer Zahlen // Videnskabs-selskabets Skrifter I Math.-Naturv. Klasse. — 1908. — № 3. — С. 1—34.
16. ↑ Thoralf Skolem Diophantische Gleichungen. — Berlin: Springer, 1938. — 128 p.
17. ↑ Статья Маркова — А. А. Марков Невозможность некоторых алгорифмов в теории ассоциативных систем // Доклады Академии наук СССР. — М., 1947. — В. 7. — Т. 55. — С. 587—590., см. также монографию А. А. Марков Теория алгорифмов // Труды Математического института АН СССР им. В. А. Стеклова. — М.—Л.: изд-во АН СССР, 1954. — Т. 42. — С. 3—375.
18. ↑ Результат Поста был опубликован в статье E. L. Post Recursive Unsolvability of a Problem of Thue (англ.) // The Journal of Symbolic Logic. — 1947. — Т. 12. — № 1. — С. 1—11.
19. ↑ Emil Leon Post Recursively enumerable sets of positive integers and their decision problems (англ.) // Bulletin of the American Mathematical Society. — 1944. — В. 5. — Т. 50. — С. 284—316.
20. ↑ В американской математической традиции 0 является натуральным числом.
21. ↑ Martin Davis Arithmetical Problems and Recursively Enumerable Predicates (англ.) // The Journal of Symbolic Logic. — 1953. — Т. 18. — № 1. — С. 33—41.
22. ↑ 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  (англ.)
23. ↑ Julia Robinson Existential definability in arithmetic (англ.) // Transactions of the American Mathematical Society. — 1952. — Т. 72. — № 3. — С. 437—449.
24. ↑ Martin Davis, Hilary Putnam Reductions of Hilbert’s tenth problem (англ.) // The Journal of Symbolic Logic. — 1958. — Т. 23. — № 2. — С. 183—187.
25. ↑ Martin Davis, Hilary Putnam, Julia Robinson The decision problem for exponential Diophantine equations (англ.) // Annals of Mathematics. — 1961. — Т. 74. — № 3. — С. 425—436.
26. ↑ Ю. В. Матиясевич Алгорифмическая неразрешимость экспоненциально-диофантовых уравнений с тремя неизвестными // Исследования по теории алгорифмов и математической логике / ред. А. А. Марков и В. И. Хомич. — М.: Наука, 1979. — В. 3. — С. 69—78.
27. ↑ «Julia Robinson and Hilbert’s Tenth Problem»  (англ.). — ZALA Films. Архивировано из первоисточника 10 апреля 2012. Проверено 27 августа 2009.
28. ↑ Carol Wood Film Review: Julia Robinson and Hilbert’s Tenth Problem (англ.) // Notices of the American Mathematical Society. — 2008. — Т. 55. — № 5. — С. 573–575. — ISSN 00029920.
29. ↑ Margaret A. M. Murray A Film of One’s Own (англ.) // College Mathematics Journal. — Washington, DC: Mathematical Association of America, 2009. — Т. 40. — № 4. — С. 306—310. — ISSN 07468342.

Литература

• Ю. В. Матиясевич Десятая проблема Гильберта. — М.: Наука: Физико-математическая литература, 1993. — 223 с. — (Математическая логика и основания математики; выпуск № 26). — ISBN 502014326X
• Ф. Варпаховский, А. Колмогоров О решении десятой проблемы Гильберта // Квант. — 1970. — № 7. — С. 38—44.
• Ю. И. Хмелевский К десятой проблеме Гильберта // Проблемы Гильберта / под ред. П. С. Александрова. — М.: Наука, 1969. — С. 141—153. — 240 с. — 10 700 экз.
• К. М. Подниекс Глава 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  (англ.). Архивировано из первоисточника 10 апреля 2012. Проверено 27 августа 2009.
• 10-я проблема Гильберта: история математического открытия. Архивировано из первоисточника 10 апреля 2012. Проверено 27 августа 2009.
• Yuri Matiyasevich Hilbert’s Tenth Problem: What can we do with Diophantine equations  (англ.). Архивировано из первоисточника 10 апреля 2012. Проверено 27 августа 2009.
• Zhi-Wei Sun On Hilbert’s tenth problem and related topics  (англ.) (14 апреля 2000). Архивировано из первоисточника 10 апреля 2012. Проверено 29 августа 2009.
• Panu Raatikainen The problem of the simplest diophantine representation  (англ.). Архивировано из первоисточника 10 апреля 2012. Проверено 29 августа 2009.