2018 seminar talk: 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 HTP-complete, with $W’\leq_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.
There is a video recording of this talk on YouTube.
Slides are available, too.