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

Десятая проблема Гильберта — десятая в списке математических задач , поставленных немецким математиком Давидом Гильбертом в 1900 году. Это задача — разработать общий алгоритм , который для любого данного диофантового уравнения ( полиномиального уравнения с целыми коэффициентами и конечным числом неизвестные), может решить, имеет ли уравнение решение, в котором все неизвестные принимают целые значения.

Например, диофантово уравнение $3x^{2}-2xy-y^{2}z-7=0$ имеет целочисленное решение: $x=1,\ y=2,\ z=-2$. Напротив, диофантово уравнение $x^{2}+y^{2}+1=0$ не имеет такого решения.

Десятая проблема Гильберта решена и имеет отрицательный ответ: такого общего алгоритма не может существовать. Это результат совместной работы Мартина Дэвиса , Юрия Матиясевича , Хилари Патнэм и Джулии Робинсон , продолжавшейся 21 год, причем Матиясевич завершил теорему в 1970 году. Теорема теперь известна как теорема Матиясевича или теорема MRDP (инициализация фамилий четырех основных участников ее решения).

Когда все коэффициенты и переменные ограничены положительными целыми числами, соответствующая проблема проверки полиномиальной идентичности становится разрешимой (без возведения в степень) вариацией школьной алгебры задачи Тарского , иногда обозначаемой ${\overline {HSI}}.$

Фон

Оригинальная формула

Гильберт сформулировал проблему следующим образом:

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

Слова «процесс» и «конечное число операций» были истолкованы как означающие, что Гильберт просил разработать алгоритм . Термин «рациональный интеграл» просто относится к целым числам, положительным, отрицательным или нулевым: 0, ±1, ±2, ... . Итак, Гильберт просил разработать общий алгоритм, позволяющий определить, имеет ли данное полиномиальное диофантово уравнение с целыми коэффициентами решение в целых числах.

Проблема Гильберта не связана с поиском решений. Он лишь спрашивает, можем ли мы вообще решить, существует ли одно или несколько решений. Ответ на этот вопрос отрицательный в том смысле, что для ответа на этот вопрос не может быть разработан «процесс». Говоря современным языком, 10-я проблема Гильберта является неразрешимой проблемой .

Диофантовые множества

Основная статья: Диофантовый набор

В диофантовом уравнении есть два типа переменных: параметры и неизвестные. Диофантовый набор состоит из назначений параметров, для которых разрешимо диофантово уравнение. Типичным примером является линейное диофантово уравнение с двумя неизвестными:

$a_{1}x+a_{2}y=a_{3}$,

где уравнение разрешимо тогда и только тогда, когда наибольший общий делитель $\gcd(a_{1},a_{2})$ равномерно делит $a_{3}$. Набор всех упорядоченных троек $(a_{1},a_{2},a_{3})$ удовлетворяющее этому ограничению, называется диофантовым множеством , определяемым формулой $a_{1}x+a_{2}y=a_{3}$. В этих терминах десятая проблема Гильберта спрашивает, существует ли алгоритм, позволяющий определить, непусто ли диофантово множество, соответствующее произвольному многочлену.

Проблема обычно понимается в терминах натуральных чисел (то есть неотрицательных целых чисел), а не произвольных целых чисел. Однако эти две проблемы эквивалентны: любой общий алгоритм, который может решить, имеет ли данное диофантово уравнение целочисленное решение, может быть модифицирован в алгоритм, который решает, имеет ли данное диофантово уравнение решение в натуральных числах, и наоборот. По теореме Лагранжа о четырех квадратах каждое натуральное число представляет собой сумму квадратов четырех целых чисел, поэтому мы могли бы переписать каждый натуральный параметр в терминах суммы квадратов четырех новых целочисленных параметров. Аналогично, поскольку каждое целое число представляет собой разность двух натуральных чисел, мы могли бы переписать каждый целочисленный параметр как разность двух натуральных параметров. Более того, мы всегда можем переписать систему одновременных уравнений $p_{1}=0,\ldots ,p_{k}=0$ (где каждый $p_{i}$ является многочленом) как одно уравнение $p_{1}^{\,2}+\cdots +p_{k}^{\,2}=0$.

Рекурсивно перечислимые множества

Рекурсивно перечисляемый набор можно охарактеризовать как набор, для которого существует алгоритм , который в конечном итоге останавливается, когда член набора предоставляется в качестве входных данных, но может продолжаться бесконечно, если входные данные не являются членами. Именно развитие теории вычислимости (также известной как теория рекурсии) обеспечило точное объяснение интуитивного понятия алгоритмической вычислимости, что сделало понятие рекурсивной перечислимости совершенно строгим. Очевидно, что диофантовы множества рекурсивно перечислимы (также известны как полуразрешимые). Это связано с тем, что можно расположить все возможные кортежи значений неизвестных в последовательность, а затем для заданного значения параметра (параметров) проверить эти кортежи один за другим, чтобы увидеть, являются ли они решениями соответствующего уравнения. Неразрешимость десятой проблемы Гильберта является следствием того удивительного факта, что верно обратное:

Любое рекурсивно перечислимое множество диофантово.

Этот результат по-разному известен как теорема Матиясевича (поскольку он обеспечил решающий шаг, завершивший доказательство) и теорема MRDP (для Юрия Матиясевича , Джулии Робинсон , Мартина Дэвиса и Хилари Патнэм ). Поскольку существует рекурсивно перечислимое множество, которое не является вычислимым, непосредственным следствием этого является неразрешимость десятой проблемы Гильберта. На самом деле можно сказать больше: существует полином

$p(a,x_{1},\ldots ,x_{n})$

с целыми коэффициентами такими, что набор значений $a$ для которого уравнение

$p(a,x_{1},\ldots ,x_{n})=0$

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

История

Год	События
1944	Эмиль Леон Пост заявляет, что десятая проблема Гильберта «требует доказательства неразрешимости».
1949	Мартин Дэвис использует Курта Гёделя метод для применения китайской теоремы об остатках в качестве трюка кодирования для получения своей нормальной формы для рекурсивно перечислимых множеств: $\left\{a\mid \exists y\forall k\leqslant y\exists x_{1},\ldots ,x_{n}:p\left(a,k,y,x_{1},\ldots ,x_{n}\right)=0\right\}$ где $p$ является многочленом с целыми коэффициентами. Чисто формально только ограниченный квантор всеобщности мешает этому определению диофантова множества. Используя неконструктивное, но простое доказательство, он выводит как следствие этой нормальной формы, что множество диофантовых множеств не замкнуто относительно дополнения, показывая, что существует диофантово множество, дополнение которого не является диофантовым. Поскольку рекурсивно перечислимые множества также не замкнуты при дополнении, он предполагает, что эти два класса идентичны.
1950	Джулия Робинсон , не зная о работе Дэвиса, исследует связь показательной функции с проблемой и пытается доказать, что EXP, набор троек $(a,b,c)$ для чего $a=b^{c}$, является Диофантином. Не добившись успеха, она выдвигает следующую гипотезу (позже названную JR): Есть диофантовый набор. $D$ пар $(a,b)$ такой, что $(a,b)\in D\Rightarrow b<a^{a}$ и за каждый позитив $k,$ существует $(a,b)\in D$ такой, что $b>a^{k}.$ Используя свойства уравнения Пелла, она доказывает, что из JR следует, что EXP диофантов, а также биномиальные коэффициенты, факториал и простые числа.
1959	Работая вместе, Дэвис и Патнэм изучают экспоненциальные диофантовые множества : множества, определяемые диофантовыми уравнениями, в которых некоторые показатели степени могут быть неизвестными. Используя нормальную форму Дэвиса вместе с методами Робинсона и предполагая тогда недоказанную гипотезу о том, что существуют сколь угодно длинные арифметические прогрессии, состоящие из простых чисел , они доказывают, что каждое рекурсивно перечислимое множество является экспоненциально диофантовым. Как следствие они также доказывают, что из JR следует, что каждое рекурсивно перечислимое множество является диофантовым, что, в свою очередь, означает, что десятая проблема Гильберта неразрешима.
1960	Робинсон упрощает доказательство условного результата для экспоненциальных диофантовых множеств и делает его независимым от гипотезы о простых числах и, следовательно, формальной теоремой. Это делает гипотезу JR достаточным условием неразрешимости десятой проблемы Гильберта. Однако многие сомневаются, что JR правдив.
1961–1969	В этот период Дэвис и Патнэм находят различные предложения, которые подразумевают JR, а Робинсон, ранее показав, что JR подразумевает, что множество простых чисел является диофантовым множеством, доказывает, что это условие «если и только если» . Юрий Матиясевич публикует некоторые сокращения десятой проблемы Гильберта.
1970	Опираясь на недавно опубликованную работу Николая Воробьева о числах Фибоначчи, Матиясевич доказывает, что множество $P=\{(a,b)|a>0,b=F_{2a}\},$ где $F_{n}$ это н й Число Фибоначчи является диофантовым и демонстрирует экспоненциальный рост. Это доказывает гипотезу JR, которая к тому времени уже 20 лет оставалась открытым вопросом. Сочетание JR с теоремой о том, что каждое рекурсивно перечислимое множество является экспоненциально диофантовым, доказывает, что рекурсивно перечислимые множества являются диофантовыми. Это делает десятую проблему Гильберта неразрешимой.

Приложения

Теорема Матиясевича/MRDP связывает два понятия — одно из теории вычислимости, другое из теории чисел — и имеет некоторые удивительные последствия. Пожалуй, самым удивительным является существование универсального диофантова уравнения:

Существует полином $p(a,n,x_{1},\ldots ,x_{k})$ такая, что для любого диофантова множества $S$ есть номер $n_{0}$ такой, что

$$S=\{\,a\mid \exists x_{1},\ldots ,x_{k}[p(a,n_{0},x_{1},\ldots ,x_{k})=0]\,\}.$$

Это верно просто потому, что диофантовые множества, будучи равными рекурсивно перечислимым множествам, также равны машинам Тьюринга . Хорошо известное свойство машин Тьюринга состоит в том, что существуют универсальные машины Тьюринга, способные выполнять любой алгоритм.

Хилари Патнэм отметила, что для любого диофантова множества $S$ положительных целых чисел существует полином

$q(x_{0},x_{1},\ldots ,x_{n})$

такой, что $S$ состоит ровно из положительных чисел среди значений, принимаемых $q$ как переменные

$x_{0},x_{1},\ldots ,x_{n}$

распространяется на все натуральные числа. Это можно увидеть следующим образом: если

$p(a,y_{1},\ldots ,y_{n})=0$

дает диофантово определение $S$, то достаточно положить

$$q(x_{0},x_{1},\ldots ,x_{n})=x_{0}[1-p(x_{0},x_{1},\ldots ,x_{n})^{2}].$$

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

Другие приложения касаются того, что логики называют $\Pi _{1}^{0}$ предложения, иногда также называемые предложениями типа Гольдбаха . Это похоже на гипотезу Гольдбаха , утверждающую, что все натуральные числа обладают определенным свойством, которое алгоритмически проверяется для каждого конкретного числа. Теорема Матиясевича/MRDP подразумевает, что каждое такое утверждение эквивалентно утверждению, утверждающему, что некоторое конкретное диофантово уравнение не имеет решений в натуральных числах. Ряд важных и знаменитых проблем имеют такую ​​форму: в частности, Великая теорема Ферма , гипотеза Римана и теорема о четырёх цветах . Кроме того, утверждение о том, что определенные формальные системы , такие как арифметика Пеано или ZFC, непротиворечивы, можно выразить как $\Pi _{1}^{0}$ предложения. Идея состоит в том, чтобы следовать Курту Гёделю в кодировании доказательств натуральными числами таким образом, чтобы свойство быть числом, представляющим доказательство, было алгоритмически проверяемым.

$\Pi _{1}^{0}$ предложения обладают особым свойством: если они ложны, этот факт можно будет доказать в любой из обычных формальных систем. Это потому, что ложность сводится к существованию контрпримера, который можно проверить с помощью простой арифметики. Итак, если $\Pi _{1}^{0}$ предложение таково, что ни оно, ни его отрицание не доказуемы ни в одной из этих систем, то это предложение должно быть истинным.

Особенно яркая форма теоремы Гёделя о неполноте также является следствием теоремы Матиясевича/MRDP:

Позволять

$p(a,x_{1},\ldots ,x_{k})=0$

дать диофантово определение невычислимого множества. Позволять $A$ быть алгоритмом, который выводит последовательность натуральных чисел $n$ такая, что соответствующее уравнение

$p(n,x_{1},\ldots ,x_{k})=0$

не имеет решений в натуральных числах. Тогда есть номер $n_{0}$ это не выводится $A$ хотя на самом деле уравнение

$p(n_{0},x_{1},\ldots ,x_{k})=0$

не имеет решений в натуральных числах.

Чтобы убедиться в справедливости теоремы, достаточно заметить, что если бы такого числа не существовало $n_{0}$можно алгоритмически проверить принадлежность числа $n$ в этом невычислимом множестве, одновременно запуская алгоритм $A$ чтобы увидеть, есть ли $n$ выводится, одновременно проверяя все возможные $k$-кортежи натуральных чисел, ищущие решение уравнения

$p(n,x_{1},\ldots ,x_{k})=0$

и мы можем связать алгоритм $A$ с любой из обычных формальных систем, таких как арифметика Пеано или ZFC, позволяя ей систематически генерировать следствия аксиом, а затем выводить число $n$ всякий раз, когда предложение формы

$\neg \exists x_{1},\ldots ,x_{k}[p(n,x_{1},\ldots ,x_{k})=0]$

генерируется. Тогда теорема говорит нам, что либо ложное утверждение такого вида доказано, либо истинное остаётся недоказанным в рассматриваемой системе.

Дальнейшие результаты

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

Уже в 1920-х годах Торальф Скулем показал, что любое диофантово уравнение эквивалентно уравнению 4-й степени и ниже. Его трюк заключался в том, чтобы ввести новые неизвестные с помощью уравнений, устанавливающих их равными квадрату неизвестного или произведению двух неизвестных. Повторение этого процесса приводит к системе уравнений второй степени; тогда уравнение степени 4 получается суммированием квадратов. Таким образом, каждое диофантово множество тривиально имеет степень 4 или меньше. Неизвестно, является ли этот результат наилучшим из возможных.

Джулия Робинсон и Юрий Матиясевич показали, что каждое диофантово множество имеет размерность не более 13. Позже Матиясевич усовершенствовал свои методы и показал, что достаточно 9 неизвестных. Хотя вполне возможно, что этот результат не самый лучший из возможных, дальнейшего прогресса не произошло. Так, в частности, не существует алгоритма проверки диофантовых уравнений с 9 и менее неизвестными на разрешимость в натуральных числах. В случае целочисленных рациональных решений (как первоначально сформулировал Гильберт) трюк с 4 квадратами показывает, что не существует алгоритма для уравнений с числом не более 36 неизвестных. Но Чжи Вэй Сунь показал, что задача для целых чисел неразрешима даже для уравнений с числом неизвестных не более 11.

Мартин Дэвис изучал алгоритмические вопросы, связанные с числом решений диофантового уравнения. Десятая проблема Гильберта спрашивает, равно ли это число 0. Пусть $A=\{0,1,2,3,\ldots ,\aleph _{0}\}$ и пусть $C$ быть собственным непустым подмножеством $A$. Дэвис доказал, что не существует алгоритма, позволяющего проверить данное диофантово уравнение и определить, является ли число его решений членом множества. $C$. Таким образом, не существует алгоритма, позволяющего определить, является ли число решений диофантова уравнения конечным, нечетным, квадратным, простым и т. д.

Доказательство теоремы MRDP было формализовано в Coq .

Расширения десятой проблемы Гильберта

Александра Шлапентох (в центре) в 2003 году.

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

Было много работ по десятой проблеме Гильберта для колец целых полей алгебраических чисел. Основываясь на более ранних работах Яна Денефа и Леонарда Липшица и используя теорию полей классов, Гарольд Н. Шапиро и Александра Шлапентох смогли доказать:

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

Шлапентох и Танас Феид (независимо друг от друга) получили тот же результат для полей алгебраических чисел, допускающих ровно одну пару комплексно-сопряженных вложений.

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

Ссылки

• Гильберт, Дэвид (1901). «Математические задачи». Архив математики и физики . 3-я серия (на немецком языке). 1 : 44–63, 213–247.
• Гильберт, Дэвид (июль 1902 г.). «Математические задачи» . Бык. амер. Математика. Соц. 8 (10): 437–479. дои : 10.1090/S0002-9904-1902-00923-3 .
• Yuri V. Matiyasevich , Hilbert's Tenth Problem , MIT Press, Cambridge, Massachusetts, 1993.
• Дэвис, Мартин ; Матиясевич Юрий ; Робинсон, Джулия (1976). «Десятая проблема Гильберта: диофантовы уравнения: положительные аспекты отрицательного решения». В Феликсе Э. Браудере (ред.). Математические разработки, вытекающие из задач Гильберта . Труды симпозиумов по чистой математике . Том. ХXVIII.2. Американское математическое общество . стр. 323–378. ISBN  0-8218-1428-1 . Збл   0346.02026 . Перепечатано в Собрании сочинений Джулии Робинсон , Соломона Фефермана , редактора, стр. 269–378, Американское математическое общество, 1996.
• Мартин Дэвис , «Десятая проблема Гильберта неразрешима», American Mathematical Monthly , том 80 (1973), стр. 233–269; перепечатано в качестве приложения в книге Мартина Дэвиса, «Вычислимость и неразрешимость» , переиздание в Дувре, 1982 г.
• Дэвис, Мартин ; Херш, Рубен (1973). «10-я проблема Гильберта». Научный американец . 229 (5): 84–91. Бибкод : 1973SciAm.229e..84D . doi : 10.1038/scientificamerican1173-84 .
• Ян Денеф , Леонард Липшиц, Танас Фидас, Ян ван Гил, редакторы, «Десятая проблема Гильберта: семинар в Гентском университете, Бельгия, 2–5 ноября 1999 г.». Современная математика, том. 270 (2000), Американское математическое общество.
• М. Рэм Мерти и Брэндон Фодден: «Десятая проблема Гильберта: введение в логику, теорию чисел и вычислимость», Американское математическое общество, ISBN   978-1-4704-4399-3 (июнь 2019 г.).

Дальнейшее чтение

• Школьная задача Тарского по алгебре
• Шлапентох, Александра (2007). Десятая проблема Гильберта. Диофантовы классы и расширения глобальных полей . Новые математические монографии. Том. 7. Кембридж: Издательство Кембриджского университета . ISBN  978-0-521-83360-8 . Збл   1196.11166 .

Внешние ссылки

• Десятая проблема Гильберта: история математических открытий
• Страница десятой задачи Гильберта!
• Чжи Вэй Сунь: О десятой проблеме Гильберта и связанных с ней темах
• Трейлер фильма «Джулия Робинсон и десятая задача Гильберта» на YouTube