# 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 *E**_{L}* and E

_{R}are constructed by using

*unary*exponentiation 2

^{C}only (rather than general

*binary*exponentiation b

^{c}). 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 *x _{3}* can be dropped from (2.17). Both of these results were further improved: in [31] to

*л =*2, in (2.6) and in [42] both x

_{2}and

*x*were dropped from (2.17).

_{3}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 D_{2},_{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* D_{2},_{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).