Estimates for a

One uses strong approximation theorem to find an a ∈ \mathcal{O}_{K} satisfying the estimates

of the main lemma.

Strong vertical method

Theorem (Denef and Lipshitz 1978)

Let L/K be an extension of number fields and n = [L : ℚ]. If x, y ∈ \mathcal{O}_{L}, y ≠ 0, and α ∈ \mathcal{O}_{K} satisfy \begin{aligned} & |σ_i(x)| < \frac{1}{2} |N_{L/ℚ}(y)|^{\frac{1}{n}} \text{ for all } 1 ≤ i ≤ n, \\ & |σ_i(α)| < \frac{1}{2} |N_{L/ℚ}(y)|^{\frac{1}{n}} \text{ for all } 1 ≤ i ≤ n, \text{ and}\\ & x \equiv α \mod (y) \text{ in } \mathcal{O}_{L}, \end{aligned} where {σ}_1, \ldots, {σ}_{n} denote the embeddings of L into the complex pane ℂ. Then x = α ∈ \mathcal{O}_{K}.

Approximations of real embeddings are Diophantine

Lemma (Denef 1980)

Let K be a number field and σ: K → ℝ be a real embedding. Then the relation σ(α) ≥ 0 is Diophantine over \mathcal{O}_{K}.

Absolute values

An absolute value on a field K is a function |\cdot| : K → ℝ, x ↦ |x| with the properties

• |x| ≥ 0 for all x ∈ K and |x| = 0 if and only if x = 0;
• |xy| = |x| |y| for all x, y ∈ K; and
• |x + y| ≤ |x| + |y| for all x, y ∈ K.

If additionally the stronger condition

• |x + y| ≤ \max(|x|, |y|)

holds for all x, y ∈ K then |\cdot| is called a .

Absolute values of a number field

Let K be a number field. Then K has the following absolute values

• a trivial absolute value defined by |0|_1 := 0 and |x|_1 := 1 for all x ∈ K \setminus \left\lbrace 0 \right\rbrace;

• one absolute value for each embedding σ: K → ℂ by setting |x| := |σ(a)|_ℂ, where |\cdot|_{ℂ} denotes the complex modulus; and

• one for each non-zero prime ideal \mathfrak{p} defined by |x|_{\mathfrak{p}} := \left(\frac{1}{ℕ\mathfrak{p}}\right)^{\mathop{\mathrm{\mathrm{ord}}}_{\mathfrak{p}}(x\mathcal{O}_{K})}, where ℕ\mathfrak{p} := [\mathcal{O}_{K}: \mathfrak{p}].

Strong approximation theorem

Let K be a number field, let \mathcal{M}_K be the set of all the absolute values of K, let \mathcal{F}_K = \left\lbrace |\cdot|_1,… ,|\cdot|_ℓ \right\rbrace ⊂ \mathcal{M}_K be a non-empty finite subset, and let a_1,…,a_{ℓ - 1} ∈ K. Then for any ε > 0 there exists an x ∈ K such that the following conditions are satisfied.

• For 1 ≤ i ≤ ℓ - 1 we have that |x − a_i|_i <ε.

• For any absolute value |\cdot| not contained in \mathcal{F}_K we have that |x| ≤ 1.

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 ∈ Q \quad ⇔ \quad ∃ y ∈ ω: R(x, y)

What we know 1

Theorem (Gödel 1931; Rosser 1936)

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

What we know 2

Theorem (Tarski 1931)

The full theories \mathtt{Th}(\mathfrak{C}) of ℂ and \mathtt{Th}(\mathfrak{R}) of ℝ are decidable. Thus, \mathtt{H10}^*(\mathfrak{C}) and \mathtt{H10}^*(\mathfrak{R}) are decidable.

What we know 3

DPRM theorem (Matijasevič 1970)

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

What we know 4

Theorem

\mathtt{H10}(\mathfrak{O}_K) is undecidable if

• K is totally real (Denef 1980),
• K has exactly one pair of non-real embeddings and at least one real embedding (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}(\mathfrak{O}_K) undecidable for all number fields K?
• Especially: Is Hilbert’s tenth problem \mathtt{H10}(\mathfrak{Q}) over ℚ decidable?