# A topological approach to undefinability
in algebraic extensions of $\mathbb{Q}$

Kirsten Eisenträger  Department of Mathematics, The Pennsylvania State
University, University Park, PA 16802, USA<EMAIL_ADDRESS>,  Russell Miller
Department of Mathematics, Queens College – City University of New York, 65-30
Kissena Blvd., Flushing, NY 11367 USA Ph.D. Programs in Mathematics and
Computer Science, Graduate Center - City University of New York, 365 Fifth
Avenue, New York, NY 10016 USA<EMAIL_ADDRESS>,  Caleb Springer
Department of Mathematics, The Pennsylvania State University, University Park,
PA 16802, USA<EMAIL_ADDRESS>and  Linda Westrick  Department of Mathematics,
The Pennsylvania State University, University Park, PA 16802, USA
<EMAIL_ADDRESS>
###### Abstract.

In this paper we investigate the algebraic extensions $K$ of $\mathbb{Q}$ in
which we cannot existentially or universally define the ring of integers
$\mathcal{O}_{K}$. A complete answer to this question would have important
consequences. For example, the existence of an existential definition of
$\mathbb{Z}$ in $\mathbb{Q}$ would imply that Hilbert’s Tenth Problem for
$\mathbb{Q}$ is undecidable, resolving one of the biggest open problems in the
area. However, a conjecture of Mazur implies that the integers are not
existentially definable in the rationals.

Although proving that an existential definition of $\mathbb{Z}$ in
$\mathbb{Q}$ does not exist appears to be out of reach right now, we show that
when we consider all algebraic extensions of $\mathbb{Q}$, this is the
generally expected outcome. Namely, we prove that in most algebraic extensions
of the rationals, the ring of integers is not existentially definable. To make
this precise, we view the set of algebraic extensions of $\mathbb{Q}$ as a
topological space homeomorphic to Cantor space. In this light, the set of
fields which have an existentially definable ring of integers is a meager set,
i.e. is very small.

On the other hand, by work of Koenigsmann and Park, it is possible to give a
universal definition of the ring of integers in finite extensions of the
rationals, i.e. in number fields. Still, we show that their results do not
extend to most algebraic infinite extensions: the set of algebraic extensions
of $\mathbb{Q}$ in which the ring of integers is universally definable is also
a meager set.

##  1\. Introduction

The current paper started as an attempt to characterize the subfields $K$ of
$\overline{\mathbb{Q}}$ whose ring of integers $\mathcal{O}_{K}$ is first-
order or existentially definable in $K$, with special attention to the cases
where definability fails. If existential definability holds in this context,
it assists a standard reduction argument that proves undecidability results
for generalizations of Hilbert’s Tenth Problem, which, in its original form,
asked for an algorithm that decides, given a polynomial equation
$f(x_{1},\dots,x_{n})=~{}0$ with coefficients in the ring $\mathbb{Z}$ of
integers, whether there is a solution with $x_{1},\dots,x_{n}\in\mathbb{Z}$.
Matiyasevich [8], building on earlier work by Davis, Putnam, and Robinson [1],
proved that no such algorithm exists, i.e., Hilbert’s Tenth Problem is
undecidable. Since then, analogues of this problem have been studied by asking
the same question for polynomial equations with coefficients and solutions in
other recursive commutative rings. One of the most important unsolved
questions in this area is Hilbert’s Tenth Problem over the field of rational
numbers $\mathbb{Q}$, and more generally over number fields. If $\mathbb{Z}$
is existentially definable in $\mathbb{Q}$, then a reduction argument shows
that Hilbert’s Tenth Problem for $\mathbb{Q}$ must be undecidable.

However, if Mazur’s Conjecture holds, then $\mathbb{Z}$ is not existentially
definable in $\mathbb{Q}$. Proving this unconditionally currently appears to
be out of reach. In fact, it seems generally very difficult to prove
undefinability results for individual fields. One example of success is the
field of all totally real algebraic numbers $\mathbb{Q}^{\operatorname{tr}}$.
Fried, Haran and Völklein showed that its first-order theory is decidable [3],
while J. Robinson showed that the first-order theory of the ring of all
totally real integers $\mathbb{Z}^{\operatorname{tr}}$ is undecidable [16].
This difference in decidability implies that $\mathbb{Z}^{\operatorname{tr}}$
cannot be first-order definable in the field $\mathbb{Q}^{\operatorname{tr}}$.
Another example is the ring $\overline{\mathbb{Z}}$ of all algebraic integers
inside $\overline{\mathbb{Q}}$, which is undefinable by the strong minimality
of $\overline{\mathbb{Q}}$. In both examples, the facts used for proving
undefinability are not remotely close to necessary conditions for
undefinability. Instead, they simply reflect the available pathways for
unconditionally proving undefinability in a limited number of cases.

While it is still an open question whether $\mathbb{Z}$ is existentially
definable in $\mathbb{Q}$, it is possible to give a first-order definition of
$\mathbb{Z}$ in $\mathbb{Q}$, i.e. a definition that uses both existential and
universal quantifiers. This was first done by J. Robinson [14], who
generalized this result to define the ring of integers $\mathcal{O}_{K}$
inside any number field $K$ [15]. Later, Rumely [17] was able to make the
definition of the ring of integers uniform across number fields. Robinson’s
definition was improved by Poonen [11] who gave a $\forall\exists$-definition
that in every number field $K$ defines its ring of integers. Following this,
Koenigsmann [5] proved that it is possible to give a universal definition of
$\mathbb{Z}$ in $\mathbb{Q}$, i.e. a definition that only involves universal
$(\forall)$ quantifiers, and Park extended his result to show that
$\mathcal{O}_{K}$ is universally definable in $K$ for every number field $K$
[10]. This raises the question of whether we can expect universal and first-
order definability to continue to hold for many infinite algebraic extensions
of $\mathbb{Q}$.

Currently, first-order definability results are only known for certain classes
of infinite extensions of the rationals. These are usually proved in order to
prove the first-order undecidability of certain infinite extensions via
reductions. For example, Videla proved the definability of the ring of
integers over certain infinite algebraic pro-$p$ extensions of $\mathbb{Q}$
[20], while Fukuzaki was able to define the ring of integers in infinite
extensions in which every finite subextension has odd degree and that satisfy
certain ramification conditions [4]. These results were further generalized by
Shlapentokh in [19], to which we refer readers for more extensive background
on known results for the first-order definability and decidability of infinite
algebraic extensions of $\mathbb{Q}$. In Shlapentokh’s framework, all known
examples of algebraic extensions of $\mathbb{Q}$ with first-order definable
rings of integers can be viewed as relatively small extensions which are
somehow “close” to $\mathbb{Q}$. On the other hand, although first-order
definability seems less likely for extensions which are similarly “far from”
$\mathbb{Q}$, very few such examples are known, as mentioned above.

In this paper, we take the perspective of considering all algebraic extensions
of $\mathbb{Q}$ simultaneously. From this vantage point, we prove that
$\mathcal{O}_{K}$ is both existentially and universally undefinable in $K$ for
“most” algebraic extensions $K$ of $\mathbb{Q}$. To make this notion precise,
we use the lens of a natural topology to view the set
$\operatorname{Sub}(\overline{\mathbb{Q}})$ of subfields of
$\overline{\mathbb{Q}}$ as a topological space in which every nonempty open
set is non-meager. The precise version of our theorem then can be written as
follows:

######  Theorem 1.1.

The set of algebraic extensions $K$ of $\mathbb{Q}$ for which
$\mathcal{O}_{K}$ is existentially or universally definable is a meager subset
of $\operatorname{Sub}(\overline{\mathbb{Q}})$.

In particular, there are uncountably many algebraic extensions $K$ of
$\mathbb{Q}$ for which the ring of integers $\mathcal{O}_{K}$ is neither
existentially nor universally definable in $K$. Moreover, the theorem remains
true when replacing $\operatorname{Sub}(\overline{\mathbb{Q}})$ with the
quotient space $\operatorname{Sub}(\overline{\mathbb{Q}})/\cong$, which only
considers fields up to isomorphism.

To prove this theorem, we study the existential definability of infinite sets
$Z\subseteq\mathbb{Q}$ whose complement is not thin, in the sense of Serre.
The necessary background of algebraic number theory, arithmetic geometry and
thin sets is recalled in Section 2. In order to prove the main theorem, we
introduce a notion of rank in Section 3 that formalizes which existential
formulas are the “simplest”. In particular, rank is a well-ordering of
existential formulas, so if $Z$ is existentially definable in $\mathbb{Q}$
over some field $L\subseteq\overline{\mathbb{Q}}$, then there is a formula of
minimal rank which does the job. By studying such minimal-rank formulas in
Section 4, we deduce a convenient normal form for existential definitions; see
Theorem 4.8. Finally, we introduce the topological spaces of
$\operatorname{Sub}(\overline{\mathbb{Q}})$ and
$\operatorname{Sub}(\overline{\mathbb{Q}})/\\!\cong$ in Section 5, and use the
normal form to deduce the main result via Hilbert’s Irreducibility Theorem. In
fact, the proof also leads to an algorithm which, given a basic open subset
$U\subseteq\operatorname{Sub}(\overline{\mathbb{Q}})$, produces a computable
field $L\in U$ in which the ring of integers $\mathcal{O}_{L}$ is neither
existentially or universally definable; see Theorem 5.11.

### Acknowledgements

This project began during a workshop at the American Institute of Mathematics
in May 2019. The authors wish to acknowledge useful conversations with Tom
Tucker. Eisenträger was partially supported by National Science Foundation
award CNS-1617802 and a Vannevar Bush Faculty Fellowship from the US
Department of Defense. Miller was partially supported by Grant # 581896 from
the Simons Foundation and by the City University of New York PSC-CUNY Research
Award Program. Springer was partially supported by National Science Foundation
award CNS-1617802. Westrick was partially supported by the Cada R. and Susan
Wynn Grove Early Career Professorship in Mathematics.

##  2\. Background from number theory and algebraic geometry

In this section, we will recall some of the basic facts that we will require
for fields, thin sets, and affine varieties. Readers can find additional
background in the books of Lang [6], Serre [18] and Liu [7], respectively.

###  2.1. Field extensions and the irreducibility of polynomials

In the material that follows, we will be presented with the following
question: Given number fields $F\subseteq K$, which field extensions of $F$
contain elements of the complement $K\setminus F$? This question is intimately
related to the irreducibility of polynomials. First, we recall a basic result
on the irreducibility of multivariable polynomials.

######  Lemma 2.1.

If $K/F$ is an extension of fields within a larger field $L$, and $z\in L$ is
algebraic over $F$ with $F(z)\cap K\neq F$, then the minimal polynomial $h(Z)$
of $f$ over $F$ must be reducible over $K$.

###### Proof.

By hypothesis $1<[F(z)\cap K:F]$, so

$[F(z):F(z)\cap K]<[F(z):F(z)\cap K]\cdot[F(z)\cap K:F]=[F(z):F].$

From this it follows that $h(Z)$ must factor over $F(z)\cap K$, so it
certainly also factors over the larger field $K$. ∎

The next proposition forms a kind of converse to Lemma 2.1 when $K/F$ is a
finite Galois extension. Given an algebraic function field
$E=\operatorname{Frac}(F[Y_{0},Y_{1},\ldots,Y_{m}]/(f))$ where $f\in
F[Y_{0},Y_{1},\ldots,Y_{m}]$ is an irreducible polynomial, the _constant
field_ of $E$ is the set of elements which are algebraic over $F$.

######  Proposition 2.2.

Let $F$ be a number field, and $K$ a finite Galois extension of $F$. If $m\geq
0$ and $f\in F[Y_{0},Y_{1},\ldots,Y_{m}]$ is an irreducible polynomial that
becomes reducible in $K[Y_{0},Y_{1},\ldots,Y_{m}]$, then the constant field of
$E=\operatorname{Frac}(F[Y_{0},Y_{1},\ldots,Y_{m}]/(f))$ is larger than $F$.
In particular, there is an element $z\in E\setminus F$ such that there is an
$F$-linear field embedding of $F(z)$ into $K$ with the image of $z$ lying in
$K\setminus F$.

###### Proof.

Assume without loss of generality that $Y_{m}$ appears nontrivially in $f$,
and write $L=F(Y_{0},Y_{1},\dots,Y_{m-1})$. We will view $E=L(\theta)$ for an
element $\theta$ in the algebraic closure $\overline{L}$ with minimal
polynomial $f$. Similarly consider $K$ to be an extension of $F$ inside
$\overline{L}$.

Suppose that $E$ contains no elements of $K\setminus F$. Then $E\cap K=L\cap
K=F$, and a basic theorem of Galois theory [6, Theorem 1.12] implies the
following because $K$ is a Galois extension of $F$:

$[EK:E]=[K:E\cap K]=[K:F]=[K:L\cap K]=[LK:L].$

Using the diamond written below, we deduce that $[E:L]=[EK:LK]$. Importantly,
these field extension degrees are also the degrees of the minimal polynomial
of $\theta$ over $L$ and $LK$, respectively.

This shows that $f$ remains irreducible over the field
${L=K(Y_{0},Y_{1},\dots,Y_{m-1})}$ as a polynomial in $Y_{m}$. We claim that
$f$ is actually irreducible as an element of the ring
$K[Y_{0},Y_{1},\dots,Y_{m}]$, which contradicts the hypothesis. To prove this,
it only remains to show that the coefficients of $f$ lying in
$K[Y_{0},\dots,Y_{m-1}]$ have no common factor; see [6, IV.2.3]. Clearly, as a
polynomial in $Y_{m}$, the coefficients of $f$ lying in $F[Y_{0},\dots,Y_{m}]$
have no common factor over $F$ because $f$ is irreducible over $F$. In fact,
this implies that the coefficients also have no common factor over any
algebraic extension of $F$ by the following lemma, which completes the proof.
∎

######  Lemma 2.3.

Let $F$ be a field and let $F^{\prime}$ be a separable extension. If
$f_{0},f_{1},\dots,f_{k}$ are a collection of polynomials in
$F[Y_{0},\dots,Y_{m}]$ with no common factor, then $f_{0},\dots,f_{k}$ also
have no common factor over the extension $F^{\prime}$.

###### Proof.

By writing $f_{0},\dots,f_{k}$ in terms of their irreducible factors, we can
reduce without loss of generality to the case of two irreducible polynomials
$f_{0},f_{1}\in F[Y_{0},\dots,Y_{m}]$. Indeed, for every irreducible factor
$p$ of $f_{0}$, there is a polynomial $f_{j}$ for $1\leq j\leq m$ which is not
divisible by $p$, and it suffices to show that the irreducible factors of
$f_{j}$ remain relatively prime to $p$ over the larger field $F^{\prime}$.

Notice that irreducible polynomials $f_{0}$ and $f_{1}$ are relatively prime
over $F$ if and only if $f_{0}f_{1}$ generates a radical ideal in
$F[Y_{0},\dots,Y_{m}]$, i.e. if and only if
$F[Y_{0},\dots,Y_{m}]/(f_{0}f_{1})$ is a reduced ring. The latter condition is
stable under separable field extensions, i.e.
$F^{\prime}[Y_{0},\dots,Y_{m}]/(f_{0}f_{1})$ is also reduced; see [7,
Proposition 3.2.7.(b)]. Therefore $f_{0}$ and $f_{1}$ have no common factors
over $F^{\prime}$. ∎

###  2.2. Dimensions of rings and affine varieties

We will require a usable notion of dimension, which can equivalently be viewed
as a geometric or algebraic phenomenon. In particular, there are related
notions of the dimension of a commutative ring $A$, and the dimension of the
associated topological space $\operatorname{Spec}A$ consisting of all prime
ideals of $A$ with the Zariski topology. In this section, we will review some
basic facts of commutative algebra and algebraic geometry, limiting the
discussion to only what is necessary for our purposes.

First, let us recall this topology and some basic notation. Given a
commutative ring $A$, the set $\operatorname{Spec}A$ is endowed with the
_Zariski topology_ by defining the following as basic closed and open sets,
respectively. For any ideal $I\subseteq A$, we define $V(I)$ to be the subset
of $\operatorname{Spec}A$ consisting of all prime ideals that contain $I$, and
$D(f)=\operatorname{Spec}A\setminus V(f)$. Notice that it is natural via the
isomorphism theorems for rings to identify $V(I)$ with
$\operatorname{Spec}A/I$. With this notation, the closed subsets of
$\operatorname{Spec}A$ in the Zariski topology are precisely the sets of the
form $V(I)$ where $I\subseteq A$ is an ideal, and sets of the form $D(f)$ for
$f\in A$ form a base for the open subsets of $\operatorname{Spec}A$. In fact,
$\operatorname{Spec}A$ is an _affine scheme_ , meaning that it has even more
structure than just a topology, although we will not require this full
structure; see [7, Chapter 2] for more background.

In this paper, we consider the ring $A=F[Y_{0},\dots,Y_{m}]$ and its
quotients, where $F$ is a subfield of $\overline{\mathbb{Q}}$. An _affine
variety over F_ is an object of the form
$V(I)=\operatorname{Spec}F[Y_{0},\dots,Y_{m}]/I$ for some $m\geq 0$ and some
ideal $I\subseteq F[Y_{0},Y_{1},\dots,Y_{m}]$. Furthermore, if the quotient
$F[Y_{0},\dots,Y_{m}]/I$ is an integral domain, then the corresponding affine
variety is called _integral_. We will write $V(I)=V(f_{1},\dots,f_{k})$ when
the ideal $I\subseteq F[X,Y_{1},\dots,Y_{m}]$ is generated by
$\\{f_{1},\dots,f_{k}\\}$. If there is ambiguity about the base field, then we
will write $V_{F}$ instead of $V$ for clarity.

Given an affine variety $V=\operatorname{Spec}F[Y_{0},\dots,Y_{m}]/I$, the
_rational points_ of $V$ (over $F$) are the tuples $(y_{0},\dots,y_{m})\in
F^{m}$ such that $f(y_{0},\dots,y_{m})=0$ for all $f\in I$. The set of
rational points can be identified with the set of all $F$-algebra
homomorphisms $\varphi:F[Y_{0},\dots,Y_{m}]/I\to F$. We refer the reader to
[7, Section 2.3.2] for more details. As we are frequently working over non-
algebraically closed fields, it is possible for nontrivial affine varieties to
have no rational points, such as the affine variety
$\operatorname{Spec}\mathbb{Q}[Y_{0},\dots,Y_{m}]/(Y_{0}^{2}+\dots+Y_{m}^{2}+1)$
for any $m\geq 0$. We can view the varieties as geometric objects which help
us find and describe the rational points.

The _Krull dimension_ of a ring $A$, written $\textnormal{dim}(A)$, is the
supremal length $r$ of a chain of prime ideals
${\mathfrak{p}}_{0}\subsetneq\dots\subsetneq{\mathfrak{p}}_{r}$ in $A$.
Similarly, given a topological space $X$, we define $\textnormal{dim}(X)$ to
be the supremal length $r$ of a chain of irreducible closed subsets
$Z_{0}\subsetneq\dots\subsetneq Z_{r}$ in $X$. The following proposition
equates these two notions of dimension. Recall that the nilradical of a
commutative ring is the set of all nilpotent elements, or equivalently the
intersection of all prime ideals.

######  Proposition 2.4 (Proposition 2.5.8, [7]).

Let $A$ be a (commutative) ring and let $N$ be the nilradical of $A$. Then
$\textnormal{dim}(\operatorname{Spec}A)=\textnormal{dim}(A)=\textnormal{dim}(A/N)$.

In our applications, we need to understand the dimension of subsets of affine
varieties. Recall that if $X$ is any topological space and $Y$ is any subset
of $X$ endowed with the subset topology, then
$\textnormal{dim}(Y)\leq\textnormal{dim}(X)$ [7, Proposition 2.5.5]. In the
context of affine varieties and open subsets, this inequality is often an
equality due to the fact that open subsets in the Zariski topology are
“large”. This idea is formulated precisely in the following proposition. Given
a field extension $L/F$, we write $\operatorname{trdeg}_{F}L$ for the
_transcendence degree_ of $L$ over $F$. If $X=\operatorname{Spec}A$ is an
integral affine variety, we call $\operatorname{Frac}(A)$ the _function field_
of $X$.

######  Proposition 2.5 (Proposition 2.5.19, [7]).

If $X=\operatorname{Spec}A$ is an integral affine variety over a field $F$,
then

$\textnormal{dim}(U)=\textnormal{dim}(X)=\operatorname{trdeg}_{F}\operatorname{Frac}(A)$

for any nonempty open subset $U\subseteq X$.

Similarly, it is helpful to know when a subset of a topological space $X$ has
strictly smaller dimension than $X$. In contrast to the result immediately
above, this often happens for proper closed subsets of an affine variety.

######  Proposition 2.6 (Corollary 2.5.26, [7]).

Let $X=\operatorname{Spec}A$ be an integral affine variety. If $f\in A$ is
nonzero, then every irreducible component of $V(f)$ has dimension
$\textnormal{dim}(X)-1$. In particular, every proper closed subset of $X$ has
strictly smaller dimension than $X$.

So far in this section, the definition of dimension depends on the base field
$F\subseteq\overline{\mathbb{Q}}$, _a priori_. However, the result below
clarifies that dimension stays the same under base extension. This allows us
to ignore the field of definition to some extent, especially when defining the
rank of a formula below, although the notion of integrality truly does depend
on the base field, so care is still required when applying the previous two
propositions.

######  Proposition 2.7 (Proposition 3.2.7, [7]).

Let $F\subseteq L\subseteq\overline{\mathbb{Q}}$ be fields. Given an affine
variety
$V_{F}(f_{1},\dots,f_{k})=\operatorname{Spec}F[Y_{0},\dots,Y_{m}]/(f_{1},\dots,f_{k})$,
the affine variety

$V_{L}(f_{1},\dots,f_{k})=\operatorname{Spec}L[Y_{0},\dots,Y_{m}]/(f_{1},\dots,f_{k})$

is the _base extension_ of the variety $V_{F}(f_{1},\dots,f_{k})$ to $L$, and
these affine varieties have the same dimension.

To apply this proposition to open sets, we remark that open sets can be
equivalently viewed as affine varieties themselves, albeit in a different
ambient space with an extra variable.

######  Corollary 2.8.

Let $F\subseteq\overline{\mathbb{Q}}$ be a field. For polynomials
$g,f_{1},\dots,f_{k}\in F[Y_{0},\dots,Y_{m}]$, define
$A=F[Y_{0},\dots,Y_{m}]/(f_{1},\dots,f_{k})$ and let $A_{g}$ be the
localization of $A$ be the element $g$. Then there are isomorphisms of ringed
topological spaces

$V_{F}(f_{1},\dots,f_{k})\cap D(g)\cong\operatorname{Spec}(A_{g})\cong
V_{F}(f_{1},\dots,f_{k},Y_{m+1}g-1).$

In particular, $\textnormal{dim}(V_{F}(f_{1},\dots,f_{k})\cap
D(g))=\textnormal{dim}(V_{L}(f_{1},\dots,f_{k})\cap D(g))$ for any algebraic
extension of fields $L\supseteq K$.

###### Proof.

The first isomorphism is [7, Lemma 2.3.7]. The second isomorphism actually
follows from a well-known isomorphism of underlying rings

$A_{g}\cong F[Y_{0},\dots,Y_{m+1}]/(f_{1},\dots,f_{k},Y_{m+1}g-1);$

see [13, Lemma §6.2]. Therefore, the statement on dimension follows
immediately from Proposition 2.7. ∎

###  2.3. Thin sets

Hilbert’s Irreducibility Theorem can take many different forms, but we put a
simple version here that suffices for the purposes of this article. For
brevity, we present _thin sets_ as a black box, and refer the reader to [18,
Prop. 3.3.5] for more details. Essentially, a thin subset $T\subseteq K$ of a
number field is small, in the view of arithmetic geometry. For example, any
set of points that is contained in a closed subvariety of affine $n$-space
$K^{n}$, and which is different from the entire space, is thin with respect to
$K$. All necessary details can be deduced from the results we recall below .

######  Theorem 2.9 (Hilbert’s Irreducibility Theorem).

Let $f(Y_{0},Y_{1},\dots,Y_{m})$ be a polynomial with coefficients in a number
field $K$ which is irreducible as an $(m+1)$-variable polynomial. There exists
a thin set $T\subseteq K^{m}$ such that if $(y_{1},\dots,y_{m})\in
K^{m}\setminus T$, then $f(Y_{0},y_{1},\dots,y_{m})$ is an irreducible single-
variable polynomial of degree $\textnormal{deg}_{Y_{0}}(f)$.

In order for the theorem above to be non-trivial, we need to know that $K^{m}$
is not a thin subset of itself, and this is indeed true for all number fields
[18, Prop 3.4.1]. Moreover, the propositions below show that thin sets cannot
contain arithmetically important subsets, which will allow us to use Hilbert’s
Irreducibility Theorem in the cases we care about.

######  Proposition 2.10 (Proposition 3.2.1, [18] ).

If $L/K$ is a finite extension of fields and $T\subseteq L^{m}$ is thin with
respect to $L$, then $T\cap K^{m}$ is thin with respect to $K$.

######  Proposition 2.11.

If $K$ is a number field, then no thin subset of $K$ contains either
$\mathbb{Z}$ or $\mathbb{Q}\setminus\mathbb{Z}$.

###### Proof.

Thin sets of $\mathbb{Q}$ cannot contain $\mathbb{Z}$ or
$\mathbb{Q}\setminus\mathbb{Z}$ by [18, Theorem 3.4.4] and [18, Prop. 3.4.2],
respectively. Thus, the result for arbitrary number fields follows from
Proposition 2.10. ∎

Moreover, we can understand thin sets in products. This lemma will be used to
show that if a set $Z\subseteq\mathbb{Q}$ is not thin, then the product
$Z\times\mathbb{Q}^{n}$ cannot be thin, either.

######  Lemma 2.12.

If $n\geq 0$ and $S\subseteq\mathbb{Q}$ is a set such that
$S\times\mathbb{Q}^{n}\subseteq\mathbb{Q}^{n+1}$ is thin, then
$S\subseteq\mathbb{Q}$ is thin.

###### Proof.

There is a line $\mathcal{L}\subseteq\mathbb{Q}^{n+1}$ such that
$\mathcal{L}\cap(S\times\mathbb{Q}^{n})$ is thin in $\mathcal{L}$ and the
projection of $\mathcal{L}$ to the first coordinate is all of $\mathbb{Q}$
[18, Proposition 3.2.3]. As $\mathcal{L}$ is a line, this projection is an
isomorphism and $\mathcal{L}\cap(S\times\mathbb{Q}^{n})$ maps onto to the set
$S$. Therefore, $S$ is thin in $\mathbb{Q}$. ∎

Finally, we prove a proposition that lets us stitch this material together.
This is ultimately the result that is required in the proof of our main
theorem.

######  Proposition 2.13.

Let $K$ be a number field and let
$f(X,Y_{1},\dots,Y_{m}),g(X,Y_{1},\dots,Y_{m})\in K[X,Y_{1},\dots,Y_{m}]$ be
relatively prime irreducible polynomials. Then there is a thin set $T\subseteq
K^{m}$ such that $f(x,y_{1},\dots,y_{m-1},Y)$ and $g(x,y_{1},\dots,y_{m-1},Y)$
are relatively prime irreducible single-variable polynomials for every
$(x,y_{1},\dots,y_{m-1})\in K^{m}\setminus T$, of degrees
$\textnormal{deg}_{Y_{m}}(f)$ and $\textnormal{deg}_{Y_{m}}(g)$, respectively.

###### Proof.

Take $T_{0}$ to be the union of the two thin sets given by applying Hilbert’s
Irreducibility Theorem to $f$ and $g$ separately. By construction,
$f(x,y_{1},\dots,y_{m-1},Y)$ and $g(x,y_{1},\dots,y_{m-1},Y)$ are irreducible
polynomials in $Y$ for every $(x,y_{1},\dots,y_{m-1})\in K^{m}\setminus
T_{0}$, and it only remains to check the claim of relative primality.

If $\textnormal{deg}_{Y_{m}}(f)\neq\textnormal{deg}_{Y_{m}}(g)$, then this
claim is trivial. Therefore, write
$d=\textnormal{deg}_{Y_{m}}(f)=\textnormal{deg}_{Y_{m}}(g)$, and consider
$(x,\dots,y_{m-1})\in K^{m}\setminus T$. Since the polynomials
$f(x,y_{1},\dots,y_{m-1},Y)$ and $g(x,y_{1},\dots,y_{m-1},Y)$ are irreducible,
the failure of relative primality implies that they are unit multiples of each
other, i.e., $f(x,y_{1},\dots,y_{m-1},Y)=zg(x,y_{1},\dots,y_{m-1},Y)$ for some
nonzero $z\in K$. In particular, if we write

$f(X,Y_{1},\dots,Y_{m})=\sum_{i=0}^{d}f_{i}(X,Y_{1},\dots,Y_{m-1})Y_{m}^{i},$
$g(X,Y_{1},\dots,Y_{m})=\sum_{i=0}^{d}g_{i}(X,Y_{1},\dots,Y_{m-1})Y_{m}^{i},$

where $f_{i},g_{i}\in K[X,Y_{1},\dots,Y_{m-1}]$ are polynomials, then this
condition is the same as

$f_{i}(x,y_{1},\dots,y_{m-1})=zg_{i}(x,y_{1},\dots,y_{m-1})$

for all $0\leq i\leq d$. Multiplying these conditions together, we get the
equations

$f_{i}g_{j}=zg_{i}g_{j}=g_{i}f_{j}$

for $0\leq i,j\leq d$. We will show that this system of equations holds only
inside a thin set, which completes the proof.

We claim that the polynomial

$f_{i}(X,Y_{1},\dots,Y_{m-1})g_{j}(X,Y_{1},\dots,Y_{m-1})-g_{i}(X,Y_{1},\dots,Y_{m-1})f_{j}(X,Y_{1},\dots,Y_{m-1})$

is nonzero for some choice of $i$ and $j$. Indeed, if this were not the case,
then we would find that

$\displaystyle f_{i}(X,Y_{1},\dots,Y_{m-1})g(X,Y_{1},\dots,Y_{m})$
$\displaystyle=\sum_{j=0}^{d}f_{i}(X,Y_{1},\dots,Y_{m-1})g_{j}(X,Y_{1},\dots,Y_{m-1})Y_{m}^{j}$
$\displaystyle=\sum_{j=0}^{d}g_{i}(X,Y_{1},\dots,Y_{m-1})f_{j}(X,Y_{1},\dots,Y_{m-1})Y_{m}^{j}$
$\displaystyle=g_{i}(X,Y_{1},\dots,Y_{m-1})f(X,Y_{1},\dots,Y_{m})$

for all $i$. As $g$ and $f$ are irreducible and the only polynomials on the
left and right sides of the equation containing the variable $Y_{m}$, we
conclude that they are unit multiples of each other, which contradicts the
hypothesis of relative primality.

Therefore, let $T_{1}$ be the set of all $K$-rational points on the affine
variety

$V_{K}(\\{f_{i}g_{j}-g_{i}f_{j}:0\leq i<j\leq\textnormal{deg}_{Y_{m}}(f)\\}).$

Since one of the polynomials in the defining set is nonzero, the affine
variety is a proper closed variety, which implies that $T_{1}$ is a thin set
by definition. By construction, the set $T=T_{0}\cup T_{1}$ is the desired
thin set. ∎

##  3\. Rank of a Formula

The goal of this section is to define a notion of rank for existential
formulas in the language of fields, using degrees of polynomials and
dimensions of varieties, as well as the number of $\exists$-quantifiers used.
Certain formulas will have the same rank, just as certain polynomials have the
same degree. Crucially, the ranks are well-ordered.

###  3.1. A useful well-ordering

######  Definition 3.1.

Let $(\mathcal{L},<)$ be a linear order. For a finite tuple
$(a_{0},\ldots,a_{n})\in\mathcal{L}^{<\omega}$, write $\vec{a}^{*}$ for the
tuple of the same $(n+1)$ elements (including repetitions) arranged in
$<$-descending order: $\vec{a}^{*}=(a_{\alpha(0)},\ldots,a_{\alpha(n)})$ where
$\alpha$ is a permutation and $a_{\alpha(i+1)}\leq a_{\alpha(i)}$ for all
$i<n$. Write $\vec{a}=^{*}\vec{b}$ just if $\vec{a}^{*}=\vec{b}^{*}$.

Then the $*$-order $(\mathcal{L}^{*},<^{*})$ is the lexicographic order
$<^{*}$ (defined using $<$ on individual coordinates) on the set
$\mathcal{L}^{*}$ of $=^{*}$-equivalence classes in $\mathcal{L}^{<\omega}$.
To be clear: if $\vec{a}^{*}$ is a proper initial segment of $\vec{b}^{*}$,
then $\vec{a}^{*}<^{*}\vec{b}^{*}$.

Equivalently, one can view the elements of $\mathcal{L}^{*}$ as finite
multisets of elements of $\mathcal{L}$, with the elements of each multiset
listed in $<$-nonincreasing order.

######  Lemma 3.2.

If $(\mathcal{L},<)$ is a well order, then so is $(\mathcal{L}^{*},<^{*})$.

###### Proof.

Clearly $<^{*}$ is a linear order. If it were not a well order, there would be
a least $a\in\mathcal{L}$ such that some infinite $<^{*}$-descending sequence
begins with an $\vec{a}^{*}$ whose greatest element is $a$. Choose such an
$\vec{a}^{*}=(a^{k},a_{1},\ldots,a_{n})$, in nonincreasing order with
$a_{1}<a$ after $a$ appears $k$ times, with $k$ as small as possible (and
allowing $n=0$). Then the infinite descending sequence beginning with this
$\vec{a}^{*}$ can only have finitely many terms that begin with $a^{k}$, for
if there were infinitely many, then by “chopping off” the $a^{k}$ from each
term, we would get an infinite sequence contradicting the choice of $a$. But
then, immediately after the last term beginning with $a^{k}$ comes a term
beginning with $a^{j}$ for $j<k$, and this term also begins an infinite
descending sequence in $\mathcal{L}^{*}$, contradicting either the minimality
of $k$ (if $j>0$) or the minimality of $a$ (if $j=0$). ∎

###  3.2. Definition of rank

We present an explicit way to put a well-ordering on the set of existential
formulas with parameters in any given field. This is done by associating a
_rank_ to every existential formula.

Any existential formula $\alpha(X)$ can be written in disjunctive normal form

$\alpha(X)=\exists\vec{Y}(\alpha_{1}\vee\alpha_{2}\vee\cdots\vee\alpha_{n}),$

where each $\alpha_{i}(X,\vec{Y})$ is a conjunction of equations and
inequations. Bringing the existential quantifiers inside the disjunctions and
discarding any unused quantifiers, any existential formula can be rewritten as

$((\exists Y_{1}\cdots\exists Y_{m_{1}})\alpha_{1})\vee\cdots\vee((\exists
Y_{1}\cdots\exists Y_{m_{n}})\alpha_{n}),$

where all variables $Y_{1},\dots,Y_{m_{i}}$ appear in $\alpha_{i}$. One can
also easily rearrange any $\alpha_{i}(X,\vec{Y})$ into a conjunction of the
form

$f_{1}(X,\vec{Y})=\cdots=f_{k}(X,\vec{Y})=0~{}\&~{}g(X,\vec{Y})\neq 0.$

Only one inequation $g\neq 0$ is needed, as several $g_{i}(X,\vec{Y})$ could
be multiplied together. It is allowed for $g$ to be the constant $1$. We call
an existential formula _rankable_ if it is given in the above format. It is
trivial to rearrange any existential formula into rankable format, so in this
paper any existential formula which appears is assumed to be rankable.

Before defining rank, we present a way to order tuples of polynomials. Notice
that this notion depends on a specific order for the variables.

######  Definition 3.3.

For the variables $X,Y_{1},\ldots,Y_{m}$, the _multidegree_ of a monomial
$X^{c}Y_{1}^{d_{1}}\cdots Y_{m}^{d_{m}}$ is $(c,d_{1},\ldots,d_{m})$, and
these $(m+1)$-tuples are ordered by the reverse lexicographic order. The
_multidegree $\textnormal{mdeg}(f)$ of a polynomial $f$_ is the maximum of the
multidegrees of each monomial appearing (with nonzero coefficient) in it.

Observe that the linear order defined above on multidegrees is a well-
ordering.

######  Definition 3.4.

A _basic rankable formula_ is an existential formula of the form

$\exists Y_{1}\cdots\exists
Y_{m}~{}[f_{1}(X,Y_{1},\ldots,Y_{m})=\cdots=f_{k}(X,Y_{1},\ldots,Y_{m})=0~{}\&~{}g(X,\vec{Y})\neq
0],$

and the _rank_ of such a formula is the triple

$\textnormal{rk}(\beta)=(m,e,(\textnormal{mdeg}(f_{1}),\ldots,\textnormal{mdeg}(f_{k}))^{*}),$

where the second component is the dimension $e$ of
$V_{\overline{\mathbb{Q}}}(\vec{f})\cap D(g)$, as defined in Section 2.2, and
the third component uses the $=^{*}$-classes of tuples of multidegrees, as in
Definition 3.1.

In this definition, we see that $V_{\overline{\mathbb{Q}}}(\vec{f})\cap D(g)$
is a subset of an ambient space of dimension $m+1$. Therefore, the first
coordinate of the definition of rank can be equivalently viewed as a measure
of the dimension of this ambient space. Additionally, by Corollary 2.8, the
base field does not matter in the definition of the dimension $e$, so we will
usually drop the $\overline{\mathbb{Q}}$ from this notation.

We define an order $\prec$ on ranks of basic rankable formulas in forwards
lexicographic order, meaning that

$(m,e,(d_{1},\ldots,d_{k})^{*})\prec(m^{\prime},e^{\prime},(d^{\prime}_{1},\ldots,d^{\prime}_{k^{\prime}})^{*})$

if and only if one of the following holds:

  * •

$m<m^{\prime}$, i.e., the first formulas uses fewer $\exists$-quantifiers; or

  * •

$m=m^{\prime}$ and $e<e^{\prime}$, so the first formula defines an open
variety of lesser dimension than the second; or

  * •

$m=m^{\prime}$ and $e=e^{\prime}$ and
$(d_{1},\ldots,d_{k})^{*}<^{*}(d^{\prime}_{1},\ldots,d^{\prime}_{k^{\prime}})^{*}$,
so the first formula uses polynomials of lower multidegree.

The least possible rank of a (satisfiable) basic rankable formula is
$(0,0,(1)^{*})$, which is the rank of the quantifier-free formula $X=x$ for
any specific value $x$: here $m=0$, $k=1$ and the variety, which has a single
component whose dimension is $0$, is defined by $f_{1}=X-x=0$ whose
multidegree (in the single variable $X$, since $m=0$) is simply $1$. (The
variety defined by $0=0$ has dimension $1$, so the formula $0=0$ has higher
rank.)

Let $\mathcal{R}$ denote the set of all possible ranks of basic rankable
formulas. Then $(\mathcal{R},\prec)$ is a well-ordering. (The third component
of $\prec$ is well-ordered by Lemma 3.2.) Let $(R^{*},\prec^{*})$ be the
result of applying Definition 3.1 to $(\mathcal{R},\prec)$.

Observe that an existential formula is rankable if and only if it is the
finite disjunction of basic rankable formulas.

######  Definition 3.5.

If $\alpha=\vee_{i=1}^{r}\beta_{i}$ is a rankable formula, the _rank_ of
$\alpha$ is defined to be

$\textnormal{rk}(\alpha)=(\textnormal{rk}(\beta_{1}),\ldots,\textnormal{rk}(\beta_{n}))^{*}\in\mathcal{R}^{*}$

The rankable formulas can then be compared using the ordering $\prec^{*}$. By
Lemma 3.2, $(\mathcal{R}^{*},\prec^{*})$ is a well-order.

##  4\. Minimal formulas and hypersurfaces

The well-ordering of ranks means that every nonempty set of existential
formulas has an element of minimal rank. For example, if there exists an
existential formula that defines $\mathcal{O}_{L}$ in $L$, then there is an
existential formula $\alpha$ that accomplishes this which has minimal rank
among all such formulas. Such a formula can be considered a minimal successful
formula. This motivates the following general definition.

######  Definition 4.1.

For a field $L\subseteq\overline{\mathbb{Q}}$ and an existential formula
$\alpha(X)$ with coefficients from $L$, we say $\alpha$ is $L$-_minimal_ if
$\alpha$ has minimal rank among all existential formulas $\alpha^{\prime}$ for
which

$\forall x(\alpha(x)\iff\alpha^{\prime}(x))$

holds over $L$.

In order for the above to make sense, $\alpha^{\prime}$ ranges only over those
existential formulas which have coefficients from $L$. We will show that any
$L$-minimal formula must take the form of a disjunction of formulas with two
very simple formats: quantifier-free formulas, and formulas with only one
equation and one inequation.

We will start by considering a general rankable formula, then minimize it as
much as possible. First, we want to minimize the number of quantifiers, which
is the first component of rank. Clearly, we can eliminate the quantifier for
any variable that does not appear in any polynomial of the formula. The
following simple lemma allows us also to remove any variables that appear in
the inequation, but none of the equations.

######  Lemma 4.2.

Let $1\leq e<m$ and let $\delta(X)$ be the basic rankable existential formula

$\exists Y_{1}\cdots\exists
Y_{m}~{}[f_{1}(X,Y_{1},\dots,Y_{e})=\dots=f_{k}(X,Y_{1},\dots,Y_{e})=0\neq
g(X,Y_{1},\dots,Y_{m})],$

where $f_{i}\in F[X,Y_{1},\dots,Y_{e}]$ and $g\in F[X,Y_{1},\dots,Y_{m}]$ for
some field $F$.

Then there are polynomials $g_{1},\dots,g_{r}\in F[X,Y_{1},\dots,Y_{e}]$ such
that $\delta(X)$ is equivalent over $F$ to the disjunction of formulas

$\vee_{i=1}^{r}\exists Y_{1}\cdots\exists
Y_{e}~{}[f_{1}(X,\vec{Y})=\dots=f_{k}(X,\vec{Y})=0\neq g_{i}(X,\vec{Y})].$

###### Proof.

Write out $g=\sum_{i=0}^{d_{m}}g_{i}(X,Y_{1},\dots,Y_{m-1})Y_{m}^{i}$ as a
polynomial in $Y_{m}$. Notice that if
$(x,y_{1},\dots,y_{m-1})\in\overline{\mathbb{Q}}^{m}$ is any tuple, then there
is a $y_{m}\in\mathbb{Q}$ such that $g(x,y_{1},\dots,y_{m})\neq 0$ if and only
if $g_{i}(x,y_{1},\dots,y_{m-1})\neq 0$ for some $0\leq i\leq d_{m}$.
Therefore, we can remove the quantifier for $Y_{m}$ and instead use a
disjunction where $g$ is replaced by $g_{j}$ for $0\leq j\leq d_{m}$ in each
formula. By induction, this completes the proof. ∎

To continue minimizing the number of quantifiers, we can take a more geometric
perspective. A basic rankable formula $\beta(X)$ with $m$ quantifiers

$\exists Y_{1}\cdots\exists
Y_{m}~{}[f_{1}(X,\vec{Y})=\dots=f_{k}(X,\vec{Y})=0\neq g(X,\vec{Y})]$

corresponds to the projection to the $X$-coordinate of the points on the
variety $D(g)\cap V(f_{1},\dots,f_{k})$. Minimizing the number of quantifiers
$m$ is equivalent to minimizing the dimension $m+1$ of the ambient space where
the variety lives. If $k$ is large, then we expect the dimension $e$ of the
variety to be much smaller than $m+1$, and we can consider this “wasteful,” as
it uses more variables than necessary. The following proposition uses a basic
result of algebraic geometry to show that, in a special case with integral
affine varieties, we only need $m=e$ quantifiers and a single equation to
describe all but a lower-dimensional closed subset. To complete the section,
we will the show that this is enough to deduce the result in general.

######  Proposition 4.3.

Let $F\subseteq\overline{\mathbb{Q}}$ be a field and
${\mathfrak{p}}=(f_{1},\dots,f_{k})\subseteq F[X,Y_{1},\dots,Y_{m}]$ a prime
ideal. Define $\beta(X)$ to be the formula

$\beta(X)=\exists
Y_{1},\dots,Y_{m}[f_{1}(X,Y_{1},\dots,Y_{m})=\dots=f_{k}(X,Y_{1},\dots,Y_{m})=0]$

and set $e=\textnormal{dim}(V_{F}({\mathfrak{p}}))$. If $\beta(X)$ is
satisfied by infinitely many values of $X$ in $\overline{\mathbb{Q}}$ and
$e\leq m-1$, then after possibly reordering indices, there are polynomials
$h\in F[X,Y_{1},\dots,Y_{e}]$ and $s\in F[X,Y_{1},\dots,Y_{e-1}]$ with $h$
irreducible and $s\not\in{\mathfrak{p}}$ such that $\beta(X)$ is equivalent to
$\gamma_{1}(X)\vee\gamma_{2}(X)$ over $F$, where

$\displaystyle\gamma_{1}(X)=$ $\displaystyle\exists Y_{1}\cdots\exists
Y_{e}~{}[h(X,\ldots,Y_{e})=0\neq s(X,\vec{Y})],$ $\displaystyle\gamma_{2}(X)=$
$\displaystyle\exists Y_{1}\cdots\exists
Y_{m}~{}[s(X,\ldots,Y_{m})=f_{1}(X,\ldots,Y_{m})=\cdots=f_{k}(X,\ldots,Y_{m})=0].$

###### Proof.

Write $L=\operatorname{Frac}(F[X,Y_{1},\dots,Y_{m}]/{\mathfrak{p}})$. By
Proposition 2.5, we know that $e$ is equal to the transcendence degree of $L$
over $F$. Since the images of $\\{X,Y_{1},\dots,Y_{m}\\}$ generate $L$ over
$F$, there is a transcendence basis consisting of a subset of these elements,
and we can force $\bar{X}$ to be in this basis because $\bar{X}$ is not
algebraic over $F$ [6, Theorem VIII.1.1]. Indeed, if $\bar{X}$ were algebraic
over $F$, then it would be the root of a single-variable polynomial over $F$,
and therefore $\beta(X)$ would only be solvable over $\overline{\mathbb{Q}}$
by finitely many $X$, which is not the case by hypothesis.

Reorder the variables so that $\\{\bar{X},\bar{Y}_{1},\dots,\bar{Y}_{e-1}\\}$
is a transcendence basis of $L$ over $F$. Write
$L_{0}=F(X,Y_{1},\dots,Y_{e-1})$. Although a particular ordering of the
variables is used when defining the multidegree component of rank in
Definition 3.4, we will produce lower-rank formulas purely in terms of
quantifiers and dimension, and therefore the multidegree will not matter here.
As $L$ is a finite separable extension of $L_{0}$, the primitive element
theorem states that $L=L_{0}(\theta)$ for a single element $\theta$. Write
$h\in L_{0}[Y]$ for the minimal polynomial of $\theta$. By clearing
denominators if necessary, we can assume without loss of generality that $h\in
F[X,Y_{1},\dots,Y_{e-1},Y]$ is an irreducible multivariable polynomial.
Therefore, writing ${\mathfrak{p}}=(f_{1},\dots,f_{k})$, we have an
isomorphism of fields:

$L_{0}[Y_{e},\dots,Y_{m}]/(f_{1},\dots,f_{k})\cong L\cong
L_{0}[Y]/(h)\cong\operatorname{Frac}(F[X,Y_{1},\dots,Y_{e-1},Y]/(h)).$

Geometrically, this says that the integral affine variety
$V_{F}({\mathfrak{p}})$ is birational to the hypersurface $V_{F}(h)$. In fact,
we can see that the two varieties contain isomorphic open sets, as follows.

Using the isomorphism of fields we can write
$Y_{j}=\sum_{\ell=0}^{N_{j}}c_{j,\ell}Y^{\ell}$ for every
$e_{\mathfrak{p}}\leq j\leq m$, and
$Y=\sum_{\vec{a}}d_{\vec{a}}Y_{e_{\mathfrak{p}}}^{a_{0}}\dots
Y_{m}^{a_{m-e_{\mathfrak{p}}}}$, where $c_{j,\ell}$ and $d_{\vec{a}}$ are
elements of $L_{0}$, and in particular not contained in ${\mathfrak{p}}$
because $L_{0}$ is a subfield of the function field of
$V_{F}({\mathfrak{p}})$. Let $s$ be the products of all denominators appearing
in these terms. Then these equations give an isomorphism of the open sets
$V_{F}({\mathfrak{p}})\cap D(s)$ and $V_{F}(h)\cap D(s)$; see [7, Lemma 3.7].
Moreover, the $X$-coordinate of rational points is unchanged by the
isomorphism because we included $X$ in the transcendence basis. As
$V_{F}({\mathfrak{p}})=(V_{F}({\mathfrak{p}})\cap D(s))\cup
V_{F}({\mathfrak{p}}+(s))$, this proves the claim that the formula $\beta$ is
equivalent over $F$ to the disjunction stated above. ∎

Next we show that minimal formulas all have a very convenient structure.

######  Proposition 4.4.

If $\alpha(X)=\vee_{i=1}^{r}\beta_{i}(X)$ is the disjunction of basic rankable
formulas which is $L$-minimal for some field
$L\subseteq\overline{\mathbb{Q}}$, then each $\beta_{i}(X)$ has one of the
following forms:

  1. (i)

The quantifier-free formula $X=z_{0}$ for a fixed $z_{0}\in L$.

  2. (ii)

The “hypersurface formula”, $\exists Y_{1}\dots\exists
Y_{e}~{}[f(X,Y_{1},\dots,Y_{e})=0\neq g(X,Y_{1},\dots,Y_{e})]$ for an
irreducible $f\in L[X,Y_{1},\dots,Y_{e}]$ and a polynomial $g\in
L[X,Y_{1},\dots,Y_{e}]$.

###### Proof.

Let $\beta(X)$ be a fixed $\beta_{i}(X)$ which does not have the desired form.
Write $\beta$ in the form

$\exists Y_{1}\cdots\exists
Y_{m}~{}[f_{1}(X,\ldots,Y_{m})=\cdots=f_{k}(X,\ldots,Y_{m})=0\neq
g(X,\vec{Y})]$

and consider the ideal $I=(f_{1},\dots,f_{k})$. Define
$e=\textnormal{dim}(V(I)\cap D(g))$. Without loss of generality, we can assume
that each $f_{i}$ is irreducible. Otherwise, if $f_{1}=h_{1}h_{2}$ is a
nontrivial factorization, then we could write $\beta$ as the disjunction of
two formulas with $f_{1}$ replaced by $h_{1}$ or $h_{2}$, respectively, which
have smaller multidegree.

Since $f_{1}$ is irreducible, $V_{L}(I)$ is a closed subset of the integral
affine variety $V_{L}(f_{1})$ which has dimension
$\textnormal{dim}(V_{L}(f_{1}))=m$ by Proposition 2.6. In fact, we see that
either $V(f_{1})=V(I)$, in which case we are done, or we have

$e=\textnormal{dim}(V(I)\cap
D(g))\leq\textnormal{dim}(V(I))<\textnormal{dim}(V(f_{1}))=m.$

By assumption, we are in the latter case, and we will produce a set of
formulas with parameters in $L$ which explicitly contradicts the minimality of
$\alpha$.

The ideal $I$ has a primary decomposition
$I={\mathfrak{q}}_{1}\cap\dots\cap{\mathfrak{q}}_{r}$ where each
${\mathfrak{q}}_{i}$ is a primary ideal associated to a prime ideal
${\mathfrak{p}}_{i}$. Indeed, the rational points on $V(I)\cap D(g)$ are the
same as the rational points on $\cup_{i=1}^{r}V({\mathfrak{p}}_{i})\cap D(g)$.
Notice that the open set $V({\mathfrak{p}}_{i})\cap D(g)$ might be empty for
some $i$, but whenever it is nonempty, $V({\mathfrak{p}}_{i})\cap D(g)$ has
the same dimension as $V({\mathfrak{p}}_{i})$ by Proposition 2.5.

To summarize, we have shown that the formula $\beta(X)$ is equivalent to the
disjunction $\vee_{i=1}^{r}\delta_{{\mathfrak{p}}_{i}}(X)$ where each
$\delta_{{\mathfrak{p}}_{i}}(X)$ is defined as a formula

$\delta_{{\mathfrak{p}}_{i}}(X)=\exists
Y_{1},\dots,Y_{m}[p^{i}_{1}(X,\vec{Y})=\dots=p^{i}_{n(i)}(X,\vec{Y})=0\neq
g(X,\vec{Y})],$

where ${\mathfrak{p}}_{i}=(p_{1}^{i},\dots,p^{i}_{n(i)})$. For each $i$, we
will replace $\delta_{{\mathfrak{p}}_{i}}(X)$ itself with an equivalent
disjunction of basic rankable formulas, each of which has rank strictly
smaller than $\beta$. By definition, this contradicts the minimality of
$\alpha$, and the proof will be done.

To this end, we analyze the primes
$S=\\{{\mathfrak{p}}_{1},\dots,{\mathfrak{p}}_{r}\\}$ and divide them
accordingly. Let $S_{\textrm{finite}}$ be the set of primes ${\mathfrak{p}}\in
S$ such that only finitely many elements of $L$ satisfy
$\delta_{{\mathfrak{p}}}(X)$ in $F$, and let $S_{\infty}$ be all other primes
of $S$. Partition $S_{\infty}=S_{\textrm{big}}\cup S_{\textrm{small}}$ where

$\displaystyle S_{\textrm{big}}$ $\displaystyle=\\{{\mathfrak{p}}\in
S_{\infty}\mid\textnormal{dim}(V({\mathfrak{p}}))=e\\},$ $\displaystyle
S_{\textrm{small}}$ $\displaystyle=\\{{\mathfrak{p}}\in
S_{\infty}\mid\textnormal{dim}(V({\mathfrak{p}}))<e\\}.$

For any prime ${\mathfrak{p}}\in S_{\textrm{finite}}$, let
$\\{z_{1},\dots,z_{n}\\}$ be the finite set of elements of $L$ which satisfy
$\delta_{{\mathfrak{p}}}(X)$ in $L$. We may therefore replace
$\delta_{\mathfrak{p}}(X)$ with the disjunction of quantifier-free formulas
$\vee_{i=1}^{n}(X-z_{i})$. Each of these quantifier-free formulas consisting
of a single-variable polynomial of degree 1 has the smallest rank possible for
a nontrivial basic rankable formula and $\beta(X)$ has strictly larger rank.

For any ${\mathfrak{p}}\in S_{\textrm{small}}$, the formula
$\delta_{\mathfrak{p}}(X)$ is already of smaller rank than $\beta$. Indeed,
the ambient space is the same, and the dimension is strictly smaller by
definition.

For any ${\mathfrak{p}}\in S_{\textrm{big}}$, letting
${\mathfrak{p}}=(p_{1},\dots,p_{n})$, we apply Proposition 4.3 to see that
$\exists\vec{Y}[p_{1}(X,\vec{Y})=\dots=p_{n}(X,\vec{Y})=0]$ is equivalent to
the disjunction of two formulas

$\displaystyle\exists Y_{1}\cdots\exists Y_{e}~{}[f(X,\ldots,Y_{e})=0\neq
s(X,\vec{Y})],$ $\displaystyle\exists Y_{1}\cdots\exists
Y_{m}~{}[s(X,\ldots,Y_{m})=p_{1}(X,\ldots,Y_{m})=\cdots=p_{n}(X,\ldots,Y_{m})=0],$

where $f\in L[X,Y_{1},\dots,Y_{e}]$ is irreducible and $s\in
L[X,Y_{1},\dots,Y_{e-1}]$ is not contained in ${\mathfrak{p}}$. Thus,
$\delta_{\mathfrak{p}}(X)$ is equivalent to the disjunction of the following
two formulas

(1) $\displaystyle\exists Y_{1}\cdots\exists Y_{m}~{}[f(X,\ldots,Y_{e})=0\neq
g(X,Y_{1},\dots,Y_{m})s(X,Y_{1},\dots,Y_{e-1})],$ (2) $\displaystyle\exists
Y_{1}\cdots\exists
Y_{m}~{}[s(X,\ldots,Y_{e-1})=p_{1}(X,\ldots,Y_{m})=\cdots=p_{n}(X,\ldots,Y_{m})=0\neq
g(X,\vec{Y})].$

By Lemma 4.2, we can replace the formula (1) with a disjunction of basic
rankable formulas, each of which uses only $e$ quantifiers. Since $e<m$, all
these formulas have strictly smaller rank than $\beta$.

On the other hand, formula (2) has $m$ quantifiers just like $\beta$, but we
claim the associated variety has smaller dimension. Indeed, we see that

$\textnormal{dim}(V({\mathfrak{p}}+(s))\cap
D(g))\leq\textnormal{dim}(V({\mathfrak{p}}+(s)))<\textnormal{dim}(V({\mathfrak{p}}))=\textnormal{dim}(V({\mathfrak{p}})\cap
D(g))=e,$

where the strict inequality follows by Proposition 2.6. Therefore this formula
also has strictly smaller rank than $\beta$. This completes the proof. ∎

We can say more about the hypersurface formula appearing in the previous
result. First, we present a simple result on elements of the function field of
an irreducible hypersurface.

######  Lemma 4.5.

Let $F\subseteq\overline{\mathbb{Q}}$ be a field and $f\in
F[X,Y_{1},\dots,Y_{m}]$ an irreducible polynomial whose degree in $Y_{m}$ is
positive. If
$\bar{p}/\bar{q}\in\operatorname{Frac}(F[X,Y_{1},\dots,Y_{m}]/(f))$, then
there are lifts of $p$ and $q$ to $F[X,Y_{1},\dots,Y_{m}]$ such that
$\textnormal{deg}_{Y_{m}}(q)<\textnormal{deg}_{Y_{m}}(f)$.

###### Proof.

Write $f=\sum_{i=0}^{d}b_{i}Y_{m}^{i}$ where $b_{i}\in
F[X,Y_{1},\dots,Y_{m-1}]$. Choose arbitrary lifts $p_{0},q_{0}\in
F[Y_{0},\dots,Y_{m}]$ of $\bar{p}$ and $\bar{q}$. If
$\textnormal{deg}_{Y_{m}}q_{0}<\textnormal{deg}_{Y_{m}}f$, then we are already
done. Otherwise, define $p_{1}=b_{d}p_{0}$ and $q_{1}=b_{d}q_{0}$, which
define the same fraction in the function field because
$b_{d},q_{0}\not\in(f)$. Then the leading coefficient of $q_{1}$ is divisible
by $b_{d}$, so we write it as $h_{1}b_{d}$ for $h_{1}\in
F[Y_{0},\dots,Y_{m-1}]$. Define
$q_{2}=q_{1}-h_{1}Y_{m}^{(\textnormal{deg}_{Y_{m}}q_{1})-d}f_{1}$, and notice
that $\textnormal{deg}_{Y_{m}}q_{2}<\textnormal{deg}_{Y_{m}}q_{1}$. Continuing
in this way, the claim follows. ∎

######  Proposition 4.6.

Suppose $L\subseteq\overline{\mathbb{Q}}$ is a field and $\beta(X)$ is a
formula with coefficients from $L$ of the following form

$\beta(X)=\exists Y_{1}\dots\exists Y_{e}[f(X,Y_{1},\dots,Y_{e})=0\neq
g(X,Y_{1},\dots,Y_{e})]$

Suppose $\beta(X)$ is $L$-minimal. Then $f$ is absolutely irreducible.

###### Proof.

First, it is clear that $f$ is irreducible in $L$; if it were reducible then
$\beta$ could be equivalently expressed as the disjunction of two hypersurface
formulas of strictly smaller rank.

Suppose for contradiction that $f$ is not absolutely irreducible. We will use
this fact to define $\\{x\in L:\beta(x)\text{ holds in }L\\}$ by a smaller
rank formula using coefficients from $L$.

Let $F\subseteq L$ be a number field containing all the coefficients which
appear anywhere in $\beta$. Let $K$ be a finite Galois extension of $F$
containing the coefficients of the absolutely irreducible factors of $f$ over
$\overline{\mathbb{Q}}$, and let $F^{\prime}=K\cap L$. Then $F\subseteq
F^{\prime}\subseteq K$, and $K$ is Galois over $F^{\prime}$ because it was
Galois over $F$. We remark that $F^{\prime}$ is a subfield of $L$, and
therefore $f$ is irreducible over $F^{\prime}$.

For each of the finitely many number fields $E$ with $F^{\prime}\subset
E\subseteq K$, let $p_{E}\in F^{\prime}[Z]$ be a minimal polynomial for a
primitive generator of $E$ over $F^{\prime}$. Since $K$ is Galois over
$F^{\prime}$, none of these finitely many $p_{E}$ have a root in $L$. Let
$h=\prod_{E:F^{\prime}\subset E\subseteq K}p_{E}$.

We claim that $L$ has a lower-ranked formula $\varphi$ with coefficients from
$F^{\prime}$ and with the property that for all $x\in L$, $\varphi(x)$ holds
over $L$ if and only if $\beta(x)$ does.

Let $M$ be the function field of $f$ over $F^{\prime}$. By Proposition 2.2,
$M$ therefore contains some element $z_{0}\in K\setminus F^{\prime}$.
Moreover, $F^{\prime}(z_{0})$ is a subfield of $K$ which strictly contains
$F^{\prime}$. So $F^{\prime}(z_{0})$ contains a root $z$ of $h$.

As an element of $M$, the root $z$ will be of the form
$\frac{p(X,\vec{Y})+(f)}{q(X,\vec{Y})+(f)}$, with $p,q\in
F^{\prime}[X,\vec{Y}]$. We may view $p$ and $q$ as polynomials $p,q\in
F^{\prime}[X,Y_{1},\ldots,Y_{e}]$, modulo the ideal $(f)$. These polynomials
will satisfy

$h\left(\frac{p(x,\vec{y})}{q(x,\vec{y})}\right)=0$

whenever $(x,\vec{y})$ is a solution to $f=0$ and $q(x,\vec{y})\neq 0$.
Therefore, every solution $(x,\vec{y})\in L^{m+1}$ to $f=0$ has
$q(x,\vec{y})=0$.

By Lemma 4.5, we may choose our specific $q\in F^{\prime}[X,\vec{Y}]$ so that
$\textnormal{deg}_{Y_{e}}(q)<\textnormal{deg}_{Y_{e}}(f)$. Notice that
$q\notin(f)$ because $q+(f)$ is the denominator of an element of the function
field, hence nonzero. Below we will consider $q$ as a polynomial of degree $d$
in $Y_{e}$, writing $q=\sum_{i\leq d}c_{i}Y_{e}^{i}$ with all $c_{i}\in
F[X,Y_{1},\ldots,Y_{e-1}]$. Without loss of generality, the leading nonzero
coefficient $c_{d}$ does not lie in $(f)$. If it happens that $Y_{e}$ does not
appear in $q$, then $d=0$ and $c_{0}=q$.

But now we can use these facts to give a lower-ranked disjunction
$\varphi(X)=\gamma_{0}(X)\vee\gamma_{1}(X)$ which is equivalent to $\beta(X)$
in $L$. Since $Y_{e}$ has lower degree in $q$ than in $f$, the trick is to use
the Euclidean algorithm here, using the leading term in the expansion
$f=\sum_{i=0}^{d_{1}}Y_{e}^{i}\cdot b_{i}(X,Y_{1},\ldots,Y_{e-1})$ and writing

$r(X,\vec{Y})=c_{d}(X,\ldots,Y_{e-1})\cdot
f(X,\vec{Y})-b_{d_{1}}(X,Y_{1},\ldots,Y_{e-1})\cdot Y_{e}^{d_{1}-d}\cdot
q(X,\vec{Y})$

as a remainder with $\textnormal{deg}_{Y_{e}}(r)<\textnormal{deg}_{Y_{e}}(q)$.
Recall that the polynomial $c_{d}$ is the coefficient of $Y_{e}^{d}$ in $q$,
hence does not involve $Y_{e}$. Observe also that all coefficients of $r$ are
in $F^{\prime}$.

We claim that in this situation, a tuple $(x,\vec{y})\in L^{m+1}$ is a point
on $V(f)\cap D(g)$ if and only if one of the following conditions holds:

(3) $q(x,\vec{y})=r(x,\vec{y})=0\neq g(x,\vec{y})\cdot
c_{d}(x,y_{1},\ldots,y_{e-1})$

or

(4) $f(x,\vec{y})=c_{d}(x,y_{1},\ldots,y_{e-1})=0\neq g(x,\vec{y}).$

To see the claim, first let $(x,\vec{y})$ be a point on $V(f)\cap D(g)$. As
shown above, we must have $q(x,\vec{y})=0$. But the Euclidean equation shows
that $r(x,\vec{y})=0$ as well, so the tuple satisfies one of the conditions,
according to whether $c_{d}(x,y_{1},\ldots,y_{m-1})=0$ or not. The converse of
the claim follows by applying the Euclidean equation to the first condition,
and the latter condition directly defines a subset of $V(f)\cap D(g)$.

The formulas $\gamma_{0}(X)$ and $\gamma_{1}(X)$ that we promised above are
simply the conditions in (3) and (4), each prefixed by $\exists
Y_{1}\cdots\exists Y_{e}$. Clearly these formulas have the same number of
quantifiers as $\beta$. The first formula corresponds to a subset $V(r,q)\cap
D(gc_{d})$ of $V(f)\cap D(g)$ because $r+b_{d_{1}}Y_{e}^{d_{1}-d}q=c_{d}f$.
Hence the dimension of the subset cannot exceed the dimension of $V(f)\cap
D(g)$. However, $r$ and $q$ were constructed to have lower multidegree than
$f$, so $\gamma_{0}$ has strictly smaller rank than $\beta$.

On the other hand, the affine variety over $F^{\prime}$ defined by the latter
formula is a proper closed subset of $V(f)$, hence

$\textnormal{dim}(V(f,c_{d}))\cap
D(g))\leq\textnormal{dim}(V(f,c_{d})))<\textnormal{dim}(V(f))=\textnormal{dim}(V(f))\cap
D(g))$

showing that $\gamma_{1}$ has strictly smaller rank than $\beta$. ∎

Putting these results together yields the following normal form theorem for
existential formulas in algebraic extensions of $\mathbb{Q}$.

######  Definition 4.7.

An _absolutely irreducible hypersurface formula_ is a formula of the form

$\exists Y_{1}\dots\exists Y_{e}~{}[f(X,Y_{1},\dots,Y_{e})=0\neq
g(X,Y_{1},\dots,Y_{e})]$

for polynomials $f,g\in\overline{\mathbb{Q}}[X,Y_{1},\dots,Y_{e}]$, where $f$
is absolutely irreducible and does not divide $g$.

######  Theorem 4.8 (Normal Form for Existential Definitions).

For any field $L\subseteq\overline{\mathbb{Q}}$, if $A\subseteq L$ is
existentially definable in $L$, then $A$ is definable in $L$ by a formula of
the form

$\alpha(X)=\vee_{i=1}^{r}\beta_{i}(X),$

where each $\beta_{i}(X)$ has one of the following forms:

  1. (i)

The quantifier-free formula $X=z_{0}$ for a fixed $z_{0}\in L$.

  2. (ii)

An absolutely irreducible hypersurface formula with coefficients from $L$
which is satisfied by infinitely many $x\in L$.

###### Proof.

Apply Propositions 4.4 and 4.6, plus the following two observations. If $f$
divides $g$ in any of the hypersurface formulas, then that formula is
unsatisfiable. If a hypersurface formula is satisfied by at most finitely many
$x\in L$ (including if it is unsatisfiable), then it could be replaced by a
(possibly empty) disjunction of formulas of the form $X=z_{0}$, lowering the
rank. ∎

##  5\. The meagerness of definability

Recall that by identifying a subset of $\overline{\mathbb{Q}}$ with its
characteristic function, we can consider the set
$\operatorname{Sub}(\overline{\mathbb{Q}})=\\{L\subseteq\overline{\mathbb{Q}}:L\text{
is a field}\\}$ as a subset of $2^{\overline{\mathbb{Q}}}$, from which it
inherits the product topology. A basis for the topology is given by the sets

$U_{\vec{a},\vec{b}}=\\{L\in\operatorname{Sub}(\overline{\mathbb{Q}}):a_{1},\dots
a_{n}\in L\text{ and }b_{1},\dots,b_{k}\not\in L\\}$

for any finite sequences of elements $\vec{a},\vec{b}$ from
$\overline{\mathbb{Q}}$. If $\vec{b}$ is empty, we write simply $U_{\vec{a}}$.

Recall that _Cantor space_ , denoted $2^{\omega}$, is the set of infinite
binary sequences with the product topology.

######  Proposition 5.1.

The space $\operatorname{Sub}(\overline{\mathbb{Q}})$ is homeomorphic to
Cantor space.

###### Proof.

Since $\operatorname{Sub}(\overline{\mathbb{Q}})$ is a closed subset of the
Cantor-homeomorphic space $2^{\overline{\mathbb{Q}}}$, it suffices to show
that $\operatorname{Sub}(\overline{\mathbb{Q}})$ has no isolated points. But
it is clear that whenever $U_{\vec{a},\vec{b}}$ is non-empty, there is
$c\in\overline{\mathbb{Q}}$ such that both $U_{(\vec{a},c),\vec{b}}$ and
$U_{\vec{a},(\vec{b},c)}$ are nonempty. ∎

The upshot of Proposition 5.1 is a structure on the set
$\operatorname{Sub}(\overline{\mathbb{Q}})$ which allows us to describe when a
set is “large” or “small” in terms of topology. In particular, we enlist the
notions of meager sets and the property of Baire.

######  Definition 5.2.

A subset of a topological space is called _nowhere dense_ if its closure has
empty interior, and _meager_ if it is the countable union of nowhere dense
sets. A topological space is _Baire_ 111Some authors use the terminology
_Baire space_ to refer to topological spaces with this property. However, we
reserve the name Baire space for the particular topological space
$\omega^{\omega}$, which is discussed in related papers, such as [9], although
we will not use it in this paper. if every non-empty open subset is non-
meager.

Cantor space $2^{\omega}$ is Baire, and by Proposition 5.1 the same is true
for $\operatorname{Sub}(\overline{\mathbb{Q}})$, which allows us to consider
meager sets to be small.

######  Definition 5.3.

For any $Z\subseteq\mathbb{Q}$, and formula $\beta(X)$ with coefficients
$\vec{a}$ from $\overline{\mathbb{Q}}$, we define $S_{\beta}(Z)$ to be the set
of algebraic fields in which $\beta$ defines a subset of $Z$ in $\mathbb{Q}$:

$S_{\beta}(Z)=\\{L\in U_{\vec{a}}:\\{x\in\mathbb{Q}:\beta(x)\text{ holds over
}L\\}\subseteq Z\\}.$

######  Proposition 5.4.

Let $Z$ be a subset of $\mathbb{Q}$ such that $\mathbb{Q}\setminus Z$ is not
thin in $\mathbb{Q}$. Then for every absolutely irreducible hypersurface
formula

$\beta(X)=\exists\vec{Y}[f(X,\vec{Y})=0\neq g(X,\vec{Y})]$

with coefficients $\vec{a}$ from $\overline{\mathbb{Q}}$, the set
$S_{\beta}(Z)$ is nowhere dense in $U_{\vec{a}}$.

###### Proof.

Let $\vec{b}$ and $\vec{c}$ be any sequences of elements of
$\overline{\mathbb{Q}}$ such that
$U_{(\vec{a},\vec{c}),\vec{b}}\neq\emptyset$. Let
$F=\mathbb{Q}(\vec{a},\vec{c})$ and let $K=F(\vec{b})$. By the application of
Hilbert’s Irreducibility Theorem in Proposition 2.13, there is a thin set
$T\subseteq K^{e}$ such that for any $(x,y_{1},\dots,y_{e-1})\in
K^{e}\setminus T$, the polynomial $f(x,y_{1},\dots,y_{e-1},Y_{e})$ is
irreducible of degree $\textnormal{deg}_{Y_{e}}(f)$, and
$g(x,y_{1},\dots,y_{e-1},Y_{e})$ is not divisible by $f$. Because $K$ is a
number field, $T_{\mathbb{Q}}=T\cap\mathbb{Q}^{e}$ is also a thin set in
$\mathbb{Q}^{e}$ by Proposition 2.10. Further, since $\mathbb{Q}\setminus Z$
is not thin in $\mathbb{Q}$, the thin set $T_{\mathbb{Q}}$ does not contain
all of $(\mathbb{Q}\setminus Z)\times\mathbb{Q}^{e-1}$ by Lemma 2.12. For any
such tuple $(x,y_{1},\dots,y_{e-1})\in(\mathbb{Q}\setminus
Z)\times\mathbb{Q}^{e-1}$ outside this thin set, the irreducibility of
$f(x,y_{1},\dots,y_{e-1},Y)$ over $K$ implies that adjoining to $F$ any root
$y$ of $f(x,y_{1},\dots,y_{e-1},Y)$ will not generate any element of $K$: we
will have $F(y)\cap K=F$, by Lemma 2.1. Thus $U_{(\vec{a},\vec{c},y),\vec{b}}$
is nonempty. Additionally, the divisibility condition implies that
$g(x,y_{1},\dots,y_{m-1},y)\neq 0$. Therefore, $U_{(\vec{a},\vec{c},y),b}\cap
S_{\beta}(Z)=\emptyset$. ∎

######  Theorem 5.5.

The set of all fields $L\in\operatorname{Sub}(\overline{\mathbb{Q}})$ such
that $\mathcal{O}_{L}$ is either existentially or universally definable in $L$
is meager.

###### Proof.

By Proposition 2.11, neither $\mathbb{Z}$ nor $\mathbb{Q}\setminus\mathbb{Z}$
is thin in $\mathbb{Q}$. Therefore, Proposition 5.4 shows that for all
absolutely irreducible hypersurface formulas $\beta$ with coefficients from
$\overline{\mathbb{Q}}$, the sets $S_{\beta}(\mathbb{Z})$ and
$S_{\beta}(\mathbb{Q}\setminus\mathbb{Z})$ are nowhere dense. Let

(5) $S=\bigcup_{\beta}(S_{\beta}(\mathbb{Z})\cup
S_{\beta}(\mathbb{Q}\setminus\mathbb{Z})).$

This is a countable union of nowhere dense sets, and is thus meager. We claim
that if $L\in\operatorname{Sub}(\overline{\mathbb{Q}})\setminus S$, then
neither $\mathcal{O}_{L}$ nor $L\setminus\mathcal{O}_{L}$ are existentially
definable in $L$.

If $\mathcal{O}_{L}$ is existentially definable in $L$, then it is definable
in $L$ by a formula $\alpha=\vee_{i<r}\beta_{i}$ in normal form, according to
Theorem 4.8. This formula also defines
$\mathbb{Z}=\mathbb{Q}\cap\mathcal{O}_{L}$ inside $\mathbb{Q}$ over $L$.
Because $\mathcal{O}_{L}$ is infinite and $r$ is finite, some $\beta_{i}$ must
be a hypersurface formula. Since $L\not\in S_{\beta_{i}}$, there is some
$x\in\mathbb{Q}\setminus\mathbb{Z}$ for which $\beta_{i}(x)$, and therefore
also $\alpha(x)$, holds over $L$, contradicting that $\alpha$ defines
$\mathcal{O}_{L}$ in $L$.

The same argument applied to $L\setminus\mathcal{O}_{L}$ shows that this set
cannot be existentially definable in $L$, and thus $\mathcal{O}_{L}$ is not
universally definable in $L$. ∎

The proof has shown a slightly stronger theorem.

######  Porism 5.6.

Let $L\in\operatorname{Sub}(\overline{\mathbb{Q}})$ and suppose $A\subseteq L$
is infinite and either existentially or universally definable in $L$. Then if
$A\cap\mathbb{Q}\subseteq\mathbb{Z}$ or
$A\cap\mathbb{Q}\subseteq\mathbb{Q}\setminus\mathbb{Z}$, we have $L\in S$,
where $S$ is defined as in (5) above.

######  Corollary 5.7.

The set of fields $L\in\operatorname{Sub}(\overline{\mathbb{Q}})$ such that
$\mathbb{Z}$ itself is either existentially or universally definable in $L$ is
meager.

We can also use the same approach when considering the definability of
subfields. The set $\mathbb{Q}$ is co-thin in itself, so Proposition 5.4 does
not apply to it. Nevertheless, Porism 5.6 yields a further result about the
definability of $\mathbb{Q}$ in algebraic field extensions of itself, and more
generally about the definability of number fields.

######  Corollary 5.8.

If $F$ is a number field, then the set of fields
$L\in\operatorname{Sub}(\overline{\mathbb{Q}})$ containing $F$ such that $F$
has an existential definition in $L$ is a meager set.

###### Proof.

By Park’s generalization [10] of a theorem of Koenigsmann [5], there is a
quantifier-free formula $\varphi(X,Y_{1},\ldots,Y_{n})$, in the language of
fields, such that $\exists\vec{Y}\varphi(X,\vec{Y})$ defines the algebraic
non-integers $F\setminus\mathcal{O}_{F}$ in the field $F$. In particular, it
defines $\mathbb{Q}\setminus\mathbb{Z}$ in $\mathbb{Q}$ over $F$. Now if
$\gamma(Y)$ is existential and defines $F$ in $L$, then the following formula
with free variable $X$,

$\gamma(X)~{}\&~{}\exists\vec{Y}[~{}\gamma(Y_{1})~{}\&\cdots\&~{}\gamma(Y_{n})~{}\&~{}\varphi(X,\vec{Y})~{}],$

is an existential definition of $(\mathbb{Q}\setminus\mathbb{Z})$ in
$\mathbb{Q}$ over $L$. By Porism 5.6, $L\in S$. ∎

###  5.1. Computable fields whose algebraic integers are not one-quantifier
definable

Next we effectivize Theorem 5.5 to obtain many computable algebraic extensions
of $\mathbb{Q}$ whose algebraic integers are not existentially or universally
definable.

Our arguments below will require the decidability of absolute irreducibility.
Recall some standard terminology: a computable field $E$ has a _splitting
algorithm_ if the _splitting set_ $S_{E}=\\{f\in E[T]:f\text{~{}is reducible
in~{}}E[T]\\}$ is decidable, and has a _root algorithm_ if the _root set_
$R_{E}=\\{f\in E[T]:f\text{~{}has a root in~{}}E\\}$ is decidable. Notice that
these are both stated for single-variable polynomials. The next lemma is a
specific case of the fact that splitting algorithms can be extended to more
variables.

######  Lemma 5.9.

Fix any computable presentation of $\overline{\mathbb{Q}}$. Then it is
decidable which polynomials in $\overline{\mathbb{Q}}[X_{1},X_{2},\ldots]$ are
absolutely irreducible.

###### Proof.

$\overline{\mathbb{Q}}$ has a splitting algorithm, of course: all polynomials
in $\overline{\mathbb{Q}}[T]$ of degree $>1$ are reducible. The lemma now
follows from another theorem of Kronecker (found in [2, $\S\S$ 58-59]),
stating that whenever a computable field $F$ has a splitting algorithm and $t$
is transcendental over $F$ (within a larger computable field), the field
$F(t)$ also has a splitting algorithm. The irreducible polynomials of
$\overline{\mathbb{Q}}[X_{1},X_{2}]$ are precisely the irreducible polynomials
of $\overline{\mathbb{Q}}[X_{1}]$ along with the polynomials which are
irreducible in $\overline{\mathbb{Q}}(X_{1})[X_{2}]$ and have no common factor
among the coefficients lying in $\overline{\mathbb{Q}}[X_{1}]$; see [6,
Theorem IV.2.3]. Therefore, reducibility is clearly decidable using
Kronecker’s result. Thus we can decide reducibility in
$\overline{\mathbb{Q}}[X_{1},X_{2}]$, and one continues by induction on the
number $n$ of variables, noting that the resulting decision procedures are
uniform in $n$. ∎

Therefore, there is a computable listing $\beta_{1},\beta_{2},\dots$ of all
absolutely irreducible hypersurface formulas. Furthermore, we have the
following effective version of Proposition 5.4.

######  Proposition 5.10.

Let $Z$ be a computable subset of $\mathbb{Q}$ such that $\mathbb{Q}\setminus
Z$ is not thin in $\mathbb{Q}$. Then there is an algorithm which, given any
absolutely irreducible hypersurface formula $\beta$ with coefficients
$\vec{a}$, and any $\vec{c},\vec{b}$ such that
$U_{(\vec{a},\vec{c}),\vec{b}}\neq\emptyset$, returns $y$ such that
$U_{(\vec{a},\vec{c},y),\vec{b}}$ is non-empty and has empty intersection with
$S_{\beta}(Z)$.

###### Proof.

The proof of Proposition 5.4 shows that there is a tuple
$(x,y_{1},\dots,y_{e-1},y)\in(\mathbb{Q}\setminus
Z)\times\mathbb{Q}^{e-1}\times\overline{\mathbb{Q}}$ which witnesses that
$\beta(x)$ holds in any field extending $\mathbb{Q}(y)$ while keeping
$U_{(\vec{a},\vec{c},y),\vec{b}}$ non-empty. So an algorithm can search all
such $x,y_{1},\dots,y_{e-1},y$ until it finds one. This works because $Z$ is
computable, and it is computable to check whether a given tuple from
$\overline{\mathbb{Q}}$ satisfies the polynomials appearing in $\beta$, and
computable to check whether $U_{(\vec{a},\vec{c},y),\vec{b}}$ is empty. ∎

######  Theorem 5.11.

For every pair of $\overline{\mathbb{Q}}$-tuples $\vec{a},\vec{b}$, there is a
computable $L\in U_{\vec{a},\vec{b}}$ such that $\mathcal{O}_{L}$ is neither
existentially or universally definable in $L$. Moreover, every computable
presentation of $L$ has a splitting algorithm.

###### Proof.

We define sequences $\vec{a}=\vec{a}_{0},\vec{a}_{1},\dots$ and
$\vec{b}=\vec{b}_{0},\vec{b}_{1},\dots$ in stages as follows. Recall that
$\beta_{1},\beta_{2},\dots$ is a computable listing of all absolutely
irreducible hypersurface formulas. Let $c_{1},c_{2},\dots$ be a computable
listing of all elements of $\overline{\mathbb{Q}}$.

At stages of the form $s=3t+1$, given $U_{\vec{a}_{s-1},\vec{b}_{s-1}}$
nonempty, use Proposition 5.10 to find a $y$ such that
$U_{(\vec{a}_{s-1},y),\vec{b}_{s-1}}$ is non-empty and disjoint from
$S_{\beta_{t}}(Z)$. Let $\vec{a}_{s}=(\vec{a}_{s-1},y)$ and
$\vec{b}_{s}=\vec{b}_{s-1}$.

At stages of the form $s=3t+2$, use an analogous process to avoid
$S_{\beta_{t}}(\mathbb{Q}\setminus Z)$.

At stages of the form $s=3t+3$, consider
$U_{(\vec{a}_{s-1},c_{t}),\vec{b}_{s-1}}$ and if it is nonempty, set
$\vec{a}_{s}=(\vec{a}_{s-1},c_{t}),\vec{b}_{s}=\vec{b}_{s-1}$. Otherwise, set
$\vec{a}_{s}=\vec{a}_{s-1}$ and $\vec{b}_{s}=(\vec{b}_{s-1},c_{t})$.

Let $E=\\{a\in\overline{\mathbb{Q}}:a\text{ appears in some }\vec{a}_{s}\\}$.
Then $E$ is computable because by stage $3(t+1)$ it has been decided whether
$c_{t}$ is included. And $E$ does not have any existential or universal
definition of $\mathcal{O}_{E}$ because by construction $E$ avoids the set $S$
from Theorem 5.5.

The splitting algorithm for $L$ follows from Rabin’s Theorem (see [12]), since
$L$ is given as a decidable subfield of (our computable presentation of)
$\overline{\mathbb{Q}}$. Finally, whenever $L\cong\widetilde{L}$ are
computable algebraic fields, their splitting sets are Turing-equivalent, so
all computable presentations of $L$ have splitting algorithms. ∎

###  5.2.  The topological space of algebraic extensions of $\mathbb{Q}$ up to
isomorphism

The questions of definability we have considered have the same answer over
isomorphic fields. Although $\operatorname{Sub}(\overline{\mathbb{Q}})$
contains at least one isomorphic copy of every possible algebraic extension of
$\mathbb{Q}$, it contains exactly one copy of an algebraic extension $L$ of
$\mathbb{Q}$ if and only if $L$ is Galois over $\mathbb{Q}$. A number field
$F$ of degree $n$ is isomorphic to at most $n$ fields in
$\operatorname{Sub}(\overline{\mathbb{Q}})$, but there are some infinite non-
Galois extensions of $\mathbb{Q}$ which are isomorphic to uncountably many
elements in $\operatorname{Sub}(\overline{\mathbb{Q}})$. Therefore, given the
isomorphism invariance of the property under consideration, one might wonder
if the results of the previous section have been skewed by the fact that some
isomorphism classes are more represented in
$\operatorname{Sub}(\overline{\mathbb{Q}})$ than others.

Thus it is also of interest to consider the collection of algebraic extensions
of $\mathbb{Q}$ up to isomorphism as a topological space, as was done in [9].
We denote this set by $\operatorname{Sub}(\overline{\mathbb{Q}})/\\!\cong$.
From the perspective of number theory, the set
$\operatorname{Sub}(\overline{\mathbb{Q}})/\\!\cong$ can be identified as a
quotient of $\operatorname{Sub}(\overline{\mathbb{Q}})$ by the absolute Galois
group $G=\text{Gal}(\overline{\mathbb{Q}}/\mathbb{Q})$, which equates
isomorphic fields. The topology on
$\operatorname{Sub}(\overline{\mathbb{Q}})/\\!\cong$ is the quotient topology
which it inherits from $\operatorname{Sub}(\overline{\mathbb{Q}})$.

Alternatively, from the perspective of computability theory, one could begin
with the space $\mathcal{ALG}_{0}^{*}$ of all possible presentations of
algebraic extensions of $\mathbb{Q}$ in a certain language. This is done in
[9] and the relevant language in this case is the language of rings enlarged
to include additional predicates for the existence of roots of monic one-
variable polynomials. Equating isomorphic fields and taking the quotient
topology leads to the space $\mathcal{ALG}_{0}^{*}/\\!\cong$, which coincides
with $\operatorname{Sub}(\overline{\mathbb{Q}})/\\!\cong$ despite various
differences between $\mathcal{ALG}_{0}^{*}$ and
$\operatorname{Sub}(\overline{\mathbb{Q}})$. For example, in
$\mathcal{ALG}_{0}^{*}$, every isomorphism class is represented with
uncountably many copies. For details about $\mathcal{ALG}_{0}^{*}$, we refer
the reader to [9].

Returning now to $\operatorname{Sub}(\overline{\mathbb{Q}})/\\!\cong$, observe
that for any $U_{\vec{a},\vec{b}}$, the following set is the smallest
$G$-invariant subset of $\operatorname{Sub}(\overline{\mathbb{Q}})$ containing
$U_{\vec{a},\vec{b}}$. It is also clopen, as there are only finitely many
images $\varphi(\vec{a}),\varphi(\vec{b})$.

$GU_{\vec{a},\vec{b}}:=\\{\varphi(L):L\in U_{\vec{a},\vec{b}},\varphi\in
G\\}=\bigcup_{\varphi\in G}U_{\varphi(\vec{a}),\varphi(\vec{b})}$

It follows that the quotient map
$q:\operatorname{Sub}(\overline{\mathbb{Q}})\rightarrow\operatorname{Sub}(\overline{\mathbb{Q}})/\\!\cong$
is open and the images of the sets $GU_{\vec{a},\vec{b}}$ form a clopen basis
for $\operatorname{Sub}(\overline{\mathbb{Q}})/\\!\cong$.

######  Proposition 5.12 (Theorem 3.3, [9]).

$\operatorname{Sub}(\overline{\mathbb{Q}})/\\!\cong$ is homeomorphic to Cantor
space.

###### Proof.

The follows because $\operatorname{Sub}(\overline{\mathbb{Q}})/\\!\cong$ is
compact, has a countable clopen basis, and has no isolated points. The last
condition follows because any non-empty $GU_{\vec{a},\vec{b}}$ contains at
least two non-isomorphic fields. ∎

Therefore, notions of meager and co-meager make sense in
$\operatorname{Sub}(\overline{\mathbb{Q}})/\\!\cong$. In order to transfer the
all our results about $\operatorname{Sub}(\overline{\mathbb{Q}})$ to results
about $\operatorname{Sub}(\overline{\mathbb{Q}})/\\!\cong$, we only need to
check the following.

######  Proposition 5.13.

Let $S\subseteq\operatorname{Sub}(\overline{\mathbb{Q}})$ be as defined in
(5), and let
$q:\operatorname{Sub}(\overline{\mathbb{Q}})\rightarrow\operatorname{Sub}(\overline{\mathbb{Q}})/\\!\cong$
be the quotient map. Then $q(S)$ is meager in
$\operatorname{Sub}(\overline{\mathbb{Q}})/\\!\cong$.

###### Proof.

Observe that $S=\cup_{\beta}GS_{\beta}$, where $\beta$ ranges over the
absolutely irreducible hypersurface formulas and

$GS_{\beta}:=\bigcup_{\varphi\in G}S_{\varphi(\beta)}.$

Here $\varphi(\beta)$ denotes the result of applying $\varphi$ to all
coefficients appearing in $\beta$. There are only finitely many possible
outcomes, so $GS_{\beta}$ is a finite union of nowhere dense sets, and thus is
nowhere dense. Additionally, since each $S_{\beta}$ is closed, so is
$GS_{\beta}$. Also, by construction $GS_{\beta}$ is $G$-invariant. Since
$\operatorname{Sub}(\overline{\mathbb{Q}})\setminus GS_{\beta}$ is dense open
and $q$ is an open map, its image
$q(\operatorname{Sub}(\overline{\mathbb{Q}})\setminus GS_{\beta})$ is dense
open. Therefore, by $G$-invariance of $GS_{\beta}$, $q(GS_{\beta})$ is nowhere
dense. Thus $q(S)=\cup_{\beta}q(GS_{\beta})$ is meager. ∎

Therefore, we have the following analogues of the results of the previous
section.

######  Corollary 5.14.

The following sets are meager in
$\operatorname{Sub}(\overline{\mathbb{Q}})/\\!\cong$:

  1. (1)

The set of isomorphism types of fields $L$ in which $\mathcal{O}_{L}$ is
existentially or universally definable.

  2. (2)

The set of isomorphism types of fields in which $\mathbb{Z}$ is existentially
or universally definable.

  3. (3)

The set of isomorphism types of fields $L$ in which some number field
$F\subset L$ is existentially definable.

###### Proof.

These sets are all contained in $q(S)$. ∎

It may seem equally natural to consider the Lebesgue measure on Cantor space
and transfer it to $\operatorname{Sub}(\overline{\mathbb{Q}})/\\!\cong$, using
some computable homeomorphism such as that obtained in [9, Theorem 3.3]. This
is attempted to some extent in [9], but the resulting measure is not
canonical: it depends to a great extent on arbitrary choices that are made
during the construction of the homeomorphism. Indeed, the notion of _Haar-
compatible measure_ , put forth in [9], has had to be abandoned, as the
reality is more complicated than the analysis in that article recognized. We
hope to investigate this situation, and measure-theoretic perspectives in
general, more fully in the near future.

## References

  * [1] Davis, M., Putnam, H., and Robinson, J. The decision problem for exponential diophantine equations.  Ann. of Math. (2) 74 (1961), 425–436.
  * [2] Edwards, H. M. Galois theory, vol. 101 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 1984.
  * [3] Fried, M. D., Haran, D., and Völklein, H. Real Hilbertianity and the field of totally real numbers.  In Arithmetic geometry (Tempe, AZ, 1993), vol. 174 of Contemp. Math. Amer. Math. Soc., Providence, RI, 1994, pp. 1–34.
  * [4] Fukuzaki, K. Definability of the ring of integers in some infinite algebraic extensions of the rationals.  MLQ Math. Log. Q. 58, 4-5 (2012), 317–332.
  * [5] Koenigsmann, J. Defining $\mathbb{Z}$ in $\mathbb{Q}$.  Ann. of Math. (2) 183, 1 (2016), 73–93.
  * [6] Lang, S. Algebra, third ed., vol. 211 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 2002.
  * [7] Liu, Q. Algebraic geometry and arithmetic curves, vol. 6 of Oxford Graduate Texts in Mathematics.  Oxford University Press, Oxford, 2002.  Translated from the French by Reinie Erné, Oxford Science Publications.
  * [8] Matiyasevich, J. V. The Diophantineness of enumerable sets.  Dokl. Akad. Nauk SSSR 191 (1970), 279–282.
  * [9] Miller, R. Isomorphism and classification for countable structures.  Computability 8, 2 (2019), 99–117.
  * [10] Park, J. A universal first-order formula defining the ring of integers in a number field.  Math. Res. Lett. 20, 5 (2013), 961–980.
  * [11] Poonen, B. Characterizing integers among rational numbers with a universal-existential formula.  Amer. J. Math. 131, 3 (2009), 675–682.
  * [12] Rabin, M. Computable algebra, general theory, and theory of computable fields.  Trans. AMS 95 (1960), 341–360.
  * [13] Reid, M. Undergraduate commutative algebra, vol. 29 of London Mathematical Society Student Texts.  Cambridge University Press, Cambridge, 1995.
  * [14] Robinson, J. Definability and decision problems in arithmetic.  J. Symbolic Logic 14 (1949), 98–114.
  * [15] Robinson, J. The undecidability of algebraic rings and fields.  Proc. Amer. Math. Soc. 10 (1959), 950–957.
  * [16] Robinson, J. On the decision problem for algebraic rings.  In Studies in mathematical analysis and related topics. Stanford Univ. Press, Stanford, Calif, 1962, pp. 297–304.
  * [17] Rumely, R. S. Undecidability and definability for the theory of global fields.  Trans. Amer. Math. Soc. 262, 1 (1980), 195–217.
  * [18] Serre, J.-P. Topics in Galois theory, second ed., vol. 1 of Research Notes in Mathematics.  A K Peters, Ltd., Wellesley, MA, 2008.  With notes by Henri Darmon.
  * [19] Shlapentokh, A. First-order decidability and definability of integers in infinite algebraic extensions of the rational numbers.  Israel J. Math. 226, 2 (2018), 579–633.
  * [20] Videla, C. R. Definability of the ring of integers in pro-$p$ Galois extensions of number fields.  Israel J. Math. 118 (2000), 1–14.