18 Boolean Analysis — Simple
18.1 Overview
This module develops the “simple” hypercontractivity results for real-valued Boolean functions \(f : \{ 0,1\} ^n \to \mathbb {R}\), that is, the results obtainable by direct induction on coordinates without the full general machinery. It builds up the \((2,4)\), \((4/3,2)\), \((2,2k)\), and \((p,2)\) hypercontractivity inequalities for the noise operator \(T_\rho \), together with the supporting character, cardinality, Fourier, and combinatorial lemmas used along the way.
18.2 Declarations
For a subset \(S \subseteq \mathrm{Fin}\, n\), a point \(x \in \{ 0,1\} ^n\), and a bit \(b\), the parity character of the lifted set equals the character of \(S\) on \(x\):
That is, appending a last coordinate \(b\) and not including it in the set leaves the character unchanged.
For \(S \subseteq \mathrm{Fin}\, n\), a point \(x\), and a bit \(b\), adjoining the last coordinate to the lifted set multiplies the character by the sign of \(b\):
where \((-1)^b\) denotes boolToSign \(b\).
For any \(\varphi \) on subsets of \(\mathrm{Fin}(n+1)\), the total sum splits according to whether the last coordinate belongs to the subset:
Lifting a set along \(\mathrm{castSucc}\) preserves its cardinality: \(|\mathrm{castSucc}(S)| = |S|\).
Adjoining the (necessarily new) last coordinate to a lifted set increases its cardinality by one: \(|\mathrm{castSucc}(S)\cup \{ \mathrm{last}\, n\} | = |S| + 1\).
For \(f : \{ 0,1\} ^{n+1} \to \mathbb {R}\) the noise operator splits over the last coordinate:
where \(\mathrm{avgLast}\, f\) and \(\mathrm{diffLast}\, f\) are the average and difference of \(f\) over the last bit.
For \(f : \{ 0,1\} ^{n+1} \to \mathbb {R}\), writing \(g = \mathrm{avgLast}\, f\) and \(h = \mathrm{diffLast}\, f\), the fourth moment of \(T_\rho f\) decomposes as
For any Boolean function \(f : \{ 0,1\} ^n \to \mathbb {R}\) and noise parameter \(\rho \) with \(\rho ^2 \le 1/3\) (equivalently \(\left\lvert \rho \right\rvert \le 1/\sqrt3\)),
that is \(\lVert T_\rho f\rVert _4 \le \lVert f\rVert _2\).
For Boolean functions \(f, g\),
Boolean functions are \((4/3, 2)\)-hypercontractive with parameter \(1/\sqrt3\): for any \(f : \{ 0,1\} ^n \to \mathbb {R}\),
The squared \(L^2\) norm of \(T_\rho f\) expands over the Fourier spectrum:
For \(\rho ^2 \le 1\) and any Boolean function \(f\),
This is the \(q = 2\) case of hypercontractivity.
For natural numbers \(k \ge 1\) and \(j \le k\),
For \(f : \{ 0,1\} ^{n+1} \to \mathbb {R}\), writing \(g = \mathrm{avgLast}\, f\) and \(h = \mathrm{diffLast}\, f\), the \(q\)-th moment decomposes as
For \(f : \{ 0,1\} ^{n+1} \to \mathbb {R}\), writing \(g = T_\rho (\mathrm{avgLast}\, f)\) and \(h = T_\rho (\mathrm{diffLast}\, f)\), the \(q\)-th moment of \(T_\rho f\) decomposes as
For any Boolean function \(f : \{ 0,1\} ^n \to \mathbb {R}\), integer \(k \ge 1\), and noise parameter \(\rho \) with \(\rho ^2 \le 1/(2k-1)\),
equivalently \(\lVert T_\rho f\rVert _{2k} \le \lVert f\rVert _2\).
For an even integer \(q \ge 2\) and noise parameter \(\rho \) with \(\rho ^2 \le 1/(q-1)\),
This is the \((2,2k)\) theorem restated in terms of an even exponent \(q = 2k\).
For \(\rho ^2 \le 1\) and any Boolean function \(f\),
the \(q = 2\) instance, which is just contractivity.
For \(\rho ^2 \le 1/5\) and any Boolean function \(f\),
For \(k \ge 1\) and noise parameter \(\rho \) with \(\rho ^2 \le 1/(2k-1)\), the \((2,2k)\) bound in the form \(\lVert T_\rho f\rVert _{2k} \le \lVert f\rVert _2\):
The self inner product of a Boolean function equals the expectation of its square: \(\langle f, f \rangle = \mathbb {E}[f^2]\).
For any \(\rho \) and Boolean function \(f\), \(\mathbb {E}[(T_\rho f)^2] \ge 0\).
For any real exponent \(p\) and Boolean function \(f\), \(\mathbb {E}[\, \left\lvert f\right\rvert ^p\, ] \ge 0\).
Composing two noise operators multiplies their parameters: \(T_\rho (T_\sigma f) = T_{\rho \sigma } f\).
Let \(1 \lt p\), \(q \ge 2\) with \(1/p + 1/q = 1\). Given a Hölder inequality for the pair \((p,q)\) and a \((2,q)\)-hypercontractivity bound for \(T_\rho \), one concludes the dual \((p,2)\) bound:
18.3 Additional declarations
Let \(a, b, A, B, C, \rho \) be reals with \(a \ge 0\), \(b \ge 0\), \(B \ge 0\), and suppose \(A \le a^2\), \(B \le b^2\), \(C^2 \le AB\), and \(\rho ^2 \le 1/3\). Then
This is the algebraic step that makes the induction in the \((2,4)\)-hypercontractivity argument close.