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

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.