Russell G. Miller: Hilbert’s Tenth Problem for Subrings of the Rational Numbers

Talk held by Russell Miller (Queens College, City University of New York (CUNY), USA) at the KGRC seminar on 2018-11-15.


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 Hilbert’s 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 \emph{HTP-complete}, with $W’ \le_1 HTP(R_W)$. On the other hand, the earlier 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.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.

This site uses Akismet to reduce spam. Learn how your comment data is processed.