PROBLEMS RELATED TO “EXTENSIONS OF HILBERT’S TENTH PROBLEM”

MODERATED BY B. POONEN AND T. SCANLON, NOTES BY J. DEMEYER

Question 1 (D’Aquino). Fermat’s little theorem states that

x^{p} ≡ x mod p

Proof 1: 𝔽_{p}^{∗} is cyclic using the fact that

#{x | P (x) = 0} ≤ deg(P)

Proof 2: List R = {1, 2, …, p − 1}. Show that for a ∈ R, multiplication by a is a permuation. Then

∏_{i=1}^{p−1} i ≡ ∏_{i=1}^{p−1}(ai) mod p

From this follows that

(p − 1)! ≡ a^{p−1}(p − 1)! mod p

Give a “simple” definition of n! mod p (this is OK for exponentiation). Proof 3: Use

(x + y)^{p} = x^{p} + y^{p} mod p

Find other proofs.

Question 2 (D’Aquino). Is DPRM a theorem of IΔ_{0}? This is Peano arithmetic with the induction axiom for every first order formula φ(x) with bounded quantifiers

I(φ) : [φ(0) ∧ (∀x)(φ(x) → φ(x + 1))] → (∀x)(φ(x))

A positive answer would imply that NP is equal to co-NP. Given a Σ_{1} formula ψ(x⃗), does there exist a polynomial P (x⃗, y⃗) such that

IΔ_{0} ⊢ (∀x⃗)(ψ(x⃗) ↔ (∃y⃗)(P (x⃗, y⃗) = 0))

Consider the language L = {+, ·, 0, 1, #, ≤}, where

#(x, y) := x^{⌊log(y)⌋}

Question 3 (Demeyer). Consider the ring 𝔽_{q}[W, Z]. Does there exist a Diophantine predicate α(f, g⃗) with f ∈ 𝔽_{q}[W, Z] and g⃗ ∈ 𝔽_{q}[Z]^{n} such that

(1) For all f ∈ 𝔽_{q}[W, Z], there exists a g⃗ ∈ 𝔽_{q}[Z]^{n} such that α(f, g⃗) holds.

(2) For all g⃗ ∈ 𝔽_{q}[Z]^{n}, the set {f ∈ 𝔽_{q}[W, Z] | α(f, g⃗) holds} is finite. This will imply that r.e. = Diophantine for 𝔽_{q}[W, Z]. It is possible to give such a Diophantine predicate if “α(⋯) holds” is replaced with

“α(⋯) does not hold”.

Question 4 (Demeyer). Fix a prime p. Is there a Diophantine model of 𝔽_{q}[Z] over 𝔽_{p}[Z], when q is a power of p, uniformly in q?

In other words, do there exist polynomials f(t, x⃗, x⃗′), g(t, y⃗, y⃗′) and h(t, z⃗, z⃗′) such that:

• For every power q of p, S_{q} := {x⃗ | f(Z^{q}, x⃗, x⃗′) = 0} is in bijection with 𝔽_{q}[Z].

• {y⃗ | g(Z^{q}, y⃗, y⃗′) = 0} ⊆ S_{q}^{3} corresponds to the graph of addition on 𝔽_{q}[Z].

• {z⃗ | h(Z^{q}, z⃗, z⃗′) = 0} ⊆ S_{q}^{3} corresponds to the graph of multiplication on 𝔽_{q}[Z]. Or with “Z^{q}” replaced by some other reasonable function {powers of p} → 𝔽_{p}[Z]. This might imply that r.e. = Diophantine for 𝔽_{p}[Z].

Question 5 (Pheidas). An additive polynomial in 𝔽_{p}[Z] is a polynomial of the form

F (Z) = α_{0}Z + α_{1}Z^{p} + α_{2}Z^{p^{2}} + ⋯ + α_{n}Z^{p^{n}} (α_{i} ∈ 𝔽_{p})

These are the polynomials that satisfy f(A + B) = f(A) + f(B) for all A, B ∈ 𝔽_{p}[Z]. Can we Diophantinely define the additive polynomials?

(Demeyer) The following suggestion by Pheidas does not work:

(∃A, B, C, L, M, N ∈ 𝔽_{p}[Z])(∃α, β, γ, λ, μ, ν ∈ 𝔽_{p})
F = (A^{p} − A) + αZ
∧ F^{2} = (B^{p} − B) + βZ + (C^{p} − C)Z + γZ^{2}
∧ F^{3} = (L^{p} − L) + λZ + (M^{p} − M)Z + μZ^{2} + (N^{p} − N)Z^{2} + νZ^{3}
⋮

Continue this up to some power F^{n}. All additive polynomials satisfy this predicate, but also the following non-additive polynomial satisfies, no matter how many equations you add:

∑_{i=0}^{p−1} (Z^{2p} − Z^{p+1})^{p^{i}}

Fact 6 (Cornelissen). Here is an example of a non-commutative undecidable theory. Let L be any field of characteristic p > 0. Let A_{L} denote the ring of additive polynomials with coefficients from L (a ring for addition and composition). Then f ∘ Z^{p} = Z^{p} ∘ f is a Diophantine definition of A_{𝔽_{p}} ≅ 𝔽_{p}[Z] in A_{L}.

The same works in the quotient skew field Q_{L} of A_{L}. Hence the Diophantine theory of A_{L} and Q_{L} in a ring language augmented by a symbol for Z is undecidable (since the theories of 𝔽_{q}[Z] and 𝔽_{q}(Z) are by Denef and Pheidas). If one can therefore give a Diophantine definition of A_{L} or Q_{L} in L[Z] or L(Z), the theory of the latter would be undecidable.

Question 5 of Pheidas tries to define the set A_{L}. For cognescenti: this works more generally if “f ∘ Z^{p} = Z^{p} ∘ f” is replaced by f ∘ ρ_{T} = ρ_{T} ∘ f for ρ a Drinfeld 𝔽_{q}[T]-module over L.

Question 7 (Davis). Let ℍ be the quaternions over ℚ, and

O = ℤ + iℤ + jℤ + kℤ

(1) Is there an algorithm to decide whether a noncommutative polynomial equation f(x_{1}, …, x_{n}) = 0 with coefficients in ℚ has a solution in ℍ?

(2) Is there an algorithm to decide whether a noncommutative polynomial equation f(x_{1}, …, x_{n}) = 0 with coefficients in ℚ has a solution in O?

(3) Is there an algorithm to decide whether a noncommutative polynomial equation f(x_{1}, …, x_{n}) = 0 with coefficients in ℍ has a solution in ℍ?

(4) Is there an algorithm to decide whether a noncommutative polynomial equation f(x_{1}, …, x_{n}) = 0 with coefficients in ℍ has a solution in O?

Is ℤ existentially definable in O? This probably works:

x ∈ ℤ ⟺ (∃I, J, K)(I^{2} = −1 ∧ J^{2} = −1 ∧ IJ = −JI ∧ xI = Ix ∧ xJ = Jx)

Very likely done by D. Tunc. This solves the problems 2 and 4.

In an analogous way, ℚ should be Diophantine in ℍ. So, 1 and 3 are equivalent with Hilbert’s Tenth Problem over ℚ.

Same questions for the matrix rings M_{n}(ℤ) and M_{n}(ℚ).

Question 8 (Pheidas). Is the following problem decidable:

Given P (x⃗) ∈ ℤ[x⃗], do there exist n_{1}, …, n_{m} ∈ ℕ such that P (2^{n_{1}}, …, 2^{n_{m}}) = 0?

The answer is YES: this is related to the Mordell–Lang conjecture for tori.

Question 9 (Pheidas). Can we redo the proof of Hilbert’s Tenth Problem over ℤ, using elliptic curves instead of Pell equations?

Hopefully, this would lead to a lower number of variables and/or lower degree.

Can this give a finite-fold Diophantine definition of all r.e. sets?

Question 10 (Davis). Find a native proof of DPRM in ℤ, instead of referring to ℕ. Prove DPRM for some class of rings abstractly, with no reference to ℕ.

Question 11 (Davis). A subset S ⊆ ℕ is called simple if and only if:

(1) S is r.e.

(2) ℕ \ S is infinite.

(3) If T ⊆ ℕ \ S is r.e., then T is finite.

Take a simple set S ⊆ O_{K} and an embedding f : O_{K} ↪ R, for some ring R. Let

S = {x ∈ O_{K} | (∃y⃗ ∈ O_{K}^{n})(P (x, y⃗) = 0)}

and consider

S′ = {x ∈ O_{K} | (∃y⃗ ∈ R^{n})(P (x, y⃗) = 0)}

Clearly, f(S) ⊆ S′. Either S′ is simple (hence not recursive) or its complement is finite. In particular, if P (x, y⃗) ∈ ℤ[x, y⃗] is such that

{x ∈ ℤ | (∃y⃗ ∈ ℤ^{n})(P (x, y⃗) = 0)}

is simple and

ℤ \ {x ∈ ℤ | (∃y⃗ ∈ ℚ^{n})(P (x, y⃗) = 0)}

is infinite, then Hilbert’s Tenth Problem for ℚ has a negative answer.

Reference: Davis, Putnam, “Diophantine sets over polynomial rings”.

Question 12 (Cornelissen). If ℤ admits a Diophantine interpretation in ℚ (that is, using an equivalence relation), does it follow that Mazur’s conjecture is wrong?

See Cornelissen–Zahidi, Contemp. Math. 270 253–260.

Question 13 (Cornelissen). Solve in integers A, B, X, Y:

(A^{2} + B^{2})(A^{2} + 11B^{2}) = 9 · 25 · (X^{2} − 5Y^{2})^{2}

This is related to defining the integers in the rational numbers by a Σ_{3}^{+}-formula, see

Cornelissen–Zahidi, ArXiv:math.NT/0412473.

Question 14 (Cornelissen). Jeroen Demeyer has observed that the existence of a polynomial bijection ℕ^{2} → ℕ implies that any first order formula over ℕ in positive prenex form is equivalent to one in which every block of consecutive universal quantifiers is replaced by just one (and the number of existential quantifiers goes up). Such a polynomial bijection can be found in Davis, Math. Monthly 80, 236–237.

Does something similar work for ℚ, in other words, can we find a Diophantine injection ℚ^{2} ↪ ℚ? There are some observations related to this in C.R.A.S. Paris 328, 3–8 (1999); for example, this would follow from the generalized abc-conjecture.

Question 15 (Rojas). What is the smallest n such that Hilbert’s Tenth Problem over ℤ restricted to one polynomial in n variables is undecidable?

Minimal n is known to be 2 ≤ n ≤ 22 by Matijasevič, and probably 2 ≤ n ≤ 11 by some Chinese. There is some evidence that n = 3.

Question 16 (Rojas). Consider sequences in ℤ[x] of the form

1, x, g_{1}, g_{2}, …

where each g_{i} is a sum, difference or product of 2 earlier terms in the sequence. Let

τ(f) := min{n | there exists such a sequence with g_{n} = f}

Conjecture: there exists a constant c such that the number of integer zeros of f is at most (1 + τ(f))^{c}, where f is not identically zero.

Question 17 (Rojas). Let c_{j} ∈ ℤ and consider polynomials of the form

P (x_{1}, …, x_{n}) = ∏_{j=1}^{n+1} c_{j}xa⃗_{j}

where a⃗_{1}, …, a⃗_{n+1} ∈ ℕ^{n} are affinely independent.

Can we decide in polynomial time (for fixed p) whether there exists a x⃗ ∈ ℚ_{p}^{n} such that P (x⃗) = 0?

Answer: NO, because the 0/1 knapsack problem can be encoded as a subproblem of this (Poonen). Over ℝ this is in NP, and probably in P (modulo some technicalities).

Can we decide whether there exists a x⃗ ∈ ℚ^{n} such that P (x⃗) = 0?

This includes the unsolved problem of deciding whether a genus 1 curve of the form ax^{3} + by^{3} = 1 has a rational point, so it is probably very hard.

Question 18 (Rojas). Is there a computable bound (in function of f) on the size of the largest integer solution to f(x, y) = 0, when there are finitely many solutions?

This is already done for genus 1 curves.

There exists an algorithm to decide finiteness of the set of solutions. For rational points, there are papers by Minhyong Kim from Arizona: “Relating decision and search algorithms for rational points on curves of higher genus”,

Arch. Math. Logic 42 (2003), no. 6, 563–568

PROBLEMS RELATED TO  “EXTENSIONS OF HILBERT’S TENTH PROBLEM”  5

“On relative computability for curves”, ArXiv:math.NT/0502224 Question 19 (Jarden). Is there an algorithm to decide whether f(x, y) = 0 has infinitely many ℚ-rational solutions?

This seems to be very hard for genus 1 curves. It has been done in other cases.

Possible if � is finite for all elliptic curves over ℚ. Question 20 (Shlapentokh). Let E be an elliptic curve over ℚ of rank 2. Does there exist an existentially definable rank 1 subgroup? Question 21 (Shlapentokh). Let E be an elliptic curve over ℚ of rank 2. Can we find a subset S of (infinitely many) primes such that the subgroup generated by E(ℤ[S^{−1}]) has rank one?

If S is finite, the Siegel–Mahler theorem states that E(ℤ[S^{−1}]) is finite. Suppose S is infinite, but of density 0. Is E(ℤ[S^{−1}]) still “small”?

Question 22 (Zahidi). Look at the Denef curve

E : f(t)Y^{2} = f(X)

where f is a cubic. If we choose the curve in a good way, then E(k(t)) has rank 1.

Define

E_{u} : f(u)Y^{2} = f(X)

Try to give conditions on u ∈ k(t) such that E_{u}(k(t)) also has rank 1. Question 23 (Pheidas). Consider the elliptic curve

E : Y^{2} = X^{3} + aX + b

The following statement is Diophantine: “End(E)/(2 End(E)) has more than 2 elements”. Because End(E) is a free finitely generated ℤ-module, this is equivalent with “End(E) ≠ ℤ”.

So, we can existentially define the following set in ℂ(Z):

{j ∈ ℂ | j is the j-invariant of a CM elliptic curve}

Can we do anything with this set? Question 24 (Pheidas). If x ∈ ℂ(Z), then

ord_{Z=0} (\frac{1 + Zx^{2}}{1 − Zx^{2}} ) = ord_{Z=∞} (\frac{1 + Zx^{2}}{1 − Zx^{2}} ) = 0

Can every f ∈ ℂ(Z) with ord_{Z=0}(f) = ord_{Z=∞}(f) even be written as (obviously, the number 1000 can be changed to any other integer)

f = u^{2} ∏_{i=1}^{1000} \frac{1 + Zx_{i}^{2}}{1 − Zx_{i}^{2}}

Weaker version: is this true at least for f ∈ ℚ(Z), with u, x_{i} ∈ ℂ(Z)? This would imply that the existential theory of ℂ(Z) is undecidable.

Question 25 (Pheidas). Is {f ∈ ℂ(Z) | ord_{Z=0}(f) ≥ 0} (existentially) definable in ℂ(Z), where there is a symbol for Z in the language?

Question 26 (Moret-Bailly). Is there a nontrivial valuation ring

R ⊂ Frac\frac{ℝ[x, y]}{(x^{2} + y^{2} + 1)}

which is definable?

Same question for “semi-local ring” (finite intersection of valuation rings) instead of “valuation ring”? This is equivalent with the problem for valuation rings.

Question 27 (Shlapentokh). Can one find an algebraically closed field K and a nontrivial valuation ring R ⊂ K(Z) (or a finite extension), which is definable in K(Z)?

Question 28 (Shlapentokh). Is there an algebraic extension K of ℚ and a nontrivial valuation ring R ⊂ K, such that the residue field of R is algebraically closed and R is definable over K?

Answer: YES. Inside ℚ_{p}^{alg} = \overline{ℚ} ∩ ℚ_{p} ⊆ \overline{ℚ_{p}}, the ring ℤ_{p}^{alg} is definable.

Fact 29 (Pheidas). ℂ[[Z]] is definable in ℂ((Z)):

x ∈ ℂ[[Z]] ⟺ (∃y)(1 + Zx^{2} = y^{2})

Proven using Hensel’s lemma.

Question 30 (Shlapentokh). Let K be a number field and O_{K} its ring of integers. Fix an embedding K ↪ ℂ, with K ⊈ ℝ. Is {α ∈ O_{K} | |α| ≤ 1} Diophantine in O_{K}?

If this is true for all K, then Hilbert’s Tenth Problem is undecidable for all O_{K}.

Question 31 (Cornelissen). Let K be a number field and O_{K} its ring of integers. A set A ⊆ O_{K} is said to be division-ample if

• It is Diophantine over O_{K}.

• Any x ∈ O_{K} divides some a ∈ A.

• There exists a positive integer l such that for any a ∈ A, there exists ã ∈ ℤ with ã|a and N(a) ≤ |ã|^{l}. Observe that if A ⊆ ℤ, then one can dispose of the last condition by choosing ã = a

and l = [K : ℚ].

Question: give an example of such A where for any finite S ⊆ O_{K}, A is not a subset of O_{K}^{∗} · (ℤ ∪ S).

Cornelissen–Pheidas–Zahidi have shown that HTP(O_{K}) has a negative answer if such A exists and there exists an elliptic curve of rank one over K.

Question 32 (Poonen). Is is true that for all number fields K, there exists a variety X (scheme of finite type) over ℤ such that

(1) X(ℤ) is infinite.

(2) X(O_{K}) = X(ℤ).

Question 33 (Videla). Let K ⊆ ℚ^{tot. real} ⊆ \overline{ℚ}. Define

A_{K} := {s ∈ ℝ_{>0} | There exist infinitely many α ∈ O_{K} such that α and its conjugates are all in [0, s]}

Question of Julia Robinson: Is the infimum of A_{K} an element of A_{K}? If so, the first order theory of O_{K} is undecidable.

For K = ℚ^{tot. real}, inf(A_{K}) = 4 ∈ A_{K}.

Question 34 (Zahidi). Let ℝ^{alg} := \overline{ℚ} ∩ ℝ. It is known that ℝ^{alg} ≡ ℝ (elementary equivalence), but that ℝ^{alg}(t) ≢ ℝ(t). On the other hand, the existential theories of ℝ^{alg}(t) and ℝ(t) are the same. What is the minimal quantifier complexity for which ℝ^{alg}(t) and ℝ(t) have different theories?

Another question is the minimal number of variables one needs.

Question 35 (Pheidas). Let X be a variety over ℚ. Call X hyperbolic iff there is no nonconstant holomorphic map ℂ → X(ℂ). Is there an algorithm which can decide whether a variety X/ℚ over hyperbolic?

Question 36 (Jarden). Given f_{1}, …, f_{n} ∈ ℂ[x_{1}, …, x_{m}] which are homogeneous of degree d. Assume that the only common zero of the f_{i} is (0, …, 0). Prove that

V (f_{1}(x⃗) = b_{1}, …, f_{n}(x⃗) = b_{n})

is finite, for all b_{1}, …, b_{n} ∈ ℂ.

Solution: If it were infinite, then the variety in ℙ^{m} defined by the homogenizations of the equations would be positive-dimensional, and then it would have to intersect the hyperplane at infinity, which would mean that the f_{i} have a common zero.