Is Multilinear Hilbert's tenth problem version undecidable?

Question

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?

Answer 1

Matt F. conjectured that a multilinear polynomial in $n$ variables, of degree $<n$, 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.)

Answer 2

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|<k/c$.

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.

Answer 3

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.