256 Boolean Analysis — Concentration
256.1 Overview
The low degree Fourier mass involving omitted coordinates is controlled by their influence threshold. The estimate permits endpoint noise rates and zero thresholds.
256.2 Declarations
Let \(f:\{ 0,1\} ^n\to \{ -1,1\} \) be a function on the uniform Boolean cube, \(J\subseteq [n]\), \(k\in \mathbb N\), \(0\le \rho \le 1\), and \(\tau \ge 0\). If \(I_i(f)\le \tau \) for every \(i\notin J\), then \(\rho ^k\sum _{|S|\le k,\ S\nsubseteq J}\widehat f(S)^2\le \tau ^{(1-\rho )/(1+\rho )}I(f)\), with \(0^0=1\). 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)\).