We prove that Hilbert's Tenth Problem over $\mathbb{N}$ remains undecidable when restricted to cubic equations (degree $\leq 3$), resolving the open case $\delta = 3$ identified by Jones (1982) and establishing sharpness against the decidability barrier at $\delta = 2$ (Lagrange's four-square theorem). For any consistent, recursively axiomatizable theory $T$ with G\"odel 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 $\beta$-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.
翻译:暂无翻译