Zhegalkin Polynomial - Formal Properties

Formal Properties

Formally a Zhegalkin monomial is the product of a finite set of distinct variables (hence square-free), including the empty set whose product is denoted 1. There are 2n possible Zhegalkin monomials in n variables, since each monomial is fully specified by the presence or absence of each variable. A Zhegalkin polynomial is the sum (exclusive-or) of a set of Zhegalkin monomials, with the empty set denoted by 0. A given monomial's presence or absence in a polynomial corresponds to that monomial's coefficient being 1 or 0 respectively. The Zhegalkin monomials, being linearly independent, span a 2n-dimensional vector space over the Galois field GF(2) (NB: not GF(2n), whose multiplication is quite different). The 22n vectors of this space, i.e. the linear combinations of those monomials as unit vectors, constitute the Zhegalkin polynomials. The exact agreement with the number of boolean operations on n variables, which exhaust the n-ary operations on {0,1}, furnishes a direct counting argument for completeness of the Zhegalkin polynomials as a boolean basis.

This vector space is not equivalent to the free boolean algebra on n generators because it lacks complementation (bitwise logical negation) as an operation (equivalently, because it lacks the top element as a constant). This is not to say that the space is not closed under complementation or lacks top (the all-ones vector) as an element, but rather that the linear transformations of this and similarly constructed spaces need not preserve complement and top. Those that do preserve them correspond to the boolean homomorphisms, e.g. there are four linear transformations from the vector space of Zhegalkin polynomials over one variable to that over none, only two of which are boolean homomorphisms.