121 Boolean Analysis — General Hypercontractivity
121.1 Overview
This module lifts one-bit hypercontractivity to the \(n\)-dimensional cube. It introduces the \(\rho \)-correlated noise kernel \(K_\rho \), rewrites the noise operator \(T_\rho \) and the inner product \(\left\langle f, T_\rho g \right\rangle \) as kernel-weighted sums, and proves an induction theorem saying that a two-function hypercontractive bound on one bit propagates to all \(n\). Building on the associated two-point inequalities, it derives the low-norms, bridging, and high-norms one-function hypercontractivity theorems, and finally the general one-function and two-function hypercontractivity theorems.
121.2 Declarations
121.2.1 The noise kernel
Definition
121.1
Noise kernel of \(\rho \)-correlated pairs
For \(\rho \in \mathbb {R}\) and \(x, y\) in the cube \(\mathrm{BoolCube}\, n\), the noise kernel is
\[ K_\rho (x,y) \; =\; \prod _{i} \frac{1 + \rho \, \chi (x_i)\, \chi (y_i)}{2}, \]
where \(\chi (\cdot )\) is the \(\pm 1\) encoding of a bit. It is the transition probability from \(x\) to \(y\) under \(\rho \)-correlated noise.
Lemma
121.2
Nonnegativity of the noise kernel
If \(0 \le \rho \le 1\) then \(K_\rho (x,y) \ge 0\) for all \(x, y \in \mathrm{BoolCube}\, n\).
Lemma
121.3
Fourier form of the kernel product
For all \(\rho \in \mathbb {R}\) and \(x, y \in \mathrm{BoolCube}\, n\),
\[ \sum _{S \subseteq [n]} \rho ^{\left\lvert S\right\rvert }\, \chi _S(x)\, \chi _S(y) \; =\; \prod _{i} \bigl(1 + \rho \, \chi (x_i)\, \chi (y_i)\bigr). \]
Lemma
121.4
Noise operator as a kernel sum
For every \(g : \mathrm{BoolCube}\, n \to \mathbb {R}\) and every \(x\),
\[ (T_\rho g)(x) \; =\; \sum _{y} K_\rho (x,y)\, g(y). \]
Lemma
121.5
Inner product as a kernel-weighted double sum
For all \(f, g : \mathrm{BoolCube}\, n \to \mathbb {R}\),
\[ \left\langle f, T_\rho g \right\rangle \; =\; \frac{1}{2^n} \sum _{x} \sum _{y} K_\rho (x,y)\, f(x)\, g(y). \]
Lemma
121.6
Monotonicity of kernel-weighted expectations
Let \(0 \le \rho \le 1\) and let \(h, h' : \mathrm{BoolCube}\, n \times \mathrm{BoolCube}\, n \to \mathbb {R}\) satisfy \(h(x,y) \le h'(x,y)\) for all \(x, y\). Then the kernel-weighted average of \(h\) is at most that of \(h'\):
\[ \frac{1}{2^n}\sum _{x}\sum _{y} K_\rho (x,y)\, h(x,y) \; \le \; \frac{1}{2^n}\sum _{x}\sum _{y} K_\rho (x,y)\, h'(x,y). \]
Lemma
121.7
Factorization of the kernel along the last coordinate
For \(x', y' \in \mathrm{BoolCube}\, n\) and bits \(b, b'\),
\[ K_\rho \bigl(\mathrm{snoc}(x',b),\ \mathrm{snoc}(y',b')\bigr) \; =\; K_\rho (x',y') \cdot \frac{1 + \rho \, \chi (b)\, \chi (b')}{2}. \]
121.2.2 Fubini-style decompositions
Lemma
121.8
Expectation on \(n+1\) bits as an iterated expectation
For \(h : \mathrm{BoolCube}\, (n+1) \to \mathbb {R}\),
\[ \mathbb {E}[h] \; =\; \mathbb {E}_{x'}\Bigl[\tfrac 12\bigl(h(\mathrm{snoc}(x',\mathit{false})) + h(\mathrm{snoc}(x',\mathit{true}))\bigr)\Bigr], \]
the outer expectation being over \(x' \in \mathrm{BoolCube}\, n\).
Lemma
121.9
Collapse of the \(p\)-th moment along the last bit
For \(p \gt 0\) and \(f : \mathrm{BoolCube}\, (n+1) \to \mathbb {R}\),
\[ \mathbb {E}\bigl[\left\lvert f\right\rvert ^p\bigr] \; =\; \mathbb {E}_{x'}\Bigl[\tfrac 12\bigl(\left\lvert f(\mathrm{snoc}(x',\mathit{false}))\right\rvert ^p + \left\lvert f(\mathrm{snoc}(x',\mathit{true}))\right\rvert ^p\bigr)\Bigr]. \]
Lemma
121.10
Decomposition of the kernel-weighted sum at dimension \(n+1\)
For \(F : \mathrm{BoolCube}\, (n+1) \times \mathrm{BoolCube}\, (n+1) \to \mathbb {R}\), the kernel-weighted bilinear average at dimension \(n+1\) equals the \(n\)-dimensional kernel-weighted average of the one-bit average of the last coordinate:
\[ \frac{1}{2^{n+1}}\sum _{x}\sum _{y} K_\rho (x,y)\, F(x,y) = \frac{1}{2^{n}}\sum _{x'}\sum _{y'} K_\rho (x',y')\, \Bigl[\tfrac 12 \sum _{b}\sum _{b'} \tfrac {1+\rho \, \chi (b)\chi (b’)}{2}\, F(\mathrm{snoc}(x',b), \mathrm{snoc}(y',b'))\Bigr]. \]
Lemma
121.11
One-bit slice sum as a one-bit inner product
Fix \(x', y' \in \mathrm{BoolCube}\, n\) and \(f, g : \mathrm{BoolCube}\, (n+1) \to \mathbb {R}\). The one-bit kernel-weighted sum of the slices of \(f\) at \(x'\) and of \(g\) at \(y'\) equals the one-bit inner product of those slices against the noise operator:
\[ \tfrac 12 \sum _{b}\sum _{b'} \tfrac {1+\rho \, \chi (b)\chi (b’)}{2}\, f(\mathrm{snoc}(x',b))\, g(\mathrm{snoc}(y',b')) \; =\; \left\langle f_{x'}, T_\rho g_{y'} \right\rangle , \]
where \(f_{x'}(t) = f(\mathrm{snoc}(x', t_0))\) and \(g_{y'}(t) = g(\mathrm{snoc}(y', t_0))\) are functions on \(\mathrm{BoolCube}\, 1\).
Lemma
121.12
\(L^p\) norm of a one-bit slice
For \(p \gt 0\), \(f : \mathrm{BoolCube}\, (n+1) \to \mathbb {R}\) and \(x' \in \mathrm{BoolCube}\, n\),
\[ \Bigl(\mathbb {E}_{t \in \mathrm{BoolCube}\, 1}\bigl[\left\lvert f(\mathrm{snoc}(x',t_0))\right\rvert ^p\bigr]\Bigr)^{1/p} \; =\; \Bigl(\tfrac {\left\lvert f(\mathrm{snoc}(x’,\mathit{false}))\right\rvert ^p + \left\lvert f(\mathrm{snoc}(x’,\mathit{true}))\right\rvert ^p}{2}\Bigr)^{1/p}. \]
Lemma
121.13
Norm collapse, clean form
For \(p \ge 1\) and \(f : \mathrm{BoolCube}\, (n+1) \to \mathbb {R}\),
\[ \mathbb {E}_{x'}\Bigl[\tfrac {\left\lvert f(\mathrm{snoc}(x’,\mathit{false}))\right\rvert ^p + \left\lvert f(\mathrm{snoc}(x’,\mathit{true}))\right\rvert ^p}{2}\Bigr] \; =\; \mathbb {E}\bigl[\left\lvert f\right\rvert ^p\bigr]. \]
121.2.3 Hölder and contraction bounds
Lemma
121.14
Hölder inequality for Boolean functions
For \(p \gt 1\) and \(f, h : \mathrm{BoolCube}\, n \to \mathbb {R}\),
\[ \left\langle f, h \right\rangle \; \le \; \bigl(\mathbb {E}[\left\lvert f\right\rvert ^p]\bigr)^{1/p} \cdot \bigl(\mathbb {E}[\left\lvert h\right\rvert ^{p/(p-1)}]\bigr)^{(p-1)/p}. \]
Lemma
121.15
\(L^q\) contractivity of the noise operator on one bit
For \(q \ge 1\), \(0 \le \rho \le 1\) and \(g : \mathrm{BoolCube}\, 1 \to \mathbb {R}\),
\[ \bigl(\mathbb {E}[\left\lvert T_\rho g\right\rvert ^q]\bigr)^{1/q} \; \le \; \bigl(\mathbb {E}[\left\lvert g\right\rvert ^q]\bigr)^{1/q}, \]
i.e. \(T_\rho \) is a contraction in \(L^q\) on one bit.
121.2.4 Induction from one bit to \(n\) bits
Lemma
121.16
Two-function hypercontractivity in dimension zero
For \(p, q \ge 1\), any \(\rho \in \mathbb {R}\), and \(f, g : \mathrm{BoolCube}\, 0 \to \mathbb {R}\),
\[ \left\langle f, T_\rho g \right\rangle \; \le \; \bigl(\mathbb {E}[\left\lvert f\right\rvert ^p]\bigr)^{1/p}\, \bigl(\mathbb {E}[\left\lvert g\right\rvert ^q]\bigr)^{1/q}. \]
Lemma
121.17
Inductive step for two-function hypercontractivity
Let \(p, q \ge 1\) and \(0 \le \rho \le 1\). If the bound \(\left\langle f, T_\rho g \right\rangle \le (\mathbb {E}[\left\lvert f\right\rvert ^p])^{1/p}(\mathbb {E}[\left\lvert g\right\rvert ^q])^{1/q}\) holds for all pairs of functions on one bit and for all pairs of functions on \(n\) bits, then it holds for all \(f, g : \mathrm{BoolCube}\, (n+1) \to \mathbb {R}\).
Theorem
121.18
Two-function hypercontractivity induction theorem
Let \(p, q \ge 1\) and \(0 \le \rho \le 1\). If \(\left\langle f, T_\rho g \right\rangle \le (\mathbb {E}[\left\lvert f\right\rvert ^p])^{1/p}(\mathbb {E}[\left\lvert g\right\rvert ^q])^{1/q}\) holds for all \(f, g : \mathrm{BoolCube}\, 1 \to \mathbb {R}\), then the same bound holds for all \(n\) and all \(f, g : \mathrm{BoolCube}\, n \to \mathbb {R}\).
121.2.5 Weak two-function hypercontractivity
Theorem
121.19
Weak two-function hypercontractivity on a single bit
For \(1 \le p \le 2\), \(1 \le q \le 2\) and \(f, g : \mathrm{BoolCube}\, 1 \to \mathbb {R}\), with \(\rho = \sqrt{(p-1)(q-1)}\),
\[ \left\langle f, T_\rho g \right\rangle \; \le \; \bigl(\mathbb {E}[\left\lvert f\right\rvert ^p]\bigr)^{1/p}\, \bigl(\mathbb {E}[\left\lvert g\right\rvert ^q]\bigr)^{1/q}. \]
Theorem
121.20
Equivalence of one- and two-function hypercontractivity
Let \(1 \le p \le q\) with \(q \ge 2\), and let \(0 \le \rho \le 1\) satisfy \(\rho \le \sqrt{(p-1)/(q-1)}\). Then the one-function bound
\[ \bigl(\mathbb {E}[\left\lvert T_\rho f\right\rvert ^q]\bigr)^{1/q} \le \bigl(\mathbb {E}[\left\lvert f\right\rvert ^p]\bigr)^{1/p} \qquad \text{for all } f \]
holds if and only if the dual two-function bound
\[ \left\langle f, T_\rho g \right\rangle \le \bigl(\mathbb {E}[\left\lvert f\right\rvert ^{q/(q-1)}]\bigr)^{(q-1)/q}\, \bigl(\mathbb {E}[\left\lvert g\right\rvert ^p]\bigr)^{1/p} \qquad \text{for all } f, g \]
holds.
Theorem
121.21
Weak two-function hypercontractivity
For \(1 \le p \le 2\), \(1 \le q \le 2\), any \(n\), and \(f, g : \mathrm{BoolCube}\, n \to \mathbb {R}\), with \(\rho = \sqrt{(p-1)(q-1)}\),
\[ \left\langle f, T_\rho g \right\rangle \; \le \; \bigl(\mathbb {E}[\left\lvert f\right\rvert ^p]\bigr)^{1/p}\, \bigl(\mathbb {E}[\left\lvert g\right\rvert ^q]\bigr)^{1/q}. \]
121.2.6 Stochasticity of the kernel and trivial contractivity
Lemma
121.22
Kernel rows sum to one
For \(0 \le \rho \le 1\) and any fixed \(x \in \mathrm{BoolCube}\, n\), \(\sum _{y} K_\rho (x,y) = 1\).
Lemma
121.23
Kernel columns sum to one
For \(0 \le \rho \le 1\) and any fixed \(y \in \mathrm{BoolCube}\, n\), \(\sum _{x} K_\rho (x,y) = 1\).
Lemma
121.24
Jensen bound for powers of the noise operator
For \(0 \le \rho \le 1\), \(s \ge 1\), \(f : \mathrm{BoolCube}\, n \to \mathbb {R}\) and any \(x\),
\[ \left\lvert (T_\rho f)(x)\right\rvert ^s \; \le \; \sum _{y} K_\rho (x,y)\, \left\lvert f(y)\right\rvert ^s. \]
Lemma
121.25
Trivial contractivity of the noise operator
For \(s \ge 1\), \(0 \le \rho \le 1\) and \(f : \mathrm{BoolCube}\, n \to \mathbb {R}\),
\[ \bigl(\mathbb {E}[\left\lvert T_\rho f\right\rvert ^s]\bigr)^{1/s} \; \le \; \bigl(\mathbb {E}[\left\lvert f\right\rvert ^s]\bigr)^{1/s}. \]
Lemma
121.26
Duality of noise-operator norm bounds
For \(p, q \gt 1\) and \(0 \le \rho \le 1\), the \((p \to q)\) bound
\[ \bigl(\mathbb {E}[\left\lvert T_\rho f\right\rvert ^q]\bigr)^{1/q} \le \bigl(\mathbb {E}[\left\lvert f\right\rvert ^p]\bigr)^{1/p} \qquad \text{for all } f \]
holds if and only if the bound for the Hölder-conjugate exponents holds:
\[ \bigl(\mathbb {E}[\left\lvert T_\rho f\right\rvert ^{p/(p-1)}]\bigr)^{(p-1)/p} \le \bigl(\mathbb {E}[\left\lvert f\right\rvert ^{q/(q-1)}]\bigr)^{(q-1)/q} \qquad \text{for all } f. \]
121.2.7 The bridging case
Lemma
121.27
Square root of a ratio at most one
If \(0 \le a\), \(0 \lt b\) and \(a \le b\), then \(\sqrt{a/b} \le 1\).
Lemma
121.28
Noise-parameter identity
If \(u - 1 \gt 0\), then
\[ \Bigl(\frac{u}{u-1} - 1\Bigr)(p-1) \; =\; \frac{p-1}{u-1}. \]
Theorem
121.29
Bridging case of one-function hypercontractivity
For \(1 \le p \le 2 \le u\), \(f : \mathrm{BoolCube}\, n \to \mathbb {R}\), and \(\rho = \sqrt{(p-1)/(u-1)}\),
\[ \bigl(\mathbb {E}[\left\lvert T_\rho f\right\rvert ^u]\bigr)^{1/u} \; \le \; \bigl(\mathbb {E}[\left\lvert f\right\rvert ^p]\bigr)^{1/p}. \]
121.2.8 Real analytic ingredients for the low-norms case
Lemma
121.30
Interpolation parameters for the low-norms case
Let \(1 \lt p \lt u \lt 2\) and \(\rho ^2 = (p-1)/(u-1)\). Then there exist \(\theta \in (0,1)\) and \(s \gt 0\) with
\[ \frac1p = \frac{\theta }{1+\rho ^2} + \frac{1-\theta }{s} \qquad \text{and}\qquad \frac1u = \frac{\theta }{2} + \frac{1-\theta }{s}. \]
Lemma
121.31
Symmetric power average is at least one
For \(p \ge 1\) and \(b \in [0,1]\),
\[ 1 \; \le \; \frac{(1+b)^p + (1-b)^p}{2}. \]
Lemma
121.32
Monotonicity of symmetric convex sums
If \(f\) is convex on \([0,\infty )\) and \(0 \le x \le y \le 1\), then
\[ f(1+x) + f(1-x) \; \le \; f(1+y) + f(1-y). \]
Lemma
121.33
Antitonicity in the exponent for nonpositive powers
For \(0 \lt x \lt 1\) and exponents \(p \le q \le 0\),
\[ (1+x)^p + (1-x)^p \; \ge \; (1+x)^q + (1-x)^q. \]
Lemma
121.34
Two-point derivative inequality
Let \(0 \le r \le s \le 1\), \(c = \sqrt{r/s}\) and \(t \in [0,1]\). Then
\[ (1+t)^r - (1-t)^r \; \ge \; c\bigl((1+ct)^s - (1-ct)^s\bigr). \]
Lemma
121.35
Integrated two-point inequality
Let \(1 \le p \le q \le 2\), \(b \in [0,1]\) and \(\rho = \sqrt{(p-1)/(q-1)}\). Then
\[ \frac{(1+\rho b)^q + (1-\rho b)^q - 2}{q} \; \le \; \frac{(1+b)^p + (1-b)^p - 2}{p}. \]
Lemma
121.36
Tangent line inequality for \(x^r\) at \(x = 1\)
For \(x \ge 0\) and \(r \ge 1\), \(x^r \ge 1 + r(x-1)\).
Theorem
121.37
General two-point inequality, unit case
Let \(1 \le p \le q \le 2\), \(b \in [0,1]\) and \(\rho = \sqrt{(p-1)/(q-1)}\). Then
\[ \frac{(1+\rho b)^q + (1-\rho b)^q}{2} \; \le \; \Bigl(\frac{(1+b)^p + (1-b)^p}{2}\Bigr)^{q/p}. \]
121.2.9 Low, high, and general hypercontractivity
Theorem
121.38
One-bit low-norms hypercontractivity
For \(1 \lt p \le q \le 2\), \(f : \mathrm{BoolCube}\, 1 \to \mathbb {R}\) and \(\rho = \sqrt{(p-1)/(q-1)}\),
\[ \bigl(\mathbb {E}[\left\lvert T_\rho f\right\rvert ^q]\bigr)^{1/q} \; \le \; \bigl(\mathbb {E}[\left\lvert f\right\rvert ^p]\bigr)^{1/p}. \]
Theorem
121.39
Low-norms hypercontractivity
For \(1 \lt p \le u \le 2\), any \(n\), \(f : \mathrm{BoolCube}\, n \to \mathbb {R}\) and \(\rho = \sqrt{(p-1)/(u-1)}\),
\[ \bigl(\mathbb {E}[\left\lvert T_\rho f\right\rvert ^u]\bigr)^{1/u} \; \le \; \bigl(\mathbb {E}[\left\lvert f\right\rvert ^p]\bigr)^{1/p}. \]
Theorem
121.40
High-norms hypercontractivity
For \(2 \le p \le u\), any \(\rho \) with \(0 \le \rho \le 1\) and \(\rho \le \sqrt{(p-1)/(u-1)}\), and \(f : \mathrm{BoolCube}\, n \to \mathbb {R}\),
\[ \bigl(\mathbb {E}[\left\lvert T_\rho f\right\rvert ^u]\bigr)^{1/u} \; \le \; \bigl(\mathbb {E}[\left\lvert f\right\rvert ^p]\bigr)^{1/p}. \]
Theorem
121.41
General one-function hypercontractivity
Let \(1 \le p \le u\) with \(u \gt 1\), and let \(0 \le \rho \le 1\) satisfy \(\rho \le \sqrt{(p-1)/(u-1)}\). Then for every \(f : \mathrm{BoolCube}\, n \to \mathbb {R}\),
\[ \bigl(\mathbb {E}[\left\lvert T_\rho f\right\rvert ^u]\bigr)^{1/u} \; \le \; \bigl(\mathbb {E}[\left\lvert f\right\rvert ^p]\bigr)^{1/p}. \]
Theorem
121.42
General two-function hypercontractivity
Let \(1 \le p \le u\) with \(u \ge 2\), and let \(0 \le \rho \le 1\) satisfy \(\rho \le \sqrt{(p-1)/(u-1)}\). Then for all \(f, g : \mathrm{BoolCube}\, n \to \mathbb {R}\),
\[ \left\langle f, T_\rho g \right\rangle \; \le \; \bigl(\mathbb {E}[\left\lvert f\right\rvert ^{u/(u-1)}]\bigr)^{(u-1)/u}\, \bigl(\mathbb {E}[\left\lvert g\right\rvert ^p]\bigr)^{1/p}. \]