I'm trying to upper-bound the number of roots of a degree $k$ multilinear polynomial $p(X_1,\ldots,X_n) \in F_2[X_1,\ldots,X_n]$

(for $1 < k \le n$).

Unfortunatelly, the Schwartz–Zippel Lemma only gives a trivial bound: $2^n$ roots,

probably because it has to consider non-multilinear polynomials like $(X_1^2 - X_1)$, or even $\sum \limits_{i=1}^n (X_i^2 - X_i)$, which disappear everywhere (over $F_2)$...

any idea about a non-trivial upper-bound for the number of roots ?

thanks in advance :)

  • $\begingroup$ Isn't a multilinear polynomial on $n$ scalar variables of the form $c X_1 \ldots X_n$ (and thus either identially $0$ or of degree $n$)? Or do you mean a homogeneous polynomial of degree $k$ that has degree $1$ in each variable? $\endgroup$ – Robert Israel Jan 30 at 23:01
  • $\begingroup$ $X_1 \ldots X_n$ has $2^n-1$ roots, so the "trivial" bound isn't far off. $\endgroup$ – Robert Israel Jan 30 at 23:04

The sharp upper bound is $2^n-2^{n-k}$. This can obviously be achieved, by a single monomial of degree $k$. To show it is an upper bound, we prove by induction on $n$ that if $p$ is a nonzero multilinear polynomial in $n$ variables of degree $\leq k$, then $p$ has at most $2^n-2^{n-k}$ zeroes. The base case $n=0$ is trivial.

Now suppose we know the upper bound is correct for polynomials in $n-1$ variables, and let $p$ be a nonzero multilinear polynomial of degree $\leq k$ in $X_1,\dots,X_n$. We can write $$p=X_nq+r,$$ where $q$ and $r$ are polynomials in $X_1,\dots,X_{n-1}$, and $\deg q\leq k-1$ and $\deg r\leq k$. Suppose first that $r=0$. Then $q\neq 0$, so by the induction hypothesis $q$ has at most $2^{n-1}-2^{n-k}$ zeroes. For $p$ to be zero, we must have either $X_n=0$ ($2^{n-1}$ solutions) or $X_n=1$ and $q=0$ (at most $2^{n-1}-2^{n-k}$ solutions). So $p$ has at most $2^{n-1}+2^{n-1}-2^{n-k}=2^n-2^{n-k}$ zeroes.

Now suppose $q+r=0$. Then $r\neq 0$, and moreover $q+r=0$ implies $r$ has degree at most $k-1$. So, by the induction hypothesis $r$ has at most $2^{n-1}-2^{n-k}$ zeroes. As in the previous case, we now see that $p$ has at most $2^{n-1}+2^{n-1}-2^{n-k}=2^n-2^{n-k}$ zeroes (the first term corresponding to the case $X_n=1$ and the second two terms corresponding to the case $X_n=0$).

Finally, suppose $r$ and $q+r$ are both nonzero. Then they are each nonzero polynomials of degree at most $k$, so by the induction hypothesis they each have at most $2^{n-1}-2^{n-1-k}$ zeroes. Zeroes of $p$ correspond to zeroes of $r$ if $X_n=0$ and zeroes of $q+r$ if $X_n=1$, so $p$ has at most $2^{n-1}-2^{n-1-k}+2^{n-1}-2^{n-1-k}=2^n-2^{n-k}$ zeroes.

This argument can be generalized to any finite field: if $p$ is a nonzero multilinear polynomial in $n$ variables of degree $\leq k$ over a field $F$ with $d$ elements, then $p$ has at most $d^n-(d-1)^kd^{n-k}$ zeroes (the number of zeroes of a degree $k$ monomial).

The proof is essentially the same except that in the induction step you must consider all the polynomials of the form $aq+r$ for $a\in F$, not just $r$ and $q+r$. If any of these polynomials is $0$, then at most one is $0$ (otherwise $p$ would be $0$), and they all have degree at most $k-1$. Adding up the zeroes of $p$ for each possible value of $X_n$ then gives that $p$ has at most $d^{n-1}+(d-1)(d^{n-1}-(d-1)^{k-1}d^{n-k})=d^n-(d-1)^{k}d^{n-k}$ zeroes. On the other hand, if none of the polynomials $aq+r$ are zero, then they all have degree at most $k$ and we find $p$ has at most $d(d^{n-1}-(d-1)^kd^{n-1-k})=d^n-(d-1)^kd^{n-k}$ zeroes.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.