Further Results on Hilbert's Tenth Problem

Zhi-Wei Sun

Published 2017-04-12Version 1

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 $\mathbb Z$ of the integers. This was finally solved by Matijasevich negatively in 1970. In this paper we obtain some further results on HTP over $\mathbb Z$. We show that there is no algorithm to determine for any $P(z_1,\ldots,z_9)\in\mathbb Z[z_1,\ldots,z_9]$ whether the equation $P(z_1,\ldots,z_9)=0$ has integral solutions with $z_9\ge0$. Consequently, there is no algorithm to test whether an arbitrary polynomial Diophantine equation $P(z_1,\ldots,z_{11})=0$ (with integer coefficients) in 11 unknowns has integral solutions, which provides the best record on the original HTP over $\mathbb Z$. We also show that there is no algorithm to test for any $P(z_1,\ldots,z_{17})\in\mathbb Z[z_1,\ldots,z_{17}]$ whether $P(z_1^2,\ldots,z_{17}^2)=0$ has integral solutions, and that there is a polynomial $Q(z_1,\ldots,z_{20})\in\mathbb Z[z_1,\ldots,z_{20}]$ such that $$\{Q(z_1^2,\ldots,z_{20}^2):\ z_1,\ldots,z_{20}\in\mathbb Z\}\cap\{0,1,2,\ldots\}$$ coincides with the set of all primes.