Solutions in Other Rings

Most likely, Hilbert expected a positive solution of his tenth problem. This would allow us to recognize solvability of polynomial equations in many other rings, for example, in the ring of algebraic integers from any finite extension of the field of rational numbers, and in the ring of rational numbers. However, the obtained negative solution of Hilbert’s tenth problem does not imply directly undecidability results for other rings. Nevertheless, different researchers were able to reduce the Tenth problem to solvability of equations in many classes of rings and thus establish the undecidability of analogs of the Tenth problem for them (for survey see book [55] or [56] in this volume).

Such reductions can be made by constructing a polynomial equation solvable in a considered ring if and only if the parameter is a rational integer, or, more generally, by constructing a Diophantine model of integers in that ring. Such an approach exploits the mere undecidability of the original Hilbert’s tenth problem and does not require any new ideas from Computability Theory. However, number-theorists foresee some deep obstacles for the existence of such models for certain rings including, maybe the most interesting, the ring Q of rational numbers.

Recently Martin Davis proposed in [11] a quite different approach based on the existence of a special kind of undecidable sets constructed by Emil Post who named them simple. A listable set S is called simple if its complement to the set N of all natural numbers is infinite but contains no infinite listable set. In [43] Bjorn Poonen proved the undecidability of a counterpart of Hilbert tenth problem for a ring U of rational numbers denominators of which are allowed to contain “almost all” prime factors. His technique allows us to define a simple set S by a formula of the form

where ya is a computable function of a, p is a polynomial, and x1,...,xm range over ~ U. When these variables are allowed to range over all rational numbers, the same formula (2.35) defines some set Sp; clearly, S c Sp.

Martin Davis Conjecture [2010]. There is a Diophantine definition of a simple set S for which N - Sp is infinite, so that Sp is undecidable.

Martin Davis wrote in [11]:

This conjecture implies the unsolvability of H10 [Hilbert’s tenth problem] over Q. The conjecture seems plausible because although it is easy to construct simple sets, and there are a number of ways to do so, and if the conjecture is false, then no matter how S is constructed, and no matter what Diophantine definition of S is provided, Sp differs from N by only finitely many elements. Because the additional primes permitted in denominators in the transition from U to Q form a sparse set, this seems implausible.

Let us believe in the wisdom of the celebrated guru.

< Prev   CONTENTS   Source   Next >