270 Boolean Analysis — Fourth Moment

270.1 Overview

Coordinate decompositions establish the second-to-fourth hypercontractive estimate and its dual fourth-thirds-to-second estimate. Fourier character identities and finite-sum inequalities give the supporting statements.

270.2 Declarations

Lemma 270.1 Walsh character is unchanged by appending an unused coordinate

✓

Fix \(n\in \mathbb {N}\), and let \(S\subseteq [n]\), \(x\in \{ 0,1\} ^n\), and \(b\in \{ 0,1\} \). Form the point \((x,b)\in \{ 0,1\} ^{n+1}\) obtained by appending \(b\) as the final coordinate, and regard \(S\) as a subset \(S'\subseteq [n+1]\) via the inclusion \([n]\hookrightarrow [n+1]\) that leaves each index fixed (so the new last coordinate never lies in \(S'\)). Then the Walsh–Fourier character of \(S'\) evaluated at the extended point agrees with that of \(S\) at the original point:

\[ \chi _{S'}\big((x,b)\big) \; =\; \chi _S(x). \]

Lemma 270.2 Walsh character on an extended coordinate set

✓

Let \(S \subseteq [n]\), let \(x \in \{ 0,1\} ^n\), and let \(b\) be a bit. Write \((x,b) \in \{ 0,1\} ^{n+1}\) for the point obtained by appending \(b\) as the final coordinate, and let \(S' \subseteq [n+1]\) be the image of \(S\) under the inclusion \([n] \hookrightarrow [n+1]\) of the first \(n\) coordinates, together with the new last coordinate \(n+1\). Then

\[ \chi _{S'}(x,b) \; =\; \sigma (b)\, \chi _S(x), \]

where \(\sigma (0)=1\) and \(\sigma (1)=-1\); that is, adjoining the last coordinate to the lifted index set multiplies the Walsh character by the sign of \(b\).

Lemma 270.3 Splitting a subset-sum by the last coordinate

✓

Fix \(n \in \mathbb {N}\) and identify a subset of \(\{ 0, 1, \dots , n\} \) that omits the top element \(n\) with the corresponding subset of \(\{ 0, 1, \dots , n-1\} \), via the inclusion \(\iota \) that sends \(T \subseteq \{ 0,\dots ,n-1\} \) to the same set regarded inside \(\{ 0,\dots ,n\} \). Then for every function \(\varphi \) assigning a real number to each subset of \(\{ 0, 1, \dots , n\} \),

\[ \sum _{S \subseteq \{ 0,\dots ,n\} } \varphi (S) = \sum _{T \subseteq \{ 0,\dots ,n-1\} } \varphi \bigl(\iota (T)\bigr) + \sum _{T \subseteq \{ 0,\dots ,n-1\} } \varphi \bigl(\iota (T) \cup \{ n\} \bigr), \]

the two terms collecting the subsets of \(\{ 0,\dots ,n\} \) that exclude and that include the element \(n\), respectively.

Lemma 270.4 Cardinality is preserved under the successor inclusion

✓

Let \(S \subseteq \{ 0, 1, \dots , n-1\} \) be a finite set of indices, and let \(\iota \colon \{ 0, 1, \dots , n-1\} \hookrightarrow \{ 0, 1, \dots , n\} \) be the order-preserving inclusion that regards each index as an element of the enlarged range. Then the image \(\iota (S)\) has the same cardinality as \(S\), that is, \(\left\lvert \iota (S)\right\rvert = \left\lvert S\right\rvert \).

Lemma 270.5 Cardinality after lifting a set and adjoining the top coordinate

✓

Let \(n\) be a natural number and let \(S \subseteq \{ 0, 1, \dots , n-1\} \). Embed \(S\) into \(\{ 0, 1, \dots , n\} \) by the map that sends each index to itself, and adjoin the top index \(n\). Since \(n\) is not the image of any element of \(S\), this union satisfies

\[ \left\lvert \{ \, i : i \in S \, \} \cup \{ n\} \right\rvert = \left\lvert S\right\rvert + 1. \]

Lemma 270.6 Noise operator splits along the last coordinate

✓

Fix \(\rho \in \mathbb {R}\) and a Boolean function \(f \colon \{ 0,1\} ^{n+1} \to \mathbb {R}\), and let \(Af\) and \(Df\) be the average and the half-difference of \(f\) over its last coordinate, each a Boolean function on \(\{ 0,1\} ^n\), with \(Af(x)=(f(x,0)+f(x,1))/2\) and \(Df(x)=(f(x,0)-f(x,1))/2\). For every \(x \in \{ 0,1\} ^n\) and every bit \(b\),

\[ T_\rho f(x, b) \; =\; T_\rho (Af)(x) \; +\; \sigma (b)\, \rho \, T_\rho (Df)(x), \]

where \((x,b) \in \{ 0,1\} ^{n+1}\) is the point obtained by appending \(b\) as the last coordinate, \(\sigma (0)=1\), \(\sigma (1)=-1\), and \(T_\rho \) is the noise operator. 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.

Lemma 270.7 Fourth-moment decomposition under the noise operator

✓

Let \(f:\{ 0,1\} ^{n+1}\to \mathbb {R}\) be a Boolean function, and let \(\rho \in \mathbb {R}\). Write \(g\) for the average of \(f\) over its last coordinate and \(h\) for the corresponding half-difference, so that

\[ g(x)=\tfrac 12\bigl(f(x,0)+f(x,1)\bigr),\qquad h(x)=\tfrac 12\bigl(f(x,0)-f(x,1)\bigr) \]

are Boolean functions of the first \(n\) variables. Then the fourth moment of \(T_\rho f\) under the uniform measure decomposes as

\[ \mathbb {E}\bigl[(T_\rho f)^4\bigr] = \mathbb {E}\bigl[(T_\rho g)^4\bigr] + 6\rho ^2\, \mathbb {E}\bigl[(T_\rho g)^2\, (T_\rho h)^2\bigr] + \rho ^4\, \mathbb {E}\bigl[(T_\rho h)^4\bigr]. \]

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.

Lemma 270.8 A quadratic inequality from bound data

✓

Let \(a,b,A,B,C,\rho \) be real numbers with \(a\ge 0\), \(b\ge 0\), and \(B\ge 0\), and suppose that \(A\le a^2\), \(B\le b^2\), \(C^2\le AB\), and \(\rho ^2\le \tfrac 13\). Then

\[ A + 6\rho ^2 C + \rho ^4 B \; \le \; (a+b)^2 . \]

Theorem 270.9 The \((2,4)\)-hypercontractive inequality

✓

Let \(f:\{ 0,1\} ^n\to \mathbb {R}\) be a Boolean function and let \(\rho \in \mathbb {R}\) be a noise parameter satisfying \(\rho ^2\le 1/3\). Then the fourth moment of the noised function is controlled by the square of its second moment:

\[ \mathbb {E}\bigl[(T_\rho f)^4\bigr]\; \le \; \bigl(\mathbb {E}[f^2]\bigr)^2, \]

where \(T_\rho \) is the noise operator and \(\mathbb {E}\) denotes expectation under the uniform measure on \(\{ 0,1\} ^n\). Equivalently, \(\lVert T_\rho f\rVert _4\le \lVert f\rVert _2\). 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.

Lemma 270.10 Hölder’s inequality for the exponents \(4/3\) and \(4\)

✓

Let \(f, g : \{ 0,1\} ^n \to \mathbb {R}\) be Boolean functions, and take all expectations with respect to the uniform measure on \(\{ 0,1\} ^n\). Then their \(L^2\) inner product satisfies

\[ \langle f, g \rangle \; \le \; \bigl(\mathbb {E}[\, \left\lvert f\right\rvert ^{4/3}\, ]\bigr)^{3/4}\, \bigl(\mathbb {E}[\, \left\lvert g\right\rvert ^{4}\, ]\bigr)^{1/4}. \]

Theorem 270.11 The \((4/3,2)\)-hypercontractive inequality at \(\rho =1/\sqrt3\)

✓

For every Boolean function \(f:\{ 0,1\} ^n\to \mathbb {R}\), applying the noise operator with parameter \(\rho =1/\sqrt3\) contracts the \(L^2\) norm below the \(L^{4/3}\) norm of the original function:

\[ \bigl(\mathbb {E}\bigl[(T_{1/\sqrt3} f)^2\bigr]\bigr)^{1/2} \; \le \; \bigl(\mathbb {E}\bigl[\, \left\lvert f\right\rvert ^{4/3}\, \bigr]\bigr)^{3/4}, \]

where both expectations are taken under the uniform measure on the hypercube. 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.