# number of roots of a multilinear polynomial over a finite field

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 ?

• 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? Jan 30, 2019 at 23:01
• $X_1 \ldots X_n$ has $2^n-1$ roots, so the "trivial" bound isn't far off. Jan 30, 2019 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.