254 Boolean Analysis — KKL
254.1 Overview
The full variance-scaled KKL theorem and its edge-isoperimetric strengthening give large coordinate influences. A further consequence locates a large nonempty Fourier coefficient at degree controlled by total influence.
254.2 Declarations
Let \(f:\{ 0,1\} ^n\to \{ -1,1\} \) be a function on the uniform Boolean cube with variance \(V\gt 0\), and put \(a=I(f)/V\). Then \((9/a^2)9^{-a}\le \max _{i\in [n]}|I_i(f)|\). For a real cube function \(h\), define \(I_i(h)=\tfrac 14\mathbb E_x(h(x)-h(x^{(i)}))^2\), where \(x^{(i)}\) flips coordinate \(i\) and \(\mathbb E_x\) is uniform expectation, and \(I(h)=\sum _{i=0}^{n-1}I_i(h)\).
Let \(f:\{ 0,1\} ^n\to \{ -1,1\} \) be a function on the uniform Boolean cube in dimension \(n\ge 2\). Some coordinate \(i\) satisfies \(\operatorname {Var}(f)\log n/(30n)\le I_i(f)\). For a real cube function \(h\), define \(I_i(h)=\tfrac 14\mathbb E_x(h(x)-h(x^{(i)}))^2\), where \(x^{(i)}\) flips coordinate \(i\) and \(\mathbb E_x\) is uniform expectation.
There exists an absolute \(c\gt 0\) such that for every natural dimension \(n\) and every \(f:\{ 0,1\} ^n\to \{ -1,1\} \) under the uniform law, \(c\operatorname {Var}(f)(\log n/n)\le \sup _{i\in [n]}|I_i(f)|\), with the empty supremum and division by zero interpreted as zero. For a real cube function \(h\), define \(I_i(h)=\tfrac 14\mathbb E_x(h(x)-h(x^{(i)}))^2\), where \(x^{(i)}\) flips coordinate \(i\) and \(\mathbb E_x\) is uniform expectation.
There exists an absolute \(C\gt 0\) such that for every \(f:\{ 0,1\} ^n\to \{ -1,1\} \) under the uniform law with \(\operatorname {Var}(f)\ge 1/2\), there is a nonempty \(S\subseteq [n]\) with \(|S|\le CI(f)\) and \(\widehat f(S)^2\ge \exp (-CI(f)^2)\). For a real cube function \(h\), define \(I_i(h)=\tfrac 14\mathbb E_x(h(x)-h(x^{(i)}))^2\), where \(x^{(i)}\) flips coordinate \(i\) and \(\mathbb E_x\) is uniform expectation, and \(I(h)=\sum _{i=0}^{n-1}I_i(h)\).
Let \(f:\{ 0,1\} ^n\to \{ -1,1\} \) be a function on the uniform Boolean cube with \(n\ge 2\) and \(\mathbb Ef=0\). Some coordinate \(i\) satisfies \(I_i(f)\ge \log n/(30n)\). For a real cube function \(h\), define \(I_i(h)=\tfrac 14\mathbb E_x(h(x)-h(x^{(i)}))^2\), where \(x^{(i)}\) flips coordinate \(i\) and \(\mathbb E_x\) is uniform expectation.