Hilbert’s tenth problem

over rings of algebraic integers

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

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{2}] = \left\lbrace x + \sqrt{2} y + \sqrt{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

1. $$y$$ is not a unit,
2. $$|σ_i(x)| ≤ |N_{L/ℚ}(y^c)|$$ for all $$1 ≤ i ≤ n$$,
3. $$|σ_i(α)| ≤ |N_{L/ℚ}(y^c)|$$ for all $$1 ≤ i ≤ n$$, and
4. $$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}

\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 ℤ$$.

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$