关于希尔伯特第十问题的解答

39

《关》第三期报道了列宁格勒年轻数学家余的杰出成就。 V. Matiyasevich 最近成功迈出了最后一步，解决了 1900 年提出的“希尔伯特问题”的含义之一。Yu 的工作。 V. Matiyasevich 发表在苏联科学院的报告中*)。而很少发生的是，一个有思想的学生能够独立理解这项工作的主要内容，这对于现代数学科学来说很重要。事实是Yu的原始部分。 V. Matiyasevich 的工作致力于定理的证明，该定理的表述非常简单，在我们发表的文章中给出。证明方法也是初级的。用小学生可以理解的语言解释这些规则更加困难，为什么这个关于斐波那契数的定理对服务器端数学科学如此重要。从其表述和证明方法来看，它很像一个巧妙的优化问题。

1. 斐波那契数定理

在接下来的内容中，我们将只处理整数。考虑一对数字 (a, b) 的以下属性：

“b 能被 a 整除。”

一对数的这一性质可以表示如下：

“存在一个数字 x，使得 ax—b=0。”

我们通过方程解的存在性来表达数字对 (a, b) 的性质

ax—b=0

（让我们再次回忆一下，我们只处理整数，因此只处理整数解）。其方程为

P(a, b, x) = 0,

其中 P 是三个变量 a、b、x 的多项式。

现在让我们介绍一个一般定义；如果在 m + n 个变量中存在这样的多项式，则有限数序列 (a₁, a2, …, aₘ) 的性质称为丢番图

P(a₁, a2, …, aₘ)，序列 (a₁, a2, …, aₘ) 具有我们的属性

*）这是文章的标题和确切的“地址”：Yu。 V.马蒂亚塞维奇。所列集合的丢番图属性，DAN SSSR，1970 年，第 191 卷，第 1 号。 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.$$

Matiyasviči 处理的数字对 $(a, b)$ 的性质是：

“$b$是斐波那契数

数字为$2a$”，即$b = \psi_{2a}$。

很明显，pairs 具有这个性质

$(0,0), (1,1), (2,3), (3,8)$

等等。马蒂亚斯维奇性质是丢番图的说法意味着存在一个多项式

$$Q(a, b, x_1, x_2, \dots, x_n)$$

当且仅当存在数字 $x_1, x_2, \dots, x_n$ 时，$b$ 将是一个带有数字 $2a$ 的斐波那契数

$$Q(a, b, x_1, x_2, \dots, x_n) = 0.$$

原则上，具有整数系数的多项式$Q$可以明确地写出。 Matiyasvich 没有这样做，甚至没有指出附加变量的数量 $n$ 是多少。

至于公式化定理的证明，正如已经说过的，这是相当初级的。马蒂亚斯维奇提到了 N. N. Vorobyov 的书《斐波那契数》中证明的一个引理，该书是为小学生编写的，而 A. I. Maltsev 的一本更科学的书中证明了一个结果，但也是初级的。在马蒂亚斯维奇的著作本身中，给出了十九个引理，但没有证明，但单独证明每个引理并不比小学生的典型问题更困难。困难只是找到实现最终目标的基本建议的特定组合。

2. 为什么这一切如此重要？

如果数学家确实需要多项式 $Q$ Matiyasvich 来进行任何计算，那么相信 Matiyasvich 不会懒得将其明确地写下来。但实际上，斐波那契数列的吸引力在于可以依次写出所有拥有此属性的对

$(0,0), (1,1), (2,3), (3,8), (4,21), (5,55), \dots$

由于这些对的多项式是无限的，因此将它们写出来的过程永远不会结束。但是我们有一个规则，根据这个规则，我们的对可以被放大地一个接一个地写出来

1. 只有具有 Matiyasvich 属性的对才会被写出，
2. 任何拥有马蒂亚斯维奇财产的人迟早都会被解雇。

有限数字序列$(a_1, a_2, \dots, a_m)$的属性（用更科学的语言来说，是“谓词”）被称为枚举，如果存在一条规则，允许通过机械地应用该规则，获得一个又一个始终具有给定属性的序列，而且，以这样的方式，任何序列

41

拥有这个属性的房产迟早会得到。

从现代的角度来看，马蒂亚斯维奇斐波那契数定理最重要的结论是

定理 1. 有限数序列的任何枚举性质都是丢番图。

在 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,$$

*) 有关希尔伯特问题的更多详细信息，请参阅 D. Hilbert, “Mathematical Problems”, “Science”, 1969 一书。

和方程

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

无整数解。

现在让我们请希尔伯特本人发言：

“给定一个具有任意数量的未知数的任意丢番图方程……；我们需要指出一种通用方法，可以使用以下过程在有限数量的步骤中找出我们是否有给定的整数解方程……”。

希尔伯特显然确信他正在寻找的通用方法是存在的，唯一的问题就是找到它。为了寻找这种方法花费了很多努力，但没有获得令人鼓舞的结果。

任意方程的整数解问题可以很容易地简化为自然（整数非负）解问题。此外，不难证明将我们限制在不高于四次的丢番图方程就足够了。对于阶数不高于二阶的丢番图方程，找到了所寻求的通用方法，但三阶方程不再输入任何数字。

由于在这个方向上的失败，人们怀疑希尔伯特公式应该找到的一般方法根本不存在！类似性质的许多其他问题也出现了类似的情况。然而，找到所需的通用方法是一回事——这里只要提出这个方法并直接验证它是否满足希尔伯特提出的条件就足够了。

但为了证明解决一系列问题的某种方法不存在，就必须对这个通用方法是什么、如何以及通过什么手段来实现给出一个准确的定义。

三十年代初，相应的定义得到扩展

42

美国科学家丘奇和英国科学家泰里格著作中的书呆子。这些定义为算法理论奠定了基础。回顾所走过的道路，数学家们应该感谢希尔伯特十个问题，因为它成为了这一理论创立的动力之一。

在算法理论的框架内，得到了我们在上一段中使用的“可枚举属性”概念的精确定义。

事实证明，根据有限数列的任何枚举性质的丢番图性质，它遵循

定理 2. 不可能有一个通用方法（算法）可以让我们确定任何给定的丢番图控制是否有整数解。

Matiyasevich 来自他关于一对数 (a, b) 特殊性质的丢番图性质的定理

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

推导了定理 1 的证明，众所周知，从中得出定理 2，即希尔伯特十个问题的负解。

为了最终理解所说的一切，你只需要清楚地了解什么是“算法”（解决无限系列问题的通用方法）和什么是“可枚举属性”（枚举谓词）。但这已经是一个困难得多的话题了。

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 本质上是递归的。让我们首先对函数 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。最后，通过对函数S(n)=n+1和φ(n)=2n应用代入运算来获得函数φ(n)： φ(n)=S(φ(n))=S(2n)=2n+1。

2. 如果自然数集合 M 与某个原始递归函数的值集合一致，则该集合 M 称为枚举集合。

例如，偶数集合是可枚举的，因为它是原始递归函数 φ(n)=2n 的值集合。奇数的集合与原始递归函数φ(n)=2n+1的值的集合重合，并且也是可枚举的。

3. 如果集合 M 与其补集 N - M 一起可枚举（其中 N 是所有自然数的集合），则该集合 M 称为可判定的。

特别是可解的数字集，因为它及其补码（奇数集）是可枚举的。

4. 存在可枚举但不可判定的集合。

可以给出这样一个集合的具体示例，但是相应的构造在技术上太复杂，无法在该评论的框架内执行。

现在令其为一组 M 个自然数。人们可能会问是否存在一种通用方法，给定每个正整数 n，在有限数量的步骤中确定该 n 是否属于集合 M。算法理论（Church 理论）的主要立场指出，当集合 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$再次满足所需的属性。 Terer 只需构造方程 $P(u, v, x_1, \dots, x_k) = 0$，当且仅当 $v = \varphi_u$ 时，该方程才有自然解 - 其余部分基于 Julia Robinson 的结果！为此，只需构造一个变量 $u, v, x_1, \dots, x_k$ 的微分方程组 $P_1 = 0, \dots, P_n = 0$，当且仅当 $v = \varphi_u$ 时，该方程组才有解 - 该方程组与唯一的方程 $P_1^2 + \dots + P_n^2 = 0$ 具有完全相同的解。

这是 Matiyasevich 获得所需方程组的形式：

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$，Matiyasevich 使用了序列$\{\varphi_k\}$的以下特征属性：

一对条件$x < y$和$x^2 - 3xy + y^2 = 1$相当于存在$k$使得$x = \varphi_k$和$y = \varphi_{k+1}$。

我们建议感兴趣的读者尝试证明这种等价性。

让我们在结论中指出，所找到的十个问题的解决方案具有许多有趣的后果，其中，也许最有效的是：您可以指定一个特定的线性多项式，其正值的集合与所有素数的集合一致！

数学科学创下了服务器和光荣的成就。

任务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.$$

由于印刷厂的错误，«Kvant»第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}$$