Exploring Hilbert's Tenth Problem in Subrings of Rationals 🧮

"Hilbert's Tenth Problem for Subrings of the Rational Numbers" Russell Miller (Queens College, City University of New York (CUNY), USA) This talk has been given in the KGRC research seminar at the Kurt Gödel Research Centre, Universität Wien on November 15, 2018. The slides for this talk are available at https://drive.google.com/file/d/131cibgjA2dN2nwoFVdWldvDnXvqGZIHr/view?usp=sharing Abstract When considering subrings of the field $\mathbb Q$ of rational numbers, one can view Hilbert's Tenth Problem as an operator, mapping each set $W$ of prime numbers to the set $HTP(R_W)$ of polynomials in $\mathbb Z[X_1,X_2,\ldots]$ with solutions in the ring $R_W=\mathbb Z[W^{-1}]$. The set $HTP(R_{\emptyset})$ is the original Hilberts Tenth Problem, known since 1970 to be undecidable. If $W$ contains all primes, then one gets $HTP(\mathbb Q)$, whose decidability status is open. In between lie the continuum-many other subrings of $\mathbb Q$. We will begin by discussing topological and measure-theoretic results on the space of all subrings of $\mathbb Q$, which is homeomorphic to Cantor space. Then we will present a recent result by Ken Kramer and the speaker, showing that the HTP operator does not preserve Turing reducibility. Indeed, in some cases it reverses it: one can have $V<_T W$, yet $HTP(R_W) <_T HTP(R_V)$. Related techniques reveal that every Turing degree contains a set $W$ which is \em{HTP-complete}, with $W\leq_1 HTP(R_W)$. On the other hand, the earlerer results imply that very few sets $W$ have this property: the collection of all HTP-complete sets is meager and has measure $0$ in Cantor space.