TCSLib

281 Boolean Analysis — Two Function

281.1 Overview

The extended power means are monotone in their finite exponent up to one. Two-function reverse hypercontractivity gives lower bounds for correlated pairings of nonnegative cube functions.

281.2 Declarations

Lemma 281.1 Monotonicity in the exponent
✓

Let \(a\le b\le 1\) and \(f:\{ 0,1\} ^n\to [0,\infty )\). Then \(M_a(f)\le M_b(f)\). For nonnegative functions \(u\), the extended mean is \(M_r(u)=(\mathbb {E}u^r)^{1/r}\) when \(r\gt 0\); the same formula applies for \(r\lt 0\) when \(u\) is positive everywhere. For positive \(u\), \(M_0(u)=\exp (\mathbb {E}\log u)\); if \(r\le 0\) and \(u\) has a zero, \(M_r(u)=0\). All expectations are uniform.

Theorem 281.2 Two-function reverse hypercontractivity
✓

Let \(p,q\lt 1\), \(0\le \rho \le 1\), and \(\rho ^2\le (1-p)(1-q)\). For all \(f,g:\{ 0,1\} ^n\to [0,\infty )\), uniform expectation satisfies \(\mathbb {E}[fT_\rho g]\ge M_p(f)M_q(g)\). For nonnegative functions \(u\), the extended mean is \(M_r(u)=(\mathbb {E}u^r)^{1/r}\) when \(r\gt 0\); the same formula applies for \(r\lt 0\) when \(u\) is positive everywhere. For positive \(u\), \(M_0(u)=\exp (\mathbb {E}\log u)\); if \(r\le 0\) and \(u\) has a zero, \(M_r(u)=0\). All expectations are uniform. 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.