Exponential bounds for witnesses of diophantine definitions of Δ_{0}-formulas Zoé Chatzidakis (CNRS - Université Paris 7) Ehud Hrushovski^{1}^{,}^{2} (The Hebrew University of Jerusalem)

(1.1) Introduction and notation. L_{ar} = {+, ·, <, 0, 1}. We define exp^{k}(x) by induction as follows: exp^{0}(x) = x, exp(x) = exp^{1}(x) = 2^{x}, and exp^{k+1}(x) = 2^{exp^{k}(x)}.

The famous Theorem of Matjasevic̆ and Robinson, Davis, Putnam states that every subset of ℕ^{n} defined by a Δ_{0}-formula φ(z̄) is in fact definable by a diophantine formula, i.e., a formula ∃ūP_{1}(z̄, ū) = P_{2}(z̄, ū). We are interested in bounding the size of the witnesses ū in terms of the size of a tuple ā satisfying the formula φ(x̄).

We will say that the (eventual) bound for diophantine witnesses of the formula φ(z̄) is exp^{k}(sup{z̄}^{ℓ}) if there are an integer m, and polynomials P_{1}(Z̄, Ū), P_{2}(Z̄, Ū) over ℕ such that for every tuple ā in ℕ and N = sup{ā, m},

ℕ ⊧ φ(ā) ⟺ ℕ ⊧ ∃ū ≤ exp^{k}(N^{ℓ}) P_{1}(ā, ū) = P_{2}(ā, ū).

Our aim is to give a proof of the following weak version of a result of Gaifman and Dimitracopoulos [DG]:

Proposition. Let φ(z̄) be a Δ_{0}-formula of the language L_{ar} = {+, ·, <, 0, 1}. The eventual bound for diophantine witnesses of φ(z̄) is exp^{3}(sup{z̄}^{ℓ}) for some ℓ. The eventual bound for diophantine witnesses of y = 2^{x} is exp(sup{x, y}^{15}), i.e., exp^{2}(x^{15}).

Remark. It follows that exp^{4}(sup{z̄}) is an eventual bound for the witnesses of φ(z̄) and for the values of the polynomials P_{1}(z̄, ū), P_{2}(z̄, ū) appearing in the associated diophantine formula.

This result is announced in [DG], with the better bound of exp^{3}(sup{z̄}) for arbitrary Δ_{0}-formulas, but with only an indication of the proof. Here we give the proof we had found, before knowing of the result in [DG]. It is a simple inspection of the classical proof of Matjasevic̆ and Robinson, Davis, Putnam. The references are to Chapter II of Smoryński’s book [S].

(1.2) Conventions. We will use the notation f(x) ≫ g(x) to mean that lim_{x→∞} g(x)/f(x) = 0. Thus for instance, if p(X̄) is any polynomial with coefficients in ℕ, then p(x̄) ≪ exp(sup{x̄}). For ease of reading, we will use freely the “minus sign” − of ℤ, and while all constants and variables (including those quantified upon) will range over ℕ, the validity of equations will come from ℤ. We also allow ourselves the use of ≤ and <, and the use of the divisibility symbol |. Thus an expression of the form “x|(y − z)” is an abbreviation for the following formula:

∃u (z ≤ y ∧ ux + z = y) ∨ (z > y ∧ ux + y = z),

1 Supported by the Israel Science Foundation

2 Research carried out for the Clay Mathematics Institute as a Clay Prize research fellow where the variables range over ℕ.

(1.3) Theorem. Let a ∈ ℕ, a ≥ 2, and consider the Pell equation

X^{2} − (a^{2} − 1)Y^{2} = 1.

The solutions (in ℕ) of this equation are given by x = X_{a}(n), y = Y_{a}(n) for n > 0, where X_{a}(n) and Y_{a}(n) are defined by

X_{a}(n) + Y_{a}(n)\sqrt{a^{2} − 1} = (a + \sqrt{a^{2} − 1})^{n}.

For n ≥ 1, we have

Y_{a}(n) ≤ (2a)^{n−1}, X_{a}(n) ≤ (2a)^{n}.

Proof. This is Theorem II.4.2, and Lemma II.4.7 for the bound on Y_{a}(n). Note that X_{a}(n)^{2} = 1 + (a^{2} − 1)Y_{a}(n)^{2}, and this gives the bound on X_{a}(n).

(1.4) Lemma. The eventual bound for diophantine witnesses of the formula y = Y_{a}(x) is exp^{2}(sup{x, log a}^{5}). Proof. By Theorem II.5.1, y = Y_{a}(x) is defined by the formula

∃w, u, v, s, t, b

\begin{matrix}2x ≤ y & y|(b − 1) \\ w^{2} = 1 + (a^{2} − 1)y^{2} & u|(t − y) \\ u^{2} = 1 + (a^{2} − 1)v^{2} & y|(t − x) \\ s^{2} = 1 + (b^{2} − 1)t^{2} & y^{2}|v \\ u|(b − a) & v > 0. \end{matrix}

This is clearly equivalent to a diophantine formula: all the divisibility relations are expressible by diophantine formulas, and a conjunction of diophantine equations is equivalent to a diophantine equation. Hence to finish the proof of the lemma, we need to find bounds on the size of w, u, v, s, t, b. The proof of Theorem II.5.1 shows that one can take

w = X_{a}(x).

Then, letting m = yY_{a}(x), one takes

u = X_{a}(m), v = Y_{a}(m).

Choose b congruent to a modulo X_{a}(m) and to 1 modulo y, and let

t = Y_{b}(x), s = Y_{b}(x).

For sufficiently large N = sup{x, log a}, we then have

y, w ≤ (2a)^{x} ≪ exp(N^{3}),
m = yY_{a}(x) ≤ (2a)^{2x} ≪ exp(N^{3}),
hence u, v ≤ (2a)^{m} ≪ (2a)^{exp(N^{3})} ≪ exp^{2}(N^{4}),
b < yX_{a}(m) ≪ exp^{2}(N^{4})
t, s ≤ (2b)^{x} ≪ (2 exp^{2}(N^{4}))^{N} ≪ exp^{2}(N^{5}).

(1.5) Lemma. The eventual bound for diophantine witnesses of the formula z = x^{y} is exp^{2}(sup{log x, y}^{15}). Proof. By Corollary II.5.4, we have

z = x^{y} ⟺ ∃a[a = Y_{2x}(y + 2) ∧ (2ax − x^{2} − 1 > z)
∧X_{a}(y) − Y_{a}(y)(a − x) ≡ z mod (2ax − x^{2} − 1)].

We know that z = x^{y} ≤ exp(N^{2}). By the previous lemma (1.4), the eventual bound for diophantine witnesses of a = Y_{2x}(y + 2) is exp^{2}((2 sup{log(2x), y + 2})^{5}) ≪ exp^{2}(N^{6}), where N = sup{log x, y} is sufficiently large. Similarly, the eventual bound for diophantine witnesses of u = X_{a}(y), v = Y_{a}(y) is exp^{2}(M^{5}), where M = sup{log(a), y} ≪ (y + 2)log(4x) ≪ N^{3}. Hence eventual bound for diophantine witnesses of the formula z = x^{y} is exp^{2}(N^{15}).

(1.6) Lemma. The eventual bound for diophantine witnesses of each of the following formulas is of the form exp^{2}(sup{x, log a, log b}^{ℓ}) for some ℓ.

(1) z = \binom{x}{y} (y ≤ x).

(2) y = x!

(3) y = ∏_{k=0}^{x}(a + bk), where a, b ∈ ℕ^{>0}.

(4) y = ∏_{k=0}^{x}(a − k), where a ∈ ℕ^{>0}. Proof. We use II.2.9 and II.2.10 of [S].

(1) z = \binom{x}{y} if and only if

∃u, v, w (u = 2^{x} + 1) ∧ ((u + 1)^{x} = vu^{y+1} + zu^{y} + w) ∧ (z < u) ∧ (w < u^{y}).

The number u is given explicitly, and the numbers v, w are bounded above by (u + 1)^{x}. The result follows by (1.5).

(2) y = x! if and only if ∃z = (2x)^{x+1}, ∃v < \binom{z}{x} z^{x} = y\binom{z}{x} + v. Use (1) and (1.5).

(3) y = ∏_{k=0}^{x}(a + bk) if and only if

∃p, z [p > (a + bx)^{x+1} > y ∧ p|(bz − a) ∧ p|(\binom{x+z}{x+1}(x + 1)!b^{x+1} − y).]

Here p is any prime larger than (a + bx)^{x+1}, and there is such a prime < 2(a + bx)^{x+1}. The number z satisfies p|(bz − a), and is < p. This gives us bounds on p and z, and the result follows by (1.5), (1) and (2).

(4) y = ∏_{k=0}^{x}(a − k) if and only if

(a < x ∧ y = 0) ∨ ∃z(z + x = a ∧ y = ∏_{k=0}^{x}(z + k)).

Follows from (3).

(1.7) Lemma. Let φ(z̄) be a Δ_{0}-formula of the language L_{ar} = {+, ·, <, 0, 1}, z̄ = (z_{1}, …, z_{n}). There are polynomials P_{1}(X, Ū, V̄ , Z̄), P_{2}(X, Ū, V̄ , Z̄) ∈ ℕ[X, Ū, V̄ , Z̄], and constants k, ℓ and m such that for all n-tuple ā in ℕ,

ℕ ⊧ φ(ā) ⟺ ∃ū ≤ exp(N^{k}) ∀x ≤ N^{ℓ} ∃v̄ ≤ exp(N^{k}) P_{1}(x, ū, v̄, ā) = P_{2}(x, ū, v̄, ā),

where N = sup{m, a_{1}, …, a_{n}}. Proof. Note that our bounds are not sensitive to replacing some a by a^{m}, and we may therefore assume that our formula is of the form

∀x_{1} < z ∃y_{1} < z ⋯ ∀x_{ℓ} < z ∃y_{ℓ} < zP_{1}(x̄, ȳ, z̄) = P_{2}(x̄, ȳ, z̄),

where P_{1}, P_{2} are polynomials with coefficients in ℕ, and z = z_{1} + 1. The function (x_{1}, …, x_{i}) ↦ x_{1} + zx_{2} + ⋯ z^{i−1}x_{i} then defines a bijection between the n-tuples of elements smaller than z and the elements smaller than z^{i}. Hence our formula is equivalent to

∃u_{1}, …, u_{ℓ}∀x < z^{ℓ} ∃x_{1}, …, x_{ℓ}, y_{1}, …, y_{ℓ} < z (x = ∑_{i=1}^{ℓ} x_{i}z^{i−1})∧

∧(⋀_{i=1}^{ℓ} β(u_{i}, ∑_{j=1}^{i} x_{j}z^{j−1}) = y_{i}) ∧ (P_{1}(x̄, ȳ, z̄) = P_{2}(x̄, ȳ, z̄)).

Here β is the Gödel function. A bound for the elements u_{1}, …, u_{ℓ} is then of the form (1 + z^{ℓ}(z^{ℓ+1})!^{z^{ℓ}} (see Thm I.7.3 in [S]), and therefore bounded above by exp(z^{2ℓ+4}) for z large enough. This also bounds the size of the witnesses used to express each subformula β(u_{i}, ∑_{j=1}^{i} x_{j}z^{j−1}) = y_{i}, and yields the result.

(1.8) Proof of the Proposition.

Lemma (1.7) shows how to transform a Δ_{0}-formula φ(z̄) into a formula ∃ū ψ(z̄, ū), where ψ(z̄, ū) is of the form ∀x ≤ u ∃ū ≤ uP_{1}(x, ȳ, z̄, ū) = P_{2}(x, ȳ, z̄, ū). Moreover, we know that for large enough N, if ā ≤ N, then the elements ū can be chosen of size ≤ exp(N^{ℓ}) for some ℓ.

This reduces the problem to showing that the eventual bound for diophantine witnesses of a Δ_{0}-formula φ(z̄) of the form ∀x ≤ z_{1}∃y_{1}, …, y_{ℓ} ≤ z_{1} P_{1}(x, ȳ, z̄) = P_{2}(x, ȳ, z̄) is exp^{2}(sup{z̄}^{k}) (as exp^{2}((exp(N^{ℓ})^{k}) ≪ exp^{3}(N^{ℓ+1})). [The bound given in [DG] for a formula of this type is exp(sup{z̄}^{k}).]

This is done by inspection of the proof of the “Bounded Quantifier Theorem” II.2.11 of [S].

We may assume that φ(z̄) implies that all z_{i} are no bigger than z_{1}, by adding a variable and bounded existential quantifiers if necessary. Let Q(Z̄) be the polynomial obtained by replacing each variable X, Y_{1}, …, Y_{ℓ} by Z_{1} in the polynomial P_{1}(X, Ȳ , Z̄) + P_{2}(X, Ȳ , Z̄) and multiplying it by Z_{1}.

Then we have (see II.2.11): for any z̄ ∈ ℕ

ℕ ⊧ ∀x ≤ z_{1} ∃y_{1}, …, y_{ℓ} ≤ z_{1} P_{1}(x, ȳ, z̄) = P_{2}(x, ȳ, z̄)
⟺

ℕ ⊧ ∃c, t, v_{1}, …, v_{m} [t = (Q(z̄)!) ∧ (1 + (c + 1)t) = ∏_{j=0}^{z_{1}}(1 + (j + 1)t)

∧(1 + (c + 1)t)| ∏_{j=0}^{z_{1}}(v_{1} − j) ∧ ⋯ ∧ (1 + (c + 1)t)| ∏_{j=0}^{z_{1}}(v_{ℓ} − j)

∧(1 + (c + 1)t)|(P_{1}(c, v̄, z̄) − P_{2}(c, v̄, z̄))].

The numbers c and t are explicitly given, and we have Q(z̄) ≪ (z_{1}^{s}) for some s. For each x ≤ z_{1}, we choose a solution ȳ(x) = (y_{1}(x), …, y_{ℓ}(x)) ≤ z_{1} of P_{1}(x, ȳ, z̄) = P_{2}(x, ȳ, z̄).

The v_{i} are then chosen so that

v_{i} ≡ y_{i}(x) mod (1 + (x + 1)t)

for all i = 1, …, ℓ and 0 ≤ x ≤ z. The v_{i}’s can therefore be chosen < ∏_{x=0}^{z_{1}}(1 + (x + 1)t) = 1 + (c + 1)t, and hence are less than exp(z_{1}^{2s}) when z_{1} is large enough.

This, together with Lemma (1.6), gives the result.

References

[DG] H. Gaifman, C. Dimitracopoulos, Fragments of Peano’s arithmetic and MRDP theorem, in: Logic and Algorithmic, An International Symposium help in Honour of Ernst Specker, Monographie No 30 de l’Enseignement Mathématique, Genève 1982, 187 – 206.

[S] C. Smoryński, Logical Number Theory I, An introduction, Universitext, Springer-Verlag Berlin Heidelberg 1991.

UFR de Mathématiques Université Paris 7 - Case 7012 2, place Jussieu 75251 Paris Cedex 05 France

e-mail: zoe@logique.jussieu.fr

Institute of Mathematics The Hebrew University Givat Ram 91904 Jerusalem Israel

e-mail: ehud@math.huji.ac.il