Десятая проблема Гильберта: ответ — «нет»

Задача

Десятая из двадцати трёх проблем Гильберта, сформулированных в 1900 году:

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

Гильберт спрашивает «указать способ» — он не сомневался, что способ есть. Понятия алгоритма тогда не существовало вовсе; оно появится только в 1936 году в работах Тьюринга, ЧёрчаАлонзо Чёрчамериканский логик и математик · 1903–1995Ответил Гильберту «нет» за семь месяцев до Тьюринга — и сделал это на языке, где нет ни чисел, ни машин, а есть только функции и подстановка; из этого языка выросло функциональное программирование. и Поста. Лишь после этого вопрос стало возможно задать корректно — и получить отрицательный ответ.

Заметим, насколько задача общая. Отдельные диофантовы уравнения решать умеют: линейные — алгоритмом куттака; $x^{2}-Ny^{2}=1$ — методом чакравала; уравнения второй степени от двух переменных — полностью. Вопрос в том, есть ли единый метод для всех сразу.

Кто и что сделал

История решения — редкий пример эстафеты, растянувшейся на сорок лет и завершённой в один вечер.

Мартин Дэвис (1949–1953) свёл задачу к вопросу о том, какие множества натуральных чисел являются диофантовыми. Множество $S$ называется диофантовым, если существует многочлен $P$ с целыми коэффициентами такой, что

$$a\in S\iff \exists x_1,\dots,x_n\in\mathbb{N}:\ P(a,x_1,\dots,x_n)=0 .$$

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

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

Оставалось убрать экспоненту — то есть показать, что показательная функция сама диофантова. Джулия Робинсон ещё в 1950 году свела и это к одному-единственному условию, которое стали называть гипотезой Джулии Робинсон:

Существует диофантово отношение $R(u,v)$, которое растёт экспоненциально: из $R(u,v)$ следует $v<u^{u}$, и при этом для всякого $k$ найдётся пара с $v>u^{k}$.

Ни одного примера такого отношения найти не удавалось двадцать лет.

Юрий Владимирович Матиясевич (род. 1947), аспирант ленинградского отделения Математического института, нашёл его в январе 1970 года — и построил на числах Фибоначчи.

Как работает трюк с Фибоначчи

Числа Фибоначчи растут экспоненциально: $F_n\approx\varphi^{n}/\sqrt5$, где $\varphi$ — золотое сечение. Значит, если отношение «$v$ есть $2n$-е число Фибоначчи» окажется диофантовым, гипотеза Робинсон будет доказана.

Отправная точка — характеризация, которую школьник может проверить сам:

$$\left|F_{n+1}^{2}-F_{n+1}F_n-F_n^{2}\right|=1 .$$

Проверим: $(F_2,F_3)=(1,2)$ даёт $4-2-1=1$; $(2,3)$ даёт $9-6-4=-1$; $(3,5)$ даёт $25-15-9=1$. Знак чередуется, модуль всегда единица.

Верно и обратное: если натуральные $x,y$ удовлетворяют

$$y^{2}-xy-x^{2}=\pm1,$$

то $x$ и $y$ — соседние числа Фибоначчи. То есть пары соседних чисел Фибоначчи суть в точности решения одного квадратного уравнения — а это уже диофантово условие.

Дальше требовалась гораздо более тонкая работа: выразить связь между индексом $n$ и значением $F_n$, а не только между соседними значениями. Матиясевич использовал свойства делимости чисел Фибоначчи (например, $F_m\mid F_n$ тогда и только тогда, когда $m\mid n$, и $F_n^{2}\mid F_{nF_n}$) и получил искомое диофантово отношение экспоненциального роста.

Он доложил результат в Ленинграде в январе 1970 года; известие дошло до США за несколько недель, и Джулия Робинсон, немедленно разобравшись, написала ему письмо со словами о том, что теперь она знает: она дождалась. Впоследствии они стали соавторами и друзьями; их совместная работа 1974 года снизила число неизвестных в универсальном уравнении.

Что из этого следует

Теорема DPRM (Дэвис — Патнэм — Робинсон — Матиясевич). Множество натуральных чисел диофантово тогда и только тогда, когда оно перечислимо.

Следствия удивительны и выходят далеко за рамки исходного вопроса.

Ответ на десятую проблему: алгоритма нет. Взяв перечислимое, но неразрешимое множество (например, множество номеров останавливающихся машин ТьюрингаАлан Тьюринганглийский математик и криптоаналитик · 1912–1954Определил, что значит «вычислить», за десять лет до появления компьютеров, взломал «Энигму» и был осуждён за то, кем он был.) и его диофантово представление, получаем семейство уравнений, для которого никакая программа не может определить разрешимость.

Существует многочлен, множество положительных значений которого — в точности простые числа. Явный пример построили ДжонсВон Джонсновозеландский математик · 1952–2020Занимался операторными алгебрами, заметил, что его формулы совпадают с соотношениями в группе кос, — и нашёл инвариант узлов, которого топологи не могли найти сто лет., Сато, Вада и Виенс в 1976 году: многочлен от 26 переменных (буквы от $a$ до $z$) степени 25. Когда переменные пробегают натуральные числа, положительные значения многочлена — ровно все простые. Формула бесполезна для вычислений (значение оказывается положительным крайне редко), но её существование — прямое следствие того, что множество простых перечислимо.

Универсальное уравнение. Существует одно уравнение $U(a,k,x_1,\dots,x_n)=0$, которое при разных значениях параметра $k$ задаёт все диофантовы множества сразу. Программа, сведённая к уравнению.

ГёдельКурт Гёдельавстрийский и американский логик · 1906–1978Доказал, что в любой достаточно богатой формальной системе есть истинные утверждения, которые она не может доказать, — и тем закрыл программу Гильберта в двадцать пять лет. в диофантовой форме. Для всякой непротиворечивой формальной системы существует диофантово уравнение, у которого нет решений, но доказать это в системе невозможно. Теорема Гёделя, которую можно было счесть курьёзом о самоссылающихся высказываниях, оказывается утверждением о самых обыкновенных целочисленных уравнениях.

Что осталось открытым

Известно, что неразрешимость сохраняется уже для уравнений с 9 неизвестными (Матиясевич) и для степени 4. Наименьшее число переменных, при котором задача становится неразрешимой, неизвестно.

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

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

Задача. Проверьте, что уравнение $y^{2}-xy-x^{2}=\pm1$ выполняется для пар $(1,1),(1,2),(2,3),(3,5),(5,8)$, и докажите, что если пара $(x,y)$ ему удовлетворяет и $y>x$, то ему удовлетворяет и пара $(y-x,\,x)$.
(Указание: подставьте и раскройте скобки; знак меняется на противоположный. Это спуск ФермаПьер Фермафранцузский юрист и математик · 1607–1665Советник тулузского парламента, не напечатавший при жизни ни одной математической книги — и успевший заложить теорию чисел, аналитическую геометрию, метод касательных и теорию вероятностей.: любое решение сводится к $(1,1)$, значит других решений, кроме пар соседних чисел Фибоначчи, нет.)

Следующая точка: Кембридж под Бостоном — где самая бесполезная теорема этой линии станет инфраструктурой цивилизации.