2025-11-14T19:52:11.648476

Cubic Incompleteness: Hilbert's Tenth Problem Over $\mathbb{N}$ Starts at $Î´=3$

Rosko

We prove that Hilbert's Tenth Problem over $\mathbb{N}$ remains undecidable when restricted to cubic equations (degree $\leq 3$), resolving the open case $Î´= 3$ identified by Jones (1982) and establishing sharpness against the decidability barrier at $Î´= 2$ (Lagrange's four-square theorem). For any consistent, recursively axiomatizable theory $T$ with GÃ¶del sentence $G_T$, we effectively construct a single polynomial $P(x_1, \ldots, x_m) \in \mathbb{Z}[\mathbf{x}]$ of degree $\leq 3$ such that $T \vdash G_T$ if and only if $\exists \mathbf{x} \in \mathbb{N}^m : P(\mathbf{x}) = 0$. Our reduction proceeds through four stages with explicit degree and variable accounting. First, proof-sequence encoding via Diophantine $Î²$-function and Zeckendorf representation yields $O(KN)$ quadratic constraints, where $K = O(\log(\max_i f_i))$ and $N$ is the proof length. Second, axiom--modus ponens verification is implemented via guard-gadgets wrapping each base constraint $E(\mathbf{x}) = 0$ into the system $u \cdot E(\mathbf{x}) = 0$, $u - 1 - v^2 = 0$, maintaining degree $\leq 3$ while introducing $O(KN^3)$ variables and equations. Third, system aggregation via sum-of-squares merger $P_{\text{merged}} = \sum_{i} P_i^2$ produces a single polynomial of degree $\leq 6$ with $O(KN^3)$ monomials. Fourth, recursive monomial shielding factors each monomial of degree exceeding $3$ in $O(\log d)$ rounds via auxiliary variables and degree-$\leq 3$ equations, adding $O(K^3 N^3)$ variables and restoring degree $\leq 3$. We provide bookkeeping for every guard-gadget and merging operation, plus a unified stage-by-stage variable-count table. Our construction is effective and non-uniform in the uncomputable proof length $N$, avoiding any universal cubic equation. This completes the proof that the class of cubic Diophantine equations over $\mathbb{N}$ is undecidable.

academic

Cubic Incompleteness: Hilbert's Tenth Problem Over $\mathbb{N}$ Starts at $\delta=3$

基本信息

论文ID: 2510.00759
标题: Cubic Incompleteness: Hilbert's Tenth Problem Over $\mathbb{N}$ Starts at $\delta=3$
作者: Milan Rosko (University of Hagen, Germany)
分类: math.LO (数理逻辑), cs.CC (计算复杂性), cs.LO (计算机科学逻辑)
发表时间: 2025年10月 (第三版预印本)
论文链接: https://arxiv.org/abs/2510.00759v3

摘要

本文证明了希尔伯特第十问题在自然数域 $\mathbb{N}$ 上对于三次方程(度数 $\leq 3$ )仍然是不可判定的，解决了Jones(1982)提出的 $\delta=3$ 开放问题，并确立了相对于 $\delta=2$ 可判定性屏障(拉格朗日四平方定理)的尖锐性。对于任何一致的递归公理化理论 $T$ 及其哥德尔句 $G_T$ ，作者有效构造了一个度数 $\leq 3$ 的单一多项式 $P(x_1,\ldots,x_m) \in \mathbb{Z}[\mathbf{x}]$ ，使得 $T \vdash G_T$ 当且仅当 $\exists \mathbf{x} \in \mathbb{N}^m : P(\mathbf{x}) = 0$ 。

研究背景与动机

问题背景

希尔伯特第十问题询问是否存在算法判定任意丢番图方程在整数域上是否有解。MRDP定理(Matiyasevich-Robinson-Davis-Putnam)已证明该问题在整数域 $\mathbb{Z}$ 上不可判定。然而，对于自然数域 $\mathbb{N}$ 和不同度数的限制，问题的可判定性边界一直是开放问题。

研究动机

度数边界的精确刻画: Jones(1982)已证明度数4的方程不可判定，度数2的方程可判定(基于拉格朗日四平方定理)，但度数3的情况未解决。
理论完整性: 确定不可判定性的精确起始点对于理解丢番图方程的计算复杂性至关重要。
技术挑战: 在保持度数限制的同时编码证明验证过程需要精巧的数学技术。

现有方法局限性

传统MRDP约化产生度数≥4的方程
朴素的约化技术会破坏度数界限
缺乏系统的度数管理框架

核心贡献

解决开放问题: 证明了 $\delta=3$ 情况下希尔伯特第十问题在 $\mathbb{N}$ 上不可判定，填补了Jones(1982)留下的空白
构造性证明: 提供了从可证性到三次丢番图方程可解性的有效约化
技术创新:
- 引入"守卫小工具"(guard-gadgets)框架保持度数≤3
- 开发递归单项式屏蔽技术进行度数约化
- 建立基于Zeckendorf表示的无进位算术编码
精确复杂性分析: 提供了每个约化阶段的变量和度数的明确计数