258 Boolean Analysis — Elementary

258.1 Overview

Elementary influence inequalities bound maxima and noisy Fourier energy on the Boolean cube. A dimension-dependent approximation by real-valued juntas complements the exponential Boolean junta theorem.

258.2 Declarations

Lemma 258.1 Noisy influence upper bound

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube, \(i\in [n]\), and \(0\le \rho \le 1\). Then \(I_i^{(\rho )}(f)\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.

Lemma 258.2 Boolean noisy influence upper bound

✓

Let \(f:\{ 0,1\} ^n\to \{ -1,1\} \) be a function on the uniform Boolean cube, \(i\in [n]\), and \(0\lt \rho \le 1\). Then \(I_i^{(\rho )}(f)\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.

Lemma 258.3 Influence Cauchy–Schwarz inequality

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube. Then \(I(f)^2\le n\sum _iI_i(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)\).

Lemma 258.4 Large influence from squared influences

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube with \(I(f)\gt 0\). There exists \(i\in [n]\) with \(I_i(f)\ge \sum _jI_j(f)^2/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)\).

Theorem 258.5 Average coordinate influence bound

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube in dimension \(n\gt 0\). Then some \(i\in [n]\) satisfies \(I_i(f)\ge I(f)/n\). 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)\).

Definition 258.6 Noisy degree-weighted Fourier energy

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube and \(\rho \in \mathbb R\). Define \(N_\rho (f)=\sum _{S\subseteq [n]}|S|\rho ^{2|S|}\widehat f(S)^2\).

Theorem 258.7 Dimension-dependent real junta approximation

✓

Let \(f:\{ 0,1\} ^n\to \{ -1,1\} \) be a function on the uniform Boolean cube and \(\varepsilon \gt 0\). There exist \(J\subseteq [n]\) and \(g:\{ 0,1\} ^n\to \mathbb R\) depending only on \(J\), with \(|J|\le 4nI(f)/\varepsilon \) and \(\mathbb E(f-g)^2\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)\).

Lemma 258.8 Balanced total influence lower bound

✓

Let \(f:\{ 0,1\} ^n\to \{ -1,1\} \) be a function on the uniform Boolean cube with \(n\gt 0\) and \(\mathbb Ef=0\). Then \(I(f)\ge 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)\).

Lemma 258.9 Nonnegative influence entropy

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube with \(I(f)\gt 0\). Then \(\sum _i[I_i(f)/I(f)]\log (I(f)/I_i(f))\ge 0\), with zero influences contributing 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, and \(I(h)=\sum _{i=0}^{n-1}I_i(h)\).