4
$\begingroup$

According to Matiyasevich, the existence of integer solutions of systems of polynomial equations with integer coefficients is undecidable. By introducing additional variables substituting factors of monomials of degree $>2$ it follows that the solvability of systems of $p$ linear and $q$ quadratic equations with integer coefficients (not all zero) in $n$ integer variables is undecidable if $p,q,n$ are unrestricted.

Given a subset $T$ of nonnegative integer triples $(p,q,n)$, one can ask about the solvability in the subclass of problems with $(p,q,n)\in T$. What is known about the boundary between decidable and undecidable in dependence on $T$? In particular, I am interested in ''smallest'' sets $T$ for which undecidability is known, and ''largest '' sets $T$ for which decidability is known.

A related, but almost disjoint MO question (intersecting in the case $p=0,q=1$) is Algorithmic (un-)solvability of diophantine equations of given degree with given number of variables . The latter refers also to Which types of Diophantine equations are solvable? , which refers to the paper

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

From Theorem 3 there, one can infer - by the above substitution process, the elimination of the single linear equation, and the substitution of the positive integer variables by $1+$ a sum of 4 integer squares - that if $T$ contains $(p,q,n)=(0,74,138)$, undecidability follows. (If the integers were constrained to be positive, $(p,q,n)=(0,47,57)$ would be enough for undecidability.)

$\endgroup$

0

Your Answer

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