Which types of Diophantine equations 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.

Answer 2

The answer of Andrés E. Caicedo is great, but its main focus is which classes are unsolvable. Let me mention some solvable families.

We consider polynomial Diophantine equations $$ P(x_1, \dots, x_n) = 0 $$ where $P$ is a polynomial with integer coefficients. We may assume that $P$ is irreducible over ${\mathbb Q}$, otherwise the problem reduces to the same problem for each of the factors.

Equations in $n=1$ variable are trivially solvable. Let us consider cases $n=2$ and $n>2$ separately. If $n=2$, our equation is $$ P(x,y)=0 $$ for some $P$ irreducible over ${\Bbb Q}$.

If $P$ is reducible over ${\Bbb C}$, the equation is solvable, see Rational solutions to $P(x,y)=0$ for $P$ reducible over ${\mathbb C}$, hence we may assume that $P$ is absolutely irreducible. Then genus $g$ of the curve $P(x,y)=0$ is well-defined.

If $g=0$, the equation is solvable, see https://doi.org/10.4064/cm-66-1-1-7 and https://doi.org/10.1006/jsco.2001.0515

If $g=1$, it is solvable as well, see https://doi.org/10.1017/s0305004100045904

(Note that by genus-degree formula, this implies that all two-variable equations of degree at most $3$ are solvable)

Equations of the form $Q(x,y)=c$ for homogeneous $Q$ are solvable (all solutions can be described). If $Q$ is irreducible over ${\mathbb Q}$ of degree $d\geq 3$ and $c\neq 0$, this is a Thue equation and it can be solved by the Theorem of Baker https://doi.org/10.1098/rsta.1968.0010 . The case of reducible $Q$ can be reduced to a finite number of Thue equations, the cases $d\leq 2$ and $c=0$ are easy.

If $P(x,y)$ is at most quadratic in one of the variables, the equation is solvable. Also, hyperelliptic equations of the form $ay^m=Q(x)$ are solvable. As noted in https://arxiv.org/abs/2108.08705, these results are easy corollaries from https://doi.org/10.1017/s0305004100044418

We say that equation $$ P(x,y) = \sum_{i=0}^m \sum_{j=0}^n a_{ij} x^i y^j = 0 $$ with integer coefficients $a_{ij}$ of degree $m>0$ in $x$ and $n>0$ in $y$ satisfies the Runge's condition if $P(x,y)$ is irreducible over ${\mathbb Q}$ and either (C1) there exists a coefficient $a_{ij}\neq 0$ of $P$ such that $ni+mj>mn$, or (C2) the sum of all monomials $a_{ij}x^iy^j$ of $P$ for which $ni + mj = nm$ can be decomposed into a product of two non-constant coprime polynomials. All equations satisfying the Runge's condition are solvable, see https://doi.org/10.4064/aa-62-2-157-172

Two-variable equations containing at most three monomials are solvable (all solutions can be described). See our paper "Diophantine equations with three monomials" https://doi.org/10.1016/j.jnt.2023.06.011 .

The simplest two-variable equations not satisfying the above conditions are the equations $y^3 \pm y = x^4+x$. I do not know how to find all integer solutions to these equations. If we are only interested to know whether solution exists, then these equations are trivial with $x=y=0$ being a solution, and the simplest open examples are $y^3+xy=x^4+4$, $y^3+xy=x^4+x+2$, $y^3+y=x^4+x+4=0$ and $y^3-y=x^4+2x-2$, see Can you solve the listed smallest open Diophantine equations?.

Now consider equations in any number of variables. Then we have the following solvable families.

Equations with no real solutions. Obviously, such equations have no integer solutions as well. Much less obviously, there is an algorithm to check whether a given equation has any real solution, see Tarski, Alfred A decision method for elementary algebra and geometry. 2nd ed. University of California Press, Berkeley-Los Angeles, Calif., 1951.

Equations with no solutions modulo some integers $m$. Obviously, such equations have no integer solutions. Much less obviously, there is an algorithm to check this condition for all $m$ in finite time, see https://doi.org/10.2307/1970438

(Equations with real solutions and solutions modulo every $m$ but with no integer solutions are called counterexamples to the integral Hasse principle, a simple example is $x^2y+2y+1=0$)

All equations with at most two monomials are solvable (all integer solutions can be described), see https://doi.org/10.2307/2371109

Equations of the form $ax_i = Q$, where $Q$ is a polynomial in other variables. This class is trivially solvable, and it contains surprisingly many random equations, in particular all linear equations.

All quadratic equations are solvable, see https://doi.org/10.2307/1970438 . We not only can determine whether an integer solution exists, but in fact output a complete list of all integer solutions, provided that this list is finite.

Equations solvable by quadratic residues method. Assume that the equation is presented in the form $$ \prod_{j=1}^k P_j = Q, $$ where $P_1,\dots,P_k,Q$ are non-constant polynomials in variables $x_1,\dots,x_n$ with integer coefficients. Then return that the equation is ``Solved'' if it is possible to find integers $m\geq 3$ and $0\leq r_1 < \dots < r_l < m$ such that (a) for any integers $x_1,\dots,x_n$, all positive divisors of $Q(x_1,\dots,x_n)$ must be equal to some $r_j$ modulo $m$, but (b) there is no solution $x_1,\dots,x_n$ modulo $m$ such that all $|P_j(x_1,\dots,x_n)|$ are equal to some $r_j$ modulo $m$. See https://arxiv.org/abs/2108.08705

Vieta jumping method. Call variable $x_i$ of a general equation $P(x_1,\dots,x_n)=0$ eligible if (a) the equation can be written in the form $$ a_i x_i^2 + Q_i x_i + R_i = 0 $$ where $a_i\neq 0$ is an integer and $Q_i$ and $R_i$ are polynomials in other variables, and (b) for every solution $x=(x_1,\dots,x_{i-1},x_{i+1},\dots,x_n)$ to this equation modulo $|a_i|$, $Q_i(x)$ is divisible by $a_i$. Then consider optimization problem of maximizing $t$ over $(x_1,\dots,x_n,t)\in {\mathbb R}^{n+1}$ subject to constraints $P=0$, $|x_i|\geq t$ for each $i$, and $|-(Q_i/a_i)-x_i|\geq |x_i|$ for each eligible variable $x_i$. If the optimal value $t^*$ is finite, then the equation is solvable, see https://arxiv.org/abs/2108.08705

A simple example of an equation outside the listed families is the equation $y^2-x^3y+z^3+3=0$, see Can you solve the listed smallest open Diophantine equations?.