The Hilbert's-tenth-problem operator (Q2414521)

The authors introduce a Hilbert's-tenth-problem operator on subsets of \(\mathbb{N}\), which maps every set of primes \(W\) to the polynomial subring \[\mathrm{HTP}(W) = \{ p \in \mathbb{Z}_W[x_1,x_2,\ldots]:\ \exists \mathbf{\bar{a}} \in \mathbb{Z}_W^n\ \ p(\mathbf{\bar{a}})=0 \}\] where \(\mathbb{Z}_W = \mathbb{Z} \left[ \frac{1}{p}: p \in W \right]\). This generalises Hilbert's original tenth problem, which is to determine whether \(\mathrm{HTP}(\emptyset)\) is computable. Famously, \textit{Yu. V. Matiyasevich} [Sov. Math., Dokl. 11, 354--358 (1970; Zbl 0212.33401); translation from Dokl. Akad. Nauk SSSR 191, 279--282 (1970)], \textit{M. Davis} et al. [Ann. Math. (2) 74, 425--436 (1961; Zbl 0111.01003)] showed that \(\mathrm{HTP}(\emptyset)\) is not computable; in fact, it is Turing equivalent to \(\emptyset'\). The full result was that \(\emptyset'\) is Diophantine in \(\mathrm{HTP}(\emptyset)\), i.e. there is a polynomial \(p \in \mathbb{Z}[x,y_1,\ldots,y_n]\) such that \[b \in \emptyset' \iff p(b,y_1,\ldots,y_n) \in \mathrm{HTP}(\emptyset)\] The authors show in \S3 that \(\emptyset\) is rare in this sense: the collection of \(W \subseteq \texttt{Primes}\) such that \(W'\) is not Diophantine in \(\mathrm{HTP}(W)\) has Lebesgue measure 1, and is comeager. In \S5, the authors study the computability properties of the \(\mathrm{HTP}\) operator, using tools from number theory. Some such properties include: that \(W \oplus\, \mathrm{HTP}(\texttt{Primes})\ \leq_\mathrm{T}\ \mathrm{HTP}(W)\ \leq_\mathrm{T}\ W'\); if \(W\) is c.e., then \(\mathrm{HTP}(W)\) is c.e.; and that \(\mathrm{HTP}(\emptyset)\, \equiv_\mathrm{T}\, \mathrm{HTP}(\emptyset')\). Using priority arguments, the authors exhibit a c.e. set \(U \subseteq \texttt{Primes}\) such that \(\mathrm{HTP}(U)'\, \equiv_\mathrm{T}\, \mathrm{HTP}(\texttt{Primes} \setminus U)\). As a corollary, they show the \(\mathrm{HTP}\) operator does not preserve Turing reducibility: there are sets \(D\, <_\mathrm{T}\, E\) such that \(\mathrm{HTP}(D)\, >_\mathrm{T}\, \mathrm{HTP}(E)\).