# Martin Davis Conjecture

## Statement and Corollaries

Very soon Martin Davis came to a conjecture, first announced in [3], that would imply the undecidability of Hilbert’s tenth problem. To be able to state this conjecture, we need to introduce a bit more terminology.

Hilbert asked for solving Diophantine equations with numerical coefficients. One can also consider equation with symbolic coefficient, that is, equations with parameters. Such an equation has the form

similar to (2.1) but now the variables are split into two groups: parameters a1, ...,am, and unknowns x1,...,xn.

As another (minor technical) deviation from Hilbert’s statement of the problem, we will assume that both the parameters and the unknowns range over the natural numbers; following the tradition of mathematical logic, we will consider 0 as a natural number.

For some choice of the values of the parameters the Eq. (2.2) may have a solution in the unknowns, and for another choice may have no solution. We can consider the set M of all m-tuples of the values of the parameters for which the Eq. (2.2) has a solution in the unknowns:

Sets having such a Diophantine representation are also named Diophantine.

Traditionally, in Number Theory an equation is the primary object, and one is interested in a description of the set of the values of the parameters for which the equation has a solution. Martin Davis, in a sense, reversed the order of things taking sets as primary objects—he decided to give a general characterization of the whole class of all Diophantine sets.

He approached this problem from a computational point of view. All Diophan- tine sets have one common property: they are listable, or, in another terminology, effectively enumerable. This means the following. Given a parametric Diophantine equation (2.2), we can start looking over, in some order, all possible (m + n)-tuples {a,...,am, x,...,xn), for each such a tuple check if the value of the polynomial P is equal to zero, and if this happens to be the case, write down the tuple {a,...,am) on some list. Sooner or later each tuple from the set (2.3) will appear on this list, maybe many times, and all tuples from the list will belong to this set.

Described above was a rather specific way of listing elements of Diophantine sets. For an arbitrary set to be listable no restriction is imposed on the method for generating its elements, the only requirement is that this should be done by an algorithm. For example, it is evident that the set of prime numbers is listable: it is easy to write a program that would print 2, 3, 5,____

Thus, computability theory imposed an obstacle for a set to be Diophantine: if a set is not listable, it cannot be Diophantine. Martin Davis conjectured that this is the only obstacle.

Martin Davis conjecture. Every listable set is Diophantine.

I find that this was a rather daring conjecture because it has many corollaries, some of them quite striking.

For example, Martin Davis conjecture implied the existence of a one-parameter Diophantine equation

having a solution if and only if a is a prime number. Hilary Putnam noticed in [47] that the same would be true for the equation

In other words, the set of all prime numbers should be exactly the set of all nonnegative values of the polynomial from the left-hand side of (2.5) assumed for all natural values of x0,..., xn .Number-theorists did not believe in such a possibility.

Some other consequences of Davis conjecture will be presented below. Of course, the undecidability of Hilbert’s tenth problem is among of them. This is due to the classical fundamental result, the existence of listable sets of natural numbers for which there is no algorithm for recognizing, given a natural number a, whether it belongs to the set or not.

Davis conjecture is much stronger than what would be sufficient for proving the undecidability of Hilbert’s tenth problem. Namely, it would suffice to find for any particular undecidable set M some representation similar to (2.2) with P being replaced by any function which becomes a polynomial in x1 ,...,xn after substituting numerical values for a,...,am. For example, we could allow parameters to appear in the exponents as it was done by Anatolyi Ivanovich Mal’tsev in [27].