Hypercontractivity on the Boolean cube

The noise operator T_ρ (BitString.noiseOp) is a hypercontraction: it is a contraction not only of L^2 but from L^p to L^2 and from L^2 to L^q for suitable ρ [Bon70] O'Donnell, Chapter 9. Writing ‖f‖_p for the L^p norm (BitString.lpNorm), this file proves:

• the Weak Two-Function Hypercontractivity Theorem: for 0 ≤ r, s ≤ 1 and 0 ≤ ρ ≤ √(r s), the expectation of f x g y over a ρ-correlated pair (x, y), which is 𝔼_x f x · T_ρ g x, is at most ‖f‖_{1 + r} ‖g‖_{1 + s} (BitString.expect_mul_noiseOp_le_lpNorm_mul_lpNorm);
• the (p, 2)-Hypercontractivity Theorem: ‖T_ρ f‖_2 ≤ ‖f‖_p for 1 ≤ p ≤ 2 and 0 ≤ ρ ≤ √(p - 1) (BitString.lpNorm_two_noiseOp_le), equivalently Stab_ρ[f] ≤ ‖f‖_{1 + ρ} ^ 2 for 0 ≤ ρ ≤ 1 (BitString.noiseStability_le_lpNorm_sq);
• the (2, q)-Hypercontractivity Theorem: ‖T_ρ f‖_q ≤ ‖f‖_2 for 2 ≤ q and 0 ≤ ρ ≤ 1 / √(q - 1) (BitString.lpNorm_noiseOp_le_lpNorm_two);
• their composition, ‖T_ρ f‖_q ≤ ‖f‖_p for 1 ≤ p ≤ 2 ≤ q and 0 ≤ ρ ≤ √((p - 1) / (q - 1)) (BitString.lpNorm_noiseOp_le_lpNorm), the Hypercontractivity Theorem in the range p ≤ 2 ≤ q;
• the special cases ‖T_{1/√3} f‖_4 ≤ ‖f‖_2 (the (2, 4)-Hypercontractivity Theorem, BitString.expect_noiseOp_pow_four_le) and Stab_{1/3}[f] ≤ ‖f‖_{4/3} ^ 2 (the (4/3, 2)-Hypercontractivity Theorem, BitString.noiseStability_one_third_le).

The proofs follow O'Donnell, Sections 9.3 and 9.4. On a single bit, the two-point inequality (BitString.lpNorm_two_noiseOp_le_of_unit) and the Cauchy–Schwarz inequality give the two-function inequality, after splitting T_ρ = T_{ρ₁} T_{ρ₂} with ρ₁ ≤ √r and ρ₂ ≤ √s and moving T_{ρ₁} across the expectation. The two-function inequality tensorizes (BitString.expect_mul_noiseOp_le_of_unit), which gives it on every cube. Taking r = s = p - 1 gives the (p, 2) theorem, and taking r = 1 / (q - 1) and s = 1 gives the (2, q) theorem by duality: ‖T_ρ f‖_q ^ q is the expectation of h · T_ρ f for h = T_ρ f |T_ρ f| ^ (q - 2), whose L^{q / (q - 1)} norm is ‖T_ρ f‖_q ^ (q - 1).

The case q = ∞ of the (2, q) theorem is not covered: ‖·‖_q is defined for real q.

Main results

• Cslib.BitString.expect_mul_noiseOp_le_lpNorm_mul_lpNorm: the Weak Two-Function Hypercontractivity Theorem.
• Cslib.BitString.lpNorm_two_noiseOp_le, Cslib.BitString.noiseStability_le_lpNorm_sq: the (p, 2)-Hypercontractivity Theorem.
• Cslib.BitString.lpNorm_noiseOp_le_lpNorm_two: the (2, q)-Hypercontractivity Theorem.
• Cslib.BitString.lpNorm_noiseOp_le_lpNorm: hypercontractivity for p ≤ 2 ≤ q.
• Cslib.BitString.expect_noiseOp_pow_four_le, Cslib.BitString.noiseStability_one_third_le: the (2, 4)- and (4/3, 2)-Hypercontractivity Theorems.

References

• A. Bonami, Étude des coefficients de Fourier des fonctions de L^p(G)
• R. O'Donnell, Analysis of Boolean Functions

Splitting the correlation

theorem Cslib.BitString.expect_mul_noiseOp_mul {ι : Type u_1} [Fintype ι] [DecidableEq ι] (ρ σ : ℝ) (f g : (ι → Bool) → ℝ) : (Finset.univ.expect fun (x : ι → Bool) => f x * noiseOp (ρ * σ) g x) = Finset.univ.expect fun (x : ι → Bool) => noiseOp ρ f x * noiseOp σ g x

Splitting the correlation: the expectation of f against T_{ρ σ} g is the expectation of T_ρ f against T_σ g.

Two-function hypercontractivity

theorem Cslib.BitString.expect_mul_noiseOp_le_lpNorm_mul_lpNorm {ι : Type u_1} [Fintype ι] [DecidableEq ι] {r s ρ : ℝ} (hr : 0 ≤ r) (hr' : r ≤ 1) (hs : 0 ≤ s) (hs' : s ≤ 1) (hρ : 0 ≤ ρ) (hρ' : ρ ≤ √(r * s)) (f g : (ι → Bool) → ℝ) : (Finset.univ.expect fun (x : ι → Bool) => f x * noiseOp ρ g x) ≤ lpNorm (1 + r) f * lpNorm (1 + s) g

The Weak Two-Function Hypercontractivity Theorem: for 0 ≤ r, s ≤ 1 and 0 ≤ ρ ≤ √(r s), the expectation 𝔼_x f x · T_ρ g x of f x g y over a ρ-correlated pair (x, y) is at most ‖f‖_{1 + r} ‖g‖_{1 + s} O'Donnell, Section 9.4.

(p, 2)-hypercontractivity

theorem Cslib.BitString.lpNorm_two_noiseOp_le {ι : Type u_1} [Fintype ι] [DecidableEq ι] {p ρ : ℝ} (hp : 1 ≤ p) (hp' : p ≤ 2) (hρ : 0 ≤ ρ) (hρ' : ρ ≤ √(p - 1)) (f : (ι → Bool) → ℝ) : lpNorm 2 (noiseOp ρ f) ≤ lpNorm p f

The (p, 2)-Hypercontractivity Theorem: for 1 ≤ p ≤ 2 and 0 ≤ ρ ≤ √(p - 1), ‖T_ρ f‖_2 ≤ ‖f‖_p O'Donnell, Section 9.4.

theorem Cslib.BitString.noiseStability_le_lpNorm_sq {ι : Type u_1} [Fintype ι] [DecidableEq ι] {ρ : ℝ} (hρ : 0 ≤ ρ) (hρ' : ρ ≤ 1) (f : (ι → Bool) → ℝ) : noiseStability ρ f ≤ lpNorm (1 + ρ) f ^ 2

The (p, 2)-Hypercontractivity Theorem, as a bound on noise stability: for 0 ≤ ρ ≤ 1, Stab_ρ[f] ≤ ‖f‖_{1 + ρ} ^ 2 O'Donnell, Chapter 9.

theorem Cslib.BitString.noiseStability_one_third_le {ι : Type u_1} [Fintype ι] [DecidableEq ι] (f : (ι → Bool) → ℝ) : noiseStability (1 / 3) f ≤ lpNorm (4 / 3) f ^ 2

The (4/3, 2)-Hypercontractivity Theorem: Stab_{1/3}[f] ≤ ‖f‖_{4/3} ^ 2 O'Donnell, Section 9.2.

(2, q)-hypercontractivity

theorem Cslib.BitString.lpNorm_noiseOp_le_lpNorm_two {ι : Type u_1} [Fintype ι] [DecidableEq ι] {q ρ : ℝ} (hq : 2 ≤ q) (hρ : 0 ≤ ρ) (hρ' : ρ ≤ (√(q - 1))⁻¹) (f : (ι → Bool) → ℝ) : lpNorm q (noiseOp ρ f) ≤ lpNorm 2 f

The (2, q)-Hypercontractivity Theorem: for 2 ≤ q and 0 ≤ ρ ≤ 1 / √(q - 1), ‖T_ρ f‖_q ≤ ‖f‖_2 O'Donnell, Section 9.4.

theorem Cslib.BitString.lpNorm_noiseOp_le_lpNorm {ι : Type u_1} [Fintype ι] [DecidableEq ι] {p q ρ : ℝ} (hp : 1 ≤ p) (hp' : p ≤ 2) (hq : 2 ≤ q) (hρ : 0 ≤ ρ) (hρ' : ρ ≤ √((p - 1) / (q - 1))) (f : (ι → Bool) → ℝ) : lpNorm q (noiseOp ρ f) ≤ lpNorm p f

Hypercontractivity for p ≤ 2 ≤ q: for 1 ≤ p ≤ 2 ≤ q and 0 ≤ ρ ≤ √((p - 1) / (q - 1)), ‖T_ρ f‖_q ≤ ‖f‖_p, composing the (p, 2) and (2, q) theorems O'Donnell, Chapter 9.

theorem Cslib.BitString.expect_noiseOp_pow_four_le {ι : Type u_1} [Fintype ι] [DecidableEq ι] (f : (ι → Bool) → ℝ) : (Finset.univ.expect fun (x : ι → Bool) => noiseOp (√3)⁻¹ f x ^ 4) ≤ (Finset.univ.expect fun (x : ι → Bool) => f x ^ 2) ^ 2

The (2, 4)-Hypercontractivity Theorem: ‖T_{1/√3} f‖_4 ≤ ‖f‖_2, that is, 𝔼 (T_{1/√3} f) ^ 4 ≤ (𝔼 f ^ 2) ^ 2 O'Donnell, Section 9.2.