Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 15 / 1

Use the uniform probability measure on the Boolean hypercube. In the Fourier-Walsh transform convention ${\chi }_S(x)=(-1{)}^{{\sum }_{i\in S}{x}_i}$, write $f={\sum }_S{\alpha }_S{\chi }_S$ with ${\alpha }_S=\mathbb{E}[f{\chi }_S]$. For the indicator $f$, Parseval's identity givesThe flip-probability influence satisfies ${\beta }_i=4{\sum }_{S\ni i}{\alpha }_S^2$, and summing gives ${\sum }_{S\ne \varnothing }|S|{\alpha }_S^2=\frac{1}{4}{\sum }_i{\beta }_i$.

For $p=1+\delta \in (1,2)$, Beckner's inequality says $\Vert T_{\sqrt{\delta }}g{\Vert }_2\le \Vert g{\Vert }_p$. Apply it to the discrete derivative of a Boolean function in coordinate $i$, viewed on the other $n-1$ coordinates. Its nonzero magnitude is $1/2$ and occurs with probability ${\beta }_i$, soSumming over $i$ gives the hypercontractive weighted influence bound

By the Cauchy-Schwarz inequality, ${\sum }_i{\beta }_i\le \sqrt{n{\sum }_i{\beta }_i^2}<\lambda$. The total influence identity in part (i) therefore gives $\boxed{\sum _{S\ne \varnothing }|S|{\alpha }_S^2<\lambda /4}$.

The Holder inequality gives ${\sum }_i{\beta }_i^{2/p}\le n^{1-1/p}({\sum }_i{\beta }_i^2{)}^{1/p}<{\lambda }^{2/p}{n}^{1-2/p}$. Substitute this into the hypercontractive weighted influence bound and multiply by $\delta$ to obtainas required. The version with ${\delta }^{|S|-1}$ is slightly stronger and will also be useful below.

Put $v=t(1-t)$. The assertion is trivial when $v=0$. Otherwise suppose it fails and set $L=\log n$, $\lambda =vL$, $\gamma =3\log L/L$, $\delta =1-\gamma$, $p=2-\gamma$ and $b=L/3$, with natural logarithms. For large $n$ these parameters lie in their required ranges. The high-level Fourier weight isFor $1\le s<b$, let $M_n=\max [s{\delta }^{s-1}{]}^{-1}$. The logarithm of this expression is a convex function of real $s$, so its maximum on $[1,b]$ is at an endpoint. Also ${\delta }^{1-b}/b\to 3$, since $-(b-1)\log (1-\gamma )=\log L+o(1)$. Hence $M_n$ is bounded. The stronger inequality in part (ii) givesDivide by $v$. Because $0<v\le 1/4$ and $2/p>1$, the factor $v^{2/p-1}$ is at most one. The remaining factor is $L^{2/p}{e}^{-\gamma L/p}=L^{-1/2+o(1)}\to 0$. Thus the low-level weight is $o(v)$ uniformly in $t$. Adding both parts contradicts ${\sum }_{S\ne \varnothing }{\alpha }_S^2=v$ for sufficiently large $n$. This proves the squared-influence logarithmic lower bound