HTP-complete rings of rational numbers

Russell Miller

Published 2019-07-06Version 1

For a ring $R$, Hilbert's Tenth Problem $HTP(R)$ is the set of polynomial equations over $R$, in several variables, with solutions in $R$. We view $HTP$ as an enumeration operator, mapping each set $W$ of prime numbers to $HTP(\mathbb Z[W^{-1}])$, which is naturally viewed as a set of polynomials in $\mathbb Z[X_1,X_2,\ldots]$. It is known that for almost all $W$, the jump $W'$ does not $1$-reduce to $HTP(R_W)$. In contrast, we show that every Turing degree contains a set $W$ for which such a $1$-reduction does hold: these $W$ are said to be "HTP-complete." Continuing, we derive additional results regarding the impossibility that a decision procedure for $W'$ from $HTP(\mathbb Z[W^{-1}])$ can succeed uniformly on a set of measure $1$, and regarding the consequences for the boundary sets of the $HTP$ operator in case $\mathbb Z$ has an existential definition in $\mathbb Q$.