Proving Poincaré's inequality for Boolean functions over the hypercube without Fourier analysis

Question

$\DeclareMathOperator\Inf{Inf}\DeclareMathOperator\unif{unif}$I have been attempting to find a non-Fourier-analytic proof of Poincaré's inequality for Boolean functions over the hypercube. Let's call this Problem P.

Problem P. For all functions $f \colon \{\pm 1\}^n \to \{\pm 1\}$, the total influence of $f$, $\Inf(f)$, is at least the variance of $f$.

Here, $\Inf(f)$ is the sum of influences in the $i$-th co-ordinate, $\Inf_i(f)$, over all co-ordinates $i \in [n]$.

Influence of a Boolean function over the hypercube can be defined in at least three different ways.

1. Probabilistic definition. $\Inf_i(f) = P_{x \sim \unif(\{\pm 1\}^n)}\left[f(x) \neq f(x^{\oplus i})\right]$, where $x^{\oplus i}$ is $x$ with its $i$-th co-ordinate inverted.

2. Directional-derivative based definition. $\Inf_{i}(f) = E_{x \sim \unif(\{\pm 1\}^n)}\left[(\partial_i(f))^2\right]$, where $\partial_i(f)$ is defined as $\frac{f(x) - f(x^{\oplus i})}{2}$.

3. "Fourier-energy"-based definition. $\Inf_{i}(f) = \sum_{S : i \in S} (\widehat{f}(S))^2$. Recall that any real function over the hypercube, $f$, can be uniquely represented as a mulitilinear polynomial, $f = \sum_{S \subseteq [n]} \widehat{f}(S)x_S$. The $\widehat{f}(S)$'s in this definition of $\Inf_i(f)$ correspond to these coefficients of the monomials.

Problem P can be proved in a few lines with Fourier-analytic techniques. I would like to prove it without F.A.-based techniques, to get a better understanding of the "advantage" of this tool for studying properties of functions over the hypercube.

In an attempt to prove Problem P without Fourier methods, to simplify the problem, I introduced the assumption that the function is balanced, i.e., $E_{x \sim \unif(\{\pm 1\}^n)}\left[f\right]=0$. Let us call this new problem, Problem P1.

I attempted to prove Problem P1 for small values of $n$, in hopes of finding a statement that I can prove by induction, and which, perhaps with other observations, implies P1. I have proved P1 for $1 \leq n \leq 4$. I found that the $n = 5$ case has an overwhelmingly large number of cases to analyze, without any additional insights. I could not find a way to "apply induction", i.e. use the fact that I have proved Problem P1 already for $1 \leq n \leq 4$.

---

I will now describe how I proved Problem P1 for $n=4$. I will assume that P1 is already proven for $1 \leq n \leq 3$. We have two observations.

Observation 1. For all balanced Boolean functions $f \colon \{\pm 1\}^n \to \{\pm 1\}$, for all $i \in [n]$, $\Inf_{i} = \frac{4k}{2^n}$, for some $k \in \mathbb{Z}_{\geq 0}$.

Observation 2. For all Boolean functions $f \colon \{\pm 1\}^n \to \{\pm 1\}$ that has a non-influential co-ordinate $i$ (i.e. $\Inf_i(f) = 0$), $\Inf(f) = \Inf(g)$, where $g \colon \{\pm 1\}^{n-1} \to \{\pm 1\}$ is the mapping $(x_1,\dots,x_{i-1},x_{i+1},\dots,x_n) \mapsto f(x_1,\dots,x_{i-1},1,x_{i+1},\dots,x_n)$. Note that $f(x_1,\dots,x_{i-1},1,x_{i+1},\dots,x_n) = f(x_1,\dots,x_{i-1},-1,x_{i+1},\dots,x_n)$, since $\Inf_i(f) = 0$.

Take an arbitrary balanced function $h$ that maps $\{\pm 1\}^4$ to $\{\pm 1\}$. If $h$ has an influential co-ordinate $i$, then, by Observation 2, $\Inf(h) = \Inf(h_i) \geq 1$, where $h_i$ is the function over three co-ordinates, that is "same as" $h$. $\Inf(h_i) \geq 1$ because we have assumed P1 for $1 \leq n \leq 3$.

Hence, we can assume that for all $i \in [4]$, $\Inf_i(h) \neq 0$. By Observation 1, we have that for all $i \in [4]$, $\Inf_i(h) \geq \frac{4}{16}$. Hence, $\Inf(h) = \sum_{i \in [4]}\Inf_i(h) \geq 1$.

---

To summarize, my goal is to find a proof of Poincaré's inequality for Boolean functions over the hypercube without applying Fourier analysis.

Answer 1

Here is the proof by induction.

Set $M(x,y)=x^{2}-y^{2}$, and let $|\nabla f|^{2}(x) = \sum |\partial_{j}f(x)|^{2}$. We have

Lemma:

$$ \mathbb{E}_{x_{1}} M(f, |\nabla f|)\leq M(\mathbb{E}_{x_{1}}f, |\nabla \mathbb{E}_{x_{1}}f|) \quad (*) $$ where $\mathbb{E}_{x_{1}}g = \frac{g(1, x_{2},..,x_{n})+g(-1, x_{2},...,x_{n})}{2}$, i.e., it averages with respect to the variable $x_{1}$.

Iterating the lemma gives the Poincar'e inequality $$ \mathbb{E}f^{2}-\mathbb{E} |\nabla f|^{2}=\mathbb{E} M(f, |\nabla f|) \leq \mathbb{E}_{x_{2}, \ldots, x_{n}} M(\mathbb{E}_{x_{1}}f, |\nabla \mathbb{E}_{x_{1}}f|) \leq \ldots \leq M(\mathbb{E}f, |\nabla \mathbb{E} f|)=(\mathbb{E}f)^{2}. $$

Proof of the lemma:

You can check, just take $a=f(, x_{2},..,x_{n})$ and $b=f(-1,x_{2},..,x_{n})$, that (*) is the same as the following four-point inequality $$ M\left( \frac{a+b}{2}, \left\| \frac{u+v}{2} \right\|\right) \geq \frac{1}{2}\left[ M\left(a, \sqrt{\left(\frac{a-b}{2}\right)^{2}+\|u\|^{2}}\right)+M\left(b, \sqrt{\left(\frac{a-b}{2}\right)^{2}+\|v\|^{2}}\right)\right] $$ for all $a,b, \in \mathbb{R}$, and all $u,v \in \mathbb{R}^{N}$ and all $N\geq 1$. Since $M_{y}\leq 0$, and $\left\| \frac{u+v}{2}\right\|\leq \frac{\|u\|+\|v\|}{2}$ it suffices to verify the four point inequality only in th ecase $N=1$ and $u,v \geq 0$, and in this case it becomes just identity for this specific $M(x,y)=x^{2}-y^{2}$.

Answer 2

Here is a martingale proof. Consider the martingale $\{f_{k}\}_{k=0}^{n}$ defined as follows

\begin{align} f_{0}&=\mathbb{E}f(x_{1}, \ldots, x_{n})\\ f_{1}(\varepsilon_{1}) &= \mathbb{E} (f(x_{1}, \ldots, x_{n})| x_{1}=\varepsilon_{1})\\ f_{2}(\varepsilon_{1}, \varepsilon_{2}) &= \mathbb{E} (f(x_{1}, \ldots, x_{n})| x_{1}=\varepsilon_{1}, x_{2}=\varepsilon_{2})\\ \ldots\\ f_{n}(\varepsilon_{1}, \ldots, \varepsilon_{n}) &= \mathbb{E} (f(x_{1}, \ldots, x_{n})|x_{1}=\varepsilon_{n}, \ldots, x_{n}=\varepsilon_{n}) = f(\varepsilon_{1}, \ldots, \varepsilon_{n}) \end{align} Let $d_{k} :=f_{k}-f_{k-1}, k=1, \ldots, n$ be the martingale difference sequence. Notice that $\mathbb{E} d_{i} d_{j}=0$ if $i\neq j$, and \begin{align} |d_{k}| &= |\mathbb{E}_{x_{k+1}, \ldots, x_{n}} \partial_{k} f|, \quad k=1, \ldots, n-1,\\ |d_{n}| &= |\partial_{n} f|. \end{align} So by Jensen's inequality $\mathbb{E} |d_{j}|^{2} \leq \mathbb{E} |\partial_{j} f|^{2}$. Thus $$ \mathbb{E}|f-\mathbb{E}f|^{2} = \mathbb{E} | d_{1}+\ldots+d_{n}|^{2}=\sum_{j=1}^{n}\mathbb{E} |d_{j}|^{2} \leq\sum_{j=1}^{n} \mathbb{E} |\partial_{j}f|^{2}. $$

Answer 3

Here is the heat flow proof.

Let $\xi_{1}(t), \ldots, \xi_{n}(t)$ be i.i.d. r.v. such that $\mathbb{P}(\xi_{1}(t)=1)=\frac{1+e^{t}}{2}$ and $\mathbb{P}(\xi_{1}(t)=-1)=\frac{1-e^{t}}{2}$. Define the heat flow $P_{t}f(x) = \mathbb{E}_{\xi}f(x_{1}\xi_{1}(t), \ldots, x_{n} \xi_{n}(t))$, where we take expectation with respect to $\xi$. Clearly $P_{0}f=f$ and $P_{\infty}f=\mathbb{E}f$. It follows from the definition that $$ P_{t}f(x) =\frac{1}{2^{n}}\sum_{\eta \in \{-1,1\}^{n}} f(\eta_{1}x_{1}, \ldots, \eta_{n}x_{n}) \prod_{j=1}^{n}\frac{1+\eta_{j}e^{-t}}{2} = \mathbb{E}_{y}f(y)\prod_{j=1}^{n}(1+e^{-t}x_{i}y_{i}). $$ The above identity implies that $\partial_{t} P_{t}f = -\Delta P_{t}f$, where $\Delta = \sum_{j=1}^{n} \partial_{j}$. If we let $$ \nabla _{j} f(x) = \frac{f(x_{1}, \ldots, x_{j-1},1, x_{j+1}, \ldots, n)-f(x_{1}, \ldots, x_{j-1},1,x_{j+1}, \ldots, x_{n})}{2}, $$ then it follows from the identity that $\nabla_{j} P_{t} f = e^{-t}P_{t} \nabla_{j}f$. Notice an important difference: if you would use $\partial_{j}$ you would not get the extra factor $e^{-t}$, and this factor will be imprortant for this argument. Clearly $\partial_{j} f = x_{j} \nabla _{j}f$. Let $\tilde{\nabla}f = (\nabla_{1}f, \ldots, \nabla_{n}f)$. Finally we need two more tings: an integration by parts formula $\mathbb{E}f\Delta f = \mathbb{E}\nabla f\cdot \nabla f = \mathbb{E} \tilde{\nabla f}\cdot \tilde{\nabla}f$ (try to see that in both side you sum squares of distances $(f(x)-f(y))^{2}$ where $x$ is the neighbor vertex of $y$), and the fact that $t \mapsto \mathbb{E} |P_{t} f|^{2}$ is decreasing. To see the second statement notice that $$ \partial_{t} E|P_{t}f|^{2} = -2\mathbb{E}P_{t}f \Delta P_{t}f = -2\mathbb{E} |\nabla P_{t} f|^{2}\leq 0. $$

Thus

\begin{align} \mathbb{E}(f-\mathbb{E}f)^{2} &= -\mathbb{E} f \int_{0}^{\infty} \partial_{t}P_{t}f\, \mathrm{d}t = \int_{0}^{\infty}\mathbb{E}f\Delta P_{t}f \,\mathrm{d}t = \int_{0}^{\infty}\mathbb{E}P_{t/2}f \Delta P_{t/2}f \, \mathrm{dt}\leq \\ &=\int_{0}^{\infty}\mathbb{E} |\tilde{\nabla} P_{t/2} f|^{2} \mathrm{d}t =\int_{0}^{\infty}e^{-t}\mathbb{E} |P_{t/2}\tilde{\nabla} f|^{2} \mathrm{d}t \leq \int_{0}^{\infty}e^{-t}\mathbb{E} |\tilde{\nabla} f|^{2} \mathrm{d}t=\mathbb{E} |\nabla f|^{2}. \end{align}

Answer 4

Here are two more additional slightly different inductive proofs which are specific to boolean functions.

First proof (induction with two-sided gradient).

Let $f :\{-1,1\}^{n} \mapsto \{-1,1\}$, and let $A_{f} := \mathbb{P}(f=1)$. Then $\mathbb{E} f = 2A_{f}-1$ and $\mathbb{E} |f-\mathbb{E}f|^{2}=4A_{f}(1-A_{f})$. The proof of $$ \mathbb{E} \sum_{j=1}^{n} |\partial_{j} f| \geq 4A_{f}(1-A_{f})=:B(A_{f}). $$ is by induction on $n$. The base case $n=1$ is simple. Assume it holds for boolean functions on $\{-1,1\}^{n-1}$. Let $f_{-1}=f(-1,x_{2}, \ldots, x_{n})$ and let $f_{1}=f(1,x_{2}, \ldots, x_{n})$. We have \begin{align} \mathbb{E} \sum_{j=1}^{n} |\partial_{j} f| &= \mathbb{E} |\partial_{1} f| +\mathbb{E} \sum_{j=2}^{n} |\partial_{j} f| \geq |A_{f_{1}}-A_{f_{-1}}|+\frac{1}{2}\left(\sum_{j=2}^{n} |\partial_{j} f_{-1}|+ \sum_{j=2}^{n} |\partial_{j} f_{1}|\right) \\ &\stackrel{induction}{\geq} |A_{f_{1}}-A_{f_{-1}}|+\frac{B(A_{f-1})+B(A_{f_{1}})}{2}. \end{align} To close the induction it suffices to show following two-point inequality: $$ |A_{f_{1}}-A_{f_{-1}}|+\frac{B(A_{f-1})+B(A_{f_{1}})}{2} \geq B\left(\frac{A_{f_{1}}+A_{f_{-1}}}{2}\right) = B(A_{f}) $$

which is true because $B\left(\frac{A_{f_{1}}+A_{f_{-1}}}{2}\right) - \frac{B(A_{f_{-1}})+B(A_{f_{1}})}{2} = |A_{f_{1}}-A_{f_{-1}}|^{2}$.

Second proof (induction with one-sided gradient).

Write $f :\{-1,1\}^{n} \mapsto \{-1,1\}$ as $f =2\cdot 1_{A}-1$, where $1_{A} :\{-1,1\}^{n} \mapsto \{0,1\}$ is an indicator function of set $A \subset \{-1,1\}^{n}$. Clearly $\sum_{j=1}^{n} \mathrm{Inf}_{j}(f) = \sum_{j=1}^{n} \mathrm{Inf}_{j}(g)$, and $\mathbb{E} |f-\mathbb{E} f|^{2} = 4|A|(1-|A|)$, where $|A| = \frac{\#A}{2^{n}}$.

Let $g=1_{A}$, and let $M(g) = \sum_{j=1}^{n}(g(x)-g(x^{\oplus j}))_{+}$, where $(y)_{+}=\max(0,y)$. Notice that $M(g)+M(1-g)=\sum_{j=1}^{n}|g(x)-g(x^{\oplus j})|$, and hence $\mathbb{E} M(g) + \mathbb{E} M(1-g) = \sum_{j=1}^{n} \mathrm{Inf}_{j}(g)$. It suffices to prove the following isoperimetric inequality $$ \mathbb{E} M(g) \geq B(|A|):=2|A|(1-|A|). \quad(*) $$ Indeed, applying the inequality (*) to $g$ and $1-g$ separately, and summing them up we obtain $\sum \mathrm{Inf}_{j}(g) \geq 4|A|(1-|A|)$.

The proof of (*) is by induction on $n$. When $n=1$ it follows from the fact that $B(0)=B(1)=0$ and $B(1/2)=1/2$. Assume the inequality is proved for subsets of $\{-1,1\}^{n-1}$. We can write $1_{A}(1, x_{2}, \ldots, x_{n})=1_{A_{1}}$ and $1_{A}(-1, x_{2},\ldots,x_{n})=1_{A_{0}}$ for some subsets $A_{1}, A_{0} \subset \{-1,1\}^{n-1}$. All we know is that $|A| = \frac{|A_{1}|+|A_{0}|}{2}$. Notice that $$ \mathbb{E}(g(x)-g(x^{\oplus 1}))_{+} = \frac{1}{2}\mathbb{E}|1_{A_{0}}-1_{A_{1}}|\geq ||A_{0}|-|A_{1}|| $$

Hence $$ \mathbb{E} M(g) = \mathbb{E} (g(x)-g(x^{\oplus 1}))_{+}+\mathbb{E} \sum_{j=2}^{n}(g(x)-g(x^{\oplus j}))_{+} \geq \frac{||A_{0}|-|A_{1}||}{2}+\frac{\mathbb{E}M(1_{A_{0}})+\mathbb{E} M(1_{A_{1}})}{2} \stackrel{induction}{\geq} \frac{||A_{0}|-|A_{1}||}{2}+\frac{B(|A_{0}|)+B(|A_{1}|)}{2} \geq B\left(\frac{|A_{0}|+|A_{1}|}{2}\right)=B(|A|), $$ where the last inequality follows from the fact that $B(x)=2x(1-x)$ satisfies the two-point inequality $$ \frac{|x-y|}{2}+\frac{B(x)+B(y)}{2}\geq B\left(\frac{x+y}{2}\right) $$ for all $x,y \in [0,1]$. Indeed, $ B\left(\frac{x+y}{2}\right) - \frac{B(x)+B(y)}{2} = \frac{|x-y|^{2}}{2}$ completes the proof.

A comment about these two proofs: one may argue that these two gradients are kind of the same because $\mathbb{E} M(g) = \frac{1}{2} \mathbb{E} \sum_{j=1}^{n}|g(x)-g(x^{\oplus j})|$, and therefore these two proofs are the same. You would be correct with that, but if you put a power, say you consider $\mathbb{E} \sqrt{M(g)}$, then the second proof would work well, and the first one would fail to give you decent lower bounds. So in practice $M(g)$ inducts much better than $|\nabla g|$.

Answer 5

Proving Poincaré inequality by differentiating another (parent) inequality.

One can try first to prove a different inequality by some inductive method (or another technique), differentiate it and get Poincaré. Here is one such example.

Poincaré from log-Sobolev

log-Sobolev inequality says that

$$ \mathbb{E} f^{2} \log f^{2} - (\mathbb{E} f^{2}) \log (\mathbb{E}f^{2}) \leq 2\mathbb{E} |\nabla f|^{2}. $$

If you apply log-Sobolev to $f(x)=1+\varepsilon g(x)$ and take $\varepsilon \to 0$, the linear terms will cancel, the terms corresponding to $\varepsilon^{2}$ will give you Poincaré inequality.

There are many ways to prove log-Sobolev without using Fourier analysis. Here are couple of ways:

1. First proof: log-Soblev, like variance, also tenzorizes so it suffices to verify it on two-point space.
2. Second proof: you can differentiate hypercontractivity $\|P_{t}f\|_{q} \leq \|f\|_{p}$, $e^{-2t}\leq \frac{p-1}{q-1}$ (see in a literature how hypercontractivity is proved via log-Sobolev) and get log-Sobolev. Hypercontractivity itself can be proved by a) induction as Beckner and Bonami did. Or you can also induct on a bilinear form (to avoid use of Minkowski's inequality), i.e,. to prove $$ \mathbb{E} P_{t}f(x)\, g(y) = \mathbb{E} f(x)g(y) \prod_{j=1}^{n}(1+e^{-t}x_{i}y_{i})\leq \|f\|_{p} \|g\|_{q'}, $$ where $q'$ is the conjugate exponent of $q$, and $e^{-2t}\leq \frac{p-1}{q-1}$. The last inequality is the same as $$ \mathbb{E} f^{a}(x)g^{b}(y)\prod_{j=1}^{n}(1+e^{-t}x_{i}y_{i}) \leq (\mathbb{E} f)^{a} (\mathbb{E} g)^{b} \quad (*) $$ holds for all nonnegative $f,g$ and $e^{-2t}\leq (1-1/a)(1-1/b)$ here $a,b \in (0,1)$. To get (*) you induct on $n$, i.e., just iterate the case $n=1$. The case $n=1$ corresponds to the following 4-point inequality $$ \frac{1}{4}\left[ (x^{a}u^{b}+y^{a}v^{b})(1+e^{-t})+(x^{a}v^{b}+y^{a}u^{b})(1-e^{-t}) \right]\leq \left(\frac{x+y}{2}\right)^{a}\left(\frac{u+v}{2}\right)^{b} $$ holds for all non-neagtive $a=f(1), b=f(-1), u=g(1), v=g(-1)$ numbers.