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 ?
thanks in advance :)
 A: 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.
