= Multilinear reduction on the Boolean cube
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\geq1$. 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.
Back to article page
