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

39

В третьем номере «Квана» сообщалось о выдающемся успесе молодого ленинградского математика Ю. В. Матиясевича, которое недавно удалось сделать завершающий шаг в решении одной из значений «проблем Гильберта», поставленных еще в 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₁, a₂, …, aₘ) называется диофантовым, если существует такой многочлен от m + n переменных

P(a₁, a₂, …, aₘ), что последовательность (a₁, a₂, …, aₘ) обладает нашим свойством в том и

*) Вот название и точный «адрес» статьи: Ю. В. Матиясевича. Диофантовость перечисленных множества, ДАН СССР, 1970, том 191, № 2.

40

только в том случае, когда существуют числа $x_1, x_2, \dots, x_n$, для которых $P(a_1, a_2, \dots, a_m, x_1, x_2, \dots, x_n) = 0$.

Основное достинение Матиясвича как раз и состоит в доказательстве диофантовости неокоторого спецальноного свойства пар чисел $(a, b)$.

Многие из вас знакомы с числами Фибоначчи

$$\psi_0 = 0, \quad \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,$$

бесконечная последовательность которых определяется рекуррентной формулой

$$\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, \dots, x_n)$$

такой, что $b$ будет числом Фибоначчи с номером $2a$ тогда и только тогда, когда существуют такие числа $x_1, x_2, \dots, x_n$, что

$$Q(a, b, x_1, x_2, \dots, 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, \dots, a_m)$ называется перечислением, если существует правило, позволяющее при помощи механического применения этого правила получить одну за другой последовательности, с непреемноностью обладающей заданным свойством, и при том так, что любая последовательность

41

ность, обладающая этим свойством, рано или поздно будет получена.

С современной точки зрения самим значительным следствием теоремы Матиясвича о числах Фибоначчи является

Теорема 1. Любое перечисление свойство конечной последовательности чисел является диофантовым.

Do 1961 года эта теорема казалась бы крайне неожиданной. Но некоторые более слабый результат Девиса, Путнама и Робинсон, доказанный в 1961 году, сделал такую гипотезу уже не столь невероятной. На ее доказательство математики были затрачены немалые усилия. Матиясвич и восползвался некоторыми, как говоря, «редукциями» проблемы к более специальным задачам. Но идея свести все к свойств чисел Фибоначчи была и в обстановке, сложившейся к 1970 году, неожиданной.

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

3. В каком смысле Матиясвич решил десятую проблему Гильберта

В десятий проблеме Гильберта*) решил об уравнениях вида

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

где $P$ многочлен с целыми коэффициентами. Степенью такого уравнения называют степень многочлена $P$. Когда вопрос ставится о нахождения их решения в целых числах, эти уравнения называют «диофантными». Например, уравнение

$$x^2 + y^2 = 1$$

имеет четые решения в целых числах

$$x = \pm 1, \quad y = \pm 1,$$

*) Более подробно о проблемах Гильберта можно прочитать в книге Д. Гильберт, «Matематические проблемы», «Наука», 1969.

а уравнение

$$x^2 + y^2 = 3$$

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

Тепер предоставим слово самому Гильберту:

«Пусть дан произвольное диофантное уравнение с произвольным числом неизвестных …; пребуемся указать общий метод, следующая компону можно было бы в конечное число шагов узнать, имеем данное уравнение решения в целых … числа или нет».

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

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

В связи с неудачами в этом направлении возникло подозрение, что тот общий метод, об отыскании которого говорится в формулировке Гильберта, попросту не существует! Сходная с ситуации сложилась и в ряде других задач аналогичного характера. Однако, одно дело найти требуемый общий метод — тут достаточно было только предъявить этот метод и неосредственно убедиться в том, что он удовлетворяет условиям, выдивинутым Гильбертом.

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

В начале тридцать годов соответствующие определения были выра

42

ботаны в трудах американского ученого Чёрча и английского ученого Тыорига. Эти определения положили начало теории алгоритмов. Оглаядыясь на проиденный путь, математики должны быть благодарны десятий проблем Гильберта уже за то, что она послужила одним из стимулов для создания этой теории.

В рамках теории алгоритмов было получено и точное определение понятия «перечислимое свойство», который мы воспользовались в предыдущем пункте.

Оказалось, что из диофантовости любого перечислного свойства конечной числовой последовательности вытекает

Теорема 2. Невозможно общий метод (алгоритм), позволяющий для любого заданного диофантова управления установить, имеет оно решения в целых числах или нет.

Матиясевич из своей теоремы о диофантовости специального свойства пары чисел (a, b)

$$b = \psi_{2a}$$

вывел доказательство теоремы 1, из которого, как уже было известно, вытекает теорема 2, т. е. отрицательное решение десятий проблем Гильберта.

Для окончательного понимания всего сказанного вам не хватает только отчетливого знания того, что такое «алгоритм» (общий метод решения бесконечного ряда задачи) и что такое «перечислимое свойство» (перечислный predикат). Но это уже значительное более трудная тема.

4. Определения и факты теории алгоритмов

5. Среди функций, определенных на множество N натуральных чисел и принимающих натуральные значения, следующим образом выделяется класс примитивно рекурсивных функций.

Рассматривают функцию S(n) n+1 и q(n)=n-p, где p²≤n<(p+1)². Из функций f(n) и q(n) разрезается образовать функцию h₁(n)=f(n)+q(n) (операция сложения), $h_2(n)=f(q(n))$ (операция подстановки), а из одной функции f(n) — функцию, определяемую равенствами h₃(0)=0, h₃(n+1)=f(h₃(n)) (операция инерирования). Класс примитивно рекурсивных функций состоит из функций S, q и всех тех функций, которые могут быть получены из них конечным числом сложений, подстановок и инерирования.

При имер. Покажем, что функция φ(n)=2n и φ(n)=2n+1-primитивно рекурсивное. Приимем сначала операцию инерирования к функции S(n)=n+1. Тогда h(0)=0, h(n+1)=S(h(n))=h(n)+1. Следовательно, h(n)=n и φ(n) получается применением операции сложения к двум функциям, каждой из которых равна h(n): φ(n)=h(n)+h(n)=n+n=2n. Наконец, функция φ(n) получается операцией подстановки, примененной к функциям S(n)=n+1 и φ(n)=2n: φ(n)=S(φ(n))=S(2n)=2n+1.

2. Множество M натуральных чисел называется перечислым, если оно совпадает со множеством значений некоторой примитивно рекурсивной функции.

Так, например, множество четных чисел перечислимо, так как является множеством значений примитивно рекурсивной функции φ(n)=2n. Множество нечетных чисел, совпадает со множеством значений примитивно рекурсивной функции φ(n)=2n+1, также перечислимо.

3. Множество M называется разрешимым, если оно перечислимо вместе со своим дополнением N—M (где N—множество всех натуральных чисел).

В частности, разрешимое множество чисел, поскольку оно перечислимо вместе со своим дополнением (множество нечетных чисел).

4. Существуют перечислимы, но неразрешимые множества.

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

Пусть теперь данное некоторое множество M натуральных чисел. Можно задать вопросом, существует ли общий метод, который по каждому натуральному n определяет в конечное число шагов, принадлежит это n множеству M или нет. Основное положение теории алгоритмов (теис Чёрча) утверждает, что макой метод (алгоритм) существует модела и молко модели, когда множество M разрешимо.

44

вательности, что неравенство $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, \dots, x_k) = 0$, которое имело бы натуральное решение тогда и только тогда, когда $v = \varphi_u$, — дальнейшее было составяя на результат Джулии Робинсон! Для этого достаточно было построить систему диффантовых уравнений $P_1 = 0, \dots, P_n = 0$ в переменных $u, v, x_1, \dots, x_k$, имеющего решение тогда и только тогда, когда $v = \varphi_u$ — ведтая система имеет в точности те же решения, что и единственное уравнение $P_1^2 + \dots + 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 < y$ и $x^2 - 3xy + y^2 = 1$ равносильно существование такого $k$, что $x = \varphi_k$ и $y = \varphi_{k+1}$.

Интересующемуся читателю рекомендуем поprobовать свои силы на доказательстве этой равносильности.

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

Matематическая наука записала в свой актив серверное и почительное достижение.

Задание 1

1. Покажите, что для любого $k$ числа $\varphi_k$ и $\varphi_{k+1}$ взаимно просты.
2. Докажите соответствие: $\varphi_{k+1} = \varphi_k + 1$.
3. Покажите, что диффантовое уравнение $P(y, x_1, \dots, x_k) = 0$ имеет решение в целях положительных числа тогда и только тогда, когда такое решение имеет уравнение

$$Z = (1 - (P(z, x_1, \dots, x_k))^2) - y.$$

По вине типографии в «Кванте» № 5 (стр. 64, зад. 1226) неправильно набран формула деления чисел. Она должна выглядеть так:

$$\frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} \times \frac{1}{2}$$