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 🙂
Best Answer
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.