Hypercontractivity of a single bit

A real function of a single uniformly random bit x = ±1 is a + b x, and the noise operator T_ρ turns it into a + ρ b x. For 1 ≤ p ≤ 2 and 0 ≤ ρ ≤ √(p - 1), the two-point inequality ‖a + ρ b x‖_2 ≤ ‖a + b x‖_p holds: raised to the power p, it reads (a ^ 2 + ρ ^ 2 b ^ 2) ^ (p / 2) ≤ (|a + b| ^ p + |a - b| ^ p) / 2 (BitString.sq_add_sq_mul_sq_rpow_le), and it says that a single bit is (p, 2, √(p - 1))-hypercontractive (BitString.lpNorm_two_noiseOp_le_of_unit) O'Donnell, Theorem 9.18.

O'Donnell proves the inequality with the generalized binomial series. Here the two sides are compared through 1 + p (p - 1) / 2 t ^ 2, with t = |b| / |a| ≤ 1: Bernoulli's inequality bounds the left side by it, and two monotonicity arguments for derivatives show 2 + p (p - 1) t ^ 2 ≤ (1 + t) ^ p + (1 - t) ^ p, using that (1 + t) ^ (p - 2) + (1 - t) ^ (p - 2) is at least 2 when p ≤ 2.

Main results

• Cslib.BitString.sq_add_sq_mul_sq_rpow_le: the two-point inequality.
• Cslib.BitString.lpNorm_two_noiseOp_le_of_unit: (p, 2)-hypercontractivity of a single bit.

References

• R. O'Donnell, Analysis of Boolean Functions

The two-point inequality

theorem Cslib.BitString.sq_add_sq_mul_sq_rpow_le {p ρ a b : ℝ} (hp : 1 ≤ p) (hp' : p ≤ 2) (hρ : ρ ^ 2 ≤ p - 1) : (a ^ 2 + ρ ^ 2 * b ^ 2) ^ (p / 2) ≤ (|a + b| ^ p + |a - b| ^ p) / 2

The two-point inequality: for 1 ≤ p ≤ 2 and ρ ^ 2 ≤ p - 1, (a ^ 2 + ρ ^ 2 b ^ 2) ^ (p / 2) ≤ (|a + b| ^ p + |a - b| ^ p) / 2. For a uniformly random bit x = ±1 it says ‖a + ρ b x‖_2 ^ p ≤ ‖a + b x‖_p ^ p, so x is (p, 2, √(p - 1))-hypercontractive O'Donnell, Theorem 9.18.

A single bit

theorem Cslib.BitString.lpNorm_two_noiseOp_le_of_unit {p ρ : ℝ} (hp : 1 ≤ p) (hp' : p ≤ 2) (hρ : 0 ≤ ρ) (hρ' : ρ ≤ √(p - 1)) (f : (Unit → Bool) → ℝ) : lpNorm 2 (noiseOp ρ f) ≤ lpNorm p f

(p, 2)-hypercontractivity of a single bit: for 1 ≤ p ≤ 2 and 0 ≤ ρ ≤ √(p - 1), ‖T_ρ f‖_2 ≤ ‖f‖_p for every function f of one bit O'Donnell, Theorem 9.18.