Multilinear polynomials and the reduction $x_i^2\mapsto x_i$ on the cube

A polynomial $f\in F[x_1,\dots ,x_n]$ is multilinear when $f=0$, or when

${\mathrm{deg}}_{x_i}f\le 1\text{for every }i\mathrm{.}$

Equivalently, $f$ is a linear combination of the monomials

$x_T:={\prod }_{i\in T}{x}_i(T\subseteq [n])\mathrm{.}$

For a multi-index $\mathbf{t}$, let $\mathrm{supp}(\mathbf{t})=\{i:t_i>0\}$. The multilinear reduction of $f={\sum }_{\mathbf{t}}{c}_{\mathbf{t}}{x}^{\mathbf{t}}$ is the unambiguously defined polynomial

$\tilde{f}:={\sum }_{\mathbf{t}}{c}_{\mathbf{t}}{x}_{\mathrm{supp}(\mathbf{t})}\mathrm{.}$

Equivalently, each monomial is reduced by replacing every positive power $x_i^{t_i}$ by $x_i$. Thus $\tilde{f}$ is multilinear, including when it is the zero polynomial. The next lemma proves that it is the unique multilinear polynomial agreeing with $f$ on the cube, and that if $\tilde{f}\mathrm{\ne }0$ then its total degree does not exceed that of $f$.

• The reduction is a cube phenomenon. It is not an algebra homomorphism on all of $F[x_1,\dots ,x_n]$; it is the canonical representative for restricting a polynomial to $\{0,1{\}}^n$.