Cubic Incompleteness: Hilbert's Tenth Problem Over $\mathbb{N}$ Starts at $δ=3$
By: Milan Rosko
Potential Business Impact:
Computers can't solve all math puzzles.
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.
Similar Papers
Cubic incompleteness: Hilbert's tenth problem begins at degree three
Logic
Proves some math problems can never be solved.
Cubic incompleteness: Hilbert's tenth problem begins at degree three
Logic
Proves some math problems can never be solved.
Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz
Computational Complexity
Solves hard math problems by finding common roots.