[FOM] bounds and Hilbert's 10th Problem

[Martin Davis]

This is in response to Gabriel's strange (to my mind) skepticism about the 
interest of mathematicians of the classical "mindset" about bounds.

In my dissertation I proved that every r.e. set of natural numbers could be 
defined by an expression of the form:
    (Ey)(Ak < y)(E x_1, ... , x_n) [p(x,k,y,x_1, ... , x_n) = 0]
where p is a polynomial with integer coefficients. The proof was easy using 
methods of Gödel, and it followed from general considerations that there 
was an absolute upper bound on n, easily seen to be in the neighborhood of 
50. Soon thereafter, Raphael Robinson published a very intricate proof that 
n could be taken to be 4. Much later, using MRDP Matiyaevich showed that 
n=2 works.

MRDP itself showed that the bounded universal quantifier could be removed 
from this expression raising the question of a bound on n on this simple 
polynomial equation. In a paper published in Acta Arithmetica, Julia 
Robinson and Yuri Matiyasevich showed that n=13 works. Refining their 
techniques, Yuri later improved the result to n=9.

I have lectured about these matters many times over the years, and have 
never failed to find intense interest in the bounds.

Martin