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

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

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

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

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

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

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

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

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

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

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

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

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

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

Каждое рекурсивно перечислимое множество является диофантовым.

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

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

с целыми коэффициентами, такими, что набор значений, для которых уравнение${\displaystyle а}$

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

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

Год	События
1944	Эмиль Леон Пост заявляет, что десятая проблема Гильберта «требует доказательства неразрешимости».
1949	Мартин Дэвис использует метод Курта Гёделя для применения китайской теоремы об остатках в качестве приема кодирования, чтобы получить его нормальную форму для рекурсивно перечислимых множеств: ${\displaystyle \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\}}$ где — многочлен с целыми коэффициентами. Чисто формально, только ограниченный квантор всеобщности препятствует тому, чтобы это было определением диофантова множества.${\displaystyle p}$ Используя неконструктивное, но простое доказательство, он выводит в качестве следствия этой нормальной формы, что множество диофантовых множеств не замкнуто относительно дополнения, показывая, что существует диофантово множество, дополнение которого не является диофантовым. Поскольку рекурсивно перечислимые множества также не замкнуты относительно дополнения, он предполагает, что эти два класса идентичны.
1950	Джулия Робинсон , не зная о работе Дэвиса, исследует связь показательной функции с проблемой и пытается доказать, что EXP, множество триплетов для которого , является диофантовым. Не преуспев, она выдвигает следующую гипотезу (позже названную JR):${\displaystyle (а,б,в)}$${\displaystyle а=b^{c}}$ Существует диофантово множество пар такое, что и для каждого положительного числа существует такое, что${\displaystyle D}$ ${\displaystyle (а,б)}$ ${\displaystyle (a,b)\in D\Стрелка вправо b<a^{a}}$ ${\displaystyle к,}$${\displaystyle (a,b)\in D}$ ${\displaystyle b>a^{k}.}$ Используя свойства уравнения Пелля, она доказывает, что из JR следует диофантовость EXP, а также биномиальные коэффициенты, факториал и простые числа.
1959	Работая вместе, Дэвис и Патнэм изучают экспоненциальные диофантовы множества : множества, определяемые диофантовыми уравнениями, в которых некоторые показатели могут быть неизвестными. Используя нормальную форму Дэвиса вместе с методами Робинсона и предполагая тогда недоказанную гипотезу о том, что существуют произвольно длинные арифметические прогрессии, состоящие из простых чисел , они доказывают, что каждое рекурсивно перечислимое множество является экспоненциальным диофантовым. Они также доказывают в качестве следствия, что JR подразумевает, что каждое рекурсивно перечислимое множество является диофантовым, что, в свою очередь, подразумевает, что десятая проблема Гильберта неразрешима.
1960	Робинсон упрощает доказательство условного результата для экспоненциальных диофантовых множеств и делает его независимым от гипотезы о простых числах и, таким образом, формальной теоремой. Это делает гипотезу JR достаточным условием неразрешимости десятой проблемы Гильберта. Однако многие сомневаются, что JR истинна. [5]
1961–1969	В этот период Дэвис и Патнэм находят различные предложения, которые подразумевают JR, а Робинсон, ранее показав, что JR влечет, что множество простых чисел является диофантовым множеством, доказывает, что это условие выполняется тогда и только тогда . Юрий Матиясевич публикует некоторые редукции десятой проблемы Гильберта.
1970	Опираясь на недавно опубликованную работу Николая Воробьева о числах Фибоначчи, [6] Матиясевич доказывает, что множество , где — n- е число Фибоначчи , является диофантовым и демонстрирует экспоненциальный рост. [7] Это доказывает гипотезу JR, которая к тому времени была открытым вопросом в течение 20 лет. Объединяя гипотезу JR с теоремой о том, что каждое рекурсивно перечислимое множество является экспоненциально диофантовым, доказывает, что рекурсивно перечислимые множества являются диофантовыми. Это делает десятую проблему Гильберта неразрешимой.${\displaystyle P=\{(a,b)|a>0,b=F_{2a}\},}$${\displaystyle F_{n}}$

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

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

$${\displaystyle S=\{\,a\mid \существует x_{1},\ldots ,x_{k}[p(a,n_{0},x_{1},\ldots ,x_{k})=0]\,\}.}$$

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

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

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

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

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

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

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

дает диофантово определение , тогда достаточно установить${\displaystyle S}$

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

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

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

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

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

Позволять

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

Предоставьте диофантово определение невычислимого множества. Пусть будет алгоритмом, который выводит последовательность натуральных чисел, такую, что соответствующее уравнение${\displaystyle А}$${\displaystyle n}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Гильберт, Дэвид (1901). «Математические задачи». Архив математики и физики . 3-я серия (на немецком языке). 1 : 44–63, 213–247.
• Гильберт, Дэвид (июль 1902 г.). «Математические проблемы». Bull. Amer. Math. Soc. 8 (10): 437–479. doi : 10.1090/S0002-9904-1902-00923-3 .
• Юрий В. Матиясевич , Десятая проблема Гильберта , MIT Press, Кембридж, Массачусетс, 1993.
• Дэвис, Мартин ; Матиясевич, Юрий ; Робинсон, Джулия (1976). «Десятая проблема Гильберта: Диофантовы уравнения: Положительные аспекты отрицательного решения». В Felix E. Browder (ред.). Математические разработки, возникающие из проблем Гильберта . Труды симпозиумов по чистой математике . Том XXVIII.2. Американское математическое общество . стр. 323–378. ISBN 0-8218-1428-1. Збл  0346.02026. Перепечатано в «Собрании сочинений Джулии Робинсон» , редактор Соломон Феферман , стр. 269–378, Американское математическое общество, 1996.
• Мартин Дэвис , «Десятая проблема Гильберта неразрешима», American Mathematical Monthly , т. 80 (1973), стр. 233–269; перепечатано в качестве приложения в Martin Davis, Computability and Unsolvability , переиздание Dover 1982.
• Дэвис, Мартин ; Херш, Рубен (1973). «10-я проблема Гильберта». Scientific American . 229 (5): 84–91. Bibcode : 1973SciAm.229e..84D. doi : 10.1038/scientificamerican1173-84.
• Ян Денеф , Леонард Липшиц, Танасес Фейдас, Ян ван Гел, редакторы, «Десятая проблема Гильберта: семинар в Гентском университете, Бельгия, 2–5 ноября 1999 г.». Contemporary Mathematics т. 270 (2000), Американское математическое общество.
• М. Рам Мёрти и Брэндон Фодден: «Десятая проблема Гильберта: введение в логику, теорию чисел и вычислимость», Американское математическое общество, ISBN 978-1-4704-4399-3 (июнь 2019 г.). 

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

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