Algorithmic (un-)solvability of diophantine equations of given degree with given number of variables

Question

Question: For which $d, k \in \mathbb{N}$ is there an algorithm to determine whether a polynomial diophantine equation $$ P(x_1, \dots, x_k) = 0, \ \ \ P \in \mathbb{Z}[x_1, \dots, x_k] $$ of total degree $d$ in $k$ variables has a solution in integers? -- And for which $d$, $k$ is there no such algorithm, respectively, is it unknown whether such algorithm exists or not?

Remarks: Since linear diophantine equations in any number of variables can be solved by means of an algorithm, the answer is "yes" for any $(d,k) \in \mathbb{N}^2$ where $d = 1$. Also since one can test whether the roots of a univariate polynomial of any degree are integers, the answer is "yes" for any $(d,k) \in \mathbb{N}^2$ where $k = 1$. Further it is well-known that the answer is also "yes" for $(d,k) = (2,2)$. On the other hand, in the 1920s Thoralf Skolem has shown that the answer is "no" for $(d,k)$ where $d \geq 4$ and $k$ is "sufficiently large", and by a result by Zhi Wei Sun, the answer is also "no" for $(d,k)$ where $k \geq 11$ and $d$ is "sufficiently large", whatever the best presently known bounds for "sufficiently large" are -- cf. the Wikipedia article on Hilbert's tenth problem. Some more information can be found in Andres Caicedo's answer to this question (though partly concerning solutions in nonnegative integers).

These results still leave a lot of cases open, which are what this question asks for. An answer to this question could be given in the form of a diagram like the following, with the bounds of the $3$ sketched areas being made precise:

Answer 1

I'm going to take a stab at this. First (as mentioned in Andres Caicedo's answer to this question), Siegel proved in 1972 that there is an algorithm to determine whether a quadratic equation in any number of variables has a solution, and so $(2,k)$ is decidable for any $k$.

Next, the case of $d = 3$ and $k = 2$ is decidable. The most interesting situation is the case of a curve of genus one, where Siegel proved that there are finitely many solutions, and Baker and Coates proved in 1970 (in a paper titled "Integer points on curves of genus $1$") that there is an effective algorithm to find them. I believe that $(1,k)$, $(2,k)$, $(3,2)$ and $(k,1)$ are the only cases now that are known to be decidable.

In particular, the case of $d = 4$ and $k = 2$ falls into the "unknown" category. The generic case here would be asking for the integral points on a plane quartic, and (unless the plane quartic is superelliptic), there is no straightforward way to apply Baker's linear forms in logarithms. The same issue arises for $d \geq 5$ and $k = 2$.

The next case is $d = 3$ and $k = 3$, which is definitely in the "unknown" category. (For example, it is unknown whether there are integer solutions to $a^{3} + b^{3} + c^{3} = 114$.) If the $d = 3$, $k = 3$ case were solvable even for homogeneous equations, we would be able to successfully do a $3$-descent on any elliptic curve over $\mathbb{Q}$ and hence there would be an algorithm to determine the ranks of elliptic curves (something else we don't know how to do).

Finding the boundary between "unknown" and "undecidable" is a bit tricky because most of the work on undecidable equations is for those where the variables are non-negative or positive, which is slightly easier. For example, Jones's 1982 paper mentioned in Caicedo's answer constructs a universal Diophantine equation with positive values for variables, with $9$ variables and degree $\approx 1.6 \cdot 10^{45}$. However, for integer values of variables, the best that is known is Zhi Wei Sun's $11$ variable case (found in the 1992 paper "Reduction of unknowns in Diophantine representations"). In the positive integer case, there are unsolvable Diophantine equations with $4$ variables and with degree $58$, $8$ variables and degree $38$, $12$ variables and degree $32$, etc. I do not know of analogues of these results in the integer case.

Where is the boundary between unknown and undecidable? In Matijasevic and Robinson's 1975 paper where they prove the existence of a universal Diophantine equation with 13 variables, they say "We believe that the minimum number of unknowns necessary is less than $13$, possibly as small as $3$, but new methods will be needed to obtain the optimum result." I expect part of the reason that Matijasevic and Robinson believe the boundary may be $3$ is that they proved (in their joint 1974 paper in Russian) that given a polynomial $f(u,v,w,x)$ the problem of determining whether $\exists u, v \in \mathbb{N}$ so that $\forall w \in \mathbb{N}$, $\exists x \in \mathbb{N}$ so that $f(u,v,w,x) = 0$ is undecidable.

Note: The ABC conjecture may or may not be a theorem. If an effective version of the ABC Conjecture is true, there is (by a result of Elkies from 1981, "ABC implies Mordell") an algorithm for finding all rational points on curves, and this should give an algorithm for all the cases $(d,2)$ for any $d \geq 1$.