24
$\begingroup$

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:

Sketch

$\endgroup$
3
  • $\begingroup$ We can say that 2 degrees is uniquely solvable. For large degrees, the problem of the impossibility of writing the formula of the solution in General for algebraic equations of large . Probably better to not consider all the equations together, and to find out what equations can be solved. $\endgroup$
    – individ
    Commented May 25, 2015 at 4:41
  • 1
    $\begingroup$ To nitpick, Skolem didn't show the answer is no, but rather proved a result that we now, after Matiyasevich's theorem, can interpret as you do. $\endgroup$ Commented Feb 9, 2017 at 7:30
  • 1
    $\begingroup$ This is a fascinating question because it mirrors what we know of the universality of Turing Machines with a given number of states and symbols: cstheory.stackexchange.com/questions/10207/… features similar graphs, with some granularity for decidability and weaker models of computation. $\endgroup$ Commented May 21, 2020 at 0:12

1 Answer 1

23
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ Just some sharpening of the bounds between "unknown" and "undecidable" would still be interesting -- e.g. is Matijasevic and Robinson's 1975 result still the best bound known? $\endgroup$
    – Stefan Kohl
    Commented May 27, 2015 at 15:33
  • 1
    $\begingroup$ If you're referring to the "13 variable universal equation", then no, this is no longer the best known. Jones's 1982 result with 9 variables is the best currently known (at least according to a 2012 survey article by Matijasevich). $\endgroup$ Commented May 27, 2015 at 17:38
  • $\begingroup$ Do you know any reference to "the case of d=3 and k=2 is decidable"? I would like to include this in the paper and need a reference.Baker and Coates covers the "most interesting" case when cubic P(x,y) is absolutely irreducible and have genus 1. Is there anywhere a theorem covering all the remaining "less interesting" cases? I search for it for 2 days and all references at best say that other cases "essentially reduce" to the quadratic equation, so let us ignore them and consider the "most interesting" case of elliptic curves... $\endgroup$ Commented Jun 11, 2020 at 16:05
  • $\begingroup$ I have found some references that cover most but not all of the remaining cases, and the ones that remain are simple to do, but I cannot explain all of this in a comment. Can I send this info to you in an e-mail? You can find my e-mail at my website (linked to from my MO profile). $\endgroup$ Commented Jun 11, 2020 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.