274 Boolean Analysis — Tensorization

274.1 Overview

A one-bit pairing bound tensorizes to arbitrary cube dimension. Holder duality and the one-bit estimates yield the weak two-function hypercontractive inequality.

274.2 Declarations

Lemma 274.1 Hölder’s inequality for Boolean functions

✓

Let \(n\) be a natural number, let \(p \gt 1\) and let \(f, h : \{ 0,1\} ^n \to \mathbb {R}\) be Boolean functions, with expectations taken under the uniform measure on \(\{ 0,1\} ^n\). Then their \(L^2\) inner product satisfies

\[ \langle f, h\rangle \; \le \; \bigl(\mathbb {E}\bigl[\left\lvert f\right\rvert ^{p}\bigr]\bigr)^{1/p}\, \bigl(\mathbb {E}\bigl[\left\lvert h\right\rvert ^{p/(p-1)}\bigr]\bigr)^{(p-1)/p}, \]

where the exponents \(p\) and \(p/(p-1)\) are conjugate.

Lemma 274.2 \(L^q\) contractivity of the one-bit noise operator

✓

Let \(q \ge 1\) and let \(\rho \) be a real number with \(0 \le \rho \le 1\). Then for every Boolean function \(g \colon \{ 0,1\} ^1 \to \mathbb {R}\) on a single bit, the noise operator \(T_\rho \) satisfies

\[ \bigl(\mathbb {E}\! \left[\, \left\lvert T_\rho g\right\rvert ^{\, q}\, \right]\bigr)^{1/q} \; \le \; \bigl(\mathbb {E}\! \left[\, \left\lvert g\right\rvert ^{\, q}\, \right]\bigr)^{1/q}, \]

where both expectations are taken with respect to the uniform measure on \(\{ 0,1\} ^1\). 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 274.3 Two-function hypercontractivity in dimension zero

✓

Let \(p, q \ge 1\) and let \(\rho \in \mathbb {R}\) be arbitrary. For any two Boolean functions \(f, g : \{ 0,1\} ^0 \to \mathbb {R}\) on the zero-dimensional cube, the \(L^2\) inner product of \(f\) with the noise-operator image \(T_\rho g\) satisfies

\[ \langle f, T_\rho g\rangle \; \le \; \bigl(\mathbb {E}\bigl[\left\lvert f\right\rvert ^p\bigr]\bigr)^{1/p}\, \bigl(\mathbb {E}\bigl[\left\lvert g\right\rvert ^q\bigr]\bigr)^{1/q}, \]

where \(\mathbb {E}\) denotes expectation 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.

Lemma 274.4 Inductive step for two-function hypercontractivity

✓

Let \(n\) be a natural number, let \(p,q\in \mathbb {R}\) satisfy \(p,q\ge 1\) and let \(\rho \) satisfy \(0 \le \rho \le 1\), and write \(T_\rho \) for the noise operator with parameter \(\rho \). Suppose the two-function bound

\[ \langle f, T_\rho g\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} \]

holds for every pair of functions \(f, g\) on the one-dimensional cube \(\{ 0,1\} ^1\), and also for every pair of functions on the \(n\)-dimensional cube \(\{ 0,1\} ^n\). Then the same bound holds for every pair of functions \(f, g : \{ 0,1\} ^{n+1} \to \mathbb {R}\). 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.

Theorem 274.5 Tensorization of two-function hypercontractivity

✓

Fix exponents \(p, q \ge 1\) and a noise parameter \(\rho \) with \(0 \le \rho \le 1\), and write \(T_\rho \) for the associated noise operator. Suppose the two-function bound

\[ \langle f, T_\rho g\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} \]

holds for every pair of Boolean functions \(f, g \colon \{ 0,1\} ^1 \to \mathbb {R}\) on the one-dimensional cube. Then, for every \(n\), the same inequality holds for every pair of Boolean functions \(f, g \colon \{ 0,1\} ^n \to \mathbb {R}\). 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.

Theorem 274.6 Weak two-function hypercontractivity on a single bit

✓

Let \(1 \le p \le 2\) and \(1 \le q \le 2\), and set \(\rho = \sqrt{(p-1)(q-1)}\). Then for any two Boolean functions \(f, g : \{ 0,1\} ^1 \to \mathbb {R}\) on a single bit,

\[ \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}, \]

where \(T_\rho \) is the noise operator, \(\mathbb {E}[\cdot ]\) is the expectation, and \(\left\langle \cdot ,\cdot \right\rangle \) is the \(L^2\) inner product, all taken with respect to the uniform measure on \(\{ 0,1\} \). 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.

Theorem 274.7 Equivalence of one- and two-function hypercontractivity

✓

Fix a natural number \(n\). Let \(1 \le p \le q\) with \(q \ge 2\), and let \(\rho \) satisfy \(0 \le \rho \le 1\) together with \(\rho \le \sqrt{(p-1)/(q-1)}\). Then the one-function hypercontractive inequality

\[ \bigl(\mathbb {E}\bigl[\left\lvert T_\rho f\right\rvert ^q\bigr]\bigr)^{1/q} \le \bigl(\mathbb {E}\bigl[\left\lvert f\right\rvert ^p\bigr]\bigr)^{1/p} \qquad \text{for every Boolean function } f \]

holds if and only if the dual two-function inequality

\[ \langle f, T_\rho g\rangle \le \bigl(\mathbb {E}\bigl[\left\lvert f\right\rvert ^{q/(q-1)}\bigr]\bigr)^{(q-1)/q}\, \bigl(\mathbb {E}\bigl[\left\lvert g\right\rvert ^p\bigr]\bigr)^{1/p} \qquad \text{for every pair of Boolean functions } f, g \]

holds, where \(T_\rho \) is the noise operator and \(\mathbb {E}\) and \(\langle \, \cdot \, ,\cdot \, \rangle \) are the expectation and \(L^2\) inner product 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.

Theorem 274.8 Pairing bound below exponent two

✓

Let \(p, q \in \mathbb {R}\) satisfy \(1 \le p \le 2\) and \(1 \le q \le 2\), and set \(\rho = \sqrt{(p-1)(q-1)}\). Then for every \(n \in \mathbb {N}\) and all Boolean functions \(f, g : \{ 0,1\} ^n \to \mathbb {R}\),

\[ \langle f,\, T_\rho g\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}, \]

where \(\langle \cdot ,\cdot \rangle \) is the \(L^2\) inner product under the uniform measure on \(\{ 0,1\} ^n\), \(\mathbb {E}\) is the corresponding expectation, and \(T_\rho \) is the noise operator with parameter \(\rho \). 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.