122 Boolean Analysis — KKL
122.1 Overview
This chapter develops the Fourier-analytic machinery behind the Kahn–Kalai–Linial theorem and Friedgut’s junta theorem: noisy influences \(\mathrm{Inf}_i^\rho [f] = \sum _{S \ni i}\rho ^{\left\lvert S\right\rvert -1}\hat f(S)^2\), the low- and high-degree truncations of a Boolean function, the set of \(\tau \)-influential coordinates, and the squared \(L^2\) distance between Boolean functions. On top of these it records the low-degree approximation bound \(\mathbb {E}[(f - f_{\le k})^2] \le I[f]/k\), the junta construction on the influential coordinates, the KKL lower bound \(\max _i \mathrm{Inf}_i[f] \ge \log n/(30n)\) for balanced \(\pm 1\)-valued functions, and Friedgut’s junta theorem.
122.2 Declarations
The noisy influence of coordinate \(i\) on \(f\) at noise rate \(\rho \) is
the sum being taken over all \(S \subseteq [n]\) containing \(i\).
The low-degree part of \(f\) at level \(k\) keeps only the Fourier coefficients of degree at most \(k\):
The high-degree part of \(f\) at level \(k\) keeps only the Fourier coefficients of degree strictly greater than \(k\):
The set of \(\tau \)-influential coordinates of \(f\) is the finite set
A function \(g\) is a \(J\)-junta if it depends only on the coordinates in \(J\): whenever \(x\) and \(y\) agree on every \(i \in J\), we have \(g(x) = g(y)\).
The squared \(L^2\) distance between two Boolean functions is \(\mathbb {E}\big[(f(x) - g(x))^2\big]\) under the uniform measure on the cube.
At noise rate \(\rho = 1\) the noisy influence coincides with the ordinary influence: \(\mathrm{Inf}_i^{1}[f] = \mathrm{Inf}_i[f]\).
For every \(\rho \),
The total influence is the sum of the coordinate influences: \(I[f] = \sum _{i} \mathrm{Inf}_i[f]\).
If \(f\) takes values in \(\{ -1, 1\} \), then \(\mathbb {E}[f^2] = 1\).
For every Boolean function \(f\), \(\sum _{S \subseteq [n]} \hat f(S)^2 = \mathbb {E}[f^2]\).
For every \(f\), every level \(k\) and every point \(x\) of the cube, \(f_{\le k}(x) + f_{\gt k}(x) = f(x)\).
The truncation acts as a projection on the Fourier side: for every \(S\), \(\widehat{f_{\le k}}(S) = \hat f(S)\) when \(\left\lvert S\right\rvert \le k\), and \(\widehat{f_{\le k}}(S) = 0\) otherwise.
The squared \(L^2\) error of the degree-\(k\) truncation is exactly the Fourier weight above level \(k\):
For \(k \gt 0\) the Fourier weight of \(f\) above level \(k\) is controlled by the total influence:
For \(k \gt 0\), the degree-\(k\) truncation approximates \(f\) with squared \(L^2\) error at most \(I[f]/k\).
For \(\tau \gt 0\) the number of \(\tau \)-influential coordinates satisfies \(\left\lvert J_\tau (f)\right\rvert \le I[f]/\tau \).
For every \(f\), every level \(k\) and every \(\tau \gt 0\) there is a function \(g\) that is a junta on the \(\tau \)-influential coordinates \(J_\tau (f)\) and satisfies \(\mathbb {E}\big[(f_{\le k} - g)^2\big] \le n\tau \).
For \(0 \le \rho \le 1\) we have \(\mathrm{Inf}_i^{\rho }[f] \le \mathrm{Inf}_i[f]\) for every coordinate \(i\).
For a \(\pm 1\)-valued \(f\) and \(0 \lt \rho \le 1\), the noisy influence of any coordinate is at most its ordinary influence: \(\mathrm{Inf}_i^{\rho }[f] \le \mathrm{Inf}_i[f]\).
The total influence obeys
If \(I[f] \gt 0\), then some coordinate \(i\) satisfies
For \(n \gt 0\) there exists a coordinate \(i\) with \(\mathrm{Inf}_i[f] \ge I[f]/n\), the trivial averaging bound.
The noisy total influence at rate \(\rho \) is
(Kahn–Kalai–Linial, 1988.) Let \(f : \{ 0,1\} ^n \to \{ -1,1\} \) be balanced, i.e. \(\mathbb {E}[f] = 0\), with \(n \ge 2\). Then some coordinate \(i\) has
(Friedgut, 1998.) Let \(f : \{ 0,1\} ^n \to \{ -1,1\} \) and let \(\varepsilon \gt 0\). Then there are a coordinate set \(J\) and a function \(g\) such that \(\left\lvert J\right\rvert \le 4n\, I[f]/\varepsilon \), the function \(g\) is a \(J\)-junta, and \(\mathbb {E}\big[(f - g)^2\big] \le \varepsilon \).
If \(f\) takes values in \(\{ -1,1\} \), \(\mathbb {E}[f] = 0\) and \(n \gt 0\), then \(I[f] \ge 1\).
If \(I[f] \gt 0\), then the entropy-like quantity attached to the influence distribution is nonnegative: