Hypercontractivity - Analysis of Boolean Functions

4 Hypercontractivity

We begin with an important lemma of Bonami.

Lemma 4.1 (Bonami’s Lemma). Let $f : {- 1, 1}^{n} \to ℝ$ be a function of degree $\leq k$ . Then $∥ f ∥_{4} \leq 3^{k ∕ 2} ∥ f ∥_{2}$ .

This statement is natural: to have $∥ f ∥_{4}$ much larger than $∥ f ∥_{2}$ , $f$ must be ‘spiky’, because if it is roughly constant, then these norms are roughly the same; but if $f$ is ‘spiky’, then we expect it to not be low degree polynomial.

Example. Consider $f (0) = 1$ , $f (x) = 0$ otherwise. $∥ f ∥_{2} = 2^{- n ∕ 2}$ , $∥ f ∥_{4} = 2^{- n ∕ 4}$ . So $∥ f ∥_{4}$ is much larger than $∥ f ∥_{2}$ in this case, and indeed $f$ is not a low degree polynomial.

Proof. Induction on $n$ . $n = 1$ is easy. Let $f : {- 1, 1}^{n} \to ℝ$ . Then $f = g + x_{n} h$ where $g (x) = E_{n} f = \frac{1}{2} (f (x_{n \to 1}) + f (x_{n \to - 1}))$ and $h (x) = D_{n} x = \frac{1}{2} (f (x_{n \to 1}) - f (x_{n \to - 1}))$ . Note also that $g$ and $x_{n} h$ are orthogonal.

Recall that

x_{A} = {\begin{matrix} 0 & n \notin A \\ x_{A ∖ {n}} & n \in A \end{matrix}

Therefore, $D_{n} f$ has degree at most $k - 1$ . First,

∥ f ∥_{2}^{2} = ∥ g ∥_{2}^{2} + ∥ x_{n} h ∥_{2}^{2} = ∥ g ∥_{2}^{2} + ∥ h ∥_{2}^{2} .

Also,

\begin{array}{l} ∥ f ∥_{4}^{4} & = 𝔼_{x} {(g (x) + x_{n} h (x))}^{4} \\ = 𝔼_{x} (g {(x)}^{4} + 4 x_{n} g {(x)}^{3} h (x) + 6 x_{n}^{2} g {(x)}^{2} h {(x)}^{2} + 4 x_{n}^{3} g (x) h {(x)}^{3} + x_{n}^{4} h {(x)}^{4}) \\ = ∥ g ∥_{4}^{4} + 6 𝔼_{x} g {(x)}^{2} h {(x)}^{2} + ∥ h ∥_{4}^{4} \end{array}

The last line uses the fact that $g$ , $h$ don’t depend on $x_{n}$ and that $x_{n} = \pm 1$ with probability $\frac{1}{2}$ . Then

\begin{array}{l} ∥ f ∥_{4}^{4} & = ∥ g ∥_{4}^{4} + 6 𝔼_{x} g {(x)}^{2} h {(x)}^{2} + ∥ h ∥_{4}^{4} \\ \leq ∥ g ∥_{4}^{4} + 6 ∥ g ∥_{4}^{2} ∥ h ∥_{4}^{2} + ∥ h ∥_{4}^{4} & (by Cauchy-Schwarz) \\ \leq 3^{2 k} ∥ g ∥_{2}^{4} + 6 \cdot 3^{k} ∥ g ∥_{2}^{2} 3^{k - 1} ∥ h ∥_{2}^{2} + 3^{2 (k - 1)} ∥ h ∥_{2}^{4} & (by inductive hypothesis) \\ \leq 3^{2 k} (∥ g ∥_{2}^{4} + 2 ∥ g ∥_{2}^{2} ∥ h ∥_{2}^{2} + \frac{1}{9} ∥ h ∥_{2}^{4}) \\ \leq 3^{2 k} {(∥ g ∥_{2}^{2} + ∥ h ∥_{2}^{2})}^{2} \\ \leq 3^{2 k} ∥ f ∥_{2}^{4} & □ \end{array}

Corollary 4.2 (Anticoncentration of low-degree functions). Let $f : {- 1, 1}^{n} \to ℝ$ have degree $\leq k$ and let $𝔼_{x} f (x) = μ$ and $Var f = σ^{2}$ . Then

ℙ [| f (x) - μ | > \frac{σ}{2}] \geq \frac{9}{16} \cdot 3^{- 2 k} .

Proof. Let $g = f - μ$ . Then $𝔼 g = 0$ and $∥ g ∥_{2}^{2} = σ^{2}$ . Let $p = ℙ [| g (x) | > \frac{σ}{2}]$ . Let $A = {x : | g (x) | \leq \frac{σ}{2}}$ , $B = A^{c}$ . Then

σ^{2} = ∥ g ∥_{2}^{2} \leq (1 - p) \frac{σ^{2}}{4} + p 𝔼_{x \in B} g {(x)}^{2} .

Therefore,

p 𝔼_{x \in B} g {(x)}^{2} \geq \frac{3}{4} σ^{2},

𝔼_{x \in B} g {(x)}^{2} \geq \frac{3 σ^{2}}{4 p} .

By Cauchy-Schwarz (or $Var (g {(x)}^{2}) \geq 0$ ) we have

𝔼_{x \in B} g {(x)}^{4} \geq \frac{9 σ^{4}}{16 p^{2}},

so $∥ g ∥_{4}^{4} \geq \frac{9 σ^{4}}{16 p}$ . But Bonami’s Lemma implies that $∥ g ∥_{4}^{4} \leq 3^{2 k} ∥ g ∥_{2}^{4} = 3^{2 k} σ^{4}$ . Therefore, $p \geq \frac{9}{16} \cdot 3^{- 2 k}$ , as stated. □

In this lecture, we are aiming towards the earlier stated stability version of Arrow’s Theorem.

Lemma 4.3. Let $g : {- 1, 1}^{n} \to ℝ$ be given by the formula $g (x) = \sum_{i = 1}^{n} a_{i} x_{i}$ . Then

Var g^{2} = 2 \sum_{i \neq j} a_{i}^{2} a_{j}^{2} .

Remark. Why should one care about studying $Var (g {(x)}^{2})$ ? Note that if $g$ is a Boolean function, then $g {(x)}^{2} \equiv 1$ , so $Var (g {(x)}^{2})$ . So $Var (g {(x)}^{2})$ can be used to measure “how close” a function is to being Boolean (or a multiple of a Boolean function).

Proof. $𝔼 g^{2} = \sum_{i} a_{i}^{2}$ by Parseval, so

\begin{array}{l} {(𝔼 g^{2})}^{2} & = \sum_{i} a_{i}^{4} + \sum_{i \neq j} a_{i}^{2} a_{j}^{2} \\ 𝔼 g^{4} & = \sum_{i, j, k, l} a_{i} a_{j} a_{k} a_{l} 𝔼_{x} x_{i} x_{j} x_{k} x_{l} \\ = \sum_{i} a_{i}^{4} + 3 \sum_{i \neq j} a_{i}^{2} a_{j}^{2} \end{array}

Note that $𝔼_{x} x_{i} x_{j} x_{k} x_{l}$ vanishes if any index appears an odd number of times, which is how we deduce the last equality above.

Subtracting the two above equations gives the result. □

Lemma 4.4. Let $g : {- 1, 1}^{n} \to ℝ$ , $1 - δ \leq ∥ g ∥_{2}^{2} \leq 1$ , $Var g^{2} \leq C δ$ , $g$ linear with no constant term. Then there exists $i$ such that $\hat{g} {(i)}^{2} \geq 1 - (2 + \frac{C}{2}) δ$ .

Proof. Let $g (x) = \sum_{i} a_{i} x_{i}$ . Then $1 - δ \leq \sum_{i} a_{i}^{2} \leq 1$ , $2 \sum_{i \neq j} a_{i}^{2} a_{j}^{2} \leq C δ$ . Therefore,

\sum_{i} a_{i}^{4} = {(\sum_{i} a_{i}^{2})}^{2} - \sum_{i \neq j} a_{i}^{2} a_{j}^{2} \geq 1 - 2 δ - \frac{C}{2} δ = 1 - (2 + \frac{C}{2}) δ .

Also,

\sum_{i} a_{i}^{4} \leq \max_{i} a_{i}^{2} (\sum_{i} a_{i}^{2}) \leq \max a_{i}^{2} = \max \hat{g} {(i)}^{2} . □

Theorem 4.5 (Friedgut, Kalai, Naor). Let $f : {- 1, 1}^{n} \to {- 1, 1}$ be a function with $W_{1} (f) \geq 1 - δ$ . Then there exists $i$ such that $\hat{f} {(i)}^{2} \geq 1 - O (δ)$ .

Proof. Let $G$ be the degree- $1$ part of $f$ , i.e. $g = \sum_{i} \hat{f} (i) x_{i}$ . Then by hypothesis, $1 - δ \leq ∥ g ∥_{2}^{2}$ , and by Parseval $∥ g ∥_{2}^{2} \leq ∥ g ∥_{2}^{2} = 1$ . Let $σ = Var g^{2}$ . Note that $g^{2}$ has degree at most $2$ . By the Anticoncentration of low-degree functions,

ℙ [| g^{2} - ∥ g ∥_{2}^{2} | > \frac{σ}{2}] \geq \frac{9}{16} \cdot \frac{1}{81} = \frac{1}{9 \times 16} .

Since $∥ g ∥_{2}^{2} \in [1 - δ, 1]$ , it follows that

ℙ [| g^{2} - 1 | > \frac{σ}{2} - δ] \geq \frac{1}{9 \times 16} .

Also, $1 = f^{2}$ . Therefore,

𝔼_{x} | g {(x)}^{2} - f {(x)}^{2} | \geq \frac{1}{9 \times 16} \cdot (\frac{σ}{2} - δ) .

But

𝔼_{x} | g {(x)}^{2} - f {(x)}^{2} | = 𝔼_{x} | g (x) + f (x) | | g (x) - f (x) | \leq ∥ f + g ∥_{2} ∥ f - g ∥_{2} \leq 2 \sqrt{δ}

by Cauchy-Schwarz. Therefore, $\frac{σ}{2} - δ \leq 32 \times 9 \sqrt{δ}$ , so $σ \leq 64 \times 9 \sqrt{δ} + 2 δ \leq 600 \sqrt{δ}$ , so $σ^{2} \leq 360000 δ$ . By Lemma 4.4, there exists $i$ such that $\hat{g} {(i)}^{2} \geq 1 - 180002 δ = 1 - O (δ)$ . But $\hat{g} {(i)}^{2} = \hat{f} {(i)}^{2}$ , so we are done. □

Let $p = ℙ [f (x) = x_{i}]$ . Then $\hat{f} (i) = 𝔼 f (x) x_{i} = p - (1 - p) = 2 p - 1$ . So if $\hat{f} (i) = 1 - O (δ)$ , then $p = O (δ)$ or $1 - p = O (δ)$ . So $f$ is well-approximated by $x_{i}$ or by $- x_{i}$ .

This completes the proof of the stability version of Arrow’s Theorem.

Next time: $∥ T_{\frac{1}{\sqrt{3}}} f ∥_{4} \leq ∥ f ∥_{2}$ .

Notation. Given $f : {- 1, 1}^{n} \to ℝ$ , write $f^{(= k)}$ for the degree- $k$ part of $f$ , i.e. $\sum_{| A | = k} \hat{f} (A) x_{A}$ .

Theorem 4.6. Let $ρ = \frac{1}{\sqrt{3}}$ . Then $∥ T_{ρ} f ∥_{4} \leq ∥ f ∥_{2}$ for every $f : {- 1, 1}^{n} \to ℝ$ .

Proof.

\begin{array}{l} ∥ T_{ρ} f ∥_{4} & = ∥ \sum_{k = 0}^{n} T_{r} h o f^{(= k)} ∥_{4} \\ = ∥ \sum_{k = 0}^{n} ρ^{k} f^{(= k)} ∥_{4} \\ \leq \sum_{k = 0}^{n} ρ^{k} ∥ f^{(= k)} ∥_{4} \\ \leq \sum_{k = 0}^{n} ρ^{k} \cdot 3^{k ∕ 2} ∥ f^{(= k)} ∥_{2} & (by Bonami’s Lemma) \\ = \sum_{k = 0}^{n} ∥ f^{(= k)} ∥_{2} \\ \leq \sqrt{n} {(\sum_{k = 0}^{n} ∥ f^{(= k)} ∥_{2}^{2})}^{\frac{1}{2}} \\ = \sqrt{n} ∥ f ∥_{2} & (since the f^{(= k)} are orthogonal) \end{array}

To get rid of the $\sqrt{n}$ we use the tensor-power trick.

Write $f^{\otimes m} : {({- 1, 1}^{n})}^{m} \to ℝ$ for the function

f^{\otimes m} (x^{1}, \dots, x^{m}) = f (x^{1}) \dots f (x^{m}) .

It is easy to check that $∥ T_{ρ} f^{\otimes m} ∥_{4} = ∥ T_{ρ} f ∥_{4}^{m}$ and $∥ f^{\otimes m} ∥_{2} = ∥ f ∥_{2}^{m}$ . Therefore,

∥ T_{ρ} f ∥_{4}^{m} = ∥ T_{ρ} f^{\otimes m} ∥_{4} \leq \sqrt{m n} ∥ f^{\otimes m} ∥_{2} = \sqrt{m n} ∥ f ∥_{2}^{m},

where the inequality is what we proved earlier.

So $∥ T_{ρ} f ∥_{4} \leq {(m n)}^{\frac{1}{2 m}} ∥ f ∥_{2}$ for every $m$ . Letting $m \to \infty$ , we deduce that $∥ T_{ρ} f ∥_{4} \leq ∥ f ∥_{2}$ . □

Remark. The tensor trick here would have worked even if $\sqrt{n}$ was replaced by any subexponential function.

Corollary 4.7. Let $ρ = \frac{1}{\sqrt{3}}$ and let $f : {- 1, 1}^{n} \to ℝ$ . Then $∥ T_{ρ} f ∥_{2} \leq ∥ f ∥_{4 ∕ 3}$ .

Proof. Note that $T_{ρ}$ is self adjoint (see the example sheet, or note that it easily follows from $\hat{T_{ρ} f} (A) = ρ^{| A |} \hat{f} (A)$ ). So

\begin{array}{l} ∥ T_{ρ} f ∥_{2} & = \max_{∥ g ∥_{2} = 1} ⟨ T_{ρ} f, g ⟩ \\ = \max_{∥ g ∥_{2} = 1} ⟨ f, T_{ρ} g ⟩ & (self-adjoint) \\ \leq \max_{∥ h ∥_{4} = 1} ⟨ f, h ⟩ & (by Theorem 4.6) \\ = ∥ f ∥_{4 ∕ 3} & (since L_{4 ∕ 3} is the dual of L_{4}) □ \end{array}

Remark. On the last $=$ in the above proof, we could instead just say $\leq$ by Hölder.

Remark. $∥ T_{ρ} f ∥_{2}^{2} = ⟨ T_{ρ} f, T_{ρ} f ⟩ = ⟨ T_{ρ^{2}} f, f ⟩ = ⟨ T_{\frac{1}{3}} f, f ⟩ = {Stab}_{\frac{1}{3}} f$ .

So an equivalent formulation of Theorem 4.6 is that ${Stab}_{\frac{1}{3}} f \leq ∥ f ∥_{\frac{4}{3}}^{2}$ .