TAOCP 7.1.1 Exercise 11
Equation (19) expresses every Boolean function $f(x_1,\ldots,x_n)$ uniquely as a multilinear polynomial, f(x_1,\ldots,x_n) = \sum_{S\subseteq\{1,\ldots,n\}} a_S \prod_{i\in S} x_i ,
Exercise 11. [M25] [M25] Is there an intuitive way to understand exactly when the multilinear representation of $f(x_1, \ldots, x_n)$ contains, say, the term $x_1 x_2 x_4 x_5$? (See (19).)
Verified: yes
Solve time: 2m34s
Solution
Equation (19) expresses every Boolean function $f(x_1,\ldots,x_n)$ uniquely as a multilinear polynomial,
$$ f(x_1,\ldots,x_n)
\sum_{S\subseteq{1,\ldots,n}} a_S \prod_{i\in S} x_i , $$
with coefficients taken over the ordinary integers. The question asks for an interpretation of when the coefficient of a particular monomial, such as
$$ x_1x_2x_4x_5, $$
is nonzero.
Let
$$ T={1,2,4,5}. $$
Set every variable not in $T$ equal to $0$. The multilinear representation then reduces to
$$ g(x_1,x_2,x_4,x_5)
\sum_{U\subseteq T} a_U \prod_{i\in U}x_i . $$
The coefficient $a_T$ of $x_1x_2x_4x_5$ is determined by the values of $g$ on the $2^{|T|}=16$ assignments of the variables in $T$. By the inclusion-exclusion form of the Möbius inversion underlying (19),
$$ a_T
\sum_{U\subseteq T} (-1)^{|T|-|U|} ,f(\chi_U), $$
where $\chi_U$ denotes the assignment in which $x_i=1$ for $i\in U$ and $x_i=0$ for $i\notin T$.
Thus $a_T$ is the alternating sum of the values of $f$ on the $16$ vertices of the $4$-dimensional cube determined by the variables $x_1,x_2,x_4,x_5$.
This gives the desired intuition. The term $x_1x_2x_4x_5$ appears exactly when the combined effect of changing all four variables cannot be explained by any combination of effects involving only proper subsets of those variables. Equivalently, after all lower-order interactions have been canceled by inclusion-exclusion, a nonzero residue remains.
In finite-difference language, $a_T$ is the fourth mixed difference
$$ (\Delta_1\Delta_2\Delta_4\Delta_5 f)(0,\ldots,0). $$
Hence the monomial $x_1x_2x_4x_5$ occurs in the multilinear representation if and only if this mixed difference is nonzero. The coefficient measures the pure four-way interaction among the variables $x_1,x_2,x_4,x_5$.
Therefore the intuitive criterion is:
$$ \boxed{\text{The term }x_1x_2x_4x_5\text{ appears iff the alternating sum of } f\text{ over the corresponding }4\text{-cube is nonzero.}} $$
Notes
For a Boolean function viewed as a set function on subsets of ${1,\ldots,n}$, the coefficient of $\prod_{i\in T}x_i$ is precisely the Möbius transform of that set function at $T$. The multilinear terms therefore record the genuine interactions among the corresponding variables.