Title:
Computable Procedures for Fields
Abstract:
Effectiveness questions for fields date back many centuries:
the traditional problem of finding roots of a polynomial has a long
and honorable history. With the development of computability theory,
we have come to use Turing machines as a formalization of the notion
of an effective procedure. Some longstanding questions about
fields now have been answered; others remain open, including the very
basic question, known as \emph{Hilbert's Tenth Problem for $\mathbb{Q}$},
of whether it is decidable which diophantine equations (in several variables)
have solutions in the field $\mathbb{Q}$ of rational numbers. This tutorial
will introduce and explore such questions and answers. Complexity-theoretic versions of many of the same questions also exist,and may be mentioned at times, but the focus will be on pure computability.
The initial question of finding a root of a polynomial (in a single variable) leads quickly into the larger question of whether a given field contains such a root, and then on to the reducibility of polynomials over a given field: does a given polynomial factor into the product of two simpler polynomials? Michael Rabin's theorem from 1960 describes a construction of the algebraic closure of a given computable field and connects it with the decidability of the reducibility
question, as well as the decidability of the existence of a root. We will
review Rabin's theorem in detail.
From there, the tutorial will bifurcate: part of the remainder will be devoted
to fields of infinite transcendence degree over the prime subfield;
the rest to algebraic field extensions of the prime subfield. We will mostly
stick to characteristic $0$, so that the prime subfield is $\mathbb{Q}$.
A theorem by Poonen, Schoutens, Shlapentokh, and the speaker, from
2018, shows that fields of countable transcendence degree over $\mathbb{Q}$
form a class of structures fully as difficult as any other class of countable
structures in any signature, and we will discuss how this is formalized and proven.
Algebraic extensions of $\mathbb{Q}$, on the other hand, are simpler
and more tractable, and we will introduce intriguing recent results about
the general tendencies of these fields -- both computable and noncomputable --
in which one puts a topology on the set of all such fields and uses Baire-category techniques to determine which properties are prevalent among these fields.