Diophantine Equations – Which Types Are Solvable?

Question

Is there a list somewhere of which types of Diophantine equations are solvable, which types are not solvable, and which types are not known to be solvable or not? (When I say solvable, I mean that we can determine in a finite number of steps whether or not there exist solutions.) For instance, we know that linear Diophantine equations are solvable. But we know by Matiyasevich's theorem that there are some Diophantine equations that are not solvable.

I am interested in seeing what the borderline between solvable and unsolvable looks like.

Answer 1

Craig:

For a while, there was some research on improving bounds on the number of variables or degree of unsolvable Diophantine equations. Unfortunately, I never got around to cataloging the known results in any systematic way, so all I can offer is some pointers to relevant references, but I am not sure of what the current records are.

Perhaps the first paper to consider along these lines is

Y. Matiyasevich, J. Robinson, "Reduction of an arbitrary Diophantine equation to one in 13 unknowns", Acta Arithmetica (27), (1975), 521-553

The most significant paper in the area is undoubtedly

J.P. Jones, "Universal Diophantine equation", Journal of Symbolic Logic (47), (1982), 549-571.

Let me quote from Matiyasevich's review for MathReviews:

It has been known since 1970 that every recursively enumerable set $W$ has a representation of the form $$ x\in W\Leftrightarrow\exists w_1\cdots w_\nu P(x,w_1,\cdots,w_\nu)=0, $$ where $P$ is a polynomial with integer coefficients and $x,w_1,\cdots,w_\nu$ are nonnegative integers. J. Robinson and the reviewer [Acta Arith. 27 (1975), 521--553; MR0387188 (52 #8033)] showed that one can always take $\nu=13$. Later the reviewer claimed [see, for example, Logic, foundations of mathematics and computability theory (London, Ont., 1975), Part 1, 121--127, Reidel, Dordrecht, 1977; MR0485685 (58 #5508)] that it suffices to have $\nu=9$; however he never wrote anything but terse notes with limited circulation. In the paper under review the author first performs the hard work of developing and making public all the cumbersome technical details of the proof. Then he develops what is known as a universal Diophantine equation, namely, an equation $U(x,z,u,y,w_1,\cdots,w_{28})=0$ such that for any recursively enumerable set $W$ a corresponding equation $P=0$ in the representation above can be obtained from $U=0$ just by substituting particular numerical values for the parameters $z$, $u$ and $y$. While the mere existence of universal equations has also been known since 1970, the author here manages to exhibit $U$ almost explicitly in only 7 printed lines!

Here is a link to Jones's abstract; of note is the following part:

In these equations there are 28 unknowns $a,b,c,d,e,f,g,h,i,j,k,l, m,n,o,p,q,r,s,t,w,A,B,C,D,E,F,G$ and four parameters $z,u,v,x$. The degree is $5^{60}$.

The degree can be reduced to 4 at the expense of the number of unknowns. The following pairs $(n,d)$ where $n$ is the number of unknowns and $d$ is the degree, are sufficient for all r.e. sets:

$(58, 4),(38, 8),(32, 12),(29, 16),(28, 20),(26, 24),(25, 28),(24, 36),(21, 96)$, $(19, 2668),(14, 2.0\times10^5),(13, 6.6\times10^{43}),(12, 1.3\times10^{44}),(11, 4.6\times10^{44})$, $(10, 8.6\times10^{44}),(9, 1.6\times10^{45})$.

The last pair $(9, 1.6\times10^{45})$ is the 9 unknowns theorem. This theorem, due to Matijasevich, is proved in this paper.

There are two other, more recent, papers I'm aware of:

Zhi Wei Sun, "J. P. Jones's work on Hilbert's tenth problem and related topics", Adv. in Math. (China) 22 (1993), no. 4, 312–331.

I haven't seen this paper, but I believe it is in Chinese. Here is the Abstract:

This paper is a survey of modern results on Hilbert's tenth problem (especially the work of J. P. Jones). It consists of six sections: 1. Hilbert's tenth problem; 2. The nine unknowns theorem; 3. Universal Diophantine equations; 4. Classification of quantifier prefixes over Diophantine equations; 5. Diophantine representations; 6. Applications of Hilbert's tenth problem. Some new results due to the author, such as the undecidability of $\exists^{11}$ over ${\mathbb Z}$, are also mentioned in the survey.

Finally, there is the following (quoting from MathReviews):

Fritz Grunewald, Dan Segal, "On the integer solutions of quadratic equations", J. Reine Angew. Math. 569 (2004), 13–45.

In the paper under review the authors construct an algorithm to determine whether an arbitrary quadratic equation in several variables has solutions in positive integers. In a 1972 paper, C. L. Siegel [Nachr. Akad. Wiss. Göttingen Math.-Phys. Kl. II 1972, 21-46; MR0311578 (47 #140)] constructed an algorithm to determine whether an arbitrary quadratic equation had integer solutions. The transition from integer solutions to positive integer solutions in the general context of Diophantine equations is usually done using Lagrange's theorem concerning representation of integers by the sums of four squares. Unfortunately, replacing all the variables by sums of squares clearly changes the degree of the equation, and therefore this method will be of no use if the degree of the equation is of concern.

To construct an algorithm for positive integer solutions, the authors solve a more general problem. They give a decision procedure to solve a system of quadratic equations in integers subject to finitely many specified congruences and linear inequalities. En route to constructing this algorithm, the authors also produce some interesting number-theoretic results concerning the distribution of integral points on quadric hypersurfaces at infinity.

While of independent number-theoretic interest, this paper is also a valuable contribution to our understanding of the boundary of Diophantine undecidabilty with respect to the degree of the equation. J. P. Jones [Bull. Amer. Math. Soc. (N.S.) 3 (1980), no. 2, 859-862; MR0578379 (81k:10094)] has shown that the degree of the equations with the decidable Hilbert's tenth problem for positive integer solutions has to be less than 4, and the results in this paper indicate that the only remaining question pertains to the degree 3 equations.

Reviewed by Alexandra Shlapentokh.

Let me close by mentioning that work on the tenth problem is still very active, although it has moved from just the setting of ${\mathbb Z}$ to more general number rings and beyond. A great reference is the recent book by Shlapentokh, "Hilbert's tenth problem. Diophantine classes and extensions to global fields". New Mathematical Monographs, 7. Cambridge University Press, Cambridge, 2007.

---

[Edit (April 12, 2017)] The talk by Zhi-Wei Sun mentioned in the comments, "On Hilbert's tenth problem and related topics", a talk given at the City University of Hong Kong on April 14, 2000, is at his page.

Also, Sun has just posted to the arXiv a paper on precisely this topic, Further Results on Hilbert's Tenth Problem. Here is the 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 $\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,\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\ge0$. 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 show 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 $$ \{Q(z_1^2,\dots,z_{20}^2): z_1,\dots,z_{20}\in\mathbb Z\}\cap\{0,1,2,\dots\} $$ coincides with the set of all primes.