CHARACTERIZING INTEGERS AMONG RATIONAL NUMBERS WITH A UNIVERSAL-EXISTENTIAL FORMULA

BJORN POONEN

Abstract. We prove that ℤ in definable in ℚ by a formula with 2 universal quantifiers followed by 7 existential quantifiers. It follows that there is no algorithm for deciding, given an algebraic family of ℚ-morphisms, whether there exists one that is surjective on rational points. We also give a formula, again with universal quantifiers followed by existential quantifiers, that in any number field defines the ring of integers.

1. Introduction

1.1. Background. D. Hilbert, in the 10th of his famous list of 23 problems, asked for an algorithm for deciding the solvability of any multivariable polynomial equation in integers. Thanks to the work of M. Davis, H. Putnam, J. Robinson [DPR61], and Y. Matijasevič [Mat70], we know that no such algorithm exists. In other words, the positive existential theory of the integer ring ℤ is undecidable.

It is not known whether there exists an algorithm for the analogous problem with ℤ replaced by the field ℚ of rational numbers. But Robinson showed that the full first-order theory of ℚ is undecidable: she reduced the problem to the corresponding known result for ℤ by showing that ℤ could be defined in ℚ by a first-order formula [Rob49, Theorem 3.1]. If there were a positive existential formula defining ℤ in ℚ, then an easy reduction from ℚ to ℤ would show that Hilbert’s 10th problem over ℚ would have a negative answer.

G. Cornelissen and K. Zahidi [CZ06] ask:

(1) What is the smallest part of the first-order theory of ℚ that can be proved undecidable?

(2) How complicated must a formula defining ℤ in ℚ be? To make these questions precise, they define the positive arithmetical hierarchy as follows: Σ_{0}^{+} = Π_{0}^{+} is the set of atomic formulas (which, in the language of rings, are polynomial equations), and for n ∈ ℤ_{≥0}, inductively define Σ_{n+1}^{+} as the set of formulas consisting of any number of existential quantifiers followed by a formula in Π_{n}^{+}, and Π_{n+1}^{+} as the set of formulas consisting of any number of universal quantifiers followed by a formula in Σ_{n}^{+}. Thus, for instance, positive existential formulas are equivalent to those in Σ_{1}^{+}, and the formula

(∀x_{1}∀x_{2}∃y∀z_{1}∀z_{2}) x_{1}^{2}w + x_{2}^{3}y − x_{2}z_{1} = x_{1}z_{2} + w^{7}

is a Π_{3}^{+}-formula with one free variable, w.

Date: June 3, 2008.

2000 Mathematics Subject Classification. Primary 11U05; Secondary 11R52.

Key words and phrases. Hilbert’s Tenth Problem, diophantine set, quaternion algebra.

This research was supported by NSF grant DMS-0301280. This article is to appear in Amer. J. Math.

As remarked in [CZ06], Robinson’s definition of ℤ in ℚ uses a Π_{4}^{+}-formula, and it follows that the Σ_{5}^{+}-theory of ℚ is undecidable. Theorems 4.2 and 5.3 of [CZ06] show that a conjecture about elliptic curves implies that ℤ is definable in ℚ by a Π_{2}^{+}-formula, and that the Π_{2}^{+}-theory of ℚ is undecidable, even if one allows only formulas with a single universal quantifier.

1.2. Our results. We prove unconditionally that ℤ is definable in ℚ by a Π_{2}^{+}-formula. Combining this with the negative answer to Hilbert’s tenth problem over ℤ shows that the Σ_{3}^{+}-theory of ℚ is undecidable. Our proof uses not elliptic curves, but quaternion algebras.

These results may be restated in geometric terms. By ℚ-variety we mean a separated scheme of finite type over ℚ. Given a ℚ-morphism π: V → T and t ∈ T (ℚ), let V_{t} = π^{−1}(t) be the fiber. Then

(a) There exists a diagram of ℚ-varieties

\xymatrix{V \ar[rr] \ar[dr] &  & W \ar[dl] \\  & 𝔸^{1}}

such that ℤ equals the set of t ∈ ℚ = 𝔸^{1}(ℚ) such that V_{t}(ℚ) → W_{t}(ℚ) is surjective. (In fact, we may take W = 𝔸^{3}, and take its map to 𝔸^{1} to be a coordinate projection.)

(b) There is no algorithm that takes as input a diagram of ℚ-varieties

\xymatrix{V \ar[rr] \ar[dr] &  & W \ar[dl] \\  & T}

and decides whether or not there exists t ∈ T (ℚ) such that V_{t}(ℚ) → W_{t}(ℚ) is surjective.

In the final section of the paper, we generalize to number fields: we find a Π_{2}^{+}-formula that in every number field k defines its ring of integers O_{k}.

2. Quaternion algebras

We use a quaternion algebra argument similar to that in the proof of [Eis05, Theorem 3.1]. Let P = {2, 3, 5, …} be the set of prime numbers. Given a, b ∈ ℚ^{×}, let H_{a,b} be the quaternion algebra over ℚ generated by i and j satisfying i^{2} = a, j^{2} = b, and ij = −ji. Let Δ_{a,b} be the set of p ∈ P that ramify in H_{a,b}. Let S_{a,b} be the set of reduced traces of elements of H_{a,b} of reduced norm 1. For p ∈ P, define S_{a,b}(ℚ_{p}) similarly for H_{a,b} ⊗ ℚ_{p}. For any prime power q, let U_{q} be the set of s ∈ 𝔽_{q} such that x^{2} − sx + 1 is irreducible in 𝔽_{q}[x]. Let ℤ_{p} be the ring of p-adic integers, and let red_{p}: ℤ_{p} → 𝔽_{p} be the reduction map.

Lemma 2.1.

(i) If p ∉ Δ_{a,b}, then S_{a,b}(ℚ_{p}) = ℚ_{p}.

(ii) If p ∈ Δ_{a,b}, then red_{p}^{−1}(U_{p}) ⊆ S_{a,b}(ℚ_{p}) ⊆ ℤ_{p}.

Proof. We have s ∈ S_{a,b}(ℚ_{p}) if and only if x^{2}−sx+1 is the reduced characteristic polynomial of an element of H_{a,b} ⊗ ℚ_{p}.

(i) If p ∉ Δ_{a,b}, then H_{a,b} ⊗ ℚ_{p} ≃ M_{2}(ℚ_{p}), and any monic quadratic polynomial is a characteristic polynomial.

(ii) Now suppose that p ∈ Δ_{a,b}. Then H_{a,b} ⊗ ℚ_{p} is the ramified quaternion algebra over ℚ_{p}, and x^{2} − sx + 1 is a reduced characteristic polynomial if and only if it is a power of a monic irreducible polynomial in ℚ_{p}[x]. If red_{p}(s) ∈ U_{p}, then x^{2} − sx + 1 is irreducible over ℚ_{p}. If s ∈ ℚ_{p} − ℤ_{p}, then x^{2} − sx + 1 is a product of two distinct factors, by the theory of Newton polygons. □

Lemma 2.2. If a, b ∈ ℚ^{×} and either a > 0 or b > 0, then S_{a,b} = ℚ ∩ ⋂_{p} S_{a,b}(ℚ_{p}).

Proof. This is a special case of the Hasse principle for rational numbers represented by quadratic forms: see [Ser73, p. 43, Corollary 1], for example. □

Lemma 2.3. For any prime power q, the set U_{q} is nonempty. If q > 11 then U_{q} + U_{q} = 𝔽_{q}.

Proof. We have U_{q} = Tr ({β ∈ 𝔽_{q^{2}} − 𝔽_{q} : N(β) = 1}), where Tr and N are the trace and norm for 𝔽_{q^{2}}/𝔽_{q}. Since 𝔽_{q^{2}} contains q + 1 norm-1 elements, U_{q} ≠ ∅. Also, −U_{q} = U_{q}, so 0 ∈ U_{q} + U_{q}. Given a ∈ 𝔽_{q}^{×} with q > 11, we hope to prove a ∈ U_{q} + U_{q}.

Suppose that q is odd. Write 𝔽_{q^{2}} = 𝔽_{q}(\sqrt{c}) with c ∈ 𝔽_{q}^{×} − 𝔽_{q}^{×2}. Then U_{q} = \{2x : x, y ∈ 𝔽_{q} and x^{2} − cy^{2} = 1}. So a ∈ U_{q} + U_{q} if and only if there exist x_{1}, y_{1}, x_{2}, y_{2} ∈ 𝔽_{q} satisfying

x_{1}^{2} − cy_{1}^{2} = 1, x_{2}^{2} − cy_{2}^{2} = 1, 2x_{1} + 2x_{2} = a, y_{1}, y_{2} ≠ 0.

These conditions define a smooth curve X in 𝔸^{4}. Eliminating x_{2} shows that the projective closure \overline{X} of X is a geometrically integral intersection of two quadrics in ℙ^{3}, with function field 𝔽_{q}(x_{1})(\sqrt{c(1 − x_{1}^{2})}, \sqrt{c(1 − (a/2 − x_{1})^{2})}). So X is of genus 1 with at most 12 punctures (the intersections of \overline{X} with three hyperplanes: y_{1} = 0, y_{2} = 0, and the one at infinity).

If instead q is even, 𝔽_{q^{2}} = 𝔽_{q}(γ) where γ^{2} + γ + c = 0 for some c ∈ 𝔽_{q}, and we seek an 𝔽_{q}-point on the curve X defined by

x_{1}^{2} + x_{1}y_{1} + cy_{1}^{2} = 1, x_{2}^{2} + x_{2}y_{2} + cy_{2}^{2} = 1, y_{1} + y_{2} = a, y_{1}, y_{2} ≠ 0.

The geometric properties of X are the same as in the odd q case.

For any q ≥ 23, the Hasse bound yields

#X(𝔽_{q}) ≥ (q + 1 − 2\sqrt{q}) − 12 > 0,

so a ∈ U_{q} + U_{q}. If 11 < q < 23 we check U_{q} + U_{q} = 𝔽_{q} by exhaustion. □

Remark 2.4. A further calculation shows that the only prime power q less than or equal to 11 for which U_{q} + U_{q} = 𝔽_{q} holds is 9.

Let N = 2·3·5·7·11 = 2310. Let T_{a,b} be the set of rational numbers of the form s+s′ +n where s, s′ ∈ S_{a,b} and n ∈ {0, 1, 2, …, N − 1}.

Lemma 2.5. If a, b ∈ ℚ^{×} and either a > 0 or b > 0, then T_{a,b} = ⋂_{p∈Δ_{a,b}} ℤ_{(p)}.

Proof. Let T′_{a,b} be the right-hand side. Lemmas 2.1 and 2.2 imply S_{a,b} ⊆ T′_{a,b}, so T_{a,b} ⊆ T′_{a,b}.

Now suppose t ∈ T′_{a,b}. Choose n ∈ {0, 1, 2, …, N − 1} such that red_{p}(t − n) ∈ U_{p} + U_{p} for all p ≤ 11. For each p > 11, Lemma 2.3 yields red_{p}(t − n) ∈ U_{p} + U_{p}. So we may choose s ∈ ℤ such that red_{p}(s), red_{p}(t − n − s) ∈ U_{p} for all p ∈ Δ_{a,b}. Now s, t − n − s ∈ S_{a,b} by Lemmas 2.1 and 2.2. So t ∈ T_{a,b}. □

Remark 2.6. It follows that the set of (a, b, c) ∈ ℚ^{×} × ℚ^{×} × ℚ such that at least one of a and b is positive and such that c is integral at all primes ramifying in H_{a,b} is diophantine over ℚ. This adds to the toolbox that might someday be useful for a negative answer to Hilbert’s Tenth Problem over ℚ. Given a prime p, it is possible to choose a, b, a′, b′ ∈ ℚ_{>0} with Δ_{a,b} ∩ Δ_{a′,b′} = {p}, so that T_{a,b} + T_{a′,b′} = ℤ_{(p)}; thus we also quickly recover the well-known fact that ℤ_{(p)} is diophantine over ℚ.

Lemma 2.7. We have ⋂_{a,b∈ℚ_{>0}} T_{a,b} = ℤ.

Proof. By Lemma 2.5, it suffices to show that for each p ∈ P there exist a, b ∈ ℚ_{>0} such that H_{a,b} is ramified at p. If p = 2, take a = b = 7. If p > 2, take a = p and choose b ∈ ℤ_{>0} with red_{p}(b) ∈ 𝔽_{p}^{×} − 𝔽_{p}^{×2}. □

3. Definition of ℤ

Theorem 3.1. The set ℤ equals the set of t ∈ ℚ for which the following Π_{2}^{+}-formula is true over ℚ:

(∀a, b)(∃a_{1}, a_{2}, a_{3}, a_{4}, b_{1}, b_{2}, b_{3}, b_{4}, x_{1}, x_{2}, x_{3}, x_{4}, y_{1}, y_{2}, y_{3}, y_{4}, n)
(a + a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + a_{4}^{2})(b + b_{1}^{2} + b_{2}^{2} + b_{3}^{2} + b_{4}^{2})
· [(x_{1}^{2} − ax_{2}^{2} − bx_{3}^{2} + abx_{4}^{2} − 1)^{2} + (y_{1}^{2} − ay_{2}^{2} − by_{3}^{2} + aby_{4}^{2} − 1)^{2}
+ n^{2}(n − 1)^{2} ⋯ (n − 2309)^{2} + (2x_{1} + 2y_{1} + n − t)^{2}] = 0.

Proof. The set of a for which there exist a_{1}, …, a_{4} such that a + a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + a_{4}^{2} = 0 are those satisfying a ≤ 0. Thus removing this factor and the corresponding factor for b is equivalent to restricting the domain of a, b to ℚ_{>0}. Now the theorem follows directly from Lemma 2.7. □

4. Reducing the number of quantifiers

The formula in Theorem 3.1 contains 2 universal quantifiers followed by 17 existential quantifiers. We do not see how to reduce the number of universal quantifiers. But we can reduce the number of existential quantifiers:

Theorem 4.1. It is possible to define ℤ in ℚ with a Π_{2}^{+}-formula with 2 universal quantifiers followed by 7 existential quantifiers.

Proof of Theorem 4.1. Starting with the formula in Theorem 3.1, we may replace each a_{i} and b_{i} by the corresponding x_{i}, and hence reuse the variables x_{i} (we thank Pace Nielsen for this idea, which greatly simplified our original proof). Next we solve 2x_{1} + 2y_{1} + n − t = 0 for y_{1} to eliminate y_{1}, and we clear denominators. Finally, the quantifier for n is unnecessary because n takes on only finitely many values. The resulting formula is

(∀a, b)(∃x_{1}, x_{2}, x_{3}, x_{4}, y_{2}, y_{3}, y_{4})
(a + x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + x_{4}^{2})(b + x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + x_{4}^{2})
· [(x_{1}^{2} − ax_{2}^{2} − bx_{3}^{2} + abx_{4}^{2} − 1)^{2} + ∏_{n=0}^{2309} ((n − t − 2x_{1})^{2} − 4ay_{2}^{2} − 4by_{3}^{2} + 4aby_{4}^{2} − 4)^{2}] = 0.□

Remark 4.2. Here we show that if f(t), g(t) ∈ ℚ(t) are rational functions, then the intersection of T_{f(a),g(a)} over all a ∈ ℚ such that f(a) and g(a) are nonzero and not both negative is always much larger than ℤ; this foils one possible approach to defining ℤ in ℚ using just one universal quantifier.

Tsen’s theorem implies that the quaternion algebra H_{f(t),g(t)} over ℚ(t) is split by \overline{ℚ}(t) and hence by k(t) for some number field k, and hence by ℚ_{p}(t) for any prime p splitting in k; for such p, we have that H_{f(a),g(a)} ⊗ ℚ_{p} is split for all a ∈ ℚ such that f(a) and g(a) are defined and nonzero. Hence any rational number whose denominator is divisible only by primes splitting in k will be in the intersection of the sets T_{f(a),g(a)} mentioned above.

We can also give a new proof of the following result, which was first proved by G. Cornelissen and A. Shlapentokh [CS07].

Theorem 4.3 (Cornelissen and Shlapentokh). For every ϵ > 0, there is a set R of primes of natural density at least 1 − ϵ such that ℤ is definable in ℤ[R^{−1}] using a Π_{2}^{+}-formula with just one universal quantifier (instead of two).

Proof. Given ϵ, choose a positive integer m such that 2^{−m} < ϵ, and let B be the set of the first m primes. Let R be the set of p ∈ P that fail to split in ℚ(\sqrt{b}) for at least one b ∈ B. The density of R equals 1 − 2^{−m} > 1 − ϵ.

For fixed b > 0, the set ⋃_{a∈ℤ[R^{−1}]} Δ_{a,b} equals the set of primes that fail to split in ℚ(\sqrt{b}), so ⋂_{a∈ℤ[R^{−1}]} T_{a,b} = ℤ[S_{b}^{−1}], where S_{b} is the set of primes that split in ℚ(\sqrt{b}). Thus

ℤ[R^{−1}] ∩ ⋂_{b∈B} ⋂_{a∈ℤ[S^{−1}]}T_{a,b} = ℤ.

The set on the left is definable in ℤ[R^{−1}] by a Π_{2}^{+}-formula, since positive existential formulas over ℚ may be modeled by equivalent positive existential formulas over ℤ[R^{−1}]. Moreover, only one universal quantifier (for a) is needed, since b ranges over only finitely many variables.

□

Remark 4.4. The proof of Theorem 4.3 shows also that for every ϵ > 0, there is a subset S ⊂ P of density less than ϵ (namely, ⋂_{b∈B} S_{b}) such that ℤ[S^{−1}] is definable in ℚ by a Π_{2}^{+}-formula with just one universal quantifier.

5. Defining rings of integers

Theorem 5.1. There is a Π_{2}^{+}-formula that in any number field k defines its ring of integers.

Proof. Let ℓ be a prime greater than 11 such that (ℓ − 1)/2 also is prime, e.g., ℓ = 23. Let ζ_{ℓ} be a primitive ℓ^{th} root of 1 in an algebraic closure of k. We will break into cases according to which subfields of ℚ(ζ_{ℓ}) are contained in k. Let ℓ^{∗} = (−1)^{(ℓ−1)/2}ℓ. Let f(x) ∈ ℤ[x] be the minimal polynomial of ζ_{ℓ} + ζ_{ℓ}^{−1} over ℚ.

Case 1: k contains a zero of f and a zero of x^{2} − ℓ^{∗}. Then k ⊇ ℚ(ζ_{ℓ}), so the residue field at every prime of k not above ℓ contains a primitive ℓ^{th} root of 1. In particular, every residue field is an 𝔽_{q} with q > 11, so Lemma 2.3 always applies. Also k has no real places. Thus the argument of Section 2 shows that for any a, b ∈ k^{×}, the analogously defined T_{a,b} (without the n) equals the set of elements of k that are integral at every prime ramifying in H_{a,b}. We can require a, b ∈ k^{×} by adding an equation abc − 1 = 0. We may combine equations over k by observing that if P_{n}(z_{1}, …, z_{n}) is the norm form for a degree-n extension of k, then P_{n}(z_{1}, …, z_{n}) = 0 is equivalent to z_{1} = ⋯ = z_{n} = 0. So O_{k} is defined in k by the following formula Φ:

(∀a, b)(∃c, x_{1}, x_{2}, x_{3}, x_{4}, y_{1}, y_{2}, y_{3}, y_{4})
P_{4}(abc − 1, x_{1}^{2} − ax_{2}^{2} − bx_{3}^{2} + abx_{4}^{2} − 1, y_{1}^{2} − ay_{2}^{2} − by_{3}^{2} + aby_{4}^{2} − 1, 2x_{1} + 2y_{1} − t) = 0.

This is not uniform in k, because the norm form must depend on k, but by quantifying over all possible coefficients for the norm form, we can replace Φ by a uniform formula.

Case 2: k contains a zero of f but not a zero of x^{2}−ℓ^{∗}. By using Case 1 and a Π_{2}^{+}-analogue of the “Going up and then down” method [Shl07, Lemma 2.1.17] (i.e., modeling a formula over k′ := k[x]/(x^{2} − ℓ^{∗}) by a formula over k, by restriction of scalars), we find a Π_{2}^{+}-formula Ψ defining O_{k} in k.

Cases 1 and 2: For any number field k containing a zero of f, we use

(((∃u) u^{2} − ℓ^{∗} = 0) ∧ Φ) ∨ (((∀v)(∃w) w(v^{2} − ℓ^{∗}) = 1) ∧ Ψ),

which, when written in positive prenex form, is a Π_{2}^{+}-formula, by [CZ06, Lemma 1.20.1]. (To replace a conjunction of polynomial equations by a single polynomial equation, we again use a norm form, and we quantify over its coefficients to make it uniform in k.)

The same approach of dividing into two cases lets us generalize to include the case where k does not contain a zero of f: in this case, f is irreducible over k since ℚ(ζ_{ℓ} +ζ_{ℓ}^{−1}) is abelian of prime degree over ℚ. □

Acknowledgements

I thank Pace Nielsen for discussions leading to, among other things, a simpler proof of Theorem 4.1. I thank also the referee for a few helpful comments on exposition.

References

[CS07] Gunther Cornelissen and Alexandra Shlapentokh, Defining the integers in large subrings of number fields using one universal quantifier, 2007. in preparation. ↑4

[CZ06] Gunther Cornelissen and Karim Zahidi, Elliptic divisibility sequences and undecidable problems about rational points (June 23, 2006). Preprint, to appear in J. reine angew. Math. ↑1.1, 1.1, 5

[DPR61] Martin Davis, Hilary Putnam, and Julia Robinson, The decision problem for exponential diophantine equations, Ann. of Math. (2) 74 (1961), 425–436. MR 0133227 (24 #A3061) ↑1.1

[Eis05] Kirsten Eisenträger, Integrality at a prime for global fields and the perfect closure of global fields of characteristic p > 2, J. Number Theory 114 (2005), no. 1, 170–181. MR 2163911 (2006f:11150) ↑2

[Mat70] Yu. Matiyasevich, The Diophantineness of enumerable sets, Dokl. Akad. Nauk SSSR 191 (1970), 279–282 (Russian). MR 0258744 (41 #3390) ↑1.1

[Rob49] Julia Robinson, Definability and decision problems in arithmetic, J. Symbolic Logic 14 (1949), 98–114. MR 0031446 (11,151f) ↑1.1

[Ser73] J.-P. Serre, A course in arithmetic, Springer-Verlag, New York, 1973. Translated from the French; Graduate Texts in Mathematics, No. 7. MR 0344216 (49 #8956) ↑2

[Shl07] Alexandra Shlapentokh, Hilbert’s tenth problem. Diophantine classes and extensions to global fields, New Mathematical Monographs, vol. 7, Cambridge University Press, Cambridge, 2007. MR 2297245 ↑5 Department of Mathematics, University of California, Berkeley, CA 94720-3840, USA

E-mail address: poonen@math.berkeley.edu
URL: http://math.berkeley.edu/~poonen/