Multilinear polynomial

A multilinear polynomial has degree at most one in each variable. It has a unique expansion $f(x)={\sum }_S{a}_S{\prod }_{i\in S}{x}_i$.

Replace each positive power $x_i^d$ by $x_i$ in a polynomial. This gives a multilinear polynomial of no larger polynomial degree with the same values on $\{0,1{\}}^n$. In the polynomial method in combinatorics, these functions lie in a vector space with a basis consisting of the square-free monomials of the required polynomial degrees.

On the uniform layer of the Boolean cube ${\Omega }_r$, every multilinear polynomial of polynomial degree at most $s\le r$ is in the span of the degree-$s$ square-free monomials. For $T\subseteq [n]$, $|T|=j\le s$, and $x_T={\prod }_{i\in T}{x}_i$, the identity isAt the characteristic vector of a set $A$ of size $r$, both sides vanish if $T⊈A$. Otherwise exactly $\left(\genfrac{}{}{0ex}{}{r-j}{s-j}\right)$ summands are $1$. Hence the dimension of the restricted polynomial space is at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. No assertion of independence of the spanning monomials is needed, so no condition $r+s\le n$ is required. Unlike ordinary homogenization, this operation preserves degree bounds by using the fixed-weight evaluation domain.

Replace each positive power $x_i^a$ in a monomial by $x_i$ and combine equal monomials. The result is a multilinear polynomial agreeing with the original polynomial at every point of $\{0,1{\}}^n$, because $x_i^a=x_i$ there for $a\ge 1$. Its polynomial degree does not increase. This reduction identifies polynomial functions on the Boolean lattice with their unique square-free monomial representations: uniqueness follows by successively evaluating at characteristic vectors of sets in increasing order of size.