The KKL theorem and Friedgut’s junta theorem - Analysis of Boolean Functions

5 The KKL theorem and Friedgut’s junta theorem

A dictator was a single variable that dictates the function. A junta is a small set of variables that dictate the function.

We view ${- 1, 1}^{n}$ as a graph, where a pair of vertices is connected by an edge if they differ in a single coordinate.

The edge boundary of a subset $A$ of a graph is the set of edges with one vertex in $A$ and one in $A^{c}$ . We denote the edge boundary by $\partial A$ .

Theorem 5.1 (The edge-isoperimetric inequality in the cube – approximate version). Let $A \subset {0, 1}^{n}$ . Then

| \partial A | \geq | A | (n - \log_{2} | A |) .

Remark. Sharp for subcubes of dimension $k$ .

Proof. Let $𝜃 A$ be the set of internal edges of $A$ – i.e. edges $a b$ with $a, b \in A$ . Then $n | A | = 2 | 𝜃 A | + | \partial A |$ , so the theorem is equivalent to showing that

| 𝜃 A | \leq \frac{1}{2} | A | \log_{2} | A |

for every $A$ .

Induction on $n$ . If $n = 1$ the result is true ( $3$ cases to check).

Let $A_{0} = {x \in A : x_{n} = 0}$ , $A_{1} = {x \in A : x_{n} = 1}$ . Then

| 𝜃 A | \leq | 𝜃 A_{0} | + | 𝜃 A_{1} | + \min {| A_{0} |, | A_{1} |} \leq \frac{1}{2} | A_{0} | \log_{2} | A_{0} | + \frac{1}{2} | A_{1} | \log_{2} | A_{1} | + \min {| A_{0} |, | A_{1} |}

by induction hypothesis. Want $\leq \frac{1}{2} (| A_{0} | + | A_{1} |) \log (| A_{0} | + | A_{1} |)$ . So it’s enough to prove

\frac{1}{2} x \log_{2} x + \frac{1}{2} y \log_{2} y + x \leq \frac{1}{2} (x + y) \log_{2} (x + y)

whenever $0 \leq x \leq y$ , or equivalently

x \log x + y \log y + 2 x \log 2 \leq (x + y) \log (x + y) .

If $x = y$ , we need

2 x \log x + 2 x \log 2 \leq 2 x \log (2 x),

which is indeed true.

Now differentiate with respect to $y$ . Left hand side becomes $\log y + 1$ , and right hand side becomes $\log (x + y) + 1$ . Since $x \geq 0$ , the left hand derivative is $\leq$ to the right hand derivative. □

Remark. If $| A | = 2^{n - 1}$ , this tells us that the edge-boundary is minimised by a half space. Let $f : {- 1, 1}^{n} \to {- 1, 1}$ be a function with $𝔼 f = 0$ , and therefore $Var f = 1$ . If $I (f) = 1$ , then $\sum_{A} | A | \hat{f} {(A)}^{2} = 1$ , but $\hat{f} (\emptyset) = 0$ and also $\sum_{A} \hat{f} {(A)}^{2} = 1$ by Parseval, so equality holds only if $f$ is linear, so $f$ is a dictator. Similarly, if equality almost holds, then by FKN $f$ is almost a dictator.

The above remark says that to minimise $I (f)$ , the best thing is to have a dictator: just one variable contributing to $I (f)$ . What if we forbid this, for example by asking that each variable has the same influence?

Might guess that taking majority vote is best for this, but as mentioned before this has $I (f) \approx \sqrt{n}$ . It turns out the following is much better:

The “tribes” function of Ben–Or and Linial: Let $k, m \in ℕ$ . Let $n = k m$ , write $[n] = A_{0} \cup \dots \cup A_{i}$ , $| A_{i} | = k$ . Define $f (x) = 1$ if and only if there exists $i$ such that $x_{j} = 1$ for every $j \in A_{i}$ .

This achieves $I (f) = \frac{c \log n}{n}$ (once we optimise $k$ and $m$ ).

Theorem 5.2 (The Kahn–Kalai–Linial edge-isoperimetric inequality). Let $f : {- 1, 1}^{n} \to {- 1, 1}$ be a Boolean function. Then there exists $i$ such that ${Inf}_{i} f \geq \frac{9}{Ĩ {(f)}^{2}} \geq \frac{9}{Ĩ {(f)}^{2}} 9^{- Ĩ (f)}$ , where $Ĩ (f) = \frac{I (f)}{Var f}$ .

Proof. We shall obtain upper and lower bounds or $\sum_{i = 1}^{n} {Stab}_{\frac{1}{3}} (D_{i} f)$ (magical idea).

Upper bound: $\sum_{i} {Stab}_{\frac{1}{3}} (D_{i} f) \leq \sum_{i} ∥ D_{i} f ∥_{4 ∕ 3}^{2}$ . But $∥ D_{i} f ∥_{4 ∕ 3}^{4 ∕ 3} = {Inf}_{i} f$ , so

\sum_{i} ∥ D_{i} f ∥_{4 ∕ 3}^{2} = \sum_{i} {({Inf}_{i} f)}^{3 ∕ 2} \leq {(\max_{i} {Inf}_{i} f)}^{\frac{1}{2}} I (f) .

Lower bound: $\sum_{i} {Stab}_{\frac{1}{3}} (D_{i} f) = \sum_{i} \sum_{A} {(\frac{1}{3})}^{| A |} \hat{D_{i} f} {(A)}^{2}$ . But

\hat{D_{i} f} (A) = {\begin{matrix} \hat{f} (A \cup {i}) & i \notin A \\ 0 & i \in A \end{matrix}

(using the formula $\hat{D_{i} f} = \sum_{B ∋ i} \hat{f} (B) x_{B ∖ {i}}$ ). So

\begin{array}{l} \sum_{i} \sum_{A} {(\frac{1}{3})}^{| A |} \hat{D_{i} f} (A) & = \sum_{i} \sum_{A ∋ i} {(\frac{1}{3})}^{| A |} \hat{f} {(A \cup {i})}^{2} \\ = \sum_{B} {(\frac{1}{3})}^{| B | - 1} | B | \hat{f} {(B)}^{2} \\ \geq 3 Var f \sum_{B \neq \emptyset} {(\frac{1}{3})}^{| B |} \frac{\hat{f} {(B)}^{2}}{Var f} \end{array}

But

\sum_{B \neq \emptyset} \hat{f} {(B)}^{2} = ∥ f ∥_{2}^{2} - \hat{f} {(0)}^{2} = 𝔼 f^{2} - {(𝔼 f)}^{2} = Var f,

so $\sum_{B \neq \emptyset} \frac{\hat{f} {(B)}^{2}}{Var f} = 1$ .

The function $x \mapsto {(\frac{1}{3})}^{x}$ is convex, so by Jensen,

\sum_{B \neq \emptyset} {(\frac{1}{3})}^{| B |} \frac{\hat{f} {(B)}^{2}}{Var f} \geq {(\frac{1}{3})}^{\sum_{B \neq \emptyset} | B | \frac{\hat{f} {(B)}^{2}}{Var f}} = {(\frac{1}{3})}^{Ĩ (f)} .

Therefore,

{(\max_{i} {Inf}_{i} f)}^{\frac{1}{2}} I (f) \geq 3 Var f {(\frac{1}{3})}^{Ĩ (f)},

which rearranges to the result. □

Corollary 5.3 (The KKL theorem). Let $f : {- 1, 1}^{n} \to {- 1, 1}$ . Then there exists $i$ such that ${Inf}_{i} f \geq \frac{c \log n}{n} Var f$ (for some absolute constant $c > 0$ ).

Proof. If $Ĩ (f) \geq c \log n$ , then the result follows trivially by averaging.

Otherwise, by ?? 35, there exists $i$ such that ${Inf}_{i} (f) \geq \frac{9}{{(c \log n)}^{2}} \cdot 9^{- c \log n}$ . For small enough $c$ , that’s much bigger than $\frac{c \log n}{n}$ . □

This shows that the “tribes” example from last lecture is the best possible.

Motivation for why $Stab$ is natural to define in order to tackle the The KKL theorem: We can assume $λ I (f) \leq c λ \log n$ . Then $e^{λ I (f)} \leq n^{c λ}$ . LHS is $e^{λ \sum_{A} | A | \hat{f} {(A)}^{2}}$ , and by Jensen we get $\leq \sum_{A} \hat{f} {(A)}^{2} \cdot e^{λ | A |} = {Stab}_{e^{λ}} f$ . So $Stab$ comes up somewhat naturally.

Definition 5.4 (Junta). Let $f : {- 1, 1}^{n} \to ℝ$ , and let $J \subset [n]$ . Then $f$ is a $J$ -junta if $f (x)$ depends only on $x |_{J}$ . We also say that $J$ is a junta. $f$ is a $k$ -junta if $f$ is a $J$ -junta for some $J$ of size $k$ .

Friedgut’s junta theorem states that a Boolean function with small total influence can be approximated by a $m$ -junta for some small $m$ .

Theorem 5.5 (Friedgut’s junta inequality). Let $f : {- 1, 1}^{n} \to {- 1, 1}$ , let $𝜀 > 0$ , and let $k \in ℕ$ . Suppose that $∥ f^{(\leq k)} ∥_{2}^{2} \geq 1 - 𝜀$ . Then there exists an $m$ -junta $g : {- 1, 1}^{n} \to ℝ$ such that $∥ f - g ∥_{2}^{2} \leq 𝜀$ with $m \leq 3^{2 k} \cdot \frac{I {(f)}^{3}}{𝜀^{2}}$ .

The proof has some similarities with ?? 35, so we include less detail in this proof.

Proof. Let $τ > 0$ a constant to be chosen later and let

J = {i \in [n] : {Inf}_{i} f \geq τ} .

This time we estimate $\sum_{i \notin J} {Stab}_{\frac{1}{3}} (D_{i} f)$ .

\sum_{i \notin J} {Stab}_{\frac{1}{3}} (D_{i} f) \leq \sum_{i \notin J} {({Inf}_{i} f)}^{3 ∕ 2} \leq τ^{\frac{1}{2}} I (f) .

(The first inequality is proved using the same technique as in ?? 35.)

In the other direction,

\begin{array}{l} \sum_{i \notin J} {Stab}_{\frac{1}{3}} (D_{i} f) & = \sum_{i \notin J} {(\frac{1}{3})}^{| A |} \hat{f} {(A \cup {i})}^{2} \\ = 3 \sum_{B} | B ∖ J | {(\frac{1}{3})}^{| B |} \hat{f} {(B)}^{2} \\ \geq 3 \sum_{B ⁄ \subset J} {(\frac{1}{3})}^{| B |} \hat{f} {(B)}^{2} \end{array}

But

3 \sum_{\begin{array}{c} B ⁄ \subset J \\ | B | \leq k \end{array}} {(\frac{1}{3})}^{| B |} \hat{f} {(B)}^{2} \geq 3 \sum_{\begin{array}{c} B ⁄ \subset J \\ | B | \leq k \end{array}} {(\frac{1}{3})}^{k} \hat{f} {(B)}^{2} = {(\frac{1}{3})}^{k - 1} \sum_{\begin{array}{c} B ⁄ \subset J \\ | B | \leq k \end{array}} \hat{f} {(B)}^{2} .

Let $g = \sum_{\begin{array}{c} B \subset J \\ | B | \leq k \end{array}} \hat{f} (A) x_{A}$ . Then

Then

∥ f - g ∥_{2}^{2} \leq \sum_{\begin{array}{c} A ⁄ \subset J \\ | A | \leq k \end{array}} \hat{f} {(A)}^{2} + \sum_{| A | > k} \hat{f} {(A)}^{2} .

By hypothesis,

\sum_{| A | > k} \hat{f} {(A)}^{2} = ∥ f^{(> k)} ∥_{2}^{2} \leq c .

But

3 \sum_{B ⁄ \subset J} | B ∖ J | {(\frac{1}{3})}^{| B |} \hat{f} {(B)}^{2} \geq 3 \sum_{\begin{array}{c} B ⁄ \subset J \\ | B | \leq k \end{array}} {(\frac{1}{3})}^{k} \hat{f} {(B)}^{2} = 3^{- (k - 1)} \sum_{\begin{array}{c} A ⁄ \subset J \\ | A | \leq k \end{array}} \hat{f} {(A)}^{2} .

\sum_{\begin{array}{c} A ⁄ \subset J \\ | A | \leq k \end{array}} \hat{f} {(A)}^{2} \leq 3^{k - 1} τ^{\frac{1}{2}} I (f) .

If we choose $τ = \frac{𝜀^{2}}{3^{2 k} I (f)}$ , then this is at most $𝜀$ , so $∥ f - g ∥_{2}^{2} \leq 2 𝜀$ . But $| J | \leq \frac{I (f)}{τ} = \frac{3^{2 k} I {(f)}^{3}}{𝜀^{2}}$ . □

Corollary 5.6 (Friedgut’s junta theorem). Let $f : {- 1, 1}^{n} \to {- 1, 1}$ and let $𝜀 > 0$ . Then there exists an $m$ -junta $g : {- 1, 1}^{n} \to ℝ$ with $∥ f - g ∥_{2}^{2} \leq 2 𝜀$ and

m = \exp (O (\frac{I (f)}{𝜀})) .

Proof.

\begin{array}{l} I (f) & = \sum_{A} | A | \hat{f} {(A)}^{2} \\ \geq \sum_{| A | > k} | A | \hat{f} {(A)}^{2} \\ \geq k ∥ f^{(> k)} ∥_{2}^{2} \end{array}

So if $k \geq \frac{I (f)}{𝜀}$ , then $∥ f^{(\leq k)} ∥_{2}^{2} \geq 1 - 𝜀$ . By Theorem 5.5 we get a junta with $m \leq 3^{2 \frac{I (f)}{𝜀}} \cdot \frac{I {(f)}^{3}}{𝜀^{2}} = \exp (O (\frac{I (f)}{𝜀}))$ . □

Remark. Let $f : {- 1, 1}^{n} \to {- 1, 1}$ , $g : {- 1, 1}^{n} \to ℝ$ and suppose that $∥ f - g ∥_{2}^{2} \leq 𝜀$ . Let

h (x) = {\begin{matrix} 1 & g (x) \geq 0 \\ - 1 & g (x) < 0 \end{matrix}

Then if $h (x) \neq f (x)$ , then $g (x)$ has a different sign from $f (x)$ , so $| g (x) - f (x) |^{2} \geq 1$ . Since $𝔼 | f (x) - g (x) |^{2} \leq 𝜀$ , we have $ℙ [f (x) \neq h (x)] \leq 𝜀$ .

In other words, we can find a Boolean function that approximates $f$ , and if $g$ is a $J$ -junta, then so is $h$ .