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.
Best Answer
Your question is probably too general, I simply hope that you'd like to learn some personal experience of people who do their research in diophantine equations or who apply the equations to other areas.
Although my starting research (under- and postgraduate level) was the theory of transcendental numbers, quite tied to diophantine equations (especially the ones related to linear forms in logarithms), I did not try to work on these. (Maybe, because of my father's attempts to prove Fermat's Last Theorem.) But at one occasion I was "introduced" to the Erdős--Moser equation $1^k+2^k+\dots+(m−1)^k=m^k$ ($m$ and $k$ positive integers), Applications of pattern-free continued fractions, and was impressed by the beauty and power of the method which Leo Moser used in 1953 to show that no solution (except $1+2=3$) exists with $m\le 10^{10^6}$. (!) Moser's method could not give much more, and I was happy enough to collaborate on some new ideas and computational achievements of nowadays to significantly extend (after more than 50 years) Moser's bound.
Another favourite diophantine equation is Catalan's equation $x^p-y^q=1$ ($p,q>1$) which was rather recently solved by Preda Mihăilescu. He even managed to avoid linear forms in logs (which are far from beauty because of so many technicalities). There are many steps in the proof, treating some special cases, most of them using completely different methods of diophantine analysis and algebraic number theory. But they are just beautiful! For example, there are two different proofs of the nonsolvability of $x^2-y^q=1$ in integers $x>1$, $y>1$ for a prime $q>3$. The original one, due to Ko Chao ([On the diophantine equation $x^2=y^n+1$, $xy\ne0$, Sci. Sinica 14 (1965) 457--460]; also given in Mordell's "Diophantine equations"), uses the law of quadratic reciprocity in a very elegant way. Another one, due to E.Z. Chein [A note on the equation $x^2=y^q+1$, Proc. Amer. Math. Soc. 56 (1976) 83--84], is extremely short and elementary.
Summarizing, I would say that natural criteria for considering some diophantine equations (and ignoring other) are the simplicity of the equation (isn't $x^n+y^n=z^n$ simple?) and the beauty and novelty of methods to solve it. Probably, the usefullness of the equation has to be taken into account as well.