Hilbert’s tenth problem over rings of algebraic integers

Master Defence

Tim B. Herbstrith

28 February 2020

Hilbert’s tenth problem, Turing machines, and decidability

Hilbert’s tenth problem

Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers.

– Hilbert (1900)

Figure 1: Portrait of David Hilbert (1912)
(Published in Reid and Weyl 1970)

Decision problems

Definition

A decision problem is a subset of the set of finite \mathtt 0-\mathtt 1-strings ω = \lbrace \mathtt{0, 1} \rbrace^* including the empty string \lambda.

An injective function \mathcal{Q} → ω, \; x ↦ \ulcorner x \urcorner is called an encoding.

Example: Simple graphs

The set of all simple graphs can be encoded by strings of the form

\begin{array}{lllll} x := & b_{1, 2} & b_{1, 3} & … & b_{1, n}\\ & & b_{2, 3} & … & b_{2,n}\\ & & & \ddots & \vdots \\ & & & & b_{n-1, n}. \end{array}

Turing machines

Definition

A Turing machine \mathbb{A} on the alphabet A = \lbrace\mathtt{\texttt{\S}, \_, 0, 1}\rbrace consists of

a finite set of states S containing s_{start}, s_{halt} and
a transition function

δ: S \times A \to S \times A \times \lbrace -1, 0, 1 \rbrace.

A Turing machine adding 1 to a number in (reversed) binary encoding.

I write \mathbb{A}(x) for the output of Turing machine \mathbb{A} on input x ∈ ω if \mathbb{A} halts on x.

Computability, decidability, and semi-decidability

Definition

A partial function f: ω \to ω is computable if there is a Turing machine \mathbb{A} with \mathbb{A}(x) = f(x) for all x in the domain of f.
A decision problem Q is decidable if its characteristic function 𝟙{}_Q is computable.
A decision problem Q is semi-decidable or computably enumerable if there exists a Turing machine \mathbb{A} such that x ∈ Q \quad ⇔ \quad \mathbb{A}(x) = \mathtt 1.

The halting set

Definition

The halting set is the set of all codes of Turing machines \mathbb{A} that halt upon receiving their code as input i.e.

\mathcal{K} := \left\lbrace \ulcorner \mathbb{A} \urcorner \mid \mathbb{A} \text{ halts on } \ulcorner \mathbb{A} \urcorner \right\rbrace

Theorem

The halting set \mathcal{K} is semi-decidable but not decidable.

Some number theory

Algebraic integers

Definition

An element α \in ℂ is called algebraic integer if there exists a monic polynomial p \in ℤ[X] such that

p(α) = α^n + c_{n - 1} α^{n - 1} + … + c_0 = 0

We write \mathcal{O}_{} for the set of all algebraic integers …
… and if K is a number field, i.e. K is finite extension of ℚ, we set \mathcal{O}_{K}= \mathcal{O}_{} ∩ K.
For K = ℚ we find \mathcal{O}_{ℚ} = \mathcal{O}_{} ∩ ℚ = ℤ.

Properties of algebraic integers

Proposition

Both \mathcal{O}_{} and \mathcal{O}_{K} are sub-rings of ℂ (for all K).
\mathcal{O}_{K} is a finitely generated free ℤ-module (for all K). A basis is called integral basis.
The quotient field of \mathcal{O}_{K} is (isomorphic to) K.

Diophantine sets

At the core of Hilbert’s Problem

Diophantine Sets

Definition

Let R be a commutative ring with unit. A set S \subseteq R^n is called Diophantine if there exists a polynomial p \in R[{X}_1, \ldots, {X}_{n}, {Y}_1, \ldots, {Y}_{m}] such that

\begin{aligned} &({α}_1, \ldots, {α}_{n}) \in S ⇔ \\ &\quad \exists {y}_1, \ldots, {y}_{m} \in R^m : \\ &\quad \quad p({α}_1, \ldots, {α}_{n}, {y}_1, \ldots, {y}_{m}) = 0 \end{aligned}

Diophantine sets are projections of vanishing sets of a polynomial.

Examples of Diophantine Sets

Let R be an integral domain. Then every finite set S \subset R is Diophantine.

Proof

Take

p(X) = \prod_{α ∈ S} (X - α).

Examples of Diophantine sets

The set of natural numbers ℕ is Diophantine over ℤ.

Proof

Using Minkowski’s theorem on convex bodies one can prove that

α ∈ ℕ \quad \Leftrightarrow \quad \exists β_1, β_2, β_3, β_4 \in ℤ: α = β_1^2 + β_2^2 + β_3^2 + β_4^2.

This fact is known as Lagrange’s foure square theorem.

Examples of Diophantine sets

Let K be a number field and \mathcal{O}_{K} its ring of algebraic integers. Then \mathcal{O}_{K}\setminus \left\lbrace 0 \right\rbrace is Diophantine over \mathcal{O}_{K}.

Proof

Using the Chinese remainder theorem one can prove that

α ≠ 0 \quad ⇔ \quad ∃ β, γ ∈ \mathcal{O}_{K}: α β = (2 γ - 1)(3 γ - 1).

Unions and conjunctions of Diophantine sets are Diophantine

Lemma

If S_1 and S_2 are Diophantine over \mathcal{O}_{K}, so are

S_1 ∪ S_2 \quad \text{and} \quad S_1 ∩ S_2.

The respective polynomial identities can be found effectively.

In the easy example \mathcal{O}_{K}= ℤ one obtains P = p^2 + q^2.

Let p_1(X, Y), p_2(X, Y) ∈ \mathcal{O}_{K}{}{[X, Y]} give Diophantine definitions of S_1 and S_2.

We have S_1 ∪ S_2 = \left\lbrace α \mid ∃ y ∈ \mathcal{O}_{K}: p_1(α, y) p_2(α, y) = 0 \right\rbrace.

To prove the claim for intersections of Diophantine sets, let

h(T) = a_m T^m + … + a_1 T + a_0 ∈ \mathcal{O}_{K}{}[T]

be a polynomial of degree m > 0 without roots in \mathrm{Quot}\, \mathcal{O}_{K}= K. Then \overline h(T) = T^m h(T^{-1}) does not have roots in K either.

Set

H(X, Y_1, Y_2) = \sum_{i=0}^m a_i p_1(X, Y_1)^i p_2(X, Y_2)^{m - i},

then

∃ y_1, y_2 ∈ \mathcal{O}_{K}: H(α, y_1, y_2) = 0 \quad ⇔ ∃ y_1 ∈ \mathcal{O}_{K}: p_1(α, y_1) = 0 \text{ and } ∃ y_2 ∈ \mathcal{O}_{K}: p_2(α, y_2) = 0

Hilbert’s tenth problem over algebraic integers

Fix a number field K. Hilbert’s tenth problem over \mathcal{O}_{K} can informally be stated as

H10: Does there exists an algorithm, deciding for every integer n > 0, every Diophantine set S ⊂ {\mathcal{O}_{K}}^n and every α ∈ {\mathcal{O}_{K}}^n, whether α ∈ S?

Which subsets of \mathcal{O}_{K} are Diophantine?

Model theory

Towards a modern formulation of Hilbert’s problem

Alternative view of Diophantine sets

Definition

Let R be a commutative ring with unit.

The language of rings with unity is \mathcal{L}_{ring} = \left\lbrace \mathtt{+, -, \cdot; 0, 1} \right\rbrace
The R-language is \mathcal{L}_{R} = \mathcal{L}_{ring} ∪ \left\lbrace \mathtt{c}_r \mid r ∈ R \right\rbrace.

Lemma

A set S \subseteq R^n is Diophantine over R iff

({α}_1, \ldots, {α}_{n}) ∈ S \quad ⇔ \quad \mathfrak{R} \models ∃ \mathtt{{y}_1, \ldots, {y}_{m}}: ϕ({α}_1, \ldots, {α}_{n}, \mathtt{{y}_1, \ldots, {y}_{m}})

holds for an atomic \mathcal{L}_{R}-formula ϕ. Here \mathfrak{R} denotes the \mathcal{L}_R-structure of R.

Decidability of theories

Definition

Let \mathcal{L} be a language.

An \mathcal{L}-theory is a set of \mathcal{L}-sentences.
An \mathcal{L}-theory \mathtt{Th} is (semi-)decidable if the set of encodings \left\lbrace \ulcorner ϕ \urcorner \mid ϕ ∈ \mathtt{Th} \right\rbrace ⊂ ω is (semi-)decidable.

Important theories for deciding Hilbert’s tenth problem

Let \mathfrak{R} be an \mathcal{L}_{ring}-structure with universe R.

	Quantifiers	Operators	Language
purely Diophantine theory \mathtt{H10}^*(\mathfrak{R})	∃	none	\mathcal{L}_{ring}
primitive positive theory \mathtt{Th}_{∃+}(\mathfrak{R})	∃	∧	\mathcal{L}_{ring}
full theory \mathtt{Th}(\mathfrak{R})	∃, ∀	∧, ∨, ¬	\mathcal{L}_{ring}
Diophantine theory \mathtt{H10}(\mathfrak{R})	∃	none	\mathcal{L}_{R}
primitive positive diagram D_{∃+}(\mathfrak{R})	∃	∧	\mathcal{L}_{R}
complete diagram D^c(\mathfrak{R})	∃, ∀	∧, ∨, ¬	\mathcal{L}_{R}
atomic diagram D(\mathfrak{R})	none	¬	\mathcal{L}_{R}

Relationships of the theories

Hilbert’s tenth problem over algebraic integers

Fix a number field K. We restate Hilbert’s tenth problem over \mathcal{O}_{K} as

H10: Is the Diophantine theory \mathtt{H10}(\mathfrak{O}_K) decidable?

Hilbert’s tenth problem is semi-decidable

Remark

The atomic diagram D(\mathfrak{O}_K) is decidable, since \mathcal{O}_{K} is a finitely generated free ℤ-algebra.

Hence, for every polynomial p ∈ \mathcal{O}_{K}[{X}_1, \ldots, {X}_{n}], the relation \mathfrak{p}({α}_1, \ldots, {α}_{n}) \; :⇔ \; p({α}_1, \ldots, {α}_{n}) = 0 is computable.

We conclude that \mathtt{H10}^*(\mathfrak{O}_K) and \mathtt{H10}(\mathfrak{O}_K) are semi-decidable.

Note: We identify \mathcal{O}_{K} with \left\lbrace \ulcorner \mathtt{c}_α \urcorner \mid α ∈ \mathcal{O}_{K} \right\rbrace \subseteq ω.

many-one-reducibility and semi-decidable sets

Definition

A problem Q is many-one reducible to a second problem Q' if there exists a total computable function f ∶ ω → ω such that x ∈ Q \quad ⇔ \quad f(x) ∈ Q'.

One writes Q ≤_m Q'.

Proposition

Let Q, Q' \subseteq ω be problems such that Q ≤_m Q'. Then if Q' is semi-decidable, so is Q.
If Q is semi-decidable, then Q ≤_m \mathcal{K}.

Relationships of the theories w.r.t many-one reducibility

If we prove that \mathcal{K} ≤_m \mathtt{H10}^*(\mathfrak{O}_k), the diagram collapses

Hilbert’s tenth problem over ℤ

DPRM theorem (Matijasevič 1970)

A subset of ℕ is semi-decidable if and only if it is Diophantine over ℤ.

Corollary

\mathcal{K} \subseteq ℕ is Diophantine over ℤ. As a consequence \mathtt{H10}(\mathfrak{Z}) is undecidable.

Going up

Lemma

Let L / K be an extension of algebraic number fields. If \mathtt{H10}(\mathfrak{O}_K) is undecidable and \mathcal{O}_{K} is Diophantine over \mathcal{O}_{L}, then \mathtt{H10}(\mathfrak{O}_L) is undecidable.

Proof

Assume to the contray, that \mathtt{H10}(\mathfrak{O}_L) is decidable.

Let p_K ∈ \mathcal{O}_{L}[X, \mathbf{Y}] give a Diophantine definition of \mathcal{O}_{K} over \mathcal{O}_{L}.

If q ∈ \mathcal{O}_{K}{}[X_1, …, X_n], then q has roots in \mathcal{O}_{K} if and only if

∃ {x}_1, \ldots, {x}_{n} ∈ \mathcal{O}_{L} \; ∃ {\mathbf{y}}_1, \ldots, {\mathbf{y}}_{n} ∈ \mathcal{O}_{L}^k : q({x}_1, \ldots, {x}_{n}) = 0 ∧ \bigwedge_{i=1}^n p_K(x_i, \mathbf{y}_i) = 0.

We conclude that \mathtt{H10}(\mathfrak{O}_K) is decidable.

A Diophantine definition of rational integers is key

Corollary

If ℤ is Diophantine over \mathcal{O}_{K} then \mathtt{H10}(\mathfrak{O}_K) is undecidable.

Theorem

If ℤ is Diophantine over \mathcal{O}_{K}, then \mathcal{K} ≤_m \mathtt{H10}^*(\mathfrak{O}_K).

DPRM Theorem over \mathcal{O}_{K} (Davis et al. 1976)

Every semi-decidable subset of \mathcal{O}_{K} is Diophantine over \mathcal{O}_{K} if and only if ℤ is Diophantine over \mathcal{O}_{K}.

Hilbert’s tenth problem over totally real number fields and number fields with one pair of non-real embeddings

Two sequences solving Pell’s equation

Definition

Let K be a totally real number field or a number field with exactly one pair of non-real embeddings and at least one real embedding and a ∈ \mathcal{O}_{K}. We set

δ(a) := \sqrt{a^2 - 1} and
ε(a) := a + δ(a).

If δ(a) ∉ K, we define \mathrm x_m(a), \mathrm y_m(a) by

\mathrm x_m(a) + δ(a) \mathrm y_m(a) = ε(a)^m.

Lemma

(±\mathrm x_m(a), ±\mathrm y_m(a))_{m ∈ ℕ} are essentially all solutions to Pell’s equation i.e. if

α^2 - δ(a)^2 β^2 = 1 \quad \text{and} \quad x + δ(a) y = (α + δ(a)β)^ν,

then x = ±\mathrm x_m(a) and y = ±\mathrm y_m(a) for some m ∈ ℕ. Here ν = |μ(K)|.

Notation

Let K be number field of degree n = [K : ℚ] and let {σ}_1, \ldots, {σ}_{n} denote all embeddings of K into ℂ.
r_K denotes the number of real embeddings and s_K the number of pairs of pairs of non-real embeddings.
All embeddings σ_i with 2 s_K < i are assumed to be real and σ_1 := \mathop{\mathrm{id}}_K.

Main Lemma

Let K ≠ ℚ be a number field of degree n > 1, let a ∈ \mathcal{O}_{K} and r_K satisfy

\begin{cases} r_K = n > 1\\ a > 2^{2(n + 1)}\\ 0 < σ_i(a) < \frac{1}{2} &\text{for } 1 < i ≤ n \end{cases} \quad \text{or} \quad \begin{cases} r_K = n - 2 > 0\\ |σ_i(a)| > 2^{2(n + 1)} &\text{for } i ∈ \left\lbrace 1, 2 \right\rbrace\\ 0 < σ_i(a) < \frac{1}{2} &\text{for } 2 < i ≤ n \end{cases},

and let ν = |μ(K)|. Define S \subseteq \mathcal{O}_{K} by ξ ∈ S ⇔ ∃ x, y, w, z, u, v, s, t, x', y', w', z', u', v', s', t', b ∈ \mathcal{O}_{K}:

\begin{array}{lll} \begin{cases} x'^2 - (a^2 - 1) y'^2 = 1 \\ w'^2 - (a^2 - 1) z'^2 = 1 \\ u'^2 - (a^2 - 1) v'^2 = 1 \\ s'^2 - (b^2 - 1) t'^2 = 1 \end{cases} & \begin{cases} x + δ(a) y = {(x' + δ(a) y')}^ν \\ u + δ(a) v = {(u' + δ(a) v')}^ν \\ s + δ(b) y = {(s' + δ(b) t')}^ν \end{cases} & \begin{array}{lr} 0 < σ_i(b) < 2^{-18}, & s_K + 1 < i ≤ n \\ \begin{cases} |σ_i(z)| ≥ C \\ |σ_i(u)| ≥ ½ \end{cases}, & s_K + 1 < i ≤ n\\ v ≠ 0, \quad z^2 \mid v & \\ \end{array} \\ w + δ(a) z = (w' + δ(a) {z')}^{νe} & b \equiv 1 \mod (z) & 2^{n + 1} \prod_{i = 0}^{n - 1} (ξ + i)^n (x + i)^n \mid z \\ s \equiv x \mod (u) & t \equiv ξ \mod (z) & b \equiv a \mod (u) \end{array}

Then S is Diophantine over \mathcal{O}_{K} and νℕ \subseteq S \subseteq ℤ.

Idea of the proof

By the previous lemma, there exist integers k, h, m, j ∈ ℕ such that

can be replaced by

\begin{aligned} x &= ±\mathrm x_k(a), & y &= ±\mathrm y_k(a), \\ w &= ±\mathrm x_{eh}(a), & z &= ±\mathrm y_{eh}(a),\\ u &= ±\mathrm x_m(a), & v &= ±\mathrm y_m(a), \\ s &= ±\mathrm x_j(b),\; \text{and} & t &= ±\mathrm y_j(b). \end{aligned}

By a theorem of Denef and Lipshitz (1978) we conclude that ξ = ±k ∈ ℤ.

Diophantine definition of the rational integers

Theorem (Denef 1980; Pheidas 1988; Shlapentokh 1989)

Let K be a totally real number field or a number field with exactly one pair of non-real embeddings and at least one real embedding. Then ℤ is Diophantine over \mathcal{O}_{K}.

Proof

By the lemma ν ℕ ⊂ S ⊂ ℤ is Diophantine. Thus, \begin{aligned} α ∈ ℤ \; ⇔ \; ∃& β_1, β_2, β_3 ∈ \mathcal{O}_{K}:\\ & α = β_1 β_2 + β_3 ∧\\ & β_1 ∈ S ∧\\ & β_2 ∈ \left\lbrace -1, 1 \right\rbrace ∧ β_3 ∈ \left\lbrace 0, 1, …, ν - 1 \right\rbrace. \end{aligned} is a Diophantine representation of ℤ.

☛ Comments

References

Davis, M., Matijasevič, Y., & Robinson, J. (1976). Hilbert’s tenth problem: Diophantine equations: Positive aspects of a negative solution. In Mathematical developments arising from Hilbert problems (Proc. Sympos. Pure Math., Vol. XXVIII, Northern Illinois Univ., De Kalb, Ill., 1974) (pp. 323–378). Amer. Math. Soc., Providence, R. I.

Denef, J. (1980). Diophantine sets over algebraic integer rings. II. Trans. Amer. Math. Soc., 257(1), 227–236. https://doi.org/10.2307/1998133

Denef, J., & Lipshitz, L. (1978). Diophantine sets over some rings of algebraic integers. J. London Math. Soc. (2), 18(3), 385–391. https://doi.org/10.1112/jlms/s2-18.3.385

Hilbert, D. (1900). Mathematische Probleme. Vortrag, gehalten auf dem internationalen Mathematiker-Kongreß zu Paris 1900. Nachrichten von der Königl. Gesellschaft der Wissenschaften zu Göttingen., 253–279.

Matijasevič, J. V. (1970). The Diophantineness of enumerable sets. Doklady Akademii Nauk SSSR, 191, 279–282.

Pheidas, T. (1988). Hilbert’s tenth problem for a class of rings of algebraic integers. Proc. Amer. Math. Soc., 104(2), 611–620. https://doi.org/10.2307/2047021

Reid, C., & Weyl, H. (1970). Hilbert. Springer Berlin Heidelberg.

Shlapentokh, A. (1989). Extension of Hilbert’s tenth problem to some algebraic number fields. Comm. Pure Appl. Math., 42(7), 939–962. https://doi.org/10.1002/cpa.3160420703