263 Boolean Analysis — Small Set Expansion
263.1 Overview
Indicators on the uniform Boolean cube satisfy moment identities and volume bounds. Two-function hypercontractivity gives a parameterized two-set expansion inequality and a one-set stability estimate.
263.2 Declarations
For a set \(A\subseteq \{ 0,1\} ^n\), define \(\mathbf1_A(x)=1\) if \(x\in A\) and \(\mathbf1_A(x)=0\) otherwise.
For a set \(A\subseteq \{ 0,1\} ^n\), define its volume \(\mu (A)=\mathbb E_x\mathbf1_A(x)=|A|/2^n\) under the uniform cube law.
For every \(A\subseteq \{ 0,1\} ^n\) and \(x\in \{ 0,1\} ^n\), \(\mathbf1_A(x)\ge 0\).
For every \(A\subseteq \{ 0,1\} ^n\) and \(x\in \{ 0,1\} ^n\), \(\mathbf1_A(x)\le 1\).
For every \(A\subseteq \{ 0,1\} ^n\) and \(x\in \{ 0,1\} ^n\), \(|\mathbf1_A(x)|=\mathbf1_A(x)\).
For every \(A\subseteq \{ 0,1\} ^n\) and \(x\in \{ 0,1\} ^n\), \(\mathbf1_A(x)^2=\mathbf1_A(x)\).
For every \(A\subseteq \{ 0,1\} ^n\), \(x\in \{ 0,1\} ^n\), and \(r\gt 0\), \(\mathbf1_A(x)^r=\mathbf1_A(x)\).
For every \(A\subseteq \{ 0,1\} ^n\), \(x\in \{ 0,1\} ^n\), and \(r\gt 0\), \(|\mathbf1_A(x)|^r=\mathbf1_A(x)\).
For every \(A\subseteq \{ 0,1\} ^n\) and \(r\gt 0\), the uniform expectation satisfies \(\mathbb E|\mathbf1_A|^r=|A|/2^n\).
For every \(A\subseteq \{ 0,1\} ^n\) and \(r\gt 0\), its moment norm under the uniform cube law satisfies \(\| \mathbf1_A\| _r=(|A|/2^n)^{1/r}\).
For every \(A\subseteq \{ 0,1\} ^n\), its uniform volume satisfies \(\mu (A)=|A|/2^n\ge 0\).
For every \(A\subseteq \{ 0,1\} ^n\), its uniform volume satisfies \(\mu (A)=|A|/2^n\le 1\).
Let \(A,B\subseteq \{ 0,1\} ^n\) have uniform volumes \(\alpha ,\beta \), and let real \(p,u,\rho \) satisfy \(1\le p\le u\), \(u\ge 2\), \(0\le \rho \le 1\), and \(\rho \le \sqrt{(p-1)/(u-1)}\). Then \(\mathbb E[\mathbf1_AT_\rho \mathbf1_B]\le \alpha ^{(u-1)/u}\beta ^{1/p}\).
For every \(A\subseteq \{ 0,1\} ^n\) of uniform volume \(\alpha \) and \(0\lt \rho \le 1\), \(\mathbb E[\mathbf1_AT_\rho \mathbf1_A]\le \alpha ^{2/(1+\rho )}\).