🔢 mathematics

An AI Proof of 18-Variable Undecidability for Diophantine Equations over $\mathbb Z[i]$

本文提出了一种由人工智能生成的证明，证明了高斯整数上丢番图方程的可解性是不可判定的，且仅需 18 个变量，通过优化的变量节省技术，改进了 Matiyasevich 和 Sun 之前提出的 20 个变量的界限。

原作者： Yuchen Ding, Junfeng Li

发布于 2026-06-12

📖 1 分钟阅读🧠 深度阅读

原作者： Yuchen Ding, Junfeng Li

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

大局观：这个“无法破解的谜题”

想象你有一个巨大的、神奇的拼图盒。盒子里有一个复杂的方程（一个数学问题），其中包含许多未知数（变量）。你的目标是弄清楚：“这个方程是否有解？”

长期以来，数学家们已经知道，如果你拥有足够多的变量，这个问题将变得无法用计算机程序来回答。这就像试图编写一本规则手册，来告诉你是否每一个可能的迷宫都有出口；最终，迷宫会变得如此扭曲，以至于没有任何规则手册能涵盖所有情况。

这篇论文是关于一种特定类型的拼图盒——高斯整数（形式为 $a + bi $的数字，其中$ i$ 是 -1 的平方根）。作者 Yuchen Ding 和 Junfeng Li 利用人工智能证明了，如果你的拼图盒有 18 个未知数，那么就不存在一个能够始终告诉你是否存在解的计算机程序。

前人的记录：20 个变量

在此之前，已知的最佳结果（由数学家 Matiyasevich 和 Sun 提出）是，你需要 20 个未知数才能让这个谜题变得无法破解。他们有一套特定的“配方”来构建这些无法破解的谜题。

本文的作者说：“我们可以用更少的零件来完成。”他们成功地将这个配方从 20 个零件缩减到了 18 个。

他们是如何做到的：两个聪明的技巧

要理解他们是如何节省了两个变量的，请想象你正在建造一台机器，用来测试一个数字在复数世界中是否为“实数”（整数）。

技巧 1：“无需额外杯子”策略

旧方法：
想象你有一个需要混合原料的配方，但说明书中涉及分数。为了让数学运算在计算机上运行，你通常需要一个额外的杯子（一个新的变量）来清除分母（分数的底部），使一切都变成整数。这个额外的杯子占据了你 20 个变量的限额。

新方法：
作者意识到他们不需要那个额外的杯子。他们没有通过添加一个新变量来清理分数，而是直接向现有的原料添加了两条严格的规则。

类比： 与其带一个新桶来接漏出的液体，不如直接把现有桶的盖子拧紧，这样就不会漏出来了。
结果： 他们通过强制数学运算保持“干净”，而不需要辅助变量，从而节省了一个变量。

技巧 2：“魔法钥匙”小工具

旧方法：
在旧的配方中，为了确保某个特定数字不为零（这对于谜题的运作至关重要），他们需要两个独立的变量作为“安全检查”。这就像使用两把不同的钥匙来解锁一扇门，仅仅是为了确保门没有被卡住。

新方法：
作者发明了一个特殊的“魔法钥匙”小工具。他们创建了一个特定的公式： $(2R + 1)(3R + 1)$ 。

神奇之处： 无论你代入什么数字，这个公式永远不会等于零。然而，如果你有一个你想“检查”的非零数字，你可以找到一个 $R$ 的值，使得这个公式能被该数字整除。
节省之处： 因为这一个公式就能完成两个独立的安全性检查，所以他们只需要一个变量（ $R$ ）而不是两个。
结果： 他们节省了第二个变量。

最终计数

通过结合这两个技巧，他们降低了证明谜题无法破解所需的总未知数数量：

10 个用于主谜题的变量（来自前人的工作）。
3 个用于第一个“整数测试”（检查数字是否为整数）的变量。
3 个用于第二个“整数测试”的变量。
1 个用于“组合”步骤的变量。
1 个用于“魔法钥匙”小工具的变量。
总计：18 个变量。

这意味着什么

这篇论文证明了，对于任何计算机程序，在处理问题变得无法解决之前，变量的数量是存在极限的。

之前： 极限已知为 20。
现在： 极限被证明为 18（或者可能更低，但 18 是新的确认底线）。

作者强调，他们并没有找到绝对最低的数字（也许是 17 或 16），但他们成功地利用这两个特定的“空间节省”技巧，将门槛从 20 降低到了 18。

总结

把它想象成在为旅行打包。旧的规则说：“你需要 20 个行李箱来装所有的衣服。”这些作者观察了衣服，发现他们可以折叠得更紧凑（技巧 1），并且可以使用压缩袋（技巧 2），然后证明了：“实际上，你只需要 18 个行李箱。”

这并不意味着旅行变得更容易了；它只是意味着“不可能”的阈值比我们之前认为的需要更少的资源就能达到。

技术摘要：关于 $\mathbb{Z}[i]$ 上丢番图方程 18 变量不可判定性的 AI 证明

问题陈述
本文研究了高斯整数环 $\mathbb{Z}[i]$ 上的希尔伯特第十问题。该问题旨在寻找一种算法，用以判定给定环上的任意多项式方程是否存在解。虽然 Matiyasevich, Davis, Putnam, 和 Robinson 的定理已经确立了该问题在整数 $\mathbb{Z}$ 上的不可判定性，但一个自然的改进方向是研究维持不可判定性所需的最小未知量数量。此前，Matiyasevich 和 Sun 的工作已确立了在 $\mathbb{Z}[i]$ 上对于 20 个未知量时仍具有不可判定性。本文通过将这一界限从 20 个变量减少到 18 个变量，提出了一个证明。

方法论与框架
该证明保留了 Matiyasevich 和 Sun 建立的一般框架，该框架依赖于三个核心组件：

Sun 的固定变量定理： 利用一个递归可枚举但非递归的集合 $A \subseteq \mathbb{N}$ 以及一个多项式 $P(Z_0, \dots, Z_{10})$ ，使得 $A$ 中的成员资格等价于存在整数解 $P(a, z_1, \dots, z_{10}) = 0$ 且 $z_{10} \neq 0$ 。
有理整数的丢番图测试： 使用特定的多项式测试（引理 3）来判定 $\mathbb{Z}[i]$ 中的元素是否为实际的有理整数。
有理性判据： 在 $\mathbb{Q}(i)$ 上应用一个判据（引理 4），基于特定构造和的有理性来强制变量为有理整数。

作者通过引入两个特定的修改来完成从 20 个变量到 18 个变量的缩减：

关键贡献与技术修改

消除分母清除变量：
在 20 变量的构造中，引入了一个辅助变量用于在应用有理性判据时清除分母。作者使用两个直接施加在变量 $Z_1, \dots, Z_{10}$ 上的整数条件取代了该变量。
令 $Y = 2 \prod_{k=1}^{10} (3Z_k + 1)$ 。作者不再添加变量来清除分母，而是施加条件：
$Y^{10} \in \mathbb{Z} \quad \text{且} \quad Y^{11} + \sum_{k=1}^{10} Z_k Y^{10-k} \in \mathbb{Z}.$
由于 $Y \neq 0$ ，这些条件确保了量 $Y + \sum Z_k Y^{-k}$ 是一个有理数。通过有理性判据，这强制所有 $Z_k$ 为有理整数。这一修改节省了一个变量。
通过单变量小工具吸收非零条件：
此前的构造需要两个变量来强制执行非零条件（具体针对乘积 $Z_{10}V_0V_1$ ）。作者引入了一个单变量多项式小工具 $Q(R) = (2R + 1)(3R + 1)$ 。

性质： $Q(R)$ 在 $\mathbb{Z}[i]$ 上永不为零。此外，对于每一个非零整数 $n$ ，都存在一个整数 $R$ 使得 $n \mid Q(R)$ 。
应用： 该小工具被集成到“关系组合引理”（引理 2）中。作者不再使用单独的方程来强制非零，而是将条件吸收进单个方程 $f(C_0, C_1, N, Q(R), M) = 0$ 中。如果 $N=0$ ，则方程简化为 $Q(R)^4 = 0$ ，这在 $\mathbb{Z}[i]$ 中是不可能的。因此，该方程隐式地强制 $N \neq 0$ ，而无需额外的变量。这一修改节省了第二个变量。

变量计数分解
最终的系统恰好使用了 18 个变量：

$Z_1, \dots, Z_{10}$ ：来自 Sun 固定变量输入的 10 个变量。
$V_0, X_0, Y_0$ 以及 $V_1, X_1, Y_1$ ：用于对 $U_0 = Y^{10}$ 和 $U_1 = W$ （其中 $W$ 由和导出）进行整数测试的两组各 3 个变量。
$M$ ：来自关系组合引理的组合变量。
$R$ ：来自非零小工具的单个变量。
总计： $10 + 3 + 3 + 1 + 1 = 18$ 。

主要结果
本文证明了 定理 1：不存在算法可以判定系数在 $\mathbb{Z}$ 中的任意多项式方程 $F(X_1, \dots, X_{18}) = 0$ 在 $\mathbb{Z}[i]^{18}$ 中是否有解。

证明表明，非递归集合 $A$ 的成员资格可以用一个在 $\mathbb{Z}[i]$ 上具有 18 个未知量的单个多项式方程来表示。根据引理 1，由构造导出的有限方程组可以合并为一个单一的多项式方程而不引入新变量，同时保持其整数系数。

意义与主张
作者指出，这一结果通过将变量数量减少两个，改进了 Matiyasevich 和 Sun 的 20 个未知量定理。论文明确指出，这并不声称达到了绝对最优；若要进一步降低计数（例如降至 17），则需要额外的改进，例如更小的整数测试、共享整数条件的见证者、更强的固定变量输入或不同的组合机制。这项工作是在建立的高斯整数丢番图不可判定性框架内的技术性精炼。