= Squared-influence logarithmic lower bound
{title2=$\sum_i\beta_i^2\geq t^2(1-t)^2(\log n)^2/n$}
For a zero-one <Boolean function> of mean $t$, the displayed bound holds for sufficiently large $n$, uniformly in $t$. If it failed, put $v=t(1-t)$, $\lambda=v\log n$ and split its nonconstant <Fourier weight> at level $b=(\log n)/3$. The <total influence> bound puts at most $3v/4$ above that level. The <hypercontractive weighted influence bound> with $\delta=1-3\log\log n/\log n$ puts only $o(v)$ below it: the conversion factor $\max_{1\leq s\leq b}[s\delta^{s-1}]^{-1}$ stays bounded, while $\lambda^{2/(1+\delta)}n^{1-2/(1+\delta)}=vO((\log n)^{-1/2+o(1)})$. This contradicts total nonconstant weight $v$.
Back to article page
