Computability problems in number theory
City University of New York
We will consider several number-theoretic questions which arise from computable model theory. One of these, recently solved by Poonen, Schoutens, Shlapentokh, and the speaker, involves attempting to “embed” a graph into a field: given a graph, one wishes to construct a field with the exact same computable-model-theoretic properties as the graph. (For instance, the automorphisms of the graph should correspond to the automorphisms of the field, by a bijective functorial correspondence which preserves the Turing degree of each automorphism.) Another arises out of consideration of Hilbert’s Tenth Problem for subrings of the rationals: we ask for subrings in which Hilbert’s Tenth Problem is no harder than it is for the rationals themselves. This is known for semilocal subrings, and Eisenträger, Park, Shlapentokh and the speaker have shown that it holds for certain non-semilocal subrings as well, but it remains open whether one can invert “very few” primes and still have it hold. We will explain this problem and discuss the number-theoretic question which arises out of it.
Russell Miller is professor of mathematics at Queens College of CUNY and also at the CUNY Graduate Center. He conducts research in mathematical logic, especially computability theory and its interaction with other areas of mathematics, as in computable model theory. He received his doctorate from the University of Chicago in 2000, as a student of Robert Soare, and subsequently held a postdoctoral position at Cornell University until 2003, when he came to CUNY.