Hilbert’s tenth problem

over rings of algebraic integers

Tim B. Herbstrith

15 June 2018

Hilbert’s tenth problem, Turing machines, and decidability

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

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)$ ?

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$

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 $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)$

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.

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$

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}.$

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}$

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.

Hilbert’s tenth problem over rings of algebraic integers Tim B. Herbstrith 15 June 2018