THREE CANDIDATE PLURALITY IS STABLEST FOR SMALL CORRELATIONS

STEVEN HEILMAN AND ALEX TARTER

Abstract. Using the calculus of variations, we prove the following structure theorem for noise stable partitions: a partition of n-dimensional Euclidean space into m disjoint sets of fixed Gaussian volumes that maximize their noise stability must be (m − 1)-dimensional, if m − 1 ≤ n. In particular, the maximum noise stability of a partition of m sets in ℝ^{n} of fixed Gaussian volumes is constant for all n satisfying n ≥ m − 1. From this result, we obtain:

(i) A proof of the Plurality is Stablest Conjecture for 3 candidate elections, for all correlation parameters ρ satisfying 0 < ρ < ρ_{0}, where ρ_{0} > 0 is a fixed constant (that does not depend on the dimension n), when each candidate has an equal chance of winning.

(ii) A variational proof of Borell’s Inequality (corresponding to the case m = 2). The structure theorem answers a question of De-Mossel-Neeman and of Ghazi-Kamath-Raghavendra. Item (i) is the first proof of any case of the Plurality is Stablest Conjecture of Khot-Kindler-Mossel-O’Donnell (2005) for fixed ρ, with the case ρ → 1^{−} being solved recently. Item (i) is also the first evidence for the optimality of the Frieze-Jerrum semidefinite program for solving MAX-3-CUT, assuming the Unique Games Conjecture. Without the assumption that each candidate has an equal chance of winning in (i), the Plurality is Stablest Conjecture is known to be false.

Contents

1. Introduction  1
2. Existence and Regularity  9
3. First and Second Variation  13
4. Noise Stability and the Calculus of Variations  14
5. Almost Eigenfunctions of the Second Variation  20
6. Proof of the Main Structure Theorem  23
7. The Case of Negative Correlation  24
References  28

1. Introduction

1.1. An Informal Introduction. A voting method or social choice function with m candidates and n voters is a function

f: {1, …, m}^{n} → {1, …, m}.

From the social choice theory perspective, the input of the function f is a list of votes of n people who are choosing between m candidates. Each of the m candidates is labelled by

Date: August 16, 2021. S. H. is Supported by NSF Grant CCF 1911216.

the integers 1, …, m. If the votes are x ∈ {1, …, m}^{n}, then x_{i} denotes the vote of person i ∈ {1, …, n} for candidate x_{i} ∈ {1, …, m}. Given the votes x ∈ {1, …, m}^{n}, f(x) is interpreted as the winner of the election.

It is both natural and desirable to find a voting method whose output is most likely to be unchanged after votes are randomly altered. One could imagine that malicious third parties or miscounting of votes might cause random vote changes, so we desire a voting method f whose output is stable to such changes. In addition to voting motivations, finding a voting method that is stable to noise has applications to the Unique Games Conjecture [KKMO07, MOO10, KM16], to semidefinite programming algorithms such as MAX-CUT [KKMO07, IM12], to learning theory [FGRW12], etc. For some surveys on this and related topics, see [O’D, Kho, Hei20].

The output of a constant function f is never altered by changes to the votes. Also, if the function f only depends on one of its n inputs, then the output of f is rarely changed by independent random changes to each of the votes. In these cases, the function f is rather “undemocratic” from the perspective of social choice theory. In the case of a constant function, the outcome of the election does not depend at all on the votes. In the case of a function that only depends on one of its inputs, the outcome of the election only depends on one voter (so f is called a dictatorship function).

Among “democratic” voting methods, it was conjectured in [KKMO07] and proven in [MOO10] that the majority voting method is the voting method that best preserves the outcome of the election. Below is an informal statement of the main result of [MOO10].

Theorem 1.1 (Majority is Stablest, Informal Version, [MOO10, Theorem 4.4]). Suppose we run an election with a large number n of voters and m = 2 candidates. We make the following assumptions about voter behavior and about the election method.

• Voters cast their votes randomly, independently, with equal probability of voting for either candidate.

• Each voter has a small influence on the outcome of the election. (That is, all influences from Definition 5 are small for the voting method.)

• Each candidate has an equal chance of winning the election. Under these assumptions, the majority function is the voting method that best preserves the outcome of the election, when votes have been corrupted independently each with probability less than 1/2.

We say a vote x_{i} ∈ {1, 2} is corrupted with probability 0 < δ < 1 when, with probability δ, the vote x_{i} is changed to a uniformly random element of {1, 2}, and with probability 1−δ, the vote x_{i} is unchanged.

For a formal statement of Theorem 1.1, see Theorem 1.8 below.

The primary interest of the authors of [KKMO07] in Theorem 1.1 was proving optimal hardness of approximation for the MAX-CUT problem. In the MAX-CUT problem, we are given a finite undirected graph on n vertices, and the objective of the problem is to find a partition of the vertices of the graph into two sets that maximizes the number of edges going between the two sets. The MAX-CUT problem is MAX-SNP hard, i.e. if P ≠ NP, there is no polynomial time (in n) approximation scheme for this problem. Nevertheless, there is a randomized polynomial time algorithm [GW95] that achieves, in expectation, at least .87856 … times the maximum value of the MAX-CUT problem. This algorithm uses semidefinite programming. Also, the exact expression for the .87856 … constant is

min_{−1≤ρ≤1} \frac{2}{π} \frac{arccos(ρ)}{1 − ρ} = .87856 …

The authors of [KKMO07] showed that, if the Unique Games Conjecture is true, then Theorem 1.1 implies that the Goemans-Williamson algorithm’s .87856… constant of approximation cannot be increased. Assuming the validity of the Unique Games Conjecture is a fairly standard in complexity theory, though the conjecture remains open. See [O’D, Kho] and the references therein for more discussion on this conjecture, and see [KMS18] for some recent significant progress.

Theorem 1.1 (i.e. Theorem 1.8) gives a rather definitive statement on the two candidate voting method that is most stable to corruption of votes. Moreover, the applcation of Theorem 1.1 gives a complete understanding of the optimal algorithm for solving MAX-CUT, assuming the Unique Games Conjecture. Unfortunately, the proof of Theorem 1.1 says nothing about elections with m > 2 candidates. Moreover, Theorem 1.1 fails to prove optimality of the Frieze-Jerrum [FJ95] semidefinite programming algorithm for the MAXm-CUT problem. In the MAX-m-CUT problem, we are given a finite undirected graph on n vertices, and the objective of the problem is to find a partition of the vertices of the graph into m sets that maximizes the number of edges going between the two sets. So, MAX-CUT is the same as MAX-2-CUT.

In order to prove the optimality of the Frieze-Jerrum [FJ95] semidefinite programming algorithm for the MAX-m-CUT problem, one would need an analogue of Theorem 1.1 for m > 2 voters, where the plurality function replaces the majority function. For this reason, it was conjectured [KKMO07, IM12] that the plurality function is the voting method that is most stable to independent, random vote corruption.

Conjecture 1.2 (Plurality is Stablest, Informal Version, [KKMO07], [IM12, Conjecture 1.9]). Suppose we run an election with a large number n of voters and m ≥ 3 candidates. We make the following assumptions about voter behavior and about the election method.

• Voters cast their votes randomly, independently, with equal probability of voting for each candidate.

• Each voter has a small influence on the outcome of the election. (That is, all influences from Definition 5 are small for the voting method.)

• Each candidate has an equal chance of winning the election. Under these assumptions, the plurality function is the voting method that best preserves the outcome of the election, when votes have been corrupted independently each with probability less than 1/2.

We say a vote x_{i} ∈ {1, …, m} is corrupted with probability 0 < δ < 1 when, with probability δ, the vote x_{i} is changed to a uniformly random element of {1, …, m}, and with probability 1 − δ, the vote x_{i} is unchanged.

In the case that the probability of vote corruption goes to zero, the first author proved the first known case of Conjecture 1.2 in [Hei19], culminating a series of previous works [CM12, MR15, BBJ17, Hei17, MN18a, MN18b, Hei18]. Conjecture 1.2 for all fixed parameters 0 < ρ < 1 was entirely open until now. Unlike the case of the Majority is Stablest (Theorem 1.8), Conjecture 1.2 cannot hold when the candidates have unequal chances of winning the election [HMN16]. This realization is an obstruction to proving Conjecture 1.2. It suggested that existing proof methods for Theorem 1.8 cannot apply to Conjecture 1.2.

Nevertheless, we are able to overcome this obstruction in the present work.

Theorem 1.3 (Main Result, Informal Version). There exists ε > 0 such that Conjecture 1.2 holds for m = 3 candidates, for all n ≥ 1, when the probability of a single vote being corrupted is any number in the range (1/2 − ε, 1/2).

Theorem 1.3 is the first proven case of the Plurality is Stablest Conjecture.1.2.

1.2. More Formal Introduction. Using a generalization of the Central Limit Theorem known as the invariance principle [MOO10, IM12], there is an equivalence between the discrete problem of Conjecture 1.2 and a continuous problem which is known as the Standard Simplex Conjecture [IM12]. For more details on this equivalence, see Section 7 of [IM12]We begin by providing some background for the latter conjecture, stated in Conjecture 1.6 below.

For any k ≥ 1, we define the Gaussian density as

\begin{aligned}γ_{k}(x) & := (2π)^{−k/2}e^{−∥x∥^{2}/2},  ⟨x, y⟩ := ∑_{i=1}^{n+1} x_{i}y_{i},  ∥x∥^{2} := ⟨x, x⟩, \\ & ∀ x = (x_{1}, …, x_{n+1}), y = (y_{1}, …, y_{n+1}) ∈ ℝ^{n+1}. \end{aligned}  (1)

Let z_{1}, …, z_{m} ∈ ℝ^{n+1} be the vertices of a regular simplex in ℝ^{n+1} centered at the origin. For any 1 ≤ i ≤ m, define

Ω_{i} := {x ∈ ℝ^{n+1} : ⟨x, z_{i}⟩ = max_{1≤j≤m}⟨x, z_{j}⟩}.  (2)

We refer to any sets satisfying (2) as cones over a regular simplex.

Let f: ℝ^{n+1} → [0, 1] be measurable and let ρ ∈ (−1, 1). Define the Ornstein-Uhlenbeck operator with correlation ρ applied to f by

\begin{aligned}T_{ρ}f(x) & := ∫_{ℝ^{n+1}} f(xρ + y\sqrt{1 − ρ^{2}})γ_{n+1}(y) dy \\ & = (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2} ∫_{ℝ^{n+1}} f(y)e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy,  ∀x ∈ ℝ^{n+1}. \end{aligned}  (3)

T_{ρ} is a parametrization of the Ornstein-Uhlenbeck operator, which gives a fundamental solution of the (Gaussian) heat equation

\frac{d}{dρ}T_{ρ}f(x) = \frac{1}{ρ}( − \overline{Δ}T_{ρ}f(x) + ⟨x, \overline{∇}T_{ρ}f(x)⟩),  ∀ x ∈ ℝ^{n+1}.  (4)

Here \overline{Δ} := ∑_{i=1}^{n+1} ∂^{2}/∂x_{i}^{2} and \overline{∇} is the usual gradient on ℝ^{n+1}. T_{ρ} is not a semigroup, but it satisfies T_{ρ_{1}}T_{ρ_{2}} = T_{ρ_{1}ρ_{2}} for all ρ_{1}, ρ_{2} ∈ (0, 1). We have chosen this definition since the usual Ornstein-Uhlenbeck operator is only defined for ρ ∈ [0, 1].

Definition 1.4 (Noise Stability). Let Ω ⊆ ℝ^{n+1} be measurable. Let ρ ∈ (−1, 1). We define the noise stability of the set Ω with correlation ρ to be

∫_{ℝ^{n+1}} 1_{Ω}(x)T_{ρ}1_{Ω}(x)γ_{n+1}(x) dx =^{(3)} (2π)^{−(n+1)}(1 − ρ^{2})^{−(n+1)/2} ∫_{Ω} ∫_{Ω} e^{\frac{−∥x∥^{2}−∥y∥^{2}+2ρ⟨x,y⟩}{2(1−ρ^{2})}} dxdy.

Equivalently, if X = (X_{1}, …, X_{n+1}), Y = (Y_{1}, …, Y_{n+1}) ∈ ℝ^{n+1} are (n + 1)-dimensional jointly Gaussian distributed random vectors with 𝔼X_{i}Y_{j} = ρ·1_{(i=j)} for all i, j ∈ {1, …, n+1}, then

∫_{ℝ^{n+1}} 1_{Ω}(x)T_{ρ}1_{Ω}(x)γ_{n+1}(x) dx = ℙ((X, Y) ∈ Ω × Ω).

Maximizing the noise stability of a Euclidean partition is the continuous analogue of finding a voting method that is most stable to random corruption of votes, among voting methods where each voter has a small influence on the election’s outcome.

Problem 1.5 (Standard Simplex Problem, [IM12]). Let m ≥ 3. Fix a_{1}, …, a_{m} > 0 such that ∑_{i=1}^{m} a_{i} = 1. Fix ρ ∈ (0, 1). Find measurable sets Ω_{1}, … Ω_{m} ⊆ ℝ^{n+1} with ∪_{i=1}^{m}Ω_{i} = ℝ^{n+1} and γ_{n+1}(Ω_{i}) = a_{i} for all 1 ≤ i ≤ m that maximize

∑_{i=1}^{m} ∫_{ℝ^{n+1}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω_{i}}(x)γ_{n+1}(x) dx,

subject to the above constraints. (Here γ_{n+1}(Ω_{i}) := ∫_{Ω_{i}} γ_{n+1}(x) dx ∀ 1 ≤ i ≤ m.)

We can now state the continuous version of Conjecture 1.2.

Conjecture 1.6 (Standard Simplex Conjecture [IM12]). Let Ω_{1}, … Ω_{m} ⊆ ℝ^{n+1} maximize Problem 1.5. Assume that m − 1 ≤ n + 1. Fix ρ ∈ (0, 1). Let z_{1}, …, z_{m} ∈ ℝ^{n+1} be the vertices of a regular simplex in ℝ^{n+1} centered at the origin. Then ∃ w ∈ ℝ^{n+1} such that, for all 1 ≤ i ≤ m,

Ω_{i} = w + {x ∈ ℝ^{n+1} : ⟨x, z_{i}⟩ = max_{1≤j≤m}⟨x, z_{j}⟩}.

It is known that Conjecture 1.6 is false when (a_{1}, …, a_{m}) ≠ (1/m, …, 1/m) [HMN16]. In the remaining case that a_{i} = 1/m for all 1 ≤ i ≤ m, it is assumed that w = 0 in Conjecture 1.6.

For expositional simplicity, we separately address the case ρ < 0 of Conjecture 1.6 in Section 7 below.

1.3. Plurality is Stablest Conjecture. As previously mentioned, the Standard Simplex Conjecture [IM12] stated in Conjecture 1.6 is essentially equivalent to the Plurality is Stablest Conjecture from Conjecture 1.2. After making several definitions, we state a formal version of Conjecture 1.2 as Conjecture 1.7 below.

If g: {1, …, m}^{n} → ℝ and 1 ≤ i ≤ n, we denote

𝔼(g) := m^{−n} ∑_{ω∈{1,...,m}^{n}} g(ω)

𝔼_{i}(g)(ω_{1}, …, ω_{i−1}, ω_{i+1}, …, ω_{n}) := m^{−1} ∑_{ω_{i}∈{1,...,m}} g(ω_{1}, …, ω_{n})

∀ (ω_{1}, …, ω_{i−1}, ω_{i+1}, …, ω_{n}) ∈ {1, …, m}^{n}.

Define also the i^{th} influence of g, i.e. the influence of the i^{th} voter of g, as

Inf_{i}(g) := 𝔼[(g − 𝔼_{i}g)^{2}].  (5)

Let

Δ_{m} := {(y_{1}, …, y_{m}) ∈ ℝ^{m}: y_{1} + ⋯ + y_{m} = 1, ∀ 1 ≤ i ≤ m, y_{i} ≥ 0}.  (6)

If f: {1, …, m}^{n} → Δ_{m}, we denote the coordinates of f as f = (f_{1}, …, f_{m}). For any ω ∈ ℤ^{n}, we denote ∥ω∥_{0} as the number of nonzero coordinates of ω. The noise stability of g: {1, …, m}^{n} → ℝ with parameter ρ ∈ (−1, 1) is

S_{ρ}g := m^{−n} ∑_{ω∈{1,...,m}^{n}} g(ω)𝔼_{ρ}g(δ)

= m^{−n} ∑_{ω∈\{1,...,m\}^{n}} g(ω) ∑_{σ∈\{1,...,m\}^{n}} (\frac{1 − (m − 1)ρ}{m})^{n−∥σ−ω∥_{0}} (\frac{1 − ρ}{m})^{∥σ−ω∥^{0}} g(σ).

Equivalently, conditional on ω, 𝔼_{ρ}g(δ) is defined so that for all 1 ≤ i ≤ n, δ_{i} = ω_{i} with probability \frac{1−(m−1)ρ}{m}, and δ_{i} is equal to any of the other (m − 1) elements of \{1, …, m\} each with probability \frac{1−ρ}{m}, and so that δ_{1}, …, δ_{n} are independent.

The noise stability of f: {1, …, m}^{n} → Δ_{m} with parameter ρ ∈ (−1, 1) is

S_{ρ}f := ∑_{i=1}^{m} S_{ρ}f_{i}.

Let m ≥ 2, k ≥ 3. For each j ∈ {1, …, m}, let e_{j} = (0, …, 0, 1, 0, …, 0) ∈ ℝ^{m} be the j^{th} unit coordinate vector. Define the plurality function PLUR_{m,n}: {1, …, m}^{n} → Δ_{m} for m candidates and n voters such that for all ω ∈ {1, …, m}^{n}.

PLUR_{m,n}(ω) := \begin{cases}e_{j} & , if |\{i ∈ \{1, …, m\}: ω_{i} = j\}| > |\{i ∈ \{1, …, m\}: ω_{i} = r\}| , \\ & ∀ r ∈ \{1, …, m\} \ \{j\} \\ \frac{1}{m} ∑_{i=1}^{m} e_{i} & , otherwise. \end{cases}

We can now state the more formal version of Conjecture 1.2.

Conjecture 1.7 (Plurality is Stablest, Discrete Version). For any m ≥ 2, ρ ∈ [0, 1], ε > 0, there exists τ > 0 such that if f: {1, …, m}^{n} → Δ_{m} satisfies Inf_{i}(f_{j}) ≤ τ for all 1 ≤ i ≤ n and for all 1 ≤ j ≤ m, and if 𝔼f = \frac{1}{m} ∑_{i=1}^{m} e_{i}, then

S_{ρ}f ≤ lim_{n→∞} S_{ρ}PLUR_{m,n} + ε.

The main result of the present paper (stated in Theorem 1.10 below) is: ∃ ρ_{0} > 0 such that Conjecture 1.7 is true for m = 3 for all 0 < ρ < ρ_{0}, for all n ≥ 1. The only previously known case of Conjecture 1.7 was the following.

Theorem 1.8 (Majority is Stablest, Formal, Biased Case, [MOO10, Theorem 4.4]). Conjecture 1.7 is true when m = 2.

For an even more general version of Theorem 1.8, see [MOO10, Theorem 4.4]. In particular, the assumption on 𝔼f can be removed, though we know this cannot be done for m ≥ 3 [HMN16].

1.4. Our Contribution. The main structure Theorem below implies that sets optimizing noise stability in Problem 1.5 are inherently low-dimensional. Though this statement might seem intuitively true, since many inequalities involving the Gaussian measure have lowdimensional optimizers, this statement has not been proven before. For example, Theorem 1.9 was listed as an open question in [DMN17, DMN18] and [GKR18]. Indeed, the lack of Theorem 1.9 has been one main obstruction to a solution of Conjectures 1.5 and 1.7.

Theorem 1.9 (Main Structure Theorem/ Dimension Reduction). Fix ρ ∈ (0, 1). Let m ≥ 2 with m ≤ n + 2. Let Ω_{1}, … Ω_{m} ⊆ ℝ^{n+1} maximize Problem 1.5. Then, after rotating the sets Ω_{1}, … Ω_{m} and applying Lebesgue measure zero changes to these sets, there exist measurable sets Ω′_{1}, … Ω′_{m} ⊆ ℝ^{m−1} such that,

Ω_{i} = Ω′_{i} × ℝ^{n−m+2}, ∀ 1 ≤ i ≤ m.

In the case m = 2, Theorem 1.9 is (almost) a variational proof of Borell’s inequality, since it reduces Problem 1.5 to a one-dimensional problem.

In the case m = 3, Theorem 1.9 says that Conjecture 1.6 for arbitrary n + 1 reduces to the case n + 1 = 2, which was solved for small ρ > 0 in [Hei14]. That is, Theorem 1.9 and the main result of [Hei14] imply:

Theorem 1.10 (Main; Plurality is Stablest for Three Candidates and Small Correlation). There exists ρ_{0} > 0 such that Conjecture 1.7 is true for m = 3 and for all 0 < ρ < ρ_{0}.

In [Hei14] it is noted that ρ_{0} = e^{−20·3^{10^{14}}} suffices in Theorem 1.10.

We can also prove a version of Theorem 1.9 when ρ < 0. See Theorem 7.9 and the discussion in Section 7. One difficulty in proving Theorem 1.9 directly for ρ < 0 is that it is not a priori obvious that a minimizer of Problem 1.5 exists in that case.

1.5. Noninteractive Simulation of Correlated Distributions. As mentioned above, Theorem 1.9 answers a question in [DMN17, DMN18] and [GKR18]. Their interest in Theorem 1.9 stems from the following problem. Let (X, Y) ∈ ℝ^{n} be a random vector. Let (X_{1}, Y_{1}), (X_{2}, Y_{2}), … be i.i.d. copies of (X, Y). Suppose there are two players A and B. Player A has access to X_{1}, X_{2}, … and player B has access to Y_{1}, Y_{2}, . . .. Without communication, what joint distributions can players A and B jointly simulate? For details on the relation of this problem to Theorem 1.9, see [DMN17, DMN18] and [GKR18].

1.6. Outline of the Proof of the Structure Theorem. In this section we outline the proof of Theorem 1.9 in the case m = 2. The proof loosely follows that of a corresponding statement [MR15, BBJ17] for the Gaussian surface area (which was then adapted to multiple sets in [MN18a, MN18b, Hei18]), with a few key differences. For didactic purposes, we will postpone a discussion of technical difficulties (such as existence and regularity of a maximizer) to Section 2.1.

Fix 0 < a < 1. Suppose there exists Ω, Ω^{c} ⊆ ℝ^{n+1} are measurable sets maximizing

∫_{ℝ^{n+1}} 1_{Ω}(x)T_{ρ}1_{Ω}(x)γ_{n+1}(x)dx,

subject to the constraint γ_{n+1}(Ω) = a. A first variation argument (Lemma 3.1 below) implies that Σ := ∂Ω is a level set of the Ornstein-Uhlenbeck operator applied to 1_{Ω}. That is, there exists c ∈ ℝ such that

Σ = {x ∈ ℝ^{n+1} : T_{ρ}1_{Ω}(x) = c}.  (7)

Since Σ is a level set, a vector perpendicular to the level set is also perpendicular to Σ. Denoting N(x) ∈ ℝ^{n+1} as the unit length exterior pointing normal vector to x ∈ ∂Ω, (7) implies that

\overline{∇}T_{ρ}1_{Ω}(x) = −N(x) ∥\overline{∇}T_{ρ}1_{Ω}(x)∥ .  (8)

(It is not obvious that there must be a negative sign here, but it follows from examining the second variation.) We now observe how the noise stability of Ω changes as the set is translated infinitesimally. Fix v ∈ ℝ^{n+1}, and consider the variation of Ω induced by the constant vector field v. That is, let Ψ: ℝ^{n+1} × (−1, 1) → ℝ^{n+1} such that Ψ(x, 0) = x and such that \frac{d}{ds}|_{s=0}Ψ(x, s) = v for all x ∈ ℝ^{n+1}, s ∈ (−1, 1). For any s ∈ (−1, 1), let Ω^{(s)} = Ψ(Ω, s). Note that Ω^{(0)} = Ω. Denote f(x) := ⟨v, N(x)⟩ for all x ∈ Σ. Then define

S(f)(x) := (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2} ∫_{Σ} f(y)e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy, ∀ x ∈ Σ.

A second variation argument (Lemma 4.5 below) implies that, if f is Gaussian volumepreserving, i.e. ∫_{Σ} f(x)γ_{n+1}(x) dx = 0, then

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∫_{ℝ^{n+1}} 1_{Ω^{(s)}}(x)T_{ρ}1_{Ω^{(s)}}(x)γ_{n+1}(x) dx

= ∫_{Σ} (S(f)(x) − ∥\overline{∇}T_{ρ}1_{Ω}(x)∥ f(x))f(x)γ_{n+1}(x) dx.

(9)

Somewhat unexpectedly, the function f(x) = ⟨v, N(x)⟩ is almost an eigenfunction of the operator S (by Lemma 5.1), in the sense that

S(f)(x) = \frac{1}{ρ}f(x) ∥\overline{∇}T_{ρ}1_{Ω}(x)∥ ,  ∀ x ∈ Σ.  (10)

Equation (10) is the key fact use in the proof of the main theorem, Theorem 1.9. Equation (10) follows from (8) and the divergence theorem (see Lemma 5.1 for a proof of (10).) Plugging (10) into (9),

∫_{Σ}⟨v, N(x)⟩γ_{n+1}(x) dx = 0 ⟹ \frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∫_{ℝ^{n+1}} 1_{Ω^{(s)}}(x)T_{ρ}1_{Ω^{(s)}}(x)γ_{n+1}(x) dx

= (\frac{1}{ρ} − 1) ∫_{Σ}⟨v, N(x)⟩^{2} ∥\overline{∇}T_{ρ}1_{Ω}(x)∥ γ_{n+1}(x) dx.

(11)

The set

V := {v ∈ ℝ^{n+1} : ∫_{Σ}⟨v, N(x)⟩γ_{n+1}(x) dx = 0}

has dimension at least n, by the rank-nullity theorem. Since Ω maximizes noise stability, the quantity on the right of (11) must be non-positive for all v ∈ V, implying that f = 0 on Σ (except possibly on a set of measure zero on Σ). (One can show that ∥\overline{∇}T_{ρ}1_{Ω}(x)∥ > 0 for all x ∈ Σ. See Lemma 4.8.) That is, for all v ∈ V, ⟨v, N(x)⟩ = 0 for all x ∈ Σ (except possibly on a set of measure zero on Σ). Since V has dimension at least n, there exists a measurable discrete set Ω′ ⊆ ℝ such that Ω = Ω′ × ℝ^{n} after rotating Ω, concluding the proof of Theorem 1.9 in the case m = 2.

Theorem 1.9 follows from the realization that all of the above steps still hold for arbitrary m in Conjecture 1.5. In particular, the key lemma (10) still holds. See Lemmas 5.1 and 5.4 below.

Remark 1.11. In the case that we replace the Gaussian noise stability of Ω with the Euclidean heat content

∫_{ℝ^{n+1}} 1_{Ω}(x)P_{t}1_{Ω}(x) dx, ∀ t > 0

P_{t}f(x) := ∫_{ℝ^{n+1}} f(x + y\sqrt{t})γ_{n+1}(y) dy,  ∀x ∈ ℝ^{n+1},  ∀ f: ℝ^{n+1} → [0, 1],

then the corresponding operator \overline{S} from the second variation of the Euclidean heat content satisfies

\overline{S}(f)(x) := t^{(n+1)/2}(2π)^{−(n+1)/2} ∫_{Σ} f(y)e^{− \frac{∥y−x∥^{2}}{2t}} dy, ∀ x ∈ Σ,

and then the analogue of (9) for f(x) := ⟨v, N(x)⟩ is

\overline{S}(f)(x) = f(x) ∥\overline{∇}P_{t}1_{Ω}(x)∥ , ∀ x ∈ Σ,

so that the second variation corresponding to f = ⟨v, N⟩ is automatically zero. This fact is expected, since a translation does not change the Euclidean heat content. However, this example demonstrates that the key property of the above proof is exactly (10). More specifically, f is an “almost eigenfunction” of S with “eigenvalue” 1/ρ that is larger than 1. It seems plausible that other semigroups could also satisfy an identity such as (10), since (10) seems related to hypercontractivity. We leave this open for further research.

2. Existence and Regularity

2.1. Preliminaries and Notation. We say that Σ ⊆ ℝ^{n+1} is an n-dimensional C^{∞} manifold with boundary if Σ can be locally written as the graph of a C^{∞} function on a relatively open subset of {(x_{1}, …, x_{n}) ∈ ℝ^{n}: x_{n} ≥ 0}. For any (n + 1)-dimensional C^{∞} manifold Ω ⊆ ℝ^{n+1} such that ∂Ω itself has a boundary, we denote

\begin{aligned}C_{0}^{∞}(Ω; ℝ^{n+1}) & := \{f: Ω → ℝ^{n+1} : f ∈ C^{∞}(Ω; ℝ^{n+1}), f(∂∂Ω) = 0, \\ & ∃ r > 0, f(Ω ∩ (B(0, r))^{c}) = 0\}. \end{aligned}  (12)

We also denote C_{0}^{∞}(Ω) := C_{0}^{∞}(Ω; ℝ). We let div denote the divergence of a vector field in ℝ^{n+1}. For any r > 0 and for any x ∈ ℝ^{n+1}, we let B(x, r) := {y ∈ ℝ^{n+1} : ∥x − y∥ ≤ r} be the closed Euclidean ball of radius r centered at x ∈ ℝ^{n+1}. Here ∂∂Ω refers to the (n − 1)-dimensional boundary of Ω.

Definition 2.1 (Reduced Boundary). A measurable set Ω ⊆ ℝ^{n+1} has locally finite surface area if, for any r > 0,

sup {∫_{Ω} div(X(x)) dx: X ∈ C_{0}^{∞}(B(0, r), ℝ^{n+1}), sup_{x∈ℝ^{n+1}} ∥X(x)∥ ≤ 1} < ∞.

Equivalently, Ω has locally finite surface area if ∇1_{Ω} is a vector-valued Radon measure such that, for any x ∈ ℝ^{n+1}, the total variation

∥∇1_{Ω}∥ (B(x, 1)) := sup_{partitions C_{1},...,C_{m} of B(x,1) m≥1} ∑_{i=1}^{m} ∥∇1_{Ω}(C_{i})∥

is finite [CL12]. If Ω ⊆ ℝ^{n+1} has locally finite surface area, we define the reduced boundary ∂^{∗}Ω of Ω to be the set of points x ∈ ℝ^{n+1} such that

N(x) := − lim_{r→0^{+}} \frac{∇1_{Ω}(B(x, r))}{∥∇1_{Ω}∥ (B(x, r))}

exists, and it is exactly one element of S^{n} := {x ∈ ℝ^{n+1} : ∥x∥ = 1}.

The reduced boundary ∂^{∗}Ω is a subset of the topological boundary ∂Ω. Also, ∂^{∗}Ω and ∂Ω coincide with the support of ∇1_{Ω}, except for a set of n-dimensional Hausdorff measure zero.

Let Ω ⊆ ℝ^{n+1} be an (n+1)-dimensional C^{2} submanifold with reduced boundary Σ := ∂^{∗}Ω. Let N: Σ → S^{n} be the unit exterior normal to Σ. Let X ∈ C_{0}^{∞}(ℝ^{n+1}, ℝ^{n+1}). We write X in its components as X = (X_{1}, …, X_{n+1}), so that divX = ∑_{i=1}^{n+1} \frac{∂}{∂x_{i}} X_{i}. Let Ψ: ℝ^{n+1} × (−1, 1) → ℝ^{n+1} such that

Ψ(x, 0) = x,  \frac{d}{ds}Ψ(x, s) = X(Ψ(x, s)), ∀ x ∈ ℝ^{n+1}, s ∈ (−1, 1).  (13)

For any s ∈ (−1, 1), let Ω^{(s)} := Ψ(Ω, s). Note that Ω^{(0)} = Ω. Let Σ^{(s)} := ∂^{∗}Ω^{(s)}, ∀ s ∈ (−1, 1).

Definition 2.2. We call {Ω^{(s)}}_{s∈(−1,1)} as defined above a variation of Ω ⊆ ℝ^{n+1}. We also call {Σ^{(s)}}_{s∈(−1,1)} a variation of Σ = ∂^{∗}Ω.

For any x ∈ ℝ^{n+1} and any s ∈ (−1, 1), define

V (x, s) := ∫_{Ω^{(s)}} G(x, y) dy.  (14)

Below, when appropriate, we let dx denote Lebesgue measure, restricted to a surface Σ ⊆ ℝ^{n+1}.

Lemma 2.3 (Existence of a Maximizer). Let 0 < ρ < 1 and let m ≥ 2. Then there exist measurable sets Ω_{1}, …, Ω_{m} maximizing Problem 1.5.

Proof. Define Δ_{m} as in (6). Let f: ℝ^{n+1} → Δ_{m}. We write f in its components as f = (f_{1}, …, f_{m}). The set D_{0} := {f: ℝ^{n+1} → Δ_{m}} is norm closed, bounded and convex, therefore it is weakly compact and convex. Consider the function

C(f) := ∑_{i=1}^{m} ∫_{ℝ^{n+1}} f_{i}(x)T_{ρ}f_{i}(x)γ_{n+1}(x) dx.

This function is weakly continuous on D_{0}, and D_{0} is weakly compact, so there exists f̃ ∈ D_{0} such that C(f̃) = max_{f∈D_{0}} C(f). Moreover, C is convex since for any 0 < t < 1 and for any f, g ∈ D_{0},

tC(f) + (1 − t)C(g) − C(tf + (1 − t)g)

= ∑_{i=1}^{m} ∫_{ℝ^{n+1}} (tf_{i}(x)T_{ρ}f_{i}(x) + (1 − t)g_{i}(x)T_{ρ}g_{i}(x)

− (tf_{i}(x) + (1 − t)g_{i}(x))T_{ρ}[tf_{i}(x) + (1 − t)g_{i}(x)])γ_{n+1}(x) dx

= t(1 − t) ∑_{i=1}^{m} ∫_{ℝ^{n+1}} ((f_{i}(x) − g_{i}(x))T_{ρ}[f_{i}(x) − g_{i}(x)])γ_{n+1}(x) dx ≥ 0.

Here we used that

∫_{ℝ^{n+1}} h(x)T_{ρ}h(x)γ_{n+1}(x) dx = ∫_{ℝ^{n+1}}(T\sqrt{ρ}h(x))^{2}γ_{n+1}(x) dx ≥ 0,  (15)

for all measurable h: ℝ^{n+1} → [−1, 1].

Since C is convex, its maximum must be achieved at an extreme point of D_{0}. Let e_{1}, …, e_{m} denote the standard basis of ℝ^{m}, so that f takes its values in {e_{1}, …, e_{m}}. Then, for any 1 ≤ i ≤ m, define Ω_{i} := {x ∈ ℝ^{n+1} : f(x) = e_{i}}, so that f_{i} = 1_{Ω_{i}} ∀ 1 ≤ i ≤ m. □

Lemma 2.4 (Regularity of a Maximizer). Let Ω_{1}, …, Ω_{m} ⊆ ℝ^{n+1} be the measurable sets maximizing Problem 1.5, guaranteed to exist by Lemma 2.3. Then the sets Ω_{1}, …, Ω_{m} have locally finite surface area. Moreover, for all 1 ≤ i ≤ m and for all x ∈ ∂Ω_{i}, there exists a neighborhood U of x such that U ∩ ∂Ω_{i} is a finite union of C^{∞} n-dimensional manifolds.

Proof. This follows from a first variation argument and the strong unique continuation property for the heat equation. We first claim that there exist constants (c_{ij})_{1≤i<j≤m} such that

Ω_{i} ⊇ {x ∈ ℝ^{n+1} : T_{ρ}1_{Ω_{i}}(x) > T_{ρ}1_{Ω_{j}}(x) + c_{ij}, ∀ j ∈ {1, …, m} \ {i}},  ∀ 1 ≤ i ≤ m. (16)

By the Lebesgue density theorem [Ste70, 1.2.1, Proposition 1], we may assume that, for all i ∈ {1, …, k}, if y ∈ Ω_{i}, then we have lim_{r→0} γ_{n+1}(Ω_{i} ∩ B(y, r))/γ_{n+1}(B(y, r)) = 1.

We prove (16) by contradiction. Suppose there exist c ∈ ℝ, j, k ∈ {1, …, m} with j ≠ k and there exists y ∈ Ω_{j} and z ∈ Ω_{k} such that

T_{ρ}(1_{Ω_{j}} − 1_{Ω_{k}})(y) < c, T_{ρ}(1_{Ω_{j}} − 1_{Ω_{k}})(z) > c.

By (3), T_{ρ}(1_{Ω_{j}} − 1_{Ω_{k}})(x) is a continuous function of x. And by the Lebsgue density theorem, there exist disjoint measurable sets U_{j}, U_{k} with positive Lebesgue measure such that U_{j} ⊆ Ω_{j}, U_{k} ⊆ Ω_{k} such that γ_{n+1}(U_{j}) = γ_{n+1}(U_{k}) and such that

T_{ρ}(1_{Ω_{j}} − 1_{Ω_{k}})(y′) < c, ∀ y′ ∈ U_{j},  T_{ρ}(1_{Ω_{j}} − 1_{Ω_{k}})(y′) > c, ∀ y′ ∈ U_{k}.  (17)

We define a new partition of ℝ^{n+1} such that Ω̃_{j} := U_{k} ∪ Ω_{j} \ U_{j}, Ω̃_{k} := U_{j} ∪ Ω_{k} \ U_{k}, and Ω̃_{i} := Ω_{i} for all i ∈ {1, …, m} \ {j, k}. Then

∑_{i=1}^{m} ∫_{ℝ^{n+1}} 1Ω̃_{i}(x)T_{ρ}1Ω̃_{i}(x)γ_{n+1}(x) dx − ∑_{i=1}^{m} ∫_{ℝ^{n+1}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω_{i}}(x)γ_{n+1}(x) dx

= ∫_{ℝ^{n+1}} 1Ω̃_{j}(x)T_{ρ}1Ω̃_{j}(x)γ_{n+1}(x) dx − ∫_{ℝ^{n+1}} 1_{Ω_{j}}(x)T_{ρ}1_{Ω_{j}}(x)γ_{n+1}(x) dx

+ ∫_{ℝ^{n+1}} 1Ω̃_{k}(x)T_{ρ}1Ω̃_{k}(x)γ_{n+1}(x) dx − ∫_{ℝ^{n+1}} 1_{Ω_{k}}(x)T_{ρ}1_{Ω_{k}}(x)γ_{n+1}(x) dx

= ∫_{ℝ^{n+1}}[1_{Ω_{j}} − 1_{U_{j}} + 1_{U_{k}}](x)T_{ρ}[1_{Ω_{j}} − 1_{U_{j}} + 1_{U_{k}}]γ_{n+1}(x) dx

+ ∫_{ℝ^{n+1}}[1_{Ω_{k}} − 1_{U_{k}} + 1_{U_{j}}]T_{ρ}[1_{Ω_{k}} − 1_{U_{k}} + 1_{U_{j}}]γ_{n+1}(x) dx

− ∫_{ℝ^{n+1}} 1_{Ω_{j}}(x)T_{ρ}1_{Ω_{j}}(x)γ_{n+1}(x) dx − ∫_{ℝ^{n+1}} 1_{Ω_{k}}(x)T_{ρ}1_{Ω_{k}}(x)γ_{n+1}(x) dx

= 2 ∫_{ℝ^{n+1}}[−1_{U_{j}} + 1_{U_{k}}](x)T_{ρ}[1_{Ω_{j}} − 1_{Ω_{k}}]γ_{n+1}(x) dx

+ 2 ∫_{ℝ^{n+1}}[1_{U_{j}} − 1_{U_{k}}]T_{ρ}[1_{U_{j}} − 1_{U_{k}}]γ_{n+1}(x) dx >^{(17)∧(15)} 0.

This contradicts the maximality of Ω_{1}, …, Ω_{m}. We conclude that (16) holds.

We now fix 1 ≤ i < j ≤ m and we upgrade (16) by examining the level sets of

T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x), ∀ x ∈ ℝ^{n+1}.

Fix c ∈ ℝ and consider the level set

Σ := {x ∈ ℝ^{n+1} : T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) = c}.

This level set has Hausdorff dimension at most n by [Che98, Theorem 2.3].

From the Strong Unique Continuation Property for the heat equation [Lin90], T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) does not vanish to infinite order at any x ∈ ℝ^{n+1}, so the argument of [HS89, Lemma 1.9] (see [HL94, Proposition 1.2] and also [Che98, Theorem 2.1]) shows that in a neighborhood of each x ∈ Σ, Σ can be written as a finite union of C^{∞} manifolds. That is, there exists a neighborhood U of x and there exists an integer k ≥ 1 such that

U ∩ Σ = ∪_{i=1}^{k}{y ∈ U: D^{i}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) ≠ 0, D^{j}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) = 0, ∀ 1 ≤ j ≤ i − 1}.

Here D^{i} denotes the array of all iterated partial derivatives of order i ≥ 1. We therefore have

Σ_{ij} := (∂^{∗}Ω_{i}) ∩ (∂^{∗}Ω_{j}) ⊇ {x ∈ ℝ^{n+1} : T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) = c_{ij}},

and the Lemma follows. □

From Lemma 2.4 and Definition 2.1, for all 1 ≤ i < j ≤ m, if x ∈ Σ_{ij}, then the unit normal vector N_{ij}(x) ∈ ℝ^{n+1} that points from Ω_{i} into Ω_{j} is well-defined on Σ_{ij}, ((∂Ω_{i}) ∩ (∂Ω_{j})) \ Σ_{ij} has Hausdorff dimension at most n − 1, and

N_{ij}(x) = ±\frac{\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)}{∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥},  ∀ x ∈ Σ_{ij}.  (18)

In Lemma 4.5 below we will show that the negative sign holds in (18) when Ω_{1}, …, Ω_{m} maximize Problem 1.5.

3. First and Second Variation

In this section, we recall some standard facts for variations of sets with respect to the Gaussian measure. Here is a summary of notation.

Summary of Notation.

• T_{ρ} denotes the Ornstein-Uhlenbeck operator with correlation parameter ρ ∈ (−1, 1).

• Ω_{1}, …, Ω_{m} denotes a partition of ℝ^{n+1} into m disjoint measurable sets.

• ∂^{∗}Ω denotes the reduced boundary of Ω ⊆ ℝ^{n+1}.

• Σ_{ij} := (∂^{∗}Ω_{i}) ∩ (∂^{∗}Ω_{j}) for all 1 ≤ i, j ≤ m.

• N_{ij}(x) is the unit normal vector to x ∈ Σ_{ij} that points from Ω_{i} into Ω_{j}, so that N_{ij} = −N_{ji}.

Throughout the paper, unless otherwise stated, we define G: ℝ^{n+1} × ℝ^{n+1} → ℝ to be the following function. For all x, y ∈ ℝ^{n+1}, ∀ ρ ∈ (−1, 1), define

\begin{aligned}G(x, y) & = (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)}e^{\frac{−∥x∥^{2}−∥y∥^{2}+2ρ⟨x,y⟩}{2(1−ρ^{2})}} \\ & = (1 − ρ^{2})^{−(n+1)/2}γ_{n+1}(x)γ_{n+1}(y)e^{\frac{−ρ^{2}(∥x∥^{2}+∥y∥^{2})+2ρ⟨x,y⟩}{2(1−ρ^{2})}} \\ & = (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2}γ_{n+1}(x)e^{\frac{−∥y−ρx∥^{2}}{2(1−ρ^{2})}} . \end{aligned}  (19)

We can then rewrite the noise stability from Definition 1.4 as

∫_{ℝ^{n+1}} 1_{Ω}(x)T_{ρ}1_{Ω}(x)γ_{n+1}(x) dx = ∫_{Ω} ∫_{Ω} G(x, y) dxdy.

Our first and second variation formulas for the noise stability will be written in terms of G.

Lemma 3.1 (The First Variation [CS07]; also [HMN16, Lemma 3.1, Equation (7)]). Let X ∈ C_{0}^{∞}(ℝ^{n+1}, ℝ^{n+1}). Let Ω ⊆ ℝ^{n+1} be a measurable set such that ∂Ω is a locally finite union of C^{∞} manifolds. Let {Ω^{(s)}}_{s∈(−1,1)} be the corresponding variation of Ω. Then

\frac{d}{ds}|_{s=0} ∫_{ℝ^{n+1}} 1_{Ω^{(s)}}(y)G(x, y) dy = ∫_{∂Ω} G(x, y)⟨X(y), N(y)⟩ dy.  (20)

The following Lemma is a consequence of (20) and Lemma 2.4.

Lemma 3.2 (The First Variation for Maximizers). Suppose Ω_{1}, …, Ω_{m} ⊆ ℝ^{n+1} maximize Problem 1.5. Then for all 1 ≤ i < j ≤ m, there exists c_{ij} ∈ ℝ such that

T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) = c_{ij}, ∀ x ∈ Σ_{ij}.

Proof. Fix 1 ≤ i < j ≤ m and denote f_{ij}(x) := ⟨X(x), N_{ij}(x)⟩ for all x ∈ Σ_{ij}. From Lemma 3.1, if X is nonzero outside of Σ_{ij}, we get

\frac{1}{2} \frac{d}{ds}|_{s=0} ∑_{i=1}^{m} ∫_{ℝ^{n+1}} 1_{Ω_{i}^{(s)}}(x)T_{ρ}1_{Ω_{i}^{(s)}}(x)γ_{n+1}(x) dx

= ∫_{Ω_{i}} G(x, y) ∫_{Σ_{ij}}⟨X(x), N_{ij}(x)⟩ dx dy + ∫_{Ω_{j}} G(x, y) ∫_{Σ_{ij}}⟨X(x), N_{ji}(x)⟩ dx dy

=^{(3)∧(19)} ∫_{Σ_{ij}} T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)f_{ij}(x) dx.

We used above N_{ij} = −N_{ji}. If T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) is nonconstant, then we can construct f_{ij} supported in Σ_{ij} with ∫_{∂^{∗}Ω_{i′}} f_{ij}(x)γ_{n+1}(x)dx = 0 for all 1 ≤ i′ ≤ m to give a nonzero derivative, contradicting the maximality of Ω_{1}, …, Ω_{m} (as in Lemma 2.4 and (17)). □

Theorem 3.3 (General Second Variation Formula, [CS07, Theorem 2.6]; also [Hei15, Theorem 1.10]). Let X ∈ C_{0}^{∞}(ℝ^{n+1}, ℝ^{n+1}). Let Ω ⊆ ℝ^{n+1} be a measurable set such that ∂Ω is a locally finite union of C^{∞} manifolds. Let {Ω^{(s)}}_{s∈(−1,1)} be the corresponding variation of Ω. Define V as in (14). Then

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}} 1_{Ω^{(s)}}(y)G(x, y)1_{Ω^{(s)}}(x) dxdy

= ∫_{Σ} ∫_{Σ} G(x, y)⟨X(x), N(x)⟩⟨X(y), N(y)⟩ dxdy + ∫_{Σ} div(V (x, 0)X(x))⟨X(x), N(x)⟩ dx.

4. Noise Stability and the Calculus of Variations

We now further refine the first and second variation formulas from the previous section. The following formula follows by using G(x, y) := γ_{n+1}(x)γ_{n+1}(y) ∀ x, y ∈ ℝ^{n+1} in Lemma 3.1 and in Theorem 3.3.

Lemma 4.1 (Variations of Gaussian Volume, [Led01]). Let Ω ⊆ ℝ^{n+1} be a measurable set such that ∂Ω is a locally finite union of C^{∞} manifolds. Let X ∈ C_{0}^{∞}(ℝ^{n+1}, ℝ^{n+1}). Let {Ω^{(s)}}_{s∈(−1,1)} be the corresponding variation of Ω. Denote f(x) := ⟨X(x), N(x)⟩ for all x ∈ Σ := ∂^{∗}Ω. Then

\frac{d}{ds}|_{s=0}γ_{n+1}(Ω^{(s)}) = ∫_{Σ} f(x)γ_{n+1}(x) dx.

\frac{d^{2}}{ds^{2}} |_{s=0}γ_{n+1}(Ω^{(s)}) = ∫_{Σ}(div(X) − ⟨X, x⟩)f(x)γ_{n+1}(x) dx.

Lemma 4.2 (Extension Lemma for Existence of Volume-Preserving Variations, [Hei18, Lemma 3.9]). Let X′ ∈ C_{0}^{∞}(ℝ^{n+1}, ℝ^{n+1}) be a vector field. Define f_{ij} := ⟨X′, N_{ij}⟩ ∈ C_{0}^{∞}(Σ_{ij}) for all 1 ≤ i < j ≤ m. If

∀ 1 ≤ i ≤ m, ∑_{j∈{1,...,m}\{i}} ∫_{Σ_{ij}} f_{ij}(x)γ_{n}(x) dx = 0,  (21)

then X′|_{∪_{1≤i<j≤m}Σ_{ij}} can be extended to a vector field X ∈ C_{0}^{∞}(ℝ^{n+1}, ℝ^{n+1}) such that the corresponding variations {Ω_{i}^{(s)}}_{1≤i≤m,s∈(−1,1)} satisfy

∀ 1 ≤ i ≤ m, ∀ s ∈ (−1, 1), γ_{n+1}(Ω_{i}^{(s)}) = γ_{n+1}(Ω_{i}).

Lemma 4.3. Define G as in (19). Let f: Σ → ℝ be continous and compactly supported. Then

∫_{Σ} ∫_{Σ} G(x, y)f(x)f(y) dxdy ≥ 0.

Proof. If g: ℝ^{n+1} → ℝ is continuous and compactly supported, then it is well known that

∫_{Σ} ∫_{Σ} G(x, y)g(x)g(y) dxdy ≥ 0,

since e.g. \frac{G(x,y)}{γ_{n+1(x)}γ_{n+1}(y)} is the Mehler kernel, which can be written as an (infinite-dimensional) positive semidefinite matrix. That is, there exists an orthonormal basis {ψ_{i}}_{i=1}^{∞} of L_{2}(γ_{n+1}) (of Hermite polynomials) and there exists a sequence of nonnegative real numbers {λ_{i}}_{i=1}^{∞} such that the following series converges absolutely pointwise:

\frac{G(x, y)}{γ_{n+1}(x)γ_{n+1}(y)} = ∑_{i=1}^{∞} λ_{i}ψ_{i}(x)ψ_{i}(y), ∀ x, y ∈ ℝ^{n+1}.

From Mercer’s Theorem, this is equivalent to : ∀ p ≥ 1, for all z^{(1)}, …, z^{(p)} ∈ ℝ^{n}, for all β_{1}, …, β_{p} ∈ ℝ,

∑_{i,j=1}^{p} β_{i}β_{j}G(z^{(i)}, z^{(j)}) ≥ 0.

In particular, this holds for all z^{(1)}, …, z^{(p)} ∈ ∂Ω ⊆ ℝ^{n+1}. So, the positive semidefinite property carries over (by restriction) to ∂Ω. □

4.1. Two Sets. For didactic purposes, we first present the second variation of noise stability when m = 2 in Conjecture 1.5.

Lemma 4.4 (Second Variation of Noise Stability). Let Ω ⊆ ℝ^{n+1} be a measurable set such that ∂Ω is a locally finite union of C^{∞} manifolds. Let X ∈ C_{0}^{∞}(ℝ^{n+1}, ℝ^{n+1}). Let {Ω^{(s)}}_{s∈(−1,1)} be the corresponding variation of Ω. Denote f(x) := ⟨X(x), N(x)⟩ for all x ∈ Σ := ∂^{∗}Ω. Then

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}} 1_{Ω^{(s)}}(y)G(x, y)1_{Ω^{(s)}}(x) dxdy = ∫_{Σ} ∫_{Σ} G(x, y)f(x)f(y) dxdy

+ ∫_{Σ}⟨\overline{∇}T_{ρ}1_{Ω}(x), X(x)⟩f(x)γ_{n+1}(x) dx
+ ∫_{Σ} T_{ρ}1_{Ω}(x)(div(X(x)) − ⟨X(x), x⟩)f(x)γ_{n+1}(x) dx.

(22)

Proof. For all x ∈ ℝ^{n+1}, we have V (x, 0) =^{(14)} ∫_{Ω} G(x, y) dy =^{(3)} γ_{n+1}(x)T_{ρ}1_{Ω}(x). So, from Theorem 3.3,

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}} 1_{Ω^{(s)}}(y)G(x, y)1_{Ω^{(s)}}(x) dxdy

= ∫_{Σ} ∫_{Σ} G(x, y)⟨X(x), N(x)⟩⟨X(y), N(y)⟩ dxdy

+ ∫_{Σ}(∑_{i=1}^{n+1} T_{ρ}1_{Ω}(x)\frac{∂}{∂x_{i}} X_{i}(x) − x_{i}T_{ρ}1_{Ω}(x)X_{i}(x)

+ \frac{∂}{∂x_{i}} T_{ρ}1_{Ω}(x)X_{i}(x))⟨X(x), N(x)⟩γ_{n+1}(x) dx.

That is, (22) holds. □

Lemma 4.5 (Volume Preserving Second Variation of Maximizers). Suppose Ω, Ω^{c} ⊆ ℝ^{n+1} maximize Problem 1.5 for 0 < ρ < 1 and m = 2. Let {Ω^{(s)}}_{s∈(−1,1)} be the corresponding variation of Ω. Denote f(x) := ⟨X(x), N(x)⟩ for all x ∈ Σ := ∂^{∗}Ω. If

∫_{Σ} f(x)γ_{n+1}(x) dx = 0,

Then there exists an extension of the vector field X|_{Σ} such that the corresponding variation of {Ω^{(s)}}_{s∈(−1,1)} satisfies

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}} 1_{Ω^{(s)}}(y)G(x, y)1_{Ω^{(s)}}(x) dxdy

= ∫_{Σ} ∫_{Σ} G(x, y)f(x)f(y) dxdy − ∫_{Σ} ∥\overline{∇}T_{ρ}1_{Ω}(x)∥ (f(x))^{2}γ_{n+1}(x) dx.

(23)

Moreover,

\overline{∇}T_{ρ}1_{Ω}(x) = −N(x) ∥\overline{∇}T_{ρ}1_{Ω}(x)∥ ,  ∀ x ∈ Σ.  (24)

Proof. From Lemma 3.1, T_{ρ}1_{Ω}(x) is constant for all x ∈ Σ. So, from Lemma 4.1 and Lemma 4.2, the last term in (22) vanishes, i.e.

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}} 1_{Ω^{(s)}}(y)G(x, y)1_{Ω^{(s)}}(x) dxdy

= ∫_{Σ} ∫_{Σ} G(x, y)⟨X(x), N(x)⟩⟨X(y), N(y)⟩ dxdy
+ ∫_{Σ}⟨\overline{∇}T_{ρ}1_{Ω}(x), X(x)⟩⟨X(x), N(x)⟩γ_{n+1}(x) dx.

(Here \overline{∇} denotes the gradient in ℝ^{n+1}.) Since T_{ρ}1_{Ω}(x) is constant for all x ∈ ∂Ω by Lemma 3.2, \overline{∇}T_{ρ}1_{Ω}(x) is parallel to N(x) for all x ∈ ∂Ω. That is,

\overline{∇}T_{ρ}1_{Ω}(x) = ± ∥\overline{∇}T_{ρ}1_{Ω}(x)∥ N(x),  ∀ x ∈ ∂Ω.  (25)

In fact, we must have a negative sign in (25), otherwise we could find a vector field X supported near x ∈ ∂Ω such that (25) has a positive sign, and then since G is a positive semidefinite function by Lemma 4.3, we would have

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}} 1_{Ω^{(s)}}(y)G(x, y)1_{Ω^{(s)}}(x) dxdy

≥ ∫_{Σ}⟨\overline{∇}T_{ρ}1_{Ω}(x), X(x)⟩⟨X(x), N(x)⟩γ_{n+1}(x) dx > 0,

a contradiction. In summary,

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}} 1_{Ω^{(s)}}(y)G(x, y)1_{Ω^{(s)}}(x) dxdy

= ∫_{Σ} ∫_{Σ} G(x, y)⟨X(x), N(x)⟩⟨X(y), N(y)⟩ dxdy
− ∫_{Σ} ∥\overline{∇}T_{ρ}1_{Ω}(x)∥ ⟨X(x), N(x)⟩^{2}γ_{n+1}(x) dx.
□

4.2. More than Two Sets. We can now generalize Section 4.1 to the case of m > 2 sets.

Lemma 4.6 (Second Variation of Noise Stability, Multiple Sets). Let Ω_{1}, …, Ω_{m} ⊆ ℝ^{n+1} be a partition of ℝ^{n+1} into measurable sets such that ∂Ω_{i} is a locally finite union of C^{∞} manifolds for all 1 ≤ i ≤ m. Let X ∈ C_{0}^{∞}(ℝ^{n+1}, ℝ^{n+1}). Let {Ω_{i}^{(s)}}_{s∈(−1,1)} be the corresponding variation of Ω_{i} for all 1 ≤ i ≤ m. Denote f_{ij}(x) := ⟨X(x), N_{ij}(x)⟩ for all x ∈ Σ_{ij} := (∂^{∗}Ω_{i}) ∩ (∂^{∗}Ω_{j}). We let N denote the exterior pointing unit normal vector to ∂^{∗}Ω_{i} for any 1 ≤ i ≤ m. Then

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∑_{i=1}^{m} ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}} 1_{Ω_{i}^{(s)}}(y)G(x, y)1_{Ω_{i}^{(s)}}(x) dxdy

= ∑_{1≤i<j≤m} ∫_{Σ_{ij}} [( ∫_{∂^{∗}Ω_{i}} − ∫_{∂^{∗}Ω_{j}} )G(x, y)⟨X(y), N(y)⟩ dy]f_{ij}(x) dx

+ ∫_{Σ_{ij}}⟨\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x), X(x)⟩f_{ij}(x)γ_{n+1}(x) dx
+ ∫_{Σ_{ij}} T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)(div(X(x)) − ⟨X(x), x⟩)f_{ij}(x)γ_{n+1}(x) dx.

(26)

Proof. From Lemma 4.4,

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}} 1_{Ω_{i}^{(s)}}(y)G(x, y)1_{Ω_{i}^{(s)}}(x) dxdy

= ∫_{∂^{∗}Ω_{i}} ∫_{∂^{∗}Ω_{i}} G(x, y)⟨X(x), N(x)⟩⟨X(y), N(y)⟩ dxdy
+ ∫_{∂^{∗}Ω_{i}}⟨\overline{∇}T_{ρ}1_{Ω_{i}}(x), X(x)⟩⟨X(x), N(x)⟩γ_{n+1}(x) dx
+ ∫_{∂^{∗}Ω_{i}} T_{ρ}1_{Ω_{i}}(x)(div(X(x)) − ⟨X(x), x⟩)⟨X(x), N(x)⟩γ_{n+1}(x) dx.

Summing over 1 ≤ i ≤ m and using N_{ij} = −N_{ji} completes the proof. □

Below, we need the following combinatorial Lemma, the case m = 3 being treated in [HMRR02, Proposition 3.3].

Lemma 4.7 ([Hei19, Lemma 4.6]). Let m ≥ 3. Let

D_{1} := \{(x_{ij})_{1≤i≠j≤m} ∈ ℝ^{\binom{m}{2}} : ∀ 1 ≤ i ≠ j ≤ m, x_{ij} = −x_{ji}, ∑_{j∈\{1,...,m\}: j≠i} x_{ij} = 0\}.

D_{2} := \{(x_{ij})_{1≤i≠j≤m} ∈ ℝ^{\binom{m}{2}} : ∀ 1 ≤ i ≠ j ≤ m, x_{ij} = −x_{ji},
∀ 1 ≤ i < j < k ≤ m x_{ij} + x_{jk} + x_{ki} = 0}.

Let x ∈ D_{1} and let y ∈ D_{2}. Then ∑_{1≤i<j≤m} x_{ij}y_{ij} = 0.

Proof. D_{1} is defined to be perpendicular to vectors in D_{2}, and vice versa. That is, D_{1} and D_{2} are orthogonal complements of each other, and in terms of vector spaces, D_{1} ⊕ D_{2} = ℝ^{\binom{m}{2}}. Consequently, the inner product of any x ∈ D_{1} and y ∈ D_{2} is zero. □

Lemma 4.8 (Volume Preserving Second Variation of Maximizers, Multiple Sets). Let Ω_{1}, …, Ω_{m} ⊆ ℝ^{n+1} be a partition of ℝ^{n+1} into measurable sets such that ∂Ω_{i} is a locally finite union of C^{∞} manifolds for all 1 ≤ i ≤ m. Let X ∈ C_{0}^{∞}(ℝ^{n+1}, ℝ^{n+1}). Let {Ω_{i}^{(s)}}_{s∈(−1,1)} be the corresponding variation of Ω_{i} for all 1 ≤ i ≤ m. Denote f_{ij}(x) := ⟨X(x), N_{ij}(x)⟩ for all x ∈ Σ_{ij} := (∂^{∗}Ω_{i}) ∩ (∂^{∗}Ω_{j}). We let N denote the exterior pointing unit normal vector to ∂^{∗}Ω_{i} for any 1 ≤ i ≤ m. Then

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∑_{i=1}^{m} ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}} 1_{Ω_{i}^{(s)}}(y)G(x, y)1_{Ω_{i}^{(s)}}(x) dxdy

= ∑_{1≤i<j≤m} ∫_{Σ_{ij}} [( ∫_{∂^{∗}Ω_{i}} − ∫_{∂^{∗}Ω_{j}} )G(x, y)⟨X(y), N(y)⟩ dy]f_{ij}(x) dx

− ∫_{Σ_{ij}} ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥ (f_{ij}(x))^{2}γ_{n+1}(x) dx.

(27)

Also,

\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) = −N_{ij}(x) ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥ ,  ∀ x ∈ Σ_{ij}.  (28)

Moreover, ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥ > 0 for all x ∈ Σ_{ij}, except on a set of Hausdorff dimension at most n − 1.

Proof. From Lemma 3.2, there exist constants (c_{ij})_{1≤i<j≤m} such that T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) = c_{ij} for all 1 ≤ i < j ≤ m, for all x ∈ Σ_{ij}. So, from Lemma 4.6,

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∑_{i=1}^{m} ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}} 1_{Ω_{i}^{(s)}}(y)G(x, y)1_{Ω_{i}^{(s)}}(x) dxdy

= ∑_{1≤i<j≤m} ∫_{Σ_{ij}} [( ∫_{∂^{∗}Ω_{i}} − ∫_{∂^{∗}Ω_{j}} )G(x, y)⟨X(y), N(y)⟩ dy]⟨X(x), N_{ij}(x)⟩ dx

+ ∫_{Σ_{ij}}⟨\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x), X(x)⟩⟨X(x), N_{ij}(x)⟩γ_{n+1}(x) dx
+ c_{ij} ∫_{Σ_{ij}} (div(X(x)) − ⟨X(x), x⟩)⟨X(x), N_{ij}(x)⟩γ_{n+1}(x) dx.

The last term then vanishes by Lemma 4.7. That is,

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∑_{i=1}^{m} ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}} 1_{Ω_{i}^{(s)}}(y)G(x, y)1_{Ω_{i}^{(s)}}(x) dxdy

= ∑_{1≤i<j≤m} ∫_{Σ_{ij}} [( ∫_{∂^{∗}Ω_{i}} − ∫_{∂^{∗}Ω_{j}} )G(x, y)⟨X(y), N(y)⟩ dy]⟨X(x), N_{ij}(x)⟩ dx

+ ∫_{Σ_{ij}}⟨\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x), X(x)⟩⟨X(x), N_{ij}(x)⟩γ_{n+1}(x) dx.

Meanwhile, if 1 ≤ i < j ≤ m is fixed, it follows from Lemma 3.2 that

\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) = ±N_{ij}(x) ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥ ,  ∀ x ∈ Σ_{ij}.  (29)

In fact, we must have a negative sign in (29), otherwise we could find a vector field X supported near x ∈ Σ_{ij} such that (25) has a positive sign, and then since G is a positive semidefinite function by Lemma 4.3, we would have

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∑_{i=1}^{m} ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}} 1_{Ω_{i}^{(s)}}(y)G(x, y)1_{Ω_{i}^{(s)}}(x) dxdy

≥ ∫_{Σ_{ij}}⟨\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x), X(x)⟩⟨X(x), N(x)⟩γ_{n+1}(x) dx > 0,

a contradiction. In summary,

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∑_{i=1}^{m} ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}} 1_{Ω_{i}^{(s)}}(y)G(x, y)1_{Ω_{i}^{(s)}}(x) dxdy

= ∑_{1≤i<j≤m} ∫_{∂Σ_{ij}} [( ∫_{∂Ω_{i}} − ∫_{∂Ω_{j}} )G(x, y)⟨X(y), N_{ij}(y)⟩ dy]⟨X(x), N_{ij}(x)⟩ dx

− ∫_{Σ_{ij}} ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥ ⟨X(x), N_{ij}(x)⟩^{2}γ_{n+1}(x) dx.
□

5. Almost Eigenfunctions of the Second Variation

For didactic purposes, we first consider the case m = 2, and we then later consider the case m > 2.

5.1. Two Sets. Let Σ := ∂^{∗}Ω. For any bounded measurable f: Σ → ℝ, define the following function (if it exists):

S(f)(x) := (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2} ∫_{Σ} f(y)e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy,  ∀ x ∈ Σ.  (30)

Lemma 5.1 (Key Lemma, m = 2, Translations as Almost Eigenfunctions). Let Ω, Ω^{c} maximize Problem 1.5 for m = 2. Let v ∈ ℝ^{n+1}. Then

S(⟨v, N⟩)(x) = ⟨v, N(x)⟩\frac{1}{ρ} ∥\overline{∇}T_{ρ}1_{Ω}(x)∥ , ∀ x ∈ Σ.

Proof. Since T_{ρ}1_{Ω}(x) is constant for all x ∈ ∂Ω by Lemma 3.2, \overline{∇}T_{ρ}1_{Ω}(x) is parallel to N(x) for all x ∈ ∂Ω. That is (24) holds, i.e.

\overline{∇}T_{ρ}1_{Ω}(x) = −N(x) ∥\overline{∇}T_{ρ}1_{Ω}(x)∥ ,  ∀ x ∈ Σ.  (31)

From Definition 3, and then using the divergence theorem,

⟨v, \overline{∇}T_{ρ}1_{Ω}(x)⟩ = (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2}⟨v, ∫_{Ω} \overline{∇}_{x}e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy⟩

= (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2} \frac{ρ}{1 − ρ^{2}} ∫_{Ω}⟨v, y − ρx⟩e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy

= −(1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2}ρ ∫_{Ω} div_{y}(ve^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} ) dy

= −(1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2}ρ ∫_{Σ}⟨v, N(y)⟩e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy

=^{(30)} −ρ S(⟨v, N⟩)(x).

(32)

Therefore,

⟨v, N(x)⟩ ∥\overline{∇}T_{ρ}1_{Ω}(x)∥ =^{(31)} −⟨v, \overline{∇}T_{ρ}1_{Ω}(x)⟩ =^{(32)} ρ S(⟨v, N⟩)(x).

□

Remark 5.2. To justify the use of the divergence theorem in (32), let r > 0 and note that we can differentiate under the integral sign of T_{ρ}1_{Ω∩B(0,r)}(x) to get

\overline{∇}T_{ρ}1_{Ω∩B(0,r)}(x) = (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2}⟨v, ∫_{Ω∩B(0,r)} \overline{∇}_{x}e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy⟩

= (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2} \frac{ρ}{1 − ρ^{2}} ∫_{Ω∩B(0,r)}⟨v, y − ρx⟩e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy

= −(1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2}ρ ∫_{Ω∩B(0,r)} div_{y}(ve^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} ) dy

= −(1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2}ρ ∫_{(Σ∩B(0,r))∪(Ω∩∂B(0,r))}⟨v, N(y)⟩e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy.

(33)

Fix r′ > 0. Fix x ∈ ℝ^{n+1} with ∥x∥ < r′. The last integral in (33) over Ω ∩ ∂B(0, r) goes to zero as r → ∞ uniformly over all such ∥x∥ < r′. Also \overline{∇}T_{ρ}1_{Ω}(x) exists a priori for all x ∈ ℝ^{n+1}, while

∥\overline{∇}T_{ρ}1_{Ω}(x) − \overline{∇}T_{ρ}1_{Ω∩B(0,r)}(x)∥ =^{(3)} \frac{ρ}{\sqrt{1 − ρ^{2}}} ∥∫_{ℝ^{n+1}} y1_{Ω∩B(0,r)^{c}}(xρ + y\sqrt{1 − ρ^{2}})γ_{n+1}(y) dy∥

≤ \frac{ρ}{\sqrt{1 − ρ^{2}}} sup_{w∈ℝ^{n+1} : ∥w∥=1} ∫_{ℝ^{n+1}} |⟨w, y⟩| 1_{B(0,r)^{c}}(xρ + y\sqrt{1 − ρ^{2}})γ_{n+1}(y) dy.

And the last integral goes to zero as r → ∞, uniformly over all ∥x∥ < r′.

Lemma 5.3 (Second Variation of Translations). Let v ∈ ℝ^{n+1}. Let Ω, Ω^{c} maximize Problem 1.5 for m = 2. Let {Ω^{(s)}}_{s∈(−1,1)} be the variation of Ω corresponding to the constant vector field X := v. Assume that

∫_{Σ}⟨v, N(x)⟩γ_{n+1}(x) dx = 0.

Then

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∫_{ℝ^{n+1}} 1_{Ω^{(s)}}(x)T_{ρ}1_{Ω^{(s)}}(x)γ_{n+1}(x) dx = (\frac{1}{ρ} − 1) ∫_{Σ} ∥\overline{∇}T_{ρ}1_{Ω}(x)∥⟨v, N(x)⟩^{2}γ_{n+1}(x) dx.

Proof. Let f(x) := ⟨v, N(x)⟩ for all x ∈ Σ. From Lemma 4.5,

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∫_{ℝ^{n+1}} 1_{Ω^{(s)}}(x)T_{ρ}1_{Ω^{(s)}}(x)γ_{n+1}(x) dx

= ∫_{Σ} (S(f)(x) − ∥\overline{∇}T_{ρ}1_{Ω}(x)∥f(x))f(x)γ_{n+1}(x) dx.

Applying Lemma 5.1, S(f)(x) = f(x)\frac{1}{ρ}∥\overline{∇}T_{ρ}1_{Ω}(x)∥ ∀ x ∈ Σ, proving the Lemma. Note also that ∫_{Σ} ∥\overline{∇}T_{ρ}1_{Ω}(x)∥⟨v, N(x)⟩^{2}γ_{n+1}(x) dx is finite priori by the divergence theorem and (24):

∞ > |∫_{Ω} ⟨v, −x + ∇⟨v, \overline{∇}T_{ρ}1_{Ω}(x)⟩⟩γ_{n+1}(x) dx| = |∫_{Ω} div(v⟨v, \overline{∇}T_{ρ}1_{Ω}(x)⟩γ_{n+1}(x)) dx|

= |∫_{Σ}⟨v, N(x)⟩⟨v, \overline{∇}T_{ρ}1_{Ω}(x)⟩γ_{n+1}(x) dx| =^{(24)} |∫_{Σ} ∥\overline{∇}T_{ρ}1_{Ω}(x)∥⟨v, N(x)⟩^{2}γ_{n+1}(x) dx| .

□

5.2. More than Two Sets. Let v ∈ ℝ^{n+1} and denote f_{ij} := ⟨v, N_{ij}⟩ for all 1 ≤ i, j ≤ m. For simplicity of notation in the formulas below, if 1 ≤ i ≤ m and if a vector N(x) appears inside an integral over ∂Ω_{i}, then N(x) denotes the unit exterior pointing normal vector to Ω_{i} at x ∈ ∂^{∗}Ω_{i}. Similarly, for simplicity of notation, we denote ⟨v, N⟩ as the collection of functions (⟨v, N_{ij}⟩)_{1≤i<j≤m}. For any 1 ≤ i < j ≤ m, define

S_{ij}(⟨v, N⟩)(x) := (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2}( ∫_{∂Ω_{i}} − ∫_{∂Ω_{j}} )⟨v, N(y)⟩e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy, ∀ x ∈ Σ_{ij}.

(34)

Lemma 5.4 (Key Lemma, m ≥ 2, Translations as Almost Eigenfunctions). Let Ω_{1}, …, Ω_{m} maximize problem 1.5. Fix 1 ≤ i < j ≤ m. Let v ∈ ℝ^{n+1}. Then

S_{ij}(⟨v, N⟩)(x) = ⟨v, N_{ij}(x)⟩\frac{1}{ρ} ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥ , ∀ x ∈ Σ_{ij}.

Proof. From Lemma 4.8, i.e. (28),

\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) = −N_{ij}(x) ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥ ,  ∀ x ∈ Σ_{ij}.  (35)

From Definition 3, and then using the divergence theorem,

⟨v, \overline{∇}T_{ρ}1_{Ω_{i}}(x)⟩ = (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2}⟨v, ∫_{Ω_{i}} \overline{∇}e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy⟩

= (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2} \frac{ρ}{1 − ρ^{2}} ∫_{Ω_{i}}⟨v, y − ρx⟩e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy

= −(1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2})ρ ∫_{Ω_{i}} div(ve^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} ) dy

= −(1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2}ρ ∫_{∂^{∗}Ω_{i}}⟨v, N(y)⟩e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy.

(36)

The use of the divergence theorem is justified in Remark 5.2. Therefore,

⟨v, N_{ij}(x)⟩ ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥ =^{(35)} −⟨v, \overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)⟩

=^{(36)} (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2}ρ( ∫_{∂^{∗}Ω_{i}} − ∫_{∂^{∗}Ω_{j}} )⟨v, N(y)⟩e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy

=^{(34)} ρ S_{ij}(⟨v, N⟩)(x).

□

Lemma 5.5 (Second Variation of Translations, Multiple Sets). Let v ∈ ℝ^{n+1}. Let Ω_{1}, …, Ω_{m} maximize problem 1.5. For each 1 ≤ i ≤ m, let {Ω_{i}^{(s)}}_{s∈(−1,1)} be the variation of Ω_{i} corresponding to the constant vector field X := v. Assume that

∫_{∂Ω_{i}}⟨v, N(x)⟩γ_{n+1}(x) dx = 0, ∀ 1 ≤ i ≤ m.

Then

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∑_{i=1}^{m} ∫_{ℝ^{n+1}} 1_{Ω_{i}^{(s)}}(x)T_{ρ}1_{Ω_{i}^{(s)}}(x)γ_{n+1}(x) dx

= (\frac{1}{ρ} − 1) ∑_{1≤i<j≤m} ∫_{Σ_{ij}} ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥⟨v, N_{ij}(x)⟩^{2}γ_{n+1}(x) dx.

Proof. For any 1 ≤ i < j ≤ m, let f_{ij}(x) := ⟨v, N_{ij}(x)⟩ for all x ∈ Σ. From Lemma 4.5,

\frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∑_{i=1}^{m} ∫_{ℝ^{n+1}} 1_{Ω^{(s)}}(x)T_{ρ}1_{Ω^{(s)}}(x)γ_{n+1}(x) dx

= ∑_{1≤i<j≤m} ∫_{Σ_{ij}} (S_{ij}(⟨v, N⟩)(x) − ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥f_{ij}(x))f_{ij}(x)γ_{n+1}(x) dx.

Applying Lemma 5.4, S_{ij}(⟨v, N⟩)(x) = f_{ij}(x)\frac{1}{ρ}∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥, proving the Lemma. Note also that ∑_{1≤i<j≤m} ∫_{Σ_{ij}} ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥⟨v, N_{ij}(x)⟩^{2}γ_{n+1}(x) dx is finite priori by the divergence theorem since

∞ > |∫_{Ω_{i}} ⟨v, −x + ∇⟨v, \overline{∇}T_{ρ}1_{Ω_{i}}(x)⟩⟩γ_{n+1}(x) dx| = |∫_{Ω_{i}} div(v⟨v, \overline{∇}T_{ρ}1_{Ω_{i}}(x)⟩γ_{n+1}(x)) dx|

= |∫_{Ω_{i}} div(v⟨v, \overline{∇}T_{ρ}1_{Ω_{i}}(x)⟩γ_{n+1}(x)) dx| = |∫_{∂^{∗}Ω_{i}}⟨v, \overline{∇}T_{ρ}(1_{Ω_{i}})(x)⟩⟨v, N(x)⟩γ_{n+1}(x) dx| .

Summing over 1 ≤ i ≤ m then gives

∞ > | ∑_{1≤i<j≤m} ∫_{Σ_{ij}}⟨v, \overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)⟩⟨v, N_{ij}(x)⟩γ_{n+1}(x) dx.|

=^{(28)} | ∑_{1≤i<j≤m} ∫_{Σ_{ij}} ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥⟨v, N_{ij}(x)⟩^{2}γ_{n+1}(x) dx.| .

□

6. Proof of the Main Structure Theorem

Proof of Theorem 1.9. Let m ≥ 2. Let 0 < ρ < 1. Fix a_{1}, …, a_{m} > 0 such that ∑_{i=1}^{m} a_{i} = 1. Let Ω_{1}, … Ω_{m} ⊆ ℝ^{n+1} be measurable sets that partition ℝ^{n+1} such that γ_{n+1}(Ω_{i}) = a_{i} for all 1 ≤ i ≤ m that maximize Problem 1.5. These sets exist by Lemma 2.3 and from Lemma 2.4 their boundaries are locally finite unions of C^{∞} n-dimensional manifolds. Define Σ_{ij} := (∂^{∗}Ω_{i}) ∩ (∂^{∗}Ω_{j}) for all 1 ≤ i < j ≤ m.

By Lemma 3.2, for all 1 ≤ i < j ≤ m, there exists c_{ij} ∈ ℝ such that

T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) = c_{ij}, ∀ x ∈ Σ_{ij}.

By this condition, the regularity Lemma 2.4, and the last part of Lemma 4.8,

\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) = −N_{ij}(x) ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥ , ∀ x ∈ Σ_{ij}.

Moreover, by the last part of Lemma 4.8, except for a set σ_{ij} of Hausdorff dimension at most n − 1, we have

∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥ > 0, ∀ x ∈ Σ_{ij} \ σ_{ij}. (37)

Fix v ∈ ℝ^{n+1}, and consider the variation of Ω_{1}, …, Ω_{m} induced by the constant vector field X := v. For all 1 ≤ i < j ≤ m, define S_{ij} as in (34). Define

V := {v ∈ ℝ^{n+1} : ∑_{j∈{1,...,m}\{i}} ∫_{Σ_{ij}}⟨v, N_{ij}(x)⟩γ_{n+1}(x) dx = 0,  ∀ 1 ≤ i ≤ m}.

From Lemma 5.5,

v ∈ V ⟹ \frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∑_{i=1}^{m} ∫_{ℝ^{n+1}} 1_{Ω_{i}^{(s)}}(x)T_{ρ}1_{Ω_{i}^{(s)}}(x)γ_{n+1}(x) dx

= (\frac{1}{ρ} − 1) ∑_{1≤i<j≤m} ∫_{Σ_{ij}} ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥⟨v, N_{ij}(x)⟩^{2}γ_{n+1}(x) dx.

Since 0 < ρ < 1, (37) implies

v ∈ V ⟹ ⟨v, N_{ij}(x)⟩ = 0,  ∀ x ∈ Σ_{ij}, ∀ 1 ≤ i < j ≤ m.  (38)

The set V has dimension at least n + 2 − m, by the rank-nullity theorem, since V is the null space of the linear operator M: ℝ^{n+1} → ℝ^{m} defined by

(M(v))_{i} := ∑_{j∈{1,...,m}\{i}} ∫_{Σ_{ij}}⟨v, N_{ij}(x)⟩γ_{n+1}(x) dx, ∀ 1 ≤ i ≤ m

and M has rank at most m − 1 (since ∑_{i=1}^{m}(M(v))_{i} = 0 for all v ∈ ℝ^{n+1}). So, by (38), after rotating Ω_{1}, …, Ω_{m}, we conclude that there exist measurable Ω′_{1}, …, Ω′_{m} ⊆ ℝ^{m−1} such that

Ω_{i} = Ω′_{i} × ℝ^{n+2−m}, ∀ 1 ≤ i ≤ m.

□

7. The Case of Negative Correlation

In this section, we consider the case that ρ < 0 in Problem 1.5. When ρ < 0 and h: ℝ^{n+1} → [−1, 1] is measurable, then quantity

∫_{ℝ^{n+1}} h(x)T_{ρ}h(x)γ_{n+1}(x) dx

could be negative, so a few parts of the above argument do not work, namely the existence Lemma 2.3. We therefore replace the noise stability with a more general bilinear expression, guaranteeing existence of the corresponding problem. The remaining parts of the argument are essentially identical, mutatis mutandis. We indicate below where the arguments differ in the bilinear case.

When ρ < 0, we look for a minimum of noise stability, rather than a maximum. Correspondingly, we expect that the plurality function minimizes noise stability when ρ < 0. If ρ < 0, then (3) implies that

∫_{ℝ^{n+1}} h(x)T_{ρ}h(x)γ_{n+1}(x) dx = ∫_{ℝ^{n+1}} h(x)T_{(−ρ)}h(−x)γ_{n+1}(x) dx.

So, in order to understand the minimum of noise stability for negative correlations, it suffices to consider the following bilinear version of the standard simplex problem with positive correlation.

Problem 7.1 (Standard Simplex Problem, Bilinear Version, Positive Correlation, [IM12]). Let m ≥ 3. Fix a_{1}, …, a_{m} > 0 such that ∑_{i=1}^{m} a_{i} = 1. Fix 0 < ρ < 1. Find measurable sets Ω_{1}, … Ω_{m}, Ω′_{1}, … Ω′_{m} ⊆ ℝ^{n+1} with ∪_{i=1}^{m}Ω_{i} = ∪_{i=1}^{m}Ω′_{i} = ℝ^{n+1} and γ_{n+1}(Ω_{i}) = γ_{n+1}(Ω′_{i}) = a_{i} for all 1 ≤ i ≤ m that minimize

∑_{i=1}^{m} ∫_{ℝ^{n+1}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω′_{i}}(x)γ_{n+1}(x) dx,

subject to the above constraints.

Conjecture 7.2 (Standard Simplex Conjecture, Bilinear Version, Positive Correlation [IM12]). Let Ω_{1}, … Ω_{m}, Ω′_{1}, … Ω′_{m} ⊆ ℝ^{n+1} minimize Problem 1.5. Assume that m − 1 ≤ n + 1. Fix 0 < ρ < 1. Let z_{1}, …, z_{m} ∈ ℝ^{n+1} be the vertices of a regular simplex in ℝ^{n+1} centered at the origin. Then ∃ w ∈ ℝ^{n+1} such that, for all 1 ≤ i ≤ m,

Ω_{i} = −Ω′_{i} = w + {x ∈ ℝ^{n+1} : ⟨x, z_{i}⟩ = max_{1≤j≤m}⟨x, z_{j}⟩}.

In the case that a_{i} = 1/m for all 1 ≤ i ≤ m, it is assumed that w = 0 in Conjecture 7.2. Since we consider a bilinear version of noise stability in Problem 7.1, existence of an

optimizer is easier than in Problem 1.5.

Lemma 7.3 (Existence of a Minimizer). Let 0 < ρ < 1 and let m ≥ 2. Then there exist measurable sets Ω_{1}, … Ω_{m}, Ω′_{1}, … Ω′_{m} that minimize Problem 7.1.

Proof. Define Δ_{m} as in (6). Let f, g: ℝ^{n+1} → Δ_{m}. The set D_{0} := {f: ℝ^{n+1} → Δ_{m}} is norm closed, bounded, and convex, therefore it is weakly compact and convex. Consider the function

C(f, g) := ∑_{i=1}^{m} ∫_{ℝ^{n+1}} f_{i}(x)T_{ρ}g_{i}(x)γ_{n+1}(x) dx.

This function is weakly continuous on D_{0} × D_{0}, and D_{0} × D_{0} is weakly compact, so there exists f̃, g̃ ∈ D_{0} such that C(f̃, g̃) = min_{f,g∈D} C(f, g). Since C is bilinear and D_{0} is convex, the minimum of C must be achieved at an extreme point of D_{0} × D_{0}. Let e_{1}, …, e_{m} denote the standard basis of ℝ^{m}, so that f, g takes their values in {e_{1}, …, e_{m}}. Then, for any 1 ≤ i ≤ m, define Ω_{i} := {x ∈ ℝ^{n+1} : f(x) = e_{i}} and Ω′_{i} := {x ∈ ℝ^{n+1} : g(x) = e_{i}}. Note that f_{i} = 1_{Ω_{i}} and g_{i} = 1_{Ω′_{i}} for all 1 ≤ i ≤ m. □

Lemma 7.4 (Regularity of a Minimizer). Let Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} ⊆ ℝ^{n+1} be the measurable sets minimizing Problem 1.5, guaranteed to exist by Lemma 7.3. Then the sets Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} have locally finite surface area. Moreover, for all 1 ≤ i ≤ m and for all x ∈ ∂Ω_{i}, there exists a neighborhood U of x such that U ∩ ∂Ω_{i} is a finite union of C^{∞} n-dimensional manifolds. The same holds for Ω′_{1}, …, Ω′_{m}.

We denote Σ_{ij} := (∂^{∗}Ω_{i}) ∩ (∂^{∗}Ω_{j}), Σ′_{ij} := (∂^{∗}Ω′_{i}) ∩ (∂^{∗}Ω′_{j}) for all 1 ≤ i < j ≤ m.

Lemma 7.5 (The First Variation for Minimizers). Suppose Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} ⊆ ℝ^{n+1} minimize Problem 7.1. Then for all 1 ≤ i < j ≤ m, there exists c_{ij}, c′_{ij} ∈ ℝ such that

T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) = c_{ij}, ∀ x ∈ Σ_{ij}.
T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x) = c′_{ij}, ∀ x ∈ Σ_{ij}.

We denote N_{ij}(x) as the unit exterior normal vector to Σ_{ij} for all 1 ≤ i < j ≤ m. Also denote N′_{ij}(x) as the unit exterior normal vector to Σ′_{ij} for all 1 ≤ i < j ≤ m. Let Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} ⊆ ℝ^{n+1} be a partition of ℝ^{n+1} into measurable sets such that ∂Ω_{i}, ∂Ω′_{i} are a locally finite union of C^{∞} manifolds for all 1 ≤ i ≤ m. Let X, X′ ∈ C_{0}^{∞}(ℝ^{n+1}, ℝ^{n+1}). Let {Ω_{i}^{(s)}}_{s∈(−1,1)} be the variation of Ω_{i} corresponding to X for all 1 ≤ i ≤ m. Let {Ω_{i}^{′(s)}}_{s∈(−1,1)} be the variation of Ω′_{i} corresponding to X′ for all 1 ≤ i ≤ m. Denote f_{ij}(x) := ⟨X(x), N_{ij}(x)⟩ for all x ∈ Σ_{ij} and f′_{ij}(x) := ⟨X′(x), N′_{ij}(x)⟩ for all x ∈ Σ′_{ij}. We let N denote the exterior pointing unit normal vector to ∂^{∗}Ω_{i} for any 1 ≤ i ≤ m and we let N′ denote the exterior pointing unit normal vector to ∂^{∗}Ω′_{i} for any 1 ≤ i ≤ m.

Lemma 7.6 (Volume Preserving Second Variation of Minimizers, Multiple Sets). Let Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} ⊆ ℝ^{n+1} be two partitions of ℝ^{n+1} into measurable sets such that ∂Ω_{i}, ∂Ω′_{i} are a locally finite union of C^{∞} manifolds for all 1 ≤ i ≤ m. Then

\frac{d^{2}}{ds^{2}} |_{s=0} ∑_{i=1}^{m} ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}} 1_{Ω_{i}^{(s)}}(y)G(x, y)1_{Ω_{i}^{′(s)}}(x) dxdy

= ∑_{1≤i<j≤m} ∫_{Σ′_{ij}} [( ∫_{∂^{∗}Ω_{i}} − ∫_{∂^{∗}Ω_{j}} )G(x, y)⟨X(y), N(y)⟩ dy]f′_{ij}(x) dx

+ ∑_{1≤i<j≤m} ∫_{Σ_{ij}} [( ∫_{∂^{∗}Ω′_{i}} − ∫_{∂^{∗}Ω′_{j}} )G(x, y)⟨X′(y), N′(y)⟩ dy]f_{ij}(x) dx

+ ∫_{Σ′_{ij}} ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥(f′_{ij}(x))^{2}γ_{n+1}(x) dx

+ ∫_{Σ_{ij}} ∥\overline{∇}T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x)∥(f_{ij}(x))^{2}γ_{n+1}(x) dx.

(39)

Also,

\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) = N′_{ij}(x)∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥,  ∀ x ∈ Σ′_{ij}.
\overline{∇}T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x) = N_{ij}(x)∥\overline{∇}T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x)∥,  ∀ x ∈ Σ_{ij}. (40)

Moreover, ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥ > 0 for all x ∈ Σ′_{ij}, except on a set of Hausdorff dimension at most n − 1, and ∥\overline{∇}T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x)∥ > 0 for all x ∈ Σ_{ij}, except on a set of Hausdorff dimension at most n − 1.

Equation (40) and the last assertion require a slightly different argument than previously used. To see the last assertion, note that if there exists 1 ≤ i < j ≤ m such that ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥ = 0 on an open set in Σ′_{ij}, then choose X′ supported in this open set so that the third term of (39) is zero. Then, choose Y such that sum of the first two terms in (39) is negative. Multiplying then X by a small positive constant, and noting that the fourth term in (39) has quadratic dependence on X, we can create a negative second derivative of the noise stability, giving a contradiction. We can similarly justify the positive signs appearing in (40) (as opposed to the negative signs from (28)).

Let v ∈ ℝ^{n+1}. For simplicity of notation, we denote ⟨v, N⟩ as the collection of functions (⟨v, N_{ij}⟩)_{1≤i<j≤m} and we denote ⟨v, N′⟩ as the collection of functions (⟨v, N′_{ij}⟩)_{1≤i<j≤m}. For any 1 ≤ i < j ≤ m, define

S_{ij}(⟨v, N⟩)(x) := (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2}( ∫_{∂Ω_{i}} − ∫_{∂Ω_{j}} )⟨v, N(y)⟩e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy, ∀ x ∈ Σ_{ij′}

S′_{ij}(⟨v, N′⟩)(x) := (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2}( ∫_{∂Ω′_{i}} − ∫_{∂Ω′_{j}} )⟨v, N′(y)⟩e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy ∀ x ∈ Σ_{ij}.

(41)

Lemma 7.7 (Key Lemma, m ≥ 2, Translations as Almost Eigenfunctions). Let Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} ⊆ ℝ^{n+1} minimize problem 7.1. Fix 1 ≤ i < j ≤ m. Let v ∈ ℝ^{n+1}. Then

S_{ij}(⟨v, N⟩)(x) = −⟨v, N′_{ij}(x)⟩\frac{1}{ρ}∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥,  ∀ x ∈ Σ′_{ij}.
S′_{ij}(⟨v, N′⟩)(x) = −⟨v, N_{ij}(x)⟩\frac{1}{ρ}∥\overline{∇}T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x)∥,  ∀ x ∈ Σ_{ij}.

When compared to Lemma 5.4, Lemma 7.7 has a negative sign on the right side of the equality, resulting from the positive sign in (40) (as opposed to the negative sign on the right side of (28)). Lemmas 7.6 and 7.7 then imply the following.

Lemma 7.8 (Second Variation of Translations, Multiple Sets). Let 0 < ρ < 1. Let v ∈ ℝ^{n+1}. Let Ω_{1}, …, Ω_{m} minimize problem 1.5. For each 1 ≤ i ≤ m, let {Ω_{i}^{(s)}}_{s∈(−1,1)} be the variation of Ω_{i} corresponding to the constant vector field X := v. Assume that

∫_{∂Ω_{i}}⟨v, N(x)⟩γ_{n+1}(x) dx = ∫_{∂Ω′_{i}}⟨v, N(x)⟩γ_{n+1}(x) dx = 0, ∀ 1 ≤ i ≤ m.

Then

\frac{d^{2}}{ds^{2}} |_{s=0} ∑_{i=1}^{m} ∫_{ℝ^{n+1}} 1_{Ω_{i}^{(s)}}(x)T_{ρ}1_{Ω_{i}^{′(s)}}(x)γ_{n+1}(x) dx

= ( − \frac{1}{ρ} + 1) ∑_{1≤i<j≤m} ∫_{Σ_{ij}} ∥\overline{∇}T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x)∥⟨v, N_{ij}(x)⟩^{2}γ_{n+1}(x) dx

+ ( − \frac{1}{ρ} + 1) ∑_{1≤i<j≤m} ∫_{Σ′_{ij}} ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥⟨v, N′_{ij}(x)⟩^{2}γ_{n+1}(x) dx.

Since ρ ∈ (0, 1), −\frac{1}{ρ} + 1 < 0. (The analogous inequality in Lemma 5.5 was \frac{1}{ρ} − 1 > 0.) Repeating the argument of Theorem 1.9 then gives the following.

Theorem 7.9 (Main Structure Theorem/ Dimension Reduction, Negative Correlation). Fix 0 < ρ < 1. Let m ≥ 2 with 2m ≤ n + 3. Let Ω_{1}, … Ω_{m}, Ω′_{1}, … Ω′_{m} ⊆ ℝ^{n+1} minimize Problem 7.1. Then, after rotating the sets Ω_{1}, … Ω_{m}, Ω′_{1}, … Ω′_{m} and applying Lebesgue measure zero changes to these sets, there exist measurable sets Θ_{1}, … Θ_{m}, Θ′_{1}, … Θ′_{m} ⊆ ℝ^{2m−2} such that,

Ω_{i} = Θ_{i} × ℝ^{n−2m+3}, Ω′_{i} = Θ′_{i} × ℝ^{n−2m+3} ∀ 1 ≤ i ≤ m.

References

[BBJ17] Marco Barchiesi, Alessio Brancolini, and Vesa Julin, Sharp dimension free quantitative estimates for the Gaussian isoperimetric inequality, Ann. Probab. 45 (2017), no. 2, 668–697. MR 3630285

[Che98] Xu-Yan Chen, A strong unique continuation theorem for parabolic equations, Math. Ann. 311 (1998), no. 4, 603–630. MR 1637972

[CL12] Marco Cicalese and Gian Paolo Leonardi, A selection principle for the sharp quantitative isoperimetric inequality, Arch. Ration. Mech. Anal. 206 (2012), no. 2, 617–643. MR 2980529

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

[CS07] Rustum Choksi and Peter Sternberg, On the first and second variations of a nonlocal isoperimetric problem, J. Reine Angew. Math. 611 (2007), 75–108. MR 2360604 (2008j:49062)

[DMN17] Anindya De, Elchanan Mossel, and Joe Neeman, Noise stability is computable and approximately low-dimensional, 32nd Computational Complexity Conference, LIPIcs. Leibniz Int. Proc. Inform., vol. 79, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017, pp. Art. No. 10, 11. MR 3691135

[DMN18] Anindya De, Elchanan Mossel, and Joe Neeman, Non interactive simulation of correlated distributions is decidable, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018 (Artur Czumaj, ed.), SIAM, 2018, pp. 2728–2746.

[FGRW12] Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, and Yi Wu, Agnostic learning of monomials by halfspaces is hard, SIAM J. Comput. 41 (2012), no. 6, 1558–1590. MR 3029261

[FJ95] Alan Frieze and Mark Jerrum, Improved approximation algorithms for MAX k-CUT and MAX BISECTION, Integer programming and combinatorial optimization (Copenhagen, 1995), Lecture Notes in Comput. Sci., vol. 920, Springer, Berlin, 1995, pp. 1–13. MR 1367967 (96i:90069)

[GKR18] Badih Ghazi, Pritish Kamath, and Prasad Raghavendra, Dimension reduction for polynomials over gaussian space and applications, 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, 2018, pp. 28:1–28:37.

[GW95] Michel X. Goemans and David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42 (1995), no. 6, 1115–1145. MR 1412228 (97g:90108)

[Hei14] Steven Heilman, Euclidean partitions optimizing noise stability, Electron. J. Probab. 19 (2014), no. 71, 37. MR 3256871

[Hei15] , Low correlation noise stability of symmetric sets, to appear, Journal of Theoretical Probability. Preprint, arXiv:1511.00382, 2015.

[Hei17] , Symmetric convex sets with minimal Gaussian surface area, to appear, American Journal of Mathematics. Preprint, arXiv:1705.06643., 2017.

[Hei18] , The structure of Gaussian minimal bubbles, to appear, Journal of Geometric Analysis. Preprint, arXiv:1805.10203, 2018.

[Hei19] , Stable Gaussian minimal bubbles, Preprint, arXiv:1901.03934, 2019.

[Hei20] Steven Heilman, Designing stable elections: A survey, to appear, Notices of the AMS. Preprint, arXiv:2006.05460, 2020.

[HL94] Qing Han and Fang-Hua Lin, Nodal sets of solutions of parabolic equations. II, Comm. Pure Appl. Math. 47 (1994), no. 9, 1219–1238. MR 1290401

[HMN16] Steven Heilman, Elchanan Mossel, and Joe Neeman, Standard simplices and pluralities are not the most noise stable, Israel Journal of Mathematics 213 (2016), no. 1, 33–53.

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

[HS89] Robert Hardt and Leon Simon, Nodal sets for solutions of elliptic equations, J. Differential Geom. 30 (1989), no. 2, 505–522. MR 1010169

[IM12] Marcus Isaksson and Elchanan Mossel, Maximally stable Gaussian partitions with discrete applications, Israel J. Math. 189 (2012), 347–396. MR 2931402

[Kho] Subhash Khot, Inapproximability of np-complete problems, discrete fourier analysis, and geometry, pp. 2676–2697.

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

[KM16] Subhash Khot and Dana Moshkovitz, Candidate hard unique game, Proceedings of the Fortyeighth Annual ACM Symposium on Theory of Computing, STOC ’16, ACM, 2016.

[KMS18] Subhash Khot, Dor Minzer, and Muli Safra, Pseudorandom sets in grassmann graph have nearperfect expansion, Electronic Colloquium on Computational Complexity (ECCC) 25 (2018), 6.

[Led01] Michel Ledoux, The concentration of measure phenomenon, Mathematical Surveys and Monographs, vol. 89, American Mathematical Society, Providence, RI, 2001. MR 1849347 (2003k:28019)

[Lin90] Fang-Hua Lin, A uniqueness theorem for parabolic equations, Comm. Pure Appl. Math. 43 (1990), no. 1, 127–136. MR 1024191

[MN18a] Emanuel Milman and Joe Neeman, The Gaussian double-bubble conjecture, Preprint, arXiv:1801.09296, 2018.

[MN18b] , The Gaussian multi-bubble conjecture, Preprint, arXiv:1805.10961, 2018.

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

[MR15] Matthew McGonagle and John Ross, The hyperplane is the only stable, smooth solution to the isoperimetric problem in Gaussian space, Geom. Dedicata 178 (2015), 277–296. MR 3397495

[O’D] Ryan O’Donnell, Social choice, computational complexity, gaussian geometry, and boolean func-

tions, In proceedings of the 2014 ICM.

[Ste70] Elias M. Stein, Singular integrals and differentiability properties of functions, Princeton Mathematical Series, No. 30, Princeton University Press, Princeton, N.J., 1970. MR 0290095 (44 #7280)

Department of Mathematics, University of Southern California, Los Angeles, CA 90089-2532

E-mail address: stevenmheilman@gmail.com
E-mail address: atarter@usc.edu