If we believe that the Majority Is Stablest Theorem should be true, then we also have to believe in its “Gaussian special case”. Let’s see what this Gaussian special case is.

Suppose $f : {\mathbb R}^n \to [-1,1]$ is a “nice” function (smooth, say, with all derivatives bounded) having $\mathop{\bf E}[f] = 0$. You’re encouraged to think of $f$ as (a smooth approximation to) the indicator $\pm 1_A$ of some set $A \subseteq {\mathbb R}^n$ of Gaussian volume $\mathrm{vol}_\gamma(A) = \tfrac{1}{2}$. Now consider the Boolean function $g : \{-1,1\}^{nM} \to \{0,1\}$ defined by \[ g = f \circ \text{BitsToGaussians}_{M}^{n}. \] Using the multidimensional Central Limit Theorem, for any $\rho \in (0,1)$ we should have \[ \mathbf{Stab}_\rho[g] \xrightarrow{M \to \infty} \mathbf{Stab}_\rho[f], \] where on the left we have Boolean noise stability and on the right we have Gaussian noise stability. Using $\mathop{\bf E}[g] \to \mathop{\bf E}[f] = 0$, the Majority Is Stablest Theorem would tell us that \[ \mathbf{Stab}_\rho[g] \leq 1 – \tfrac{2}{\pi}\arccos \rho + o_\epsilon(1), \] where $\epsilon = \mathbf{MaxInf}[g]$. But $\epsilon = \epsilon(M) \to 0$ as $M \to \infty$. Thus we should simply have the Gaussian noise stability bound \begin{equation} \label{eqn:vol12-Borell} \mathbf{Stab}_\rho[f] \leq 1 – \tfrac{2}{\pi}\arccos \rho. \end{equation} (By a standard approximation argument this extends from “nice” $f : {\mathbb R}^n \to [-1,1]$ with $\mathop{\bf E}[f] = 0$ to any measurable $f : {\mathbb R}^n \to [-1,1]$ with $\mathop{\bf E}[f] = 0$.) Note that the upper bound \eqref{eqn:vol12-Borell} is achieved when $f$ is the $\pm 1$-indicator of any halfspace through the origin; see Corollary 20. (Note also that if $n = 1$ and $f = \mathrm{sgn}$, then the function $g$ is simply $\mathrm{Maj}_M$.)

The “isoperimetric inequality” \eqref{eqn:vol12-Borell} is indeed true, and is a special case of a theorem first proved by Borell **[Bor85]**.

Borell’s Isoperimetric Theorem (volume-${\frac{\mathbf 1}{\mathbf 2}}$ case)Fix $\rho \in (0,1)$. Then for any $f \in L^2({\mathbb R}^n,\gamma)$ with range $[-1,1]$ and $\mathop{\bf E}[f] = 0$, \[ \mathbf{Stab}_{\rho}[f] \leq 1 – \tfrac{2}{\pi}\arccos \rho, \] with equality if $f$ is the $\pm 1$-indicator of any halfspace through the origin.

Remark 41In Borell’s Isoperimetric Theorem, nothing is lost by restricting attention to functions with range $\{-1,1\}$, i.e., by considering only $f = \pm 1_A$ for $A \subseteq {\mathbb R}^n$. This is because the case of range $[-1,1]$ follows straightforwardly from the case of range $\{-1,1\}$, essentially because $\sqrt{\mathbf{Stab}_\rho[f]} = \|\mathrm{U}_{\sqrt{\rho}} f\|_2$ is a convex functional of $f$; see the exercises.

More generally, Borell showed that for any fixed volume $\alpha \in [0,1]$, the maximum Gaussian noise stability of a set of volume $\alpha$ is no greater than that of a halfspace of volume $\alpha$. We state here the more general theorem, using range $\{0,1\}$ rather than range $\{-1,1\}$ for future notational convenience (and with Remark 41 applying equally):

Borell’s Isoperimetric TheoremFix $\rho \in (0,1)$. Then for any $f \in L^2({\mathbb R}^n, \gamma)$ with range $[0,1]$ and $\mathop{\bf E}[f] = \alpha$, \[ \mathbf{Stab}_{\rho}[f] \leq \Lambda_\rho(\alpha). \] Here $\Lambda_\rho(\alpha)$ is theGaussian quadrant probabilityfunction, discussed in Exercise 5.33, and equal to $\mathbf{Stab}_\rho[1_H]$ for any (every) halfspace $H \subseteq {\mathbb R}^n$ having Gaussian volume $\mathrm{vol}_\gamma(H) = \alpha$.

We’ve seen that the volume-$\tfrac{1}{2}$ case of Borell’s Isoperimetric Theorem is a special case of the Majority Is Stablest Theorem, and similarly, the general version of Borell’s theorem is a special case of the General-Volume Majority Is Stablest Theorem mentioned at the beginning of the chapter. As a consequence, proving Borell’s Isoperimetric Theorem is a *prerequisite* for proving the General-Volume Majority Is Stablest Theorem. In fact, our proof in Section 7 of the latter will be a reduction to the former.

The proof of Borell’s Isoperimetric Theorem itself is not too hard; one of five known proofs, the one due to Mossel and Neeman **[MN12]**, is outlined in the exercises. If our main goal is just to prove the basic Majority Is Stablest Theorem, then we only need the volume-$\tfrac{1}{2}$ case of Borell’s Isoperimetric Inequality. Luckily, there’s a very simple proof of this volume-$\tfrac{1}{2}$ case for “many” values of $\rho$, as we will now explain.

Let’s first slightly rephrase the statement of Borell’s Isoperimetric Theorem in the volume-$\tfrac{1}{2}$ case. By Remark 41 we can restrict attention to sets; then the theorem asserts that among sets of Gaussian volume $\tfrac{1}{2}$, halfspaces through the origin have maximal noise stability, for each positive value of $\rho$. Equivalently, halfspaces through the origin have minimal noise *sensitivity* under correlation $\cos \theta$, for $\theta \in (0,\frac{\pi}{2})$. The formula for this minimal noise sensitivity was given as inequality (2) in our proof of Sheppard’s Formula. Thus we have:

Equivalent statement of the volume-${\frac{\mathbf 1}{\mathbf 2}}$ Borell Isoperimetric TheoremFix $\theta \in (0,\frac{\pi}{2})$. Then for any $A \subset {\mathbb R}^n$ with $\mathrm{vol}_\gamma(A) = \tfrac{1}{2}$, \[ \mathop{\bf Pr}_{\substack{(\boldsymbol{z}, \boldsymbol{z}') \\\text{$\cos \theta$-correlated}}}[1_A(\boldsymbol{z}) \neq 1_A(\boldsymbol{z}')] \geq \tfrac{\theta}{\pi}, \] with equality if $A$ is any halfspace through the origin.

In the remainder of this section we’ll show how to prove this formulation of the theorem whenever $\theta = \frac{\pi}{2\ell}$, where $\ell$ is a positive integer. This gives the volume-$\tfrac{1}{2}$ case of Borell’s Isoperimetric Inequality for all $\rho$ of the form $\arccos\frac{\pi}{2\ell}$, $\ell \in {\mathbb N}^+$; in particular, for an infinite sequence of $\rho$’s tending to $1$. To prove the theorem for these values of $\theta$, it’s convenient to introduce notation for the following noise sensitivity variant:

Definition 42For $A \subseteq {\mathbb R}^n$ and $\delta \in {\mathbb R}$ (usually $\delta \in [0,\pi]$) we write $\mathbf{RS}_A(\delta)$ for the defined by \[ \mathbf{RS}_A(\delta) = \mathop{\bf Pr}_{\substack{(\boldsymbol{z}, \boldsymbol{z}') \\ \cos \delta\text{-correlated}}}[1_A(\boldsymbol{z}) \neq 1_A(\boldsymbol{z}')]. \]

The key property of this definition is the following:

Theorem 43For any $A \subseteq {\mathbb R}^n$ the function $\mathbf{RS}_A(\delta)$ is subadditive; i.e., \[ \mathbf{RS}_A(\delta_1 + \cdots + \delta_\ell) \leq \mathbf{RS}_A(\delta_1) + \cdots + \mathbf{RS}_A(\delta_\ell). \] In particular, for any $\delta \in {\mathbb R}$ and $\ell \in {\mathbb N}^+$, \[ \mathbf{RS}_A(\delta) \leq \ell \cdot \mathbf{RS}_A(\delta/\ell). \]

*Proof:* Let $\boldsymbol{g}, \boldsymbol{g}’ \sim \mathrm{N}(0,1)^n$ be drawn independently and define $\boldsymbol{z}(\theta) = (\cos\theta)\boldsymbol{g} + (\sin\theta)\boldsymbol{g}’$. Geometrically, as $\theta$ goes from $0$ to $\frac{\pi}{2}$ the random vectors $\boldsymbol{z}(\theta)$ trace from $\boldsymbol{g}$ to $\boldsymbol{g}’$ along the origin-centered ellipse passing through these two points. The random vectors $\boldsymbol{z}(\theta)$ are jointly normal, with each individually distributed as $\mathrm{N}(0,1)^n$. Further, for each fixed $\theta, \theta’ \in {\mathbb R}$ the pair $(\boldsymbol{z}(\theta), \boldsymbol{z}(\theta’))$ constitute $\rho$-correlated Gaussians with \[ \rho = \cos\theta \cos\theta' + \sin\theta \sin\theta' = \cos(\theta' - \theta). \] Now consider the sequence $\theta_0, \dots, \theta_\ell$ defined by the partial sums of the $\delta_i$’s, i.e., $\theta_j = \sum_{i = 1}^j \delta_i$. We get that $\boldsymbol{z}(\theta_0)$ and $\boldsymbol{z}(\theta_\ell)$ are $\cos(\delta_1 + \cdots + \delta_\ell)$-correlated, and that $\boldsymbol{z}(\theta_{j-1})$ and $\boldsymbol{z}(\theta_{j})$ are $\cos\delta_j$-correlated for each $j \in [\ell]$. Thus \begin{align} \mathbf{RS}_A(\delta_1 + \cdots + \delta_\ell) &= \mathop{\bf Pr}[1_A(\boldsymbol{z}(\theta_0)) \neq 1_A(\boldsymbol{z}(\theta_\ell))] \nonumber\\ &\leq \sum_{j=1}^\ell \mathop{\bf Pr}[1_A(\boldsymbol{z}(\theta_{j})) \neq 1_A(\boldsymbol{z}(\theta_{j-1}))] = \sum_{j=1}^\ell \mathbf{RS}_A(\delta_j), \label{eqn:ellipse-union-bound} \end{align} where the inequality is the union bound. $\Box$

With this subadditivity result in hand, it’s indeed easy to prove the equivalent statement of the volume-$\tfrac{1}{2}$ Borell Isoperimetric Theorem for any $\theta \in \{\frac{\pi}{4}, \frac{\pi}{6}, \frac{\pi}{8}, \frac{\pi}{10}, \dots\}$. As we’ll see in Section 7, the case of $\theta = \frac{\pi}{4}$ can be used to give an excellent UG-hardness result for the Max-Cut CSP.

Corollary 44The equivalent statement of the volume-$\tfrac{1}{2}$ Borell Isoperimetric Theorem holds whenever $\theta = \frac{\pi}{2\ell}$ for $\ell \in {\mathbb N}^+$.

*Proof:* The exact statement we need to show is $\mathbf{RS}_A(\frac{\pi}{2\ell}) \geq \frac{1}{2\ell}$. This follows by taking $\delta = \frac{\pi}{2}$ in Theorem 43 because \[ \mathbf{RS}_A(\tfrac{\pi}{2}) = \mathop{\bf Pr}_{\substack{(\boldsymbol{z}, \boldsymbol{z}') \\ 0\text{-correlated}}}[1_A(\boldsymbol{z}) \neq 1_A(\boldsymbol{z}')] = \tfrac12, \] using that $0$-correlated Gaussians are independent and that $\mathrm{vol}_\gamma(A) = \frac12$. $\Box$

Remark 45Although Sheppard’s Formula already tells us that equality holds in this corollary when $A$ is a halfspace through the origin, it’s also not hard to derive this directly from the proof. The only inequality in the proof, \eqref{eqn:ellipse-union-bound}, is an equality when $A$ is a halfspace through the origin, because the elliptical arc can only cross such a halfspace $0$ or $1$ times.

Remark 46Suppose that $A \subseteq {\mathbb R}^n$ not only has volume $\tfrac{1}{2}$, it has the property that $x \in A$ if and only if $-x \not \in A$; in other words, the $\pm 1$-indicator of $A$ is an odd function. (In both statements, we allow a set of measure $0$ to be ignored.) An example set with this property is any halfspace through the origin. Then $\mathbf{RS}_A(\pi) = 1$, and hence we can establish Corollary 44 more generally for any $\theta \in \{\frac{\pi}{1}, \frac{\pi}{2}, \frac{\pi}{3}, \frac{\pi}{4}, \frac{\pi}{5}, \dots\}$ by taking $\delta = \pi$ in the proof.

## Leave a Reply