Isoperimetric Inequalities Made Simpler

Isoperimetric inequalities are fundamental results in mathematics with a myriad of applications. The main topic of this paper is discrete isoperimetric inequalities, and more specifically isoperimetric inequalities over the hypercube $\{0,1\}^{n}$. Classical results along these lines are due to Harper, Bernstein, Lindsey and Hart [Har66, Ber67, Lin64, Har76], Harper [Har66], Margulis [Mar74], Talagrand [Tal93, Tal97, Tal94] and Kahn, Kalai and Linial [KKL88].

All of these theorems discuss various measures of boundaries and relations between them for Boolean functions. For a function $f\colon{\left\{0,1\right\}}^{n}\to{\left\{0,1\right\}}$ and a point $x\in{\left\{0,1\right\}}^{n}$, we define the sensitivity of $f$ at $x$, denoted by $s_{f}(x)$, to be the number of coordinates $i\in[n]$ such that $f(x\oplus e_{i})\neq f(x)$. The vertex boundary of a function $f$, denoted by $V_{f}$, is the set of all $x$’s such that $s_{f}(x)>0$, and the edge boundary $E_{f}$ of $f$ is defined to be the set of edges $(x,x\oplus e_{i})$ of the hypercube whose endpoints are assigned different values by $f$. The most basic isoperimetric result related to Boolean functions, known as Poincaré’s inequality, asserts that $\frac{\left|{E_{f}}\right|}{2^{n}}\geqslant{\sf var}(f)$, i.e. the edge boundary of a function $f$ cannot be too small.⁵⁵5We remark that the term “Poincaré’s inequality” comes from the theory of functional inequalities and Markov chains and refers to a much more general result, see for example [KT14, Section 2]. In the case of graphs, it asserts that for a graph $G$, if the first non-trivial eigenvalue of its Laplacian $L$ is at least $\lambda$, then $\|Lf\|_{2}\geqslant\lambda\|f-\mathop{\mathbb{E}}[f]\|_{2}$. In our example, the Laplacian $L$ is $L=I-\frac{1}{n}A$ where $A$ is the adjacency matrix of the Boolean hypercube, and $\lambda$ is $2/n$. The edge isoperimetric inequality for the hypercube, due to Harper, Bernstein, Lindsey and Hart [Har66, Ber67, Lin64, Har76], is a strengthening of that statement, asserting that for a fixed value of $\mathop{\mathbb{E}}[f]$, the functions that minimize the edge boundary $\frac{\left|{E_{f}}\right|}{2^{n}}$ are indicator functions of initial segments in lexicographical orderings of the hypercube. In particular, this result implies that if $f$ is a non-constant Boolean function, then $\frac{\left|{E_{f}}\right|}{2^{n}}\geqslant\mathop{\mathbb{E}}[f]\log\left(\frac{1}{\mathop{\mathbb{E}}[f]}\right)$ (here and throughout, $\log$ means the logarithm function with base $2$). The vertex isoperimetric inequality, due to Harper [Har66], asserts that among all Boolean function of a given measure, the functions that minimize the size of the vertex boundary $V_{f}$ are the indicator functions of initial segments in simplicial orderings of the hypercube. Margulis [Mar74] proved a result that combines the notion of edge boundary and vertex boundary, showing that for all functions $f$ one has that $\frac{\left|{V_{f}}\right|}{2^{n}}\cdot\frac{\left|{E_{f}}\right|}{2^{n}}\geqslant\Omega({\sf var}(f)^{2})$.

Talagrand considered a different notion of boundary for a function $f$, namely the quantity ${\mathop{\mathbb{E}}_{x}\left[{\sqrt{s_{f}(x)}}\right]}$, which we will refer to as the Talagrand boundary of $f$. Here and throughout, the distribution over $x$ will be uniform over the hypercube ${\left\{0,1\right\}}^{n}$. Talagrand proved a number of results about this quantity [Tal93, Tal97], the most basic of which asserts that ${\mathop{\mathbb{E}}_{x}\left[{\sqrt{s_{f}(x)}}\right]}\geqslant\Omega({\sf var}(f))$. Using a simple application of the Cauchy-Schwarz inequality one sees that the result of Talagrand implies Margulis’ theorem. Talagrand then went on and strengthened the result for functions with small variance, proving the following theorem:

We remark that Talagrand’s result is in fact more general and slightly stronger. First, Talagrand proves that the above inequality holds for the $p$-biased measure of the cube if one inserts a factor of $\frac{\min(p,1-p)}{\sqrt{p(1-p)}}$ to the right hand side. The result and techniques of the current paper also generalize to the $p$-biased measure in a straight-forward manner, and we focus on the case that $p=1/2$ for simplicity. Second, Talagrand considers a variant of the quantity $s_{f}(x)$ wherein $s_{f}(x)$ is defined to be $0$ for $x$ such that $f(x)=0$. The results we state below also hold with this stronger definition.

While Theorem 1.1 can be seen to be tight up to constant factors (as can be seen by considering sub-cubes), it leaves something to be desired: it is incomparable to yet another prominent isoperimetric result – the KKL theorem [KKL88]. The KKL Theorem is concerned with the influence of coordinates on a function. For a coordinate $i\in[n]$, the influence of $i$ is defined by

In words, it is the fraction of edges along direction $i$ that are in the edge boundary of $f$. The KKL theorem [KKL88] asserts that any function must have a variable that is at least somewhat influential; more quantitatively, they proved that $\max_{i}I_{i}[f]\geqslant\Omega\left(\frac{\log n}{n}{\sf var}(f)\right)$.

Since the isoperimetric results of Talagrand and of KKL look very different (as well as the techniques that go into their proofs), Talagrand asked whether one can establish a single isoperimetric inequality that is strong enough to capture both of these results simultaneously. In [Tal97], Talagrand conjectures such a statement, and makes some progress towards it. Namely, he shows that there exists $\alpha\in(0,1/2]$ such that for any non-constant function $f\colon{\left\{0,1\right\}}^{n}\to{\left\{0,1\right\}}$ it holds that

for some absolute constant $c>0$. This inequality can be seen to imply a weaker result along the lines of the KKL theorem,⁶⁶6Namely that there is $\beta>0$ such that if ${\sf var}(f)\geqslant\Omega(1)$, $\max_{i}I_{i}[f]\geqslant\Omega((\log n)^{\beta}/n)$. but is not enough to fully recover it. Talagrand conjectured that the above inequality holds for $\alpha=1/2$, a statement that is strong enough to directly imply the KKL theorem.

Recently, Eldan and Gross [EG] introduced techniques from stochastic processes to the field, and used these to prove that Talagrand’s conjecture is true, i.e. that one may take $\alpha=1/2$ in (1).

We show a unified and simple Fourier analytic approach, based on random restrictions, to establish the results mentioned above, as well as a strengthening of Friedgut’s junta theorem [Fri98]. Our results are:

1. 1.

   Classical isoperimetric inequalities. We give Fourier analytic proofs of the inequalities above by Margulis, Talagrand and Eldan-Gross, as well as of robust versions of them. Our proof technique also unravels a connection between these isoperimetric inequalities and other classical results in the area, such as the Friedgut junta theorem [Fri98] and Bourgain’s tail theorem [Bou02]. The fact that such purely Fourier analytic proof exists is quite surprising to us, as the quantity ${\mathop{\mathbb{E}}_{x}\left[{\sqrt{s_{f}(x)}}\right]}$ does not seem to relate well to Fourier analytic methods (and indeed, the proof of Talagrand proceeds by induction, whereas the proof of Eldan and Gross uses stochastic calculus).

2. 2.

   Strengthened junta theorems. We establish a strengthening of Friedgut’s theorem in which the assumption that the average sensitivity of $f$ is small, i.e. that ${\mathop{\mathbb{E}}_{x}\left[{s_{f}(x)}\right]}$ is small, is replaced by the weaker condition that ${\mathop{\mathbb{E}}_{x}\left[{s_{f}(x)^{p}}\right]}$ is small, for $p$ slightly larger than $1/2$.

In the rest of this introductory section, we describe our results in more detail.

We give simpler proofs for the results below, which are due to Talagrand [Tal93] and Eldan-Gross [EG].

Our technique is more general, and can be used to prove more robust versions of Theorems 1.2, 1.3. For a $2$-coloring of the edges of the hypercube ${\sf col}\colon E(\{0,1\}^{n})\to\{{\sf red},{\sf blue}\}$, define the red sensitivity as $s_{f,{\sf red}}(x)=0$ if $f(x)=0$, and otherwise $s_{f,{\sf red}}(x)$ is the number of sensitive edges adjacent to $x$ that are red. Similarly, define the blue sensitivity as $s_{f,{\sf blue}}(x)=0$ if $f(x)=1$ and otherwise $s_{f,{\sf blue}}(x)$ is the number of sensitive edges adjacent to $x$ that are blue. Then, defining

we have that the left hand side of Theorems 1.2, 1.3 can be replaced by ${\sf Talagrand}_{{\sf col}}(f)$ for any $2$-coloring ${\sf col}$. Such results can be used to prove the existence of nearly bi-regular structures in the sensitivity graph of $f$ which are sometimes useful in applications (for example, in [KMS18] such structures in the directed sensitivity graph are necessary to construct monotonicity testers). To get some intuition, consider the bipartite sub-graph of the hypercube consisting of sensitive edges of $f$, and suppose that we want to find a large sub-graph of it which is nearly regular, in the sense that the degrees of one side are between $d$ and $2d$, while the degrees of the other side are at most $d$ for some $d$. In that case, taking the coloring ${\sf col}_{{\sf red}}$ that assigns to all edges red or the coloring ${\sf col}_{{\sf blue}}$ that assigns all of the edges blue (which amount to Talagrand’s original formulation) gives us information about the typical degrees of vertices $x$ with $f(x)=1$ and vertices $y$ with $f(y)=0$ respectively. It doesn’t give us any information about the possible relation between the degrees of such $x$’s and such $y$’s, though. Using the coloring ${\sf col}$ appropriately, one may establish a better balance between these two degrees and get useful information on the relation between them. Establishing such robust results using the techniques of [EG] is more challenging.

Next, we study connections between Talagrand-like quantities such as ${\mathop{\mathbb{E}}_{x}\left[{\sqrt{s_{f}(x)}}\right]}$, and the notion of juntas. For a point $x\in\{0,1\}^{n}$ and a subset $J\subseteq[n]$, we denote by $x_{J}$ the point in $\{0,1\}^{J}$ corresponding to the value of $x$ on coordinates $J$.

On the one hand, it is possible that the quantity ${\mathop{\mathbb{E}}_{x}\left[{\sqrt{s_{f}(x)}}\right]}$ is constant while the function $f$ is very far from being a junta, as can be seen by taking $f$ to be the majority function. On the other hand, if we look at the expected sensitivity – that is ${\mathop{\mathbb{E}}_{x}\left[{s_{f}(x)}\right]}$ – a well known result of Friedgut [Fri98] asserts that if ${\mathop{\mathbb{E}}_{x}\left[{s_{f}(x)}\right]}=O(1)$, then $f$ is close to junta. More precisely, Friedgut’s result asserts that if ${\mathop{\mathbb{E}}_{x}\left[{s_{f}(x)}\right]}\leqslant A$, then for all $\varepsilon>0$, $f$ is $\varepsilon$-close to a $2^{O(A/\varepsilon)}$-junta. In light of this contrast, it is interesting to ask what happens if an intermediate moment of the sensitivity, say the $p$th moment for $p\in(1/2,1)$, is constant.

We prove a strengthening of Friedgut’s junta theorem [Fri98] addressing this case, morally showing that for any $p>1/2$, bounded $p$-moment of the sensitivity implies closeness to junta. More precisely:

Theorem 1.5 is tight, and can be seen as a generalization of Friedgut’s Junta Theorem (corresponding to the case that $p=1$) that is somewhat close in spirit to Bourgain’s Junta Theorem. Indeed, for all $p\geqslant 1/2$ the tribes function shows this to be tight. Here, the tribes function is the function in which we take a partition $P_{1}\cup\ldots\cup P_{m}$ of $[n]$ and define ${\sf Tribes}(x)=1$ if there is $i$ such that $x_{P_{i}}=\vec{1}$, and ${\sf Tribes}(x)=0$ otherwise. We take $P_{i}$ of equal size and the probability that ${\sf Tribes}(x)=1$ is roughly $1/2$; the correct choice of parameters is $\left|{P_{i}}\right|=\log n-\log\log n+c$ and $m=\frac{n}{\log n-\log\log n+c}$ where $c=O(1)$. For this function one has ${\mathop{\mathbb{E}}_{x}\left[{s_{{\sf Tribes}}(x)^{p}}\right]}=\Theta((\log n)^{p})$. Indeed, as $s_{{\sf Tribes}}(x)=\Theta(\log n)$ with constant probability we have the lower bound, and the upper bound follows by Jensen’s inequality and the fact that the total influence of ${\sf Tribes}$ is $\Theta(\log n)$.

As a consequence, Theorem 1.5 also implies a version of the KKL theorem for $p$th moments of sensitivity:

We note that the KKL theorem is this statement for $p=1$, and the version for $p<1$ is only stronger than the KKL theorem as always ${\mathop{\mathbb{E}}_{x}\left[{s_{f}(x)^{p}}\right]}\leqslant{\mathop{\mathbb{E}}_{x}\left[{s_{f}(x)}\right]}^{p}$.

In this section we give an outline of the proof of Theorems 1.2 and 1.3. Both results rely on the same simple observation, that, once combined with off-the-shelf Fourier concentration results, finishes the proof.

Given $f\colon{\left\{0,1\right\}}^{n}\to\{0,1\}$, we consider its Fourier coefficients $\widehat{f}(S)={\mathop{\mathbb{E}}_{x\in{\left\{0,1\right\}}^{n}}\left[{f(x)\prod\limits_{i\in S}(-1)^{x_{i}}}\right]}$ as well as its gradient $\nabla f\colon{\left\{0,1\right\}}^{n}\to\{-1,0,1\}^{n}$ defined as $\nabla f(x)=(f(x\oplus e_{i})-f(x))_{i=1,\ldots,n}$. We first observe that the square root of the sensitivity of $f$ at $x$ is nothing but $\|\nabla f(x)\|_{2}$, and also that looking at the absolute value of the $i$th entry in $\nabla f$, namely at the function $x\rightarrow\left|{f(x\oplus e_{i})-f(x)}\right|$, one has that its average is at least the absolute value of the singleton Fourier coefficient $\left|{\widehat{f}(\{i\})}\right|$. This suggests that if $f$ has significant singleton Fourier coefficients then the magnitude of the gradient should be large, and therefore the expected root of the sensitivity should also be large. Indeed, by a simple application of the triangle inequality one gets that

which is equal to $\sqrt{\sum\limits_{i=1}^{n}\widehat{f}(\{i\})^{2}}$. As the sum of all the squares of all of the Fourier coefficients is at most $1$, we get that ${\mathop{\mathbb{E}}_{x\in{\left\{0,1\right\}}^{n}}\left[{\|\nabla f(x)\|_{2}}\right]}\geqslant\sum\limits_{i=1}^{n}\widehat{f}(\{i\})^{2}$. In words, via a simple application of the triangle inequality we managed to show a lower bound of the quantity we are interested in by the level $1$ Fourier weight of the function $f$. This is already a rather interesting isoperimetric consequence, albeit rather weak.

We next show how to bootstrap this basic result into Theorems 1.2 and 1.3 via random restrictions. To get some intuition, suppose that we knew our function $f$ has significant weight on level $d$ (where $d>1$); can we utilize the above logic to say anything of interest about lower bounds of ${\mathop{\mathbb{E}}_{x\in{\left\{0,1\right\}}^{n}}\left[{\|\nabla f(x)\|_{2}}\right]}$? The answer is yes, and one way to do that is via random restrictions. If $f$ has considerable weight on level $d$, we choose a subset of coordinates $J\subseteq[n]$ by independently including each coordinate in it with probability $p=1/d$ and then restrict the coordinates inside $\overline{J}$ to a uniformly chosen value $z\in{\left\{0,1\right\}}^{\overline{J}}$. In that case, we expect the weight of $f$ to collapse from level $d$ to roughly level $pd$ , which by the choice of the parameter $p$ is roughly the first Fourier level. At that point we could apply the above logic on the restricted function and get some lower bound for the expected root of the sensitivity of the restricted function. But how does this last quantity relate to ${\mathop{\mathbb{E}}_{x\in{\left\{0,1\right\}}^{n}}\left[{\|\nabla f(x)\|_{2}}\right]}$?

Thinking about it for a moment, for a fixed point $x$, if we choose $J$ randomly as above and fix all coordinates inside $\overline{J}$, then only roughly $1/d$ of the coordinates sensitive on $x$ remain alive, hence we expect the sensitivity to drop by a factor of $1/d$ as a result of this restriction. Indeed, it can be shown that under random restrictions, the quantity ${\mathop{\mathbb{E}}_{x\in{\left\{0,1\right\}}^{n}}\left[{\|\nabla f(x)\|_{2}}\right]}$ drops by a factor of $1/\sqrt{d}$. Thus, combining this observation with the above reasoning suggests that we should get a lower bound of

and indeed this is the bound we establish.

Theorems 1.2 and 1.3 then follow from known Fourier tail bounds. Specifically, it is known that (1) if $f$ has small variance then most of its Fourier mass lies above level $d=\Omega(\log(1/{\sf var}(f)))$, and (2) if $f$ has small influences then most Fourier mass lies above level $d=\Omega(\log(1/\sum\limits_{i=1}^{n}I_{i}[f]^{2}))$.

We consider the space of real-valued functions $f:{\left\{0,1\right\}}^{n}\to{\mathbb{R}}$, equipped with the inner product $\langle{f},{g}\rangle={\mathop{\mathbb{E}}_{x\in_{R}{\left\{0,1\right\}}^{n}}\left[{f(x)g(x)}\right]}$. It is well-known that the collection of functions ${\left\{\chi_{S}\right\}}_{S\subseteq[n]}$ defined by $\chi_{S}(x)=\prod\limits_{i\in S}{(-1)^{x_{i}}}$ forms an orthonormal basis, so any function $f$ may be written as $f(x)=\sum\limits_{S\subseteq[n]}{\widehat{f}(S)\chi_{S}(x)}$ in a unique way, where $\widehat{f}(S)=\langle{f},{\chi_{S}}\rangle$. We also consider $L_{p}$ norms for $p\geqslant 1$, that are defined as $\|f\|_{p}=\left({\mathop{\mathbb{E}}_{x}\left[{\left|{f(x)}\right|^{p}}\right]}\right)^{1/p}$.

For $z\in{\left\{0,1\right\}}^{n}$, we denote by $z_{-i}\in{\left\{0,1\right\}}^{n-1}$ the vector resulting from dropping the $i$th coordinate of $z$. We denote by $(x_{i}=1,x_{-i}=z_{-i})$ the $n$-bit vector which is $1$ on the $i$th coordinate and is equal to $z$ on any other coordinate.

Note that for a Boolean function $f$, for each $x\in{\left\{0,1\right\}}^{n}$, $\partial_{i}f(x)\neq 0$ if and only if the coordinate $i$ is sensitive on $x$, and in this case its value is either $1$ or $-1$. Thus, $\|\nabla f(x)\|_{2}=\sqrt{s_{f}(x)}$, and it will be often convenient for us to use the $\ell_{2}$-norm of the gradient of $f$ in place of $\sqrt{s_{f}(x)}$.

Next, we define the level $d$ Fourier weight of a function $f$, the approximate level $d$ weight of a function $f$ and the Fourier weight of $f$ up to/ above level $d$.

For a function $f\colon{\left\{0,1\right\}}^{n}\to\mathbb{R}$, we also define the level at most $d$ part of $f$, denoted by $f^{\leqslant d}$, as $f^{\leqslant d}(x)=\sum\limits_{\left|{S}\right|\leqslant d}\widehat{f}(S)\chi_{S}(x)$. We note that by Parseval’s equality we have that $\|f^{\leqslant d}\|_{2}^{2}=W_{\leqslant d}[f]$.

For a function $f\colon\{0,1\}^{n}\to\mathbb{R}$, a set of coordinates $J\subseteq[n]$ and $z\in{\left\{0,1\right\}}^{\overline{J}}$, we define the restriction of $f$ according to $(J,z)$ as the function $f_{\overline{J}\rightarrow z}\colon\{0,1\}^{J}\to\mathbb{R}$ defined by

We refer to the coordinates of $J$ as “alive”, and refer to the coordinates of $\overline{J}$ as fixed. We will often be interested in random restrictions of a function $f$. By that, we mean that the set $J$ is chosen randomly by including in it each $i\in[n]$ independently with some probability (which is specified), and $z\in{\left\{0,1\right\}}^{\overline{J}}$ is chosen uniformly. We have the following fact, which establishes a relation between the approximate level $d$ weight of $f$ and the level $1$ weight of a random restriction of $f$ in which each $i\in[n]$ is included in $J$ with probability $\frac{1}{2d}$ (see [KKO18, Fact 4.1] and [KKK⁺, Section 3.1]).

The degree of a function $f\colon{\left\{0,1\right\}}^{n}\to\mathbb{R}$ is defined as ${\sf deg}(f)=\max\left\{\left.\left|{S}\right|\;\right|\widehat{f}(S)\neq 0\right\}$. We will need the following consequence of the Bonami-Beckner-Gross hypercontractive inequality [Bec75, Bon70, Gro75] (see also [O’D14]), showing that the $4$-norm of a low-degree function $f$ is comparable to its $2$-norm.

If ${\sf var}(f)\geqslant 2^{-16}$, then it is enough to prove a lower bound of $\gtrsim{\sf var}(f)$. Applying Lemma 3.2 on $d$’s that are powers of $2$ between $1$ and $n$, we get that

and by geometric sum, the left hand side is $\lesssim{\mathop{\mathbb{E}}\left[{\|\nabla f(x)\|_{2}}\right]}$.

We thus assume that ${\sf var}(f)\leqslant 2^{-16}$, and without loss of generality the majority value of $f(x)$ is $0$. Thus, $\mathop{\mathbb{E}}[f]\leqslant 2{\sf var}(f)$. Setting $d=\frac{1}{8}\log(1/{\sf var}(f))$, we have that