# Is Hilbert's tenth problem undecidable for multilinear polynomials in $\mathbb Z[x_1,\dots,x_n]$?

A multilinear polynomial $$f\in\mathbb Z[x_1,\dots,x_t]$$ has terms only of form $$b\prod_{i=1}^tx_i^{a_i}$$ where $$a_i\in\{0,1\}$$ and $$b\in\mathbb Z$$.

1. Is there no general purpose algorithm for finding integer roots of this class of polynomials?

2. Given $$f$$ is there a bound $$0 such that $$\{(x_1,\dots,x_t)\in\mathbb Z^n\wedge\|(x_1,\dots,x_n)\|_\infty\leq d\implies f(x_1,\dots,x_n)\neq0\}\iff\{\forall(x_1,\dots,x_n)\in\mathbb Z^n\mbox{ }f(x_1,\dots,x_n)\neq0\}$$ holds?

• The problem of the existence of an integer zero of a finite set of multilinear integer polynomials is undecidable, since given any integer polynomial $g$ we can replace each $x_i^{b_i}$ with $x_{i,1}\cdots x_{i,b_i}$ and adjoin the equations $x_{i,1}=\cdots=x_{i,b_i}$. Also, making the same substitution for $x_i^{b_i}$ and adding to $g$ the polynomial $\sum_j (x_{i,1}-x_{i,j})^2$ shows that if we allow $a_i\in\{0,1,2\}$ rather than $a_i\in\{0,1\}$, then the existence of an integer zero for one polynomial is undecidable. This suggests the undecidability for $a_i\in\{0,1\}$. – Richard Stanley Aug 10 at 2:59
• A good test case is $5xyz+3(x+y+z)−1$, which is too hard for Mathematica. Asking for "FindInstance[5 x y z + 3 (x + y + z) == 1, {x, y, z}, Integers]" gets the reply "The methods available to FindInstance are insufficient to find the required instances or prove that they do not exist." -- The polynomial looks good in that it has roots over the reals and over all obvious $Z/p^nZ$. But we can rule out integer roots with $xyz=0$ in $Z/3Z$. And we can rule out integer roots with $xyz\neq 0$ by the lack of real solutions to $x^2 \ge 1, y^2 \ge 1, ((1-3x-3y)/(5xy+3))^2 \ge 1$. – Matt F. Aug 10 at 12:10
• The problem of the existence of an integer zero of a set of two multilinear polynomials is undecidable. First, by Richard Stanley’s comment, we can reduce integer solvability of a general polynomial system to a single “multiquadratic” polynomial, and by applying his reduction again, we reduce it to solvability of a system of the form $\{f(x_1,\dots,x_n,y_1,\dots,y_n)=0,x_1=y_1,\dots,x_n=y_n\}$, where $f$ is multilinear. Moreover, we can combine $\{x_1-y_1,\dots,x_n-y_n\}$ to a single multilinear polynomial: using the fact that the only integer solution of $3xy+x+y=0$ is $(0,0)$, we can ... – Emil Jeřábek Aug 12 at 16:44
• ... combine any pair of multilinear polynomials in disjoint sets of variables to a single multilinear polynomial, and the same holds for any finite set of multilinear polynomials in pairwise disjoint sets of variables by applying this trick several times. – Emil Jeřábek Aug 12 at 16:46
• In case it's helpful for anyone else to see the Stanley-Jerabek procedure: to solve $$x^2+5=y^3$$ in integers, the multiquadratic form is $$(a-b)^2+(c-d)^2+(d-e)^2+(ab+5-cde)^2=0,$$and the two-equation multilinear form is $$\{(a-b)(a'-b')+(c-d)(c'-d')+(d-e)(d'-e')+(ab+5-cde)(a'b'+5-c'd'e')=0,$$ $$(3a-3a'+1)(3b-3b'+1)(3c-3c'+1)(3d-3d'+1)(3e-3e'+1)=1\}$$ – Matt F. Aug 13 at 11:56