HYPERSTABLE SETS WITH VOTING AND ALGORITHMIC HARDNESS APPLICATIONS

STEVEN HEILMAN

Abstract. The noise stability of a Euclidean set A with correlation ρ is the probability that (X, Y) ∈ A × A, where X, Y are standard Gaussian random vectors with correlation ρ ∈ (0, 1). It is well-known that a Euclidean set of fixed Gaussian volume that maximizes noise stability must be a half space.

For a partition of Euclidean space into m > 2 parts each of Gaussian measure 1/m, it is still unknown what sets maximize the sum of their noise stabilities. In this work, we classify partitions maximizing noise stability that are also critical points for the derivative of noise stability with respect to ρ. We call a partition satisfying these conditions hyperstable. Uner the assumption that a maximizing partition is hyperstable, we prove:

• a (conditional) version of the Plurality is Stablest Conjecture for 3 or 4 candidates.

• a (conditional) sharp Unique Games Hardness result for MAX-m-CUT for m = 3 or 4 • a (conditional) version of the Propeller Conjecture of Khot and Naor for 4 sets.

We also show that a symmetric set that is hyperstable must be star-shaped.

For partitions of Euclidean space into m > 2 parts of fixed (but perhaps unequal) Gaussian measure, the hyperstable property can only be satisfied when all of the parts have Gaussian measure 1/m. So, as our main contribution, we have identified a possible strategy for proving the full Plurality is Stablest Conjecture and the full sharp hardness for MAXm-CUT: to prove both statements, it suffices to show that sets maximizing noise stability are hyperstable. This last point is crucial since any proof of the Plurality is Stablest Conjecture must use a property that is special to partitions of sets into equal measures, since the conjecture is false in the unequal measure case.

Contents

1. Introduction  2
2. Existence and Regularity  10
3. First and Second Variation  12
4. Noise Stability and the Calculus of Variations  13
5. Almost Eigenfunctions of the Second Variation  15
6. Symmetric Sets  19
7. Negative Correlation, Dimension Reduction  20
8. Bilinear Version: Dilation  25
9. One Set, Negative Correlation  29
References  31

Date: September 22, 2022. S. H. is Supported by NSF Grant CCF 1911216.

1. Introduction

The noise stability of a measurable set Ω ⊆ ℝ^{n+1} with correlation ρ is the probability that (X, Y) ∈ A × A, where X, Y are standard Gaussian random vectors with correlation ρ ∈ (−1, 1):

ℙ((X, Y) ∈ Ω × Ω),  (1)

where X = (X_{1}, …, X_{n+1}), Y = (Y_{1}, …, Y_{n+1}), and 𝔼X_{i}X_{j} = 𝔼Y_{i}Y_{j} = 1_{{i=j}} for all 1 ≤ i, j ≤ n + 1 and 𝔼X_{i}Y_{j} = ρ · 1_{{i=j}} for all 1 ≤ i, j ≤ n + 1.

The noise stability of a set could also be called its Gaussian heat content. Inequalities for noise stability have been investigated in many places, including [Bor85, Led94, MN15, Eld15, HT21, Hei21e]. Besides their intrinsic interest, noise stability inequalities have applications to social choice theory [KKMO07, MOO10, IM12], the Unique Games Conjecture in theoretical computer science [KKMO07, MOO10, KM16], to semidefinite programming algorithms such as MAX-CUT [KKMO07, IM12], to learning theory [FGRW12], information theory [DMN17, DMN18, HT22], etc. For some surveys on these and related topics, see [O’D, Kho, Hei21a].

A basic question, answered in [Bor85] is: which measurable Euclidean sets of fixed Gaussian volume maximizes noise stability? More generally, our primary question of interest will be: which partitions of Euclidean space of fixed Gaussian volumes maximize the sum of their noise stabilities [IM12]? This particular question was asked in [IM12]: it is the continuous version of the Plurality is Stablest Conjecture from social choice theory [KKMO07, MOO10, IM12]. Some “robust” statements of this kind have been investigated. It was shown in [HT21, Hei21e] that half spaces are the only local maximizers of the noise stability subject to a Gaussian volume constraint. That is, for any Ω ⊆ ℝ^{n+1}, if for any collection of measurable sets {Ω^{(s)}}_{s∈(−1,1)} with Ω^{(0)} = Ω and with constant Gaussian volume ℙ(X ∈ Ω^{(s)}) = ℙ(X ∈ Ω), ∀ s ∈ (−1, 1) such that

\frac{d}{ds}|_{s=0} ℙ((X, Y) ∈ Ω^{(s)} × Ω^{(s)}) = 0,

if we have

\frac{d^{2}}{ds^{2}} |_{s=0} ℙ((X, Y) ∈ Ω^{(s)} × Ω^{(s)}) ≤ 0,

then Ω must be a half space (i.e. the set of all points lying on one side of a hyperplane) (up to measure zero changes to Ω). Borell’s inequality follows as a Corollary [Bor85]: half spaces maximize noise stability among all Euclidean sets of fixed Gaussian volume. In fact, [Hei21e] also showed that sets close to half spaces nearly maximize noise stability, proving some cases of a Conjecture of Eldan [Eld15], following similar “robust” inequalities of [MN15, Eld15].

For partitions of Euclidean space with m > 2 fixed Gaussian volumes, an analogous characterization of local maxima should hold [IM12], though obtaining such a characterization requires the Gaussian volumes to be equal [HMN16]. That is, we let Ω_{1}, …, Ω_{m} ⊆ ℝ^{n+1} be a partition of Euclidean space into m sets such that ℙ(X ∈ Ω_{i}) = 1/m for all 1 ≤ i ≤ m. If for any collection of measurable sets {Ω_{i}^{(s)}}_{s∈(−1,1),1≤i≤m} with ∪_{i=1}^{m}Ω_{i}^{(s)} = ℝ^{n+1} for all s ∈ (−1, 1), Ω_{i}^{(0)} = Ω_{i} for all 1 ≤ i ≤ m and ℙ(X ∈ Ω_{i}^{(s)}) = 1/m for all 1 ≤ i ≤ m such that

\frac{d}{ds}|_{s=0} ∑_{i=1}^{m} ℙ((X, Y) ∈ Ω_{i}^{(s)} × Ω_{i}^{(s)}) = 0,

we have

\frac{d^{2}}{ds^{2}} |_{s=0} ∑_{i=1}^{m} ℙ((X, Y) ∈ Ω_{i}^{(s)} × Ω_{i}^{(s)}) ≤ 0,

then Ω_{1}, …, Ω_{m} should be cones over the regular simplex centered at the origin (up to measure zero changes to the sets). This conjecture is known as the Standard Simplex Conjecture [IM12], or the continuous version of the Plurality is Stablest Conjecture [KKMO07]. When m = 2, this conjecture has been proven: it is Borell’s inequality [Bor85] for a set of Gaussian measure 1/2. The only known result for m > 2 is the case m = 3 and ρ > 0 small, proven in [HT21].

Since the Gaussian measures we consider have a correlation parameter ρ ∈ (−1, 1), below we write ℙ_{ρ} in place of ℙ, to denote the dependence of the measure on ρ, when appropriate.

Definition 1.1 (Hyperstable Set). We say a measurable set Ω ⊆ ℝ^{n+1} is hyperstable for correlation parameter ρ ∈ (0, 1) if the following holds. For any collection of measurable sets {Ω^{(s)}}_{s∈(−1,1)} with constant Gaussian volume ℙ(X ∈ Ω^{(s)}) = ℙ(X ∈ Ω) ∀ s ∈ (−1, 1), such that Ω^{(0)} = Ω and such that

\frac{d}{ds}|_{s=0} ℙ((X, Y) ∈ Ω^{(s)} × Ω^{(s)}) = 0,

we have

\frac{d^{2}}{ds^{2}} |_{s=0} ℙ((X, Y) ∈ Ω^{(s)} × Ω^{(s)}) ≤ 0, and \frac{d^{2}}{ds dρ}|_{s=ρ=0} ℙ_{ρ}((X, Y) ∈ Ω^{(s)} × Ω^{(s)}) = 0.

In the case ρ ∈ (−1, 0), the inequality is reversed.

Definition 1.2 (Hyperstable Symmetric Set). We say a measurable set Ω ⊆ ℝ^{n+1} is a hyperstable symmetric set for correlation parameter ρ ∈ (0, 1) if the following holds. We have Ω = −Ω and for any collection of measurable sets {Ω^{(s)}}_{s∈(−1,1)} with constant Gaussian volume ℙ(X ∈ Ω^{(s)}) = ℙ(X ∈ Ω) ∀ s ∈ (−1, 1) such that Ω^{(0)} = Ω and such that

\frac{d}{ds}|_{s=0} ℙ((X, Y) ∈ Ω^{(s)} × Ω^{(s)}) = 0,

we have

\frac{d^{2}}{ds^{2}} |_{s=0} ℙ((X, Y) ∈ Ω^{(s)} × Ω^{(s)}) ≤ 0, and \frac{d^{2}}{ds dρ}|_{s=ρ=0} ℙ_{ρ}((X, Y) ∈ Ω^{(s)} × Ω^{(s)}) = 0.

In the case ρ ∈ (−1, 0), the inequality is reversed.

Definition 1.3 (Hyperstable Partition). We say that a partition of Euclidean space into measurable sets Ω_{1}, …, Ω_{m} ⊆ ℝ^{n+1} is hyperstable for correlation parameter ρ ∈ (0, 1) if the following holds. For any collection of measurable sets {Ω_{i}^{(s)}}_{s∈(−1,1),1≤i≤m} with ∪_{i=1}^{m}Ω_{i}^{(s)} = ℝ^{n+1} for all s ∈ (−1, 1), Ω_{i}^{(0)} = Ω_{i} for all 1 ≤ i ≤ m and ℙ(X ∈ Ω_{i}^{(s)}) = 1/m for all 1 ≤ i ≤ m such that

\frac{d}{ds}|_{s=0} ∑_{i=1}^{m} ℙ((X, Y) ∈ Ω_{i}^{(s)} × Ω_{i}^{(s)}) = 0,

we have

\frac{d^{2}}{ds^{2}} |_{s=0} ∑_{i=1}^{m} ℙ((X, Y) ∈ Ω_{i}^{(s)} ×Ω_{i}^{(s)}) ≤ 0, and \frac{d^{2}}{ds dρ}|_{s=ρ=0} ∑_{i=1}^{m} ℙ_{ρ}((X, Y) ∈ Ω_{i}^{(s)} ×Ω_{i}^{(s)}) = 0.

In the case ρ ∈ (−1, 0), the inequality is reversed.

Conjecture 1.4 (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 15 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.

1.1. Our Contribution. Our main contribution is a conditional proof of the continuous version of the Plurality is Stablest Conjecture 1.4 for m = 3 or m = 4 candidates.

Theorem 1.5 (Conditional Proof of Standard Simplex Conjecture). Let 3 ≤ m ≤ 4. Let ρ ∈ (0, 1). Let Ω_{1}, …, Ω_{m} ⊆ ℝ^{n+1} be a partition of Euclidean space with ℙ(X ∈ Ω_{i}) = 1/m for all 1 ≤ i ≤ m such that

∑_{i=1}^{m} ℙ_{ρ}((X, Y) ∈ Ω_{i} × Ω_{i}) ≥ ∑_{i=1}^{m} ℙ_{ρ}((X, Y) ∈ Θ_{i} × Θ_{i})

for all partitions Θ_{1}, …, Θ_{m} ⊆ ℝ^{n+1} with ℙ(X ∈ Θ_{i}) = 1/m for all 1 ≤ i ≤ m. Assume additionally that any Ω_{1}, …, Ω_{m} are hyperstable, as in Definition 1.3. Then Ω_{1}, …, Ω_{m} are the cones over a regular simplex centered at the origin.

We also prove a bilinear version of Theorem 1.5 (see Theorem 8.5 below), implying an analogue of Theorem 1.5 for negative ρ. The case of negative ρ then implies a (conditional) hardness result for MAX-m-CUT for m = 3 and m = 4 [IM12].

Theorem 1.6 (Conditional Proof of MAX-m-CUT Hardness). Let 3 ≤ m ≤ 4. Under the assumption of Theorem 1.5, the Frieze-Jerrum semidefinite program for MAX-m-CUT [FJ95] achieves the best possible quality of approximation in polynomial time, assuming the Unique Games Conjecture.

Since the Proof of Theorem 1.5 identifies all local maxima of the noise stability (assuming hyperstability of the optimal sets), we can conclude a conditional version of the related Propeller Conjecture of Khot and Naor for four sets. (The case of 3 sets follows from an elementary argument, and the case of 4 sets was proven using computer-assistance in [HMN16], though our result below avoids any computer assistance.)

Theorem 1.7 (Conditional Proof of Propeller Conjecture). Let 3 ≤ m ≤ 4. Let Ω_{1}, …, Ω_{m} ⊆ ℝ^{n+1} be a partition of Euclidean space with ℙ(X ∈ Ω_{i}) = 1/m for all 1 ≤ i ≤ m such that

∑_{i=1}^{m} ℙ((X, Y) ∈ Ω_{i} × Ω_{i}) ≥ ∑_{i=1}^{m} ℙ((X, Y) ∈ Θ_{i} × Θ_{i})

for all partitions Θ_{1}, …, Θ_{m} ⊆ ℝ^{n+1} with ℙ(X ∈ Θ_{i}) = 1/m for all 1 ≤ i ≤ m. Assume additionally that Ω_{1}, …, Ω_{m} are hyperstable, as in Definition 1.3. Then, for any partition A_{1}, …, A_{m} of ℝ^{n+1} into measurable sets,

∑_{i=1}^{m} ∥∫_{A_{i}} xγ_{n+1}(x) dx∥_{ℓ_{2}^{n+1}}^{2} ≤ \frac{9}{8π} .

And equality holds uniquely (up to rotations and measure zero changes) A′_{1}, A′_{2}, A′_{3} ⊆ ℝ^{2} are three 120 degree sectors centered at the origin, A_{i} = A′_{i} × ℝ^{n−1} for all 1 ≤ i ≤ 3, and A_{i} = ∅ for all 4 ≤ i ≤ m.

The restriction that m ≤ 4 in the above statements arises since we are presently unable to classify dilation-invariant hyperstable partitions when m ≥ 5. See Remark 8.4 for more on this difficulty.

Lastly, we can show that hyperstable symmetric cylinders are star-shaped. This result can be compared with an analogous Gaussian surface area result of [Hei22]. The latter (unconditional) result says that cylinders that are Gaussian minimal surfaces must be convex (or have a convex complement).

Theorem 1.8 (Symmetric Hyperstable Cylinders are Star-Shaped). Suppose Ω ⊆ ℝ^{n+1} is a symmetric hyperstable set and ∃ Ω_{0} ⊆ ℝ^{n} such that

Ω = Ω_{0} × ℝ.

Then Ω or Ω^{c} is star-shaped with respect to the origin.

1.2. Related Work: Level Sets of Caloric Functions and the “Matzoh ball soup” Problem. Let Ω ⊆ ℝ^{n+1} and let P_{t}1_{Ω} denote the heat flow applied to 1_{Ω} at time t > 0, i.e.

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

so that

\frac{∂}{∂t}P_{t}f(x) = ∑_{i=1}^{n+1} \frac{∂^{2}}{∂x_{i}^{2}} P_{t}f(x), ∀ t > 0, ∀ x ∈ ℝ^{n+1}.

Suppose Ω is a superlevel set of P_{t}1_{Ω}, for all t > 0 (that is, Ω = {x ∈ ℝ^{n+1} : P_{t}1_{Ω}(x) ≥ c} for some c = c(t) ∈ ℝ). It was then shown in [MS02] that Ω must be a ball (assuming a priori that Ω is compact, and it satisfies regularity assumptions: it satisfies an exterior sphere condition and an interior cone condition.) More generally, if Ω is bounded, if Ω satisfies an exterior sphere condition, and if D ⊆ Ω with \overline{D} ⊆ Ω, if ∂D satisfies an interior cone condition, and if D is a superlevel set of P_{t}1_{D} for all t > 0, then Ω must be a ball. This result of [MS02] solved the so-called “Matzoh Ball Soup Problem.”

There is an analogy with this problem and our hyperstable assumption for sets optimizing noise stability. If Ω maximizes noise stability ∫_{ℝ^{n+1}} 1_{Ω}(x)T_{ρ}1_{Ω}(x)γ_{n+1}(x) dx for fixed ρ > 0, then Ω is a superlevel set of T_{ρ}1_{ρ}, where T_{ρ} is the Ornstein-Uhlenbeck operator from (13). (See e.g. Lemma 3.2.) If Ω is also a critical point of \frac{d}{dη} |_{η=ρ} ∫_{ℝ^{n+1}} 1_{Ω}(x)T_{η}1_{Ω}(x)γ_{n+1}(x) dx,

then ∂Ω is also a level set of \frac{d}{dη} |_{η=ρ}T_{η}1_{Ω}(x), so that ∂Ω is a level set of T_{η}1_{Ω} as η converges

to ρ. This condition is analogous to that of [MS02], which requires a stronger assumption on the level set for all times t, rather than just an infinitesimal neighborhood of times.

1.3. Related Work: Self-Shrinkers for Mean Curvature Flow. Let Σ ⊆ ℝ^{n+1} be a compact C^{∞} smooth manifold. Assume that Σ is a self-shrinker, so that

H(x) = ⟨x, N(x)⟩,  ∀ x ∈ Σ.  (2)

Here N(x) is the exterior pointing unit normal vector to Σ at x and H(x) := div(N)(x) is the mean curvature of Σ at x. Self-shrinkers are of interest in the theory of mean curvature flows, since they are stationary under the flow. In their investigation of mean curvature flow [CM12], Colding and Minicozzi studied a maximal version of the Gaussian surface area of an n-dimensional C^{∞} hypersurface Σ in ℝ^{n+1}. They called this quantity

sup_{a>0,b∈ℝ^{n+1}} ∫_{Σ} a^{− \frac{n}{2}} γ_{n}((x − b)a^{−1/2})dx  (3)

the “entropy” of Σ. It turns out the self-shrinkers are critical points of the entropy functional [CM12]. More specifically, taking the second derivative of (3) when a = 0 and b = 1, one obtains − ∫_{Σ} f(x)Lf(x)γ_{n+1}(x) dx, where the operator L is defined on smooth compactly supported functions f on Σ:

L := Δ − ⟨x, ∇⟩ + ∥A∥^{2} + 1.  (4)

Here ∥A∥^{2} is the sum of the squares of all second order partial derivatives of the unit normal vector N at x. (That is, A is the second fundamental form.) Also, Δ is the Laplacian on Σ (the sum of repeated second derivatives), and ∇ is the gradient on Σ.

For self-shrinkers (2), it was a key insight of [CM12] that L has two distinct eigenspaces with positive eigenvalues. The first eigenspace has eigenvalue one. For any v ∈ ℝ^{n+1}, the function x ↦ ⟨v, N(x)⟩ satisfies

L⟨v, N⟩ = ⟨v, N⟩.  (5)

The second eigenspace has eigenvalue two. The function f(x) := ⟨x, N(x)⟩ satisfies

Lf = 2f.  (6)

We note in passing that the function x ↦ ⟨v, N(x)⟩ corresponds to an infinitesimal translation of the surface Σ, and the function x ↦ ⟨x, N(x)⟩ corresponds to an infinitesimal dilation of the surface Σ. Also, the eigenvalues written in [CM12] are half of those written here, since our Gaussian measure has an exponent that divides by 2 whereas theirs has a division by 4.

If H does not changes sign on Σ, then Σ satisfying (2) must be a round cylinder[Hui90]. If H changes sign on Σ, then ⟨x, N(x)⟩ changes sign on Σ. So (6) and Courant’s Nodal Domain theorem imply there is yet another eigenfunction of L with eigenvalue greater than 2, demonstrating that Σ is an unstable critical point for the functional (3). So, in either case, one can classify the compact smooth self-shrinkers that are stable critical points of the entropy (3) [CM12].

It was noted in [MR15] that, if the surface Σ satisfies the more general equation

H(x) = ⟨x, N(x)⟩ + λ,  ∀ x ∈ Σ  (7)

for some λ ∈ ℝ, then (5) still holds, but unfortunately (6) no longer holds [Hei21d, Lemma 4.1]. If f(x) := ⟨x, N(x)⟩ and if (7) holds, then

Lf = 2f + λ.  (8)

The realization that (7) implies (5) led [MR15] to classify half spaces as the only stable critical points of the Gaussian surface area functional. An analogous realization for partitions of Euclidean space was one crucial ingredient in the proofs of the Gaussian double bubble and multi-bubble conjecture [Hei21c, MN22, Hei19].

In our noise stability problem, there are analogues of (5) and (8) for a single set and for partitions of Euclidean space into multiple sets. For simplicity of exposition, we focus for now on one set. Since the Gaussian surface area functional can be obtained as an appropriate limit of noise stability [Led94], it is not unreasonable that one could generalize (5) and (8) to the setting of noise stability. However, it was not obvious how to obtain such a generalization, and it first appeared in [HT21, Hei21e]. To generalize (5) and (8), we replace the Colding-Minicozzi entropy functional (3) with the noise stability of a measurable Euclidean set Ω ⊆ ℝ^{n+1} with correlation 0 < ρ < 1:

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

(The Ornstein-Uhleneck operator T_{ρ} is defined in (13). Also, it is a standard exercise to show that (9) is equal to ℙ_{ρ}((XY) ∈ Ω × Ω), i.e. this definition agrees with our previous definition of noise stability (1).) When we take the second derivative of this functional, we obtain the quantity

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

where S is the second variation operator analogous to (4), defined for C^{∞} compactly supported functions f: Σ → ℝ.

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

For critical points Ω of the noise stability functional (9), if Σ := ∂Ω, then there is an analogue of (5):

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

In (5) there was an eigenvalue of 1, which has now become an eigenvalue of 1/ρ.

However, the analogy with (6) is imperfect. In the setting of Gaussian surface area, we know [CM12] that (2) implies (6). Yet, the assumption for noise stability that is analogous to (2) is unclear. Setting λ = 0 in (7) results in an eigenfunction in (8), and this is a key fact in [CM12]. Analogously, a critical point of noise stability satisfies T_{ρ}1_{Ω}(x) = c for all x ∈ ∂Ω (by Lemma 3.2), and there is no clear way to impose e.g. a constraint on c that results in a corresponding eigenfunction equation for the second variation operator S. As a remedy for this issue, below we will argue that the appropriate analogue of the condition (2) for noise stability is a hyperstable set.

A critical point of the Gaussian surface area functional satisfies (7) and the almosteigenfunction equation (8) holds. Similarly, a critical point Ω ⊆ ℝ^{n+1} of the noise stability functional satisfies the almost-eigenfunction equation (see (33) below)

S(f)(x) = \frac{1}{ρ^{2}} f(x)∥\overline{∇}T_{ρ}1_{Ω}(x)∥ + (\frac{1}{ρ^{2}} − 1)ρ\frac{d}{dρ}T_{ρ}1_{Ω}(x),  ∀ x ∈ Σ,  (10)

where f(x) := ⟨x, N(x)⟩. Without the derivative term on the right, this equation would say that f is an eigenfunction of S with eigenvalue 1/ρ^{2}. Similarly, when λ = 0 in (7), (8) says that f is an eigenfunction of L with eigenvalue 2. So, conditions guaranteeing that the derivative term in (10) are zero are analogous to the self-shrinker equation (2).

In summary, the hyperstability condition for the noise stability functional is a natural analogue of the self-shrinker condition (2) for the Colding-Minicozzi entropy (3).

1.4. 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.4 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.11 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}  (11)

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}⟩}.  (12)

We refer to any sets satisfying (12) 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}  (13)

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

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

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.9 (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 =^{(13)} (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.10 (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.

We can now state the continuous version of Conjecture 1.4.

Conjecture 1.11 (Standard Simplex Conjecture [IM12]). Let Ω_{1}, … Ω_{m} ⊆ ℝ^{n+1} maximize Problem 1.10. 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.11 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.11.

1.5. Plurality is Stablest Conjecture. As previously mentioned, the Standard Simplex Conjecture [IM12] stated in Conjecture 1.11 is essentially equivalent to the Plurality is Stablest Conjecture from Conjecture 1.4. After making several definitions, we state a formal version of Conjecture 1.4 as Conjecture 1.12 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}].  (15)

Let

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

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.4.

Conjecture 1.12 (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} + ε.

One main result of [HT21] is: ∃ ρ_{0} > 0 such that Conjecture 1.12 is true for m = 3 for all 0 < ρ < ρ_{0}, for all n ≥ 1. The only previously known case of Conjecture 1.12 was the following.

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

For an even more general version of Theorem 1.13, 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.6. Outline of the Proof of the Structure Theorem.

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}  (17)

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).  (18)

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.  (19)

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.10.

Lemma 2.4 (Regularity of a Maximizer). Let Ω_{1}, …, Ω_{m} ⊆ ℝ^{n+1} be the measurable sets maximizing Problem 1.10, 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.

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}.  (20)

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

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}  (21)

We can then rewrite the noise stability from Definition 1.9 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.  (22)

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

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

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

Theorem 3.3 (General Second Variation Formula, [CS07, Theorem 2.6]; also [Hei21b, 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 (19). 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, [Hei21c, 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,  (23)

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 (21). Let f: Σ → ℝ be continous and compactly supported. Then

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

4.1. Two Sets.

Lemma 4.4 (Volume Preserving Second Variation of Maximizers). Suppose Ω, Ω^{c} ⊆ ℝ^{n+1} maximize Problem 1.10 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.

(24)

Moreover,

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

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

Lemma 4.5 (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)

Lemma 4.6 (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.

5. Almost Eigenfunctions of the Second Variation

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 ∈ Σ.  (29)

The following Lemma was proven in [HT21, Lemma 5.1]. We reproduce that proof, since we require it below.

Lemma 5.1 (Key Lemma, m = 2, Translations as Almost Eigenfunctions). Let Ω, Ω^{c} ⊆ ℝ^{n+1} maximize Problem 1.10 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 (25) holds, i.e.

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

From Definition 13, 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

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

(31)

Therefore,

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

A priori finiteness of the above integrals was shown in [HT21, Remark 5.2] to follow from the divergence theorem.

Lemma 5.2 (Dilation as Almost Eigenfunction). Let Ω, Ω^{c} ⊆ ℝ^{n+1} maximize Problem 1.10 with m = 2. Then

\begin{matrix}S(⟨·, N⟩)(x) − ⟨x, N(x)⟩∥\overline{∇}T_{ρ}(1_{Ω})(x)∥ \\ = (\frac{1}{ρ^{2}} − 1)(⟨x, N(x)⟩ ∥\overline{∇}T_{ρ}(1_{Ω})(x)∥ + ρ\frac{d}{dρ}T_{ρ}(1_{Ω})(x)),  ∀ x ∈ Σ. \end{matrix} (33)

Proof. Taking the gradient and divergence of (13),

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

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

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

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

(34)

Applying the divergence theorem to the last equality in (34),

\begin{aligned}div\overline{∇}T_{ρ}1_{Ω}(x) & = (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2} \frac{−ρ^{2}}{1 − ρ^{2}} ∫_{Σ} ⟨(y − ρx), N(y)⟩e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy \\ & =^{(29)} −\frac{ρ^{2}}{1 − ρ^{2}} (S(⟨·, N⟩)(x) − ρ⟨x, S(N)(x)⟩) \\ & =^{(32)} −\frac{ρ^{2}}{1 − ρ^{2}} (S(⟨·, N⟩)(x) − ⟨x, N(x)⟩ ∥∇T_{ρ}1_{Ω}(x)∥ ). \end{aligned} (35)

This equation and (30) proves (33), together with

div\overline{∇}T_{ρ}1_{Ω}(x) = \overline{Δ}T_{ρ}1_{Ω}(x) − ⟨x, ∇T_{ρ}1_{Ω}(x) + ⟨x, \overline{∇}T_{ρ}1_{Ω}(x)⟩

=^{(14)∧(30)} −ρ\frac{d}{dρ}T_{ρ}1_{Ω}(x) − ⟨x, N(x)⟩∥\overline{∇}T_{ρ}1_{Ω}(x)∥.

□

A priori finiteness of the above integrals will be shown in Remark 5.6 below.

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}.

(36)

Lemma 5.3 (Key Lemma, m ≥ 2, Translations as Almost Eigenfunctions, [HT21, Lemma 5.4]). Let Ω_{1}, …, Ω_{m} ⊆ ℝ^{n+1} maximize Problem 1.10. 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}.

Lemma 5.4 (Second Variation of Translations, Multiple Sets, [HT21, Lemma 5.5]). Let v ∈ ℝ^{n+1}. Let Ω_{1}, …, Ω_{m} ⊆ ℝ^{n+1} maximize Problem 1.10. 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.

Lemma 5.5 (Dilation as Almost Eigenfunction). Let Ω_{1}, …, Ω_{m} ⊆ ℝ^{n+1} maximize Problem 1.10. Then for all 1 ≤ i, j ≤ m,

S_{ij}(⟨·, N⟩)(x) − ⟨x, N_{ij}(x)⟩∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥

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

(37)

Proof. From (28), for all 1 ≤ i, j ≤ m,

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

Taking the divergence of (38), for all 1 ≤ i, j ≤ m,

div\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) = −div(N_{ij}(x)) ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥

− ⟨N_{ij}(x), \overline{∇} ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥⟩. (39)

Taking the gradient and divergence of (13),

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

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

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

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

(40)

Applying the divergence theorem to the last equality in (40),

div\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)

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

=^{(36)} −\frac{ρ^{2}}{1 − ρ^{2}} (S_{ij}(⟨·, N⟩)(x) − ρ⟨x, S_{ij}(N)(x)⟩)

=^{(38)∧(31)} −\frac{ρ^{2}}{1 − ρ^{2}} (S_{ij}(⟨·, N⟩)(x) − ⟨x, N_{ij}(x)⟩ ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})∥ ).

(41)

This equation and (39) proves (37), together with

div\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)

= \overline{Δ}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) − ⟨x, ∇T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)⟩ + ⟨x, \overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)⟩

=^{(14)∧(38)} −ρ\frac{d}{dρ}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) − ⟨x, N_{ij}(x)⟩∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥.

□

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

\begin{aligned}\overline{∇}T_{ρ}1_{Ω∩B(0,r)}(x) & = (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2} ∫_{Ω∩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)}(y − ρx)e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy \end{aligned} (42)

div\overline{∇}T_{ρ}1_{Ω∩B(0,r)}(x)

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

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

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

(43)

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

|div\overline{∇}T_{ρ}1_{Ω}(x) − div\overline{∇}T_{ρ}1_{Ω∩B(0,r)}(x)|

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

≤ (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2} ∫_{B(0,r)^{c}} (ρ^{2} \frac{∥y − ρx∥^{2}}{(1 − ρ^{2})^{2}} + (n + 1)\frac{ρ^{2}}{1 − ρ^{2}} )e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy.

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

6. Symmetric Sets

Proof of Theorem 1.8. Consider the functions f, g: Σ → ℝ defined by

g(x) := ⟨x, N(x)⟩, ∀ x ∈ Σ.
f(x) := (x_{n+1}^{2} − 1)g(x), ∀ x ∈ Σ.

Note that ⟨x, N(x)⟩ is constant as x_{n+1} varies, and (x_{n+1}^{2} − 1) is constant as x_{1}, …, x_{n} varies. We can therefore apply Fubini’s Theorem when we compute S(f), and also note that ∫_{Σ} f(x)γ_{n+1}(x) dx = 0 since ∫_{ℝ}(x_{n+1}^{2} − 1)γ_{1}(x_{n+1}) dx_{n+1} = 0. From (29), and using the well-known property of Hermite polynomials on the real line that T_{ρ}(x_{1}^{2} − 1) = ρ^{2}(x_{1}^{2} − 1) for all x_{1} ∈ ℝ, we have

S(f)(x) = ρ^{2}(x_{n+1}^{2} − 1)S(g)(x), ∀ x ∈ Σ.

From Lemma 5.2,

S(g)(x) = \frac{1}{ρ^{2}} g(x)∥\overline{∇}T_{ρ}1_{Ω}(x)∥ + ρ(1 − ρ^{2})\frac{d}{dρ}T_{ρ}(1_{Ω})(x),  ∀ x ∈ Σ.  (44)

Plugging this into Lemma 4.4, and using also ∫_{ℝ}(x_{n+1}^{2} − 1)^{2}γ_{1}(x_{n+1}) dx_{n+1} = 1 and that ∥\overline{∇}T_{ρ}1_{Ω}(x)∥ is constant as x_{n+1} varies, the variation of \{Ω^{(s)}\}_{s∈(−1,1)} corresponding to this choice of f satisfies

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

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

= ∫_{Σ} (ρ^{2}g(x)S(g)(x) − |g(x)|^{2} ∥\overline{∇}T_{ρ}1_{Ω}(x)∥))γ_{n+1}(x) dx

=^{(44)} ρ^{3}(1 − ρ^{2}) ∫_{Σ} \frac{d}{dρ}T_{ρ}(1_{Ω})(x)⟨x, N(x)⟩γ_{n+1}(x) dx ≥ 0.

(45)

The last inequality follows by assumption. Now, consider the function

f̃(x) := (x_{n+1}^{2} − 1) |⟨x, N(x)⟩| , ∀ x ∈ Σ.

If Ω is not star shaped, then since G(x, y) > 0 for all x, y ∈ ℝ^{n+1}, we have a strict inequality

∫_{Σ} |g(x)| S(|g|)(x)γ_{n+1}(x) dx =^{(29)} ∫_{Σ} ∫_{Σ} |g(x)| G(x, y) |g(y)| dxdy

> ∫_{Σ} ∫_{Σ} g(x)G(x, y)g(y) dxdy =^{(29)} ∫_{Σ} gS(g)(x)γ_{n+1}(x) dx.

(46)

So, the variation of {Ω^{(s)}}_{s∈(−1,1)} corresponding to this choice of f̃ satisfies,

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

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

= ∫_{Σ} (ρ^{2} |g(x)| S(|g|)(x) − |g(x)|^{2} ∥\overline{∇}T_{ρ}1_{Ω}(x)∥)γ_{n+1}(x) dx

>^{(46)} ∫_{Σ} (ρ^{2}g(x)S(g)(x) − |g(x)|^{2} ∥\overline{∇}T_{ρ}1_{Ω}(x)∥)γ_{n+1}(x) dx ≥^{(45)} 0.

Since we have found a variation f̃ with positive second derivative, ∫_{Σ} f̃(x)γ_{n+1}(x) dx = 0, and f̃(−x) = f̃(x) for all x ∈ Σ, we have arrived at a contradiction. We conclude that Ω or Ω^{c} is star-shaped. □

7. Negative Correlation, Dimension Reduction

In this section, we consider the case that ρ < 0 in Problem 1.10. 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 (13) 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, Equal Measure Constraint). Let m ≥ 3. 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}) 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.

We remark that even the case m = 2 of this bilinear problem is interesting, as it played a role in [CR11] in proving an optimal lower bound for the Gap-Hamming-Distance problem in communication complexity. However, the problem relevant to [CR11] also requires an extra symmetry assumption.

Conjecture 7.2 (Standard Simplex Conjecture, Bilinear Version, Positive Correlation [IM12]). Let Ω_{1}, … Ω_{m}, Ω′_{1}, … Ω′_{m} ⊆ ℝ^{n+1} minimize Problem 1.10. 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, for all 1 ≤ i ≤ m,

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

Since we consider a bilinear version of noise stability in Problem 7.1, existence of an optimizer is easier than in Problem 1.10.

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 (16). Let f, g: ℝ^{n+1} → Δ_{m}. The set D_{0} := {(f, g): f, g: ℝ^{n+1} → Δ_{m}, ∫_{ℝ^{n+1}} f(x)γ_{n+1} dx = ∫_{ℝ^{n+1}} g(x)γ_{n+1} dx} 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}, and D_{0} is weakly compact, so there exists (f̃, g̃) ∈ D_{0} such that C(f̃, g̃) = min_{f,g∈D_{0}} 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}. (If e.g. g is fixed, then f ↦ C(f, g) is linear in f, and {f: (f, g) ∈ D_{0}} is a convex set.) 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.10, 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.

(47)

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}. (48)

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 (48) 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 (47) is zero. Then, choose Y such that sum of the first two terms in (47) is negative. Multiplying then X by a small positive constant, and noting that the fourth term in (47) 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 (48) (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π)^{− \frac{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π)^{− \frac{n+1}{2}} ( ∫_{∂Ω′_{i}} − ∫_{∂Ω′_{j}} )⟨v, N′(y)⟩e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy, ∀ x ∈ Σ_{ij}.

(49)

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

\begin{aligned}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}. \end{aligned}  (50)

When compared to Lemma 5.3, Lemma 7.7 has a negative sign on the right side of the equality, resulting from the positive sign in (48) (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.10. 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.4 was \frac{1}{ρ} − 1 > 0.) The following Theorem is a modification of the corresponding [HT21, Theorem 7.9]. In [HT21], the main dimension reduction result in the case of negative correlation obtained a sub-optimal dimension by restricting both γ_{n+1}(Ω_{i}) and γ_{n+1}(Ω′_{i}) for all 1 ≤ i ≤ m. Here we obtain the optimal dimension dependence (concluding that the Θ sets below are contained in ℝ^{m−1}, which is optimal), by instead imposing the restriction that γ_{n+1}(Ω_{i}) = γ_{n+1}(Ω′_{i}) for all 1 ≤ i ≤ m. In fact, the argument below seems to work with arbitrary linear constraints on the measures of the sets Ω_{i} and Ω′_{i}.

Theorem 7.9 (Main Structure Theorem/ Dimension Reduction, Negative Correlation). Fix 0 < ρ < 1. Let m ≥ 2 with m ≤ n + 2. Let Ω_{1}, … Ω_{m}, Ω′_{1}, … Ω′_{m} ⊆ ℝ^{n+1} minimize Problem 7.1 (that exist by Lemma 7.3). 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} ⊆ ℝ^{m−1} such that,

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

Proof. The sets Ω_{1}, … Ω_{m}, Ω′_{1}, … Ω′_{m} ⊆ ℝ^{n+1} with γ_{n+1}(Ω_{i}) = γ_{n+1}(Ω′_{i}) for all 1 ≤ i ≤ m that minimize Problem 1.10 exist by Lemma 7.3. From Lemma 7.4 their boundaries are locally finite unions of C^{∞} n-dimensional manifolds.

By Lemma 7.5, 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}.

By this condition, the regularity Lemma 7.4, and the last part of Lemma 7.6,

\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}.

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

\begin{aligned}∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥ & > 0,  ∀ x ∈ Σ′_{ij} \ σ′_{ij}. \\ ∥\overline{∇}T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x)∥ & > 0,  ∀ x ∈ Σ_{ij} \ σ_{ij}. \end{aligned}  (51)

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

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

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

From Lemma 7.8,

v ∈ V ⟹ \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, (51) implies

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

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 − ∫_{Σ_{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 (52), after rotating Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m}, we conclude ∃ measurable Θ_{1}, …, Θ_{m}, Θ′_{1}, …, Θ′_{m} ⊆ ℝ^{m−1} such that

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

8. Bilinear Version: Dilation

Lemma 8.1 (Dilation as Almost Eigenfunction). Let Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} ⊆ ℝ^{n+1} minimize Problem 7.1. Then for all 1 ≤ i, j ≤ m,

S_{ij}(⟨·, N⟩)(x) + ⟨x, N′_{ij}(x)⟩∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥

= (\frac{1}{ρ^{2}} − 1)( − ⟨x, N′_{ij}(x)⟩ ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥ + ρ\frac{d}{dρ}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)), ∀ x ∈ Σ′_{ij}.

(53)

S′_{ij}(⟨·, N′⟩)(x) + ⟨x, N_{ij}(x)⟩∥\overline{∇}T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x)∥

= (\frac{1}{ρ^{2}} − 1)( − ⟨x, N_{ij}(x)⟩∥\overline{∇}T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x)∥ + ρ\frac{d}{dρ}T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x)), ∀ x ∈ Σ_{ij}.

(54)

Proof. We prove (53). From (48), for all 1 ≤ i, j ≤ m,

\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}. (55)

Taking the divergence of (55), for all 1 ≤ i, j ≤ m,

div\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) = div(N′_{ij}(x)) ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥

⟨N′_{ij}(x), \overline{∇} ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥⟩. (56)

Applying the divergence theorem to the last equality in (40),

div\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)

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

=^{(49)} −\frac{ρ^{2}}{1 − ρ^{2}} (S_{ij}(⟨·, N⟩)(x) − ρ⟨x, S_{ij}(N)(x)⟩)

=^{(50)} −\frac{ρ^{2}}{1 − ρ^{2}} (S_{ij}(⟨·, N⟩)(x) + ⟨x, N′_{ij}(x)⟩ ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})∥ ).

(57)

This equation and (56) proves (53), together with

div\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)

= \overline{Δ}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) − ⟨x, ∇T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)⟩ + ⟨x, \overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)⟩

=^{(14)∧(55)} −ρ\frac{d}{dρ}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x) + ⟨x, N′_{ij}(x)⟩∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥.

Equation (54) is proven analogously. A priori finiteness follows from Remark 5.6. □

Using the dilation as an eigenfunction for hyperstable sets implies that those sets are dilation invariant.

Lemma 8.2 (Hyperstable Implies Dilation Invariance). Let Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} ⊆ ℝ^{n+1} minimize Problem 7.1. Assume ∃ measurable Θ_{1}, …, Θ_{m}, Θ′_{1}, …, Θ′_{m} ⊆ ℝ^{m−1} such that

Ω_{i} = Θ_{i} × ℝ, Ω′_{i} = Θ′_{i} × ℝ ∀ 1 ≤ i ≤ m.

Assume also that

∑_{1≤i<j≤m} [ ∫_{Σ′_{ij}}⟨x, N′_{ij}(x)⟩\frac{d}{dρ}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)γ_{n+1}(x) dx

+ ∫_{Σ_{ij}}⟨x, N_{ij}(x)⟩\frac{d}{dρ}T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x)γ_{n+1}(x) dx] ≤ 0.

Then Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} are dilation invariant. That is,

tΩ_{i} = Ω_{i},  tΩ′_{i} = Ω′_{i},  ∀ t > 0 ∀ 1 ≤ i ≤ m.

Proof. Consider the vector field X: ℝ^{n+1} → ℝ defined by

X(x) := x_{n+1} · x, ∀ x ∈ ℝ^{n+1}.

Note that ⟨X, N_{ij}(x)⟩ and ⟨X, N′_{ij}(x)⟩ is constant as x_{n+1} varies, and x_{n+1} is constant as x_{1}, …, x_{n} varies. We can therefore apply Fubini’s Theorem when we apply S_{ij} and S′_{ij} to the variation corresponding to X, and also note that ∫_{∂^{∗}Ω_{i}}⟨X(x), N(x)⟩γ_{n+1}(x) dx = 0 and ∫_{∂^{∗}Ω′_{i}}⟨X(x), N′(x)⟩γ_{n+1}(x) dx = 0 for all 1 ≤ i ≤ m since ∫_{ℝ} x_{n+1}γ_{1}(x_{n+1}) dx_{n+1} = 0. From (49), and using the well-known property of Hermite polynomials on the real line that T_{ρ}x_{1} = ρx_{1} for all x_{1} ∈ ℝ, we have for all 1 ≤ i, j ≤ m,

S_{ij}(⟨X, N⟩)(x) = ρx_{n+1}S_{ij}(⟨·, N(·)⟩)(x),  ∀ x ∈ Σ′_{ij}.
S′_{ij}(⟨X, N′⟩)(x) = ρx_{n+1}S_{ij}(⟨·, N′(·)⟩)(x),  ∀ x ∈ Σ_{ij}.

Combining this with Lemma 8.1, for all 1 ≤ i, j ≤ m,

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

(58)

Combining these facts and Lemma 7.6, and using also ∫_{ℝ} x_{n+1}^{2}γ_{1}(x_{n+1}) dx_{n+1} = 1 and that ∥\overline{∇}T_{ρ}1_{Ω}(x)∥ is constant as x_{n+1} varies, the variation of \{Ω_{i}^{(s)}\}_{s∈(−1,1)}, \{Ω_{i}^{′(s)}\}_{s∈(−1,1)} corresponding to this choice of X satisfies

\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}} (S_{ij}(⟨X, N⟩)(x)f′_{ij}(x) + ∥\overline{∇}T_{ρ}(1_{Ω_{i}} − 1_{Ω_{j}})(x)∥(f′_{ij}(x))^{2}) dx

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

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

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

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

+ ∫_{Σ_{ij}}⟨x, N_{ij}(x)⟩\frac{d}{dρ}T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x)γ_{n+1}(x) dx].

(59)

By assumption, the last quantity is nonpositive. By the minimization property of the sets Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m}, we have

\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 ≥ 0.

In order for this inequality to be true, since 0 < ρ < 1, 1 − (1/ρ) < 0, we must have

⟨x, N′_{ij}(x)⟩ = 0, ∀ x ∈ Σ′_{ij}, ∀ 1 ≤ i < j ≤ m.
⟨x, N_{ij}(x)⟩ = 0, ∀ x ∈ Σ_{ij}, ∀ 1 ≤ i < j ≤ m.

That is, the sets Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} are dilation invariant. □

Lemma 8.3 (Dilation Invariance Implies Simplicial). Let m ≤ 4. Assume that Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} ⊆ ℝ^{m} are dilation invariant partitions and hyperstable, so that

tΩ_{i} = Ω_{i},  tΩ′_{i} = Ω′_{i},  ∀ t > 0 ∀ 1 ≤ i ≤ m.

Then Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} are congruent, regular simplicial cones.

Proof. Case of Dimension One. If it occurs that Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} ⊆ ℝ, then dilation invariance implies that two of the sets Ω_{1}, …, Ω_{m} are opposing half lines and the rest of these sets are empty. Similarly, two of the sets Ω′_{1}, …, Ω′_{m} are opposing half lines and the rest are empty. Up to relabeling the sets, there are only two possibly configurations of the partitions, namely

Ω_{1} = (−∞, 0], Ω_{2} = (0, ∞), Ω′_{1} = (−∞, 0], Ω′_{2} = (0, ∞), or
Ω_{1} = (−∞, 0], Ω_{2} = (0, ∞), Ω′_{1} = (0, ∞), Ω′_{2} = (−∞, 0].

The latter case has smaller noise stability than the former case, so the latter case completes the proof when the sets are all contained in ℝ.

Case of m = 2 sets. By Theorem 7.9, we may assume that Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} ⊆ ℝ, so the proof is completed by the previous case.

Case of m = 3 Sets. By Theorem 7.9, we may assume that Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} ⊆ ℝ^{2}. Dilation Invariance of these sets implies that each set is a finite union of sectors, and for any 1 ≤ i < j ≤ m, (∂Ω_{i})∩(∂Ω_{j}) is a union of half-lines emanating from the origin (and similarly for (∂Ω′_{i}) ∩ (∂Ω′_{j}).) For some fixed 1 ≤ i < j ≤ m, let L′ be a half line in (∂Ω_{i}) ∩ (∂Ω_{j}) and consider the function T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x) where x varies in the line L containing L′. The First Variation condition in Lemma 7.5 implies that T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x) is constant on the half line L′. In particular, we have by dilation invariance and (13),

γ_{2}(Ω′_{i}) − γ_{2}(Ω′_{j}) = T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(0).  (60)

Also, as x ∈ L′ tends to infinity, since Ω′_{i} and Ω′_{j} are finite unions of sectors, we have

lim_{x∈L′, ∥x∥→∞} T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x) ∈ {0, 1}.

If this limit is 1, then (60) is violated. We conclude that

lim_{x∈L′, ∥x∥→∞} T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x) = 0.  (61)

Then (60) is also equal to zero since T_{ρ}(1_{Ω′_{i}} −1_{Ω′_{j}})(x) is constant for all x ∈ L′. Consequently, either γ_{2}(Ω_{i}) = γ_{2}(Ω′_{i}) = 1/3 for all 1 ≤ i ≤ 3, or some Ω_{i} and Ω′_{j} are empty, in which case we return to the previous m = 2 case.

So, for the remainder of the proof, we may assume that

γ_{2}(Ω_{i}) = γ_{2}(Ω′_{i}) = 1/3, ∀ 1 ≤ i ≤ 3.

Since Ω′_{i} and Ω′_{j} are finite unions of sectors, in order to have T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x) = 0 for all x in the half line L′, it must be the case that Ω′_{i} is the reflection of Ω′_{j} across L′. Therefore, with 1 ≤ i < j ≤ m fixed, let A′_{ij} denote the group of all such reflections that interchange Ω′_{i} and Ω′_{j}. (If A′_{ij} is empty, then Ω_{i} ∩Ω_{j} = ∅.) If A′_{ij} is nonempty with more than two elements, then the composition of two distinct reflections is a rotation of Ω′_{i} that fixes Ω′_{i}. Since Ω′_{i} is invariant under a non-identity rotation, we conclude that ∫_{Ω′_{i}} xγ_{2}(x) dx = 0. Lemma 7.8 then implies that we can reduce back to the dimension one case.

Having ruled out the cases that A′_{ij} is empty or it has more than two elements, we are left with the case that A′_{ij} has exactly two elements (i.e. the identity and one reflection). That is, we assume for all 1 ≤ i < j ≤ 3, Ω′_{i} ∩ Ω′_{j} is either a single half line, or a pair of parallel half lines. The latter case implies that ∫_{Ω′_{i}} xγ_{2}(x) dx = 0. The former case implies that Ω′_{1}, …, Ω′_{3} are three 120 degree sectors.

The case m = 3 is therefore concluded.

Case of m = 4 Sets. By Theorem 7.9, we may assume that Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} ⊆ ℝ^{3}. As in the m = 3 case, we may deduce that

γ_{3}(Ω_{i}) = γ_{3}(Ω′_{i}) = 1/4, ∀ 1 ≤ i ≤ 4.

As in the m = 3 case, in order to have T_{ρ}(1_{Ω′_{i}} −1_{Ω′_{j}})(x) = 0 for all x in the boundary between Ω′_{i} and Ω′_{j}, it must be the case that Ω′_{i} is the reflection of Ω′_{j} across a plane containing a part of this boundary.

For any 1 ≤ i < j ≤ m fixed, let A′_{ij} denote the group of all such reflections that interchange Ω′_{i} and Ω′_{j}. (If A′_{ij} is empty, then Ω_{i}∩Ω_{j} = ∅.) If A′_{ij} is nonempty with more than two elements, then the composition of two distinct reflections is a rotation of Ω′_{i} that fixes Ω′_{i}. Since Ω′_{i} is invariant under a non-identity rotation, we conclude that ∫_{Ω′_{i}} xγ_{2}(x) dx = 0. Lemma 7.8 then implies that we can reduce to the dimension two case. The dimension two case then proceeds as in the m = 3 case.

Having ruled out the cases that A′_{ij} is empty or it has more than two elements, we are left with the case that A′_{ij} has exactly two elements (i.e. the identity and one reflection). That is, we assume for all 1 ≤ i < j ≤ 4, Ω′_{i} ∩ Ω′_{j} is a disc sector. We then conclude that Ω′_{1}, …, Ω′_{4} are congruent regular tetrahedral cones. (Since T_{ρ}(1_{Ω′_{i}} − 1_{Ω′_{j}})(x) = 0 for all x in the boundary between Ω′_{i} and Ω′_{j}, if we particularly choose a line that is the intersection of three of the sets, then it must be the case that the three sets meet at 120 degree angles.)

□

Remark 8.4. When m ≥ 5, unlike in the case m ≤ 4, there seems to be no simple a priori reason that the interfaces between the sets Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} ⊆ ℝ^{n+1} are flat. We expect this should be true, but we cannot presently prove it.

Lemmas 8.2 and 8.3 together imply the following, which is a restatement of Theorem 1.5.

Theorem 8.5. Let m ≤ 4. Suppose Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} ⊆ ℝ^{n+1} minimize Problem 7.1 and these partitions are hyperstable. Then Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} are congruent, regular simplicial cones.

9. One Set, Negative Correlation

Here we single out the case that m = 2 for negative correlation, since this case can be solved exactly. This case follows from Borell’s inequality, but a variational proof of this inequality has not been given before. In the positive correlation case, this proof appeared already in [HT21, Hei21e], but some small changes are needed to solve the negative correlation case. In particular, we only impose the constraint that both sets have the same measure, without further constraining what that measure could be. Such a constraint is most natural for applications to hardness of the MAX-CUT problem [KKMO07, IM12].

Problem 7.1 in the case m = 2 can be restated in the following way.

Problem 9.1. Let Ω, Ω′ ⊆ ℝ^{n+1} be measurable sets minimizing

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

subject to the constraint that γ_{n+1}(Ω) = γ_{n+1}(Ω′).

Theorem 7.9 says that we may assume that Ω, Ω′ ⊆ ℝ in order to solve Problem 9.1. Since Ω_{1} = Ω and Ω_{2} = Ω^{c}, Equation 49 can be simplified to

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

Then (50) says

\begin{aligned}S(⟨v, N⟩)(x) & = −⟨v, N′(x)⟩\frac{1}{ρ}∥2\overline{∇}T_{ρ}(1_{Ω})(x)∥,  ∀ x ∈ Σ′. \\ S′(⟨v, N′⟩)(x) & = −⟨v, N(x)⟩\frac{1}{ρ}∥2\overline{∇}T_{ρ}(1_{Ω′})(x)∥,  ∀ x ∈ Σ. \end{aligned}  (63)

Plugging this into Lemma 7.6, we get

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

= ∫_{Σ′} S(f)(x) · f′(x)γ_{n+1}(x) dx + ∫_{Σ} S′(f′)(x) · f(x)γ_{n+1}(x) dx

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

(64)

Definition 9.2. A pair of sets Ω, Ω′ ⊆ ℝ^{n+1} is called locally stable for noise stability for negative correlation if, for any family of pairs of sets {Ω_{s}}_{s∈(−1,1)}, {Ω′_{s}}_{s∈(−1,1)} with Ω_{0} = Ω, Ω′_{0} = Ω′ such that

\frac{d}{ds}|_{s=0}γ_{n+1}(Ω_{s}) = \frac{d}{ds}|_{s=0}γ_{n+1}(Ω′_{s}),

we have

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

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

We say two (open) half spaces are opposing if their intersection is either empty or the boundary of this intersection is exactly two parallel hyperplanes.

Corollary 9.3. Opposing half spaces are the only locally stable sets for noise stability for negative correlation.

An analogous statement for positive correlation was shown in [Hei21e].

Proof. Suppose without loss of generality that Ω ⊆ ℝ^{n+1} is not a half space. Then we have by definition (29) of S the following strict inequality

∫_{Σ′} S(− |⟨v, N⟩|)(x) · |⟨v, N′(x)⟩| γ_{n+1}(x) dx < ∫_{Σ′} S(⟨v, N⟩)(x) · ⟨v, N(x)⟩γ_{n+1}(x) dx. (65)

(If we do not multiply the right by −1, the left is positive and the right is negative, so it is necessary to multiply by −1 on the left to get the correct inequality.) In the case that Ω = Ω′ × ℝ (which we can assume by the Dimension Reduction Theorem 7.9), consider the functions g(x) := −x_{n+1} |⟨v, N(x)⟩| defined on Σ and g′(x) := x_{n+1} |⟨v, N(x)⟩| defined on Σ′. Then

∫_{Σ′} (S(−g)(x) + ∥2\overline{∇}T_{ρ}1_{Ω}(x)∥g′(x))g′(x)γ_{n+1}(x) dx

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

<^{(65)} ∫_{Σ′} (ρS(⟨v, N⟩)(x) + ∥2\overline{∇}T_{ρ}1_{Ω}(x)∥⟨v, N′(x)⟩)⟨v, N′(x)⟩γ_{n+1}(x) dx =^{(63)} 0.

Similarly, we have a (possibly strict) inequality for integrating on Σ:

∫_{Σ} (S′(g′)(x) − ∥2\overline{∇}T_{ρ}1_{Ω}(x)∥g(x))g(x)γ_{n+1}(x) dx

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

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

So, ∫_{Σ} g(x)γ_{n+1}(x) dx = ∫_{Σ′} g′(x)γ_{n+1}(x) dx = 0 while the corresponding variation of g, g′ satisfies

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

That is, the half space is the only stable maximum of noise stability. More specifically, both Ω and Ω′ are half spaces. A two-case comparison shows that the noise stability is larger when one half space contains the other, and smaller when one half space does not contain the other. □

References

[Bor85] Christer Borell, Geometric bounds on the Ornstein-Uhlenbeck velocity process, Z. Wahrsch. Verw. Gebiete 70 (1985), no. 1, 1–13. MR 795785 (87k:60103)

[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 [CR11] Amit Chakrabarti and Oded Regev, An optimal lower bound on the communication complexity

of gap Hamming distance, Proc. 43rd Annual ACM Symposium on the Theory of Computing, 2011, pp. 51–60.

[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.

[Eld15] Ronen Eldan, A two-sided estimate for the gaussian noise stability deficit, Inventiones mathematicae 201 (2015), no. 2, 561–624 (English).

[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)

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

[Hei21a] , Designing stable elections, Notices Amer. Math. Soc. 68 (2021), no. 4, 516–527. MR 4228125

[Hei21b] , Low correlation noise stability of symmetric sets, Journal of Theoretical Probability 34 (2021), 2192–2240.

[Hei21c] , The structure of Gaussian minimal bubbles, Journal of Geometric Analysis 31 (2021), no. 6, 6307–6348.

[Hei21d] , Symmetric convex sets with minimal Gaussian surface area, Amer. J. Math. 143 (2021), no. 1, 53–94. MR 4201779

[Hei21e] , A variational proof of robust gaussian noise stability, Preprint, arXiv:2108.04950, 2021.

[Hei22] , Convex cylinders and the symmetric gaussian isoperimetric problem, Preprint, arXiv:2204.12003, 2022.

[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.

[HT21] Steven Heilman and Alex Tarter, Three candidate plurality is stablest for small correlations, Forum of Mathematics, Sigma 9 (2021), e65.

[HT22] Steven Heilman and Alex Tarter, Dimension-free noninteractive simulation from Gaussian sources, Preprint, arXiv:2202.09309, 2022.

[Hui90] Gerhard Huisken, Asymptotic behavior for singularities of the mean curvature flow, J. Differential Geom. 31 (1990), no. 1, 285–299. MR 1030675

[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.

[Led94] Michel Ledoux, Semigroup proofs of the isoperimetric inequality in Euclidean and Gauss space, Bull. Sci. Math. 118 (1994), no. 6, 485–510. MR 1309086 (96c:49061)

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

[MN15] Elchanan Mossel and Joe Neeman, Robust optimality of Gaussian noise stability, J. Eur. Math. Soc. (JEMS) 17 (2015), no. 2, 433–482. MR 3317748

[MN22] Emanuel Milman and Joe Neeman, The gaussian double-bubble and multi-bubble conjectures, Ann. of Math. (2) 195 (2022), no. 1, 89–206.

[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

[MS02] Rolando Magnanini and Shigeru Sakaguchi, Matzoh ball soup: heat conductors with a stationary isothermic surface, Ann. of Math. (2) 156 (2002), no. 3, 931–946. MR 1954240

[O’D] Ryan O’Donnell, Social choice, computational complexity, gaussian geometry, and boolean functions, In proceedings of the 2014 ICM.

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

  E-mail address: stevenmheilman@gmail.com