TCSLib

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

Lemma 220.1 Derivative under last-coordinate restriction
✓

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.

Lemma 220.2 Last derivative of a restricted point
✓

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.

Lemma 220.3 Squared gradient under restriction
✓

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.

Lemma 220.4 Mean of the last 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\).

Lemma 220.5 Length of an expected pair
✓

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}\).

Lemma 220.6 Midpoint with additional Euclidean coordinates
✓

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\).

Lemma 220.7 Linearity of discrete differentiation
✓

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\).