Definition 39 In the context of $p$-biased Fourier analysis we define the basis function $\phi : \{-1,1\} \to {\mathbb R}$ by \[ \phi(x_i) = \frac{x_i - \mu}{\sigma}, \] where \[ \mu = \mathop{\bf E}_{{\boldsymbol{x}}_i \sim \pi_p}[{\boldsymbol{x}}_i] = q-p = 1- 2p, \quad \sigma = \mathop{\bf stddev}_{{\boldsymbol{x}}_i \sim \pi_p}[{\boldsymbol{x}}_i] = \sqrt{4pq} = 2\sqrt{p}\sqrt{1-p}. \] Note that $\sigma^2 = 1 – \mu^2$. We also have the formula $\phi(1) = \sqrt{p/q}$, $\phi(-1) = -\sqrt{q/p}$.

We will use the notation $\mu$ and $\sigma$ throughout this section. It’s clear that $\{1, \phi\}$ is indeed a Fourier basis for $L^2(\{-1,1\}, \pi_p)$ because $\mathop{\bf E}[\phi({\boldsymbol{x}}_i)] = 0$ and $\mathop{\bf E}[\phi({\boldsymbol{x}}_i)^2] = 1$ by design.

Definition 40 In the context of $L^2(\{-1,1\}^n, \pi_p^{\otimes n})$ we define the product Fourier basis functions $(\phi_S)_{S \subseteq [n]}$ by \[ \phi_S(x) = \prod_{i \in S} \phi(x_i). \] Given $f \in L^2(\{-1,1\}^n, \pi_p^{\otimes n})$ we write $\widehat{f}(S)$ for the associated Fourier coefficient; i.e., \[ \widehat{f}(S) = \mathop{\bf E}_{{\boldsymbol{x}} \sim \pi_p^{\otimes n}}[f({\boldsymbol{x}})\,\phi_S({\boldsymbol{x}})]. \] Thus we have the biased Fourier expansion \[ f(x) = \sum_{S \subseteq [n]} \widehat{f}(S)\,\phi_S(x). \]

Although the notation is very similar to that of the classic uniform-distribution Fourier analysis, we caution that in general, \[ \phi_S \phi_T \neq \phi_{S \triangle T}. \]

Example 41 Let $\chi_i \in L^2(\{-1,1\}^n, \pi_p^{\otimes n})$ be the $i$th dictator function, $\chi_i(x) = x_i$, viewed under the $p$-biased distribution. We have \[ \phi(x_i) = \frac{x_i - \mu}{\sigma} \quad\Rightarrow\quad x_i = \mu + \sigma\phi(x_i), \] and the latter is evidently $f$’s (biased) Fourier expansion. I.e., \[ \widehat{\chi_i}(\emptyset) = \mu, \quad \widehat{\chi_i}(\{i\}) = \sigma, \quad \widehat{\chi_i}(S) = 0 \text{ otherwise}. \]

This example lets us see a link between a function’s “usual” Fourier expansion and its biased Fourier expansion. (For more on this, see the exercises.) Let’s abuse notation a little by writing simply $\phi_i$ instead of $\phi(x_i)$. We have the formulas \begin{equation} \label{eqn:p-biased-substitution} \phi_i = \frac{x_i – \mu}{\sigma} \quad\Leftrightarrow\quad x_i = \mu + \sigma \phi_i, \end{equation} and we can go from the usual Fourier expansion to the biased Fourier expansion simply by plugging in the latter.

Example 42 Recall the “selection function” $\mathrm{Sel} : \{-1,1\}^3 \to \{-1,1\}$ from Exercise 1.1(j); $\mathrm{Sel}(x_1, x_2, x_2)$ outputs $x_2$ if $x_1 = -1$ and outputs $x_3$ if $x_1 = 1$. The usual Fourier expansion of $\mathrm{Sel}$ is \[ \mathrm{Sel}(x_1, x_2, x_3) = \tfrac{1}{2} x_2 + \tfrac{1}{2} x_3 -\tfrac{1}{2} x_1 x_2 + \tfrac{1}{2} x_1 x_3. \] Using the substitution from \eqref{eqn:p-biased-substitution} we get \begin{align} \mathrm{Sel}(x_1, x_2, x_3) &= \tfrac{1}{2} (\mu + \sigma \phi_2) + \tfrac{1}{2} (\mu + \sigma \phi_3) -\tfrac{1}{2} (\mu + \sigma \phi_1) (\mu + \sigma \phi_2) + \tfrac{1}{2} (\mu + \sigma \phi_1) (\mu + \sigma \phi_3) \nonumber\\ &= \mu + (\tfrac{1}{2} – \tfrac{1}{2} \mu)\sigma \, \phi_{2} + (\tfrac{1}{2} + \tfrac{1}{2} \mu) \sigma \, \phi_{3} – \tfrac{1}{2} \sigma^2 \, \phi_1 \phi_2 + \tfrac{1}{2} \sigma^2 \, \phi_1 \phi_3. \label{eqn:sel-biased} \end{align} Thus if we write $\mathrm{Sel}^{(p)}$ for the selection function thought of as an element of $L^2(\{-1,1\}^3, \pi_p^{\otimes 3})$, we have \begin{gather*} \widehat{\mathrm{Sel}^{(p)}}(\emptyset) = \mu, \quad \widehat{\mathrm{Sel}^{(p)}}(2) = (\tfrac{1}{2} – \tfrac{1}{2} \mu)\sigma, \quad \widehat{\mathrm{Sel}^{(p)}}(3) = (\tfrac{1}{2} + \tfrac{1}{2} \mu)\sigma, \\ \widehat{\mathrm{Sel}^{(p)}}(\{1,2\}) = -\tfrac{1}{2}\sigma^2, \quad \widehat{\mathrm{Sel}^{(p)}}(\{1,3\}) = \tfrac{1}{2}\sigma^2, \quad \widehat{\mathrm{Sel}^{(p)}}(S) = 0 \text{ else}. \end{gather*} By the Fourier formulas of Section 2 we can deduce, e.g., that $\mathop{\bf E}[\mathrm{Sel}^{(p)}] = \mu$, $\mathbf{Inf}_1[\mathrm{Sel}^{(p)}] = (-\tfrac{1}{2} \sigma^2)^2 + (\tfrac{1}{2} \sigma^2)^2 = \tfrac{1}{2} \sigma^4$, etc.

Let’s codify a piece of notation from this example:

Notation 43 Let $f : \{-1,1\}^n \to {\mathbb R}$ and let $p \in (0,1)$. We write $f^{(p)}$ for the function when viewed as an element of $L^2(\{-1,1\}^n, \pi_{p}^{\otimes n})$.

We now discuss derivative operators. We would like to define an operator $\mathrm{D}_i$ on $L^2(\{-1,1\}^n, \pi_p^{\otimes n})$ which acts like differentiation on the biased Fourier expansion. E.g., referring to \eqref{eqn:sel-biased} we would like to have \[ \mathrm{D}_3 \mathrm{Sel}^{(p)} = (\tfrac{1}{2} + \tfrac{1}{2} \mu) \sigma + \tfrac{1}{2} \sigma^2 \, \phi_1. \] In general we are seeking $\frac{\partial}{\partial \phi_i}$ which, by basic calculus and the relationship \eqref{eqn:p-biased-substitution}, satisfies \[ \frac{\partial}{\partial \phi_i} = \frac{\partial x_i}{\partial \phi_i} \cdot \frac{\partial}{\partial x_i} = \sigma \cdot \frac{\partial}{\partial x_i}. \] Recognizing $\frac{\partial}{\partial x_i}$ as the “usual” $i$th derivative operator, we are led to the following:

Definition 44 For $i \in [n]$, the $i$th (discrete) derivative operator $\mathrm{D}_i$ on $L^2(\{-1,1\}^n, \pi_p^{\otimes n})$ is defined by \[ \mathrm{D}_i f(x) = \sigma \cdot \frac{f(x^{(i\mapsto 1)}) - f(x^{(i \mapsto -1)})}{2}. \] Note that this defines a different operator for each value of $p$. We sometimes write the above definition as \[ \mathrm{D}_{\phi_i} = \sigma \cdot \mathrm{D}_{x_i}. \] With respect to the biased Fourier expansion of $f \in L^2(\{-1,1\}^n, \pi_p^{\otimes n})$ the operator $\mathrm{D}_i$ satisfies \begin{equation} \label{eqn:p-biased-deriv} \mathrm{D}_i f = \sum_{S \ni i} \widehat{f}(S)\,\phi_{S \setminus \{i\}}. \end{equation}

Given this definition we can derive some addition formulas for influences, including a generalization of Proposition 2.20:

Proposition 45 Suppose $f \in L^2(\{-1,1\}^n, \pi_p^{\otimes n})$ is boolean-valued (i.e., has range $\{-1,1\}$). Then \[ \mathbf{Inf}_i[f] = \sigma^2 \mathop{\bf Pr}_{{\boldsymbol{x}} \sim \pi_p^{\otimes n}}[f({\boldsymbol{x}}) \neq f({\boldsymbol{x}}^{\oplus i})] \] for each $i \in [n]$. If furthermore $f$ is monotone then $\mathbf{Inf}_i[f] = \sigma \widehat{f}(i)$.

Proof: Using Definition 44‘s notation and \eqref{eqn:p-biased-deriv} we have \[ \mathbf{Inf}_i[f] = \mathop{\bf E}_{\pi_p}[(\mathrm{D}_{\phi_i} f)^2] = \sigma^2 \mathop{\bf E}_{\pi_p}[(\mathrm{D}_{x_i} f)^2]. \] Since $(\mathrm{D}_{x_i} f)^2$ is the $0$-$1$ indicator that $i$ is pivotal for $f$, the first formula follows. When $f$ is monotone we furthermore have that $(\mathrm{D}_{x_i} f)^2 = \mathrm{D}_{x_i} f$ and hence \[ \mathbf{Inf}_i[f] = \sigma^2 \mathop{\bf E}_{\pi_p}[\mathrm{D}_{x_i} f] = \sigma \mathop{\bf E}_{\pi_p}[\mathrm{D}_{\phi_i} f] = \sigma \widehat{f}(i), \] as claimed. $\Box$

The remainder of this section is devoted to the topic of threshold phenomena in boolean functions. Much of the motivation for this comes from theory of random graphs, which we now briefly introduce.

Definition 46 Given an undirected graph $G$ on $v \geq 2$ vertices, we identify it with the string in $\{\mathsf{True}, \mathsf{False}\}^{\binom{v}{2}}$ which indicates which edges are present ($\mathsf{True}$) and which are absent ($\mathsf{False}$). We write $\mathcal{G}(v,p)$ for the distribution $\pi_{p}^{\otimes \binom{v}{2}}$; this is called the Erdős–Rényi random graph model. Note that if we permute the $v$ vertices of a graph, this induces a permutation on the $\binom{v}{2}$ edges. A ($v$-vertex) graph property is a boolean function $f : \{\mathsf{True}, \mathsf{False}\}^{\binom{v}{2}} \to \{\mathsf{True}, \mathsf{False}\}$ which is invariant under all $v!$ such permutations of its input; colloquially, this means that $f$ “does not depend on the names of the vertices”.

Graph properties are always transitive-symmetric functions in the sense of Definition 2.10.

Examples 47 The following are all $v$-vertex graph properties: \begin{align*} \text{Conn}(G) &= \mathsf{True} \text{ if $G$ is connected;} \\ \text{3Col}(G) &= \mathsf{True} \text{ if $G$ is $3$-colourable;} \\ \text{Clique}_{k}(G) &= \mathsf{True} \text{ if $G$ is contains a clique on at least $k$ vertices;} \\ \mathrm{Maj}_{n}(G) &= \mathsf{True} \textstyle \text{ (assuming $n = \binom{v}{2}$ is odd) if $G$ has at least $\binom{v}{2}/2$ edges;} \\ \chi_{[n]}(G) &= \mathsf{True} \text{ if $G$ has an odd number of edges.} \\ \end{align*} Note that each of these actually defines a family of boolean functions, one for each value of $v$; this is the typical situation in the study of graph properties. An example of a function $f : \{\mathsf{True},\mathsf{False}\}^{\binom{v}{2}} \to \{\mathsf{True}, \mathsf{False}\}$ which is not a graph property is the one defined by $f(G) = \mathsf{True}$ if vertex #$1$ has at least one neighbour; this $f$ is not invariant under permuting the vertices.

Graph properties which are monotone are particularly nice to study; these are the ones for which adding edges can never make the property go from $\mathsf{True}$ to $\mathsf{False}$. The properties $\text{Conn}$, $\text{Clique}_{k}$, and $\mathrm{Maj}_n$ defined above are all monotone, as is $\neg\text{3Col}$. Take any monotone graph property, say $\text{Conn}$; a typical question in random graph theory would be, “how many edges does a graph need to have before it is likely to be connected?” Or more precisely, how does $\mathop{\bf Pr}_{\boldsymbol{G} \sim \mathcal{G}(v,p)}[\text{Conn}(\boldsymbol{G}) = \mathsf{True}]$ vary as $p$ increases from $0$ to $1$?

There’s no need to ask this question just for graph properties. Given any monotone boolean function $f : \{\mathsf{True},\mathsf{False}\}^n \to \{\mathsf{True}, \mathsf{False}\}$ it is intuitively clear that when $p$ increases from $0$ to $1$ this causes $\mathop{\bf Pr}_{\pi_p} [f({\boldsymbol{x}}) = \mathsf{True}]$ to increase from $0$ to $1$ (unless $f$ is a constant function). As illustration, we show a plot of $\mathop{\bf Pr}_{\pi_p} [f({\boldsymbol{x}}) = \mathsf{True}]$ versus $p$ for the dictator function, $\mathrm{AND}_2$, and $\mathrm{Maj}_{101}$.

Plot of Pr_{π_p}(f(x) = True) versus p for f a dictator (dotted), f = AND_2 (dashed), and f =Maj_{101} (solid)

The Margulis–Russo Formula quantifies the rate at which $\mathop{\bf Pr}_{\pi_p} [f({\boldsymbol{x}}) = \mathsf{True}]$ increases with $p$; specifically, it relates the slope of the curve at $p$ to the total influence of $f$ under $\pi_p^{\otimes n}$. To prove the formula we switch to $\pm 1$ notation.

Margulis–Russo Formula Let $f : \{-1,1\}^n \to {\mathbb R}$. Recalling Notation 43 and the relation $\mu = 1-2p$, we have \begin{equation} \label{eqn:marg-russo1} \frac{d}{d\mu}\mathop{\bf E}[f^{(p)}] = \frac{1}{\sigma} \cdot \sum_{i=1}^n \widehat{f^{(p)}}(i). \end{equation} In particular, if $f : \{-1,1\}^n \to \{-1,1\}$ is monotone then \begin{equation} \label{eqn:marg-russo2} \frac{d}{dp}\,\mathop{\bf Pr}_{{\boldsymbol{x}} \sim \pi_p^{\otimes n}}[f({\boldsymbol{x}}) = -1] = \frac{d}{d\mu}\mathop{\bf E}[f^{(p)}] = \frac{1}{\sigma^2} \cdot \mathbf{I}[f^{(p)}]. \end{equation}

Proof: Treating $f$ as a multilinear polynomial over $x_1, \dots, x_n$ we have \[ \mathop{\bf E}[f^{(p)}] = \mathrm{T}_\mu f(1, \dots, 1) = f(\mu, \dots, \mu) \] (this also follows from Exercise 1.5). By basic calculus, \[ \frac{d}{d\mu}f(\mu, \dots, \mu) = \sum_{i=1}^n \mathrm{D}_{x_i} f(\mu, \dots, \mu). \] But \[ \mathrm{D}_{x_i} f(\mu, \dots, \mu) = \mathop{\bf E}[\mathrm{D}_{x_i} f^{(p)}] = \frac{1}{\sigma} \mathop{\bf E}[\mathrm{D}_{\phi_i} f^{(p)}] = \frac{1}{\sigma} \widehat{f^{(p)}}(i), \] completing the proof of \eqref{eqn:marg-russo1}. As for \eqref{eqn:marg-russo2}, the second equality follows immediately from Proposition 45. The first equality holds because $\mu = 1-2p$ and $\mathop{\bf E}[f] = 1-2\mathop{\bf Pr}[f = -1]$; the two factors of $-2$ cancel. $\Box$

Looking again at the figure we see that the plot for $\mathrm{Maj}_{101}$ looks very much like a step function, jumping from nearly $0$ to nearly $1$ around the critical value $p = 1/2$. For $\mathrm{Maj}_n$, this “sharp threshold at $p = 1/2$” becomes more and more pronounced as $n$ increases. This is clearly suggested by the Margulis–Russo Formula: the derivative of the curve at $p = 1/2$ is equal to $\mathbf{I}[\mathrm{Maj}_n]$ (the usual, uniform-distribution total influence), which has the very large value $\Theta(\sqrt{n})$ (Theorem 2.32). Such sharp thresholds exist for many boolean functions; we give some examples:

Examples 48 In the exercises you are asked to show that for every $\epsilon > 0$ there is a $C$ such that \[ \mathop{\bf Pr}_{\pi_{1/2 - C/\sqrt{n}}}[\mathrm{Maj}_n = \mathsf{True}] \leq \epsilon, \quad \mathop{\bf Pr}_{\pi_{1/2 + C/\sqrt{n}}}[\mathrm{Maj}_n = \mathsf{True}] \geq 1 – \epsilon. \] Regarding the Erdős–Rényi graph model, the following facts are known: \begin{align*} \mathop{\bf Pr}_{\boldsymbol{G} \sim \mathcal{G}(v,p)}[\text{Clique}_{\log v}(\boldsymbol{G}) = \mathsf{True}] &\xrightarrow[v \to \infty]{} \begin{cases} 0 & \text{if } p < 1/4, \\ 1 & \text{if } p > 1/4. \end{cases} \\ \mathop{\bf Pr}_{\boldsymbol{G} \sim \mathcal{G}(v,p)}[\text{Conn}(\boldsymbol{G}) = \mathsf{True}] &\xrightarrow[v \to \infty]{} \begin{cases} 0 & \text{if } p < \frac{\ln v}{v}(1-\tfrac{\log \log v}{\log v}), \\ 1 & \text{if } p > \frac{\ln v}{v}(1+\tfrac{\log \log v}{\log v}). \end{cases} \\ \end{align*}

In the above examples you can see that the “jump” occurs at various values of $p$. To investigate this phenomenon, we first single out the value for which $\mathop{\bf Pr}_{\pi_p}[f({\boldsymbol{x}}) = \mathsf{True}] = 1/2$:

Definition 49 Let $f : \{\mathsf{True},\mathsf{False}\}^n \to \{\mathsf{True}, \mathsf{False}\}$ be monotone and nonconstant. The critical probability for $f$, denoted $p_c$, is the unique value in $(0,1)$ for which $\mathop{\bf Pr}_{{\boldsymbol{x}} \sim \pi_p^{\otimes n}}[f({\boldsymbol{x}}) = \mathsf{True}] = 1/2$. We also write $q_c = 1-p_c$, $\mu_c = q_c – p_c = 1-2p_c$, and $\sigma = \sqrt{4p_cq_c}$.

In the exercises you are asked to verify that $p_c$ is well defined.

Now suppose that $\Delta$ is the derivative of $\mathop{\bf Pr}_{\pi_p}[f({\boldsymbol{x}}) = \mathsf{True}]$ at $p = p_c$. Roughly speaking, we would expect $\mathop{\bf Pr}_{\pi_p}[f({\boldsymbol{x}}) = \mathsf{True}]$ to jump from near $0$ to near $1$ in an interval of around $p_c$ of width about $1/\Delta$. Thus a “sharp threshold” should roughly correspond to the case that $1/\Delta$ is small, even compared to $\min(p_c, q_c)$. The Margulis–Russo Formula says that $\Delta = \frac{1}{\sigma_c^2} \mathbf{I}[f^{(p_c)}]$, and since $\min(p_c,q_c)$ is proportional to $4p_cq_c = \sigma_c^2$ it follows that $1/\Delta$ is “small” compared to $\min(p_c,q_c)$ if and only if $\mathbf{I}[f^{(p_c)}]$ is “large”. Thus we have a neat criterion:

Sharp threshold principle: Let $f : \{\mathsf{True}, \mathsf{False}\}^n \to \{\mathsf{True}, \mathsf{False}\}$ be monotone. Then, roughly speaking, $\mathop{\bf Pr}_{\pi_p}[f({\boldsymbol{x}}) = \mathsf{True}]$ has a “sharp threshold” if and only if $f$ has “large” (“superconstant”) total influence under its critical probability distribution.

Of course this should all be made a bit more precise; see the exercises for details. In light of this principle, we can prove that a given $f$ has a sharp threshold by proving that $\mathbf{I}[f^{(p_c)}]$ is not “small”. This strongly motivates the problem of “characterizing” functions $f \in L^2(\{-1,1\}^n, \pi_p^{\otimes n})$ for which $\mathbf{I}[f]$ is small. Friedgut’s Junta Theorem, mentioned at the end of Section 3.1 and proved in a later chapter, tells us that in the uniform distribution case $p = 1/2$, the only way $\mathbf{I}[f]$ can be small is if $f$ is close to a junta. In particular, any monotone graph property with $p_c = 1/2$ must have a sharp threshold: since it is transitive-symmetric, all $n$ coordinates are equally influential and it can’t be close to a junta. These results also hold so long as $p$ is bounded away from $0$ and $1$, as we will show in Chapter 9. However many interesting monotone graph properties have $p_c$ very close to $0$: e.g. connectivity, as we saw in Examples 48. Characterizing the functions $f \in L^2(\{-1,1\}^n, \pi_p^{\otimes n})$ with small $\mathbf{I}[f]$ when $p = o_n(1)$ is a trickier task; see the work of Friedgut, Bourgain, and Hatami described in Chapter 10.

To make this more precise, let’s start with the familiar case of $f : \{-1,1\}^n \to {\mathbb R}$. Here it is possible to define the functions $f^{=S} : \{-1,1\}^n \to {\mathbb R}$ simply by $f^{=S} = \widehat{f}(S)\,\chi_S$. (Later we will give an equivalent definition which doesn’t involve the Fourier basis.) This definition satisfies \eqref{eqn:pm1-orthog-decomp} as well as the following two properties:

1. $f^{=S}$ depends only on the coordinates in $S$.
2. If $T \subsetneq S$ and $g$ is a function depending only on the coordinates in $T$, then $\langle f^{=S}, g \rangle = 0$.

These properties describe what we mean precisely when we say that $f^{=S}$ is the “contribution to $f$ coming from coordinates $S$ (but not from any subset of $S$)”. Furthermore, the decomposition \eqref{eqn:pm1-orthog-decomp} is orthogonal, meaning $\langle f^{=S}, f^{=T} \rangle = 0$ whenever $S \neq T$.

To make this definition basis-free, recall the “projection of $f$ onto coordinates $J$”, $f^{\subseteq J}$ Definition 17. You can think of $f^{\subseteq J}$ as the “contribution to $f$ coming from coordinates $J$ (collectively)”. It has a probabilistic definition not depending on any basis, and with the definition $f^{=S} = \widehat{f}(S)\,\chi_S$ we have from Proposition 19 that \begin{equation} \label{eqn:orthog-invert-me} f^{\subseteq J} = \sum_{S \subseteq J} f^{=S}. \end{equation} It is precisely by inverting \eqref{eqn:orthog-invert-me} that we can give a basis-free definition of the functions $f^{=S}$.

Let’s do this inversion for a general $f \in L^2(\Omega^n, \pi^{\otimes n})$. The projection functions $f^{\subseteq J} \in L^2(\Omega^n, \pi^{\otimes n})$ can be defined as in Definition 17. If we want \eqref{eqn:orthog-invert-me} to hold for $J = \emptyset$ then we should define \[ f^{=\emptyset} = f^{\subseteq \emptyset} \] (which is the constant function equal to $\mathop{\bf E}[f]$). Given this, if we want \eqref{eqn:orthog-invert-me} to hold for singleton sets $J = \{j\}$ then we need \[ f^{\subseteq \{j\}} = f^{=\emptyset} + f^{=\{j\}} \quad\Leftrightarrow\quad f^{=\{j\}} = f^{\subseteq \{j\}} - f^{\subseteq \emptyset}. \] In other words, \[ f^{= \{j\}}(x) = \mathop{\bf E}_{{\boldsymbol{x}} \sim \pi^{\otimes n}} [f \mid {\boldsymbol{x}}_j = x_j] – \mathop{\bf E}_{{\boldsymbol{x}} \sim \pi^{\otimes n}} [f({\boldsymbol{x}})]. \] Notice this function only depends on the input value $x_j$; it measures the change in expectation of $f$ if you know the value $x_j$. Moving on to sets of cardinality $2$, if we want \eqref{eqn:orthog-invert-me} to hold for $J = \{i,j\}$ then we need \begin{align*} f^{\subseteq \{i,j\}} &= f^{=\emptyset} + f^{=\{i\}} + f^{=\{j\}} + f^{=\{i,j\}} \\ &= f^{\subseteq \emptyset} + (f^{\subseteq \{i\}} – f^{\subseteq \emptyset}) + (f^{\subseteq \{j\}} – f^{\subseteq \emptyset}) + f^{=\{i,j\}} \end{align*} and hence \[ f^{=\{i,j\}} = f^{\subseteq \{i,j\}} - f^{\subseteq \{i\}} - f^{\subseteq \{j\}} + f^{\subseteq \emptyset}. \] It’s clear that we can continue this and define all the functions $f^{=S}$ by the principle of inclusion-exclusion. To show this definition leads to an orthogonal decomposition we will need the following lemma:

Lemma 34 Let $f, g \in L^2(\Omega^n, \pi^{\otimes n})$. Assume that $f$ does not depend on any coordinate outside $I \subseteq [n]$, and $g$ does not depend on any coordinate outside $J \subseteq [n]$. Then $\langle f, g \rangle = \langle f^{\subseteq I \cap J}, g^{\subseteq I \cap J} \rangle$.

Proof: We may assume without loss of generality that $I \cup J = [n]$. Given any $x \in \Omega^n$ we can break it into the parts $(x_{I \cap J}, x_{I \setminus J}, x_{J \setminus I})$. We then have \begin{align*} \langle f, g\rangle = \mathop{\bf E}_{{\boldsymbol{x}}_{I \cap J}, {\boldsymbol{x}}_{I \setminus J}, {\boldsymbol{x}}_{J \setminus I}}[f({\boldsymbol{x}}_{I \cap J}, {\boldsymbol{x}}_{I \setminus J}) \cdot g({\boldsymbol{x}}_{I \cap J}, {\boldsymbol{x}}_{J \setminus I})], \end{align*} where we have abused notation slightly by writing $f$ and $g$ as functions just of the coordinates on which they actually depend. Since ${\boldsymbol{x}}_{I \setminus J}$ and ${\boldsymbol{x}}_{J \setminus I}$ are independent, the above equals \[ \mathop{\bf E}_{{\boldsymbol{x}}_{I \cap J}}\left[\mathop{\bf E}_{{\boldsymbol{x}}_{I \setminus J}}[f({\boldsymbol{x}}_{I \cap J}, {\boldsymbol{x}}_{I \setminus J})] \cdot \mathop{\bf E}_{{\boldsymbol{x}}_{J \setminus I}}[g({\boldsymbol{x}}_{I \cap J}, {\boldsymbol{x}}_{J \setminus I})] \right]. \] But now $\mathop{\bf E}_{{\boldsymbol{x}}_{I \setminus J}}[f({\boldsymbol{x}}_{I \cap J}, {\boldsymbol{x}}_{I \setminus J})]$ is nothing more than $f^{\subseteq I \cap J}({\boldsymbol{x}}_{I \cap J})$, and similarly $\mathop{\bf E}_{{\boldsymbol{x}}_{J \setminus I}}[g({\boldsymbol{x}}_{I \cap J}, {\boldsymbol{x}}_{J \setminus I})] = g^{\subseteq I \cap J}({\boldsymbol{x}}_{I \cap J})$. Thus the above equals \[ \mathop{\bf E}_{{\boldsymbol{x}}_{I \cap J}}[f^{\subseteq I \cap J}({\boldsymbol{x}}_{I \cap J}) \cdot g^{\subseteq I \cap J}({\boldsymbol{x}}_{I \cap J})] = \langle f^{\subseteq I \cap J}, g^{\subseteq I \cap J} \rangle. \qquad \Box\]

We can now give the main theorem on orthogonal decomposition:

Theorem 35 Let $f \in L^2(\Omega^n, \pi^{\otimes n})$. Then $f$ has a unique decomposition as \[ f = \sum_{S \subseteq [n]} f^{=S} \] where the functions $f^{=S} \in L^2(\Omega^n, \pi^{\otimes n})$ satisfy the following:

1. $f^{=S}$ depends only on the coordinates in $S$.
2. If $T \subsetneq S$ and $g \in L^2(\Omega^n, \pi^{\otimes n})$ depends only on the coordinates in $T$ then $\langle f^{=S}, g \rangle = 0$.

This decomposition has the following additional properties:

3. Condition (ii) additionally holds whenever $S \not \subseteq T$.
4. The decomposition is orthogonal: $\langle f^{=S}, f^{=T} \rangle = 0$ for $S \neq T$.
5. $\sum_{S \subseteq T} f^{=S} = f^{\subseteq T}$.
6. For each $S \subseteq [n]$, the mapping $f \mapsto f^{=S}$ is a linear operator.

Proof: We first show the existence of a decomposition satisfying (i)–(vi). We then show uniqueness for decompositions satisfying (i) and (ii). As suggested above, for each $S \subseteq [n]$ we define \[ f^{=S} = \sum_{J \subseteq S} (-1)^{|S| - |J|} f^{\subseteq J}, \] where the functions $f^{\subseteq J} \in L^2(\Omega^n, \pi^{\otimes n})$ are as in Definition 17. Since each $f^{\subseteq J}$ depends only on the coordinates in $J$, condition (i) certainly holds. It is also immediate that condition (v) holds by inclusion-exclusion; you are asked to prove this explicitly in the exercises. Condition (vi) also follows because each $f \mapsto f^{\subseteq J}$ is a linear operator, as discussed after Definition 17.

We now verify (ii). Assume $T \subsetneq S$ and that $g \in L^2(\Omega^n, \pi^{\otimes n})$ only depends on the coordinates in $T$. We have \begin{equation} \label{eqn:pair-me} \langle f^{=S}, g \rangle = \sum_{J \subseteq S} (-1)^{|S| – |J|} \langle f^{\subseteq J}, g \rangle. \end{equation} Take any $i \in S \setminus T$ and pair up the summands in \eqref{eqn:pair-me} as $J’$, $J”$, where $J’ \not \ni i$ and $J” = J’ \cup \{i\}$. By Lemma 34 we have \[ \langle f^{\subseteq J''}, g \rangle = \langle f^{\subseteq J'' \cap T}, g^{\subseteq T} \rangle = \langle f^{\subseteq J' \cap T}, g^{\subseteq T} \rangle, \] the latter equality using $i \not \in T$. But the signs $(-1)^{|S| – |J’|}$ and $(-1)^{|S| – |J”|}$ are opposite, so the summands in \eqref{eqn:pair-me} cancel in pairs. This shows the sum is $0$, confirming (ii).

We complete the existence proof by noting that (ii) $\Rightarrow$ (iii) $\Rightarrow$ (iv) (assuming (i)). The first implication is because $\langle f^{=S}, g \rangle = \langle f^{= S}, g^{\subseteq S \cap T} \rangle$ when $g$ depends only on the coordinates in $T$ (Lemma 34), and $S \cap T \subsetneq S$ when $S \not \subseteq T$. The second implication is because $S \neq T$ implies either $S \not \subseteq T$ or $T \not \subseteq S$.

It remains to prove the uniqueness statement. Suppose $f$ has two representations satisfying (i) and (ii). By subtracting them we get a decomposition of the $0$ function that satisfies (i) and (ii); our goal is to show that each function in this decomposition is the $0$ function. We can do this by showing that any decomposition satisfying (i) and (ii) also satisfies “Parseval’s Theorem”: $\langle f, f \rangle = \sum_{S \subseteq [n]} \|f^{=S}\|_2^2$. But this is an easy consequence of (iv), which we just noted is itself a consequence of (i) and (ii). $\Box$

We can connect the orthogonal decomposition of $f$ to its expansion under Fourier bases as follows:

Proposition 36 Let $f \in L^2(\Omega^n, \pi^{\otimes n})$ have orthogonal decomposition $f = \sum_{S \subseteq [n]} f^{=S}$. Fix any Fourier basis $\phi_0, \dots, \phi_{m-1}$ for $L^2(\Omega, \pi)$. Then \begin{equation} \label{eqn:orthog-decomp-basis} f^{=S} = \sum_{\substack{\alpha \in {\mathbb N}^n_{< m} \\ \mathrm{supp}(\alpha) = S}} \widehat{f}(\alpha)\,\phi(\alpha). \end{equation}

Proof: This follows easily from the uniqueness part of Theorem 35. If we take \eqref{eqn:orthog-decomp-basis} as the definition of functions $f^{=S}$, it is immediate that $\sum_S f^{=S} = f$ and that $f^{=S}$ depends only on the coordinates in $S$. Further, if $g$ depends only on coordinates $T \subsetneq S$ then $f^{=S}$ and $g$ have disjoint Fourier support by Corollary 20; hence $\langle f^{=S}, g \rangle = 0$ by Plancherel (Proposition 16). $\Box$

Example 37 Let’s compute the orthogonal decomposition of the function $f : \{a,b,c\}^2 \to \{0,1\}$ from Example 15. Recall that in this example $\{a,b,c\}$ has the uniform distribution and $f(x_1,x_2) = 1$ if and only if $x_1 = x_2 = c$. First, \[ f^{=\emptyset} = \mathop{\bf E}[f] = \tfrac{1}{9}. \] Next, for $i = 1,2$ we have that $f^{\subseteq \{i\}}(x)$ is $\frac13$ if $x_i = c$ and $0$ otherwise; hence \[ f^{= \{i\}}(x_1,x_2) = \begin{cases} +\frac{2}{9} & \text{if } x_i = c, \\ -\frac{1}{9} & \text{else.} \end{cases} \] Finally, it’s easiest to compute $f^{=\{1,2\}}$ as $f – f^{=\emptyset} – f^{=\{1\}} – f^{=\{2\}}$; this yields \[ f^{= \{1,2\}}(x_1,x_2) = \begin{cases} +\frac{4}{9} & \text{if } x_1 = x_2 = c, \\ -\frac{2}{9} & \text{if exactly one of } x_1,\ x_2 \text{ is } c, \\ +\frac{1}{9} & \text{if } x_1, x_2 \neq c. \end{cases} \] You can check (exercise) that this is consistent with Proposition 36 and the Fourier expansion from Example 15.

We can write all of the Fourier formulas from Section 2 in terms of the orthogonal decomposition; e.g., \[ \langle f, g \rangle = \sum_{S \subseteq [n]} \langle f^{=S}, g^{=S} \rangle, \quad \mathbf{Inf}_i[f] = \sum_{S \ni i} \|f^{=S}\|_2^2, \quad \mathrm{T}_\rho f = \sum_{S \subseteq [n]} \rho^{|S|} f^{=S}. \] These formulas can be proved either by using the connection from Proposition 36 or by reasoning directly from the defining Theorem 35; see the exercises. The orthogonal decomposition also gives us the natural way of stratifying $f$ by degree: we end this section by generalizing some more definitions from Chapter 1.4:

Definition 38 For $f \in L^2(\Omega^n, \pi^{\otimes n})$ and $k \in {\mathbb N}$ we define the degree $k$ part of $f$ to be $f^{=k} = \sum_{|S| = k} f^{=S}$ and the weight of $f$ at degree $k$ to be $\mathbf{W}^{k}[f] = \|f^{=k}\|_2^2$. We also use notation like $f^{\leq k} = \sum_{|S| \leq k} f^{=S}$ and $\mathbf{W}^{> k}[f] = \sum_{|S| > k} \|f^{=S}\|_2^2$.

In this chapter we focus on the case where all the $\Omega_i$’s are the same, as are the $\pi_i$’s. (This is just to save on notation; it will be clear that everything we do holds in the more general setting.) Important classic cases include functions on the $p$-biased hypercube (Section 4) and functions on abelian groups (Section 5). For the issue of generalizing the range of functions — e.g., studying functions $f : \{0,1,2\}^n \to \{0,1,2\}$ — see the exercises.

Happy holidays……..

The idea of assisting testers by providing proofs grew out of complexity-theoretic research on interactive proofs and PCPs; see the early work Ergun, Kumar, and Rubinfeld [EKR99] and the references therein. The specific definition of PCPPs was introduced independently by Ben-Sasson–Goldreich–Harsha–Sudan–Vadhan [BGH+04] and by Dinur–Reingold [DR04] in 2004. Both of these works obtained the PCPP Theorem, relying on the fact that previous literature essentially already gave PCPP reductions of exponential (or greater) proof length): [BGH+04] observed that Theorem 20 can be obtained from [ALM+98] (their proof is Exercise 18), while [DR04] pointed out that the slightly easier Theorem 19 can be extracted from [BGS98]. The proof we gave for Theorem 16 is inspired by the presentation in [Din07].

The PCP Theorem and its stronger forms (the PCPP Theorem and Theorem 21) have a somewhat remarkable consequence. Suppose a researcher claims to prove a famous mathematical conjecture, say “$\mathsf{P} \neq \mathsf{NP}$”. To ensure maximum confidence in correctness, a journal might request the researcher submit a formalized proof, suitable for a mechanical proof-checking system. If the submitted formalized proof $w$ is a boolean string of length $n$, the proof-checker will be implementable by a circuit $C$ of size $O(n)$. Notice that the string property $\mathcal{C}$ decided by $C$ is nonempty if and only if there exists a (length-$n$) proof of $\mathsf{P} \neq \mathsf{NP}$. Suppose the journal applies Theorem 21 to $C$ and requires the researcher submit the additional proof $\Pi$ of length $n \cdot \mathrm{polylog}(n)$. Now the journal can run a rather amazing testing algorithm which reads just $3$ bits of the submitted proof $(w,\Pi)$. If the researcher’s proof of $\mathsf{P} \neq \mathsf{NP}$ is correct then the test will accept with probability $1$. On the other hand, if the test accepts with probability at least $1-\gamma$ (where $\gamma$ is the rejection rate in Theorem 21) then $w$ must be $1$-close to the set of strings accepted by $C$. This doesn’t necessarily mean that $w$ is a correct proof of $\mathsf{P} \neq \mathsf{NP}$ — but it does mean that $\mathcal{C}$ is nonempty and hence a correct proof of $\mathsf{P} \neq \mathsf{NP}$ exists! By querying a larger constant number of bits from $(w,\Pi)$ as in Exercise 1, say $\lceil 30/\gamma\rceil$ bits, the journal can become $99.99$% convinced that indeed $\mathsf{P} \neq \mathsf{NP}$.

CSPs are very widely studied in computer science; it is impossible to survey the topic here. In the case of boolean CSPs the monographs [CKS01,KSTW01] contain useful background regarding complexity theory and approximation algorithms. The notion of approximation algorithms and the derandomized $(\frac78,1)$-approximation algorithm for Max-E$3$-Sat (Proposition 37, Exercise 21) are due to Johnson [Joh74]. Incidentally, there is also an efficient $(\frac78,1)$-approximation algorithm for Max-$3$-Sat [KZ97] but both the algorithm and its analysis are extremely difficult, the latter requiring computer assistance [Zwi02]. Håstad’s hardness theorems are from [Has01], building on [Has96,Has99]. That paper also proves $\mathsf{NP}$-hardness of $(\frac1p + \delta, 1-\delta)$-approximating Max-E$3$-Lin(mod $p$) (for $p$ prime) and of $(\frac78, 1)$-approximating Max-$\mathrm{CSP}(\{\mathrm{NAE}_4\})$, both of which are optimal. Using tools from [TSSW00], Håstad\xspace also showed $\mathsf{NP}$-hardness of $(\frac{11}{16} + \delta, \frac34)$-approximating Max-Cut which is still the best known such result. The best known inapproximability result for Unique-Games($q$) is $\mathsf{NP}$-hardness of $(\frac38 + q^{-\Theta(1)}, \tfrac{1}{2})$-approximation [OW12]. Khot’s influential Unique Games Conjecture was made in [Kho02]; the peculiar name has its origins in a work of Feige and Lov{á}sz [FL92]. The generic Theorem 41, giving UG-hardness from Dictator-vs.-No-Notables tests, essentially appears in [KKMO07]. (We remark that the terminology “Dictator-vs.-No-Notables” is not standard.) If one is willing to assume the Unique Games Conjecture, there is an almost-complete theory of optimal inapproximability due to Raghavendra [Rag09] which will be discussed further in Chapter 14. Many more inapproximability results, with and without the Unique Games Conjecture, are known; for some recent surveys, see [Kho05,Kho10a,Kho10].

As mentioned, Exercise 8 is due to [BGS95,PRS01]. The technique described in Exercise 21 is known as the Method of Conditional Expectations. The trick in Exercise 23 is closely related to the notion of “folding” from the theory of PCPs. The bug described in Exercise 31 is rarely addressed in the literature; the trick used to overcome it appears in, e.g., [ABH+05].