220 Boolean Analysis — Cube
220.1 Overview
Coordinate restrictions respect discrete derivatives and split the squared gradient. Euclidean triangle inequalities give expectation and midpoint bounds used in tensorization.
220.2 Declarations
Let \(f:\{ 0,1\} ^{n+1}\to \mathbb R\) and \(f_b(x)=f(x,b)\). For \(i\lt n\), \(b\in \{ 0,1\} \), and \(x\in \{ 0,1\} ^n\), \(D_i f_b(x)=D_i f(x,b)\), where \(D_i\) is the coordinate half-difference.
Let \(f:\{ 0,1\} ^{n+1}\to \mathbb R\), \(f_b(x)=f(x,b)\), and \(d=(f_0-f_1)/2\). Then \(D_n f(x,b)=d(x)\) for all \(x\) and \(b\), where \(D_n\) is the last-coordinate half-difference.
Let \(f:\{ 0,1\} ^{n+1}\to \mathbb R\), \(f_b(x)=f(x,b)\), and \(d=(f_0-f_1)/2\). Then \(\sum _{i\lt n+1}(D_i f(x,b))^2=\sum _{i\lt n}(D_i f_b(x))^2+d(x)^2\) for every \(x,b\), with \(D_i\) the coordinate half-difference.
Let \(f:\{ 0,1\} ^{n+1}\to \mathbb R\), \(f_b(x)=f(x,b)\), and \(d=(f_0-f_1)/2\). Uniform expectation satisfies \(\mathbb E d=(\mathbb E f_0-\mathbb E f_1)/2\).
For any real functions \(u,v\) on a uniform Boolean cube, \(\sqrt{(\mathbb E u)^2+(\mathbb E v)^2}\le \mathbb E\sqrt{u^2+v^2}\).
Let \(m\ge 0\), \(u,v\in \mathbb R^m\), and \(A,B,C\in \mathbb R\). If \(0\le A\le (B+C)/2\), then \(\sqrt{A^2+\sum _j u_j^2}\le \bigl(\sqrt{B^2+\sum _j(u_j+v_j)^2}+\sqrt{C^2+\sum _j(u_j-v_j)^2}\bigr)/2\).
For any real functions \(f,g\) on \(\{ 0,1\} ^n\), real scalars \(c,d\), and a coordinate \(i\lt n\), \(D_i(cf+dg)=cD_i f+dD_i g\), where \(D_i f(x)=(f(x^{i\leftarrow 0})-f(x^{i\leftarrow 1}))/2\).