## Analysis of Boolean Functions

by Ryan O'Donnell

Fall 2012 course at Carnegie Mellon

# §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.

November 4th, 2011 | Tags: Fourier expansion | Category: All chapter sections, Chapter 1: Boolean functions and the Fourier expansion

### 3 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

### Recent comments

• Deepak: Cool! That all makes sense.
• Ryan O'Donnell: Thanks on both!
• Ryan O'Donnell: 1. Fixed, thanks 2. Fixed, thanks 3. For the first two occ...
• Avishay Tal: Two small comments regarding the proof of theorem 16. - In ...
• Deepak: A couple of small things: Ex. 42, under equation (2), \pi...
• Ryan O'Donnell: Correct, thanks!
• Tim Black: I think your $j$ should be an $i$ (or vice-versa) in the sen...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 66, "mathjax_display_tex": 9, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.7660205960273743, "perplexity_flag": "head"}