§1.2: The Fourier expansion: functions as multilinear polynomials

The Fourier expansion of a boolean function $f : \{-1,1\}^n \to \{-1,1\}$ is simply its representation as a real, multilinear polynomial. (Multilinear means that no variable $x_i$ appears squared, cubed, etc.) For example, suppose $n = 2$ and $f = {\textstyle \min_2}$, the “minimum” function on $2$ bits:

\begin{align*} {\textstyle \min_2}(+1,+1) &= +1, \\ {\textstyle \min_2}(-1,+1) &= -1, \\ {\textstyle \min_2}(+1,-1) &= -1, \\ {\textstyle \min_2}(-1,-1) &= -1. \end{align*} Then ${\textstyle \min_2}$ can be expressed as a multilinear polynomial, $$\label{eqn:min2-expansion} {\textstyle \min_2}(x_1,x_2) = -\tfrac12 + \tfrac12 x_1 + \tfrac12 x_2 + \tfrac12 x_1 x_2;$$ this is the “Fourier expansion” of ${\textstyle \min_2}$. As another example, consider the majority function on $3$ bits, $\mathrm{Maj}_3 : \{-1,1\}^3 \to \{-1,1\}$, which outputs the $\pm 1$ bit occurring more frequently in its input. Then it’s easy to verify the Fourier expansion $$\label{eqn:maj3-expansion} \mathrm{Maj}_3(x_1,x_2,x_3) = \tfrac{1}{2} x_1 + \tfrac{1}{2} x_2 + \tfrac{1}{2} x_3 – \tfrac{1}{2} x_1x_2x_3.$$ The functions ${\textstyle \min_2}$ and $\mathrm{Maj}_3$ will serve as running examples in this chapter.

Let’s see how to obtain such multilinear polynomial representations in general. Given an arbitrary boolean function $f : \{-1,1\}^n \to \{-1,1\}$ there is a familiar method for finding a polynomial which interpolates the $2^n$ values which $f$ assigns to the points $\{-1,1\}^n \subset {\mathbb R}^n$. For each point $a = (a_1, \dots, a_n) \in \{-1,1\}^n$ the indicator polynomial $1_{\{a\}}(x) = \left(\tfrac{1+a_1x_1}{2}\right)\left(\tfrac{1+a_2x_2}{2}\right) \cdots \left(\tfrac{1+a_nx_n}{2}\right)$ takes value $1$ when $x = a$ and value $0$ when $x \in \{-1,1\}^n \setminus \{a\}$. Thus $f$ has the polynomial representation $f(x) = \sum_{a \in \{-1,1\}^n} f(a) 1_{\{a\}}(x).$ Illustrating with the $f = {\textstyle \min_2}$ example again, we have \begin{align} \qquad\qquad\quad {\textstyle \min_2}(x)\quad=\quad& \left(+1\right) \left(\tfrac{1+x_1}{2}\right)\left(\tfrac{1+x_2}{2}\right)\nonumber\\ \quad+\quad& \left(-1\right) \left(\tfrac{1-x_1}{2}\right)\left(\tfrac{1+x_2}{2}\right) \label{eqn:min2-fourier-computation}\\ \quad+\quad& \left(-1\right) \left(\tfrac{1+x_1}{2}\right)\left(\tfrac{1-x_2}{2}\right)\nonumber\\ \quad+\quad& \left(-1\right) \left(\tfrac{1-x_1}{2}\right)\left(\tfrac{1-x_2}{2}\right)\nonumber \quad=\quad -\tfrac12 + \tfrac12 x_1 + \tfrac12 x_2 + \tfrac12 x_1 x_2. \nonumber \end{align} Let us make two remarks about this interpolation procedure. First, it works equally well in the more general case of real-valued boolean functions, $f : \{-1,1\}^n \to {\mathbb R}$. Second, since the indicator polynomials are multilinear when expanded out, the interpolation always produces a multilinear polynomial. Indeed it makes sense that we can represent functions $f : \{-1,1\}^n \to {\mathbb R}$ with multilinear polynomials: since we only care about inputs $x$ where $x_i = \pm 1$, any factor of $x_i^2$ can be replaced by $1$.

We have illustrated that every $f : \{-1,1\}^n \to {\mathbb R}$ can be represented by a real multilinear polynomial; as we will see in Section 3, this representation is unique. The multilinear polynomial for $f$ may have up to $2^n$ terms, corresponding to the subsets $S \subseteq [n]$. We write the monomial corresponding to $S$ as $x^S = \prod_{i \in S} x_i \tag{with x^\emptyset = 1 by convention}$ and we use the following notation for its coefficient: \begin{equation*} \widehat{f}(S) = \text{coefficient on monomial $x^S$ in the multilinear representation of $f$}. \end{equation*} We summarize this discussion by the Fourier expansion theorem:

Theorem 1 Every function $f : \{-1,1\}^n \to {\mathbb R}$ can be uniquely expressed as a multilinear polynomial, $$\label{eqn:multilinear-expansion} f(x) = \sum_{S \subseteq [n]} \widehat{f}(S)\,x^S.$$ This expression is called the Fourier expansion of $f$, and the real number $\widehat{f}(S)$ is called the Fourier coefficient of $f$ on $S$. Collectively, the coefficients are called the Fourier spectrum of $f$.

As examples, from \eqref{eqn:min2-expansion} and \eqref{eqn:maj3-expansion} we obtain: $\widehat{{\textstyle \min_2}}(\emptyset) = -\tfrac{1}{2}, \quad \widehat{{\textstyle \min_2}}(\{1\}) = \tfrac{1}{2}, \quad \widehat{{\textstyle \min_2}}(\{2\}) = \tfrac{1}{2}, \quad \widehat{{\textstyle \min_2}}(\{1,2\}) = \tfrac{1}{2};$ $\widehat{\mathrm{Maj}_3}(\{1\}),\ \widehat{\mathrm{Maj}_3}(\{2\}),\ \widehat{\mathrm{Maj}_3}(\{3\}) = \tfrac{1}{2}, \quad \widehat{\mathrm{Maj}_3}(\{1,2,3\}) = -\tfrac{1}{2}, \quad \widehat{\mathrm{Maj}_3}(S) = 0 \text{ else.}$

We finish this section with some notation. It is convenient to think of the monomial $x^S$ as a function on $x = (x_1, \dots, x_n) \in {\mathbb R}^n$; we write it as $\chi_S(x) = \prod_{i \in S} x_i.$ Thus we sometimes write the Fourier expansion of $f : \{-1,1\}^n \to {\mathbb R}$ as $f(x) = \sum_{S \subseteq [n]} \widehat{f}(S)\,\chi_S(x).$ So far our notation only makes sense when representing the Hamming cube by $\{-1,1\}^n \subseteq {\mathbb R}^n$. The other frequent representation we will use for the cube is ${\mathbb F}_2^n$. We can define the Fourier expansion for functions $f : {\mathbb F}_2^n \to {\mathbb R}$ by “encoding” input bits $0, 1\in {\mathbb F}_2$ by the real numbers $-1,1 \in {\mathbb R}$. We choose the encoding $\chi : {\mathbb F}_2 \to {\mathbb R}$ defined by $\chi(0_{{\mathbb F}_2}) = +1, \quad \chi(1_{{\mathbb F}_2}) = -1.$ This encoding is not so natural from the perspective of boolean logic; e.g., it means the function $\min_2$ we have discussed represents logical $\mathrm{OR}$. But it’s mathematically natural because for $b \in {\mathbb F}_2$ we have the formula $\chi(b) = (-1)^b$. We now extend the $\chi_S$ notation:

Definition 2 For $S \subseteq [n]$ we define $\chi_S : {\mathbb F}_2^n \to {\mathbb R}$ by $\chi_S(x) = \prod_{i \in S} \chi(x_i) = (-1)^{\sum_{i \in S} x_i},$ which satisfies $$\label{eqn:chi-character} \chi_S(x+y) = \chi_S(x)\chi_S(y).$$

In this way, given any function $f : {\mathbb F}_2^n \to {\mathbb R}$ it makes sense to write its Fourier expansion as \begin{equation*} f(x) = \sum_{S \subseteq [n]} \widehat{f}(S)\,\chi_S(x). \end{equation*}

In fact, if we are really thinking of ${\mathbb F}_2^n$ the $n$-dimensional vector space over ${\mathbb F}_2$, it makes sense to identify subsets $S \subseteq [n]$ with vectors $\gamma \in {\mathbb F}_2^n$. This will be discussed in Chapter 3.

6 comments to §1.2: The Fourier expansion: functions as multilinear polynomials

• Hi Ryan, is there a typo in the definition of the indicator polynomial ? the right hand side has no term involving the variable x at all.

• Fixed, thanks!

• Gil Kalai

Dear Ryan
best luck with this new project –Gil

• It refers to the fact that all the Fourier coefficients other than the preceding ones listed are $0$. Thanks.
Hello, may I ask why $\chi_S(x+y) = \chi(x)\chi(y)$? If we have x = 00101 and y = 01110, then the result is 10011. We let S = {2,3,5}, then $\chi_S(10011) = -1$ and $\chi_S(x) = \chi_S(00101) = 1$ and $\chi_S(y) = \chi_S(01110) = 1$. So $\chi_S(x+y) = -1$ and $\chi_S(x)\chi_S(y) = 1$. They are not equal. Am I missing something?