§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, \begin{equation} \label{eqn:min2-expansion} {\textstyle \min_2}(x_1,x_2) = -\tfrac12 + \tfrac12 x_1 + \tfrac12 x_2 + \tfrac12 x_1 x_2; \end{equation} 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 \begin{equation} \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. \end{equation} 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, \begin{equation} \label{eqn:multilinear-expansion} f(x) = \sum_{S \subseteq [n]} \widehat{f}(S)\,x^S. \end{equation} 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 \begin{equation} \label{eqn:chi-character} \chi_S(x+y) = \chi_S(x)\chi_S(y). \end{equation}

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.

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

Leave a Reply

  

  

  

You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>