Generalized Samorodnitsky Noisy Function Inequalities, with Applications to Error-Correcting Codes

An inequality by Samorodnitsky states that if f:F2n → ℝ is a nonnegative function, and S ⊆ [n] is chosen by randomly including each coordinate with probability a certain λ = λ(q,ρ) < 1, then log||Tρf||q ≤ ES log||E(f|S)||q. Samorodnitsky’s inequality has several applications to the theory of error-correcting codes. Perhaps most notably, it can be used to show that any binary linear code (with minimum distance ω(logn)) that has vanishing decoding error probability on the BEC(λ) (binary erasure channel) also has vanishing decoding error on all memoryless symmetric channels with capacity above some C = C(λ). Samorodnitsky determined the optimal λ = λ(q,ρ) for his inequality in the case that q ≥ 2 is an integer. In this work, we generalize the inequality to f : Ωn → ℝ under any product probability distribution µ⊗ n on Ωn; moreover, we determine the optimal value of λ = λ(q,µ,ρ) for any real q ∈ [2,∞], ρ ∈ [0,1], and distribution µ. As one consequence, we obtain the analogue of the aforementioned coding theory result for linear codes over any finite alphabet.