Hilbert’s tenth problem

over rings of algebraic integers

Tim B. Herbstrith

15 June 2018

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)

Turing machines

Definition

A Turing machine \(\mathbb{A}\) on the alphabet \(A = \lbrace\mathtt{\texttt{\S}, \_, 0, 1}\rbrace\) is a tuple \((S, δ)\), where \(s_{start}, s_{halt} \in S\) is a finite non-empty set, called set of states, and

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

is called transition function. If \(δ(s, a) = (s', b, m)\), one demands that the following axioms are satisfied

\(a = \texttt{\S}\) if and only if \(b = \texttt{\S}\),
If \(a = \texttt{\S}\), then \(m \neq -1\), and
If \(s = s_{halt}\), then \(s' = s_{halt}\), \(a = b\) and \(m = 0\).

Turing machines

Example: Adding \(1\) to a number in binary encoding

δ("start",    '§') = ("overflow", '§', 1 )
δ("overflow", '1') = ("overflow", '0', 1 )
δ("overflow", '0') = ("return",   '1', -1)
δ("overflow", '_') = ("return",   '1', -1)
δ("return",   '§') = ("halt",     '§', 0 )
δ("return",   b)   = ("return",   b  , -1)
δ("halt",     b)   = ("halt",     b  , 0 )

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

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\).

Example: Connected graphs

The set of all connected graphs can be encoded as the set of the respective adjacency matrices written as a string

\[b_{00}b_{01} … b_{0n}b_{10} … b_{nn}\]

of length \((n + 1)^2\).

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 is decidable if its characteristic function is computable.
A decision problem \(Q\) is semi-decidable or computably enumerable if there is a Turing machine that returns \(\mathtt{1}\) on all members of \(Q\).

Characterizations of semi-decidable sets

Proposition

Let \(Q \subseteq ω\) be a problem. The following are equivalent.

\(Q\) is semi-decidable.
\(Q\) is the range of a computable function.
There exists a computable binary relation \(R\) on \(ω^2\) such that \[ x \in Q \Leftrightarrow \exists y : R(x, y)\]

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 is semi-decidable but not decidable.

Sketch of Proof

Assume \(\mathbb{B}\) decides the halting set i.e.

\[\mathbb{B}(\ulcorner \mathbb{A} \urcorner) = \begin{cases} \mathtt 1& \text{if } \mathbb{A} \text{ halts on } \ulcorner \mathbb{A} \urcorner \\ \mathtt 0& \text{otherwise} \end{cases}. \]

Consider \(\mathbb{B}'\) defined by

\[\mathbb{B}'(\ulcorner \mathbb{A} \urcorner) = \begin{cases} \mathtt 1& \text{if } \mathbb{B}(\ulcorner \mathbb{A} \urcorner) = \mathtt 0\\ \uparrow & \text{otherwise} \end{cases}. \]

What is \(\mathbb{B}'(\ulcorner \mathbb{B}' \urcorner)\)?

Church-Turing thesis

I will use without hesitation:

The class of intuitively computable functions coincides with the class of all Turing computable functions.

Some number theory

Number fields

Definition

A number field \(K\) is a finite extension of the rationals \(ℚ\).

Examples

\(ℚ[i] = \left\lbrace x + i y \mid x, y ∈ ℚ \right\rbrace\)
\(ℚ[\sqrt[3]{2}] = \left\lbrace x + \sqrt[3]{2} y + \sqrt[3]{4} z \mid x, y, z ∈ ℚ \right\rbrace\)

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, we set \(\mathcal{O}_{K}= \mathcal{O}_{} ∩ K\).

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 and variants of Hilbert’s tenth problem

Purely Diophantine sets

Definition

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

\[({α}_1, \ldots,{α}_{n}) \in S \Leftrightarrow \exists {y}_1, \ldots,{y}_{m} \in R^m : p({α}_1, \ldots,{α}_{n}, {y}_1, \ldots,{y}_{m}) = 0\]

Examples of purely Diophantine sets

Let \(R\) be a commutative ring with unit. Then divisibility is purely Diophantine over \(R\).

Proof

We have \(a \mid b\) iff \(\exists y ∈ R: a y = b\). Choose \(p(a, b, y) = a y - b\) and obtain

\[a \mid b \quad ⇔ \quad ∃ y ∈ R: p(a, b, y) = 0.\]

Alternative characterization

Definition

The language of rings with unit is \(\mathcal{L}_{ring} = \left\lbrace +, -, \cdot, 0, 1 \right\rbrace\).

Remark

A set \(S \subseteq R^n\) is purely Diophantine over the ring structure \(\mathfrak{R} = ⟨R; +^{\mathfrak{R}}, -^{\mathfrak{R}}, \cdot^{\mathfrak{R}}; 0^{\mathfrak{R}}, 1^{\mathfrak{R}}⟩\) iff

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

holds for an atomic \(\mathcal{L}_{ring}\)-formula \(φ\).

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

\[({α}_1, \ldots,{α}_{n}) \in S \Leftrightarrow \exists {y}_1, \ldots,{y}_{m} \in R^m : p({α}_1, \ldots,{α}_{n}, {y}_1, \ldots,{y}_{m}) = 0\]

Examples of Diophantine Sets

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

Proof

Take

\[p(X) = \prod_{a ∈ S} (X - a).\]

Examples of Diophantine sets

The set of natural numbers \(ℕ\) is Diophantine over \(ℤ\).

Proof

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

\[x ∈ ℕ \quad \Leftrightarrow \quad \exists y_1, y_2, y_3, y_4 \in ℤ: x = y_1^2 + y_2^2 + y_3^2 + y_4^2.\]

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).\]

Alternative characterization

Definition

Let \(R\) be an at most countable commutative ring with unit. The \(R\)-language is \(\mathcal{L}_{R} = \mathcal{L}_{ring} ∪ \left\lbrace c_r \mid r ∈ R \right\rbrace\).

Remark

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

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

holds for an atomic \(\mathcal{L}_{R}\)-formula \(φ\).

Connection to Hilbert’s tenth problem

Given a commutative ring with unit \(R\) we consider \(4\) theories.

	\(\mathcal{L}_{ring}\)-theories	\(\mathcal{L}_{R}\)-theories
\(∃\)-quantified	purely Diophantine \(\mathtt{H10}^*(R)\)	Diophantine \(\mathtt{H10}(R)\)
\(∃\)- or \(∀\)-quantified	full theory \(\mathtt{Th}(R)\)	complete diagram \(D^c(R)\)

Which sets are Diophantine?

What we know 1

Theorem (Gödel 1931; Rosser 1936)

The full theory \(\mathtt{Th}(ℕ)\) is undecidable.

Corollary

The full theory \(\mathtt{Th}(ℤ)\) is undecidable.

Theorem (Robinson 1959)

The full first order theories \(\mathtt{Th}(K)\) and \(\mathtt{Th}(\mathcal{O}_{K})\) are undecidable for every number field \(K\).

What we know 2

Theorem

The full theory \(\mathtt{Th}(ℂ)\) is decidable. Thus, \(\mathtt{H10}^*(ℂ)\) is decidable.

Theorem (Rumely 1986; van den Dries 1988)

The theories \(\mathtt{H10}(\mathcal{O}_{})\) and \(D^c(\mathcal{O}_{})\) are decidable.

What we know 3

DPRM theorem (Matijasevič 1970)

A subset of \(ℤ\) is semi-decidable if and only if it is Diophantine over \(ℤ\).

Corollary

\(\mathtt{H10}(ℤ)\) is undecidable.

What we know 4

Theorem

\(\mathtt{H10}(\mathcal{O}_{K})\) is undecidable if

\(K\) is totally real (Denef 1980),
\(K\) has exactly one pair of non-real embeddings (Pheidas 1988; Shlapentokh 1989),
if \(K\) is a quadratic extension of a totally real number field (Denef and Lipshitz 1978), or
if \(K\) is a subfield of a field with one of the properties above (Shapiro and Shlapentokh 1989).

What we would like to know

Is \(\mathtt{H10}(\mathcal{O}_{K})\) and \(\mathtt{H10}(K)\) undecidable for all number fields \(K\)?
Especially: Is \(\mathtt{H10}(ℚ)\) decidable?

Computable rings and structural methods

Computable ring

Definition

A ring \(R \subseteq ω\) is computable if \(R\) is decidable and all ring operations are computable.
A ring \(R\) is computably presentable if \(R\) is isomorphic to a computable ring.

Examples of computably presentable rings

\(ℤ\) is computably presentable.
Using an integral basis, the ring of integers \(\mathcal{O}_{K}\) is computably presentable.
If \(R\) is a computable integral domain then the ring of polynomials \(R[X_1, X_2, …]\) is computably presentable.

Connection to Hilbert’s tenth problem

Corollary

Let \(K\) be a number field. Then Hilbert’s tenth problem over \(\mathcal{O}_{K}\) is semi-decidable.

Proof

Let \(p ∈ \mathcal{O}_{K}{} [{X}_1, \ldots,{X}_{n}]\) be a polynomial. Interpret \(p: \mathcal{O}_{K}^n → \mathcal{O}_{K}\), then \(p\) is computable.

Deciding whether \(p\) has roots in \(\mathcal{O}_{K}\) is equivalent to deciding

\[∃ {x}_1, \ldots,{x}_{n} : p({x}_1, \ldots,{x}_{n}) \doteq 0,\]

which is semi-decidable.

Unions and conjunctions

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 resp. polynomial identities can be found effectively.

Proof

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\]

Going up

Lemma

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

Proof

Assume otherwise and let \(p_K ∈ \mathcal{O}_{L}[X, 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 a root in \(\mathcal{O}_{K}\) if and only if

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

A Diophantine definition of rational integers is key

Theorem

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

Strong vertical method of Denef and Lipshitz

Theorem

Let \(L /K\) be an extension of number fields and \(n = [L : ℚ]\). If \(x, y ∈ \mathcal{O}_{L}\) and \(α ∈ \mathcal{O}_{K}\) satisfy

\(y\) is not a unit,
\(|σ_i(x)| ≤ |N_{L/ℚ}(y^c)|\) for all \(1 ≤ i ≤ n\),
\(|σ_i(α)| ≤ |N_{L/ℚ}(y^c)|\) for all \(1 ≤ i ≤ n\), and
\(x \equiv α \mathrel{\mathrm{mod}}\left(2 y^{2cn}\right)\) in \(\mathcal{O}_{L}\)

where \({σ}_1, \ldots,{σ}_{n}\) denote the embeddings of \(L\) into \(ℂ\) and \(c ∈ ℕ\) is a fixed, then

\[x = α ∈ \mathcal{O}_{K}.\]

A Diophantine definition of rational integers over the integers of a totally real number field

Two sequences

Definition

Let \(K\) be totally real 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\]

View this as an analogue to

\[\cos(m) + i \sin(m) = e^{im}\]

Pell’s equation

\[X^2 - (a^2 - 1) Y^2 = 1\]

Lemma

\((±\mathrm x_m(a), ±\mathrm y_m(a))_{m ∈ ℕ}\) are all solutions to Pell’s equation with parameter \(a\) in \(\mathcal{O}_{K}\).

View this as an analogue to

\[\cos(m)^2 - i^2 \sin(m)^2 = 1\]

Notation

Let \(K\) be number field of degree \(n = [K : ℚ]\) and let \({σ}_1, \ldots,{σ}_{n}\) denote all embeddings of \(K\) into \(ℂ\). For all \(α ∈ K\) we set

\[α_i := σ_i(α) \quad\text{for all } 1 ≤ i ≤ n\]

Main Lemma

Let \(K ≠ ℚ\) be a totally real number field of degree \(n = [K : ℚ]\) and let \(a ∈ \mathcal{O}_{K}\) satisfy

\[a_1 ≥ 2^{2n}, \quad |a_i| ≤ \frac{1}{8} \text{ for all } 2 ≤ i ≤ n.\]

Define \(S \subseteq \mathcal{O}_{K}\) by \(ξ ∈ S ⇔ ∃ x, y, w, z, u, v, s, t, b ∈ \mathcal{O}_{K}:\)

\[\begin{aligned} 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\\ v &≠ 0\\ z^2 & \mid v\\ \end{aligned}\]

\[\begin{aligned} b_1 &≥ 2^{2n}\\ |b_i| &≤ \frac{1}{2} \; \text{for } 2 ≤ i ≤ n\\ |u_i| &≥ \frac{1}{2} \; \text{for } 2 ≤ i ≤ n\\ |z_i| &≥ \frac{1}{2} \; \text{for } 2 ≤ i ≤ n\\ b &\equiv 1 \mathrel{\mathrm{mod}}(z)\\ \end{aligned}\]

\[\begin{aligned} b &\equiv a \mathrel{\mathrm{mod}}(u)\\ s &\equiv x \mathrel{\mathrm{mod}}(u)\\ t &\equiv ξ \mathrel{\mathrm{mod}}(z)\\ 2^{2n+1}& \prod_{i = 0}^{n - 1} (ξ + i)^n \prod_{j = 0}^{n - 1} (x + j)^n \;\big\vert\; z \end{aligned}\]

Then \(ℕ \subseteq S \subseteq ℤ\).

Main Lemma

Let \(K ≠ ℚ\) be a totally real number field of degree \(n = [K : ℚ]\) and let \(a ∈ \mathcal{O}_{K}\) satisfy

\[a_1 ≥ 2^{2n}, \quad |a_i| ≤ \frac{1}{8} \text{ for all } 2 ≤ i ≤ n.\]

Define \(S \subseteq \mathcal{O}_{K}\) by \(ξ ∈ S ⇔ ∃ x, y, w, z, u, v, s, t, b ∈ \mathcal{O}_{K}:\)

\[\begin{aligned} x = ±\mathrm x_k(a), & \; y = ±\mathrm y_k(a)\\ w = ±\mathrm x_h(a), & \; z = ±\mathrm y_h(a)\\ u = ±\mathrm x_m(a), & \; v = ±\mathrm y_m(a)\\ s = ±\mathrm x_j(b), & \; t = ±\mathrm y_k(b)\\ v &≠ 0\\ z^2 & \mid v\\ \end{aligned}\]

Then \(ℕ \subseteq S \subseteq ℤ\).

Diophantine definition of the rational integers

Theorem (Denef 1980)

Let \(K\) be a totally real number field. Then \(ℤ\) is Diophantine over \(\mathcal{O}_{K}\).

Use Minkowski’s theorem on convex bodies to find an \(a ∈ \mathcal{O}_{K}\) satisfying the estimates in the previous lemma.

Then \(ℕ \subseteq S \subseteq ℤ\) is Diophantine over \(\mathcal{O}_{K}\), and \(\left\lbrace -1, 1 \right\rbrace\) is Diophantine as well. Now

\[α ∈ ℤ \quad ⇔ \quad ∃ s, ξ: α = s ξ ∧ (s - 1)(s + 1) = 0 ∧ ξ ∈ S\]

References

Denef, J. 1980. “Diophantine Sets over Algebraic Integer Rings. II.” Trans. Amer. Math. Soc. 257 (1): 227–36. https://doi.org/10.2307/1998133.

Denef, J., and L. Lipshitz. 1978. “Diophantine Sets over Some Rings of Algebraic Integers.” J. London Math. Soc. (2) 18 (3): 385–91. https://doi.org/10.1112/jlms/s2-18.3.385.

Gödel, Kurt. 1931. “Über Formal Unentscheidbare Sätze Der Principia Mathematica Und Verwandter Systeme I.” Monatsh. Math. Phys. 38 (1): 173–98. https://doi.org/10.1007/BF01700692.

Hilbert, David. 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–79.

Matijasevič, Ju. V. 1970. “The Diophantineness of Enumerable Sets.” Doklady Akademii Nauk SSSR 191: 279–82.

Pheidas, Thanases. 1988. “Hilbert’s Tenth Problem for a Class of Rings of Algebraic Integers.” Proc. Amer. Math. Soc. 104 (2): 611–20. https://doi.org/10.2307/2047021.

Robinson, Julia. 1959. “The Undecidability of Algebraic Rings and Fields.” Proc. Amer. Math. Soc. 10: 950–57. https://doi.org/10.2307/2033628.

Rosser, Barkley. 1936. “Extensions of Some Theorems of Gödel and Church.” Journal of Symbolic Logic 1 (3): 87–91. https://doi.org/10.2307/2269028.

Rumely, Robert S. 1986. “Arithmetic over the Ring of All Algebraic Integers.” J. Reine Angew. Math. 368: 127–33. https://doi.org/10.1515/crll.1986.368.127.

Shapiro, Harold N., and Alexandra Shlapentokh. 1989. “Diophantine Relationships Between Algebraic Number Fields.” Comm. Pure Appl. Math. 42 (8): 1113–22. https://doi.org/10.1002/cpa.3160420805.

Shlapentokh, Alexandra. 1989. “Extension of Hilbert’s Tenth Problem to Some Algebraic Number Fields.” Comm. Pure Appl. Math. 42 (7): 939–62. https://doi.org/10.1002/cpa.3160420703.

van den Dries, Lou. 1988. “Elimination Theory for the Ring of Algebraic Integers.” J. Reine Angew. Math. 388: 189–205. https://doi.org/10.1515/crll.1988.388.189.