17 Boolean Analysis — One Bit

17.1 Overview

This module establishes hypercontractivity for functions on the single-bit cube \(\{ \mathbb {F}\} ^1\). It develops the Fourier description of one-bit functions, the core real two-point inequality, and derives both the \((p,2)\)- and \((2,q)\)-hypercontractivity theorems for one bit (together with the noise-operator duality and the supporting power-mean, Cauchy–Schwarz, and Hölder-sharpness lemmas).

17.2 Declarations

Lemma 17.1 Enumeration of the one-bit cube

✓

The universal finite set of points of \(\mathrm{BoolCube}\, 1\) equals the two-element set \(\{ (\_ \mapsto \mathit{false}),\ (\_ \mapsto \mathit{true})\} \).

Lemma 17.2 Enumeration of subsets of \(\mathrm{Fin}\, 1\)

✓

The universal finite set of subsets of \(\mathrm{Fin}\, 1\) equals \(\{ \emptyset ,\ \{ 0\} \} \).

Lemma 17.3 The two one-bit inputs differ

✓

The constant-\(\mathit{false}\) and constant-\(\mathit{true}\) inputs on \(\mathrm{Fin}\, 1\) are distinct.

Lemma 17.4 Empty set differs from \(\{ 0\} \) in \(\mathrm{Fin}\, 1\)

✓

The empty subset of \(\mathrm{Fin}\, 1\) is not equal to \(\{ 0\} \).

Lemma 17.5 One-bit value at \(\mathit{false}\)

✓

For a one-bit function \(f\), its value on the all-\(\mathit{false}\) input is the sum of its two Fourier coefficients: \(f(\mathit{false}) = \widehat{f}(\emptyset ) + \widehat{f}(\{ 0\} )\).

Lemma 17.6 One-bit value at \(\mathit{true}\)

✓

For a one-bit function \(f\), its value on the all-\(\mathit{true}\) input is the difference of its two Fourier coefficients: \(f(\mathit{true}) = \widehat{f}(\emptyset ) - \widehat{f}(\{ 0\} )\).

Lemma 17.7 Expected square of the noised one-bit function

✓

For a one-bit function \(f\) and noise rate \(\rho \),

\[ \mathbb {E}\big[(T_\rho f)^2\big] = \widehat{f}(\emptyset )^2 + \rho ^2\, \widehat{f}(\{ 0\} )^2 . \]

Lemma 17.8 Expected \(p\)-th power of \(|f|\) on one bit

✓

For a one-bit function \(f\), writing \(a = \widehat{f}(\emptyset )\) and \(b = \widehat{f}(\{ 0\} )\),

\[ \mathbb {E}\big[|f|^p\big] = \frac{|a+b|^p + |a-b|^p}{2}. \]

Lemma 17.9 \(L^p\) norm monotonicity (power-mean inequality)

✓

For \(1 \le r \le s\) and any \(f : \mathrm{BoolCube}\, n \to \mathbb {R}\),

\[ \big(\mathbb {E}[|f|^r]\big)^{1/r} \le \big(\mathbb {E}[|f|^s]\big)^{1/s}. \]

This is the power-mean inequality for the uniform probability measure on the cube.

Theorem 17.10 Two-point inequality on the unit interval

✓

For \(1 \le p \le 2\) and \(0 \le b \le 1\),

\[ \big(1 + (p-1)b^2\big)^{p/2} \le \frac{(1+b)^p + (1-b)^p}{2}. \]

Lemma 17.11 Two-point inequality: the \(a=0\) case

✓

For \(1 \le p \le 2\) one has \((p-1)^{p/2} \le 1\), which yields the two-point inequality in the case \(a = 0\).

Lemma 17.12 Noise operator does not increase the absolute-value \(L^2\) contribution

✓

For real \(a, b\) and \(0 \le \rho \le 1\), writing \(u = a+b\) and \(v = a-b\),

\[ a^2 + \rho ^2 b^2 \le \Big(\tfrac {|u| + |v|}{2}\Big)^2 + \rho ^2 \Big(\tfrac {|u| - |v|}{2}\Big)^2 . \]

Theorem 17.13 Two-point inequality (full version)

✓

For \(1 \le p \le 2\), all \(a, b \in \mathbb {R}\), and \(\rho \ge 0\) with \(\rho ^2 \le p-1\),

\[ \big(a^2 + \rho ^2 b^2\big)^{1/2} \le \Big(\frac{|a+b|^p + |a-b|^p}{2}\Big)^{1/p}. \]

Theorem 17.14 One-bit \((p,2)\)-hypercontractivity

✓

For \(f : \mathrm{BoolCube}\, 1 \to \mathbb {R}\), \(1 \le p \le 2\), and \(\rho \ge 0\) with \(\rho ^2 \le p-1\),

\[ \big(\mathbb {E}[(T_\rho f)^2]\big)^{1/2} \le \big(\mathbb {E}[|f|^p]\big)^{1/p}. \]

Lemma 17.15 Sign times value equals absolute value

✓

For all real \(x\), \(\operatorname {sign}(x)\cdot x = |x|\).

Lemma 17.16 Absolute value of sign is one for nonzero input

✓

For \(x \neq 0\), \(|\operatorname {sign}(x)| = 1\).

Lemma 17.17 Expectation of a nonnegative function is nonnegative

✓

If \(f \ge 0\) pointwise, then \(\mathbb {E}[f] \ge 0\).

Lemma 17.18 Expectation of a constant function

✓

The expectation over the cube of the constant function with value \(c\) equals \(c\).

Lemma 17.19 Cauchy–Schwarz for the Boolean inner product

✓

For \(f, g : \mathrm{BoolCube}\, n \to \mathbb {R}\),

\[ \langle f, g\rangle \le \big(\mathbb {E}[f^2]\big)^{1/2}\, \big(\mathbb {E}[g^2]\big)^{1/2}. \]

Lemma 17.20 Hölder sharpness

✓

For Hölder conjugate exponents \((p, q)\) and any function \(u\), there exists a function \(f\) with \(\lVert f\rVert _p \le 1\) and \(\lVert u\rVert _q \le \langle f, u\rangle \).

Theorem 17.21 Noise operator duality

✓

If, for Hölder conjugate exponents \(p\) and \(p'\) with \(1 \le p\), the noise operator with rate \(\sqrt{p-1}\) satisfies the \((p,2)\)-hypercontractive bound for every one-bit function, then it also satisfies the dual \((2,p')\)-hypercontractive bound: for every \(g\),

\[ \big(\mathbb {E}[|T_{\sqrt{p-1}} g|^{p'}]\big)^{1/p'} \le \big(\mathbb {E}[g^2]\big)^{1/2}. \]

Theorem 17.22 One-bit \((2,q)\)-hypercontractivity

✓

For \(g : \mathrm{BoolCube}\, 1 \to \mathbb {R}\) and \(q \ge 2\),

\[ \lVert T_{1/\sqrt{q-1}}\, g\rVert _q \le \lVert g\rVert _2 . \]