STANDARD SIMPLICES AND PLURALITIES ARE NOT THE MOST NOISE STABLE

STEVEN HEILMAN, ELCHANAN MOSSEL, AND JOE NEEMAN

Abstract. The Standard Simplex Conjecture and the Plurality is Stablest Conjecture are two conjectures stating that certain partitions are optimal with respect to Gaussian and discrete noise stability respectively. These two conjectures are natural generalizations of the Gaussian noise stability result by Borell (1985) and the Majority is Stablest Theorem (2004). Here we show that the standard simplex is not the most stable partition in Gaussian space and that Plurality is not the most stable low influence partition in discrete space for every number of parts k ≥ 3, for every value ρ ≠ 0 of the noise and for every prescribed measures for the different parts as long as they are not all equal to 1/k. Our results do not contradict the original statements of the Plurality is Stablest and Standard Simplex Conjectures in their original statements concerning partitions to sets of equal measure. However, they indicate that if these conjectures are true, their veracity and their proofs will crucially rely on assuming that the sets are of equal measures, in stark contrast to Borell’s result, the Majority is Stablest Theorem and many other results in isoperimetric theory. Given our results it is natural to ask for (conjectured) partitions achieving the optimum noise stability.

1. Introduction

Noise stability is a natural concept which appears in the study of Gaussian processes, voting, percolation and theoretical computer science. The study of partitions of the space which are optimal with respect to noise stability may be viewed as a natural extension of isoperimetric theory; see e.g. [20, Chapter 8].

The basic case which was studied most extensively is the following: which partitions of a space into two parts (with given measures) maximize noise stability? The answer to this question follows the development of isoperimetric theory: the surface-minimizing body in ℝ^{n} with prescribed Lebesgue measure is a ball [26, 29, 21]. In the sphere it is a cap, or geodesic ball [21] which in turn implies that in Gaussian space it is a half-space [2, 27, 4]. The answer to the noise stability question is analogous: half-spaces maximize the Gaussian noise stability among all sets of a given measure [3, 23, 12]. Using an invariance principle, this implies that the majority functions maximize noise stability among all low-influence functions on the discrete cube [24]. Informally, a common feature of all of the results above

Date: January 11, 2015. The first author was supported by NSF Graduate Research Fellowship DGE-0813964 and a Simons-

Berkeley Research Fellowship. Part of this work was completed while the first author visited the Network Science and Graph Algorithms program at ICERM..

The second author was supported by NSF grant DMS-1106999, NSF grant CCF 1320105, DOD ONR grant N000141110140 and grant 328025 from the Simons Foundation.

The third author was supported by NSF grant DMS-1106999 and DOD ONR grant N000141110140. Part of this work was carried out while the authors were visiting the Real Analysis in Computer Science program at the Simons Institute for the Theory of Computing.

is that the geometric nature of the optimal partition remains the same no matter what the prescribed measure is (a half-space, a cap etc.).

1.1. Partitions into more than two parts. A much more challenging question deals with partitions into more than two parts. For the isoperimetric question, it took more than 100 years to prove the “Double Bubble Theorem” [14] which determines the minimal surface area that encloses and separates two fixed volumes in ℝ^{3}. The optimal partition is given by two spheres which intersect at a 120^{∘} angle having a third spherical cap separating the two volumes. Such a partition is called a double bubble partition. It is further conjectured that multi-bubble partitions minimize the surface area when partitioning into k parts in ℝ^{n} as long as k ≤ n + 1 [28, Proposition 2] [22, p. 153]. An analogous isoperimetric result was established in Gaussian space, i.e. ℝ^{n} equipped with the standard Gaussian density. Building on the previous work on the Double Bubble Conjecture, the authors of [11] found the partition of ℝ^{n} (n ≥ 2) into three parts, each having Gaussian volume about \frac{1}{3}, that minimizes the Gaussian surface area between the three volumes. Their work shows that the optimal partition is a standard simplex partition, which can be seen as the limit of the double bubble partition scaled up around one point on the intersection. The standard simplex partition is defined by taking a regular simplex with center P, so that each element of the partition is the cone of a facet of the simplex with common base point P.

The analogies with the isoperimetric problem led the authors of [15] to conjecture that standard simplices are optimal for Gaussian noise stability.

In discrete product spaces, the questions regarding noise stability are central in studying hardness of approximation and voting. The relevant question in this setting involves lowinfluence partitions. Using a non-linear invariance principle it was shown that the majority function maximizes noise stability [24] as conjectured both in the context of hardness of approximation [17] and in voting [16]. Since plurality is the natural generalization of majority, it was conjectured in [17] that plurality is the most stable low-influence partition into k ≥ 3 parts of {1, …, k}^{n}. Furthermore it was shown in [15] that the standard simplex being optimal for Gaussian noise stability is equivalent to the statement that plurality is stablest. Therefore, the authors of [17, 15] conjectured that plurality is stablest and demonstrated a number of applications of this result in hardness of approximation and voting.

1.2. Our Results. In our main results we show that the standard simplex is not the most stable partition in Gaussian space and that plurality is not the most stable low-influence partition in discrete space for every number of parts k ≥ 3, for every value ρ ≠ 0 of the noise stability and for every prescribed measures for the different parts as long as they are not all equal to 1/k.

In other words, the optimal partitions for noise stability are of a different nature than the ones considered for partitions into three parts in isoperimetric theory. Thus, we now know that the extension of noise stability theory from two to three or more parts is very much different than the extension of isoperimetric theory from two to three or more parts. Moreover, all existing proofs which optimize noise stability of two sets [3, 19, 15, 23, 12] must fail for more than three sets, since these proofs rely on the fact that a half-space optimizes noise stability with respect to any measure restriction.

1.3. Proof Techniques. The main new ingredient in our work is developed in Section §4, in particular, Lemma 4.1. Here it is shown that the Ornstein-Uhlenbeck operator applied to the indicator function of a simplicial cone becomes holomorphic when restricted to certain lines. This holomorphicity condition, when combined with a first variation argument (i.e. an infinite dimensional perturbative argument of the first order), then shows that any simplicial cone can be perturbed in a volume-preserving manner to improve its noise stability. Such a holomorphicity argument seems unavailable for the isoperimetric problem, since this argument uses the inherent nonlocality of the Ornstein-Uhlenbeck semigroup. That is, this semigroup at a point x computes an average over all points in Euclidean space. On the other hand, the local arguments used in isoperimetric theory, e.g. in the investigation of solutions of mean curvature flow [7, 9, 8], do not seem to be available in the noise stability setting. More specifically, the area of a surface is equal to the sum of the areas of many small pieces of the that surface, so it suffices to change a small portion of that surface to improve the total surface area. Yet, the noise stability of a set is not equal to the sum of the noise stabilities of many small pieces of the set, so the same logic does not apply in our setting. From this perspective, the holomorphicity argument could be surprising, since it allows for a local perturbation argument for the nonlocal quantity of the noise stability.

An additional argument we use is the the first variation argument within Lemma 3.1 which is more standard. For readers who may not be very familiar with variational arguments, we recall the basic setup and provide some references. When there is some quantity to minimize involving integrals, one wants to say that the function or set minimizing the integral has a zero derivative, in some sense. Often the space of functions or sets is infinite dimensional, so one has to be careful with what it means for the optimizer to have zero derivatives.

In our context, the notion of zero derivative of noise stability is then formalized using the first variation, as follows. Let A be a set of fixed volume and optimal noise stability, and let {A^{(t)}}_{t∈(−1,1)} be a family of sets such that A^{(0)} = A and such that the volume of A^{(t)} is equal to the volume of A. Then the rate of change of the noise stability of A^{(t)} must be zero at t = 0, assuming that the sets A^{(t)} change in a smooth manner as t changes. We employ this general principle by starting with a set A with smooth boundary, and then by smoothly perturbing the boundary of A to maintain the desired volume constraint. This argument is known as a normal variation argument, and it is standard within the literature of isoperimetric inequalities or of the calculus of variations. For just a few of many possible references which are relevant here, see [10, 6, 5]. In fact, we are dealing with the noise stability of multiple sets, and within Lemma 3.1 we perturb two sets A_{i}, A_{j} simultaneously, while leaving the remaining sets intact. Yet, the argument is similar to the case of one set, since we restrict our attention to sets which are simplicial cones.

1.4. The Original Conjectures. We note again that our results do not contradict the precise conjectures stated in [17, 15] as these are stated in the case where the measures of all partition elements are exactly 1/k. However, the authors of [17, 15] gave no indication that they believe there is something special about the case of equal measured partitions – rather, they made the conjectures that were needed for the applications presented in their paper.

2. Definition and Statement of Main Results

2.1. Gaussian Noise Stability. Let n ≥ 1, let y = (y_{1}, …, y_{n}) ∈ ℝ^{n}, and define dγ_{n}(y) := e^{−(y_{1}^{2}+···+y_{n}^{2})/2}dy/(2π)^{n/2}. Let ℓ_{2}^{n} denote the ℓ_{2} norm on ℝ^{n}. For r > 0, define B(y, r) := {x ∈ ℝ^{n}: ∥x − y∥_{ℓ_{2}^{n}} < r}.

Definition 2.1. Let n ≥ 1, n ∈ ℤ. Let ρ ∈ (−1, 1), x ∈ ℝ^{n}. Let f: ℝ^{n} → [0, 1]. The Ornstein-Uhlenbeck (or Bonami-Beckner, or noise) operator is defined by

T_{ρ}f(x) := ∫_{ℝ^{n}} f(xρ + y\sqrt{1 − ρ^{2}} )dγ_{n}(y).

Definition 2.2. Let A_{1}, …, A_{k} ⊆ ℝ^{n} be measurable, k ≤ n + 1. We say that {A_{i}}_{i=1}^{k} is a partition of ℝ^{n} if ∪_{i=1}^{k}A_{i} = ℝ^{n}, and γ_{n}(A_{i} ∩ A_{j}) = 0 for all i ≠ j, i, j ∈ {1, …, k}.

Definition 2.3. Let {A_{i}}_{i=1}^{k} be a partition of ℝ^{n}. We say that {A_{i}}_{i=1}^{k} has volumes (a_{1}, …, a_{k}) if γ_{n}(A_{i}) = a_{i} for all i = 1, …, k.

Definition 2.4 (Flat / Simplex Partitions). Let {A_{i}}_{i=1}^{k} be a partition of ℝ^{n}. We say that {A_{i}}_{i=1}^{k} is a flat partition if there exist y ∈ ℝ^{n} and {y_{i}}_{i=1}^{k} ⊆ ℝ^{n} \ {0}, such that

• For all i, j ∈ {1, …, k}, i ≠ j, y_{i} is not a positive multiple of y_{j}, and

• for all i ∈ {1, …, k}, A_{i} = y + {x ∈ ℝ^{n}: ⟨x, y_{i}⟩ = max_{j=1,...,k}⟨x, y_{j}⟩}.

If y = 0 we say that {A_{i}}_{i=1}^{k} is centered. If y ≠ 0, we say it is shifted.

A standard simplex partition is a flat partition where ∥y_{i}∥_{2} = 1 for all i and ⟨y_{i}, y_{j}⟩ = −\frac{1}{k−1} for all i ≠ j, i, j ∈ {1, …, k}. Again, we call a standard simplex partition centered if y = 0 and shifted if y ≠ 0.

Definition 2.5 (Gaussian Noise Stability). The Gaussian noise stability of a partition {A_{i}}_{i=1}^{k} is given by

S_{ρ}({A_{i}}_{i=1}^{k}) := ∑_{i=1}^{k} ∫_{ℝ^{n}} 1_{A_{i}}T_{ρ}1_{A_{i}}dγ_{n}.

Note the following probabilistic interpretation of noise stability. Let X = (X_{1}, …, X_{n}) and let Y = (Y_{1}, …, Y_{n}) ∈ ℝ^{n} be standard Gaussian random vectors such that 𝔼(X_{i}Y_{j}) = ρ1_{i=j} for all i, j ∈ {1, …, n}. Then for any A ⊆ ℝ^{n}, ∫ 1_{A}T_{ρ}1_{A}dγ_{n} = Prob((X, Y) ∈ A × A). So, Definition 2.5 can be equivalently written as ∑_{i=1}^{k} Prob((X, Y) ∈ (A_{i}, A_{i})).

2.2. Optimal Partitions are not Flat. As mentioned earlier, the result of [11] finds the partition of ℝ^{n} into three sets of fixed Gaussian measures a_{1}, a_{2}, a_{3} with |a_{i} − 1/3| < .04 for all i = 1, 2, 3 and of minimum total Gaussian surface area. This partition is always given by three 120 degree sectors, so if the a_{i} are not all 1/3 then it is a shifted standard simplex partition. This, along with the standard simplex conjecture of [24] may suggest that standard simplex partitions are always optimal. In our main result we prove that this is not the case:

Theorem 2.1. Let {A_{i}}_{i=1}^{n+1} ⊆ ℝ^{n} be a shifted flat partition with volumes a := (a_{1}, …, a_{n+1}) ≠ (1/(n + 1), …, 1/(n + 1)). Let 0 < ρ < 1. Then

S_{ρ}({A_{i}}_{i=1}^{n+1}) < sup_{{B_{i}}_{i=1}^{n+1} is a partition of ℝ^{n} with volumes (a_{1},...,a_{n+1})} S_{ρ}({B_{i}}_{i=1}^{n+1}).  (1)

where the supremum is taken over all partitions. Similarly for −1 < ρ < 0, we have that:

S_{ρ}({A_{i}}_{i=1}^{n+1}) > inf_{{B_{i}}_{i=1}^{n+1} is a partition of ℝ^{n} with volumes (a_{1},...,a_{n+1})} S_{ρ}({B_{i}}_{i=1}^{n+1}).  (2)

Our results indicate in particular that there is no straightforward generalization of the any of the methods of [3, 19, 15, 23, 12] that is applicable to the study of noise stability for more than two sets. As mentioned earlier, Theorem 2.1 also indicates a dramatic difference between the noise stability problem with two sets (where the optimal partitions are always simplex partitions) and three or more sets. This also indicates a difference between the isoperimetric problem with three sets (where in all the known cases the partitions are simplex partitions) and the noise stability problem.

2.3. Discrete Noise Stability. Using the invariance principle [24], [15, Theorem 1.10], it is by now standard to deduce discrete analogues of our main theorem. For simplicity we formulate one special case for partitions into 3 parts with 0 < ρ < 1 in Corollary 2.2 below, which only requires the Central Limit Theorem.

Definition 2.6 (Plurality). A plurality function f_{n} : {1, 2, 3}^{n} → {1, 2, 3} is a function satisfying f_{n}(x_{1}, …, x_{n}) := i whenever |{ℓ ∈ {1, …, n} : x_{ℓ} = i}| > |{ℓ ∈ {1, …, n} : x_{ℓ} = j}| for all j ≠ i, i, j ∈ {1, 2, 3}. Note that we do not prescribe any behavior in cases of ties, i.e. when {i, j, k} = {1, 2, 3} and

|{ℓ ∈ {1, …, n} : x_{ℓ} = i}| = |{ℓ ∈ {1, …, n} : x_{ℓ} = j}| > |{ℓ ∈ {1, …, n} : x_{ℓ} = k}| .

Since the values of f_{n} for ties does not concern us particularly, we will often write “plurality” or “the plurality function” to denote an arbitrary plurality function.

Definition 2.7 (Influences). Given a probability measure P on {1, 2, 3}, the i’th influence I_{i}(f) ∈ ℝ of a function f : {1, 2, 3}^{n} → {1, 2, 3} is defined by

I_{i}(f) := P [f(x_{1}, …, x_{i−1}, x_{i}, x_{i+1}, …, x_{n}) ≠ f(x_{1}, …, x_{i−1}, y, x_{i+1}, …, x_{n})],

where x_{i}, y are i.i.d. samples from P for all i = 1, …, n. We say that the sequence f_{n}: {1, 2, 3}^{n} → {1, 2, 3} has vanishing influences if

lim_{n→∞} max_{1≤i≤n} I_{i}(f_{n}) = 0.

Note that any sequence of plurality functions has vanishing influences.

Corollary 2.2 (Plurality is not Stablest). Let α, β ∈ ℝ. Consider the space {1, 2, 3} equipped with the probability measure Q̃ where

Q̃(1) = \frac{1}{3} + αn^{−1/2}, Q̃(2) = \frac{1}{3} + βn^{−1/2}, Q̃(3) = \frac{1}{3} − (α + β)n^{−1/2}.

Let P̃ be the distribution of correlated pairs on {1, 2, 3}^{2} with marginals Q̃ where the two values agree with probability ρ > 0 and are otherwise independent: for all x, y ∈ {1, 2, 3},

P̃(x, y) = ρ1_{(x=y)}Q̃(x) + (1 − ρ)Q̃(x)Q̃(y),

and let P = P̃^{n}. Let f_{n} : {1, 2, 3}^{n} → {1, 2, 3} be the sequence of plurality functions and assume (α, β) ≠ (0, 0). Then there exist a sequence g_{n}: {1, 2, 3}^{n} → {1, 2, 3} of functions of vanishing influences with respect to P such that

lim_{n→∞} P [f_{n} = i] = lim_{n→∞} P [g_{n} = i], ∀i ∈ {1, 2, 3}

and for x, y ∈ {1, 2, 3}^{n} distributed according to P,

lim_{n→∞} P [f_{n}(x) = f_{n}(y)] < lim_{n→∞} P [g_{n}(x) = g_{n}(y)].

Informally, the corollary says that plurality is not the most stable low-influence function among all functions that have the same probability of getting all outcomes, when the election is slightly biased. Here we think of n as the number of voters in an election, {1, 2, 3} as possible votes between 3 candidates, and f_{n}, g_{n} as functions which input the votes and output the winner of the election. We further note that for every fixed values of α and β a sequence of functions has vanishing influences if and only if it has vanishing influences under the uniform measure.

2.4. Bilinear Noise Stability. Given our main results, it is natural to ask what is optimal partition for noise stability when partitioning into three or more parts of unequal measures. While we do not have a conjecture for what the partition is, there is a very special case where we consider two different partitions of special sizes where the optimal partitions can be found explicitly using Borell’s results.

Proposition 2.3. Let ρ ∈ (0, 1). Then there exist partitions {A_{1}, A_{2}, A_{3}} ⊆ ℝ^{2} and {B_{1}, B_{2}, B_{3}} ⊆ ℝ^{2} with volumes a = (1/3, 1/3, 1/3) and b = (1/2, 0, 1/2) respectively, so that

∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{A_{i}(a)}T_{ρ}1_{B_{i}(b)}dγ_{2} = sup_{{C_{i}}_{i=1}^{3} is a partition of ℝ^{2} with volumes a {D_{i}}_{i=1}^{3} is a partition of ℝ^{2} with volumes b} ∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{C_{i}}T_{ρ}1_{D_{i}}dγ_{2}. (3)

Moreover the maximizing partitions (must) satisfy that A_{1} and B_{1} (and also A_{3} and B_{3}) are parallel half-spaces of measures 1/3 and 1/2.

Note in particular that the partition {A_{1}, A_{2}, A_{3}} is not a standard simplex partition. The proposition in this case follows from Borell’s results as each of the terms ∫_{ℝ^{2}} f_{1}T g_{1}dγ_{2} and ∫_{ℝ^{2}} f_{3}T g_{3}dγ_{2} is individually maximized by A_{1}, B_{1} and A_{3}, B_{3} respectively. Moreover, given the uniqueness version of Borell’s result [23, 12] these are the only partitions that achieve the maximum. We note again that in the case of partitions into two parts, even in the bilinear case of partitions {A_{1}, A_{2}} and {B_{1}, B_{2}} the optimal partitions are always half-space (standard simplex) partitions.

We further note that even if the measures are slightly perturbed for example by letting b̃ = (1/2 − ε, 2ε, 1/2 − ε) for a small ε > 0 then any (almost) optimal partitions Ã, B̃ for a, b̃ in (3) have to be close to those given by A and B in the sense that they can be matched so that γ_{n}(Ã_{i}ΔA_{i}) and γ_{n}(B̃_{i}ΔB_{i}) are small for all 1 ≤ i ≤ 3. This follows since if A, B are almost optimal for a, b̃ then they are almost optimal for a, b. The robust versions of Borell’s result given in [23, 12] then implies that A, B have to be close to the optimal partition.

2.5. Organization. In §3, we compute the first variation of the noise stability of flat partitions. This computation shows that, if a partition {A_{i}}_{i=1}^{n+1} optimizes noise stability, then T_{ρ}(1_{A_{i}} − 1_{A_{j}}) must be constant on A_{i} ∩ A_{j} for all i, j ∈ {1, …, n + 1}, i ≠ j. We will use this statement in the contrapositive form, since in §4, we show that for many flat partitions {A_{i}}_{i=1}^{n+1}, there exists i, j ∈ {1, …, n + 1} with i ≠ j such that T_{ρ}(1_{A_{i}} − 1_{A_{j}}) is not constant on A_{i} ∩ A_{j}. And therefore, many flat partitions {A_{i}}_{i=1}^{n+1} do not optimize noise stability. The Lemmas of §3 and §4 are combined in §5, where Theorem 2.1 is proved. Finally, Corollary 2.2 is shown to be a consequence of Theorem 2.1 in §6.

3. The First Variation

We compute the first variation of the noise stability, in order to understand the sets that achieve equality in (1) and (3). The following argument is a normal variation implementation of arguments from [18, Lemma 3.3], [13, Lemma 2.7]. Basically, we move some mass between two sets to show that the noise stability can be improved. The movement of mass is defined by a vector field V.

Lemma 3.1 (Normal Variation). Let ρ ∈ (−1, 0) ∪ (0, 1). Let {A_{p}}_{p=1}^{n+1} be a flat partition of ℝ^{n} with volumes (a_{1}, …, a_{n+1}). Assume that there exist i, j ∈ {1, …, n + 1} with i ≠ j such that T_{ρ}(1_{A_{i}} − 1_{A_{j}}) is not constant on A_{i} ∩ A_{j}. Then

ρ ∈ (0, 1) ⟹ S_{ρ}({A_{p}}_{p=1}^{n+1}) < sup_{{B_{p}}_{p=1}^{n+1} is a partition of ℝ^{n} with volumes (a_{1},...,a_{n+1})} S_{ρ}({B_{p}}_{p=1}^{n+1}).

ρ ∈ (−1, 0) ⟹ S_{ρ}({A_{p}}_{p=1}^{n+1}) > inf_{{B_{p}}_{p=1}^{n+1} is a partition of ℝ^{n} with volumes (a_{1},...,a_{n+1})} S_{ρ}({B_{p}}_{p=1}^{n+1}).

(4)

Proof. Let A ⊆ ℝ^{n} be a set with smooth boundary, and let N: ∂A → S^{n−1} denote the unit exterior normal to ∂A. Let V : ℝ^{n} → ℝ^{n} be specified later. Let Ψ: ℝ^{n} × (−1, 1) → ℝ^{n} such that (d/dt)|_{t=0}Ψ(x, t) = V (x) for all x ∈ ℝ^{n}, and such that Ψ(x, 0) = x for all x ∈ ℝ^{n}. For x, y ∈ ℝ^{n}, define

G(x, y) := e^{−∥ρx−y∥_{2}^{2}/[2(1−ρ^{2})]}.

Define A^{(t)} := Ψ(A, t). For f: ℝ^{n} → ℝ, using Definition 2.1, write

T_{ρ}f(x) = ∫ f(y)G(x, y)dy.  (5)

Let JΨ(y, t) denote |det DΨ(y, t)| = |det(∂Ψ_{i}(y, t)/∂y_{j})_{1≤i,j≤n}| ∈ ℝ. We then claim that

\frac{d}{dt}|_{t=0}T_{ρ}1_{A^{(t)}}(x) = ∫_{∂A} G(x, y)⟨V (y), N(y)⟩dy.  (6)

Indeed, using Ψ(y, 0) = y, we have JΨ(y, 0) = 1 for all y, and

\frac{d}{dt}|_{t=0}JΨ(y, t) = \frac{d}{dt}|_{t=0} det(1 + tDΨ(y, t) + O(t^{2}))

= \frac{d}{dt}|_{t=0}(1 + t · traceDΨ(y, t) + O(t^{2})) = ∇V (y).

So, using the chain rule and the divergence theorem,

\begin{aligned}\frac{d}{dt}|_{t=0} ∫ 1_{A^{(t)}}(y)G(x, y)dy & = \frac{d}{dt}|_{t=0} ∫_{A^{(t)}} G(x, y)dy = \frac{d}{dt}|_{t=0} ∫_{A} G(x, Ψ(y, t))JΨ(y, t)dy \\ & = ∫_{A} div_{y}(G(x, y)V (y))dy = ∫_{∂A} G(x, y)⟨V (y), N(y)⟩dy. \end{aligned} (7)

So, using G(x, y)γ_{n}(x) = G(y, x)γ_{n}(y),

\begin{matrix}\frac{d}{dt}|_{t=0} ∫ 1_{A^{(t)}}T_{ρ}1_{A^{(t)}}dγ_{n} = 2 ∫ 1_{A}(\frac{d}{dt}|_{t=0}T_{ρ}1_{A^{(t)}})dγ_{n} \\ =^{(6)} 2 ∫_{A} ∫_{∂A} G(x, y)⟨V (y), N(y)⟩dydγ_{n}(x) \\ = 2 ∫_{∂A} ∫_{A} G(x, y)dγ_{n}(x)⟨V (y), N(y)⟩dy = 2 ∫_{∂A} ∫_{A} G(y, x)dx⟨V (y), N(y)⟩γ_{n}(y)dy \\ =^{(5)} 2 ∫_{∂A} T_{ρ}1_{A}(y)⟨V (y), N(y)⟩γ_{n}(y)dy. \end{matrix} (8)

Suppose V : ℝ^{n} → ℝ^{n} satisfies

∫_{∂A}⟨V (y), N(y)⟩γ_{n}(y)dy = 0.  (9)

We then claim that Ψ is volume-preserving at t = 0. Indeed, using (6) for ρ = 0,

\frac{d}{dt}|_{t=0}γ_{n}(A^{(t)}) = ∫_{∂A}⟨V (y), N(y)⟩dγ_{n}(y).

Let N denote the exterior normal to A_{i}, so that −N is the exterior normal to A_{j}. For a subset of (∂A_{i}) ∩ (∂A_{j}), we denote γ_{n−1} as the measure γ_{n} restricted to (∂A_{i}) ∩ (∂A_{j}). Since T_{ρ}(1_{A_{i}} − 1_{A_{j}}) is continuous and not constant on A_{i} ∩ A_{j}, there exist disjoint relatively open sets U_{1}, U_{2} ⊆ (∂A_{i}) ∩ (∂A_{j}) such that γ_{n−1}(U_{1}) = γ_{n−1}(U_{2}) > 0, and such that

T_{ρ}(1_{A_{i}} − 1_{A_{j}})(u_{1}) > T_{ρ}(1_{A_{i}} − 1_{A_{j}})(u_{2}) ∀ u_{1} ∈ U_{1}, u_{2} ∈ U_{2}.  (10)

Let A := A_{i}. Let ϕ_{1}, ϕ_{2} : ℝ^{n} → [0, ∞) be C^{∞} functions such that (∂A_{i})∩(∂A_{j})∩support(ϕ_{1}) is disjoint from (∂A_{i}) ∩ (∂A_{j}) ∩ support(ϕ_{2}), and such that

∫_{U_{1}} ϕ_{1}(y)γ_{n}(y)dy = ∫_{U_{2}} ϕ_{2}(y)γ_{n}(y)dy.  (11)

Define V : ℝ^{n} → ℝ^{n} by V (y) := (ϕ_{1}(y) − ϕ_{2}(y))N. Note that V is C^{∞}, and

∫_{∂A}⟨V (y), N(y)⟩γ_{n}(y)dy = ∫_{U_{1}} ϕ_{1}γ_{n}(y)dy − ∫_{U_{2}} ϕ_{2}γ_{n}(y)dy =^{(11)} 0.

So, V satisfies (9). We can therefore compute

\frac{d}{dt}|_{t=0}S_{ρ}(\{A_{p}^{(t)}\}_{p=1}^{n+1}) = \frac{d}{dt}|_{t=0} ∫ 1_{A_{i}^{(t)}}T_{ρ}1_{A_{i}^{(t)}}dγ_{n} + \frac{d}{dt}|_{t=0} ∫ 1_{A_{j}^{(t)}}T_{ρ}1_{A_{j}^{(t)}}dγ_{n}

=^{(8)} 2 ∫_{(∂A_{i})∩(∂A_{j})} T_{ρ}1_{A_{i}}(y)⟨V (y), N(y)⟩γ_{n}(y)dy − 2 ∫_{(∂A_{i})∩(∂A_{j})} T_{ρ}1_{A_{j}}(y)⟨V (y), N(y)⟩γ_{n}(y)dy

= 2 ∫_{(∂A_{i})∩(∂A_{j})}(T_{ρ}1_{A_{i}}(y) − T_{ρ}1_{A_{j}}(y))⟨V (y), N(y)⟩γ_{n}(y)dy

= 2 ∫_{(∂A_{i})∩(∂A_{j})}(T_{ρ}1_{A_{i}}(y) − T_{ρ}1_{A_{j}}(y))(ϕ_{1}(y) − ϕ_{2}(y))γ_{n}(y)dy >^{(10)∧(11)} 0.  (12)

Finally, applying the Implicit Function Theorem as in [1, Lemma 2.4], there exists ε > 0 such that, for every t ∈ (−ε, ε), there exists a partition {Ã_{p}^{(t)}}_{p=1}^{n+1} of ℝ^{n} with volumes (a_{1}, …, a_{n+1}) such that

\frac{d}{dt}|_{t=0} ∑_{p=1}^{n+1} ∫_{ℝ^{n}} 1_{A_{p}^{(t)}}T_{ρ}1_{A_{p}^{(t)}}dγ_{n} = \frac{d}{dt}|_{t=0} ∑_{p=1}^{n+1} ∫_{ℝ^{n}} 1Ã_{p}^{(t)}T_{ρ}1Ã_{p}^{(t)}dγ_{n}.  (13)

Then (12) and (13) imply (4). □

4. Analyticity of the Ornstein-Uhlenbeck Operator

Let A be a polyhedral cone, and let ρ ∈ (−1, 0) ∪ (0, 1). In this section we show, roughly speaking, that if we restrict T_{ρ}1_{A} to a line parallel to a facet of A, then we get a holomorphic function. Let ℂ = \{x_{1} + x_{2}\sqrt{−1}: x_{1}, x_{2} ∈ ℝ\} denote the complex numbers.

The following statements establish some notation and assumptions on a partition {A_{p}}_{p=1}^{n+1}. Rather than repeating these statements multiple times below, we will instead repeatedly reference them as Assumption 1.

Assumption 1. (Geometric Assumptions) Let {A_{p}}_{p=1}^{n+1} be a flat partition of ℝ^{n} with volumes a := (a_{1}, …, a_{n+1}). Fix i, j ∈ {1, …, n + 1}, i ≠ j and let Π ⊆ ℝ^{n} be a hyperplane so that A_{i} ∩ A_{j} ⊆ Π. Assume that A_{i} and A_{j} share a common facet. Let c ∈ ℝ and let N ∈ ℝ^{n} with ∥N∥_{2} = 1 so that

Π = {x ∈ ℝ^{n}: ⟨x, N⟩ = c}.  (14)

Without loss of generality, assume that

A_{i} ⊆ {x ∈ ℝ^{n}: ⟨x, N⟩ ≤ c}.  (15)

Let int(A_{i}∩A_{j}) denote the relative interior of A_{i}∩A_{j}. Note that A_{i}∩A_{j} is a nonempty (n−1)- dimensional set. Let L ⊆ Π be any infinite line so that L ∩ int(A_{i} ∩ A_{j}) ≠ ∅. Let w ∈ ℝ^{n} so that L = {cN + tw: t ∈ ℝ}. Without loss of generality, assume A_{i} ∩ A_{j} ⊇ {cN + tw: t ≥ 1}.

The following is the key lemma used to prove Theorem 2.1.

Lemma 4.1. (Analyticity Restricted to Lines) Let ρ ∈ (−1, 0) ∪ (0, 1). Suppose Assumption 1 holds. Then the function T_{ρ}(1_{A_{i}} − 1_{A_{j}}) satisfies the following two properties.

(a) lim_{t→∞} T_{ρ}(1_{A_{i}} −1_{A_{j}})(cN +tw) = lim_{t→−∞} T_{ρ}(1_{A_{i}} −1_{A_{j}})(cN +tw) if and only if c = 0.

(b) The function t ↦ T_{ρ}(1_{A_{i}} − 1_{A_{j}})(cN + tw), initially defined for t ∈ ℝ, can be extended to a holomorphic function of t ∈ ℂ.

Proof of (a). We first assume that ρ ∈ (0, 1). By Assumption 1, A_{i} ∩A_{j} ⊇ {cN +tw: t > 1}. Also, L ∩ int(A_{i} ∩ A_{j}) ≠ 0, and A_{i}, A_{j} are cones, so

lim_{t→∞} T_{ρ}(1_{A_{i}} − 1_{A_{j}})(cN + tw) = T_{ρ}(1_{{z∈ℝ^{n}: ⟨z,N⟩≤c}} − 1_{{z∈ℝ^{n}: ⟨z,N⟩≥c}})(c)

= ∫ 1_{(−∞,c)}(cρ + s\sqrt{1 − ρ^{2}} )dγ_{1}(s) − ∫ 1_{(c,∞)}(cρ + s\sqrt{1 − ρ^{2}} )dγ_{1}(s)

= ∫_{−∞}^{(c−cρ)/\sqrt{1−ρ^{2}}} dγ_{1}(s) − ∫_{(c−cρ)/\sqrt{1−ρ^{2}}}^{∞} dγ_{1}(s) = 2 sign(c) · γ_{1}([0, |c| \frac{1 − ρ}{\sqrt{1 − ρ^{2}}} )).

So, lim_{t→∞} T_{ρ}(1_{A_{i}} − 1_{A_{j}})(cN + tw) = 0 if and only if c = 0. In order to prove (a), it remains to show that lim_{t→−∞} T_{ρ}(cN + tw) = 0. Since cN + w ∈ int(A_{i} ∩ A_{j}) by Assumption 1 and Definition 2.4, we know that ⟨y_{i}, w⟩ > ⟨y_{p}, w⟩ and ⟨y_{j}, w⟩ > ⟨y_{p}, w⟩ for all p ∈ {1, …, n + 1} \ {i, j}. So, ⟨y_{i}, −w⟩ < ⟨y_{p}, −w⟩ and ⟨y_{j}, −w⟩ < ⟨y_{p}, −w⟩ for all p ∈ {1, …, n + 1} \ {i, j}. Therefore, there exists δ > 0 and T < 0 such that, for all t < T, B(cN + tw, δ |t|) does not intersect either A_{i} or A_{j}. Hence, there is some δ′ > 0 such that

| lim sup_{t→−∞} T_{ρ}(1_{A_{i}} − 1_{A_{j}})(cN + tw)| ≤ lim sup_{t→−∞} ∫_{B(ρ(cN+|t|w),δ′t(1−ρ^{2})^{−1/2})^{c}} dγ_{n} = 0.  (16)

The proof is therefore completed for ρ ∈ (0, 1). For ρ ∈ (−1, 0), we similarly conclude that lim_{t→−∞} T_{ρ}(1_{A_{i}} − 1_{A_{j}})(cN + tw) = 0 if and only if c = 0, and lim_{t→∞} T_{ρ}(cN + tw) = 0.

□

Proof of (b). We prove this by induction on n. We first consider the case n = 2. In this case, A_{p} is a two-dimensional sector for p = 1, 2, 3. Fix i ∈ {1, 2, 3}. We will show that T_{ρ}1_{A_{i}}(cn + tw) is holomorphic in t. Without loss of generality, assume that one edge of A_{i} is parallel to the x_{2} axis. Further, without loss of generality, suppose there exist α, β, γ ∈ ℝ such that A_{i} = {(x_{1}, x_{2}) ∈ ℝ^{2} : x_{1} ≥ α, x_{2} ≥ βx_{1} + γ}. Then

T_{ρ}1_{A_{i}}(x) = ∫_{(A_{i}−ρx)/\sqrt{1−ρ^{2}}} dγ_{2} = ∫_{(α−ρx_{1})/\sqrt{1−ρ^{2}}}^{∞} ∫_{(βs+γ−ρx_{2})/\sqrt{1−ρ^{2}}}^{∞} e^{−r^{2}/2}e^{−s^{2}/2}drds/2π.

Note that the set {cN + tw: t ≥ 1} ⊆ ℝ^{2} has constant first coordinate, and the second coordinate of {cN + tw: t ≥ 1} is an affine function of t. So, defining a constant α′ := (α − ρ(cN + w)_{1})/\sqrt{1 − ρ^{2}} ∈ ℝ, (where (cN + w)_{1} is the x_{1} coordinate of cN + w), we have

T_{ρ}1_{A_{i}}(cN + tw) = ∫_{α′}^{∞} ∫_{β′s+γ′+c′t}^{∞} e^{−r^{2}/2}e^{−s^{2}/2}drds/2π.

For s, t ∈ ℝ, define

ϕ(s, t) := ∫_{β′s+γ′+c′t}^{∞} e^{−r^{2}/2}dr/\sqrt{2π} = \frac{1}{2} − ∫_{0}^{β′s+γ′+c′t} e^{−r^{2}/2}dr/\sqrt{2π}.  (17)

For fixed s ∈ ℝ, ϕ(s, t) is a holomorphic function in t. For z ∈ ℂ and fixed s ∈ ℝ, define the following function, where we interpret the integral as a contour integral.

g(z) := ∫_{0}^{β′s+γ′+c′z} e^{−r^{2}/2}dr/\sqrt{2π}.  (18)

Since e^{−r^{2}/2} is an entire function of r ∈ ℂ with no poles, the choice of the path in the definition of g does not matter. In particular, for z = (x_{1}, x_{2}) ∈ ℂ, if we choose the path that first moves from 0 to (β′s + γ′ + c′x_{1}, 0) along a straight line, and then from (β′s + γ′ + c′x_{1}, 0) to (β′s + γ′ + c′x_{1}, c′x_{2}) along a straight line, we get from (18) the bound

|g(z)| ≤ ∫_{0}^{∞} e^{−r^{2}/2} \frac{dr}{\sqrt{2π}} +| ∫_{0}^{c′x_{2}} e^{−(β′s+γ′+c′x_{1}+ir)^{2}/2}dr| ≤ \frac{1}{2}+∫_{0}^{c′x_{2}} e^{r^{2}/2}dr ≤ \frac{1}{2}+c′ |x_{2}| e^{c′x_{2}^{2}/2}.

(19)

In the penultimate estimate, we used |e^{−(x_{1}+ix_{2})^{2}}| ≤ |e^{x_{2}^{2}}|. Combining (19) and (17),

|ϕ(s, (x_{1}, x_{2}))| ≤ 1 + c′ |x_{2}| e^{c′x_{2}^{2}/2}.  (20)

Consider the function f_{ε}(z) := ∫_{α}^{1/ε} ϕ(s, z)e^{−s^{2}/2}ds, z ∈ ℂ. This function is an entire function of z ∈ ℂ, by e.g. [25, Theorem 5.4]. To prove that f(z) := T_{ρ}1_{A_{i}}(cN + zw) is holomorphic, it now suffices to show that f_{ε} converges uniformly to f on any compact subset of ℂ, as ε → 0. So, let z = (x_{1}, x_{2}) ∈ ℂ. From (20),

\begin{aligned}|f_{ε}(z) − f(z)| & ≤ ∫_{1/ε}^{∞} |ϕ(s, z)| e^{−s^{2}/2}ds \\ & ≤ ∫_{1/ε}^{∞}(1 + c′ |x_{2}| e^{c′x_{2}^{2}/2})e^{−s^{2}/2}ds ≤ (1 + c′ |x_{2}| e^{c′x_{2}^{2}/2})e^{−1/(2ε^{2})}. \end{aligned}  (21)

So, (21) gives the desired uniform convergence property, completing the proof in the case n = 2. Note that, by (20)

|f(z)| ≤ ∫_{α}^{∞} |ϕ(s, z)| e^{−s^{2}/2}ds ≤ 1 + c′ |x_{2}| e^{c′x_{2}^{2}/2}.  (22)

For the more general case, we induct on n. We are given an n-dimensional polyhedral cone Σ_{n} with n + 1 facets, and we write Σ_{n} as a union of translates of an (n − 1)-dimensional simplicial cone Σ_{n−1}, which can be taken to be one of the facets of Σ_{n}. That is, there exists u ∈ ℝ^{n} such that Σ_{n} = ∪_{s>α}(Σ_{n−1} + su). So,

T_{ρ}1_{Σ_{n}}(cN + tw) = ∫_{α′}^{∞} ∫_{Σ_{n−1}+wt} dγ_{n−1}e^{−s^{2}/2}ds/\sqrt{2π} =: ∫_{α′}^{∞} ψ(s, t)e^{−s^{2}/2}ds/\sqrt{2π}.

Now, ψ(s, t) is known, by the inductive hypothesis, to be holomorphic in t = (x_{1}, x_{2}), for each s. Moreover, by the inductive hypothesis, |ψ(s, (x_{1}, x_{2}))| ≤ 1 + c′ |x_{2}| e^{c′x_{2}^{2}/2}. We therefore truncate and make a tail estimate as in (21) to prove uniform convergence of f_{ε}(z) := ∫_{1/ε}^{∞} Ψ(s, z)e^{−s^{2}/2}ds to f(z) := T_{ρ}1_{A_{i}}(cn+zw). Finally, showing the following bound completes the inductive step.

|f(z)| ≤ ∫_{α}^{∞} |Ψ(s, z)| e^{−s^{2}/2}ds/\sqrt{2π} ≤ 1 + c′ |x_{2}| e^{c′x_{2}^{2}/2}.
□

5. The Main Theorem

Corollary 5.2 below implies the Main Theorem 2.1.

Corollary 5.1. (An Optimal Flat Partition Must be Centered)

(1) Let ρ ∈ (0, 1). Suppose {A_{i}}_{i=1}^{n+1} is a partition of ℝ^{n} satisfying

S_{ρ}({A_{i}}_{i=1}^{n+1}) = sup_{{B_{i}}_{i=1}^{n+1} is a partition of ℝ^{n} with volumes (a_{1},...,a_{n+1})} S_{ρ}({B_{i}}_{i=1}^{n+1}).

Suppose Assumption 1 holds. Then y = 0 in Assumption 1 (and in Definition 2.4).

(2) Let ρ ∈ (−1, 0). Suppose {A_{i}}_{i=1}^{n+1} is a partition of ℝ^{n} satisfying

S_{ρ}({A_{i}}_{i=1}^{n+1}) = inf_{{B_{i}}_{i=1}^{n+1} is a partition of ℝ^{n} with volumes (a_{1},...,a_{n+1})} S_{ρ}({B_{i}}_{i=1}^{n+1}).

Suppose Assumption 1 holds. Then y = 0 in Assumption 1 (and in Definition 2.4).

Proof. Fix i and j in {1, …, n + 1}, and recall the definition of c from Assumption 1. It suffices to show that if c ≠ 0 then the partition {A_{p}}_{p=1}^{n+1} is not optimal. Suppose, therefore, that c ≠ 0. Note that if T_{ρ}(1_{A_{i}} −1_{A_{j}}) were constant on a line segment L contained in A_{i} ∩A_{j}, then Lemma 4.1(b) implies that T_{ρ}(1_{A_{i}} − 1_{A_{j}}) is constant on an infinite line containing L, by uniqueness of analytic continuation. But then Lemma 4.1(a) implies that c = 0, contradicting that c ≠ 0. Therefore, T_{ρ}(1_{A_{i}} −1_{A_{j}}) is not constant on any line segment contained in A_{i} ∩A_{j}. We then apply Lemma 3.1 to see that the partition {A_{p}}_{p=1}^{n+1} is not optimal. □

Corollary 5.2. (Biased Optimizers are not Flat) Let {A_{i}}_{i=1}^{n+1} be a partition of ℝ^{n} with volumes a = (a_{1}, …, a_{n+1}).

(1) Let ρ ∈ (0, 1). Suppose {A_{i}}_{i=1}^{n+1} is a partition of ℝ^{n} satisfying

S_{ρ}({A_{i}}_{i=1}^{n+1}) = sup_{{B_{i}}_{i=1}^{n+1} is a partition of ℝ^{n} with volumes (a_{1},...,a_{n+1})} S_{ρ}({B_{i}}_{i=1}^{n+1}).

If Assumption 1 also holds, then we must have a = (\frac{1}{n+1}, …, \frac{1}{n+1}).

(2) Let ρ ∈ (−1, 0). Suppose {A_{i}}_{i=1}^{n+1} is a partition of ℝ^{n} satisfying

S_{ρ}({A_{i}}_{i=1}^{n+1}) = inf_{{B_{i}}_{i=1}^{n+1} is a partition of ℝ^{n} with volumes (a_{1},...,a_{n+1})} S_{ρ}({B_{i}}_{i=1}^{n+1}).

If Assumption 1 also holds, then we must have a = (\frac{1}{n+1}, …, \frac{1}{n+1}).

Proof. Suppose that {A_{i}}_{i=1}^{n+1} is a flat, optimal partition; we will show that it must be unbiased. First, Corollary 5.1 implies that 0 ∈ A_{p} for all p ∈ {1, …, n + 1}. Then, by Lemma 3.1 and (16), we have T_{ρ}(1_{A_{i}} − 1_{A_{j}})(0) = 0 for all i, j ∈ {1, …, n + 1}. Since each A_{p} is a cone, its scale-invariance and the definition of T_{ρ} imply that γ_{n}(A_{p}) = (T_{ρ}1_{A_{p}})(0); hence, γ_{n}(A_{i}) = γ_{n}(A_{j}) for all i, j ∈ {1, …, n + 1} with i ≠ j. □

6. Voting Interpretation

As mentioned earlier our results imply that, generically speaking, plurality is not the most noise stable discrete function. Gaussian space may be obtained as a limit of discrete spaces in multiple ways, each resulting in a somewhat different statement of Plurality is not stablest, via Corollary 5.2. For concreteness we prove Corollary 2.2.

Proof of Cor. 2.2. The proof follows from the Central Limit Theorem. Let f_{n}: {1, 2, 3}^{n} → {1, 2, 3} be the sequence of plurality functions from Definition 2.6 and let (α, β) ≠ (0, 0). In order to prove Corollary 2.2 we first claim that there exists a shifted flat partition A = {A_{1}, A_{2}, A_{3}} of ℝ^{2} such that

lim_{n→∞} P[f_{n} = i] = γ_{2}(A_{i}), ∀ i ∈ {1, 2, 3},

and moreover

lim_{n→∞} P[f_{n}(x) = f_{n}(y)] = ∑_{i=1}^{3} P[X ∈ A_{i}, Y ∈ A_{i}].

This follows from the central limit theorem, noting that the vector (X_{i}^{n})_{i=1}^{3} ∈ ℝ^{3} given by

X_{i}^{n}(ω_{1}, …, ω_{n}) := n^{−1/2} ∑_{j=1}^{n}(1(ω_{j} = i) − 1/3), i = 1, 2, 3

converges to a centered normal vector (N_{i})_{i=1}^{3} ∈ ℝ^{3} with variances 2/9 and covariances −2/3 as n → ∞. Also, the partition {(X_{i}^{n})_{i=1}^{3} : f_{n} = 1}, {(X_{i}^{n})_{i=1}^{3} : f_{n} = 2}, {(X_{i}^{n})_{i=1}^{3} : f_{n} = 3} converges in the weak L_{1}(γ_{2}) norm to the sets given by

A_{i} = {x ∈ ℝ^{2} : i = argmax_{j=1,2,3}(N_{1}(x) + α, N_{2}(x) + β, N_{3}(x) − α − β)}.

In other words, {A_{1}, A_{2}, A_{3}} is a shifted standard simplex.

Let {B_{1}, B_{2}, B_{3}} be a partition of ℝ^{2} which satisfies γ_{2}(A_{i}) = γ_{2}(B_{i}) for all i = 1, 2, 3 and

∑_{i=1}^{3} P[X ∈ A_{i}, Y ∈ A_{i}] < ∑_{i=1}^{3} P[X ∈ B_{i}, Y ∈ B_{i}].

Note that {B_{1}, B_{2}, B_{3}} exists by Theorem 2.1. By approximating {B_{1}, B_{2}, B_{3}} by a finite number of axis-parallel rectangles, we may assume that {B_{1}, B_{2}, B_{3}} consists of a finite union of axis-parallel rectangles.

Consider now g̃_{n}: {1, 2, 3}^{n} → {1, 2, 3} satisfying g̃_{n} = i if (X_{1}^{n}, X_{2}^{n}, X_{3}^{n}) ∈ B_{i}. Since {B_{1}, B_{2}, B_{3}} consists of a finite number of axis-parallel rectangles, Definition 2.7 shows that max_{i=1,...,n} I_{i}g̃_{n} = O(n^{−1/2}). Moreover by the Central Limit Theorem, we see that

|P[g̃_{n} = i] − γ_{2}(B_{i})| = O(n^{−1/2}), |P[f̃_{n} = i] − γ_{2}(A_{i})| = O(n^{−1/2}).

and

lim_{n→∞} P[g̃_{n}(x) = g̃_{n}(y)] = ∑_{i=1}^{3} P[X ∈ B_{i}, Y ∈ B_{i}] > ∑_{i=1}^{3} P[X ∈ A_{i}, Y ∈ A_{i}]

as needed.

□

Acknowledgement. Thanks to Oded Regev for reading and commenting on the manuscript. Thanks to Ronen Eldan, Kostya Makarychev, and Assaf Naor for helpful comments. This work was mostly conducted during the semester on “Real Analysis in Computer Science” at the Simons Institute for Theoretical Computer Science. We are grateful to the institute for its hospitality and support.

References

[1] João Lucas Barbosa and Manfredo do Carmo, Stability of hypersurfaces with constant mean curvature, Mathematische Zeitschrift 185 (1984), no. 3, 339–353. MR 731682 (85k:58021c)

[2] Christer Borell, The Brunn-Minkowski inequality in Gauss space, Inventiones Mathematicae 30 (1975), no. 2, 207–216. MR 0399402 (53 #3246)

[3] Christer Borell, Geometric bounds on the Ornstein-Uhlenbeck velocity process, Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 70 (1985), no. 1, 1–13. MR 795785 (87k:60103)

[4] Christer Borell, The Ehrhard inequality, Comptes Rendus Mathématique. Académie des Sciences. Paris 337 (2003), no. 10, 663–666. MR 2030108 (2004k:60102)

[5] Isaac Chavel, Riemannian geometry, second ed., Cambridge Studies in Advanced Mathematics, vol. 98, Cambridge University Press, Cambridge, 2006, A modern introduction. MR 2229062 (2006m:53002)

[6] Rustum Choksi and Peter Sternberg, On the first and second variations of a nonlocal isoperimetric problem, Journal für die Reine und Angewandte Mathematik. [Crelle’s Journal] 611 (2007), 75–108. MR 2360604 (2008j:49062)

[7] Tobias H. Colding and William P. Minicozzi, II, Minimal surfaces and mean curvature flow, Surveys in geometric analysis and relativity, Adv. Lect. Math. (ALM), vol. 20, Int. Press, Somerville, MA, 2011, pp. 73–143. MR 2906923

[8] Tobias H. Colding and William P. Minicozzi, II, Generic mean curvature flow I: generic singularities, Annals of Mathematics. Second Series 175 (2012), no. 2, 755–833. MR 2993752

[9] Tobias Holck Colding, Tom Ilmanen, William P. Minicozzi, II, and Brian White, The round sphere minimizes entropy among closed self-shrinkers, Journal of Differential Geometry 95 (2013), no. 1, 53– 69. MR 3128979

[10] Tobias Holck Colding and William P. Minicozzi, II, A course in minimal surfaces, Graduate Studies in Mathematics, vol. 121, American Mathematical Society, Providence, RI, 2011. MR 2780140

[11] J. Corneli, I. Corwin, S. Hurder, V. Sesum, Y. Xu, E. Adams, D. Davis, M. Lee, R. Visocchi, and N. Hoffman, Double bubbles in Gauss space and spheres, Houston Journal of Mathematics 34 (2008), no. 1, 181–204. MR 2383703 (2009e:53007)

[12] Ronen Eldan, A two-sided estimate for the gaussian noise stability deficit, Preprint, arXiv:1307.2781, 2013.

[13] Steven Heilman, Euclidean partitions optimizing noise stability, Electronic Journal of Probability 19 (2014), no. 71, 37. MR 3256871

[14] Michael Hutchings, Frank Morgan, Manuel Ritoré, and Antonio Ros, Proof of the double bubble conjecture, Annals of Mathematics. Second Series 155 (2002), no. 2, 459–489. MR 1906593 (2003c:53013)

[15] Marcus Isaksson and Elchanan Mossel, Maximally stable Gaussian partitions with discrete applications, Israel Journal of Mathematics 189 (2012), 347–396. MR 2931402

[16] Gil Kalai, A Fourier-theoretic perspective on the Condorcet paradox and Arrow’s theorem, Advances in Applied Mathematics 29 (2002), no. 3, 412–426. MR 1942631 (2003h:91046)

[17] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?, SIAM Journal on Computing 37 (2007), no. 1, 319–357. MR 2306295 (2008d:68035)

[18] Subhash Khot and Assaf Naor, Approximate kernel clustering, Mathematika. A Journal of Pure and Applied Mathematics 55 (2009), no. 1-2, 129–165. MR 2573605 (2011c:68166)

[19] Guy Kindler and Ryan O’Donnell, Gaussian noise sensitivity and Fourier tails, 2012 IEEE 27th Conference on Computational Complexity—CCC 2012, IEEE Computer Soc., Los Alamitos, CA, 2012, pp. 137–147. MR 3026322

[20] Michel Ledoux, Isoperimetry and Gaussian analysis, Lectures on probability theory and statistics (Saint-Flour, 1994), Lecture Notes in Math., vol. 1648, Springer, Berlin, 1996, pp. 165–294. MR 1600888 (99h:60002)

[21] Paul Lévy, Problèmes concrets d’analyse fonctionnelle. Avec un complément sur les fonctionnelles analytiques par F. Pellegrino, Gauthier-Villars, Paris, 1951, 2d ed. MR 0041346 (12,834a)

[22] Frank Morgan, Geometric measure theory, fourth ed., Elsevier/Academic Press, Amsterdam, 2009, A beginner’s guide. MR 2455580 (2009i:49001)

[23] Elchanan Mossel and Joe Neeman, Robust optimality of gaussian noise stability, Preprint, arXiv:1210.4126, 2012.

[24] Elchanan Mossel, Ryan O’Donnell and Krzysztof Oleszkiewicz, Noise stability of functions with low influences: invariance and optimality, Annals of Mathematics. Second Series 171 (2010), no. 1, 295– 341. MR 2630040 (2012a:60091)

[25] Elias M. Stein and Rami Shakarchi, Complex analysis, Princeton Lectures in Analysis, II, Princeton University Press, Princeton, NJ, 2003. MR 1976398 (2004d:30002)

[26] Jakob Steiner, Einfache beweise der isoeperimetrische hauptsätze, J. Reine Angew. Math. 18 (1838), 281–296.

[27] V. N. Sudakov and B. S. Cirel′son, Extremal properties of half-spaces for spherically invariant measures, Zapiski Naučnyh Seminarov Leningradskogo Otdelenija Matematičeskogo Instituta im. V. A. Steklova Akademii Nauk SSSR (LOMI) 41 (1974), 14–24, 165, Problems in the theory of probability distributions, II. MR 0365680 (51 #1932)

[28] John M. Sullivan and Frank Morgan, Open problems in soap bubble geometry, International Journal of Mathematics 7 (1996), no. 6, 833–842. MR 1417788 (98a:53014)

[29] Karl Weierstrass, Mathematische Werke. VII. Vorlesungen über Variationsrechnung, Georg Olms Verlagsbuchhandlung, Hildesheim, 1967. MR 0218197 (36 #1285)

Department of Mathematics, University of California, Los Angeles, CA 90095-1555

E-mail address: heilman@math.ucla.edu

Departments of Statistics and Computer Science, U. Penn and U.C. Berkeley

E-mail address: mossel@wharton.upenn.edu

Mathematics and Electrical and Computer Engineering, University of Texas at Austin, Austin, TX 78712

E-mail address: joeneeman@gmail.com