Lesson 10

Theorem. For any function \(f \in B_{n}\), there exists a unique Zhegalkin polynomial.

Proof.

• Existence  can be shown almost the same way as the existence of DNF: for each set of variable values for which the function equals one, we add a “literal” monomial (product of literals) to the polynomial. For example, for an assignment \(x_{1}=0,x_{2}=0,x_{3}=1\), we add a monomial \((1 \oplus x_{1})(1 \oplus x_{2})x_{3}\). After this, we expand all brackets and get the polynomial.
  Existence can also be proven by induction on \(n\). For this, we consider a decomposition analogous to the one discussed above: \[f(x_{1}, \dotsc, x_{n})= (1 \oplus x_{1})f_{0}(x_{2}, \dotsc, x_{n}) \oplus x_{1}f_{1}(x_{2}, \dotsc, x_{n}) \ .\] After this, we can use the induction hypothesis. (The base case is easy to check.)


• Uniqueness  can be proven using a counting argument: the number of different polynomials is \(2^{2^n}\) (each of the \(2^{n}\) monomials in the polynomial is either present or not). The number of Boolean functions on \(n\) variables is also \(2^{2^n}\). Thus, if some function could be represented by two polynomials, then some other function would lack a polynomial.
  Uniqueness can also be proven in another way. Suppose that the multilinear polynomials \(p(x_{1}, \dotsc, x_{n})\) and \(q(x_{1}, \dotsc, x_{n})\) coincide with the function \(f \in B_{n}\) at all points \(x \in \{0,1\}^{n}\), but are different (as sets of monomials). Then, the polynomial \(d=(p \oplus q)\) contains monomials and is equal to zero at all points. We will show that this cannot happen by induction on \(n\). Let's expand: \[\begin{align*}d(x_{1}, \dotsc, x_{n})&= (1 \oplus x_{1})d_{0}(x_{2}, \dotsc, x_{n}) \oplus x_{1}d_{1}(x_{2}, \dotsc, x_{n})\\&=x_{1}(d_{0} \oplus d_{1})(x_{2}, \dotsc, x_{n}) \oplus d_{0}(x_{2}, \dotsc, x_{n})\end{align*}\] Now, substitute \(x_{1}=0\). We find that the polynomial \(d_{0}\) is zero at all points. Then, by the induction hypothesis, it contains no monomials, and our expansion simplifies to \[x_{1}d_{1}(x_{2}, \dotsc, x_{n}) \ .\] Substituting \(x_{1}=1\), we conclude that \(d_{1}\) also contains no monomials.
  Finally, we can also prove by contradiction that a polynomial containing monomials cannot vanish at all points. Let \(p(x_{1},\dotsc,x_{n})\) be such a polynomial. It is clear that its constant term equals zero (otherwise \(p(0,\dotsc,0)=1\)). We then take a monomial \(m\) that contains the fewest variables. We substitute one into these variables and zero into all others. The value of the polynomial on this set will be equal to one. Indeed, any other monomial contains a variable not in \(m\): if this were not the case for some monomial, then that monomial would be a subset of \(m\). Thus, all other monomials vanish, and the value of the polynomial is equal to one. This is a contradiction.

◼