Representations with a Small Number of Quantifiers

The existence of universal listable sets together with the DPRM-theorem implies that we can bound the number of unknowns in a Diophantine representation (2.3) of an arbitrary listable set M; today’s record n = 9 was obtained by me [34] (a detailed proof is presented in [19]). Accordingly, Hilbert’s tenth problem remains undecidable even if we restrict ourselves to equations in 9 unknowns.

With present techniques, in order to get results for even smaller number of variables, one has to broaden the class of admissible formulas.

For example, for the DPR-theorem 3 unknowns are sufficient; originally this was proved in [36], and even for single-fold representations. Later this result was improved in [20, 21] to representations of the form

where exponential polynomials EL and ER are constructed by using unary exponentiation 2C only (rather than general binary exponentiation bc). Harry R. Levitz proved in [26] that this result cannot be further improved to single unknown.

Soon after Martin Davis introduction of the normal form (2.6), Raphael Robinson [51] gave a rather different proof and showed that one can always take n = 4. In the same paper he gave another representation with 6 quantified variables, namely,

Much later, exploiting the power of the DPRM-theorem, he [52] improved the bound for Davis normal form (2.6) to л = 3 and showed that x3 can be dropped from (2.17). Both of these results were further improved: in [31] to л = 2, in (2.6) and in [42] both x2 and x3 were dropped from (2.17).

More interesting is the possibility to replace the bounded universal quantifier in (2.6) and (2.17) by finite conjunction. For example, it was shown in [31] that every listable set has a representation of the form

where l is a fixed number and Qi are polynomials with integer coefficients.

Clearly, the right-hand side of (2.18) can be rewritten as a system of Diophantine equations in 2l + 2 unknowns. While this quantity is high, each single equation has only 4 unknowns. This implies, for example, the following. Consider the class D2,2 of Diophantine sets that can be defined by formulas of the form

Clearly, we саллв1 decide whether a giveл mtersecto of ^АлШу талу sets from class D2,2 is empty or лot. Informally, this means that among sets of pairs of natural numbers defined by Diophantine equations with just 2 unknowns there are sets with complicated structure having no “transparent” description.

In the above cited results the variables range over natural numbers; for the case of integer-valued variables corresponding results are at present somewhat weaker (in terms of the number of unknowns).