UNDECIDABILITY OF Q(2) .
CARLOS MARTINEZ-RANERO, JAVIER UTRERAS, AND CARLOS R. VIDELA

Abstract. It is shown that the compositum Q(2) of all degree 2 extensions
of Q has undecidable theory.

MSC: 11U05, 03B25, 11R11.
1. Introduction
In this note we are interested in the following question.
Problem 1. For which infinite algebraic extensions K of Q is the theory Th(K)
undecidable?
This question was first raised by A. Tarski and J. Robinson. In the 1930’s
A. Tarski showed that Qalg and R ∩ Qalg have decidable theories, and in 1959
J. Robinson showed that all number fields (that is, finite extensions of Q) have
undecidable theory. Since there are uncountably many, non-elementarily equivalent,
infinite algebraic extensions of Q and only countably many decision algorithms, it
follows that most of them are undecidable. Such examples were pointed out by
J. Robinson [4]: for any non-recursive set S of prime numbers the field QS =
√
Q({ p : p ∈ S}) has undecidable theory. Later the third named author [7] showed
that the field QS has undecidable theory for any infinite set of primes S.
An interesting class of fields in which to study the above question, and to test
current methods is the class of fields K (d) , which are the compositum of all extensions fields F/K of degree at most d over K, where K is a number field.
These fields are Galois over K of infinite degree over K, and every element of
Gal(K (d) /K) has order dividing d!. Thus Gal(K (d) /K) is a pro-S Galois extension,
where S is the set of prime numbers that divide d!.
E. Bombieri and U. Zannier [1] conjecture that these fields have the Northcott
property making them, in this respect, similar to number fields. They proved that
K (2) has the Northcott property.
The first named author was partially supported by Proyecto VRID-Enlace No. 218.015.0221.0.
The second named author was supported by FONDECYT-Postdoctorado No. 3160301.
Part of this work was done while the third author was visiting X. Vidaux in Concepción during
May 2018 under Conicyt Project: Fondecyt 1170315.
1

2

CARLOS MARTINEZ-RANERO, JAVIER UTRERAS, AND CARLOS R. VIDELA

In this note, we show the following result:
Main Theorem. The theory Q of R. Robinson is first-order interpretable in Q(2) ,
hence T h(Q(2) ) is undecidable.
X. Vidaux and C. Videla [8] establish a relation between the Northcott property
and undecidability. Based on this connection and our present result we conjecture
that all K (d) have undecidable theory.
We refer the reader to A. Shlapentokh ([5]) for an update on the subject, and to
J. Koenigsmann [2] for a general survey.
2. Undecidability
Before proceeding any further let us fix some notation. Let Qalg denote a fixed
algebraic closure of Q. Recall that for any field T ⊂ Qalg , the ring OT denotes the
integral closure of Z in T , OT× denotes the multiplicative group of units of OT and
µT denotes the group of roots of unity of the field T . Let {pn : n ∈ N≥1 } be the
√
increasing enumeration of the rational prime numbers, K = Q({ p : p is prime}),
√
L = K(i), Kn = Q({ p` : ` ≤ n}) and Ln = Kn (i). Note that L = Q(2) . Recall
that for f (x) ∈ Z[x] given by an xn + · · · + a0 and any k ∈ N, the forward difference
operator is given by ∆k f (x) = f (x + k) − f (x) and that the n-th iteration satisfies
∆nk f (x) = n!an k n .
Let Lring = {0, 1; +, ·} denote the language of rings, and for any Lring -structure
F we denote by Th(F ) its first-order Lring -theory.
In order to show that Th(L) is undecidable, we first use the following Theorem
of the third named author (see [7]).
Theorem 2. Let F be a number field and T ⊂ Q̃ a pro-p Galois extension of F ,
then OT is first-order definable in T .
In particular since L is a pro-2 Galois extension it follows that OL is first-order
definable in L. This reduces the problem to showing that the theory Th(OL ) is
undecidable. In order to do so, we use an improvement, due to C. W. Henson (see
[6]), of a result of J. Robinson (see [3]).
Lemma 3. Let R be a ring of algebraic integers and let F ⊂ P(R) be a family of
subsets of R parametrised by an Lring -formula ϕ(x; y1 , . . . , yn ), i.e.,
F ∈ F ⇐⇒ ∃b1 , . . . , bn ∈ R ∀x [x ∈ F ↔ ϕ(x; b1 , . . . , bn )]
If the family F contains sets of arbitrary large finite cardinality, then the theory of
the ring Th(R) interprets the theory Q of R. Robinson, hence is undecidable.
Moreover, in the same paper, J. Robinson proves the following result:

UNDECIDABILITY OF Q(2) .

3

Lemma 4. For each t ∈ R the set {x ∈ OK : 0  x  t} is finite where 0  x  t
means that x and all its conjugates lie strictly between 0 and t.
We are left to show that there is a family as in Lemma 3. This will be done
below.
Lemma 5. The group µL of roots of unity of L is finite.
Proof. Suppose otherwise. Fix {wk : k ∈ N} an enumeration of µL , and consider
the sequence tk = 2 + wk + wk−1 , note that each tk ∈ K and 0  tk  4, which
contradicts Lemma 4.



Let N denote the order of the finite group µL .
×
×
Lemma 6. If u is an element of OL
, then u2N ∈ OK
.
×
Proof. Fix n such that u ∈ OL
. By a theorem of H. Hasse (see [9], Theorem
n
×
×
×
4.12), we have that [OL
: µLn OK
] ∈ {1, 2}. Thus, u2 ∈ µLn OK
, so we can write
n
n
n
×
u2 = ζw for some ζ ∈ µL and w ∈ OK
. It follows from the choice of N that
n
×
u2N = wN ∈ OK
.



Lemma 7. There is a first-order definable subset W of OL such that N ⊂ W ⊂ OK .
Proof. We define, recursively, a sequence of definable sets as follows: Let X (0) =
×
2N
(n+1)
{x2N
= {x ∈ OL : ∃x1 , x2 ∈ X (n) (x = x1 −
1 + x2 : x1 , x2 ∈ OL }, and let X

x2 )}. Observe that for each n, the set X (n) is first-order definable and X (n) ⊆ OK .
Consider the following polynomial with integer coefficients
p
p
f (x) = (x + x2 + 1)2N + (x − x2 + 1)2N .
Note that for each n ∈ N, f (n) ∈ X (0) . Thus, it follows that for each k ∈ N,
2N
the 2N -th iteration of the discrete derivative ∆2N
∈ X (2N ) . By
k f = 2(2N )!k

Hilbert’s solution to Waring’s problem, there is a natural number, usually denoted
by g(2N ), so that every natural number is a sum of at most g(2N ) 2N -powers of
natural numbers. Thus,
2(2N )!

W =

[

g(2N )

{x ∈ OL : ∃x1 , . . . , xg(2N ) ∈ X

(2N )

, x=

`=0

X

xk + `}

k=1

is as required.



We are now in position to prove the main theorem of this note.
Main Theorem. The theory Th(Q(2) ) is undecidable.
Proof. Consider the family F parametrised by the formula ϕ(x, p, q)
px 6= 0 ∧ px 6= q ∧ ∃x1 , . . . , x8 ∈ W [px = x21 + · · · + x24 ∧ (q − px) = x25 + · · · + x28 ]

4

CARLOS MARTINEZ-RANERO, JAVIER UTRERAS, AND CARLOS R. VIDELA

In particular, for p, q ∈ N this means that ϕ(x; p, q) implies that 0  px  q.
Hence, it follows from Lemma 4 and Lagrange’s four square theorem that F contains
sets of arbitrary large finite cardinality.



We are unable to treat the case of K (2) , where K is an arbitrary totally real
number field.
References
[1] Bombieri, Enrico; Zannier, Umberto A note on heights in certain infinite extensions of Q.
Atti Accad. Naz. Lincei Cl. Sci. Fis. Mat. Natur. Rend. Lincei (9) Mat. Appl. 12 (2001), 5-14
(2002).
[2] Koenigsmann, Jochen Undecidability in number theory. Model theory in algebra, analysis
and arithmetic, 159-195, Lecture Notes in Math., 2111, Fond. CIME/CIME Found. Subser.,
Springer, Heidelberg, 2014.
[3] Robinson, Julia On the decision problem for algebraic rings. 1962 Studies in mathematical
analysis and related topics pp. 297-304 Stanford Univ. Press, Stanford, Calif.
[4] Robinson, Julia The decision problem for fields. 1965 Theory of Models (Proc. 1963 Internat.
Sympos. Berkeley) pp. 299-311 North-Holland, Amsterdam.
[5] Shlapentokh, Alexandra First order definability and decidability in infinite algebraic extensions of rational numbers. Israel Journal Math. 226 (2018), 579-633.
[6] van den Dries, Lou Elimination theory for the ring of algebraic integers. J. Reine Angew.
Math. 388 (1988), 189-205.
[7] Videla, Carlos R. Definability of the ring of integers in pro-p Galois extensions of number
fields. Israel J. Math. 118 (2000), 1-14.
[8] Vidaux, Xavier; Videla, Carlos R. A note on the Northcott property and undecidability. Bull.
Lond. Math. Soc. 48 (2016), no. 1, 58-62.
[9] Washington, Lawrence C. Introduction to cyclotomic fields. Second edition. Graduate Texts
in Mathematics, 83. Springer-Verlag, New York, 1997. xiv+487 pp. ISBN: 0-387-94762-0
Universidad de Concepción, Concepción, Chile, Facultad de Ciencias Fı́sicas y Matemáticas,
Departamento de Matemática, Casilla 160 C
E-mail address: cmartinezr@udec.cl
Universidad de Concepción, Concepción, Chile, Facultad de Ciencias Fı́sicas y Matemáticas,
Departamento de Matemática, Casilla 160 C
E-mail address: javierutreras@udec.cl
Mount Royal University, Calgary, Canada, Department of Mathematics and Computing
E-mail address: cvidela@mtroyal.ca