Return to Answer

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.

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

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

Comments: 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

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.

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.

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.

Comments: Will Sawin's answer offers more comments on this. Here I record some of the more elementary cases: The conjecture clearly holds if $f$ is linear, e.g. $f(x,y,z)=6x + 10y+ 15z + 7$ or $6x+10y+30z+7$. So in particular it holds for $f(x)$ and $f(x,y)$. I have verified that the conjecture holds for $f(x,y,z)$ mod 5, mod 7, mod 8 and mod 9, where a non-trivial example may look like $f(x,y,z)=xy+yz+xz+x-5$. 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$.

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

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

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

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

Comments: This clearly holds if $f$ is linear, e.g. $f(x,y,z)=6x + 10y+ 15z + 7$ or $6x+10y+30z+7$. For non-linear but still multilinear $f$, non-trivial examples may look like $f(x,y,z)=xy+yz+zx+x-5$. I have done some numerical investigations of cases like this; we are looking for solutions to a multilinear Diophantine equation in at least three unknowns, and my conjecture is that it always has a root.

Algorithm conditional on the above

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.

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

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

Comments: Will Sawin's answer offers more comments on this. Here I record some of the more elementary cases: The conjecture clearly holds if $f$ is linear, e.g. $f(x,y,z)=6x + 10y+ 15z + 7$ or $6x+10y+30z+7$. So in particular it holds for $f(x)$ and $f(x,y)$. I have verified that the conjecture holds for $f(x,y,z)$ mod 5, mod 7, mod 8 and mod 9, where a non-trivial example may look like $f(x,y,z)=xy+yz+xz+x-5$. 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

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.