# Is Multilinear Hilbert's tenth problem version undecidable?

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

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

• 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 '19 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 '19 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 '19 at 16:44
• Explicitly, $\{x_1=y_1,\dots,x_n=y_n\}$ is equivalent to $\bigl(3(x_1-y_1)+1\bigr)\cdots\bigl(3(x_n-y_n)+1\bigr)=1$. – Emil Jeřábek Aug 13 '19 at 7:24
• 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 '19 at 11:56

Matt F. conjectured that a multilinear polynomial in $$n$$ variables, of degree $$, has solutions unless the gcd of its nonconstant coefficients does not divide the constant coefficient.

Lemma: A multilinear polynomial equation is soluble in $$\mathbb Z_p$$ for all $$p$$ and soluble in $$\mathbb R$$ unless the gcd of the nonconstant coefficients does not divide the constant coefficient.

Thus, Matt F.'s conjecture is equivalent to the statement that these polynomials satisfy the Hasse principle. Because in this case the degree is less than the number of variables, a Hasse principle is plausible here. I don't know if anyone has written down a general Hasse principle conjecture that would imply this one, and because the degree is only one less than the number of variables in the worst case, a Hasse principle is likely to be very hard to prove.

Proof of Lemma: We may assume that the gcd of all the coefficients is $$1$$. Suppose there are no solutions over $$\mathbb Z_p$$. If we fix the values of every variable except one $$x_i$$, we get a linear equation in $$i$$. This is automatically solvable unless the coefficient of $$x_i$$ is zero mod $$p$$. The coefficient of $$x_i$$ mod $$p$$ is a multilinear polynomial in the other variables and can only be identically zero if its coefficients all vanish mod $$p$$ - this can be proven by induction on the number of variables, for instance. So if there is a local obstruction, the coefficients of all monomials containing $$x_i$$ must be zero mod $$p$$. Because the gcd is one, the constant coefficient must be nonzero mod $$p$$, and so the gcd of the nonconstant coefficients does not divide the constant coefficient.

Over the reals, a linear equation in $$x_i$$ is soluble unless the coefficient of $$x_i$$ is exactly zero, which can only always happen if all the coefficients of monomials containing $$x_i$$ are zero, so there is only a real obstruction if the polynomial is constant. (In fact, this argument shows something slightly stronger, which is that the set of real solutions is noncompact, since fixing all variables but one, a dense set of values of the fixed variable admit a nontrivial choice for the unfixed variable.)

• Thanks! I am glad to see the lemma and the impression of plausibility. – Matt F. Aug 23 '19 at 16:11
• Does this give an argument that if there is a solution mod $p$, then there is also a solution mod $p^k$? – Matt F. Sep 6 '19 at 12:29
• @MattF. Yes if the coefficients do not all together have a common factor. – Will Sawin Sep 6 '19 at 12:30
• I don't understand how that works, e.g. for $f(x,y,z)=xy+yz+xz+2x+1$. Then $(1,1,1)$ is a root mod $2$ which does not lift to any roots mod $4$. (That is not a counterexample to the claim, since $(0,1,3)$ is a root mod $4$, but it makes me realize that I don't understand how the proof works.) – Matt F. Sep 7 '19 at 21:49
• @MattF. The coefficients of $x,y,z$ in the linear form you get by fixing the other variables are all zero mod $2$ in that case. My method only finds solutions where at least one of those coefficients is nonzero. – Will Sawin Sep 7 '19 at 22:46

Here is a proposition and a conjecture, which together would establish an algorithm for determining whether a multilinear $$f$$ has a root.

Proposition

Let $$c$$ be the coefficient of $$x_1x_2\cdots x_t$$ in a multilinear $$f(x_1,\ldots,x_t)$$.

Let $$k$$ be the sum of the absolute values of the coefficients in $$f$$.

If $$c>0$$, then $$f$$ has roots iff it has roots where some $$x_i$$ has $$|x_i|.

Proof: Suppose all the $$x_i$$ have $$|x_i|\ge k/c$$. Let $$P = x_1x_2\cdots x_t$$. We rewrite the equation $$f(x_1,\ldots,x_t)=0$$ so the left side has the term with $$P$$, and the right side has everything else. The left side is $$cP$$. On the right side, each product of variables is at most $$P/(k/c)$$, since each of those products is missing at least one factor that goes into $$P$$. Taking absolute values gives $$c|P| \le (k-c)\,|P|\,/(k/c)$$, which is impossible.

Conjecture

Let $$c$$ be the coefficient of $$x_1x_2\cdots x_t$$ in a multilinear $$f(x_1,\ldots,x_t)$$ where each $$x_i$$ appears non-trivially.

If $$c=0$$, then $$f$$ has roots iff its constant coefficient is divisible by the gcd of the non-constant coefficients.

Proof of conjecture for linear $$f$$: This is just restating that the gcd of a set is a linear combination of its elements. Example: $$6x + 10y+ 15z + 7$$ has a root, but $$6x+10y+30z+7$$ does not.

Proof of conjecture mod $$p^r$$: Assume wlog that the gcd of the non-constant coefficients is $$1$$. Let $$c_S x_S$$ be a term of minimal degree among all those non-constant terms of $$f$$ whose coefficients are relatively prime to $$p$$. Let $$j$$ be the smallest index in $$S$$. Then set $$x_i = 1$$ if $$i \in S - \{j\}$$, set $$x_i = 0$$ if $$i \notin S$$. The resulting restriction of $$f$$ is of the form $$(c_S + pq) x_j + b$$, and since $$c_S+pq$$ is invertible mod $$p^r$$, this has a root mod $$p^r$$. Example: Let $$x=x_1$$, $$y=x_2$$, $$z=x_3$$. To find a root for $$xy+yz+zx+2x+1$$ mod $$8$$, we can take $$xy$$ as the term of minimal degree among all those terms whose coefficients are relatively prime to $$2$$. So we set $$y=1$$, $$z=0$$, and the polynomial reduces to $$3x+1$$, which indeed has a root mod $$8$$ with $$x=5$$.

Reason for non-triviality: $$z$$ appears trivially in $$f(x,y,z)=5xy+2x+2y$$, which is why this conjecture doesn't apply to that $$f$$, e.g. it does not represent $$3$$.

Comments on general approaches: As Will Sawin's answer points out, given that the conjecture holds mod $$p^r$$, and that the real version holds trivially, the conjecture is equivalent to a Hasse principle. The linear argument above handles the cases of $$f(x)$$ and $$f(x,y)$$; I hope someone else will be able to prove the case of $$f(x,y,z)$$; and for $$f(w,x,y,z)$$, I can either prove the conjecture outright or reduce it to the three-variable case so long as $$f$$ has a coefficient of 0 for one of $$wxy$$, $$wxz$$, $$wyz$$ or $$xyz$$.

Algorithm conditional on the above

Recall that $$t$$ is the number of variables.

If $$t=1$$ it is trivial to determine if $$f$$ has a root.

If $$t>1$$ and $$c=0$$, we can determine whether $$f$$ has a root according to the above conjecture.

If $$t>1$$ and $$c\neq 0$$, let $$d=\lfloor k/|c|\rfloor$$. Then we can determine whether $$f$$ has a root by substituting the integers in $$[-d,d]$$ for each variable. Specifically, we test whether $$f(-d,x_2,\ldots,x_t)$$ has a root, and whether $$f(-d+1,x_2,\ldots,x_t)$$ has a root, making all possible substitutions until testing whether $$f(x_1,x_2,\ldots,d)$$ has a root. By the above proposition, $$f$$ has a root iff one of these polynomials with fewer variables has a root.

Summary: We use real inequalities if $$f$$ has a term with all the variables, and divisibility otherwise, and that may be enough.

• Can you prove that the equation is locally soluble if and only if the constant coefficient is a multiple of the gcd of the others? – Will Sawin Aug 23 '19 at 13:09
• @WillSawin, I am hoping that the three-variable case can be solved by people who know the theory of ternary quadratics better than I do. I may work on reducing the four-variable case or higher to the three-variable case. – Matt F. Aug 23 '19 at 14:28
• For my question (local obstructions all take the specified form) I think it can be proved in an arbitrary number of variables. I will write this up shortly. – Will Sawin Aug 23 '19 at 15:07
• For the case of ternary quadratic forms, see mathoverflow.net/questions/341845/… – GH from MO Sep 17 '19 at 21:22
• By Sidney Raffer’s answer (or rather, his comment below his answer), the conjecture as written is false. – Emil Jeřábek Oct 3 '19 at 6:22

This is not an answer but a longish comment.

There is no Hasse Principle for multilinear polynomials. Take for example the polynomial equation $$(5x+2)(5y+3)=11.$$ Evidently the equation has no integer solutions. I'll show that it has $$p$$-adic solutions for every prime $$p$$.

First take $$x=0$$ in the displayed equation. We then require a $$p$$-adic integer $$y$$ such that $$2(5y+3)=11$$. The latter equation is equivalent to $$10y=5$$, which has a $$p$$-adic integer solution for all $$p\ne2$$. Next, take $$y=0$$ in the displayed equation. We then require a $$p$$-adic integer $$x$$ such that $$3(5x+2)=11$$. This is equivalent to $$15x=5$$, which has a p-adic integer solution for all $$p\ne3$$. Therefore the displayed equation has $$p$$-adic integer solutions for all $$p$$. Clearly there are real solutions. So the Hasse Principle fails for multilinear polynomials.

• Yes, and that’s why the conjecture above is restricted to multilinear polynomials whose degree is strictly smaller than the number of variables. (I’m skeptical that this restriction is enough to make a Hasse principle hold, but anyway.) – Emil Jeřábek Oct 1 '19 at 16:09
• @Emil: For the case where the number of variables is greater than the degree, consider $((5x+2)(5y+3)-11)(3(u+v)+1)$. Maybe the conjecture can be saved by requiring irreducibility? – Sidney Raffer Oct 3 '19 at 4:11
• Oh yes, indeed. – Emil Jeřábek Oct 3 '19 at 6:23
• Thanks. $((5x+2)(5y+3)+11)(3(u+v)+1)$ is a cleaner counterexample, since it’s not divisible by 5. – Matt F. Oct 3 '19 at 11:34
• Irreducibility is not enough, since even if $f$ is reducible, $f+1$ is probably irreducible. We could add “except for irreducibility modulo an additive constant” to the conjecture, but that doesn’t sound like an improvement to me at the moment. – Matt F. Oct 7 '19 at 3:06