Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 13 / 3

Work on the unbiased Boolean hypercube with values $\{-1,1\}$ for the coordinates and $\{0,1\}$ for $f$. Write its Fourier-Walsh transform asThe flip-probability influences satisfyThese factors of four are essential for zero-one $f$. If $v=0$, the conclusion is immediate. Otherwise suppose, for a contradiction, that $I<2bv$, where $b=\log (1/\beta )/3$. Take $\beta$ small enough that $b\ge 1$. The high-level Fourier weight obeysThis proves the first intermediate claim, including when $b$ is not an integer.

Set $\delta =e^{-1}$ and $r=2/(1+\delta )$. For the discrete derivative of a Boolean function, $D_{i}f$ has magnitude $1/2$ exactly on a set of measure ${\beta }_i$. Beckner's inequality, in the precise form $\Vert T_{\sqrt{\delta }}g{\Vert }_2\le \Vert g{\Vert }_{1+\delta }$ for the noise operator on the Boolean hypercube, yieldsFor $1\le s\le b$, concavity of $\log s-s+1$ shows that $s{\delta }^{s-1}$ is at least the smaller endpoint value $\min (1,b{\delta }^{b-1})$, and this is at least $b{\delta }^b$ since $b{e}^{-b}\le 1$. Therefore the low-level Fourier weight gives the second required intermediate bound:On the other hand, ${\beta }_i\le \beta$ and the assumed bound on $I$ giveCombining these inequalities would imply ${\beta }^{r-1}>{\delta }^b={\beta }^{1/3}$. But $r-1=(1-\delta )/(1+\delta )>1/3$ and $0<\beta <1$, so the inequality is impossible. ConsequentlyIn fact, this proof needs sufficiently small $\beta$ but no separate lower bound on $n$.

Put $v=t(1-t)$ and $M={\max }_i{\beta }_i$. If $v=0$ the assertion is immediate. Otherwise, supposeSince $v\le 1/4$, this makes $M\le \log n/(8n)$, so $M$ is sufficiently small to apply the maximum-influence logarithmic lower bound once $n$ is large. That bound givesFor all sufficiently large $n$, the last quantity exceeds $v\log n/2$, contradicting $nM<v\log n/2$. The choice of sufficiently large $n$ is independent of $t$. Therefore