[FOM] bounds and Hilbert's 10th Problem
Martin Davis
martin at eipye.com
Sat Apr 15 15:37:04 EDT 2006
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
More information about the FOM
mailing list