269 Boolean Analysis — Even Moments
269.1 Overview
Even-moment hypercontractivity controls noise from the second norm to every even integer norm. Fourier contraction, coordinate decompositions, and a finite-exponent duality principle supply related estimates.
269.2 Declarations
Let \(n\in \mathbb {N}\), let \(f\colon \{ 0,1\} ^n\to \mathbb {R}\) be a Boolean function, and let \(\rho \in \mathbb {R}\). Write \(T_\rho \) for the noise operator with parameter \(\rho \), \(\langle \, \cdot \, ,\, \cdot \, \rangle \) for the \(L^2\) inner product under the uniform measure on \(\{ 0,1\} ^n\), and \(\hat f(S)\) for the Fourier–Walsh coefficient of \(f\) at frequency \(S\subseteq [n]\). Then
For \(d\in \mathbb N\), \(h:\{ 0,1\} ^d\to \mathbb {R}\), and \(\tau \in \mathbb {R}\), the spectral noise operator is \(T_\tau h(x)=\sum _{S\subseteq [d]}\tau ^{|S|}\widehat h(S)\chi _S(x)\), where \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) and \(\widehat h(S)=\mathbb {E}[h\chi _S]\) under the uniform measure.
Fix \(n\), let \(f\colon \{ 0,1\} ^n\to \mathbb {R}\) be any Boolean function, and let \(\rho \in \mathbb {R}\) satisfy \(\rho ^2\le 1\). Writing \(T_\rho \) for the noise operator, so that \(T_\rho f(x)=\sum _{S\subseteq [n]}\rho ^{|S|}\, \hat f(S)\, \chi _S(x)\), one has
where the expectation is taken with respect to the uniform measure on \(\{ 0,1\} ^n\). Here the Walsh characters are \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) and the Fourier coefficients are \(\widehat f(S)=\mathbb {E}[f\chi _S]\), with uniform expectation.
For every natural number \(k \ge 1\) and every natural number \(j\) with \(j \le k\), the inequality
holds.
Let \(q\) be a natural number and let \(f:\{ 0,1\} ^{n+1}\to \mathbb {R}\) be a Boolean function. Write \(g\) for the average of \(f\) over its last coordinate and \(h\) for the half-difference of \(f\) over its last coordinate, defined by \(g(x)=(f(x,0)+f(x,1))/2\) and \(h(x)=(f(x,0)-f(x,1))/2\) on \(\{ 0,1\} ^n\). Then the \(q\)-th moment of \(f\) under the uniform measure on \(\{ 0,1\} ^{n+1}\) decomposes as
where the expectation on the right is taken over the uniform measure on \(\{ 0,1\} ^n\).
Let \(f:\{ 0,1\} ^{n+1}\to \mathbb {R}\) be a Boolean function, let \(\rho \in \mathbb {R}\), and let \(q\) be a nonnegative integer. Write \(A\) for the average of \(f\) over its last coordinate and \(D\) for the half-difference of \(f\) over its last coordinate, defined by \(A(x)=(f(x,0)+f(x,1))/2\) and \(D(x)=(f(x,0)-f(x,1))/2\) on \(\{ 0,1\} ^n\). Then the \(q\)-th moment of \(T_\rho f\) over the uniform measure on \(\{ 0,1\} ^{n+1}\) decomposes as
where on the right-hand side the noise operator acts on functions of \(n\) variables. For \(d\in \mathbb N\), \(h:\{ 0,1\} ^d\to \mathbb {R}\), and \(\tau \in \mathbb {R}\), the spectral noise operator is \(T_\tau h(x)=\sum _{S\subseteq [d]}\tau ^{|S|}\widehat h(S)\chi _S(x)\), where \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) and \(\widehat h(S)=\mathbb {E}[h\chi _S]\) under the uniform measure.
Fix an integer \(k \ge 1\) and a real number \(\rho \) with \(\rho ^2 \le \dfrac {1}{2k-1}\). Then for every function \(f : \{ 0,1\} ^n \to \mathbb {R}\) on the Boolean hypercube,
where the expectation is taken under the uniform measure on \(\{ 0,1\} ^n\) and \(T_\rho \) is the noise operator \(T_\rho f = \sum _{S \subseteq [n]} \rho ^{|S|}\, \hat f(S)\, \chi _S\). Equivalently, \(\lVert T_\rho f\rVert _{2k} \le \lVert f\rVert _2\). Here the Walsh characters are \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) and the Fourier coefficients are \(\widehat f(S)=\mathbb {E}[f\chi _S]\), with uniform expectation.
Let \(q \ge 2\) be an even integer, and let \(\rho \in \mathbb {R}\) satisfy \(\rho ^2 \le \tfrac {1}{q-1}\). Then for every Boolean function \(f : \{ 0,1\} ^n \to \mathbb {R}\), the noise operator \(T_\rho \) contracts from \(L^2\) to \(L^q\) in the sense that
where both expectations are taken with respect to the uniform measure on \(\{ 0,1\} ^n\). For \(d\in \mathbb N\), \(h:\{ 0,1\} ^d\to \mathbb {R}\), and \(\tau \in \mathbb {R}\), the spectral noise operator is \(T_\tau h(x)=\sum _{S\subseteq [d]}\tau ^{|S|}\widehat h(S)\chi _S(x)\), where \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) and \(\widehat h(S)=\mathbb {E}[h\chi _S]\) under the uniform measure.
Let \(\rho \in \mathbb {R}\) satisfy \(\rho ^2\le 1\), and let \(f:\{ 0,1\} ^n\to \mathbb {R}\) be a Boolean function. Then the noise operator \(T_\rho \) does not increase the \(L^2\) norm under the uniform measure:
For \(d\in \mathbb N\), \(h:\{ 0,1\} ^d\to \mathbb {R}\), and \(\tau \in \mathbb {R}\), the spectral noise operator is \(T_\tau h(x)=\sum _{S\subseteq [d]}\tau ^{|S|}\widehat h(S)\chi _S(x)\), where \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) and \(\widehat h(S)=\mathbb {E}[h\chi _S]\) under the uniform measure.
Let \(\rho \in \mathbb {R}\) satisfy \(\rho ^2\le \tfrac 15\), and let \(f:\{ 0,1\} ^n\to \mathbb {R}\) be any Boolean function. Then the sixth moment of the noised function \(T_\rho f\) is controlled by the cube of the second moment of \(f\):
where both expectations are taken with respect to the uniform measure on \(\{ 0,1\} ^n\). For \(d\in \mathbb N\), \(h:\{ 0,1\} ^d\to \mathbb {R}\), and \(\tau \in \mathbb {R}\), the spectral noise operator is \(T_\tau h(x)=\sum _{S\subseteq [d]}\tau ^{|S|}\widehat h(S)\chi _S(x)\), where \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) and \(\widehat h(S)=\mathbb {E}[h\chi _S]\) under the uniform measure.
Fix an integer \(k \ge 1\) and a real noise rate \(\rho \) satisfying \(\rho ^2 \le \tfrac {1}{2k-1}\). Then for every Boolean function \(f\colon \{ 0,1\} ^n\to \mathbb {R}\), the image \(T_\rho f\) under the noise operator obeys the \(L^2\)-to-\(L^{2k}\) hypercontractive bound
where the expectation is taken with respect to the uniform measure on \(\{ 0,1\} ^n\). For \(d\in \mathbb N\), \(h:\{ 0,1\} ^d\to \mathbb {R}\), and \(\tau \in \mathbb {R}\), the spectral noise operator is \(T_\tau h(x)=\sum _{S\subseteq [d]}\tau ^{|S|}\widehat h(S)\chi _S(x)\), where \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) and \(\widehat h(S)=\mathbb {E}[h\chi _S]\) under the uniform measure.
For a Boolean function \(f : \{ 0,1\} ^n \to \mathbb {R}\), the \(L^2\) inner product of \(f\) with itself equals the expectation of its square: \(\langle f, f\rangle = \mathbb {E}[f^2]\), that is, \(2^{-n}\sum _{x \in \{ 0,1\} ^n} f(x)^2\).
Let \(f\colon \{ 0,1\} ^n\to \mathbb {R}\) be a Boolean function and let \(\rho \in \mathbb {R}\) be arbitrary. Applying the noise operator \(T_\rho \) to \(f\) and averaging the square over the uniform measure gives a nonnegative quantity:
For \(d\in \mathbb N\), \(h:\{ 0,1\} ^d\to \mathbb {R}\), and \(\tau \in \mathbb {R}\), the spectral noise operator is \(T_\tau h(x)=\sum _{S\subseteq [d]}\tau ^{|S|}\widehat h(S)\chi _S(x)\), where \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) and \(\widehat h(S)=\mathbb {E}[h\chi _S]\) under the uniform measure.
Let \(f:\{ 0,1\} ^n\to \mathbb {R}\) be a Boolean function and let \(p\in \mathbb {R}\) be any real exponent. Using \(0^0=1\) and \(0^p=0\) for \(p\ne 0\), including negative \(p\), the expected value of \(\left\lvert f\right\rvert ^p\) under the uniform measure on the hypercube is nonnegative:
For any real parameters \(\rho ,\sigma \) and any Boolean function \(f\colon \{ 0,1\} ^n\to \mathbb {R}\), applying the noise operator \(T_\sigma \) and then the noise operator \(T_\rho \) is the same as applying the single noise operator \(T_{\rho \sigma }\); that is,
For \(d\in \mathbb N\), \(h:\{ 0,1\} ^d\to \mathbb {R}\), and \(\tau \in \mathbb {R}\), the spectral noise operator is \(T_\tau h(x)=\sum _{S\subseteq [d]}\tau ^{|S|}\widehat h(S)\chi _S(x)\), where \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) and \(\widehat h(S)=\mathbb {E}[h\chi _S]\) under the uniform measure.
Let \(1 \lt p\) and \(q \ge 2\) be conjugate exponents, so that \(1/p + 1/q = 1\), let \(\rho \in \mathbb {R}\), and let \(f : \{ 0,1\} ^n \to \mathbb {R}\) be a Boolean function; write \(\lVert g\rVert _r = (\mathbb {E}[\left\lvert g\right\rvert ^r])^{1/r}\) for the \(L^r\) norm under the uniform measure on the hypercube. Suppose Hölder’s inequality holds for the exponent pair \((p,q)\), that is, \(\langle u, v\rangle \le \lVert u\rVert _p\, \lVert v\rVert _q\) for all Boolean functions \(u,v\), and suppose the noise operator satisfies the \((2,q)\) bound \(\mathbb {E}\bigl[\left\lvert T_\rho g\right\rvert ^q\bigr] \le \bigl(\mathbb {E}[g^2]\bigr)^{q/2}\) for every Boolean function \(g\). Then \(T_\rho \) satisfies the dual \((p,2)\) bound
For \(d\in \mathbb N\), \(h:\{ 0,1\} ^d\to \mathbb {R}\), and \(\tau \in \mathbb {R}\), the spectral noise operator is \(T_\tau h(x)=\sum _{S\subseteq [d]}\tau ^{|S|}\widehat h(S)\chi _S(x)\), where \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) and \(\widehat h(S)=\mathbb {E}[h\chi _S]\) under the uniform measure.