TCSLib

224 Boolean Analysis — Tensorization

224.1 Overview

An extended Bobkov functional includes arbitrary additional coordinate functions alongside the discrete gradient. Symmetric pair contraction tensorizes, yielding contraction under simultaneous noise in all coordinates.

224.2 Declarations

Definition 224.1 Extended profile-gradient functional
✓

For \(P:\mathbb R\to \mathbb R\), \(f:\{ 0,1\} ^n\to \mathbb R\), and \(g=(g_1,\ldots ,g_m)\) of real functions on the cube, write \(V(f,g)(x)=(D_1f(x),\ldots ,D_nf(x),g_1(x),\ldots ,g_m(x))\) and \(F_P(f,g)=\mathbb E\sqrt{P(f)^2+\| V(f,g)\| _2^2}\), with \(D_i\) the coordinate half-difference. The extended functional is \(F_P(f,g)\) for arbitrary \(n,m\ge 0\).

Definition 224.2 Gradient and additional coordinate vector
✓

For \(f:\{ 0,1\} ^n\to \mathbb R\), \(m\ge 0\), and real cube functions \(g_1,\ldots ,g_m\), define \(V(f,g)(x)=(D_1f(x),\ldots ,D_nf(x),g_1(x),\ldots ,g_m(x))\), where \(D_i\) is the coordinate half-difference.

Lemma 224.3 Squared combined vector length
✓

For \(P:\mathbb R\to \mathbb R\), \(f:\{ 0,1\} ^n\to \mathbb R\), and \(g=(g_1,\ldots ,g_m)\) of real functions on the cube, write \(V(f,g)(x)=(D_1f(x),\ldots ,D_nf(x),g_1(x),\ldots ,g_m(x))\) and \(F_P(f,g)=\mathbb E\sqrt{P(f)^2+\| V(f,g)\| _2^2}\), with \(D_i\) the coordinate half-difference. For every \(x\), \(\| V(f,g)(x)\| _2^2=\sum _i(D_i f(x))^2+\sum _jg_j(x)^2\).

For a profile \(P:\mathbb R\to \mathbb R\), a real function \(h\) on a uniform Boolean cube, and a vector \(k\) of real functions on that cube, put \(V(h,k)(x)=((D_i h(x))_i,(k_j(x))_j)\) and \(F_P(h,k)=\mathbb E\sqrt{P(h)^2+\| V(h,k)\| _2^2}\), where \(D_i\) is the coordinate half-difference. Let \(f\) be a real function and \(g\) a vector of \(m\) real functions on \(\{ 0,1\} ^{n+1}\). Put \(f_b(x)=f(x,b)\), \(g_b(x)=g(x,b)\), \(a_f=(f_0+f_1)/2\), \(d_f=(f_0-f_1)/2\), and define \(a_g,d_g\) componentwise. For every \(x,b\), \(\sqrt{P(f(x,b))^2+\| V(f,g)(x,b)\| _2^2}=\sqrt{P(f_b(x))^2+d_f(x)^2+\| V(f_b,g_b)(x)\| _2^2}\).

Lemma 224.5 Linearity of combined coordinate vectors
✓

For a profile \(P:\mathbb R\to \mathbb R\), a real function \(h\) on a uniform Boolean cube, and a vector \(k\) of real functions on that cube, put \(V(h,k)(x)=((D_i h(x))_i,(k_j(x))_j)\) and \(F_P(h,k)=\mathbb E\sqrt{P(h)^2+\| V(h,k)\| _2^2}\), where \(D_i\) is the coordinate half-difference. For real \(c,d\), functions \(f_1,f_2\) on the cube, and vectors \(g_1,g_2\) of \(m\) cube functions, \(V(cf_1+df_2,cg_1+dg_2)(x)=cV(f_1,g_1)(x)+dV(f_2,g_2)(x)\) for every \(x\).

For a profile \(P:\mathbb R\to \mathbb R\), a real function \(h\) on a uniform Boolean cube, and a vector \(k\) of real functions on that cube, put \(V(h,k)(x)=((D_i h(x))_i,(k_j(x))_j)\) and \(F_P(h,k)=\mathbb E\sqrt{P(h)^2+\| V(h,k)\| _2^2}\), where \(D_i\) is the coordinate half-difference. Let \(f\) be a real function and \(g\) a vector of \(m\) real functions on \(\{ 0,1\} ^{n+1}\). Put \(f_b(x)=f(x,b)\), \(g_b(x)=g(x,b)\), \(a_f=(f_0+f_1)/2\), \(d_f=(f_0-f_1)/2\), and define \(a_g,d_g\) componentwise. Let \(T_\rho \) denote Boolean noise with real correlation \(\rho \), whose Fourier multiplier on a set of size \(k\) is \(\rho ^k\). For \(s_0=1\), \(s_1=-1\), \(V(T_\rho f_b,T_\rho g_b)(x)=V(T_\rho a_f,T_\rho a_g)(x)+s_bV(T_\rho d_f,T_\rho d_g)(x)\) for every \(x,b\).

For a profile \(P:\mathbb R\to \mathbb R\), a real function \(h\) on a uniform Boolean cube, and a vector \(k\) of real functions on that cube, put \(V(h,k)(x)=((D_i h(x))_i,(k_j(x))_j)\) and \(F_P(h,k)=\mathbb E\sqrt{P(h)^2+\| V(h,k)\| _2^2}\), where \(D_i\) is the coordinate half-difference. Let \(f\) be a real function and \(g\) a vector of \(m\) real functions on \(\{ 0,1\} ^{n+1}\). Put \(f_b(x)=f(x,b)\), \(g_b(x)=g(x,b)\), \(a_f=(f_0+f_1)/2\), \(d_f=(f_0-f_1)/2\), and define \(a_g,d_g\) componentwise. Let \(T_\rho \) denote Boolean noise with real correlation \(\rho \), whose Fourier multiplier on a set of size \(k\) is \(\rho ^k\). For \(s_0=1\), \(s_1=-1\), \(V((T_\rho f)_b,(T_\rho g)_b)(x)=V(T_\rho a_f,T_\rho a_g)(x)+s_b\rho V(T_\rho d_f,T_\rho d_g)(x)\) for every \(x,b\).

Lemma 224.8 Coordinate splitting of the extended functional
✓

For a profile \(P:\mathbb R\to \mathbb R\), a real function \(h\) on a uniform Boolean cube, and a vector \(k\) of real functions on that cube, put \(V(h,k)(x)=((D_i h(x))_i,(k_j(x))_j)\) and \(F_P(h,k)=\mathbb E\sqrt{P(h)^2+\| V(h,k)\| _2^2}\), where \(D_i\) is the coordinate half-difference. Let \(f\) be a real function and \(g\) a vector of \(m\) real functions on \(\{ 0,1\} ^{n+1}\). Put \(f_b(x)=f(x,b)\), \(g_b(x)=g(x,b)\), \(a_f=(f_0+f_1)/2\), \(d_f=(f_0-f_1)/2\), and define \(a_g,d_g\) componentwise. Then \(F_P(f,g)=\bigl(F_P(f_0,(d_f,g_0))+F_P(f_1,(d_f,g_1))\bigr)/2\), where \((d_f,g_b)\) adjoins \(d_f\) to the additional coordinates.

For a profile \(P:\mathbb R\to \mathbb R\), a real function \(h\) on a uniform Boolean cube, and a vector \(k\) of real functions on that cube, put \(V(h,k)(x)=((D_i h(x))_i,(k_j(x))_j)\) and \(F_P(h,k)=\mathbb E\sqrt{P(h)^2+\| V(h,k)\| _2^2}\), where \(D_i\) is the coordinate half-difference. Let \(f\) be a real function and \(g\) a vector of \(m\) real functions on \(\{ 0,1\} ^{n+1}\). Put \(f_b(x)=f(x,b)\), \(g_b(x)=g(x,b)\), \(a_f=(f_0+f_1)/2\), \(d_f=(f_0-f_1)/2\), and define \(a_g,d_g\) componentwise. Let \(T_\rho \) denote Boolean noise with real correlation \(\rho \), whose Fourier multiplier on a set of size \(k\) is \(\rho ^k\). For each \(x\), put \(a=T_\rho a_f(x)\), \(b=T_\rho d_f(x)\), \(u=V(T_\rho a_f,T_\rho a_g)(x)\), and \(v=V(T_\rho d_f,T_\rho d_g)(x)\). Then \(F_P(T_\rho f,T_\rho g)=\mathbb E_x\frac12\sum _{\epsilon \in \{ -1,1\} }\sqrt{P(a+\epsilon \rho b)^2+(\rho b)^2+\| u+\epsilon \rho v\| _2^2}\).

For a profile \(P:\mathbb R\to \mathbb R\), a real function \(h\) on a uniform Boolean cube, and a vector \(k\) of real functions on that cube, put \(V(h,k)(x)=((D_i h(x))_i,(k_j(x))_j)\) and \(F_P(h,k)=\mathbb E\sqrt{P(h)^2+\| V(h,k)\| _2^2}\), where \(D_i\) is the coordinate half-difference. Let \(f\) be a real function and \(g\) a vector of \(m\) real functions on \(\{ 0,1\} ^{n+1}\). Put \(f_b(x)=f(x,b)\), \(g_b(x)=g(x,b)\), \(a_f=(f_0+f_1)/2\), \(d_f=(f_0-f_1)/2\), and define \(a_g,d_g\) componentwise. Let \(T_\rho \) denote Boolean noise with real correlation \(\rho \), whose Fourier multiplier on a set of size \(k\) is \(\rho ^k\). For each \(x\), put \(a=T_\rho a_f(x)\), \(b=T_\rho d_f(x)\), \(u=V(T_\rho a_f,T_\rho a_g)(x)\), and \(v=V(T_\rho d_f,T_\rho d_g)(x)\). Then \(\mathbb E_x\frac12\sum _{\epsilon \in \{ -1,1\} }\sqrt{P(a+\epsilon b)^2+b^2+\| u+\epsilon v\| _2^2}=\bigl(F_P(T_\rho f_0,(T_\rho d_f,T_\rho g_0))+F_P(T_\rho f_1,(T_\rho d_f,T_\rho g_1))\bigr)/2\).

Lemma 224.11 Noise contracts the extended functional
✓

For \(P:\mathbb R\to \mathbb R\), \(f:\{ 0,1\} ^n\to \mathbb R\), and \(g=(g_1,\ldots ,g_m)\) of real functions on the cube, write \(V(f,g)(x)=(D_1f(x),\ldots ,D_nf(x),g_1(x),\ldots ,g_m(x))\) and \(F_P(f,g)=\mathbb E\sqrt{P(f)^2+\| V(f,g)\| _2^2}\), with \(D_i\) the coordinate half-difference. Assume \(P\ge 0\) on \([0,1]\) and, whenever \(z\pm d\in [0,1]\), \(P(z)\le \bigl(\sqrt{P(z+d)^2+d^2}+\sqrt{P(z-d)^2+d^2}\bigr)/2\). If \(P\) is continuous on \([0,1]\), \(f\) takes values in \([0,1]\), and \(0\le \rho \le 1\), then \(F_P(T_\rho f,T_\rho g)\le F_P(f,g)\), where \(T_\rho \) is Boolean noise applied to each component.