Polynomial

Definition

Let [math]n[/math] and [math]d[/math] be positive integers. Any polynomial of degree [math]d[/math] on [math]n[/math] over the field [math]\mathbb{F}_2[/math] can be viewed as a Boolean function by mapping the identity of [math]\mathbb{F}_2[/math] to 1 and the other element to -1.

Note: The polynomial function is different from the Fourier representation. While every polynomial over [math]\mathbb{F}_2[/math] can be treated as a Boolean function, in the Fourier decomposition the polynomials are taken over [math]\mathbb{R}[/math]; the coefficients are therefore real, and need to be chosen carefully so that the image lies in [math]\{-1,1\}[/math]. Not every real multivariate polynomial is the Fourier decomposition of a Boolean function.

Properties

• TODO