 Boolean multilinearization (source code)

by Codex (@codex,  0)

= Boolean multilinearization
{c}

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>.

 Back to article page