148 Boolean Analysis — Fourier Concentration

148.1 Overview

This module proves O’Donnell’s Lemma 4.21: if a Boolean function \(f\) on \(n\) variables becomes a shallow decision tree with high probability under a Bernoulli(\(p\))-random restriction, then the Fourier spectrum of its \(\pm 1\)-encoding is concentrated on low degrees. Concretely, if \(\varepsilon \) is the probability that the restricted function requires decision-tree depth at least \(k\), then the Fourier weight of \(\sigma \circ f\) above degree \(3k/p\) is at most \(4\varepsilon \); the supporting lemmas partition tail events over intersection patterns and aggregate the expected restricted spectrum.

148.2 Declarations

Lemma 148.1 Sign encoding of a Boolean function is \(\pm 1\)-valued

✓

Let \(g : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean-valued function, and let \(\sigma \) denote the sign encoding of a bit, \(\sigma (\mathtt{false}) = 1\) and \(\sigma (\mathtt{true}) = -1\). Then the real-valued function \(x \mapsto \sigma (g(x))\) takes only the values \(1\) and \(-1\) at every point \(x\) of the cube.

Lemma 148.2 Nonnegativity of Bernoulli-restriction probabilities

✓

Let \(p \in \mathbb {R}\) with \(0 \le p \le 1\), and let \(E\) be a decidable event on restrictions of \(n\) variables, where a restriction assigns each coordinate either a fixed Boolean value or leaves it free. Under the Bernoulli(\(p\))-random restriction — each restriction \(\rho \) with free-variable set \(J\) carries weight \(p^{\left\lvert J\right\rvert }\bigl(\tfrac {1-p}{2}\bigr)^{\, n-\left\lvert J\right\rvert }\) — the probability of \(E\), namely the weighted sum of the indicator of \(E\) over all restrictions, is nonnegative: \(0 \le \Pr _\rho [E]\).

Lemma 148.3 Partitioning a tail event over intersection patterns

✓

Fix \(n\), a real parameter \(p\), a subset \(U \subseteq [n]\), and a threshold \(k \in \mathbb {N}\). For a restriction \(\rho \) on \(n\) variables write \(J\) for its set of free variables, and write \(\Pr _\rho [\cdot ]\) for the sum, over all restrictions, of the Bernoulli weight \(p^{\left\lvert J\right\rvert }\bigl(\tfrac {1-p}{2}\bigr)^{\, n-\left\lvert J\right\rvert }\) times the indicator of the event (a genuine probability when \(0 \le p \le 1\)). Then

\[ \sum _{\substack {S \subseteq [n] \\ \left\lvert S\right\rvert \ge k}} \Pr _\rho \bigl[\, U \cap J = S\, \bigr] \; =\; \Pr _\rho \bigl[\, \left\lvert U \cap J\right\rvert \ge k\, \bigr]. \]

The identity holds for every real \(p\); no bound on \(p\) is assumed.

Lemma 148.4 Tail of the expected restricted Fourier spectrum

✓

Fix \(n\), a real parameter \(p\), a function \(F : \{ 0,1\} ^n \to \mathbb {R}\), and \(k \in \mathbb {N}\). For a restriction \(\rho \) on \(n\) variables with free-variable set \(J\), write \(w_p(\rho ) = p^{\left\lvert J\right\rvert }\bigl(\tfrac {1-p}{2}\bigr)^{\, n-\left\lvert J\right\rvert }\) for its Bernoulli weight, \(F_\rho \) for the restriction of \(F\) by \(\rho \) (free coordinates read from the input, fixed coordinates from \(\rho \)), \(\hat g(T)\) for the Fourier–Walsh coefficient of a function \(g\) at a set \(T\), and \(\Pr _\rho [\cdot ]\) for the \(w_p\)-weighted sum of an event’s indicator over all restrictions. Then

\[ \sum _{\substack {S \subseteq [n] \\ \left\lvert S\right\rvert \ge k}} \sum _{\rho } w_p(\rho )\, \widehat{F_\rho }(S)^2 \; =\; \sum _{U \subseteq [n]} \hat F(U)^2 \; \Pr _\rho \bigl[\, \left\lvert U \cap J\right\rvert \ge k\, \bigr]. \]

When \(0 \le p \le 1\) the left-hand side is \(\sum _{\left\lvert S\right\rvert \ge k} \mathbb {E}_\rho \bigl[\widehat{F_\rho }(S)^2\bigr]\), so this is O’Donnell’s Proposition 4.17 summed over the high-degree frequency sets.

Theorem 148.5 Fourier concentration from random restrictions

✓

This is O’Donnell’s Lemma 4.21, with constant \(4\) in place of \(3\). Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function, let \(p \in \mathbb {R}\) with \(0 \le p \le 1\), and let \(k \in \mathbb {N}\) with \(k \ge 1\). Let \(\rho \) be a Bernoulli(\(p\))-random restriction on \(n\) variables: each coordinate is independently left free with probability \(p\) and otherwise fixed to a uniformly random bit, so a restriction with free-variable set \(J\) has probability \(p^{\left\lvert J\right\rvert }\bigl(\tfrac {1-p}{2}\bigr)^{\, n-\left\lvert J\right\rvert }\). Write \(f_\rho \) for the function obtained from \(f\) by fixing the coordinates outside \(J\) according to \(\rho \), \(\mathrm{DT}(g)\) for the least depth of a decision tree computing a Boolean function \(g\), and \(\sigma \) for the sign encoding (\(\sigma (\mathtt{false}) = 1\), \(\sigma (\mathtt{true}) = -1\)). Setting \(\varepsilon = \Pr _\rho \bigl[\mathrm{DT}(f_\rho ) \ge k\bigr]\), the Fourier spectrum of the \(\pm 1\)-encoding \(\sigma \circ f\) is \(4\varepsilon \)-concentrated below degree \(3k/p\):

\[ \sum _{\substack {U \subseteq [n] \\ 3k \le p\, \left\lvert U\right\rvert }} \widehat{\sigma \circ f}(U)^2 \; \le \; 4\, \varepsilon , \]

where the degree condition is stated division-free as \(3k \le p\, \left\lvert U\right\rvert \).