Further results on Hilbert's tenth problem (Q829448)

``Hilbert's Tenth Problem (HTP) asks for an algorithm to test whether an arbitrary polynomial Diophantine equation with integer coefficients has solutions over the ring \(\mathbb Z\) of integers. This was finally solved negatively by Matiyasevich in 1970. In this paper we obtain some further results on HTP over \(\mathbb Z\). We prove that there is no algorithm to determine for any \(P(z_1,\dots,z_9)\in\mathbb Z[z_1,\dots,z_9]\) whether the equation \(P(z_1,\dots,z_9) = 0\) has integral solutions with \(z_9\geq0\). Consequently, there is no algorithm to test whether an arbitrary polynomial Diophantine equation \(P(z_1 ,\dots, 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 prove that there is no algorithm to test for any \(P(z_1,\dots,z_{17})\in\mathbb Z[z_1,\dots,z_{17}]\) whether \(P(z_1^2,\dots,z_{17}^2) = 0\) has integral solutions, and that there is a polynomial \(Q(z_1,\dots,z_{20})\in \mathbb Z[z_1,\dots,z_{20}]\) such that \(\{\mathbb Q(z_1^2,\dots,z_{20}^2) \colon z_1,\dots,z_{20}\in\mathbb Z\}\cap\{0,1,2,\dots\}\) coincides with the set of all primes.'' One of the main results of this work, the fact that \(11\) variables are sufficient to obtain the undecidability result over the integers, was known since the author's PhD thesis in 1992, but never published in English.