Generalized Samorodnitsky noisy function inequalities, with applications to error-correcting codes

An inequality by Samorodnitsky states that if $f:{\mathbb{F}}_2^n\to \mathbb{R}$ is a nonnegative boolean function, and $S\subseteq [n]$ is chosen by randomly including each coordinate with probability a certain $\lambda =\lambda (q,\rho )<1$, then \begin{equation} \log |T_ρf|q \leq $\mathbb{E}${S} \log |$\mathbb{E}$(f|S)|_q;. \end{equation} Samorodnitsky’s inequality has several applications to the theory of error-correcting codes. Perhaps most notably, it can be used to show that \emph{any} binary linear code (with minimum distance $\omega (\log n)$) that has vanishing decoding error probability on the BEC$(\lambda )$ (binary erasure channel) also has vanishing decoding error on \emph{all} memoryless symmetric channels with capacity above some $C=C(\lambda )$. Samorodnitsky determined the optimal $\lambda =\lambda (q,\rho )$ for his inequality in the case that $q\ge 2$ is an integer. In this work, we generalize the inequality to $f:{\mathrm{\Omega }}^n\to \mathbb{R}$ under any product probability distribution ${\mu }^{\otimes n}$ on ${\mathrm{\Omega }}^n$; moreover, we determine the optimal value of $\lambda =\lambda (q,\mu ,\rho )$ for any real $q\in [2,\mathrm{\infty }]$, $\rho \in [0,1]$, and distribution~$\mu$. As one consequence, we obtain the aforementioned coding theory result for linear codes over \emph{any} finite alphabet.