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<d<\infty$ 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?

  • 7
    $\begingroup$ 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\}$. $\endgroup$ – Richard Stanley Aug 10 at 2:59
  • 2
    $\begingroup$ 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$. $\endgroup$ – Matt F. Aug 10 at 12:10
  • 3
    $\begingroup$ 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 ... $\endgroup$ – Emil Jeřábek Aug 12 at 16:44
  • 2
    $\begingroup$ ... 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. $\endgroup$ – Emil Jeřábek Aug 12 at 16:46
  • 3
    $\begingroup$ 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\}$$ $\endgroup$ – Matt F. Aug 13 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.