= Maximum-influence logarithmic lower bound
{title2=$\sum_i\beta_i\geq\tfrac23\operatorname{Var}(f)\log(1/\beta)$}
For a zero-one <Boolean function> on the unbiased <Boolean hypercube> with flip-probability <influences> $\beta_i\leq\beta$, the displayed bound holds for sufficiently small $\beta>0$. If it fails, write $b=\log(1/\beta)/3$. The <total influence> identity puts at least half the nonconstant <Fourier weight> on levels $1\leq|S|\leq b$. The <hypercontractive weighted influence bound> at $\delta=e^{-1}$ then gives $\sum_i\beta_i^{2/(1+\delta)}\geq2b\delta^b\operatorname{Var}(f)$. Its upper bound $\beta^{(1-\delta)/(1+\delta)}\sum_i\beta_i$ contradicts $(1-\delta)/(1+\delta)>1/3$.
Back to article page
