Paperlane

no. 14 · Friday 13 November 2026

Diophantine equations in matrix rings and semirings

Mihai Prunescu

math.LO · v2

Abstract

For every fixed positive integer $n$, we prove that it is undecidable whether a single noncommutative polynomial equation with scalar integer coefficients has a solution in $M_n(\mathbb N)$ or in $M_n(\mathbb Z)$. An integral range calculation for central polynomials yields a common reduction from integer Diophantine equations; the single-equation and finite-system problems are computably enumerable complete. The same polynomials have exact range $\mathbb Q I_n$ on rational, even nonnegative rational, arguments. Consequently, the single-equation and finite-system problems over $M_n(\mathbb Q)$ are computably many-one equivalent to Hilbert's tenth problem over $\mathbb Q$, unconditionally. The rational undecidability claims reported in 2026 by OpenAI and Zhi-Wei Sun imply rational-matrix undecidability, with at most $86$, $87$, and $88$ matrix variables in dimensions $1$, $2$, and at least $3$, respectively. An explicit Diophantine definition of $\mathbb Z$ in $\mathbb Q$ reported by the project coordinated by Elliot Glazer further gives completeness among computably enumerable problems. These consequences of recent arithmetic claims are stated conditionally.

fields
Logic, Number Theory
pdf ↗ page arXiv:2507.15265 ↗