TCSLib

253 Boolean Analysis — Influence

253.1 Overview

Hypercontractivity bounds stable coordinate influences and the low Fourier levels of indicator functions. The level-one estimate has the sharp logarithmic coefficient obtained from linear correlations.

253.2 Declarations

Let \(f:\{ 0,1\} ^n\to \{ 0,1\} \) and \(0\lt \rho \le 1\). Then under the uniform cube law \(\mathbb E[fT_\rho f]\le (\mathbb Ef)^{2/(1+\rho )}\).

Lemma 253.2 Indicator correlation with linear forms
✓

Let \(f:\{ 0,1\} ^n\to \{ 0,1\} \) have uniform mean \(\alpha \gt 0\), and let \(a_i\in \mathbb R\) satisfy \(\sum _ia_i^2=1\). Then \(\big(\mathbb E[f(x)\sum _i a_i(-1)^{x_i}]\big)^2\le 2\alpha ^2\log (1/\alpha )\).

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube, \(i\in [n]\), and \(\rho \ge 0\). Then \(I_i^{(\rho )}(f)=\| T_{\sqrt\rho }D_if\| _2^2\), where \(D_if(x)=(f(x^{i\leftarrow 0})-f(x^{i\leftarrow 1}))/2\).

Let \(f:\{ 0,1\} ^n\to \{ -1,1\} \) be a function on the uniform Boolean cube, \(i\in [n]\), and \(p\gt 0\). Then \(\mathbb E|D_if|^p=I_i(f)\), where \(D_if(x)=(f(x^{i\leftarrow 0})-f(x^{i\leftarrow 1}))/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.

Let \(f:\{ 0,1\} ^n\to \{ -1,1\} \) 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)^{2/(1+\rho )}\). 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.

Theorem 253.6 One-third stable influence
✓

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

Lemma 253.7 Weighted low-level Fourier bound
✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube, \(k\in \mathbb N\), and \(0\le \rho \le 1\). Then \(\rho ^k\sum _{|S|\le k}\widehat f(S)^2\le \mathbb E[fT_\rho f]\).

Lemma 253.8 Indicator exponent estimate
✓

For every \(0\lt \alpha \le 1\) and \(\rho \ge 0\), \(\alpha ^{2/(1+\rho )}\le \alpha ^2\exp (2\rho \log (1/\alpha ))\).

Lemma 253.9 Level bound parameter optimization
✓

Let \(0\lt \alpha \le 1\), \(W\in \mathbb R\), and a positive integer \(k\) satisfy \(k\le 2\log (1/\alpha )\). If \(\rho ^kW\le \alpha ^{2/(1+\rho )}\) for every \(0\lt \rho \le 1\), then \(W\le ((2e/k)\log (1/\alpha ))^k\alpha ^2\).

Theorem 253.10 Level-k indicator inequality
✓

Let \(f:\{ 0,1\} ^n\to \{ 0,1\} \) have uniform mean \(\alpha \gt 0\), and let \(k\) be a positive integer with \(k\le 2\log (1/\alpha )\). Then \(\sum _{|S|\le k}\widehat f(S)^2\le ((2e/k)\log (1/\alpha ))^k\alpha ^2\).

Theorem 253.11 Level-one indicator inequality
✓

Let \(f:\{ 0,1\} ^n\to \{ 0,1\} \) have uniform mean \(\alpha \gt 0\). Then \(\sum _{|S|=1}\widehat f(S)^2\le 2\alpha ^2\log (1/\alpha )\).