Lesson 8

Zhegalkin polynomial or algebraic normal form (ANF) of a function \(f \in B_{n}\) is a multilinear polynomial \(P(x_{1}, \dotsc, x_{n})\) with 0/1 coefficients such that for all \(x_{1}, \dotsc, x_{n} \in \{0,1\}\) it holds that \(f(x_{1}, \dotsc, x_{n})=P(x_{1}, \dotsc, x_{n})\). The term “multilinear” means that the degree of every variable in every monomial is at most one.

As usual, a polynomial is a sum of monomials, and a monomial is a product of variables. Both sum and product are taken modulo two. Since we are only interested in the value of the polynomial for \(x_{i} \in \{0,1\}\), we can assume that each variable appears in a monomial to a power not greater than one (since \(x_{i}^{2}=x_{i}\) for \(x_{i} \in \{0,1\}\)).

For example, for the (ternary) disjunction function \(\operatorname{OR}_{3}(x_{1}, x_{2}, x_{3})=x_{1}\lor x_{2} \lor x_{3}\), such a polynomial is \[x_{1} \oplus x_{2} \oplus x_{3} \oplus x_{1}x_{2} \oplus x_{2}x_{3} \oplus x_{1}x_{2} \oplus x_{1}x_{2}x_{3} \ .\]

from itertools import product

for x1, x2, x3 in product(range(2), repeat=3):
    value = (x1 + x2 + x3 + x1 * x2 + x2 * x3 + x3 * x1 + x1 * x2 * x3) % 2
    print(f'p({x1},{x2},{x3})={value}')

p(0,0,0)=0
p(0,0,1)=1
p(0,1,0)=1
p(0,1,1)=1
p(1,0,0)=1
p(1,0,1)=1
p(1,1,0)=1
p(1,1,1)=1