вычитать текст, пока - слегка причёсанный дипсик
В третьем номере «Кванта» сообщалось о выдающемся успехе молодого ленинградского математика
Ю. В. Матиясевича, которому недавно удалось сделать завершающий шаг в решении одной из знаменитых
«проблем Гильберта», поставленных ещё в 1900-м году. Работа Ю. В. Матиясевича опубликована в Докладах Академии наук
СССР .
И что бывает редко — вдумчивый школьник может
самостоятельно разобраться в основном содержании этой работы,
имеющей важное значение для современной математической науки.
Дело в том, что оригинальная часть работы
Ю. В. Матиясевича посвящена доказательству теоремы, формулировка которой вполне элементарна
и приведена в публикуемой нами статье. Методы доказательства тоже элементарны. Труднее, правда,
объяснить на понятном школьнику языке, почему эта теорема о числах Фибоначчи имеет столь
значительный
интерес для серьёзной математической науки. По своей формулировке и методам доказательства
она скорее
напоминает хитроумную олимпиадную задачу.
1. Теорема о числах Фибоначчи
Во всём дальнейшем мы будем иметь дело только с целыми числами.
Рассмотрим такое свойство пары чисел
$(a, b)$: «$b$ делится на $a$». Это свойство пары чисел можно выразить и так:
«существует число $x$ такое,
что $ax-b=0$». Мы выразили наше свойство пары чисел $(a, b)$
через существование решения уравнения
$$
ax-b=0
$$
(напомним ещё раз, что мы имеем дело только с целыми числами и, значит, только с целыми решениями).
Уравнение это имеет вид $$
P(a, b, x)=0,
$$
где $P$ — многочлен от трёх переменных $a, b, x$.
Введём теперь общее определение; свойство конечной последовательности чисел
$(a_1, a_2, \ldots, a_m)$ называется диофантовым, если существует такой многочлен от $m+n$
переменных
$$
P(a_1,a_2,\ldots,a_m,x_1,x_2,\ldots,x_n),
$$
что последовательность $(a_1, a_2,\ldots,a_m)$ обладает нашим свойством в том и только в том случае,
когда существуют числа $x_1, x_2, \ldots, x_n$, для которых
$$
P(a_1, a_2, \ldots, a_m, x_1, x_2, \ldots, x_n) = 0.
$$
Основное достижение Матиясевича как раз и состоит в доказательстве диофантовости
некоторого специального свойства пар чисел $(a, b)$.
Многие из вас знакомы с числами Фибоначчи
$$\begin{gathered}\begin{alignat*}{2}
\psi_0 &= 0, &\psi_1 &= 1,\\
\psi_2 &= \psi_0 +{} &\psi_1 &= 1,\\
\psi_3 &= \psi_1 +{} &\psi_2 &= 2,\\
\psi_4 &= \psi_2 +{} &\psi_3 &= 3,\\
\psi_5 &= \psi_3 +{} &\psi_4 &= 5,
\end{alignat*}\\ .~.~.~.~.~.~.~.~.~.~.~.\end{gathered}
$$
бесконечная последовательность которых определяется рекуррентной формулой
$$
\psi_{n+1} = \psi_{n-1} + \psi_n.
$$
Свойство пары чисел $(a, b)$, которым занимается Матиясевич, таково:
«$b$ есть число Фибоначчи с номером $2a$, т. е. $b = \psi_{2a}$». Ясно, что этим свойством обладают
пары
$$
(0,0),\ (1,1),\ (2,3),\ (3,8)
$$
и т. д. Утверждение, что свойство Матиясевича диофантово,
означает, что существует многочлен
$$
Q(a, b, x_1, x_2, \ldots, x_n)
$$
такой, что $b$ будет числом Фибоначчи с номером $2a$ тогда и только тогда, когда существуют такие числа
$x_1, x_2, \ldots, x_n$, что $$
Q(a, b, x_1, x_2, \ldots, x_n) = 0.
$$
Многочлен $Q$ с целыми коэффициентами можно было бы в принципе явно выписать.
Матиясевич этого не делает и даже не указывает, каково число $n$ дополнительных переменных.
Что касается доказательства сформулированной теоремы, то, как уже было сказано, оно вполне элементарно.
Матиясевич ссылается на одну лемму, доказанную в книжке Н. Н. Воробьёва «Числа Фибоначчи»,
предназначенной для школьников, и один результат, доказанный в более учёной книге А. И. Мальцева,
но тоже элементарный. В самой работе Матиясевича девятнадцать лемм приведены без доказательства,
но доказательство каждой из них в отдельности не труднее обычных задач для школьников.
Трудность состояла лишь в том, чтобы найти ту именно комбинацию элементарных предложений,
которая ведёт к конечной цели.
2. Почему всё это так важно?
Если бы многочлен $Q$ Матиясевича был в самом деле очень нужен математикам
для проведения каких-либо расчётов, то вероятно, Матиясевич не поленился бы его явно выписать.
Но в действительности само обращение к числам Фибоначчи являлось для Матиясевича
лишь вспомогательным средством для установления весьма общих и важных закономерностей.
В случае свойства Матиясевича существует очень простой регулярный способ (алгоритм)
для последовательного выписывания всех обладающих этим свойством пар $$
(0,0),\ (1,1),\ (2,3),\ (3,8),\ (4,21),\ (5,55),\ \dots
$$
Так как множество этих пар бесконечно, то процесс их выписывания никогда не кончится.
Но мы располагаем правилом, по которому наши пары можно выписывать одну за другой с уверенностью в том, что 1) будут выписаны только пары, обладающие свойством Матиясевича, 2) любая пара, обладающая свойством Матиясевича, рано или поздно будет выписана.
Свойство (на более учёном языке «предикат») конечной последовательности чисел
$(a_1, a_2, \ldots, a_m)$ называется перечислимым, если существует правило,
позволяющее при помощи механического применения этого правила получать одну за другой последовательности,
с непременностью обладающие заданным свойством, и притом так, что любая последовательность,
обладающая этим свойством, рано или поздно будет получена. С современной точки зрения самым
значительным следствием теоремы Матиясевича о числах Фибоначчи является
Теорема 1. Любое перечислимое свойство конечной последовательности чисел является диофантовым.
До 1961 года эта теорема казалась бы крайне неожиданной. Но некоторый более слабый результат Девиса,
Путнама и Робинсон, доказанный в 1961 году, сделал такую гипотезу уже не столь невероятной.
На её доказательство математиками были затрачены немалые усилия. Матиясевич и воспользовался некоторыми,
как говорят, «редукциями» проблемы к более специальным задачам. Но идея свести всё к свойствам
чисел Фибоначчи была и в обстановке, сложившейся к 1970 году, неожиданной.
Таким образом крупный успех Матиясевича требовал соединения понимания больших проблем
современной математики и эрудиции в своей области с искусством находить неожиданные вполне элементарные
пути решения специальных задач.
3. В каком смысле Матиясевич решил десятую проблему Гильберта
В десятой проблеме Гильберта
речь идёт об уравнениях вида
$$
P \left( x_1, x_2, \ldots, x_n \right) = 0,
$$
где $P$ — многочлен с целыми коэффициентами. Степенью такого уравнения называют степень многочлена $P$.
Когда вопрос ставится о нахождении их решений в целых числах, эти уравнения называют «диофантовыми».
Например, уравнение
$$
x^2 + y^2 = 1
$$
имеет четыре решения в целых числах
$$
x = \pm 1, \quad y = \pm 1,
$$
а уравнение
$$
x^2 + y^2 = 3
$$
в целых числах решений не имеет. Теперь предоставим слово самому Гильберту:
«Пусть одно произвольное диофантовое уравнение с произвольным числом неизвестных ...;
требуется указать общий метод, следуя которому можно было бы в конечное число шагов узнать,
имеет данное уравнение решение в целых ... числах или нет».
Гильберт, по-видимому, был убеждён, что искомый общий метод существует,
и дело заключалось лишь в том, чтобы найти его. Немало усилий было затрачено,
чтобы отыскать этот метод, но сколь-нибудь обнадёживающих результатов не получалось.
Задача о целых решениях произвольного уравнения легко сводится к задаче о натуральных
(целых неотрицательных) решениях. Далее, совсем нетрудно показать, что достаточно
ограничиться диофантовыми уравнениями степени не выше четвёртой. Для диофантовых
уравнений степени не выше второй искомый общий метод был найден,
но уже уравнения третьей степени не поддавались никаким усилиям.
В связи с неудачами в этом направлении возникло подозрение,
что тот общий метод, об отыскании которого говорится в формулировке Гильберта,
попросту не существует! Сходная ситуация сложилась и в ряде других задач аналогичного характера.
Однако, одно дело найти требуемый общий метод — тут достаточно было только предъявить
этот метод и непосредственно убедиться в том, что он удовлетворяет условиям,
выдвинутым Гильбертом.
А вот чтобы доказать несуществование некоего общего метода для решения серии задач,
требовалось дать точное определение тому, что такое этот общий метод, как и какими средствами
он может быть реализован. В начале тридцатых годов соответствующие определения были выработаны
в трудах американского учёного Чёрча и английского учёного Тьюринга.
Эти определения положили начало теории алгоритмов. Оглядываясь на пройденный путь,
математики должны быть благодарны десятой проблеме Гильберта уже за то, что она послужила одним
из стимулов для создания этой теории.
В рамках теории алгоритмов было получено и точное определение понятия
«перечислимое свойство», которым мы воспользовались в предыдущем пункте.
Оказалось, что из диофантовости любого перечислимого свойства конечной
числовой последовательности вытекает
Теорема 2. Невозможен общий метод (алгоритм), позволяющий для любого заданного
диофантова уравнения установить, имеет оно решения в целых числах или нет.
Матиясевич из своей теоремы о диофантовости специального свойства пары чисел $a, b$
$$
b = \psi_{2a}
$$
вывел доказательство теоремы 1, из которой, как уже было известно, вытекает теорема 2,
т. е. отрицательное решение десятой проблемы Гильберта.
Для окончательного понимания всего сказанного вам не хватает только отчётливого знания того,
что такое «алгоритм» (общий метод решения бесконечного ряда задач) и что такое
«перечислимое свойство» (перечислимый предикат). Но это уже значительно более трудная тема.
4. Определения и факты теории алгоритмов
1. Среди функций, определённых на множестве $\mathbb{N}$ натуральных чисел и принимающих натуральные
значения, следующим образом выделяется класс примитивно рекурсивных функций.
Рассматриваются функции $S(n) = n + 1$ и $q(n) = n - p$, где $p^2 \leq n \lt (p + 1)^2$. Из функций $h(n)$ и $q(n)$ разрешается образование функции
$h_1(n) = f(n) + q(n)$ (операция сложения),
$h_2(n) = f(q(n))$ (операция подстановки), а из одной функции $f(n)$ — функцию,
определяемую равенствами $h_3(0) = 0$, $h_3(n+1) = f(h_3(n))$ (операция итерирования).
Класс примитивно рекурсивных функций состоит из функций $S$, $q$ и всех тех функций,
которые могут быть получены из них конечным числом сложений, подстановок и итерирований.
Пример. Покажем, что функции $q(n) = 2n$ и $\psi(n) = 2n + 1$ примитивно рекурсивные.
Применим сначала операцию итерирования к функции $S(n) = n + 1$.
Тогда $h(0) = 0$, $h(n) = S(h(n)) = h(n) + 1$. Следовательно, $h(n) = n$ и $q(n)$
получается применением операции сложения к двум функциям, каждая из которых равна $h(n)$:
$q(n) = h(n) + h(n) = n + n - 2n$. Наконец, функции $\psi(n)$ получается операцией подстановки,
применённой к функции $S(n) = n + 1$ и $q(n) = 2n$: $\psi(n) = S(q(n)) = S(2n) = 2n + 1$.
2. Множество $M$ натуральных чисел называется перечислимым,
если оно совпадает со множеством значений некоторой примитивно рекурсивной функции.
Так, например, множество чётных чисел перечислимо, так как является множеством
значений примитивно рекурсивной функции $q(n) = 2n$. Множество нечётных чисел,
совпадающее со множеством значений примитивно рекурсивной функции $\psi(n) = 2n + 1$,
также перечислимо.
3. Множество $M$ называется разрешимым, если оно перечислимо вместе со своим дополнением $N-M$
(где $N$ — множество всех натуральных чисел).
В частности, разрешимо множество чётных чисел, поскольку оно перечислимо вместе со своим
дополнением (множеством нечётных чисел).
4. Существуют перечислимые, но неразрешимые множества.
Можно привести конкретный пример такого множества,
однако соответствующая конструкция технически слишком сложна,
для того чтобы её можно было выполнить в рамках настоящей заметки.
Пусть теперь дано некоторое множество $M$ натуральных чисел.
Можно задаться вопросом, существует ли общий метод, который по каждому натуральному $n$
определяет в конечное число шагов, принадлежит это $n$ множеству $M$ или нет.
Основное положение теории алгоритмов (тезис Чёрча) утверждает, что такой метод (алгоритм)
существует тогда и только тогда, когда множество $M$ разрешимо.
Для отрицательного решения десятой проблемы Гильберта достаточно было доказать
диофантовость каждого перечислимого множества, т.е. по каждому перечислимому множеству $M$
уметь строить такое диофантово уравнение $P(y, x_1, \ldots, x_n) = 0$, которое имело
бы натуральные решения $x_1, \ldots, x_n$ для всех $y$, принадлежащих $M$,
и только для таких $y$.
В самом деле, если бы это можно было сделать, то, взяв в качестве $M$ неразрешимое множество
(такие есть среди перечислимых, см. п. 4), мы получили бы, что уже для соответствующего
уравнения $P(y, x_1, \ldots, x_n) = 0$ нет общего метода (алгоритма),
который по каждому натуральному $y$ давал бы ответ на вопрос о существовании
у этого уравнения натуральных решений. Ведь если бы этот метод имелся, то можно было бы за конечное число шагов узнать, имеет ли уравнение $P(0, x_1, \ldots, x_n) = 0$ решение
(т. е. принадлежит ли число 0 множеству $M$), имеет ли уравнение $P(1, x_1, \ldots, x_n) = 0$
решение (т. е. принадлежит ли число 1 множеству $M$) и т. д. Получилось бы, что существует общий метод, который по каждому натуральному $y$ определяет
за конечное число шагов, принадлежит это $y$ множеству $M$ или нет.
Тогда в силу тезиса Чёрча $M$ было бы разрешимо, вопреки выбору этого множества.
5. Что было сделано и что сделал Матиясевич.
В пятидесятые годы группа американских математиков
(Р. Робинсон, Х. Путнам, М. Дэвис, Дж. Робинсон) получила ряд значительных и обнадёживаюших
результатов в поисках доказательства диофантовости перечислимых множеств.
(Гипотезу о диофантовости перечислимых множеств выдвинул Мартин Дэвис.)
Американским ученым ценою значительных усилий удалось свести задачу к доказательству
диофантовости отношения $y = z^u$. Джулия Робинсон пошла даже несколько дальше, показав,
что достаточно построить конкретное уравнение $R(u, v, x_1, ..., x_h) = 0$,
не допускающее решения $c \, v > u^u$, но для каждого $n$ имеющее решение $c \, v > u^n$.
Именно такого рода уравнение и удалось построить Ю. В. Матиясевичу, предложившему
вполне элементарную, но чрезвычайно остроумную и оригинальную конструкцию.
При этом пришлось решать задачу, необычную для традиционной теории чисел.
Ведь в теории чисел по заданному уравнению, как правило, исследуются свойства его решений,
здесь же, наоборот, задавшись определенными свойствами решений,
нужно было искать требуемое уравнение.
вставить таблицу иллюстрацией
Обратившись к рассмотрению последовательности Фибоначчи, Матиясевич заметил,
что если за $u$ взять половину номера четного члена последовательности,
а за $v$ — сам член, то неравенство $v > u^u$ будет всегда неверно,
а для любого $n$ можно найти такой четный член последовательности,
что неравенство $v>u^n$ будет верно.
Это обстоятельство иллюстрируется таблицей приведённой на стр. 43.
(В ней выделены те клетки, в которых числа $u^k$ оказываются меньше соответствующих чисел $v$).
После того как указанное свойство было проверено, Матиясевич «подправил»
последовательность Фибоначчи, выбросив из неё нечётные члены.
Именно, он рассмотрел последовательность, задаваемую соотношениями:
$\varphi_0=0$, $\varphi_1=1$, $\varphi_{n+1}=3\varphi_n-\varphi_{n-1}$.
Получилось в точности последовательность из чётных членов первоначальной последовательности:
$\varphi_0=0$, $\varphi_1=1$, $\varphi_2=3$, $\varphi_3=8$,
$\varphi_4=21$, $\varphi_5=55$, $\varphi_6=144$, $\varphi_7=377$ и т. д.
Приняв теперь за $u$ номер члена последовательности,
а за $v$ — член последовательности с номером $u$,
т. е. $\varphi_u$, мы получаем, что снова выполняется требуемое свойство для $u$ и $v$.
Теперь оставалось построить уравнение $P(u, v, x_1, \ldots, x_h) = 0$,
которое имело бы натуральное решение тогда и только тогда, когда $v = \varphi_u$,
дальше можно было сослаться на результат Джулии Робинсон! Для этого достаточно было построить
систему диофантовых уравнений $P_1=0$, ..., $P_n=0$ в переменных $u$, $v$, $x_1$, ..., $x_h$,
имеющую решение тогда и только тогда, когда $v = \varphi_u$ — ведь такая система имеет
в точности те же решения, что и единственное уравнение $P_1^2 + \ldots + P_n^2=0$.
Вот в каком виде получил Матиясевич требуемую систему уравнений:
1) $u+(a-1)=v$,
2) $v+b=l$,
3) $l^2-lk-k^2=1$,
4) $g^2-gh-h^2=1$,
5) $l^2c=g$,
6) $ld=r-2$,
7) $(2h+g)e=r-3$,
8) $x^2-rxy+y^2=1$,
9) $lp=x-u$,
10) $(2h+g)q=x-v$.
Для доказательства того, что существование натурального решения этой системы
равносильно соотношению $v=\varphi_u$, Матиясевич использовал следующее характеристическое
свойство последовательности $\{ \varphi_k \}$: пара условий $x\lt y$ и $x^2-3xy+y^2=1$
равносильна существованию такого $k$, что $x=\varphi_k$ и $y=\varphi_{k+1}$.
Интересующемуся читателю рекомендуем попробовать свои силы на доказательстве
этой равносильности.
Укажем в заключение, что найденное решение десятой проблемы имеет ряд интересных следствий,
из которых, быть может, наиболее эффектным является следующее:
можно указать конкретный многочлен пятой степени, множество положительных
значений которого совпадает со множеством всех простых чисел!
Математическая наука записала в свой актив серьёзное и поучительное достижение.
Задачи
1. Покажите, что для любого $k$ числа $\varphi_k$ и $\varphi_{k+1}$ взаимно просты.
2. Докажите соотношение: $\varphi_{k+1}=\varphi_{k+1}\varphi_l-\varphi_k\varphi_{l-1}$.
3. Покажите, что диофантовое уравнение $P(y, x_1, \ldots, x_h) = 0$ имеет решение
в целых положительных числах тогда и только тогда, когда такое решение имеет уравнение
$$
Z=(1-(P(z, x_1, \ldots, x_h))^2)-y.
$$
