FG1 Seminar talk
Undecidability of algebraic integer rings
Given a ring A, we consider the following decision problem.
- Input : A first-order formula in the language of rings +, -, *, 0, 1.
- Output : Yes if the formula is satisfied in A, no otherwise.
We also consider the problem restricting to positive existential first order formulae, and to the existence of roots to a polynomial (also called Hilbert tenth problem).
For example Tarski (1951) proved that the first-order theory of the ring of real numbers is decidable. Similarly the first-order theory of the ring of complex numbers is decidable. On the other hands the first order theory of the ring of integers is undecidable. The Hilbert tenth problem is undecidable for Z (Matiyasevich 1970, and also Robinson, Davis, and Putman).
Julia Robinson (1959) proved that the algebraic integer ring of every extension of finite degree of the rationals has undecidable first order theory. For example the ring of Gaussian integers ( a+ib, a,b integers) has undecidable first order theory. Note that this ring has also undecidable Hilbert tenth problem)
For infinite algebraic extensions, few examples are known. The ring of totally real algebraic integers has undecidable first-order theory (Robinson 1962). The ring of all algebraic integers has decidable first-order theory (van den Dries 1988)
Vidaux and Videal (2016), using the tools constructed by Julia Robinson, noticed that for every field K, with the Northcott property, the algebraic integer ring of K has undecidable first-order theory.
We will give a new family of infinite extensions of the rationals such that their rings of algebraic integers have undecidable first-order theory. The construction is based on CM fields, and the main tool used is the computation of the Julia Robinson's numbers of those fields.
(joint work with Ranieri)