The Exercise

Take polynomials in variables $x_i$ , one for each index $i$ in a set $\sigma$ , and evaluate them only at bit strings: points $x$ whose coordinates are each $0$ or $1$ . These points form the Boolean cube $\{0,1\}^{\sigma}$ . Since $x_i^2 = x_i$ for a bit, the polynomials $x_1^2$ and $x_1$ take the same values on the cube, and so do many other pairs.

The exercise is that this ambiguity disappears once every variable appears at most to the first power. Two such polynomials that agree at every bit string are the same polynomial, with the same coefficient on every monomial.^✦

The library states this claim over a commutative ring $R$ of coefficients, such as the real or the complex numbers.

Multilinear Polynomials

A polynomial $p$ in the variables $x_i$ , $i \in \sigma$ , with coefficients in $R$ is multilinear when its degree in each variable, the highest power of that variable in any of its monomials, is at most one: $\deg_{x_i} p \le 1 \qquad \text{for every } i \in \sigma .$ (1)^✦ Thus $x_1 x_2 - 3x_3$ is multilinear and $x_1^2$ is not.

The Claim

For a point $x$ with coordinates in $R$ , write $p(x)$ for the value of $p$ at $x$ , the element of $R$ obtained by substituting each coordinate for its variable.

Theorem 1. Let $p$ and $q$ be multilinear polynomials in the variables $x_i$ , $i \in \sigma$ , with coefficients in $R$ , and suppose they take the same value at every point of the Boolean cube. Then $p$ and $q$ are equal: $p(x) = q(x) \ \text{ for all } x \in \{0,1\}^{\sigma} \quad\Longrightarrow\quad p = q .$ (2)^✦

What Is Checked

The $0$ and $1$ of the Boolean cube are the zero and the unit of $R$ .

What the library proves about multilinear polynomials is the uniqueness (2).