§3.1: Low-degree spectral concentration

One way a boolean function’s Fourier spectrum can be “simple” is for it to be mostly concentrated at small degree.

Definition 1 We say that the Fourier spectrum of $f : \{-1,1\}^n \to {\mathbb R}$ is $\epsilon$-concentrated on degree up to $k$ if \[ \mathbf{W}^{>k}[f] = \sum_{\substack{S \subseteq [n] \\|S| > k}} \widehat{f}(S)^2 \leq \epsilon. \] For $f : \{-1,1\}^n \to \{-1,1\}$ we can express this condition using the spectral sample: $\mathop{\bf Pr}_{\boldsymbol{S} \sim \mathscr{S}_{f}}[|\boldsymbol{S}| > k] \leq \epsilon$.

It’s possible to show such a concentration result combinatorially by showing that a function has small total influence:

Proposition 2 For any $f : \{-1,1\}^n \to {\mathbb R}$ and $\epsilon > 0$, the Fourier spectrum of $f$ is $\epsilon$-concentrated on degree up to $\mathbf{I}[f]/\epsilon$.

Proof: This follows immediately from Theorem 2.37, $\mathbf{I}[f] = \sum_{k=0}^n k \cdot \mathbf{W}^{k}[f]$. For $f : \{-1,1\}^n \to \{-1,1\}$, this is Markov’s inequality applied to the cardinality of the spectral sample. $\Box$

For example, in Exercise 2.11 you showed that $\mathbf{I}[\mathrm{Tribes}_{w,2^w}] \leq O(\log n)$, where $n = w2^w$; thus this function’s spectrum is $.01$-concentrated on degree up to $O(\log n)$, a rather low level. Proving this by explicitly calculating Fourier coefficients would be quite painful.

Another means of showing low-degree spectral concentration is through noise stability/sensitivity:

Proposition 3 For any $f : \{-1,1\}^n \to \{-1,1\}$ and $\delta \in (0, 1/2]$, the Fourier spectrum of $f$ is $\epsilon$-concentrated on degree up to $1/\delta$ for \[ \epsilon = \tfrac{2}{1-e^{-2}}\mathbf{NS}_\delta[f] \leq 3 \mathbf{NS}_\delta[f]. \]

Proof: Using the Fourier formula from Theorem 2.48, \begin{align*} 2\mathbf{NS}_\delta[f] &= \mathop{\bf E}_{\boldsymbol{S} \sim \mathscr{S}_{f}}[1 - (1-2\delta)^{|\boldsymbol{S}|}] \\ &\geq (1-(1-2\delta)^{1/\delta}) \cdot \mathop{\bf Pr}_{\boldsymbol{S} \sim \mathscr{S}_{f}}[|\boldsymbol{S}| \geq 1/\delta] \\ &\geq (1-e^{-2}) \cdot \mathop{\bf Pr}_{\boldsymbol{S} \sim \mathscr{S}_{f}}[|\boldsymbol{S}| \geq 1/\delta], \end{align*} where the first inequality used that $1-(1-2\delta)^k$ is a nonnegative nondecreasing function of $k$. The claim follows. $\Box$

As an example, Theorem 2.44 tells us that for $\delta > 0$ sufficiently small and $n$ sufficiently large (as a function of $\delta$), $\mathbf{NS}_\delta[\mathrm{Maj}_n] \leq \sqrt{\delta}$. Hence the Fourier spectrum of $\mathrm{Maj}_n$ is $3\sqrt{\delta}$-concentrated on degree up to $1/\delta$; equivalently, it is $\epsilon$-concentrated on degree up to $9/\epsilon^2$. (We will give sharp constants for majority’s spectral concentration in a later chapter.) This example also shows there is no simple converse to Proposition 2: although $\mathrm{Maj}_n$ has its spectrum $.01$-concentrated on degree up to $O(1)$, its total influence is $\Theta(\sqrt{n})$.

Finally, suppose a function $f : \{-1,1\}^n \to \{-1,1\}$ has its Fourier spectrum $0$-concentrated up to degree $k$; in other words, $f$ has real degree $\deg(f) \leq k$. In this case $f$ must be somewhat simple; indeed, if $k$ is a constant then $f$ is a junta:

Theorem 4 Suppose $f : \{-1,1\}^n \to \{-1,1\}$ has $\deg(f) \leq k$. Then $f$ is a $k2^{k-1}$-junta.

The bound $k2^{k-1}$ cannot be significantly improved, as you will show in an exercise. The key to proving Theorem 4 is the following lemma, the proof of which will be outlined in an exercise:

Lemma 5 Suppose $\deg(f) \leq k$, where $f : \{-1,1\}^n \to {\mathbb R}$ is not identically $0$. Then $\mathop{\bf Pr}[f({\boldsymbol{x}}) \neq 0] \geq 2^{-k}$.

Since $\deg(\mathrm{D}_i f) \leq k-1$ when $\deg(f) \leq k$ (by the “differentiation” formula) and since $\mathbf{Inf}_i[f] = \mathop{\bf Pr}[\mathrm{D}_i f({\boldsymbol{x}}) \neq 0$] for boolean-valued $f$, we immediately infer:

Proposition 6 If $f : \{-1,1\}^n \to \{-1,1\}$ has $\deg(f) \leq k$ then $\mathbf{Inf}_i[f]$ is either $0$ or at least $2^{1-k}$ for all $i \in [n]$.

We can now give the proof of Theorem 4 — from Proposition 6 the number of coordinates which have nonzero influence on $f$ is at most $\mathbf{I}[f]/2^{1-k}$, and this in turn is at most $k2^{k-1}$ by the following fact:

Fact 7 For $f : \{-1,1\}^n \to \{-1,1\}$, $\mathbf{I}[f] \leq \deg(f)$.

Fact 7 is immediate from the Fourier formula for total influence. We remark that the FKN Theorem (stated in Chapter 2.5) is a “robust” version of Theorem 4 for $k=1$. In a much later chapter we will prove the Kindler–Safra Theorem and the Bourgain Theorem which give robust versions of Theorem 4 for general $k$. Another related robust result which we will prove is Friedgut’s Theorem, which shows that if $\mathbf{I}[f] \leq k$ then $f$ is $\epsilon$-close to a $2^{O(k/\epsilon)}$-junta.