259 Boolean Analysis — Junta
259.1 Overview
Influential coordinates capture low degree Fourier mass and give Boolean approximations under a Fourier tail bound. Choosing the degree cutoff yields the dimension-independent Friedgut junta theorem.
259.2 Declarations
Let \(f:\{ 0,1\} ^n\to \{ -1,1\} \) be a function on the uniform Boolean cube, \(0\lt \varepsilon \le 1\), and \(k\in \mathbb N\). Write \(I=I(f)\), put \(\tau =1\) if \(I=0\) and \(\tau =\varepsilon ^2/(I^2 9^k)\) otherwise, and set \(J=\{ i:I_i(f)\ge \tau \} \). Then \(|J|\le I^3 9^k/\varepsilon ^2\) and \(\sum _{|S|\le k,\ S\nsubseteq J}\widehat f(S)^2\le \varepsilon \); if \(\sum _{|S|\gt k}\widehat f(S)^2\le \varepsilon \), then \(\sum _{\neg (S\subseteq J\ \mathrm{and}\ |S|\le k)}\widehat f(S)^2\le 2\varepsilon \) and there exists \(h:\{ 0,1\} ^n\to \{ -1,1\} \) depending only on \(J\) with \(\Pr (f\ne h)\le \varepsilon \). 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)\).
There exists an absolute \(C\gt 0\) such that for every \(f:\{ 0,1\} ^n\to \{ -1,1\} \) under the uniform law and \(0\lt \varepsilon \le 1\), there exist \(J\subseteq [n]\) and \(h:\{ 0,1\} ^n\to \{ -1,1\} \) depending only on \(J\) with \(|J|\le \exp (CI(f)/\varepsilon )\), \(\sum _{\neg (S\subseteq J\ \mathrm{and}\ |S|\le I(f)/\varepsilon )}\widehat f(S)^2\le 2\varepsilon \), and \(\Pr (f\ne h)\le \varepsilon \). 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 \(I=I(f)\gt 0\). For \(\varepsilon ,\eta \gt 0\) and \(k\in \mathbb N\) satisfying \(\sum _{|S|\gt k}\widehat f(S)^2\le \varepsilon \), put \(\rho =\eta /(2+\eta )\). There exist \(J\subseteq [n]\) and \(h:\{ 0,1\} ^n\to \{ -1,1\} \) depending only on \(J\), with \(|J|\le I^{2+\eta }/(\varepsilon \rho ^k)^{1+\eta }\) and \(\Pr (f\ne h)\le \varepsilon \). 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)\).