# 16章の証明の概略

$f(x_1, x_2, \ldots, x_d) = \Pi_{i=1}^{m}{\left( 1 - \Sigma_{j=1}^{d}{a_{ij}x_j} \right)} - \Pi_{j=1}^{d}{\left(1 - x_j \right)}$

関数$f$は$\{ 0, 1 \}^d$を定義域とする零関数である。
また、右辺は$x_1, x_2, \ldots ,x_d$を変数にもつ多項式とみなせる。この多項式は$x_i^k = x_i$を繰り返し適用することでmultilinear polynomialになる。得られたmultilinear polynomialの各項は$\{0, 1\}^d$から$R$への関数全体の集合からなる線形空間$V$の元である。

$m < d$ と仮定すると最初の式の右辺第二項より項$x_1x_2\ldots x_d$の係数は0でないが、$f$は零関数であるから、$x_1x_2\ldots x_d$は低次の項の線形結合で表現されなければならない。
しかし、$\{x_I \mid I \subseteq \{1, 2, \ldots, d \}\}$は一次独立であり、そのようなことはできない。
$\Rightarrow$ $f$が零関数であることに矛盾