$$

This note explains how one single trick (which I’m calling Plancherel’s trick) is used to express many properties of a function (2-norm, influence, noise stability, effect of random restrictions) in terms of its Fourier weights. This trick basically is just a manifestation of the pairwise uniformity / orthonormality of parities.

2-norm (aka Parseval’s)

Say we know that some function $f$ is a sum of a few parities: $f(x)=\sum _S\hat{f}(S)x^S$. How can we estimate $\mathrm{E}\left[f^2\right]$ based on those coefficients $\hat{f}(S)$? Well, if there’s only one parity, it’s easy: $f(x)$ would always be $\pm \hat{f}(S)$, so $\mathrm{E}[f^2]=\hat{f}(S{)}^2$.

But what if there’s two ore more parities, e.g. $f(x)=\hat{f}(S)x^S+\hat{f}(T)x^T$? The value would always be $\pm \hat{f}(S)\pm \hat{f}(T)$, but now it’s hard to tell how often those coefficients would “reinforce” vs “cancel” each other.¹ It seems like $\mathrm{E}[f^2]$ could be anywhere between ${(|\hat{f}(S)|-|\hat{f}(T)|)}^2$ and ${(|\hat{f}(S)|+|\hat{f}(T)|)}^2$…

But it turns out that no matter what, the truth of the matter will be smack in the middle! They will reinforce each other as often as they cancel each other out, because they’re pairwise uniform:

$$\begin{array}{rl}\text{(Plancherel's trick)}& \mathrm{E}[f(x{)}^2]& =\mathrm{E}\left[{(\sum _S\hat{f}(S)x^S)}^2\right]& =\sum _{S,T}\hat{f}(S)\hat{f}(T)\mathrm{E}\left[x^S{x}^T\right]\\ \text{(pairwise uniformity)}& & =\sum _{S,T}\hat{f}(S)\hat{f}(T)\mathbb{1}[S=T]& =\sum _S\hat{f}(S{)}^2.\end{array}$$

In words: $\mathrm{E}[f^2]$ inherits the mass of all parities.

Generalizing the trick

In general, the conclusion if that you’re computing the expectation of a product of the form

$$(\sum _S\hat{f}(S)x^S)(\sum _T\hat{g}(T)x^T)$$

then you can just focus on the coefficients where $S=T$ and sum up the products $\hat{f}(S)\hat{g}(S)$ (which is exactly Plancherel’s theorem).

What I’m calling Plancherel’s trick is the move where you express the quantity you care about as an expectation of such a product.

Influence

Suppose that $f(x)=\sum _S\hat{f}(S)x^S$ has $\pm 1$ outputs, then what is the influence of the $i^{\text{th}}$ variable? In order for $i$ to be influencial on some point $x$, we need either $f(x)=-1$ and $f(x^{\oplus i})=+1$, or the opposite. In that context, it seems like each parity $\hat{f}(S)x^S$ such that $i\in S$ independently gets you “$|\hat{f}(S)|$ of the way there”: they contribute either $f(x)=\hat{f}(S)$ and $f(x^{\oplus i})=-\hat{f}(S)$, or vice versa. So, if it were the case that those parities always only reinforce each other, then a reasonable guess would be ${\mathrm{Inf}}_i[f]=\sum _{S\ni i}|\hat{f}(S)|$.

But of course, they sometimes cancel each other out, and it turns out that the correct formula is ${\mathrm{Inf}}_i[f]=\sum _{S\ni i}\hat{f}(S{)}^2$. It means that somehow, even though each $\hat{f}(S)x^S$ individually “gets you $|\hat{f}(S)|$ of the way” towards ${\mathrm{Inf}}_i[f]=1$, when put together they only contribute $\hat{f}(S{)}^2$ to the influence of $i$. This is very odd and unintuitive to me!

The reason is because influence is basically a 2-norm in hiding: because the outputs are in $\{\pm 1\}$, we can express $\mathbb{1}[f(x)\ne f(x^{\oplus i})]$ as ${\left(\frac{f(x)-f(x^{\oplus i})}{2}\right)}^2$. We can simplify this $\frac{f(x)-f(x^{\oplus i})}{2}$ part as

$$\begin{array}{rl}\frac{f(x)-f(x^{\oplus i})}{2}& =\sum _S\hat{f}(S)\frac{x^S-(x^{\oplus i}{)}^S}{2}\\ & =\sum _S\hat{f}(S)x^S\mathbb{1}[(x^{\oplus i}{)}^S\ne x^S]\\ & =\sum _S\hat{f}(S)x^S\mathbb{1}[i\in S]\\ & =\sum _{S\ni i}\hat{f}(S)x^S,\end{array}$$

and therefore get

$$\begin{array}{rl}\text{(Plancherel's trick)}& {\mathrm{Inf}}_i[f]& =\mathrm{E}\left[{\left(\frac{f(x)-f(x^{\oplus i})}{2}\right)}^2\right]& =\mathrm{E}\left[{(\sum _{S\ni i}\hat{f}(S))}^2\right]\\ \text{(Plancherel's theorem)}& & =\sum _{S\ni i}\hat{f}(S{)}^2.\end{array}$$

In words: ${\mathrm{Inf}}_i[f]$ inherits the mass of all parities that include $i$.

Noise stability

The $\rho$-noise stability of $f$ is the correlation between $f(x)$ and $f(y)$ for $y$ is a “corrupted version of $x$”: each $y_i$ is independently drawn to have correlation $\rho$ with $x_i$ (we denote this as $y\sim N_{\rho }(x)$). Intuitively, parities involving more variables are less noise stable, so they should contribute less to the stability. And indeed, if $f(x)=\hat{f}(S)x^S$, then its easy to verify that $\mathrm{Stab}[f]={\rho }^{|S|}\hat{f}(S)$.²

Here, Plancherel’s trick will be to push $y$ inside the expectation:

$${\mathrm{Stab}}_{\rho }[f]=\underset{\begin{array}{c}x\sim {\{\pm 1\}}^n\\ y\sim N_{\rho }(y)\end{array}}{\mathrm{E}}[f(x)f(y)]=\underset{x}{\mathrm{E}}[f(x)\cdot \underset{y\sim N_{\rho }(x)}{\mathrm{E}}[f(y)]].$$

Indeed, ${\mathrm{E}}_{y\sim N_{\rho }(x)}[f(y)]=:{\mathrm{T}}_{\rho }f(x)$ itself is some function of $x$, so if we can express it as a sum of parities, we’re golden. And indeed,

$$\begin{array}{rl}\underset{y\sim N_{\rho }(x)}{\mathrm{E}}[f(y)]& =\underset{y\sim N_{\rho }(x)}{\mathrm{E}}[\sum _S\hat{f}(S)y^S]\\ & =\sum _S\hat{f}(S)\underset{y\sim N_{\rho }(x)}{\mathrm{E}}\left[y^S\right]\\ \text{(by independence)}& & =\sum _S\hat{f}(S){\rho }^{|S|}{x}^S.\end{array}$$

So we get

$$\begin{array}{rl}\text{(Plancherel's trick)}& {\mathrm{Stab}}_{\rho }[f]& =\underset{x}{\mathrm{E}}[f(x)\cdot \underset{y\sim N_{\rho }(x)}{\mathrm{E}}[f(y)]]& =\underset{x}{\mathrm{E}}\left[(\sum _S\hat{f}(S)x^S)(\sum _S\hat{f}(S){\rho }^{|S|}{x}^S)\right]\\ & =\sum _S{\rho }^{|S|}\hat{f}(S{)}^2\end{array}$$

In words: $\mathrm{Stab}[f]$ inherits a ${\rho }^k$ fraction of the mass at degree $k$.

Effect of random restrictions

For some set $J\subseteq [n]$ and string $z\in {\{0,1\}}^{\bar{J}}$, let $f_{J|z}:{\{0,1\}}^J\to \{0,1\}$ denote the restriction of $f$ to $J$ (with the rest fixed to $z$). If $z$ is drawn at random, what should we expect the weight of some set $S\subseteq J$ to be: what is ${\mathrm{E}}_z[\widehat{f_{J|z}}(S{)}^2]$?

First, Plancherel’s trick requires us to express $\widehat{f_{J|z}}(S)$ as a sum of parities in $z$. We have

$$f_{J|z}(y)=\sum _U\hat{f}(U)(y\circ z{)}^U=\sum _{\begin{array}{c}S\subseteq J\\ T\subseteq \bar{J}\end{array}}\hat{f}(S\cup T)y^S{z}^T=\sum _{S\subseteq J}(\sum _{T\subseteq \bar{J}}\hat{f}(S\cup T)z^T)y^S,$$

which shows that $\widehat{f_{J|z}}(S)=\sum _{T\subseteq \bar{J}}\hat{f}(S\cup T)z^T$. Then we only need to plug this in and apply Plancherel’s theorem:

$$\begin{array}{rl}\text{(Plancherel's trick)}& \underset{z}{\mathrm{E}}[\widehat{f_{J|z}}(S{)}^2]& =\underset{z}{\mathrm{E}}\left[{(\sum _{T\subseteq \bar{J}}\hat{f}(S\cup T)z^T)}^2\right]\text{(Plancherel's theorem)}& & =\sum _{T\subseteq \bar{J}}\hat{f}(S\cup T{)}^2& =\sum _{U\cap J=S}\hat{f}(U{)}^2.\end{array}$$

In words: $\widehat{f_{S|z}}(S{)}^2$ inherits (on average) the mass of all parities that are reduced to $S$.

(For the version where $J$ is random too, see Random restrictions vs Fourier.)

1. And as soon as there’s more than $n$ parities involved, it’s clear that we won’t get all possible sign assignments, since there’s only $2^n$ values of $x$. ↩

2. Unlike for influence, the fact that stability is defined as a correlation makes it relatively intuitive from the get-go that the squares of the Fourier coefficients should be involved, rather than their absolute values. On the other hand, if we had looked at noise sensitivity, which is the analogous “purely boolean” notion, we’d run into the same intuition issue. ↩