Homework #5 & Talagrand

Solutions are posted.

Regarding Question #2: I referred to this as "Talagrand's Lemma", and that's how I personally think of it, having learned it first as Proposition 2.2 in Michel Talagrand's ingenious paper How much are increasing sets positively correlated?.

I think that, really, it should count as a folklore result. For example, in arithmetic combinatorics I think it's sometimes called Chang's Theorem. It is also the pith of the very technical proof of Bourgain's Theorem on the Fourier tails of boolean functions (not available online, but appearing in a paper of Khot and Naor). Bourgain uses a different proof, but doesn't quite derive it explicitly. The different proof relies on hypercontractivity and is extremely short:

Given $f:\{-1,1{\}}^n\to ℝ$, let $L$ be the degree-1 part of $f$. Then by Plancherel, $W_1\left(f\right)=\langle f,L\rangle \le \parallel f{\parallel }_{qʹ}\parallel L{\parallel }_q$ for any $1/q+1/qʹ=1$, by Holder. Use hypercontractivity on $\parallel L{\parallel }_q$, noting that it has degree 1. One gets $\parallel L{\parallel }_q\le \sqrt{q-1}\parallel L{\parallel }_2=\sqrt{q-1}\sqrt{W_1\left(f\right)}$. On the other hand, we have $\parallel f{\parallel }_{qʹ}=E[\mid f{\mid }^{qʹ}{]}^{1/qʹ}\le p^{1/qʹ}=p^{1-1/q}$ where $p=E[\mid f\mid ]$, since $\mid f\mid \le 1$ and $qʹ\ge 1$. Putting it together, we get $\sqrt{W_1\left(f\right)}\le p^{1-1/q}\sqrt{q-1}$, which implies $W_1\left(f\right)\le p^2\cdot q(1/p{)}^{2/q}$. Now we just need to choose $q$ to balance $q$ and $(1/p{)}^{2/q}$; the optimum choice is $q=\Theta (\log (1/p))$, and this completes the proof.