Submission date: 12 April 2017

Abstract:

Hilbert's Tenth Problem (HTP) asked for an algorithm to test whether an arbitrary polynomial Diophantine equation with integer coefficients has solutions over the ring Z of the integers. This was finally solved by Matijasevich negatively in 1970. In this paper we obtain some further results on HTP over Z. We show that there is no algorithm to determine for any P(z_1,...,z_9) in Z[z_1, ... ,z_9] whether the equation P(z_1, ... ,z_9)=0 has integral solutions with z_9 ≥ 0. Consequently, there is no algorithm to test whether an arbitrary polynomial Diophantine equation P(z_1, ... ,z_{11})=0 (with integer coefficients) in 11 unknowns has integral solutions, which provides the best record on the original HTP over Z. We also show that there is no algorithm to test for any P(z_1, ... ,z_{17}) in Z[z_1, ... ,z_{17}] whether P(z_1^2, ... ,z_{17}^2)=0 has integral solutions, and that there is a polynomial Q(z_1, ... ,z_{20}) in Z[z_1, ... ,z_{20}] such that { Q(z_1^2, ... ,z_{20}^2) : z_1, ... ,z_{20} in Z } ∩ {0,1,2, ... } coincides with the set of all primes.

Mathematics Subject Classification: 11U05, 03D35, 03D25, 11D99, 11A41, 11B39

Keywords and phrases:

Full text arXiv 1704.03504: pdf, ps.