THREE CANDIDATE PLURALITY IS STABLEST FOR CORRELATIONS AT MOST 1/10

STEVEN HEILMAN

Abstract. We prove the three candidate Plurality is Stablest Conjecture of Khot-Kindler-Mossel-O’Donnell from 2005 for correlations ρ satisfying −1/43 < ρ < 1/10: the Plurality function is the most noise stable three candidate election method with small influences, when the corrupted votes have correlation −1/43 < ρ < 1/10 with the original votes. The previous best result of this type only achieved positive correlations at most 10^{−10^{10}}. Our result follows by solving the three set Standard Simplex Conjecture of Isaksson-Mossel from 2011 for all correlations −1/43 < ρ < 1/10.

The Gaussian Double Bubble Theorem corresponds to the case ρ → 1^{−}, so in some sense, our result is a generalization of the Gaussian Double Bubble Theorem. Our result is also notable since it is the first result for any ρ < 0, which is the only relevant case for computational hardness of MAX-3-CUT. In fact, assuming the Unique Games Conjecture, we show that MAX-3-CUT is NP-hard to approximate within a multiplicative factor of .98937, which improves on the known (unconditional) NP-hardness of approximation within a factor of 1 − (1/102), proven in 1997. As an additional corollary, we conclude that three candidate Borda Count is stablest for all −1/43 < ρ < 1/10.

Contents

1. Introduction  1
2. Fourier analysis of Spherical Noise Stability  11
3. Derivative Estimates  14
4. Stability Estimates  18
5. Change of Measure  24
6. Circular Rearrangement  30
7. A Convolution Bound  32
8. Proof of Main Theorem: Positive Correlation  34
9. Proof of Main Theorem: Negative Correlation  37
10. Proof of Unique Games Hardness  42
References  42

1. Introduction

Motivated by a result of Bourgain [Bou02] in discrete Fourier analysis and by computational hardness results for MAX-CUT [KKMO07], Mossel, O’Donnell and Oleszkiewicz proved the Majority is Stablest Theorem 1.2 below [MOO10]. This Theorem says that the majority function is the most noise stable voting method, such that each candidate has

Date: August 10, 2023. Key words and phrases. social choice theory, noise stability, plurality, max-cut, max-3-cut.

an equal chance of winning the election, and such that each voter has a small influence on the election’s outcome. Here we interpret a function f: {−1, 1}^{n} → {−1, 1} as a voting method with two candidates, denoted as 1 and −1. That is, the input of f are votes x = (x_{1}, …, x_{n}) ∈ {−1, 1}^{n}, where the i^{th} person’s vote is for candidate x_{i} ∈ {−1, 1}, and the winner of the election is f(x) when the votes are x.

The Majority is Stablest Theorem can also be motivated by social choice theory, which seeks “optimal” voting methods. For a mathematical discussion of social choice theory, see e.g. [O’D14, MOO10, IM12, Kal02]. Noise stability has also been investigated in percolation, e.g. in [BKS99].

Another main motivation of Theorem 1.2 was [KKMO07] computational hardness of MAX-CUT . The MAX-CUT problem asks for the partition of the vertices of a finite undirected graph into two sets that maximizes the number of edges going between the two sets. The MAX-CUT problem is NP-hard, so if P≠NP, no polynomial time algorithm can solve it. Moreover, it was shown that it is NP-hard to find a partition of a graph that is about 94% as much as the largest partition value [Hås01] [TSSW00] (for every ε > 0, a multiplicative approximation of 16/17 + ε is NP-hard). However, this NP-hardness result does not quite match the best known polynomial time algorithm for MAX-CUT. For any ε > 0, the semidefinite programming algorithm of [GW95] approximates the MAX-CUT problem in polynomial time within a multiplicative factor of α_{2} − ε, where

α_{2} := inf_{−1≤ρ≤1} \frac{2}{1} \frac{\frac{1}{π} arccos(ρ)}{1 − ρ} ≈ .87856720578.

That is, it is possible to obtain in polynomial time a partition of the graph where the number of edges going between the two partition elements is at least 87.8% as much as the largest partition value.

Assuming the Unique Games Conjecture, the gap between the 16/17 hardness and the .87856 … approximation can be closed exactly.

Theorem 1.1 (Sharp Hardness for MAX-CUT, [KKMO07, Theorem 1]). Assume that the Unique Games Conjecture is true [Kho02, Kho10, KMS18]. Then, for any ε > 0, it is NP-hard to approximate MAX-CUT within a multiplicative factor of α_{2} + ε.

Theorem 1.1 is called a sharp hardness result since the quantity α_{2} gives an exact barrier between tractability (i.e. the polynomial time algorithm of [GW95]) and intractability (as stated in Theorem 1.1).

For a statement of the Unique Games Conjecture, see [Kho02, Kho10]. For some recent progress demonstrating that the conjecture is “half way proven,” see [KMS18].

One main ingredient in the proof of Theorem 1.1 was Theorem 1.2.

Theorem 1.2 (Majority is Stablest, [MOO10]). Let ε > 0 and let 0 < ρ < 1. Then there exists a τ > 0 such that the following holds. Let n be a positive integer. Let f: {−1, 1}^{n} → {−1, 1} satisfy ∑_{x∈{−1,1}^{n}} f(x) = 0 and max_{1≤i≤n} Inf_{i}(f) ≤ τ. Then

S_{ρ}(f) ≤ 1 − \frac{2}{π} arccos(ρ) + ε.

For each 1 ≤ i ≤ n, we defined the i^{th} influence of f to be

Inf_{i}(f) := 2^{−n} ∑_{x∈\{−1,1\}^{n}} \frac{1}{2} |f(x) − f(x_{1}, …, x_{i−1}, −x_{i}, x_{i+1}, …, x_{n})| ,

and we defined the noise stability of f with parameter ρ ∈ (−1, 1) to be

S_{ρ}(f) := 2^{−n} ∑_{x∈\{−1,1\}^{n}} f(x) ∑_{y∈\{−1,1\}^{n}}((1 − ρ)/2)^{\frac{∥x−y∥_{1}}{2}} ((1 + ρ)/2)^{n− \frac{∥x−y∥_{1}}{2}} f(y).

Equivalently, S_{ρ}(f) is the expected value 𝔼(f(X)f(Y)), where X is a uniformly random element of {−1, 1}^{n}, and Y = (Y_{1}, …, Y_{n}) has independent pm1 entries with 𝔼X_{i}Y_{i} = ρ for all 1 ≤ i ≤ n. We also used ∥x∥_{1} := ∑_{i=1}^{n} |x_{i}| for all x = (x_{1}, …, x_{n}) ∈ ℝ^{n}.

In Theorem 1.2, the quantity 1 − \frac{2}{π} arccos(ρ) can also be written as

lim_{n→∞} S_{ρ}(Maj_{n}),  (1)

where Maj_{n}(x) := sign(x_{1} + ⋯ + x_{n}), for all x = (x_{1}, …, x_{n}) ∈ {−1, 1}^{n}, is the majority function. (The value of the limit in (1) does not depend on the definition of the sign of zero.)

Note that the name “Majority is Stablest” for Theorem 1.2 is a slight misnomer, since for any particular n, the majority function Maj_{n} is not guaranteed to exactly maximize noise stability, due to the +ε term in the inequality of Theorem 1.2. Moreover, S_{ρ}(−Maj_{n}) = S_{ρ}(Maj_{n}), i.e. anti-majority has the same noise stability as the majority function.

The full Majority is Stablest Theorem from [MOO10] is actually more general than Theorem 1.2, since the constraint 2^{−n} ∑_{x∈{−1,1}^{n}} f(x) = 0 can be replaced with the following constraint: for some fixed −1 < a < 1, we have 2^{−n} ∑_{x∈{−1,1}^{n}} f(x) = a. Under this assumption, a shifted majority function is most noise stable.

1.1. From Two Sets to Three. Theorem 1.1 addresses the MAX-CUT problem, where a graph is split into two pieces. One can consider a similar problem for splitting a graph into k ≥ 3 pieces. This problem is called the MAX-k-CUT problem.

Definition 1.3 (MAX-k-CUT). Let w: {1, …, n}^{2} → [0, ∞) be an n × n symmetric matrix with w(i, i) = 0 for all 1 ≤ i ≤ n. Fix k ≥ 2. The goal of the MAX-k-CUT problem is to find a partition P_{1}, …, P_{k} of {1, …, n} that maximizes the quantity ∑_{1≤i<j≤k} ∑_{ℓ∈P_{i},m∈P_{j}} w(ℓ, m).

Choosing k = 2 shows MAX-CUT is the same as MAX-2-CUT, when w is the adjacency matrix of an n-vertex graph.

It was conjectured in [KKMO07] that an analogue of Theorem 1.1 should be true for MAX-k-CUT. However, this result has been open since it was formulated.

Theorem 1.2 was proven as a Corollary of the so-called invariance principle [MOO10] (see also [Cha06, Rot79]). That is, the main insight used to prove Theorem 1.2 was that Theorem 1.2 is equivalent to a continuous inequality for Euclidean sets equipped with the Gaussian measure. Such a continuous inequality was proven already in 1985 [Bor85]. This inequality says that the noise stability of a set of fixed Gaussian measure is maximized by half spaces. (We define the noise stability of a Euclidean set in Definition 1.13 below.) The equivalence between the discrete problem of Theorem 1.2 and Borell’s inequality in Euclidean space [Bor85] was proven via a nonlinear generalization of the Berry-Esseén Central Limit Theorem, called an invariance principle.

If we try to generalize Theorem 1.2 to product domains e.g. to functions f: {1, 2, 3}^{n} → {1, 2, 3}, then we obtain the so-called Plurality is Stablest Conjecture [KKMO07, IM12]. As in [MOO10], this new conjecture is equivalent to a continuous problem in Euclidean space [IM12], which is a 3-set generalization of the inequality of Borell [Bor85].

In [IM12], the arguments of [KKMO07, MOO10] were adapted to show that sharp computational hardness for the MAX-k-CUT problem would follow from a k-set generalization of the inequality of Borell [Bor85]. Despite this equivalence, the k-set analogue of Borell’s inequality (known as the Standard Simplex Conjecture) was not known to be true or false. (The k = 3 case of this conjecture is stated in Theorem 1.5 below.) Moreover, previously studied proofs of Borell’s inequality did not generalize to k ≥ 3 sets, despite the development of many different proofs of Borell’s inequality [Bor85, Led94, Led96, Bob97, BS01, Bor03, MN15a, MN15b, Eld15].

Recently, we have been developing calculus of variations methods in order to prove the Conjecture of [IM12], i.e. a generalization of Theorem 1.2 to other finite product domains. Such methods originated in [CM12] (itself inspired by e.g. [Sim68, Per02]), where a monotone quantity for the mean curvature flow was created and its stable critical points were investigated. This monotone quantity was a supremum of Gaussian surface area. It was unclear if the methods of [CM12] could apply to the noise stability functional in Definition 1.13 until [HT21], where these methods were adapted to show that the k-set Standard Simplex Conjecture in ℝ^{n} reduces to the same conjecture in ℝ^{k−1}, for any n ≥ k − 1. This proof method can also prove Borell’s original inequality [HT21, Hei21]. The result of [HT21] also circumvented a difficulty identified in [HMN16]. Although Theorem 1.2 holds when the average value of f is fixed to be some number −1 < a < 1, the three candidate analogue of the Majority is Stablest Theorem can only be true when the voting method takes all of its values with equal probability. Likewise, the arguments used to prove the k = 3 set case of the Standard Simplex Conjecture must only work when each of the Euclidean sets in question has Gaussian measure 1/3. For other measure constraints, it may be impossible to easily describe the optimal sets, as e.g. observed in attempts to optimize Krivine’s functional as it relates to Grothendieck’s constant [BMMN13].

In this paper, we prove the k = 3 set analogue of Borell’s inequality (i.e. the k = 3 set Standard Simplex Conjecture) for all correlation parameters −.0234 ≤ ρ ≤ .1082, thereby proving the 3 candidate case of the Plurality is Stablest Conjecture, i.e. the 3 candidate analogue of Theorem 1.2 for all correlation parameters −.0234 ≤ ρ ≤ .1082. These conjectures have remained open since 2006 [KKMO07]. The current paper and the previous results [HT21, Hei14] seem to be the only works verifying cases of the Plurality is Stablest conjecture.

1.2. Some Notation. For any x = (x_{1}, …, x_{n}), y = (y_{1}, …, y_{n}) ∈ ℝ^{n}, denote

⟨x, y⟩ := ∑_{i=1}^{n} x_{i}y_{i}, ∥x∥ := ⟨x, x⟩^{1/2}.

Denote the (n − 1)-dimensional sphere in ℝ^{n} as

S^{n−1} := {x ∈ ℝ^{n}: ∥x∥ = 1}.

For any integer k ≥ 2, denote the standard simplex in ℝ^{k} as

Δ_{k} := {x ∈ ℝ^{k}: ∑_{i=1}^{k} x_{i} = 1, x_{i} ≥ 0, ∀ 1 ≤ i ≤ k}.

Define the Gaussian density function in ℝ^{n} as

γ_{n}(x) := (2π)^{−n/2}e^{−∥x∥^{2}/2}, ∀ x ∈ ℝ^{n}.

When A ⊆ ℝ^{n} is a measurable set, denote the Gaussian measure of A as γ_{n}(A) := ∫_{A} γ_{n}(x) dx.

Definition 1.4 (Ornstein-Uhlenbeck Operator). Let −1 < ρ < 1. Let f: ℝ^{n} → [0, 1] be measurable. Define the Ornstein-Uhlenbeck operator applied to f by

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

1.3. Main Results. Below, we say that Ω_{1}, Ω_{2}, Ω_{3} ⊆ ℝ^{n} is a partition of ℝ^{n} if Ω_{1}, Ω_{2}, Ω_{3} are measurable, Ω_{i} ∩ Ω_{j} = ∅ for all 1 ≤ i < j ≤ 3, and ∪_{i=1}^{3}Ω_{i} = ℝ^{n}.

Below, we also let Θ_{1}, Θ_{2}, Θ_{3} ⊆ ℝ^{2} be a partition of ℝ^{2} into three disjoint sectors (cones) each with cone angle 2π/3, centered at the origin.

Theorem 1.5 (Standard Simplex Conjecture, 3 Sets, [IM12, Conjecture 1.4]). Let n ≥ 2. Let Ω_{1}, Ω_{2}, Ω_{3} be a partition of ℝ^{n}.

If 0 < ρ ≤ .1082, and if γ_{n}(Ω_{i}) = 1/3 for all 1 ≤ i ≤ 3, then

∑_{i=1}^{3} ∫_{ℝ^{n}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω_{i}}(x) γ_{n}(x) dx ≤ ∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{Θ_{i}}(x)T_{ρ}1_{Θ_{i}}(x) γ_{2}(x) dx.

If −.0234 ≤ ρ < 0, (with no restriction on the measures γ_{n}(Ω_{i})), then

∑_{i=1}^{3} ∫_{ℝ^{n}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω_{i}}(x) γ_{n}(x) dx ≥ ∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{Θ_{i}}(x)T_{ρ}1_{Θ_{i}}(x) γ_{2}(x) dx.

Theorem 1.5 should hold for all −1 < ρ < 1 [IM12]. The two main inequalities in Theorem 1.5 are equalities only when Ω_{i} = Θ_{i} × ℝ^{n−1} for all 1 ≤ i ≤ 3 (up to measure zero changes and rotations applied to the sets). That is, we actually prove a stronger “stability” version of Theorem 1.5 in (53) and (65) when n = 2:

If 0 < ρ ≤ .1082, and if γ_{n}(Ω_{i}) = 1/3 for all 1 ≤ i ≤ 3, then

∑_{i=1}^{3} ∫_{ℝ^{n}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω_{i}}(x) γ_{n}(x) dx − ∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{Θ_{i}}(x)T_{ρ}1_{Θ_{i}}(x) γ_{2}(x) dx

≤ (−.3 + 3(ρ + ρ^{2})) ∫_{r=0}^{∞} r(1 − e^{−ρr/2})e^{−r^{2}/2} ∑_{i=1}^{3}(σ(Ω_{i} ∩ rS^{1}) − 1/3)^{2} \frac{3}{2} dr.

If −.0234 ≤ ρ < 0, (with no restriction on the measures γ_{n}(Ω_{i})), then

∑_{i=1}^{3} ∫_{ℝ^{n}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω_{i}}(x) γ_{n}(x) dx − ∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{Θ_{i}}(x)T_{ρ}1_{Θ_{i}}(x) γ_{2}(x) dx

≥ (2 · .75/13.2 − (3\sqrt{π/2}ρ + 8ρ^{2})) ∫_{r=0}^{∞} r(1 − e^{−ρr/2})e^{−r^{2}/2} ∑_{i=1}^{3}(σ(Ω_{i} ∩ rS^{1}) − 1/3)^{2} \frac{3}{2} dr.

Here σ denotes normalized (Haar) probability measure on the sphere S^{1}. Note that the “penalty” terms we wrote above only check how far the measure of each set is from 1/3 when restricted to sphere of radius r, though in the course of the proof we find that such restricted sets must be circular arcs.

As demonstrated in [IM12], Theorem 1.5 has a discrete analogue, known as the Plurality is Stablest Conjecture. This Conjecture was first formulated in [KKMO07].

Theorem 1.6 (Plurality is Stablest, 3 Candidates, Informal Statement, [KKMO07, page 9], [IM12, Conjecture 1.9]). The Plurality function is the most noise stable threecandidate voting method with small influences, for all correlations ρ satisfying −.0234 ≤ ρ ≤ .1082

More formally, Conjecture 1.10 below holds when m = 3 and −.0234 ≤ ρ ≤ .1082.

Theorem 1.6 should hold for all −1/2 ≤ ρ < 1 [KKMO07, IM12]. This is called the three candidate Plurality is Stablest Conjecture. If this conjecture holds, then we would be able to conclude sharp hardness of approximation for the MAX-3-CUT problem, assuming the Unique Games Conjecture.

Conjecture 1.7 (Sharp Hardness for MAX-3-CUT, [IM12]). Assume that the Unique Games Conjecture is true [Kho02, Kho10, KMS18]. Assume the Plurality is Stablest Conjecture holds (for three candidates) [IM12]. Then, for any ε > 0, it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of α_{3} + ε.

As shown in [IM12] using the formula from [KPW04], we have

α_{3} := inf_{− \frac{1}{2} ≤ρ≤1} \frac{3}{2} \frac{1 − ∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{Θ_{i}}(x)T_{ρ}1_{Θ_{i}}(x) γ_{2}(x) dx}{1 − ρ}

= inf_{− \frac{1}{2} ≤ρ≤1} \frac{3}{2} \frac{1 − 3(\frac{1}{9} + \frac{[arccos(−ρ)]^{2}−[arccos(ρ/2)]^{2}}{4π^{2}} )}{1 − ρ}

= \frac{3}{2} \frac{1 − 3(\frac{1}{9} + \frac{[arccos(1/2)]^{2}−[arccos(−1/4)]^{2}}{4π^{2}} )}{1 + 1/2} ≈ .83600811464.

The semidefinite programming algorithm of [FJ95] shows that Conjecture 1.7 is sharp, since the polynomial time algorithm of [FJ95] approximates the MAX-3-CUT problem with a multiplicative factor of α_{3} − ε, for any ε > 0.

A corollary of our main result Theorem 1.5 is a weaker version of Conjecture 1.7.

Theorem 1.8 (Unique Games Hardness for MAX-3-CUT). Assume that the Unique Games Conjecture is true [Kho02, Kho10, KMS18]. Then it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of .98937.

Although Theorem 1.8 does not achieve the .836 … hardness of approximation of Conjecture 1.7, the constant in Theorem 1.8 does improve upon (to the author’s knowledge) the best (unconditional) NP-hardness result for MAX-3-CUT [KKLP97], which says that MAX-3-CUT is NP-hard to approximate within a multiplicative factor of 1 − 1/(34(3)) ≈ .990 . . ..

Another consequence of Theorem 1.6 and the main result of [Hei22b] is that Borda Count is the most noise stable three-candidate ranked choice voting method with small influences satisfying the Condorcet Loser Criterion, for all correlations ρ satisfying −.0234 ≤ ρ ≤ .1082

1.4. Sketch of Proof of Main Theorem. Here we sketch the proof of Theorem 1.5 when ρ > 0. First, the main result of [HT21] (or [Hei22a] for negative correlations) reduces Theorem 1.5 to the case n = 2. Next, we use a spherical harmonic decomposition, as suggested as an approach to the conjectured vector-valued Borell inequality of [HNP^{+}21] (though note that their inequality is presently unproven). That is, we write the noise stability of a set Ω = Ω_{i} ⊆ ℝ^{2} as an average over spheres. Using Definition 1.4 below, we have

∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω_{i}}(x)γ_{2}(x) dx

= ∑_{i=1}^{3} \frac{1}{2π(1 − ρ^{2})} ∫_{r=0}^{∞} ∫_{s=0}^{∞} rse^{\frac{−r^{2}−s^{2}}{2(1−ρ^{2})}} ∫_{u∈S^{1}} ∫_{v∈S^{1}} 1_{rS^{1}∩Ω_{i}}(ru)1_{sS^{1}∩Ω_{i}}(sv)e^{\frac{ρrs⟨u,v⟩}{1−ρ^{2}}} dvdudsdr.

One might try to maximize the “spherical noise stability” by fixing r, s > 0 and then maximizing the two inner integrals in u, v over choices of Ω_{1}, Ω_{2}, Ω_{3} constrained to the circles rS^{1} and sS^{1}. However, such a maximization would ruin the measure constraint in Theorem 1.5, since the two inner integrals are maximized when rS^{1}∩Ω_{1} = rS^{1} and when sS^{1}∩Ω_{1} = sS^{1} (with Ω_{2} = Ω_{3} = ∅). In order to ameliorate this issue, it is natural to add and subtract the mean value c_{i}(r) := ∫_{rS^{1}∩Ω_{i}} dv/2π of 1_{Ω_{i}} on the circle rS^{1}, by writing:

∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω_{i}}(x)γ_{2}(x) dx

= ∑_{i=1}^{3} \frac{1}{2π(1 − ρ^{2})} ∫_{r=0}^{∞} ∫_{s=0}^{∞} rse^{\frac{−r^{2}−s^{2}}{2(1−ρ^{2})}} (c_{i}(r)c_{i}(s)

+ ∫_{u∈S^{1}} ∫_{v∈S^{1}}[1_{rS^{1}∩Ω_{i}}(ru) − c_{i}(r)][1_{sS^{1}∩Ω_{i}}(sv) − c_{i}(s)]e^{\frac{ρrs⟨u,v⟩}{1−ρ^{2}}} dvdu)dsdr.

(2)

Now, when r, s > 0 are fixed, the two inner integrals in u, v have a product of mean subtracted terms. These terms together can be considered a “mean subtracted spherical noise stability.” Crucially, this quantity is no longer maximized when rS^{1} ∩ Ω_{1} = rS^{1} and when sS^{1} ∩ Ω_{1} = sS^{1}. Such a mean subtraction step was also used in the earlier work [Hei14], though using Hermite polynomials as a Fourier basis instead of spherical harmonics. (It might be possible to use the methods of [Hei14] to prove Theorem 1.5, but we have not tried to do so.)

The decomposition (2) is natural since the mean subtracted spherical noise stability is exactly maximized when Ω_{1}, Ω_{2}, Ω_{3} intersected with rS^{1} are three disjoint spherical arcs of angle 2π/3, for all r > 0. This statement holds without any measure constraint on the sets.

Again, such a realization was crucial in [Hei14], in the context of Hermite polynomials, since we can temporarily ignore the measure constraint that γ_{2}(Ω_{i}) = 1/3 for all 1 ≤ i ≤ 3.

However, this observation and (2) are insufficient to prove Theorem 1.5, due to the first term (i.e. the product of the means c_{i}(r)c_{i}(s)) in (2). This term is instead maximized when rS^{1} ∩Ω_{i} = rS^{1} for some 1 ≤ i ≤ 3, for each r > 0. (In fact, even if we constrain γ_{2}(Ω_{i}) = 1/3 for all 1 ≤ i ≤ 3, the mean term in (2) seems to be maximized when Ω_{1}, Ω_{2}, Ω_{3} ⊆ ℝ^{2} are disjoint annuli.) Since the two terms of (2) have different maximizers, a naïve implementation of (2) does not prove Theorem 1.5. However, it turns out that we can upper bound the first c_{i}(r)c_{i}(s) term in (2) by the second mean subtracted noise stability term in (2), at least when the correlation ρ > 0 is close to zero. (See Lemma 5.1, which uses both spherical and Hermite Fourier analysis, combined with Corollary 4.2, which uses a derivative estimate in the angular direction.) Therefore, a straightforward spherical rearrangement (see e.g. Lemma 6.1) shows that (2) really is maximized when the intersection of each Ω_{i} with a circle centered at the origin is a circular arc of angle 2π/3. However, showing that the first term is (2) is bounded by the second term relies on some estimates that only seem to hold when ρ > 0 is small, so this is one main bottleneck in trying to solve the full problem for all correlations ρ. Interestingly, some of these estimates (such as Lemma 5.1) hold in ℝ^{n} for any n ≥ 2, but not when n = 1, since Lemma 5.1 uses integrability of the radial function r ↦ 1/r near r = 0 in ℝ^{n} when n = 2.

Our above discussion focused on the case ρ > 0. The above strategy almost works in the case ρ < 0. However, the case ρ < 0 presents an unexpected difficulty. When r · s is small enough (depending on ρ < 0), the last term in (2) is minimized when Ω_{1}, Ω_{2}, Ω_{3} intersected with rS^{1} are three disjoint spherical arcs of angle 2π/3. However, when r · s is large, this is no longer true! When r · s is large, the last term in (2) is minimized when Ω_{1}, Ω_{2} intersected with rS^{1} are two disjoint spherical arcs of angle π (and the intersection with Ω_{3} is empty). That is, a straightforward spherical rearrangement can no longer apply when ρ < 0, since when r · s is large, the optimizing sets do not agree with what they should be in Theorem 1.5. Nevertheless, we can further split the last term of (2) into two parts, one of which is maximized by three circular arcs with angle 2π/3 (for all r, s > 0), and the remaining term which is “smaller” in an L_{2} sense, leading again to a spherical rearrangement argument. Lastly, for technical reasons (such as proving that the optimal sets are “low-dimensional”), when ρ < 0 we need to deal with a bilinear version of noise stability, rather than the quadratic version used e.g. in (2). (For similar technical reasons, the bilinear noise stability was used e.g. in [HT21, Hei22a].)

1.5. On the Difficulty of Four or More Sets. One might wonder if the results of this paper could apply to k ≥ 4 sets, since our result only holds for k = 3 sets. At present, some difficulties remain for k ≥ 4. The key spherical rearrangement Lemma 6.1 is false when k ≥ 4. This can be seen as a consequence of the Propeller Conjecture in ℝ^{3} [HJN13]. The derivative of the noise stability of a partition at ρ = 0 in ℝ^{3} is maximized for three congruent flat cones with cone angle 2π/3, rather than for four regular tetrahedral cones, as observed in e.g. [HJN13]. Consequently, Lemma 6.1 cannot hold for k = 4 sets. Put another way, if we start with a partition of Euclidean space into 4 sets of Gaussian measure 1/4 each, and we then restrict the sets to spheres of various radii (as in (2)), then maximizing noise stability restricted to the spheres will result in three spherical simplices rather than four. That is, the analogue of the final inequality (45) is false when k ≥ 4. Inequality (45) shows that the noise stability (minus the measures of the sets) is larger when comparing three congruent cones to two half space of measure 1/2 each. But the analogous statement comparing four regular tetrahedral cones to three regular sectors is false.

Our strategy for k = 3 sets relies on maximizing a mean subtracted noise stability on circles (i.e. the last term in (2)), while ignoring any measure constraints on the sets. It may be possible (in fact, it seems necessary) to use the measure constraints on the sets in order to consider at least k ≥ 4 sets Ω_{1}, …, Ω_{k}. Likewise, incorporating first or second variation arguments (as in [HT21, Hei22a]) might further constrain the sets under consideration when k ≥ 4, and possibly lead to progress when k ≥ 4. Our proof of Theorem 1.5 does not use any direct measure constraints or first/second variation arguments.

One main obstacle to proving Theorem 1.5, as identified in [HMN16], is that Theorem 1.5 cannot hold for ρ > 0 if the sets satisfy (γ_{n}(Ω_{1}), γ_{n}(Ω_{2}), γ_{n}(Ω_{3})) ≠ (1/3, 1/3, 1/3). More specifically, the sets optimizing noise stability are not the affine of simplicial cones with flat facets, unless (γ_{n}(Ω_{1}), γ_{n}(Ω_{2}), γ_{n}(Ω_{3})) = (1/3, 1/3, 1/3). Therefore, a proof of Theorem 1.5 must somehow only work in the case (γ_{n}(Ω_{1}), γ_{n}(Ω_{2}), γ_{n}(Ω_{3})) = (1/3, 1/3, 1/3). And indeed, our proof accomplishes this task.

In this work we have also identified a new obstacle to proving Theorem 1.5 for ρ < 0 which does not seem to have been identified before, as described above. Namely, the spherical version of Theorem 1.5 is false for spheres of large radii when ρ < 0.

1.6. Formal Statement of Plurality is Stablest. Here we provide a formal statement of the Plurality is Stablest Conjecture, as written e.g. in [Hei22a].

Let k ≥ 2, k ∈ ℤ. If g: {1, …, k}^{n} → ℝ and 1 ≤ i ≤ n, we denote

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

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

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

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

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

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

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

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

Remark 1.9. The Plurality is Stablest Conjecture is only stated for −1/(k − 1) ≤ ρ ≤ 1, whereas the Standard Simplex Conjecture is stated for all −1 < ρ < 1, since the discrete noise stability S_{ρ}g only corresponds to an expected value when ρ ≥ −1/(k − 1).

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

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

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

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

We can now state the more formal version of the Plurality is Stablest Conjecture from [KKMO07, page 9], [IM12, Conjecture 1.9].

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

• If ρ ≥ 0 and if 𝔼f = \frac{1}{k} ∑_{i=1}^{k} e_{i}, then

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

• If −\frac{1}{m−1} ≤ ρ < 0, then

S_{ρ}f ≥ lim_{n→∞} S_{ρ}PLUR_{k,n} − ε.

We now state some remaining definitions.

Definition 1.11 (Correlated Gaussians). Let −1 < ρ < 1. Let G_{ρ}(x, y) denote the joint probability density function on ℝ^{n} × ℝ^{n} such that

G_{ρ}(x, y) := \frac{1}{(2π)^{n}(1 − ρ^{2})^{n/2}} e^{\frac{−∥x∥^{2}−∥y∥^{2}+2ρ⟨x,y⟩}{2(1−ρ^{2})}}  ∀ x, y ∈ ℝ^{n}.  (4)

We denote X ∼_{ρ} Y when (X, Y) ∈ ℝ^{n} × ℝ^{n} have joint probability density function G_{ρ}.

Definition 1.12 (Correlated Random Variables on the Sphere). Let G_{ρ}^{r,s}(u, v) denote the probability density function on S^{n−1} × S^{n−1} such that the first variable is uniform on S^{n−1} and such that the second variable conditioned on the first has conditional density

G_{ρ}^{r,s}(v|u) := \frac{1}{z_{ρ,r,s}} e^{\frac{ρrs⟨u,v⟩}{1−ρ^{2}}} , ∀ v ∈ S^{n−1}.

Here z_{ρ,r,s} is a normalizing constant, chosen so that ∫_{S^{n−1}} G_{ρ}^{r,s}(v|u)dσ(v) = 1, where σ denotes the uniform probability (Haar) measure on S^{n−1}.

We let N_{ρ}^{r,s} denote the above distribution on S^{n−1} × S^{n−1} and we denote (U, V) ∼ N_{ρ}^{r,s} when (U, V) ∈ S^{n−1} × S^{n−1} have the distribution N_{ρ}^{r,s}.

Definition 1.13 (Noise Stability). Let −1 < ρ < 1. Let Ω ⊆ ℝ^{n} be measurable. Define the noise stability of Ω with correlation ρ, to be

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

More generally, for any measurable f: ℝ^{n} → Δ_{k}, define its noise stability with correlation ρ, to be

∫_{ℝ^{n}}⟨f(x), T_{ρ}f(x)⟩γ_{n}(x) dx.

1.7. Expected Value Notation.

• 𝔼 with no subscript denotes expected value on a sphere with respect to the uniform (Haar) probability measure.

• 𝔼_{(U,V)∼N_{ρ}^{r,s}} denotes expected value with respect to (U, V) from Definition 1.12.

• 𝔼_{X∼_{ρ}Y} denotes expected value with respect to (X, Y) from Definition 1.11.

• 𝔼_{R,S} denotes expected value with respect to R, S where R = ∥X∥ , S = ∥Y ∥, and X, Y are two standard ρ-correlated Gaussians, as in Definition 1.11.

• 𝔼_{γ} denotes expected value with respect to the Gaussian density γ_{n}.

2. Fourier analysis of Spherical Noise Stability

In this section, we derive some properties of the noise stability restricted to sets in a sphere. Fix r, s > 0 and let 0 < ρ < 1. Define g: [−1, 1] → ℝ by

g(t) = g_{ρ,r,s}(t) := \sqrt{π} \frac{Γ((n − 1)/2)}{Γ(n/2)} \frac{e^{\frac{ρrst}{1−ρ^{2}}}}{∫_{−1}^{1}(1 − a^{2})^{\frac{n}{2} − \frac{3}{2}} e^{\frac{ρrsa}{1−ρ^{2}}} da},  ∀ t ∈ [−1, 1].  (5)

Recall that, if h: ℝ → ℝ is continuous, then

\frac{1}{Vol(S^{n−1})} ∫_{S^{n−1}} h(y_{1})dy = \frac{Vol(S^{n−2})}{Vol(S^{n−1})} ∫_{−1}^{1}(1 − t^{2})^{\frac{n}{2} − \frac{3}{2}} h(t)dt

= \frac{2π^{(n−1)/2}/Γ((n − 1)/2)}{2π^{n/2}/Γ(n/2)} ∫_{−1}^{1}(1 − t^{2})^{\frac{n}{2} − \frac{3}{2}} h(t)dt

= \frac{1}{\sqrt{π}} \frac{Γ(n/2)}{Γ((n − 1)/2)} ∫_{−1}^{1}(1 − t^{2})^{\frac{n}{2} − \frac{3}{2}} h(t)dt.

We have chosen the constants so that 1 = \frac{1}{Vol(S^{n−1})} ∫_{S^{n−1}} h(y_{1})dy, when h = g. When h := 1,

we have ∫_{−1}^{1}(1 − t^{2})^{\frac{n}{2} − \frac{3}{2}} dt = \sqrt{π} \frac{Γ((n−1)/2)}{Γ(n/2)}, so

g(t) = g_{ρ,r,s}(t) =^{(5)} e^{\frac{ρrst}{1−ρ^{2}}} · \frac{∫_{−1}^{1}(1 − a^{2})^{\frac{n}{2} − \frac{3}{2}} da}{∫_{−1}^{1}(1 − a^{2})^{\frac{n}{2} − \frac{3}{2}} e^{\frac{ρrsa}{1−ρ^{2}}} da},  ∀ t ∈ [−1, 1].  (6)

Definition 2.1 (Spherical Noise Stability). Let ρ ∈ (−1, 1), r, s > 0. Let f: S^{n−1} → [0, 1] be measurable. Define g = g_{ρ,r,s}: [−1, 1] → ℝ by (6). Define the smoothing operator U_{g} applied to f by

U_{g}f(x) := ∫_{S^{n−1}} g(⟨x, y⟩)f(y) dσ(y), ∀x ∈ S^{n}.

Here σ denotes the (normalized) Haar probability measure on S^{n−1}. The spherical noise stability of a set Ω ⊆ S^{n−1} with parameters ρ, r, s is

∫_{S^{n−1}} 1_{Ω}(x)U_{g}1_{Ω}(x) dσ(x).

When n = 2, we have, for any −1 < t < 1, using the substitution a = cos θ,

g(t) =^{(6)} e^{\frac{ρrst}{1−ρ^{2}}} · \frac{∫_{−1}^{1}(1 − a^{2})^{−1/2}da}{∫_{−1}^{1}(1 − a^{2})^{−1/2}e^{\frac{ρrsa}{1−ρ^{2}}} da} = e^{\frac{ρrst}{1−ρ^{2}}} · \frac{∫_{0}^{π} dθ}{∫_{0}^{π} e^{\frac{ρrs cos θ}{1−ρ^{2}}} dθ} = \frac{e^{\frac{ρrst}{1−ρ^{2}}}}{\frac{1}{π} ∫_{0}^{π} e^{\frac{ρrs cos θ}{1−ρ^{2}}} dθ}. (7)

∫_{S^{1}} 1_{Ω}(x)U_{g}1_{Ω}(x) dσ(x) =^{(7)} \frac{\frac{1}{(2π)^{2}} ∫_{S^{1}} ∫_{S^{1}} 1_{Ω}(x)1_{Ω}(y)e^{\frac{ρrs⟨x,y⟩}{1−ρ^{2}}} dxdy}{\frac{1}{2π} ∫_{0}^{2π} e^{\frac{ρrs cos θ}{1−ρ^{2}}} dθ}

= \frac{∫_{a=0}^{a=2π} ∫_{b=0}^{b=2π} 1_{Ω}(a)1_{Ω}(b)e^{\frac{ρrs cos(a−b)}{1−ρ^{2}}} dadb}{2π ∫_{0}^{2π} e^{\frac{ρrs cos a}{1−ρ^{2}}} da}.

(8)

Here and below we abuse notation slightly by identifying S^{1} with the interval [0, 2π].

The spherical noise stability has a decomposition into Fourier series by the Funk-Hecke Formula [HNP^{+}21, Theorem 4.3] (see also (14) for the definition of λ_{d,2}^{r,s})

∫_{S^{1}} 1_{Ω}(x)U_{g}1_{Ω}(x) dσ(x) = [σ(Ω)]^{2} + \frac{1}{2π^{2}} ∑_{d=1}^{∞} λ_{d,2}^{r,s}(( ∫_{Ω} cos(xd) dx)^{2} + ( ∫_{Ω} sin(xd) dx)^{2}).

(9)

More generally, for any measurable Ω, Ω′ ⊆ S^{1}, we have e.g. by applying a polarization identity to (9),

∫_{S^{1}} 1_{Ω}(x)U_{g}1_{Ω′}(x) dσ(x) = σ(Ω)σ(Ω′)

+ \frac{1}{2π^{2}} ∑_{d=1}^{∞} λ_{d,2}^{r,s}( ∫_{Ω} cos(xd) dx ∫_{Ω′} cos(xd) dx + ∫_{Ω} sin(xd) dx ∫_{Ω′} sin(xd) dx).

(10)

Below, we will obtain some bounds for the constants λ_{d,2}^{r,s} in e.g. (16), (19) and (21). Roughly speaking, λ_{d,2}^{r,s} behaves like (ρrs)^{d} for r · s near zero, and λ_{d,2}^{r,s} is close to 1 for large r · s. We note in passing that, for any 0 < t ≤ π,

∫_{S^{1}} 1_{[−t/2,t/2]}(x)U_{g}1_{[−t/2,t/2]}(x) dσ(x) =^{(9)} (\frac{t}{2π} )^{2} + \frac{2}{π^{2}} ∑_{d=1}^{∞} λ_{d,2}^{r,s} \frac{1}{d^{2}} sin^{2}(td/2).  (11)

Notation: Rising Factorial. For any x ∈ ℝ and for any integer d ≥ 1, we denote (x)_{d} := ∏_{j=0}^{d−1}(x + j).

Let C_{d}^{(α)} : [−1, 1] → ℝ denote the index α degree d Gegenbauer polynomial, which satisfies a Rodrigues formula [AAR99, p. 303, 6.4.14]

(1 − t^{2})^{α−1/2}C_{d}^{(α)}(t) = \frac{(−2)^{d}(α)_{d}}{d!(d + 2α)_{d}} \frac{d^{d}}{dt^{d}} (1 − t^{2})^{α+d−1/2}, ∀ t ∈ [−1, 1].

Letting α := \frac{n}{2} − 1, we have

(1 − t^{2})^{\frac{n}{2} − \frac{3}{2}} C_{d}^{( \frac{n}{2} −1)}(t) = \frac{(−2)^{d}(\frac{n}{2} − 1)_{d}}{d!(d + n − 2)_{d}} \frac{d^{d}}{dt^{d}} (1 − t^{2})^{\frac{n}{2} +d− \frac{3}{2}} ,  ∀ t ∈ [−1, 1]. (12)

From [AAR99, p. 302],

C_{d}^{( \frac{n}{2} −1)}(1) = \frac{(n − 2)_{d}}{d!} .  (13)

Then [HNP^{+}21, Corollary 4.6] defines

λ_{d,n}^{r,s} := \frac{∫_{−1}^{1} \frac{C_{d}^{( \frac{n}{2} −1)}(t)}{C_{d}^{( \frac{n}{2} −1)}(1)}(1 − t^{2})^{\frac{n}{2} − \frac{3}{2}} g(t)dt}{∫_{−1}^{1}(1 − t^{2})^{\frac{n}{2} − \frac{3}{2}} dt} =^{(6)} \frac{∫_{−1}^{1} \frac{C_{d}^{( \frac{n}{2} −1)}(t)}{C_{d}^{( \frac{n}{2} −1)}(1)}(1 − t^{2})^{\frac{n}{2} − \frac{3}{2}} e^{\frac{ρrst}{1−ρ^{2}}} dt}{∫_{−1}^{1}(1 − t^{2})^{\frac{n}{2} − \frac{3}{2}} e^{\frac{ρrst}{1−ρ^{2}}} dt}

=^{(12)∧(13)} \frac{(−2)^{d}(\frac{n}{2} − 1)_{d}}{d!(d + n − 2)_{d}} \frac{d!}{(n − 2)_{d}} \frac{∫_{−1}^{1} [\frac{d^{d}}{dt^{d}} (1 − t^{2})^{\frac{n}{2} +d− \frac{3}{2}} ]e^{\frac{ρrst}{1−ρ^{2}}} dt}{∫_{−1}^{1}(1 − t^{2})^{\frac{n}{2} − \frac{3}{2}} e^{\frac{ρrst}{1−ρ^{2}}} dt}.

Integrating by parts d times,

λ_{d,n}^{r,s} = (\frac{ρrs}{1 − ρ^{2}} )^{d} \frac{(−2)^{d}(\frac{n}{2} − 1)_{d}}{(n − 2)_{2d}} \frac{(−1)^{d} ∫_{−1}^{1}(1 − t^{2})^{\frac{n}{2} +d− \frac{3}{2}} e^{\frac{ρrst}{1−ρ^{2}}} dt}{∫_{−1}^{1}(1 − t^{2})^{\frac{n}{2} − \frac{3}{2}} e^{\frac{ρrst}{1−ρ^{2}}} dt}.  (14)

We now examine the ratio of integrals

\frac{∫_{−1}^{1}(1 − t^{2})^{\frac{n}{2} +d− \frac{3}{2}} e^{\frac{ρrst}{1−ρ^{2}}} dt}{∫_{−1}^{1}(1 − t^{2})^{\frac{n}{2} − \frac{3}{2}} e^{\frac{ρrst}{1−ρ^{2}}} dt},  (15)

which is a ratio of modified Bessel functions of the first kind. To recall their definition, first recall the definition of the Bessel function J_{α} of the first kind of order α ≥ 0 [AAR99, p. 204]

J_{α}(x) := \frac{1}{\sqrt{π}Γ(α + 1/2)}(x/2)^{α} ∫_{−1}^{1} e^{ixt}(1 − t^{2})^{α−1/2}dt, ∀ x ∈ ℝ.

The modified Bessel function I_{α} of the first kind of order α ≥ 0 is then defined to be [AAR99, p. 222]

I_{α}(x) := i^{−α}J_{α}(ix) = \frac{1}{\sqrt{π}Γ(α + 1/2)}(x/2)^{α} ∫_{−1}^{1} e^{−xt}(1 − t^{2})^{α−1/2}dt

= \frac{1}{\sqrt{π}Γ(α + 1/2)}(x/2)^{α} ∫_{−1}^{1} e^{xt}(1 − t^{2})^{α−1/2}dt, ∀ x ∈ ℝ.

\frac{I_{α+d}(a)}{I_{α}(a)} = \frac{(a/2)^{d}}{(α + 1/2)_{d}} \frac{∫_{−1}^{1} e^{at}(1 − t^{2})^{α+d−1/2}dt}{∫_{−1}^{1} e^{at}(1 − t^{2})^{α−1/2}dt}, ∀ a ∈ ℝ, ∀ α ≥ 0.

So, setting α = (n/2) − 1 here, the ratio from (15) is equal to

(\frac{n − 1}{2})_{d}(\frac{2(1 − ρ^{2})}{ρrs})^{d} · \frac{I_{n/2+d−1}(ρrs/[1 − ρ^{2}])}{I_{(n/2)−1}(ρrs/[1 − ρ^{2}])}.

Combining with (14), we have

\begin{aligned}λ_{d,n}^{r,s} & = (\frac{ρrs}{1 − ρ^{2}} )^{d} \frac{2^{d}(n/2 − 1)_{d}}{(n − 2)_{2d}} (\frac{n − 1}{2})_{d}(\frac{2(1 − ρ^{2})}{ρrs})^{d} \frac{I_{n/2+d−1}(ρrs/[1 − ρ^{2}])}{I_{(n/2)−1}(ρrs/[1 − ρ^{2}])} \\ & = \frac{I_{n/2+d−1}(ρrs/[1 − ρ^{2}])}{I_{(n/2)−1}(ρrs/[1 − ρ^{2}])} = ∏_{j=1}^{d} \frac{I_{(n/2)+j−1}(ρrs/[1 − ρ^{2}])}{I_{(n/2)+j−2}(ρrs/[1 − ρ^{2}])}. \end{aligned} (16)

We have [Amo74, p. 241]

\frac{a}{α + 1 + \sqrt{(α + 1)^{2} + a^{2}}} ≤ \frac{I_{α+1}(a)}{I_{α}(a)} ≤ \frac{a}{α + \sqrt{α^{2} + a^{2}}} ,  ∀ a, α ≥ 0.  (17)

It therefore follows from (16) that

λ_{d,n}^{r,s} ≥ λ_{d+1,n}^{r,s},  ∀ d ≥ 0,  (18)

and

\begin{aligned}0 & < ∏_{j=0}^{d−1} \frac{ρrs/[1 − ρ^{2}]}{n/2 + j + \sqrt{(n/2 + j)^{2} + [ρrs/[1 − ρ^{2}]]^{2}}} ≤ λ_{d,n}^{r,s} \\ & ≤ ∏_{j=0}^{d−1} \frac{ρrs/[1 − ρ^{2}]}{(n/2 + j − 1) + \sqrt{(n/2 + j − 1)^{2} + [ρrs/[1 − ρ^{2}]]^{2}}} ≤ 1, ∀ r, s > 0, ∀ ρ ∈ (0, 1). \end{aligned}

(19)

Also, from [Amo74, p. 242]

\frac{a}{α + 1/2 + \sqrt{(α + 3/2)^{2} + a^{2}}} ≤ \frac{I_{α+1}(a)}{I_{α}(a)} ≤ \frac{a}{α + 1/2 + \sqrt{(α + 1/2)^{2} + a^{2}}} , ∀ a, α ≥ 0.

(20)

So, for all r, s > 0 and for all ρ ∈ (0, 1),

\begin{aligned}0 & < ∏_{j=0}^{d−1} \frac{ρrs/[1 − ρ^{2}]}{n/2 + j − 1/2 + \sqrt{(n/2 + j + 1/2)^{2} + [ρrs/[1 − ρ^{2}]]^{2}}} ≤ λ_{d,n}^{r,s} \\ & ≤ ∏_{j=0}^{d−1} \frac{ρrs/[1 − ρ^{2}]}{(n/2 + j − 1/2) + \sqrt{(n/2 + j − 1/2)^{2} + [ρrs/[1 − ρ^{2}]]^{2}}} ≤ 1. \end{aligned}  (21)

Also, from [Amo74, p. 241]

\frac{a}{1 + α + \sqrt{(α + 1)^{2} + a^{2}}} ≤ \frac{I_{α+1}(a)}{I_{α}(a)} ≤ \frac{a}{α + \sqrt{(α + 2)^{2} + a^{2}}} ,  ∀ a, α ≥ 0. (22)

3. Derivative Estimates

As demonstrated in (8), the quantity F (θ) defined below is the mean subtracted spherical noise stability of an interval [0, θ] ⊆ ℝ/2πℤ. In this section we consider derivative properties of the mean subtracted spherical noise stability of a partition of the circle S^{1}, parameterized as ℝ/2πℤ. The ultimate goal is control of the second term in (2).

Lemma 3.1. Denote

F (θ) := \frac{∫_{a=0}^{a=θ} ∫_{b=0}^{b=θ} e^{\frac{ρrs cos(a−b)}{1−ρ^{2}}} dadb}{2π ∫_{0}^{2π} e^{\frac{ρrs cos a}{1−ρ^{2}}} da} − (\frac{θ}{2π} )^{2}.  (23)

Suppose θ_{1} > θ_{2} > 0 and π ≤ θ_{1} + θ_{2} ≤ 2π. Then

\frac{d}{dθ}|_{θ=0}[F (θ_{1} + θ) + F (θ_{2} − θ)] < 0.

If additionally θ_{1} − θ_{2} ≤ π, then

\frac{d}{dθ}|_{θ=0}[F (θ_{1} + θ) + F (θ_{2} − θ)] ≤ ( − 1 + e^{− \frac{ρrs cos([θ_{1}−θ_{2}]/2)[θ_{1}+θ_{2}−π]/2}{1−ρ^{2}}} )\frac{θ_{1} − θ_{2}}{2π^{2}} .

Proof. We have

\frac{d}{dθ}|_{θ=0}[F (θ_{1} + θ) + F (θ_{2} − θ)] = F′(θ_{1}) − F′(θ_{2})

= 2\frac{∫_{b=0}^{b=θ_{1}} e^{\frac{ρrs cos(θ_{1}−b)}{1−ρ^{2}}} db}{2π ∫_{0}^{2π} e^{\frac{ρrs cos a}{1−ρ^{2}}} da} − \frac{θ_{1}}{2π^{2}} − 2\frac{∫_{b=0}^{b=θ_{2}} e^{\frac{ρrs cos(θ_{2}−b)}{1−ρ^{2}}} db}{2π ∫_{0}^{2π} e^{\frac{ρrs cos a}{1−ρ^{2}}} da} + \frac{θ_{2}}{2π^{2}}

= 2\frac{∫_{b=0}^{b=θ_{1}} e^{\frac{ρrs cos(b)}{1−ρ^{2}}} db}{2π ∫_{0}^{2π} e^{\frac{ρrs cos a}{1−ρ^{2}}} da} − \frac{θ_{1}}{2π^{2}} − 2\frac{∫_{b=0}^{b=θ_{2}} e^{\frac{ρrs cos(b)}{1−ρ^{2}}} db}{2π ∫_{0}^{2π} e^{\frac{ρrs cos a}{1−ρ^{2}}} da} + \frac{θ_{2}}{2π^{2}}

= 2\frac{∫_{b=θ_{2}}^{b=θ_{1}} e^{\frac{ρrs cos(b)}{1−ρ^{2}}} db}{2π ∫_{0}^{2π} e^{\frac{ρrs cos a}{1−ρ^{2}}} da} − \frac{θ_{1} − θ_{2}}{2π^{2}} .

(24)

In the case θ_{1} − θ_{2} ≥ π, (24) is negative by the monotonicity of the cosine function:

2\frac{∫_{b=θ_{2}}^{b=θ_{1}} e^{\frac{ρrs cos(b)}{1−ρ^{2}}} db}{2π ∫_{0}^{2π} e^{\frac{ρrs cos a}{1−ρ^{2}}} da} ≤ 2\frac{∫_{b=0}^{b=θ_{1}−θ_{2}} e^{\frac{ρrs cos(b)}{1−ρ^{2}}} db}{2π ∫_{0}^{2π} e^{\frac{ρrs cos a}{1−ρ^{2}}} da} < \frac{θ_{1} − θ_{2}}{2π^{2}} .  (25)

So, it remains to consider the case that θ_{1} − θ_{2} < π, i.e. that [θ_{1} − θ_{2}]/2 < π/2.

Using cos(x−y)−cos(x) = ∫_{x−y}^{x} sin(y) dy ≥ y min(sin(x), sin(x−y)) ≥ y min_{x−y≤z≤x} sin(z), for all θ_{2} ≤ b ≤ θ_{1}, we have

e^{\frac{ρrs cos(b−[θ_{1}+θ_{2}−π]/2)}{1−ρ^{2}}} − e^{\frac{ρrs cos(b)}{1−ρ^{2}}} = e^{\frac{ρrs cos(b)}{1−ρ^{2}}} [e^{\frac{ρrs(cos(b−[θ_{1}+θ_{2}−π]/2)−cos(b))}{1−ρ^{2}}} − 1]
= e^{\frac{ρrs cos(b)}{1−ρ^{2}}} [e^{\frac{ρrs ∫{b \atop b−[θ_{1}+θ_{2}−π]/2} sin(y) dy}{1−ρ^{2}}} − 1]
≥ e^{\frac{ρrs cos(b)}{1−ρ^{2}}} [e^{\frac{ρrs cos([θ_{1}−θ_{2}]/2)·[θ_{1}+θ_{2}−π]/2}{1−ρ^{2}}} − 1].

That is, e^{\frac{ρrs cos(b)}{1−ρ^{2}}} ≤ e^{\frac{ρrs cos(b−[θ_{1}+θ_{2}−π]/2)}{1−ρ^{2}}} e^{− \frac{ρrs cos([θ_{1}−θ_{2}]/2)·[θ_{1}+θ_{2}−π]/2}{1−ρ^{2}}} , ∀ θ_{2} ≤ b ≤ θ_{1}.

Therefore, denoting c := e^{− \frac{ρrs cos([θ_{1}−θ_{2}]/2)·[θ_{1}+θ_{2}−π]/2}{1−ρ^{2}}} ,

∫_{b=θ_{2}}^{b=θ_{1}} e^{\frac{ρrs cos(b)}{1−ρ^{2}}} db ≤ c ∫_{b=θ_{2}}^{b=θ_{1}} e^{\frac{ρrs cos(b−[θ_{1}+θ_{2}−π]/2)}{1−ρ^{2}}} db = c ∫_{b=θ_{2}− \frac{θ_{1}+θ_{2}−π}{2}}^{b=θ_{1}− \frac{θ_{1}+θ_{2}−π}{2}} e^{\frac{ρrs cos(b)}{1−ρ^{2}}} db

= c ∫_{b= \frac{θ_{2}−θ_{1}}{2} + \frac{π}{2}}^{b= \frac{θ_{1}−θ_{2}}{2} + \frac{π}{2}} e^{\frac{ρrs cos(b)}{1−ρ^{2}}} db = c ∫_{b= \frac{θ_{2}−θ_{1}}{2}}^{b= \frac{θ_{1}−θ_{2}}{2}} e^{− \frac{ρrs sin(b)}{1−ρ^{2}}} db = c ∫_{b= \frac{θ_{2}−θ_{1}}{2}}^{b= \frac{θ_{1}−θ_{2}}{2}} e^{\frac{ρrs sin(b)}{1−ρ^{2}}} db.

(26)

The Lemma then follows from Lemma 3.2 below, since Lemma 3.2 implies that

\frac{2 ∫_{b= \frac{θ_{2}−θ_{1}}{2}}^{b= \frac{θ_{1}−θ_{2}}{2}} e^{\frac{ρrs sin(b)}{1−ρ^{2}}} db}{∫_{0}^{2π} e^{\frac{ρrs cos a}{1−ρ^{2}}} da} < \frac{θ_{1} − θ_{2}}{π} ,

which concludes the first part of the proof by plugging into (24).

□

Lemma 3.2.

\frac{2 ∫_{b=−t}^{b=t} e^{\frac{ρrs sin(b)}{1−ρ^{2}}} db}{∫_{0}^{2π} e^{\frac{ρrs cos a}{1−ρ^{2}}} da} < \frac{2t}{π} < 0, ∀ 0 < t < π/2.

Proof. We must show that

\frac{1}{2t} ∫_{b=−t}^{b=t} e^{\frac{ρrs sin(b)}{1−ρ^{2}}} db < \frac{1}{2π} ∫_{0}^{2π} e^{\frac{ρrs cos a}{1−ρ^{2}}} da = \frac{1}{π} ∫_{0}^{π} e^{\frac{ρrs cos a}{1−ρ^{2}}} da, ∀ 0 < t < π/2.

The quantity on the left is monotone increasing in t, and it is equal to the right when t = π/2. The former statement follows since

\frac{1}{2t} ∫_{b=−t}^{b=t} e^{\frac{ρrs sin(b)}{1−ρ^{2}}} db = \frac{1}{4t} ∫_{b=−t}^{b=t} (e^{\frac{ρrs sin(b)}{1−ρ^{2}}} + e^{− \frac{ρrs sin(b)}{1−ρ^{2}}} ) db,

and the function h(b) := e^{\frac{ρrs sin(b)}{1−ρ^{2}}} + e^{− \frac{ρrs sin(b)}{1−ρ^{2}}} is even and increasing for all 0 < b < π/2, so its average value on the interval [−t, t] is increasing for all 0 < t < π/2, as can be seen by taking a derivative:

\frac{d}{dt}(\frac{1}{t} ∫_{b=−t}^{b=t} h(b) db) = \frac{1}{t}2h(t) − \frac{1}{t^{2}} ∫_{b=−t}^{b=t} h(b) db

= \frac{1}{t}(\frac{1}{t} ∫_{b=−t}^{b=t} h(t)db − \frac{1}{t} ∫_{b=−t}^{b=t} h(b) db) = \frac{1}{t^{2}} ∫_{b=−t}^{b=t}(h(t) − h(b))db.

□

Integrating Lemma 3.1 gives the following stability estimate, showing that three intervals each of length 2π/3 maximize the second term of (2), at least among partitions into three intervals. (The case that θ_{i} ≥ π for some 1 ≤ i ≤ 3 in Lemma 3.3 will be treated separately in Lemma 4.1 below.)

Lemma 3.3. Let θ_{1}, θ_{2}, θ_{3} ≥ 0 with θ_{1} + θ_{2} + θ_{3} = 2π. Define F as in (23). Assume that θ_{i} ≤ π for all 1 ≤ i ≤ 3. Then

−3F (2π/3) + ∑_{i=1}^{3} F (θ_{i}) ≤ (.158)( − 1 + (1 − \frac{3^{4/3}}{5} )e^{− \frac{ρrs}{1−ρ^{2}} \frac{π}{2}} ⋯

+ \frac{3^{4/3}}{5} e^{− \frac{ρrs}{1−ρ^{2}} \frac{π}{6}} ) ∑_{1≤i<j≤3} (\frac{θ_{i}}{2π} − 1/3)^{2}.

Proof. Since θ_{i} ≤ π for all 1 ≤ i ≤ 3 and θ_{1} + θ_{2} + θ_{3} = 2π, we have |θ_{i} − θ_{j}| ≤ π and θ_{i} + θ_{j} ≥ π for all 1 ≤ i < j ≤ 3. We will use the latter inequalities frequently below.

We will replace θ_{1} ≥ θ_{2} with θ_{1} − t, θ_{2} + t, where 0 ≤ t ≤ (θ_{1} − θ_{2})/2. We change the first two regions to have the same measure. From Lemma 3.1, after integrating in t, we will then get a factor of

∫_{t=0}^{t=[θ_{1}−θ_{2}]/2} ( − 1 + e^{− \frac{ρrs cos((θ_{1}−θ_{2}−2t)/2)[θ_{1}+θ_{2}−π]/2}{1−ρ^{2}}} )\frac{θ_{1} − θ_{2} − 2t}{2π^{2}} dt

= \frac{1}{2} ∫_{t=0}^{t=θ_{1}−θ_{2}} ( − 1 + e^{− \frac{ρrs cos(t/2)[θ_{1}+θ_{2}−π]/2}{1−ρ^{2}}} )\frac{t}{2π^{2}} dt.

Now, the region has angles, {[θ_{1} + θ_{2}]/2, [θ_{1} + θ_{2}]/2, θ_{3}}. We will replace these angles with {[θ_{1} + θ_{2}]/2 − t, [θ_{1} + θ_{2}]/2 − t, θ_{3} + 2t}, where 0 ≤ t ≤ [(θ_{1} + θ_{2})/2 − θ_{3}]/3. Then, change all three regions to have the same measure. After integrating in t, we will get an additional factor from Lemma 3.1 of

2 ∫_{t=0}^{t=[(θ_{1}+θ_{2})/2−θ_{3}]/3} ( − 1 + e^{− \frac{ρrs cos \frac{1}{2} ((θ_{1}+θ_{2})/2−θ_{3}−3t)[θ_{1}+θ_{2}−t+2t+2θ_{3}−2π]/4]}{1−ρ^{2}}} )\frac{(θ_{1} + θ_{2})/2 − θ_{3} − 3t)}{2 · 2π^{2}}dt

= \frac{2}{3} ∫_{t=0}^{t=[θ_{1}+θ_{2}]/2−θ_{3}} ( − 1 + e^{− \frac{ρrs cos(t/2)[θ_{3}+t]/4]}{1−ρ^{2}}} )\frac{t}{2π^{2}} dt.

So, the total you get is, using −1 + e^{−εc} ≤ (−1 + e^{−ε})c, when c = cos(t/2)

\frac{1}{2} ∫_{t=0}^{t=θ_{1}−θ_{2}} ( − 1 + e^{− \frac{ρrs cos(t/2)[θ_{1}+θ_{2}−π]/2}{1−ρ^{2}}} )\frac{t}{2π^{2}} dt

+ \frac{2}{3} ∫_{t=0}^{t=[θ_{1}+θ_{2}]/2−θ_{3}} ( − 1 + e^{− \frac{ρrs cos(t/2)θ_{3}/4}{1−ρ^{2}}} )\frac{t}{2π^{2}} dt

≤ \frac{1}{2}( − 1 + e^{− \frac{ρrs[θ_{1}+θ_{2}−π]/2}{1−ρ^{2}}} ) ∫_{t=0}^{t=θ_{1}−θ_{2}} cos(t/2)\frac{t}{2π^{2}} dt

+ \frac{2}{3}( − 1 + e^{− \frac{ρrsθ_{3}/4}{1−ρ^{2}}} ) ∫_{t=0}^{t=[θ_{1}+θ_{2}]/2−θ_{3}} cos(t/2)\frac{t}{2π^{2}} dt.

Integrating and using ∫_{0}^{c} t cos(t/2)dt = 2c sin(c/2) + 4(cos(c/2) − 1) and ∫_{0}^{c} cos(t/2)dt = 2 sin(c/2). We have c^{2}/2 − c^{4}/34 ≥ ∫_{0}^{c} t cos(t/2)dt ≥ c^{2}/2 − c^{4}/32 for all 0 ≤ c ≤ π/2.

\frac{1}{2}( − 1 + e^{− \frac{ρrs[θ_{1}+θ_{2}−π]/2}{1−ρ^{2}}} )[(\frac{θ_{1} − θ_{2}}{2π} )^{2}(\frac{1}{2} − \frac{1}{32}(θ_{1} − θ_{2})^{2})

+ \frac{2}{3}( − 1 + e^{− \frac{ρrsθ_{3}/4}{1−ρ^{2}}} )(\frac{[θ_{1} − θ_{3}]/2 + (θ_{2} − θ_{3})/2}{2π})^{2}(\frac{1}{2} − \frac{1}{32}([θ_{1} − θ_{3}]/2 + (θ_{2} − θ_{3})/2)^{2})

= \frac{1}{2}( − 1 + e^{− \frac{ρrs[π−θ_{3}]/2}{1−ρ^{2}}} )[(\frac{θ_{1} − θ_{2}}{2π} )^{2}(\frac{1}{2} − \frac{1}{32}(θ_{1} − θ_{2})^{2})

+ \frac{2}{3}( − 1 + e^{− \frac{ρrsθ_{3}/4}{1−ρ^{2}}} )(\frac{[θ_{1} − θ_{3}]/2 + (θ_{2} − θ_{3})/2}{2π})^{2}(\frac{1}{2} − \frac{1}{32}([θ_{1} − θ_{3}]/2 + (θ_{2} − θ_{3})/2)^{2}).

Averaging over all permutations of θ_{1}, θ_{2}, θ_{3}, we arrive at the function (1/6)(e^{−α[π−θ_{3}]/2} + (2/3)e^{−αθ_{3}/4}), which is minimized over all 0 ≤ θ_{3} ≤ π at the value (1/6)3^{1/3}e^{−απ/6} when 2 log 3/π ≤ α, or θ_{3} = 0 gets the minimum value of (1/6)((2/3)+e^{−πα/2}) when α < 2 log 3/π. In summary,

−3F (2π/3) + ∑_{i=1}^{3} F (θ_{i}) ≤ ∑_{1≤i<j≤3} ( − 5/18 + (1/6)((2/3) + e^{− \frac{ρrs}{1−ρ^{2}} \frac{π}{2}} )1_{\{ \frac{ρrs}{1−ρ^{2}} ≤ \frac{2 log 3}{π} \}}

+ (1/6)3^{1/3}e^{− \frac{ρrs}{1−ρ^{2}} \frac{π}{6}} 1_{\{ \frac{ρrs}{1−ρ^{2}} > \frac{2 log 3}{π} \}}) · (.19)(\frac{θ_{i} − θ_{j}}{2π} )^{2}.

Finally, we use the elementary inequality

∑_{1≤i<j≤3} (\frac{θ_{i} − θ_{j}}{2π} )^{2} ≥ 3 ∑_{i=1}^{3} (\frac{θ_{i}}{2π} − 1/3)^{2},

(actually an equality) valid for all θ_{1}, θ_{2}, θ_{3} ≥ 0 with ∑_{i=1}^{3} θ_{i} = 2π, to get

−3F (2π/3) + ∑_{i=1}^{3} F (θ_{i}) ≤ ∑_{1≤i<j≤3} ( − 5/18 + (1/6)((2/3) + e^{− \frac{ρrs}{1−ρ^{2}} \frac{π}{2}} )1_{\{ \frac{ρrs}{1−ρ^{2}} ≤ \frac{2 log 3}{π} \}}

+ (1/6)3^{1/3}e^{− \frac{ρrs}{1−ρ^{2}} \frac{π}{6}} 1_{\{ \frac{ρrs}{1−ρ^{2}} > \frac{2 log 3}{π} \}}) · (.57) ∑_{i=1}^{3} (\frac{θ_{i}}{2π} − 1/3)^{2}.

A slightly larger upper bound is

−3F (2π/3) + ∑_{i=1}^{3} F (θ_{i}) ≤ \frac{5}{18} · (.57)( − 1 + (1 − \frac{3^{4/3}}{5} )e^{− \frac{ρrs}{1−ρ^{2}} \frac{π}{2}}

+ \frac{3^{4/3}}{5} e^{− \frac{ρrs}{1−ρ^{2}} \frac{π}{6}} ) ∑_{i=1}^{3} (\frac{θ_{i}}{2π} − 1/3)^{2}.

The proof is completed. □

4. Stability Estimates

In Section 3, we gave derivative estimates for the mean subtracted spherical noise stability (23) for intervals in ℝ/2πℤ. However, these derivative estimates do not apply for intervals of length larger than π. In this section, using more direct computations, we consider the mean subtracted spherical noise stability of partitions of ℝ/2πℤ into three disjoint intervals, where one of the intervals has length larger than π. Getting good constants in Lemma 4.1 below requires considering several different cases in a rather tedious manner. We will eventually circumvent Lemma 4.1 with a numerical computation, but we still prove Lemma 4.1 to show that a rigorous (non-numerical) bound can be achieved, with a constant that is worse by a multiplicative factor of about 1/2.

Lemma 4.1. Let θ_{1}, θ_{2}, θ_{3} ≥ 0 with θ_{1} + θ_{2} + θ_{3} = 2π. Denote

F (θ) := \frac{∫_{a=0}^{a=θ} ∫_{b=0}^{b=θ} e^{\frac{ρrs cos(a−b)}{1−ρ^{2}}} dadb}{2π ∫_{0}^{2π} e^{\frac{ρrs cos a}{1−ρ^{2}}} da} − (\frac{θ}{2π} )^{2}.

If θ_{1} ≥ π, then

−3F (2π/3) + ∑_{i=1}^{3} F (θ_{i}) ≤ −\frac{1}{π^{2}} \frac{13}{9}λ_{1,n}^{r,s} ∑_{i=1}^{3} (\frac{θ_{i}}{2π} − 1/3)^{2}.

Proof. The function F satisfies F′(0) = F′(π) = 0, F′′(θ) > 0 for θ > 0 near zero, and then F′′(θ) < 0 for all larger θ < π. It follows that F is strictly increasing for all θ ∈ [0, π]. Also, since F′′ is monotone decreasing, the function θ ↦ F (θ_{1} − θ) + F (θ) is maximized at either the midpoint or endpoint of θ ∈ [0, θ_{1}]. (Either this function has positive second derivative everywhere, or it is positive except for an interval containing the midpoint, where it is negative, and we know the midpoint is a critical point itself.)

Case 1. If 5π/3 ≥ θ_{1} ≥ 4π/3, then from the monotonicity properties of F, ∑_{i=1}^{3} F (θ_{i}) is largest when θ_{1} = 4π/3. To find the values of θ_{2}, θ_{3} that make ∑_{i=1}^{3} F (θ_{i}) largest, we use Lemma 3.1, (and F (a) = F (2π − a) ∀ 0 ≤ a ≤ 2π, which follows by (9)), to get

∑_{i=1}^{3} F (θ_{i}) ≤ F (4π/3) + max(F (2π/3), 2F (π/3)) = F (2π/3) + max(F (2π/3), 2F (π/3)).

We then have

−3F (2π/3) + ∑_{i=1}^{3} F (θ_{i}) ≤ max(−F (2π/3), 2(F (π/3) − F (2π/3)))
= − min(F (2π/3), 2(F (π/3) − F (2π/3))).

Using (11), we can estimate

F (2π/3) ≥ \frac{3}{2π^{2}} (λ_{1,n}^{r,s} + \frac{1}{4}λ_{2,n}^{r,s} + \frac{1}{16}λ_{4,n}^{r,s} + \frac{1}{25}λ_{5,n}^{r,s}).  (27)
2[F (2π/3) − F (π/3)] ≥ \frac{2}{π^{2}} (\frac{7}{9}λ_{1,n}^{r,s} + \frac{1}{25}λ_{5,n}^{r,s}).  (28)

Then

min(F (2π/3), 2(F (π/3) − F (2π/3))) ≥ \frac{3}{2π^{2}} (λ_{1,n}^{r,s} + \frac{1}{25}λ_{5,n}^{r,s})

So,

− 3F (2π/3) + ∑_{i=1}^{3} F (θ_{i}) ≤ −\frac{3}{2π^{2}} (λ_{1,n}^{r,s} + \frac{1}{25}λ_{5,n}^{r,s}).  (29)

Also, by assumption on θ_{1},

∑_{i=1}^{3} (\frac{θ_{i}}{2π} − 1/3)^{2} ≤ (1/2)^{2} + (1/6)^{2} + (1/3)^{2} = 7/18.

In summary, combining with (29),

−3F (2π/3)+∑_{i=1}^{3} F (θ_{i}) ≤ −\frac{3}{2π^{2}} (λ_{1,n}^{r,s} + \frac{1}{25}λ_{5,n}^{r,s}) ≤ −\frac{18}{7} \frac{3}{2π^{2}} (λ_{1,n}^{r,s} + \frac{1}{25}λ_{5,n}^{r,s}) ∑_{i=1}^{3} (\frac{θ_{i}}{2π} −1/3)^{2}.

(30)

Case 2. If θ_{1} ≥ 5π/3, then by Lemma 3.1, we have (using F (a) = F (2π − a) for all 0 ≤ a ≤ 2π, which follows by (9)),

∑_{i=1}^{3} F (θ_{i}) ≤ F (5π/3) + max(F (π/3), 2F (π/6)) = F (π/3) + max(F (π/3), 2F (π/6)).

Using (11), we then have the estimate

\begin{matrix}− 3F (2π/3) + ∑_{i=1}^{3} F (θ_{i}) ≤ −3F (2π/3) + F (π/3) + max(F (π/3), 2F (π/6)) \\ ≤ max ( − F (2π/3) − 2[F (2π/3) − F (π/3)] , \\ − F (2π/3) + F (π/3) − 2[F (2π/3) − F (π/6)]). \end{matrix} (31)

Adding (27) and (28),

− F (2π/3) − 2[F (2π/3) − F (π/3)] ≤ −\frac{3}{π^{2}} λ_{1,n}^{r,s}.  (32)

Using (11), we can estimate

− π^{2}[F (2π/3) − F (π/6)]

= −\frac{1 + \sqrt{3}}{2} \frac{λ_{1,n}^{r,s}}{1} − \frac{λ_{2,n}^{r,s}}{4} + \frac{λ_{3,n}^{r,s}}{9} − \frac{1 − \sqrt{3}}{2} \frac{λ_{5,n}^{r,s}}{25} + 2\frac{λ_{6,n}^{r,s}}{36} − \frac{1 − \sqrt{3}}{2} \frac{λ_{7,n}^{r,s}}{49} + \frac{λ_{9,n}^{r,s}}{81} + ⋯

≤ −1.44λ_{1,n}^{r,s}.

Adding this to (28),

−F (2π/3) + F (π/3) − 2[F (2π/3) − F (π/6)] ≤ −\frac{2.44}{π^{2}}λ_{1,n}^{r,s}.

Combining with (32) in (31),

−3F (2π/3) + ∑_{i=1}^{3} F (θ_{i}) ≤ −\frac{2.44}{π^{2}}λ_{1,n}^{r,s}.

Also, ∑_{i=1}^{3} (\frac{θ_{i}}{2π} − 1/3)^{2} ≤ (2/3)^{2} + 2(1/3)^{2} = 2/3. In summary,

− 3F (2π/3) + ∑_{i=1}^{3} F (θ_{i}) ≤ −\frac{2.44}{π^{2}}λ_{1,n}^{r,s} ≤ −\frac{7.32}{2π^{2}}λ_{1,n}^{r,s} ∑_{i=1}^{3} (\frac{θ_{i}}{2π} − 1/3)^{2}.  (33)

Case 3. If 4π/3 ≥ θ_{1} ≥ π and θ_{2} − θ_{3} ≥ π/2, then by Lemma 3.1, we have (using F (a) = F (2π − a) for all 0 ≤ a ≤ 2π, which follows by (9)),

∑_{i=1}^{3} F (θ_{i}) ≤ max(2F (π), F (π) + F (π/4) + F (3π/4)).

Using (11) (or (45) below), we can estimate

−3F (2π/3) + 2F (π) ≤ −\frac{1}{2π^{2}} (λ_{1,n}^{r,s} + λ_{2,n}^{r,s}).

Similarly,

− 3F (2π/3) + F (π) + F (π/4) + F (3π/4) ≤ −\frac{1}{π^{2}} \frac{1}{2}λ_{1,n}^{r,s}.  (34)

In more detail, the coefficient pattern here is 24-periodic by (11), so that

π^{2}(3F (2π/3) − [F (π) + F (π/4) + F (3π/4)])

= \frac{1}{2} \frac{λ_{1,n}^{r,s}}{1} + \frac{7}{2} \frac{λ_{2,n}^{r,s}}{4} − 4\frac{λ_{3,n}^{r,s}}{9} + \frac{5}{2} \frac{λ_{4,n}^{r,s}}{16} + \frac{1}{2} \frac{λ_{5,n}^{r,s}}{25} − 1\frac{λ_{6,n}^{r,s}}{36} + \frac{1}{2} \frac{λ_{7,n}^{r,s}}{49} + \frac{9}{2} \frac{λ_{8,n}^{r,s}}{64}

− 4\frac{λ_{9,n}^{r,s}}{81} + \frac{7}{2} \frac{λ_{10,n}^{r,s}}{100} + \frac{1}{2} \frac{λ_{11,n}^{r,s}}{121} − 2\frac{λ_{12,n}^{r,s}}{144} + \frac{1}{2} \frac{λ_{13,n}^{r,s}}{169} + \frac{7}{2} \frac{λ_{14,n}^{r,s}}{196} − 4\frac{λ_{15,n}^{r,s}}{225} + \frac{9}{2} \frac{λ_{16,n}^{r,s}}{256}

+ \frac{1}{2} \frac{λ_{17,n}^{r,s}}{289} − 1\frac{λ_{18,n}^{r,s}}{324} + \frac{1}{2} \frac{λ_{19,n}^{r,s}}{361} + \frac{5}{2} \frac{λ_{20,n}^{r,s}}{400} − 4\frac{λ_{21,n}^{r,s}}{441} + \frac{7}{2} \frac{λ_{22,n}^{r,s}}{484} + \frac{1}{2} \frac{λ_{23,n}^{r,s}}{529} + 0\frac{λ_{24,n}^{r,s}}{576} + ⋯

From the seventh term onwards, the sum of the coefficients is nonnegative by (18). Then the sum of the first six terms is bounded as in (34), using (18) again.So,

−3F (2π/3) + ∑_{i=1}^{3} F (θ_{i}) ≤ −\frac{1}{π^{2}} \frac{1}{2}λ_{1,n}^{r,s}.

Also, ∑_{i=1}^{3} (\frac{θ_{i}}{2π} − 1/3)^{2} ≤ 2(1/3)^{2} = 2/9. In summary,

− 3F (2π/3) + ∑_{i=1}^{3} F (θ_{i}) ≤ −\frac{1}{π^{2}} \frac{1}{2}λ_{1,n}^{r,s}. ≤ −\frac{9}{4π^{2}} λ_{1,n}^{r,s} ∑_{i=1}^{3} (\frac{θ_{i}}{2π} − 1/3)^{2}.  (35)

Case 4. If 7π/6 ≥ θ_{1} ≥ π and θ_{2} − θ_{3} ≤ π/2, then arguing as before,

∑_{i=1}^{3} F (θ_{i}) ≤ max(F (π) + 2F (π/2), F (π) + F (π/4) + F (3π/4)).

The second term is bounded already in (34). For the first term, we have by (11)

− 3F (2π/3) + F (π) + F (π/4) + F (3π/4) ≤ −\frac{1}{π^{2}} \frac{13}{72}λ_{1,n}^{r,s}.  (36)

In more detail, the coefficient pattern here is 12-periodic by (11), so that

π^{2}(3F (2π/3) − [F (π) + 2F (π/2)])

= \frac{1}{2} \frac{λ_{1,n}^{r,s}}{1} + \frac{1}{2} \frac{λ_{2,n}^{r,s}}{4} − 4\frac{λ_{3,n}^{r,s}}{9} + \frac{9}{2} \frac{λ_{4,n}^{r,s}}{16} + \frac{1}{2} \frac{λ_{5,n}^{r,s}}{25} − 4\frac{λ_{6,n}^{r,s}}{36}

+ \frac{1}{2} \frac{λ_{7,n}^{r,s}}{49} + \frac{9}{2} \frac{λ_{8,n}^{r,s}}{64} − 4\frac{λ_{9,n}^{r,s}}{81} + \frac{1}{2} \frac{λ_{10,n}^{r,s}}{100} + \frac{1}{2} \frac{λ_{11,n}^{r,s}}{121} + 0\frac{λ_{12,n}^{r,s}}{144} + · · · .

From the fourth term onwards, the sum of the coefficients is nonnegative by(18). Then the sum of the first three terms is bounded as in (36), using (18) again.So, combining (36) and (34)

−3F (2π/3) + ∑_{i=1}^{3} F (θ_{i}) ≤ −\frac{1}{π^{2}} \frac{13}{72}λ_{1,n}^{r,s}.

Also, ∑_{i=1}^{3} (\frac{θ_{i}}{2π} − 1/3)^{2} ≤ 2(1/4)^{2} = 1/8. In summary,

− 3F (2π/3) + ∑_{i=1}^{3} F (θ_{i}) ≤ −\frac{1}{π^{2}} \frac{13}{72}λ_{1,n}^{r,s}. ≤ −\frac{1}{π^{2}} \frac{13}{9}λ_{1,n}^{r,s} ∑_{i=1}^{3} (\frac{θ_{i}}{2π} − 1/3)^{2}.  (37)

Case 5. If 4π/3 ≥ θ_{1} ≥ 7π/6 and θ_{2} − θ_{3} ≤ π/2,

∑_{i=1}^{3} F (θ_{i}) ≤ max(F (7π/6) + 2F (5π/12), F (7π/6) + F (π/6) + F (2π/3))
= max(F (5π/6) + 2F (5π/12), F (5π/6) + F (π/6) + F (2π/3)).

For the first term, we have by (11)

− 3F (2π/3) + F (5π/6) + 2F (5π/12) ≤ −\frac{1}{π^{2}} (.728)λ_{1,n}^{r,s}.  (38)

In more detail, the coefficient pattern here is 24-periodic by (11), so that

π^{2}(3F (2π/3) − [F (5π/6) + 2F (5π/12)])

= 1.1516 … \frac{λ_{1,n}^{r,s}}{1} + (2 − \sqrt{3})\frac{λ_{2,n}^{r,s}}{4} − (3 + \sqrt{2})\frac{λ_{3,n}^{r,s}}{9} + 2\frac{λ_{4,n}^{r,s}}{16}

+ 4.29 … \frac{λ_{5,n}^{r,s}}{25} − 4\frac{λ_{6,n}^{r,s}}{36} + .434 … \frac{λ_{7,n}^{r,s}}{49} + 0\frac{λ_{8,n}^{r,s}}{64}

− (3 − \sqrt{2})\frac{λ_{9,n}^{r,s}}{81} + (2 − \sqrt{3})\frac{λ_{10,n}^{r,s}}{100} + .116 … \frac{λ_{11,n}^{r,s}}{121} − 4\frac{λ_{12,n}^{r,s}}{144}

+ .116 … \frac{λ_{13,n}^{r,s}}{169} + (2 − \sqrt{3})\frac{λ_{14,n}^{r,s}}{196} − (3 − \sqrt{2})\frac{λ_{15,n}^{r,s}}{225} + 0\frac{λ_{16,n}^{r,s}}{256}

+ .434 … \frac{λ_{17,n}^{r,s}}{289} − 4\frac{λ_{18,n}^{r,s}}{324} + 4.29 … \frac{λ_{19,n}^{r,s}}{361} + 2\frac{λ_{20,n}^{r,s}}{400}

− (3 + \sqrt{2})\frac{λ_{21,n}^{r,s}}{441} + (2 − \sqrt{3})\frac{λ_{22,n}^{r,s}}{484} + 1.1516 … \frac{λ_{23,n}^{r,s}}{529} + 0\frac{λ_{24,n}^{r,s}}{576} + · · · .

From the nineteenth term onwards, the sum of the coefficients is nonnegative, so (18) implies that these terms have a nonnegative sum (over a period of 24 terms, the sum of coefficients is 2, and terms four through eighteen have a nonnegative sum.)

For the second term, we have by (11)

− 3F (2π/3) + [F (5π/6) + F (π/6) + F (2π/3)] ≤ −\frac{1}{π^{2}} λ_{1,n}^{r,s}.  (39)

In more detail, the coefficient pattern here is 12-periodic by (11), so that

π^{2}(3F (2π/3) − [F (2π/3) + F (5π/6) + F (π/6)])

= \frac{λ_{1,n}^{r,s}}{1} + 2\frac{λ_{2,n}^{r,s}}{4} − 2\frac{λ_{3,n}^{r,s}}{9} + 0\frac{λ_{4,n}^{r,s}}{16} + 1\frac{λ_{5,n}^{r,s}}{25} − 4\frac{λ_{6,n}^{r,s}}{36}

+ \frac{λ_{7,n}^{r,s}}{49} + 0\frac{λ_{8,n}^{r,s}}{64} − 2\frac{λ_{9,n}^{r,s}}{81} + 2\frac{λ_{10,n}^{r,s}}{100} + \frac{λ_{11,n}^{r,s}}{121} + 0\frac{λ_{12,n}^{r,s}}{144} + · · · .

From the tenth term onwards, the sum of the coefficients is nonnegative, so (18) implies that these terms have a nonnegative sum (over a period of 12 terms, the sum of coefficients is 0, and terms two through nine have a nonnegative sum.)

So, combining (38) and (39),

−3F (2π/3) + ∑_{i=1}^{3} F (θ_{i}) ≤ −\frac{1}{π^{2}} (.728)λ_{1,n}^{r,s}.

Also, ∑_{i=1}^{3} (\frac{θ_{i}}{2π} − 1/3)^{2} ≤ (1/3)^{2} + 1/12^{2} + 1/6^{2} = 7/48. In summary,

− 3F (2π/3) + ∑_{i=1}^{3} F (θ_{i}) ≤ −\frac{1}{π^{2}} (.728)λ_{1,n}^{r,s}. ≤ −\frac{1}{π^{2}} (.728)\frac{48}{7}λ_{1,n}^{r,s} ∑_{i=1}^{3} (\frac{θ_{i}}{2π} − 1/3)^{2}. (40)

Combining Cases 1 through 5.

Combining (30), (33), (35), (37) and (40), we have, whenever θ_{1} ≥ π,

−3F (2π/3) + ∑_{i=1}^{3} F (θ_{i}) ≤ −\frac{1}{π^{2}} \frac{13}{9}λ_{1,n}^{r,s} ∑_{i=1}^{3} (\frac{θ_{i}}{2π} − 1/3)^{2}.

□

Lemma 3.3 and Lemma 4.1 and the following inequality imply Corollary 4.2 below.

−\frac{x}{1/2 + \sqrt{9/4 + x^{2}}} ≤ (3/4)( − 1 + (1 − \frac{3^{4/3}}{5} )e^{−x \frac{π}{2}} + \frac{3^{4/3}}{5} e^{−x \frac{π}{6}} ), ∀ x > 0.

Corollary 4.2. Let θ_{1}, θ_{2}, θ_{3} ≥ 0. Define F as in (23). Then

−3F (2π/3) + ∑_{i=1}^{3} F (θ_{i}) ≤ −\frac{1}{π^{2}} \frac{13}{9} \frac{3}{4}(1 − (1 − \frac{3^{4/3}}{5} )e^{− \frac{ρrs}{1−ρ^{2}} \frac{π}{2}} − \frac{3^{4/3}}{5} e^{− \frac{ρrs}{1−ρ^{2}} \frac{π}{6}} ) ∑_{i=1}^{3} (\frac{θ_{i}}{2π} − 1/3)^{2}.

5. Change of Measure

The following inequality allows us to show that the first term in (2) is smaller than the second one. The proof amounts to an elementary truncated heat kernel bound, though with a change of measure using the λ_{1,n}^{r,s} term from (14).

Lemma 5.1. Let f: ℝ^{2} → Δ_{3} be a radial function (for any r > 0, the function f|_{rS^{1}} is constant). Denote 𝔼_{γ}f := ∫_{ℝ^{2}} f(x)γ_{2}(x) dx. Let ϕ: ℝ^{2} → (0, ∞). Then

|∫_{ℝ^{2}}⟨f(x) − 𝔼_{γ}f, T_{ρ}[f − 𝔼_{γ}f](x)⟩γ_{2}(x) dx|

≤ ∫_{ℝ^{2}} ϕ(x) ∥f(x) − 𝔼_{γ}f∥^{2} γ_{2}(x) dx ∑_{d≥2: d even} ρ^{d} ∑_{k∈(2ℕ)^{2} : ∥k∥_{1}=d} ∫_{ℝ^{2}} |\sqrt{k!}h_{k}(x)\frac{1}{\sqrt{ϕ(x)}}|^{2} γ_{2}(x) dx.

In particular, if ϕ(x) = (1 − e^{−ρ∥x∥/2}) for all x ∈ ℝ^{2}, and 0 < ρ < 1/7, then

|∫_{ℝ^{2}}⟨f(x) − 𝔼_{γ}f, T_{ρ}[f − 𝔼_{γ}f](x)⟩γ_{2}(x) dx| ≤ 2.5(ρ + ρ^{2}) ∫_{ℝ^{2}} ϕ(x) ∥f(x) − 𝔼_{γ}f∥^{2} γ_{2}(x)dx.

Proof. Let h_{0}, h_{1}, …: ℝ → ℝ be the Hermite polynomials with h_{m}(x) = ∑_{k=0}^{⌊m/2⌋} \frac{x^{m−2k}(−1)^{k}2^{−k}}{k!(m−2k)!} ∀ m ≥ 0, m ∈ ℤ, ∀ x ∈ ℝ. It is well known [Hei14] that \{\sqrt{m!}h_{m}\}_{m≥0} is an orthonormal basis of the Hilbert space of functions ℝ → ℝ equipped with the inner product ⟨g, h⟩ := ∫_{ℝ} g(x)h(x)γ_{2}(x) dx. For any k ∈ ℕ^{2}, define k! := k_{1}! · k_{2}!, and let ∥k∥_{1} := |k_{1}| + |k_{2}|. Let α_{k} ∈ ℝ to be determined later. Since f is radial, the Hermite-Fourier expansion of f − 𝔼_{γ}f is

∫_{ℝ^{2}}⟨f(x) − 𝔼_{γ}f, T_{ρ}[f − 𝔼_{γ}f](x)⟩γ_{2}(x) dx

= ∑_{d≥2: d even} ρ^{d} ∑_{k∈(2ℕ)^{2} : ∥k∥_{1}=d} ∥∫_{ℝ^{2}} \sqrt{k!}h_{k}(x)(f(x) − 𝔼_{γ}f)γ_{2}(x) dx∥^{2}

= ∑_{d≥2: d even} ρ^{d} ∑_{k∈(2ℕ)^{2} : ∥k∥_{1}=d} ∥∫_{ℝ^{2}} \sqrt{k!}[h_{k}(x) − α_{k}](f(x) − 𝔼_{γ}f)γ_{2}(x) dx∥^{2}

= ∑_{d≥2: d even} ρ^{d} ∑_{k∈(2ℕ)^{2} : ∥k∥_{1}=d} ∥∫_{ℝ^{2}} \sqrt{k!}[h_{k}(x) − α_{k}]\frac{1}{\sqrt{ϕ(x)}}\sqrt{ϕ(x)}(f(x) − 𝔼_{γ}f)γ_{2}(x) dx∥^{2}

≤ ∑_{\begin{matrix}d≥2: \\ d even \end{matrix}} ρ^{d} ∑_{\begin{matrix}k∈(2ℕ)^{2} : \\ ∥k∥_{1}=d \end{matrix}} ∫_{ℝ^{2}} |\sqrt{k!}[h_{k}(x) − α_{k}]\frac{1}{\sqrt{ϕ(x)}}|^{2} γ_{2}(x) dx · ∫_{ℝ^{2}} ϕ(x) ∥f(x) − 𝔼_{γ}f∥^{2} γ_{2}(x) dx

= ∫_{ℝ^{2}} ϕ(x) ∥f(x) − 𝔼_{γ}f∥^{2} γ_{2}(x) dx · ∑_{\begin{matrix}d≥2: \\ d even \end{matrix}} ρ^{d} ∑_{\begin{matrix}k∈(2ℕ)^{2} : \\ ∥k∥_{1}=d \end{matrix}} ∫_{ℝ^{2}} |\sqrt{k!}[h_{k}(x) − α_{k}]\frac{1}{\sqrt{ϕ(x)}}|^{2} γ_{2}(x) dx.

To conclude, it remains to bound the last term. We use the inequality

\frac{r}{1 − e^{−ρr/2}} ≤ r + \frac{2}{ρ}, ∀ r > 0,

which follows from the inequality a ≤ e^{a} − 1 for all a > 0 (where a = ρr/2), along with

\frac{r}{1 − e^{−ρr/2}} ≤ r/1.7 + \frac{2}{ρ}, ∀ 0 < r < 1/ρ,

we obtain (using G_{ρ}(x, y) = γ_{2}(x)γ_{2}(y) ∑_{d≥0} ρ^{d} ∑_{k∈ℕ^{2} : ∥k∥_{1}=d} h_{k}(x)h_{k}(y)k!, i.e. the expansion of the Mehler kernel from (4) into Hermite polynomials), and choosing α_{k} := α·1_{{k=(2,0)}},

∑_{d≥2: d even} ρ^{d} ∑_{k∈(2ℕ)^{2} : ∥k∥_{1}=d} ∫_{ℝ^{2}} |\sqrt{k!}[h_{k}(x) − α_{k}]\frac{1}{\sqrt{ϕ(x)}}|^{2} γ_{2}(x) dx

= ∫_{ℝ^{2}} \frac{1}{ϕ(x)}[2π \frac{G_{ρ}(x, x) + G_{ρ}(x, −x)}{2e^{−∥x∥^{2}/2}} − γ_{2}(x) − 2ρ^{2}α(x_{1}^{2} − 1)γ_{2}(x) + α^{2}ρ^{2}γ_{2}(x)] dx

= ∫_{ℝ^{2}} \frac{1}{ϕ(x)}[\frac{1}{2π} \frac{1}{1 − ρ^{2}} e^{− \frac{∥x∥^{2}}{1−ρ^{2}}} \frac{e^{\frac{ρ∥x∥^{2}}{1−ρ^{2}}} + e^{− \frac{ρ∥x∥^{2}}{1−ρ^{2}}}}{2e^{−r^{2}/2}} − γ_{2}(x) − 2αρ^{2}(x_{1}^{2} − 1)γ_{2}(x) + α^{2}ρ^{2}γ_{2}(x)] dx

= ∫_{r=0}^{∞}((r/1.7)1_{r<1/ρ} + r1_{r>1/ρ} + 2/ρ)\frac{1}{2(1 − ρ^{2})}

· ( − 2(1 − ρ^{2})(1 − α^{2}ρ^{2} + 2αρ^{2}(r^{2}/2 − 1))e^{−r^{2}/2} + e^{−r^{2} \frac{1−ρ}{1−ρ^{2}}} e^{r^{2}/2} + e^{−r^{2} \frac{1+ρ}{1−ρ^{2}}} e^{r^{2}/2}) dr

= ∫_{r=0}^{∞}((r/1.7)1_{r<1/ρ} + r1_{r>1/ρ} + 2/ρ)\frac{1}{2(1 − ρ^{2})}

· ( − 2(1 − ρ^{2})(1 − α^{2}ρ^{2} + 2αρ^{2}(r^{2}/2 − 1))e^{−r^{2}/2} + e^{−r^{2}(\frac{1}{1+ρ} − \frac{1}{2})} + e^{−r^{2}(\frac{1}{1−ρ} − \frac{1}{2})}) dr

= \frac{1}{2(1 − ρ^{2})} \frac{1}{1.7}( − 2(1 − ρ^{2})(1 − α^{2}ρ^{2}) + \frac{1}{2[\frac{1}{1+ρ} − \frac{1}{2}]} + \frac{1}{2[\frac{1}{1−ρ} − \frac{1}{2}]})

+ \frac{1}{2(1 − ρ^{2})}(1 − \frac{1}{1.7})( − 2(1 − ρ^{2})(1 − α^{2}ρ^{2} − α)(−e^{−1/(2ρ^{2})})

+ \frac{1}{2[\frac{1}{1+ρ} − \frac{1}{2}]}(−e^{− \frac{1}{ρ^{2}} [ \frac{1}{1+ρ} − \frac{1}{2} ]}) + \frac{1}{2[\frac{1}{1−ρ} − \frac{1}{2}]}(−e^{− \frac{1}{ρ^{2}} [ \frac{1}{1−ρ} − \frac{1}{2} ]}))

+ \frac{1}{ρ} \frac{1}{1 − ρ^{2}} \sqrt{\frac{π}{2}} ( − 2(1 − ρ^{2})(1 − α^{2}ρ^{2} − αρ^{2}) + \frac{1}{\sqrt{2[\frac{1}{1+ρ} − \frac{1}{2}]}} + \frac{1}{\sqrt{2[\frac{1}{1−ρ} − \frac{1}{2}]}}).

When α = −1/2 and ρ < 1/7, this quantity is upper bounded by 2.5(ρ + ρ^{2}). □

It would be interesting to find the optimal constant in Lemma 5.1, since improving the constants here would also improve the constants in Theorem 1.5.

For the negative correlation case of Theorem 1.5, we require a bilinear version of Lemma 5.1 above. The proof of Lemma 5.2 is similar to that of Lemma 5.1, though the constants in Lemma 5.1 are slightly improved, hence our repetition of many of the same steps with different results.

Lemma 5.2. Let f̃, g̃: ℝ^{2} → Δ_{3}. Define

ϕ(x) = \frac{ρ}{1 − ρ^{2}} ∥x∥ e^{− \frac{(1.1ρ∥x∥)^{2}}{1−ρ^{2}} − \frac{1.1ρ}{1−ρ^{2}} ∥x∥}, ∀ x ∈ ℝ^{2}.

If 0 < ρ < .1, then

∑_{d≥2} ρ^{d} ∑_{k∈ℕ^{2} : ∥k∥_{1}=d} |⟨ ∫_{ℝ^{2}} \sqrt{k!}h_{k}(x)f̃(x)γ_{2}(x) dx, ∫_{ℝ^{2}} \sqrt{k!}h_{k}(y)g̃(y)γ_{2}(y) dy⟩|

≤ (5ρ + 8ρ^{2}) · \frac{1}{2}( ∫_{ℝ^{2}} ϕ(x)∥f̃(x)∥^{2}γ_{2}(x) dx + ∫_{ℝ^{2}} ϕ(x)∥g̃(x)∥^{2}γ_{2}(x) dx).

Proof. We will show that

\begin{matrix}∑_{d≥2} ρ^{d} ∑_{k∈ℕ^{2} : ∥k∥_{1}=d} ∥∫_{ℝ^{2}} \sqrt{k!}h_{k}(x)f̃(x)γ_{2}(x) dx∥^{2} \\ ≤ (5ρ + 8ρ^{2}) ∫_{ℝ^{2}} ϕ(x)∥f̃(x)∥^{2}γ_{2}(x)dx. \end{matrix}  (41)

The conclusion of the Lemma then follows from this inequality and the Cauchy-Schwarz inequality. We therefore prove (41).

Let h_{0}, h_{1}, …: ℝ → ℝ be the Hermite polynomials with h_{m}(x) = ∑_{k=0}^{⌊m/2⌋} \frac{x^{m−2k}(−1)^{k}2^{−k}}{k!(m−2k)!} for all integers m ≥ 0. It is well known [Hei14] that \{\sqrt{m!}h_{m}\}_{m≥0} is an orthonormal basis of the Hilbert space of functions ℝ → ℝ equipped with the inner product ⟨g, h⟩ := ∫_{ℝ} g(x)h(x)γ_{2}(x) dx. For any k ∈ ℕ^{2}, define k! := k_{1}! · k_{2}!, and define ∥k∥_{1} := |k_{1}| + |k_{2}|.

∑_{d≥2} ρ^{d} ∑_{k∈ℕ^{2} : ∥k∥_{1}=d} ∥∫_{ℝ^{2}} \sqrt{k!}h_{k}(x)f̃(x)γ_{2}(x) dx∥^{2}

= ∑_{d≥2} ρ^{d} ∑_{k∈ℕ^{2} : ∥k∥_{1}=d} ∥∫_{ℝ^{2}} \sqrt{k!}h_{k}(x)\frac{1}{\sqrt{ϕ(x)}}\sqrt{ϕ(x)}f̃(x)γ_{2}(x) dx∥^{2}

≤ ∑_{d≥2} ρ^{d} ∑_{k∈ℕ^{2} : ∥k∥_{1}=d} ∫_{ℝ^{2}} |\sqrt{k!}h_{k}(x)\frac{1}{\sqrt{ϕ(x)}}|^{2} γ_{2}(x) dx · ∫_{ℝ^{2}} ϕ(x)∥f̃(x)∥^{2}γ_{2}(x) dx

= ∫_{ℝ^{2}} ϕ(x)∥f̃(x)∥^{2}γ_{2}(x) dx · ∑_{d≥2} ρ^{d} ∑_{k∈ℕ^{2} : ∥k∥_{1}=d} ∫_{ℝ^{2}} |\sqrt{k!}h_{k}(x)\frac{1}{\sqrt{ϕ(x)}}|^{2} γ_{2}(x) dx.

It remains to bound the final term. Using the expansion of the Mehler kernel from (4) into Hermite polynomials, i.e. G_{ρ}(x, y) = γ_{2}(x)γ_{2}(y) ∑_{d≥0} ρ^{d} ∑_{k∈ℕ^{2} : ∥k∥_{1}=d} h_{k}(x)h_{k}(y)k!,

∑_{d≥2} ρ^{d} ∑_{k∈ℕ^{2} : ∥k∥_{1}=d} ∫_{ℝ^{2}} |\sqrt{k!}h_{k}(x)\frac{1}{\sqrt{ϕ(x)}}|^{2} γ_{2}(x) dx

= ∫_{ℝ^{2}} \frac{1}{ϕ(x)}[2π \frac{G_{ρ}(x, x)}{e^{−∥x∥^{2}/2}} − γ_{2}(x) − ρ ∥x∥^{2} γ_{2}(x)] dx

= \frac{1}{1 − ρ^{2}} ∫_{ℝ^{2}} \frac{1}{ϕ(x)}[\frac{1}{2π} e^{− \frac{∥x∥^{2}(1−ρ−(1−ρ^{2})/2)}{1−ρ^{2}}} − (1 − ρ^{2})(1 + ρ ∥x∥^{2})γ_{2}(x)] dx

≤ \frac{1}{1 − ρ^{2}} ∫_{r=0}^{∞} \frac{1 − ρ^{2}}{ρ} \frac{r}{r}e^{− \frac{(1.1ρr)^{2}}{1−ρ^{2}} − \frac{1.1ρ}{1−ρ^{2}} r}[e^{− \frac{r^{2}(1/2−ρ+ρ^{2}/2)}{1−ρ^{2}}} − (1 − ρ^{2})(1 + ρr^{2})e^{−r^{2}/2}] dr

= \frac{1}{ρ} ∫_{r=0}^{∞} e^{− \frac{(1.1ρr)^{2}}{1−ρ^{2}} − \frac{1.1ρ}{1−ρ^{2}} r}[e^{− \frac{r^{2}(1/2−ρ+ρ^{2}/2)}{1−ρ^{2}}} − (1 − ρ^{2})(1 + ρr^{2})e^{−r^{2}/2}] dr

= \frac{1}{ρ}(e^{\frac{(1.1ρ)^{2}}{4((1.1ρ)^{2}+1/2−ρ+ρ^{2}/2)(1−ρ^{2})}} \sqrt{\frac{1 − ρ^{2}}{(1.1ρ)^{2} + 1/2 − ρ + ρ^{2}/2}} ∫ ∞_{\frac{1.1ρ\sqrt{(1.1ρ)^{2}+1/2−ρ+ρ^{2}/2}}{\sqrt{1−ρ^{2}}}} e^{−r^{2}} dr

− (1 − ρ^{2})e^{\frac{(1.1ρ)^{2}}{4((1.1ρ)^{2}+1/2)(1−ρ^{2})}} \sqrt{\frac{1 − ρ^{2}}{(1.1ρ)^{2} + 1/2}} ∫ ∞_{\frac{1.1ρ\sqrt{(1.1ρ)^{2}+1/2}}{\sqrt{1−ρ^{2}}}} e^{−r^{2}} dr

− (1 − ρ^{2})ρ[\frac{2[((1.1ρ)^{2} + 1/2)/(1 − ρ^{2})] + [1.1ρ/(1 − ρ^{2})]^{2}}{4} e^{\frac{(1.1ρ)^{2}}{4((1.1ρ)^{2}+1/2)(1−ρ^{2})}}

· (\frac{1 − ρ^{2}}{(1.1ρ)^{2} + 1/2})^{5/2} ∫ ∞_{\frac{1.1ρ\sqrt{(1.1ρ)^{2}+1/2}}{\sqrt{1−ρ^{2}}}} e^{−r^{2}} dr + \frac{−1.1ρ/(1 − ρ^{2})}{2[((1.1ρ)^{2} + 1/2)/(1 − ρ^{2})]^{2}} ]).

When ρ < .1, this quantity is upper bounded by 5ρ + 8ρ^{2}.

□

In the following Lemma, if f: ℝ^{2} → [0, 1], we define Proj_{1}(f): ℝ^{2} → ℝ to be equal to the degree one projection of f onto spherical harmonics of a given radius ∥x∥. That is,

\begin{aligned}Proj_{1}(f)(x) & := 2(𝔼_{y∈∥x∥S^{1}}f(y)\frac{y_{1}}{∥x∥})\frac{x_{1}}{∥x∥} \\ & + 2(𝔼_{y∈∥x∥S^{1}}f(y)\frac{y_{2}}{∥x∥})\frac{x_{2}}{∥x∥}, ∀ x = (x_{1}, x_{2}) ∈ ℝ^{2} \ \{0\}. \end{aligned} (42)

Lemma 5.3. Let f, g: ℝ^{2} → Δ_{3}. Define

ϕ(x) = \frac{ρ}{1 − ρ^{2}} ∥x∥ e^{− \frac{(1.1ρ∥x∥)^{2}}{1−ρ^{2}} − \frac{1.1ρ}{1−ρ^{2}} ∥x∥}, ∀ x ∈ ℝ^{2}.

If 0 < ρ < 1/36, then |∫_{ℝ^{2}}⟨Proj_{1}(f), T_{ρ}[Proj_{1}(g)](x)⟩γ_{2}(x) dx|

≤ (\frac{1}{2}\sqrt{\frac{π}{2}} + 1.35ρ)\frac{1}{2}( ∫_{ℝ^{2}} ϕ(x)∥Proj_{1}(f)(x)∥^{2}γ_{2}(x) dx + ∫_{ℝ^{2}} ϕ(x)∥Proj_{1}(g)(x)∥^{2}γ_{2}(x) dx).

Proof. We will show that

|∫_{ℝ^{2}}⟨Proj_{1}(f), T_{ρ}[Proj_{1}(f)](x)⟩γ_{2}(x) dx|

≤ (\frac{1}{2}\sqrt{\frac{π}{2}} + 1.35ρ) ∫_{ℝ^{2}} ϕ(x) ∥Proj_{1}(f)(x)∥^{2} γ_{2}(x)dx.

(43)

The conclusion of the Lemma then follows from this inequality and the Cauchy-Schwarz inequality. We therefore prove (43). We use the Hermite polynomial notation from Lemma 5.2. Since Proj_{1}f is an odd function, its Hermite-Fourier expansion is

∫_{ℝ^{2}}⟨Proj_{1}(f), T_{ρ}[Proj_{1}(f)](x)⟩γ_{2}(x) dx

= ∑_{d≥1: d odd} ρ^{d} ∑_{k∈ℕ^{2} : ∥k∥_{1}=d} ∥∫_{ℝ^{2}} \sqrt{k!}h_{k}(x)Proj_{1}(f)γ_{2}(x) dx∥^{2}

= ∑_{d≥1: d odd} ρ^{d} ∑_{k∈ℕ^{2} : ∥k∥_{1}=d} ∥∫_{ℝ^{2}} \sqrt{k!}[h_{k}(x)]\frac{1}{\sqrt{ϕ(x)}}\sqrt{ϕ(x)}Proj_{1}(f)γ_{2}(x) dx∥^{2}

≤ ∑_{d≥1: d odd} ρ^{d} ∑_{\begin{matrix}k∈ℕ^{2} : \\ ∥k∥_{1}=d \end{matrix}} ∫_{ℝ^{2}} |\sqrt{k!}h_{k}(x)\frac{1}{\sqrt{ϕ(x)}}|^{2} γ_{2}(x) dx · ∫_{ℝ^{2}} ϕ(x) ∥Proj_{1}(f)∥^{2} γ_{2}(x) dx

= ∫_{ℝ^{2}} ϕ(x) ∥Proj_{1}(f)(x)∥^{2} γ_{2}(x) dx · ∑_{d≥1: d odd} ρ^{d} ∑_{\begin{matrix}k∈ℕ^{2} : \\ ∥k∥_{1}=d \end{matrix}} ∫_{ℝ^{2}} |\sqrt{k!}h_{k}(x)\frac{1}{\sqrt{ϕ(x)}}|^{2} γ_{2}(x) dx.

To conclude, it remains to bound the last term. Without loss of generality, we may restrict the sum over k ∈ ℕ^{2} to k ∈ ℕ^{2} \ {(0, 1)} by rotation invariance of the Gaussian measure. We therefore denote

α := ρ ∫_{ℝ^{2}} x_{1}^{2} \frac{1 − ρ}{ρ} \frac{1}{∥x∥}e^{\frac{1.1ρ}{1−ρ^{2}} ∥x∥+ \frac{(1.1ρ∥x∥)^{2}}{1−ρ^{2}}} γ_{2}(x) dx,

and we estimate the last term minus α. Using the expansion of the Mehler kernel from (4) into Hermite polynomials, i.e. G_{ρ}(x, y) = γ_{2}(x)γ_{2}(y) ∑_{d≥0} ρ^{d} ∑_{k∈ℕ^{2} : ∥k∥_{1}=d} h_{k}(x)h_{k}(y)k!,

∑_{d≥1: d odd} ρ^{d} ∑_{\begin{matrix}k∈ℕ^{2} : \\ ∥k∥_{1}=d \end{matrix}} ∫_{ℝ^{2}} |\sqrt{k!}h_{k}(x)\frac{1}{\sqrt{ϕ(x)}}|^{2} γ_{2}(x) dx

= ∫_{ℝ^{2}} \frac{1}{ϕ(x)}[2π \frac{G_{ρ}(x, x) − G_{ρ}(x, −x)}{2e^{−∥x∥^{2}/2}}]dx = ∫_{ℝ^{2}} \frac{1}{ϕ(x)}[\frac{1}{2π} \frac{1}{1 − ρ^{2}} e^{− \frac{∥x∥^{2}}{1−ρ^{2}}} \frac{e^{\frac{ρ∥x∥^{2}}{1−ρ^{2}}} − e^{− \frac{ρ∥x∥^{2}}{1−ρ^{2}}}}{2e^{−∥x∥^{2}/2}} ] dx

= ∫_{r=0}^{∞} \frac{1 − ρ^{2}}{ρ} \frac{1}{r}e^{\frac{1.1ρ}{1−ρ^{2}} r+ \frac{(1.1ρr)^{2}}{1−ρ^{2}}} [\frac{1}{1 − ρ^{2}} e^{− \frac{r^{2}}{1−ρ^{2}}} \frac{e^{\frac{ρr^{2}}{1−ρ^{2}}} − e^{− \frac{ρr^{2}}{1−ρ^{2}}}}{2e^{−r^{2}/2}} ] rdr

= \frac{1}{2ρ} ∫_{r=0}^{∞} [e^{−r^{2} \frac{1−ρ}{1−ρ^{2}} + \frac{r^{2}}{2} + \frac{1.1ρr+(1.1ρ)^{2}r^{2}}{1−ρ^{2}}} − e^{−r^{2} \frac{1+ρ}{1−ρ^{2}} + \frac{r^{2}}{2} + \frac{1.1ρr+(1.1ρ)^{2}r^{2}}{1−ρ^{2}}} ] dr

= \frac{1}{2ρ} ∫_{r=0}^{∞} [e^{− \frac{1}{2} r^{2} \frac{2−2ρ−(1−ρ^{2})−2.42ρ^{2}}{1−ρ^{2}} + \frac{1.1ρ}{1−ρ^{2}} r} − e^{− \frac{1}{2} r^{2} \frac{2+2ρ−(1−ρ^{2})−2.42ρ^{2}}{1−ρ^{2}} + \frac{1.1ρ}{1−ρ^{2}} r}] dr

= \frac{1}{2ρ} ∫_{r=0}^{∞} [e^{− \frac{1}{2} r^{2} \frac{1−2ρ−1.42ρ^{2}}{1−ρ^{2}} + \frac{1.1ρ}{1−ρ^{2}} r} − e^{− \frac{1}{2} r^{2} \frac{1+2ρ−1.42ρ^{2}}{1−ρ^{2}} + \frac{1.1ρ}{1−ρ^{2}} r}] dr

= \frac{1}{2ρ} ∫_{r=0}^{∞} [e^{− \frac{1}{2} \frac{1−2ρ−1.42ρ^{2}}{1−ρ^{2}} (r− \frac{1.1ρ}{1−2ρ−1.42ρ^{2}} )^{2}+ \frac{(1.1ρ)^{2}}{2(1−2ρ−1.42ρ^{2})(1−ρ^{2})}}

− e^{− \frac{1}{2} \frac{1+2ρ−1.42ρ^{2}}{1−ρ^{2}} (r− \frac{1.1ρ}{1+2ρ−1.42ρ^{2}} )^{2}+ \frac{(1.1ρ)^{2}}{2(1+2ρ−1.42ρ^{2})(1−ρ^{2})}} ] dr

= \frac{1}{2ρ}e^{\frac{(1.1ρ)^{2}}{2(1−2ρ−1.42ρ^{2})(1−ρ^{2})}} ∫_{r=− \frac{1.1ρ}{1−2ρ−1.42ρ^{2}}}^{∞} e^{− \frac{1}{2} \frac{1−2ρ−1.42ρ^{2}}{1−ρ^{2}} r^{2}}dr

− \frac{1}{2ρ}e^{\frac{(1.1ρ)^{2}}{2(1+2ρ−1.42ρ^{2})(1−ρ^{2})}} ∫_{r=− \frac{1.1ρ}{1+2ρ−1.42ρ^{2}}}^{∞} e^{− \frac{1}{2} \frac{1+2ρ−1.42ρ^{2}}{1−ρ^{2}} r^{2}}dr

= \frac{1}{2ρ}e^{\frac{(1.1ρ)^{2}}{2(1−2ρ−1.42ρ^{2})(1−ρ^{2})}} \sqrt{\frac{1 − ρ^{2}}{1 − 2ρ − 1.42ρ^{2}}} ∫_{r=− \frac{1.1ρ}{\sqrt{1−2ρ−1.42ρ^{2}}\sqrt{1−ρ^{2}}}}^{∞} e^{− \frac{1}{2} r^{2}}dr

− \frac{1}{2ρ}e^{\frac{(1.1ρ)^{2}}{2(1+2ρ−1.42ρ^{2})(1−ρ^{2})}} \sqrt{\frac{1 − ρ^{2}}{1 + 2ρ − 1.42ρ^{2}}} ∫_{r=− \frac{1.1ρ}{\sqrt{1+2ρ−1.42ρ^{2}}\sqrt{1−ρ^{2}}}}^{∞} e^{− \frac{1}{2} r^{2}}dr.

When 0 < ρ < 1/36, this quantity is bounded by 2.5ρ + \sqrt{π/2}. The α term is similarly bounded below by (1/2)[\sqrt{π/2} + 2.3ρ], so our final bound is at most (1/2)\sqrt{π/2} + 1.35ρ.

□

Lemma 5.4. If f|_{S^{1}} consists of three circular arcs with lengths θ_{1}, θ_{2}, θ_{3}, respectively, then

∫_{S^{1}} ∥Proj_{1}(f − h)∥^{2} dσ ≤ .9555 ∑_{i=1}^{3} (\frac{θ_{i}}{2π} − 1/3)^{2}.

As usual, σ denotes Haar measure on S^{1}.

Lemma 5.4 is verified with the following Matlab program, where the constant .9555 is an upper bound of the vlalue 2(4.715)/π^{2}.

numpts=200;
x=linspace(0 ,2*pi ,numpts);
y=linspace(0 ,2*pi ,numpts);
xv=ones(numpts,1)*x;
yv= y' * ones(1,numpts);
zv=  ((sin(xv/2) - sqrt(3)/2).^2  + (sin(yv/2) - sqrt(3)/2).^2 ...
    + (sin((2*pi - xv - yv)/2) - sqrt(3)/2).^2  ).*(xv+yv<= 2*pi);
zz= ( ( (xv/(2*pi)) - 1/3).^2  +  ( (yv/(2*pi)) - 1/3).^2 +  ...
    ( ((2*pi - xv - yv)/(2*pi)) - 1/3).^2   ).*(xv+yv<= 2*pi);
hold on;
surf(x,y, zv - 4.715*zz);
if sum(sum( zv-4.715*zz >0))==0
    fprintf('Verified\r');  % verify zv< 4.7 zz
end

6. Circular Rearrangement

In this section, we prove the key lemma, that the bilinear noise stability on the sphere S^{1} (minus the measure of the set) is uniquely maximized for a partition into three congruent arcs. After rearranging, this follows from Corollary 4.2.

In the following Lemma, we say A_{1}, A_{2}, A_{3} ⊆ S^{1} is a partition of S^{1} if A_{i} ∩ A_{j} = ∅ for all 1 ≤ i < j ≤ 3 and ∪_{i=1}^{3}A_{i} = S^{1}.

Lemma 6.1 (Circular Rearrangement, Maximization). Let 0 < ρ < 1. Let r, s > 0. Let A_{1}, A_{2}, A_{3} be a partition of S^{1}. Let B_{1}, B_{2}, B_{3} be a partition of S^{1}. Let σ denote the normalized (Haar) probability measure on S^{1}, and define g = g_{ρ,r,s} by (7). Then

∑_{i=1}^{3} ∫_{S^{1}}[1_{A_{i}}(x) − σ(A_{i})]U_{g}[1_{B_{i}} − σ(B_{i})](x) dσ(x)

≤ ∑_{i=1}^{3} ∫_{S^{1}}[1_{D_{i}}(x) − σ(D_{i})]U_{g}[1_{D_{i}} − σ(D_{i})](x) dσ(x)

− (1 − (1 − \frac{3^{4/3}}{5} )e^{− \frac{ρrs}{1−ρ^{2}} \frac{π}{2}} − \frac{3^{4/3}}{5} e^{− \frac{ρrs}{1−ρ^{2}} \frac{π}{6}} )\frac{(.109)}{2} ∑_{i=1}^{3} ((σ(A_{i}) − 1/3)^{2} + (σ(B_{i}) − 1/3)^{2}).

where D_{1}, D_{2}, D_{3} is a partition of S^{1} into three congruent circular arcs (each with angle 2π/3).

Proof. We first show that we may assume A_{i} = B_{i} for all 1 ≤ i ≤ 3. Since λ_{d,2}^{r,s} > 0 for all d ≥ 0 by (19), we can write U_{g} = (\sqrt{U_{g}})^{2}, where \sqrt{U_{g}} is a positive definite operator. Using then the Cauchy-Schwarz inequality and ab ≤ (a^{2} + b^{2})/2 for all a, b ∈ ℝ, we have

∑_{i=1}^{3} ∫_{S^{1}}[1_{A_{i}}(x) − σ(A_{i})]U_{g}[1_{B_{i}} − σ(B_{i})](x) dσ(x)

= ∑_{i=1}^{3} ∫_{S^{1}} \sqrt{U_{g}}[1_{A_{i}}(x) − σ(A_{i})](x)\sqrt{U_{g}}[1_{B_{i}} − σ(B_{i})](x) dσ(x)

≤ ∑_{i=1}^{3} ( ∫_{S^{1}}[\sqrt{U_{g}}[1_{A_{i}}(x) − σ(A_{i})](x)]^{2})^{1/2}( ∫_{S^{1}}[\sqrt{U_{g}}[1_{B_{i}} − σ(B_{i})](x)]^{2} dσ(x))^{1/2}

≤ \frac{1}{2} ∑_{i=1}^{3} ∫_{S^{1}}[1_{A_{i}}(x) − σ(A_{i})]U_{g}[1_{A_{i}} − σ(A_{i})](x) dσ(x)

+ \frac{1}{2} ∑_{i=1}^{3} ∫_{S^{1}}[1_{B_{i}}(x) − σ(B_{i})]U_{g}[1_{B_{i}} − σ(B_{i})](x) dσ(x).

So, the general case of the Lemma follows from the special case that A_{i} = B_{i} for all 1 ≤ i ≤ 3. We now proceed with this assumption. Fix 1 ≤ i ≤ 3. Spherical rearrangement with Definition 1.12 (using e.g. [IT76, Theorem 2] and that t ↦ e^{ρrst/(1−ρ^{2})} is increasing in t) implies that

∑_{i=1}^{3} ∫_{S^{1}}[1_{A_{i}}(x) − σ(A_{i})]U_{g}[1_{A_{i}} − σ(A_{i})](x) dσ(x)

≤ ∑_{i=1}^{3} ∫_{S^{1}}[1_{H_{i}}(x) − σ(H_{i})]U_{g}[1_{H_{i}} − σ(H_{i})](x) dσ(x).

where H_{i} ⊆ S^{1} is a spherical arc such that σ(A_{i}) = σ(H_{i}).

Corollary 4.2 therefore concludes the proof. □

Remark 6.2. We note in passing that three 120 degree arcs have larger value of

\begin{matrix}∑_{i=1}^{3} ∫_{S^{1}}[1_{H_{i}}(x) − σ(H_{i})]U_{g}[1_{H_{i}} − σ(H_{i})](x) dσ(x) \\ = ∑_{i=1}^{3} [ ∫_{S^{1}} 1_{H_{i}}(x)U_{g}(1_{H_{i}})(x) dσ(x) − (σ(H_{i}))^{2}]. \end{matrix}  (44)

then two 180 degree arcs, i.e. we claim

\frac{9}{2π^{2}} · ∑_{d≥1: d≡1 mod 3 or d≡2 mod 3} λ_{d,2}^{r,s} \frac{1}{d^{2}} > \frac{4}{π^{2}} · ∑_{d≥1: d odd} λ_{d,2}^{r,s} \frac{1}{d^{2}} ,  ∀ 0 < ρ < 1, ∀ r, s > 0.  (45)

This fact follows from Corollary 4.2, but the explicit computation is still enlightening (especially when ρ < 0, in which case (45) is false for r · s large.)

Since λ_{d,2}^{r,s} ≥ λ_{d+1}^{r,s} for all d ≥ 0 by (18), (45) follows by a straightforward term-by-term monotonicity of the terms in (45). That is, Denote ℕ_{1,2} := {d ≥ 1: d ≡ 1 mod 3 or d ≡ 2 mod 3} and let ℕ_{odd} denote odd positive integers. Define J: ℕ_{1,2} → ℕ_{odd} as the order preserving map with J(1) = 1 and recursively, J(d) := min{y ∈ ℕ_{odd} : y ∉ ∪_{d′∈ℕ_{1,2}}{J(d′)}}. For example, J(1) = 1, J(2) = 3, J(4) = 5, J(5) = 7, J(7) = 9, J(8) = 11, and so on. Since λ_{d,2}^{r,s} ≥ λ_{d+1}^{r,s} for all d ≥ 0 by (18), since J is surjective and J(d) ≥ d for all d ∈ ℕ_{1,2} each term in the right sum of (45) has a corresponding larger or equal term on the left side of (45). We conclude that (45) holds. The Lemma follows.

7. A Convolution Bound

Lemma 7.1. Let r > 0. Let a := ρr/(1 − ρ^{2}). Let ϕ(x) := 1 − e^{−a∥x∥} for all x ∈ ℝ^{2}. Then

T_{ρ}ϕ(r) ≥ 1 − e^{− \frac{ρ^{2}r^{2}}{2[1−ρ^{2}]}} ∫_{t=0}^{t=∞} γ_{1}(t) dt − e^{\frac{3}{2} \frac{ρ^{2}r^{2}}{1−ρ^{2}}} ∫_{t=−∞}^{t=− \frac{2ρr}{\sqrt{1−ρ^{2}}}} γ_{1}(t) dt.

Proof. From Definition 1.4 we have

T_{ρ}ϕ(x) = ∫_{ℝ^{2}}(1 − e^{−a∥ρx+y\sqrt{1−ρ^{2}}∥})γ_{2}(y) dy, ∀ x ∈ ℝ^{2}.

When y ∈ ℝ^{2} is fixed, if z ∈ ℝ^{2} is perpendicular to ρx + y\sqrt{1 − ρ^{2}}, then ∥ρx + (y + z)\sqrt{1 − ρ^{2}}∥ ≥ ∥ρx + y\sqrt{1 − ρ^{2}}∥. Therefore,

T_{ρ}ϕ(x) ≥ ∫_{ℝ}(1 − e^{−a∥ρx+t \frac{x}{∥x∥} \sqrt{1−ρ^{2}}∥})γ_{1}(t) dt = ∫_{ℝ}(1 − e^{−a|ρ∥x∥+t\sqrt{1−ρ^{2}}|})γ_{1}(t) dt

= 1 − ∫_{t=− \frac{ρ∥x∥}{\sqrt{1−ρ^{2}}}}^{t=∞} e^{−a|ρ∥x∥+t\sqrt{1−ρ^{2}}|}γ_{1}(t) dt − ∫_{t=−∞}^{t=− \frac{ρ∥x∥}{\sqrt{1−ρ^{2}}}} e^{−a(|ρ∥x∥+t\sqrt{1−ρ^{2}}|}γ_{1}(t) dt

= 1 − ∫_{t=− \frac{ρ∥x∥}{\sqrt{1−ρ^{2}}}}^{t=∞} e^{−a(∥x∥ρ+t\sqrt{1−ρ^{2}})}γ_{1}(t) dt − ∫_{t=−∞}^{t=− \frac{ρ∥x∥}{\sqrt{1−ρ^{2}}}} e^{a(∥x∥ρ+t\sqrt{1−ρ^{2}})}γ_{1}(t) dt

= 1 − e^{−aρ∥x∥} ∫_{t=− \frac{ρ∥x∥}{\sqrt{1−ρ^{2}}}}^{t=∞} e^{−at\sqrt{1−ρ^{2}}}γ_{1}(t) dt − e^{aρ∥x∥} ∫_{t=−∞}^{t=− \frac{ρ∥x∥}{\sqrt{1−ρ^{2}}}} e^{at\sqrt{1−ρ^{2}}}γ_{1}(t) dt.

Then, using e^{−t^{2}/2}e^{λt} = e^{−(1/2)(t−λ)^{2}}e^{λ^{2}/2},

T_{ρ}ϕ(x) ≥ 1 − e^{−aρ∥x∥+ \frac{1}{2} a^{2}(1−ρ^{2})} ∫_{t=− \frac{ρ∥x∥}{\sqrt{1−ρ^{2}}} +a\sqrt{1−ρ^{2}}}^{t=∞} γ_{1}(t) dt

− e^{aρ∥x∥+ \frac{1}{2} a^{2}(1−ρ^{2})} ∫_{t=−∞}^{t=− \frac{ρ∥x∥}{\sqrt{1−ρ^{2}}} −a\sqrt{1−ρ^{2}}} γ_{1}(t) dt.

Plugging in the definition of a = ρr/(1 − ρ^{2}), we get

T_{ρ}ϕ(x) ≥ 1 − e^{−ρ^{2}r∥x∥/(1−ρ^{2})+ \frac{1}{2} ρ^{2}r^{2}/(1−ρ^{2})} ∫_{t= \frac{−ρ∥x∥+ρr}{\sqrt{1−ρ^{2}}}}^{t=∞} γ_{1}(t) dt

− e^{ρ^{2}r∥x∥/(1−ρ^{2})+ \frac{1}{2} ρ^{2}r^{2}/(1−ρ^{2})} ∫_{t=−∞}^{t= \frac{−ρ∥x∥−ρr}{\sqrt{1−ρ^{2}}}} γ_{1}(t) dt

≥ 1 − e^{− \frac{ρ^{2}r}{1−ρ^{2}} (∥x∥−r/2)} ∫_{t=− \frac{ρ(∥x∥−r)}{\sqrt{1−ρ^{2}}}}^{t=∞} γ_{1}(t) dt − e^{\frac{ρ^{2}r}{1−ρ^{2}} (∥x∥+r/2)} ∫_{t=−∞}^{t=− \frac{ρ(∥x∥+r)}{\sqrt{1−ρ^{2}}}} γ_{1}(t) dt.

In particular, when ∥x∥ = r, we get

T_{ρ}ϕ(r) ≥ 1 − e^{− \frac{ρ^{2}r^{2}}{2[1−ρ^{2}]}} ∫_{t=0}^{t=∞} γ_{1}(t) dt − e^{\frac{3}{2} \frac{ρ^{2}r^{2}}{1−ρ^{2}}} ∫_{t=−∞}^{t=− \frac{2ρr}{\sqrt{1−ρ^{2}}}} γ_{1}(t) dt.
□

Lemma 7.2. Let r > 0 and let 0 < ρ < 1. Let f: ℝ^{2} → ℝ be defined by

f(x) := \frac{ρr ∥x∥}{1 − ρ^{2}}e^{−ρr∥x∥/(1−ρ^{2})}, ∀ x ∈ ℝ^{2}.

For all r > 0 and for all 0 < ρ < .05,

T_{ρ}f(r, 0) ≥ 1.2\frac{ρr}{1 − ρ^{2}} e^{− \frac{(1.1ρr)^{2}}{1−ρ^{2}} −1.1 \frac{ρr}{1−ρ^{2}}} .

function  convolveexp
%plot the 2d convolve of the function
%f(x) = (rho r|x|/ 1-rho^2) exp(- (rho r|x|/ 1-rho^2))
% since it is a radial function, suffices to do a one-dimensional plot
rho=.05;
numpts=1000;
r=linspace(0 ,10,numpts);
for i=1:numpts
    plotme(i) = comyfcn(r(i),0,rho);
end
lb = 1.2*(rho*r/(1-rho^2)) .* exp(-((1.1*rho*r).^2)/(1-rho^2) ...
        - 1.1*(rho*r / (1-rho^2)));
plot(r,plotme,r, lb );
legend('orig','lb')
    if  sum(plotme - lb <0)==0  % then the inequality is verified
       fprintf('Verified\r');
    end
end
function out=comyfcn(x,y,rho)
%2d convolve the function
%f(x) = (rho r|x|/ 1-rho^2) exp(- (rho r|x|/ 1-rho^2))

% T_rho f(z) = int f(rho z + ysqrt(1-rho^2))gamma(y)
% output is T_rho f(x,y)
r=sqrt(x.^2 + y.^2);
rhor = rho*r / (1-rho^2);
f= @(a,b) rhor*sqrt(a.^2 + b.^2) .* exp(- rhor * sqrt(a.^2 + b.^2));
myfun = @(a,b) (f(rho*x + a*sqrt(1-rho^2), rho*y + b*sqrt(1-rho^2)))...
    .*exp(-(a.^2 + b.^2)/2) ;
out = (1/(2*pi))* integral2(myfun, -10, 10, -10, 10);
end

8. Proof of Main Theorem: Positive Correlation

Proof of Theorem 1.5 when ρ > 0. The main result of [HT21] implies that, since k = 3, we can and will assume that Ω_{1}, Ω_{2}, Ω_{3} ⊆ ℝ^{2}. That is, the case n = 2 is sufficient to prove the case n > 2 in Theorem 1.5.

Denote f: ℝ^{2} → {(1, 0, 0), (0, 1, 0), (0, 0, 1)} by (f(x))_{i} := 1_{Ω_{i}}(x) for all 1 ≤ i ≤ 3. Denote also f_{r}: ℝ^{2} → Δ_{2} by f_{r}(x) := f|_{rS^{1}}, i.e. f_{r} is f restricted to the sphere rS^{1}, and denote 𝔼f_{r} as the average value of f_{r} on rS^{1} (with respect to the normalized Haar probability measure σ on S^{1}.) Using Definitions 1.13 and 1.11 we then write (recalling notation from Section 1.7)

∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω_{i}}(x)γ_{2}(x) dx = 𝔼_{X∼_{ρ}Y} ⟨f(X), f(Y)⟩ = 𝔼_{R,S}𝔼_{(U,V)∼N_{ρ}^{R,S}}⟨f_{R}(U), f_{S}(V)⟩

= 𝔼_{R,S}𝔼_{(U,V)∼N_{ρ}^{R,S}}⟨f_{R}(U) − 𝔼f_{R} + 𝔼f_{R}, f_{S}(V) − 𝔼f_{S} + 𝔼f_{S}⟩
= 𝔼_{R,S}(⟨𝔼f_{R}, 𝔼f_{S}⟩ + 𝔼_{(U,V)∼N_{ρ}^{R,S}}⟨f_{R}(U) − 𝔼f_{R}, f_{S}(V) − 𝔼f_{S}⟩).

(46)

Let Θ_{1}, Θ_{2}, Θ_{3} ⊆ ℝ^{2} be three disjoint cones centered at the origin, each with cone angle 2π/3. Define then h: ℝ^{2} → Δ_{3} by h(x) := (1_{Θ_{1}}(x), 1_{Θ_{3}}(x), 1_{Θ_{3}}(x)) for all x ∈ ℝ^{2}.

We first upper bound the rightmost term in (46). From Corollary 4.2 we have, ∀ r, s > 0,

\begin{matrix}𝔼_{(U,V)∼N_{ρ}^{r,s}}⟨f_{r}(U) − 𝔼f_{r}, f_{s}(V) − 𝔼f_{s}⟩ ≤ 𝔼_{(U,V)∼N_{ρ}^{r,s}}⟨h_{r}(U) − 𝔼h_{r}, h_{s}(V) − 𝔼h_{s}⟩ \\ − ( − 1 + (1 − \frac{3^{4/3}}{5} )e^{− \frac{ρrs}{1−ρ^{2}} \frac{π}{2}} + \frac{3^{4/3}}{5} e^{− \frac{ρrs}{1−ρ^{2}} \frac{π}{6}} ) \\ · \frac{(.109)}{2} ∑_{i=1}^{3} ((σ(Ω_{i} ∩ rS^{1}) − 1/3)^{2} + (σ(Ω_{i} ∩ sS^{1}) − 1/3)^{2}). \end{matrix} (47)

Then, using Lemma 7.1, we get

𝔼_{R,S} 𝔼_{(U,V)∼N_{ρ}^{R,S}}⟨f_{R}(U) − 𝔼f_{R}, f_{S}(V) − 𝔼f_{S}⟩ ≤ 𝔼_{R,S} 𝔼_{(U,V)∼N_{ρ}^{R,S}}⟨h_{R}(U) − 𝔼h_{R}, h_{S}(V) − 𝔼h_{S}⟩

− 𝔼_{R}[1 − (1 − \frac{3^{4/3}}{5} )e^{− \frac{ρ^{2}R^{2}(π/2)^{2}}{2[1−ρ^{2}]}} ∫_{t=0}^{t=∞} γ_{1}(t) dt − (1 − \frac{3^{4/3}}{5} )e^{\frac{3}{2} \frac{ρ^{2}R^{2}(π/2)^{2}}{1−ρ^{2}}} ∫_{t=−∞}^{t=− \frac{2ρR(π/2)}{\sqrt{1−ρ^{2}}}} γ_{1}(t) dt

− \frac{3^{4/3}}{5} e^{− \frac{ρ^{2}R^{2}(π/6)^{2}}{2[1−ρ^{2}]}} ∫_{t=0}^{t=∞} γ_{1}(t) dt − \frac{3^{4/3}}{5} e^{\frac{3}{2} \frac{ρ^{2}R^{2}(π/6)^{2}}{1−ρ^{2}}} ∫_{t=−∞}^{t=− \frac{2ρR(π/6)}{\sqrt{1−ρ^{2}}}} γ_{1}(t) dt]

· (.109) ∑_{i=1}^{3}(σ(Ω_{i} ∩ R · S^{1}) − 1/3)^{2}.

(48)

Using Matlab, we simplify this bound to (1 − e^{−ρR/2}), i.e.

rho=.1;
r=linspace(0,150,10000);
y=.109 - (.109)*(1- (3^(4/3))/5)*( (exp(-(rho^2)*(r.^2)*(pi/2)^2 ...
 /(2*(1-rho^2))))*(.5)  + .5*(exp((3/2)*(rho^2)*(r.^2)*(pi/2)^2 ...
  /(1-rho^2))).*erfc(  2*rho*r*(pi/2)/sqrt(2*(1-rho^2))))  ...
   -(.109)*((3^(4/3))/5)*( (exp(-(rho^2) *(r.^2)*(pi/6)^2 ...
   /(2*(1-rho^2))))*(.5) + .5*(exp((3/2)*(rho^2)*(r.^2)*(pi/6)^2 ...
  /(1-rho^2))).*erfc(  2*rho*r*(pi/6)/sqrt(2*(1-rho^2))));
plot(r, y, r,  .109*(1-exp(-r*rho/2))   );
axis([0 150 0 .109]);
legend('original','lower bound');
if sum((y - .109*(1-exp(-r*rho/2))<0))==0, fprintf('Verified\r'), end;

\begin{matrix}𝔼_{R,S} 𝔼_{(U,V)∼N_{ρ}^{R,S}}⟨f_{R}(U) − 𝔼f_{R}, f_{S}(V) − 𝔼f_{S}⟩ ≤ 𝔼_{R,S} 𝔼_{(U,V)∼N_{ρ}^{R,S}}⟨h_{R}(U) − 𝔼h_{R}, h_{S}(V) − 𝔼h_{S}⟩ \\ − .109 · 𝔼_{R}(1 − e^{−Rρ/2}) ∑_{i=1}^{3}(σ(Ω_{i} ∩ R · S^{1}) − 1/3)^{2}. \end{matrix}

(49)

Or, rewriting using our notation for f,

\begin{matrix}𝔼_{R,S} 𝔼_{(U,V)∼N_{ρ}^{R,S}}⟨f_{R}(U) − 𝔼f_{R}, f_{S}(V) − 𝔼f_{S}⟩ ≤ 𝔼_{R,S} 𝔼_{(U,V)∼N_{ρ}^{R,S}}⟨h_{R}(U) − 𝔼h_{R}, h_{S}(V) − 𝔼h_{S}⟩ \\ − (.109) · 𝔼_{R}(1 − e^{−Rρ/2}) ∑_{i=1}^{3} ∥f_{R} − 1/3∥^{2} . \end{matrix}

(50)

Here we denote 1 := (1, 1, 1) ∈ ℝ^{3}. We now bound the ⟨𝔼f_{R}, 𝔼f_{S}⟩ term in (46). Using the assumption that 𝔼_{R,S}f_{R} = 𝔼_{R}f_{R} = 1/3, we have

\begin{aligned}𝔼_{R,S}⟨𝔼f_{R}, 𝔼f_{S}⟩ & = 𝔼_{R,S}⟨𝔼f_{R} − 1/3 + 1/3, 𝔼f_{S} − 1/3 + 1/3⟩ \\ & = 1/3 + 𝔼_{R,S}⟨𝔼f_{R} − 1/3, 𝔼f_{S} − 1/3⟩ \\ & = 1/3 + 𝔼_{X∼_{ρ}Y} ⟨𝔼f_{∥X∥} − 1/3, 𝔼f_{∥Y ∥} − 1/3⟩. \end{aligned}  (51)

Combining (51) and (50) into (46), we get

\begin{matrix}∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω_{i}}(x)γ_{2}(x) dx − ∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{Θ_{i}}(x)T_{ρ}1_{Θ_{i}}(x)γ_{2}(x) dx \\ ≤ 𝔼_{X∼_{ρ}Y} ⟨𝔼f_{∥X∥} − 1/3, 𝔼f_{∥Y ∥} − 1/3⟩ − (.109) · 𝔼_{R}(1 − e^{−Rρ/2}) ∑_{i=1}^{3} ∥f_{R} − 1/3∥^{2} . \end{matrix} (52)

Lemma 5.1 with 𝔼_{γ}f = 1/3 then bounds the penultimate term, yielding

\begin{matrix}∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω_{i}}(x)γ_{2}(x) dx − ∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{Θ_{i}}(x)T_{ρ}1_{Θ_{i}}(x)γ_{2}(x) dx \\ ≤ (2.5(ρ + ρ^{2}) − .109)𝔼_{R}(1 − e^{−Rρ/2}) ∑_{i=1}^{3} ∥f_{R} − 1/3∥^{2} . \end{matrix}  (53)

When 0 < ρ < .0418, we have (2.5ρ + 2.5ρ^{2} − .109) < 0, so the right side of (53) is nonpositive, with equality only when f_{R} = 1/3. The proof is therefore concluded by (53), when ρ satisfies 0 < ρ < .0418. □

Remark 8.1. Using computer assistance, we can replace the constant .109 above with .3, so, with computer assistance, the main theorem holds for all 0 < ρ such that 2.5(ρ+ρ^{2}) < .3, i.e. 0 < ρ < \frac{1}{10}(\sqrt{37} − 5) = .108 . . .. In particular, Theorem 1.5 holds for all 0 < ρ < 1/10.

function  surfplotfcn
    rho=.01;
numpts=100;
x=linspace(0 ,2*pi ,numpts);
y=linspace(0 ,2*pi ,numpts);
xv=ones(numpts,1)*x;
yv= y' * ones(1,numpts);
zv= (-3*myfun(2*pi/3,rho)+  myfun(xv,rho) + myfun(yv,rho) ...
    + myfun(2*pi-xv-yv,rho)).*(xv+yv<= 2*pi);
hold on;
pv=(1/3- xv/(2*pi)).^2  + (1/3- yv/(2*pi)).^2 + (2/3 - (xv+yv)/(2*pi)).^2;
surf(x,y, zv +.3*pv.*(xv+yv <=2*pi)*(besseli(1,rho))/besseli(0,rho));
%%% this surface being nonpositive demonstrates that a constant

%%%  .3 can be used in
end
function out=myfun(th,rho)
%output is mean subtracted noise stability of an interval [0,th]
% with positive correlation
k=30; % number of terms in expansion to use
out=zeros(size(th));
for i=1:k
    out=out + (1/i)^2 *(besseli(i,rho)/besseli(0,rho))*(sin(th*i/2)).^2;
end
out = out*2/pi^2;
end

Likewise, we check the inequality (49) with the constant .3 instead of .109.

rho=.04;
r=linspace(0,150,10000);
y=.3 - (.3)*(1- (3^(4/3))/5)*( (exp(-(rho^2)*(r.^2)*(pi/2)^2 ...
 /(2*(1-rho^2))))*(.5)  + .5*(exp((3/2)*(rho^2)*(r.^2)*(pi/2)^2 ...
  /(1-rho^2))).*erfc(  2*rho*r*(pi/2)/sqrt(2*(1-rho^2))))  ...
   -(.3)*((3^(4/3))/5)*( (exp(-(rho^2) *(r.^2)*(pi/6)^2 ...
   /(2*(1-rho^2))))*(.5) + .5*(exp((3/2)*(rho^2)*(r.^2)*(pi/6)^2 ...
  /(1-rho^2))).*erfc(  2*rho*r*(pi/6)/sqrt(2*(1-rho^2))));
plot(r, y, r,  .3*(1-exp(-r*rho/2))   );
axis([0 150 0 .3]);
legend('original','lower bound');
if sum((y - .109*(1-exp(-r*rho/2))<0))==0, fprintf('Verified\r'), end;

9. Proof of Main Theorem: Negative Correlation

Proof of Theorem 1.5 when ρ < 0. Let 0 < ρ < 1. In this proof, we will minimize the quantity

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

over all (measurable) partitions Ω_{1}, Ω_{2}, Ω_{3} ⊆ ℝ^{n} and Ω′_{1}, Ω′_{2}, Ω′_{3} ⊆ ℝ^{n} (so e.g. ∪_{i=1}^{3}Ω_{i} = ℝ^{n} and ∪_{i=1}^{3}Ω′_{i} = ℝ^{n}) subject to the constraint that

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

The main result of [HT21] (as adapted in [Hei22a]) implies that, since k = 3, we can and will assume that Ω_{1}, Ω_{2}, Ω_{3}, Ω′_{1}, Ω′_{2}, Ω′_{3} ⊆ ℝ^{2}.

We will demonstrate that Ω_{i} = −Ω′_{i} = Θ_{i} for all 1 ≤ i ≤ 3, where Θ_{1}, Θ_{2}, Θ_{3} are three disjoint sectors (cones) each with cone angle 2π/3 centered at the origin. Since T_{−ρ}f(x) = T_{ρ}f(−x), this result proves the negative correlation case of Theorem 1.5, i.e. the case −.0234 ≤ ρ < 0 of Theorem 1.5. Within the current proof, we assume that 0 < ρ ≤ .0234.

Denote f, g: ℝ^{2} → {(1, 0, 0), (0, 1, 0), (0, 0, 1)} by (f(x))_{i} := 1_{Ω_{i}}(x) and (g(x))_{i} := 1_{Ω′_{i}}(x) for all 1 ≤ i ≤ 3. Define also h: ℝ^{2} → Δ_{3} by h(x) := (1_{Θ_{1}}(x), 1_{Θ_{3}}(x), 1_{Θ_{3}}(x)) for all x ∈ ℝ^{2}.

Denote also f_{r}: ℝ^{2} → Δ_{2} by f_{r}(x) := f|_{rS^{1}}, i.e. f_{r} is f restricted to the sphere rS^{1}, and denote 𝔼f as the average value of f_{r} on rS^{1} (with respect to the normalized Haar probability measure on S^{1}.) Using Definitions 1.13 and 1.11, and also (10), (recalling notation from Section 1.7)

∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω′_{i}}(x)γ_{2}(x) dx = 𝔼_{X∼_{ρ}Y} ⟨f(X), f(Y)⟩ = 𝔼_{R,S}𝔼_{(U,V)∼N_{ρ}^{R,S}}⟨f_{R}(U), g_{S}(V)⟩

= 𝔼_{R,S}(⟨𝔼f_{R}, 𝔼g_{S}⟩ + λ_{1,n}^{R,S} \frac{1}{2π^{2}} ⟨ ∫_{S^{1}} f_{R}(x) cos(x) dx, ∫_{S^{1}} g_{S}(y) cos(y) dy⟩

+ λ_{1,n}^{R,S} \frac{1}{2π^{2}} ⟨ ∫_{S^{1}} f_{R}(x) sin(x) dx, ∫_{S^{1}} g_{S}(y) sin(y) dy⟩

+ ∑_{d=2}^{∞} λ_{d,n}^{R,S} \frac{1}{2π^{2}} (⟨ ∫_{S^{1}} f_{R}(x) cos(xd) dx, ∫_{S^{1}} g_{S}(y) cos(yd) dy⟩

+ ⟨ ∫_{S^{1}} f_{R}(x) sin(xd) dx, ∫_{S^{1}} g_{S}(y) sin(yd) dy⟩).

(55)

We introduce a notation for each of the forms on the right. We rewrite (55) as

Q(f, g) = Q_{0}(f, g) + Q_{1}(f, g) + Q_{2}(f, g).  (56)

That is, Q(f, g) := 𝔼_{R,S}𝔼_{(U,V)∼N_{ρ}^{R,S}}⟨f_{R}(U), g_{S}(V)⟩, Q_{0}(f, g) := 𝔼_{R,S}⟨𝔼f_{R}, 𝔼g_{S}⟩,

Q_{1}(f, g) := 𝔼_{R,S}(λ_{1,n}^{R,S} \frac{1}{2π^{2}} ⟨ ∫_{S^{1}} f_{R}(x) cos(x) dx, ∫_{S^{1}} g_{S}(y) cos(y) dy⟩

+ λ_{1,n}^{R,S} \frac{1}{2π^{2}} ⟨ ∫_{S^{1}} f_{R}(x) sin(x) dx, ∫_{S^{1}} g_{S}(y) sin(y) dy⟩),

and Q_{2}(f, g) denotes the remaining d ≥ 2 terms in (55).

Denote h_{−}(·) := h(−·). Since Q_{1} is bilinear, we have

Q_{1}(f, g) = Q_{1}(f − h + h, g − h_{−} + h_{−})
= Q_{1}(f − h, g − h_{−}) + Q_{1}(f − h, h_{−}) + Q_{1}(h, g − h_{−}) + Q_{1}(h, h_{−})
= Q_{1}(f − h, g − h_{−}) + Q_{1}(f, h_{−}) + Q_{1}(g, h) − Q_{1}(h, h_{−})
= Q_{1}(f − h, g − h_{−}) + Q_{1}(f, h_{−}) + Q_{1}(g, h) − Q_{1}(h, h_{−}).

And similarly for Q_{0} and Q_{2}. Using this identity in (56), we therefore have

\begin{matrix}Q(f, g) − Q(h, h_{−}) \\ =^{(56)} ∑_{i=0}^{2} (Q_{i}(f − h, g − h_{−}) + Q_{i}(f, h_{−}) − Q_{i}(h, h_{−}) + Q_{i}(g, h) − Q_{i}(h_{−}, h)) \\ = ∑_{i=0}^{2} (Q_{i}(f − h, g − h_{−}) + Q_{i}(f − h, h_{−}) + Q_{i}(g − h_{−}, h)). \end{matrix}  (57)

Plan of the Proof. We will bound the terms in (57) separately. We begin with the last two terms when i = 1, 2, which we bound from below. Then, we will bound the first term in (57) with i = 1, demonstrating this term is smaller than the previously mentioned terms. Finally, after subtracting a mean term, the remaining terms in (57) will be shown to be small, i.e. O(ρ) (whereas the previously mentioned terms are O(1), as ρ → 0.)

Step 1. We bound the last two i = 1, 2 terms from below in (41). We numerically verify the following inequality with the subsequent Matlab program.

\begin{matrix}∑_{i=1}^{2} (Q_{i}(f − h, h_{−}) + Q_{i}(g − h_{−}, h)) \\ ≥ .3133 · 𝔼_{R,S}(\frac{ρRS}{1 − ρ^{2}} · e^{− \frac{ρRS}{1−ρ^{2}}} ) ∑_{i=1}^{3} ((σ(Ω_{i} ∩ RS^{1}) − 1/3)^{2} + σ(Ω′_{i} ∩ SS^{1}) − 1/3)^{2}). \end{matrix}

(58)

function  surfplotfcnnegcorlinear
    rho=10;
numpts=140;
x=linspace(0 ,2*pi ,numpts);
y=linspace(0 ,2*pi ,numpts);
xv=ones(numpts,1)*x;
yv= y' * ones(1,numpts);
%%%%  mean subtracted noise stability, linear
zv= (-3*nmyfun(2*pi/3,-rho)+nmyfun(xv,-rho) + nmyfun(yv,-rho) ...
    +nmyfun((2*pi - xv - yv),-rho)).*(xv+yv<= 2*pi);
surf(xv,yv,zv);
hold on;
con=rho*exp(-rho) / 125.3;
surf(xv,yv,(con)*( (xv- 2*pi/3).^2 + (yv- 2*pi/3).^2 +...
     (2*pi - xv - yv - 2*pi/3).^2).*(xv+yv<= 2*pi))
if  sum(sum( ( zv>0 & zv < (con)*( (xv- 2*pi/3).^2 +...
     (yv- 2*pi/3).^2 + (2*pi - xv - yv - 2*pi/3).^2).*(xv+yv<= 2*pi) )))==0
    fprintf('Verified\r')
end
end
function out=nmyfun(th,rho)
%output is bilinear mean subtracted noise stability of an interval [0,th]
% against an interval [-pi/3 pi/3]
k=30; % number of terms in expansion to use
out=zeros(size(th));
for i=1:k
    out=out + (1/i)^2 *(besseli(i,rho)/besseli(0,rho))...

        *(sin(th*i/2)).*sin(i*pi/3);
end
out = out*2/pi^2;
end

Then, using Lemma 7.2 in (58), we have

\begin{matrix}∑_{i=1}^{2} (Q_{i}(f − h, h_{−}) + Q_{i}(g − h_{−}, h)) \\ ≥ .3133(1.2) · 𝔼_{R}ϕ(R) ∑_{i=1}^{3} ((σ(Ω_{i} ∩ RS^{1}) − 1/3)^{2} + σ(Ω′_{i} ∩ RS^{1}) − 1/3)^{2}), \end{matrix} (59)

where

ϕ(r) := \frac{ρ}{1 − ρ^{2}} re^{− \frac{(1.1ρr)^{2}}{1−ρ^{2}} − \frac{1.1ρ}{1−ρ^{2}} r}, ∀ r > 0.

Step 2. We bound the first i = 1 term in (41), using Lemmas 5.3 and 5.4 to get

\begin{matrix}|Q_{1}(f − h, g − h_{−})| \\ ≤ \frac{1}{2}(.9555)(\frac{1}{2}\sqrt{\frac{π}{2}} + 1.35ρ) · 𝔼_{R}ϕ(R) ∑_{i=1}^{3} ((σ(Ω_{i} ∩ RS^{1}) − 1/3)^{2} + σ(Ω′_{i} ∩ RS^{1}) − 1/3)^{2}). \end{matrix}

(60)

Step 3. We bound the remaining terms in (57), i.e. the last i = 0 term, and the first i = 0, 2 terms.

The last i = 0 terms in (57) are zero, since h and h_{−} have Haar measure 1/3 assigned to each partition element, on a sphere of any radius centered at the origin. The first i = 0 term in (57) is equal to a nonnegative term plus a term that is bounded by Lemma 5.2. Finally, the first i = 2 term in (57) is also bounded via Lemma 5.2. In fact, we can combine the first i = 0, 2 terms in (57) and estimate them as a single term. Using the notation of Lemma 5.3 (i.e. (42)), Let Proj(f): ℝ^{2} → ℝ^{2} denote f minus its degree one projection onto spherical harmonics, i.e.

Proj(f) :=^{(42)} f − Proj_{1}(f).  (61)

We then have

∑_{i=0,2} Q_{i}(f − h, g − h_{−}) = 𝔼_{X∼_{ρ}Y} ⟨Proj(f − h), Proj(g − h_{−})⟩

= ∥𝔼_{γ}(f − h)∥^{2} + ∑_{d≥2} ρ^{d} ∑_{k∈ℕ^{2} : ∥k∥_{1}=d}

⟨ ∫_{ℝ^{2}} \sqrt{k!}h_{k}(x)Proj(f − h)(x)γ_{2}(x) dx, ∫_{ℝ^{2}} \sqrt{k!}h_{k}(x)Proj(g − h_{−})(x)γ_{2}(x) dx⟩.

(62)

Applying Lemma 5.2 to (62), we then get

|∑_{i=0,2} Q_{i}(f − h, g − h_{−}) − ∥𝔼_{γ}(f − h)∥^{2}|

≤ (5ρ + 8ρ^{2})\frac{1}{2} · 𝔼_{X∼γ}ϕ(∥X∥)( ∥Proj(f − h)(X)∥^{2} + ∥Proj(g − h_{−})(X)∥^{2} ).

(63)

Since Proj is a contraction on each sphere centered at the origin, (63) implies that

\begin{matrix}|∑_{i=0,2} Q_{i}(f − h, g − h_{−}) − ∥𝔼_{γ}(f − h)∥^{2}| \\ ≤ (5ρ + 8ρ^{2})\frac{1}{2} · 𝔼_{X∼γ}ϕ(∥X∥)( ∥f(X) − h(X)∥^{2} + ∥g(X) − h_{−}(X)∥^{2} ). \end{matrix}  (64)

Combining (57), (59) and (64),

∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω′_{i}}(x)γ_{2}(x) dx − ∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{Θ_{i}}(x)T_{ρ}1_{Θ′_{i}}(x)γ_{2}(x) dx

≥^{(55)∧(57)} ∥𝔼_{γ}(f − h)∥^{2} + (.3133)(1.2)𝔼_{R}ϕ(R) · (∥𝔼f_{R} − 1/3∥^{2} + ∥𝔼g_{R} − 1/3∥^{2})

− \frac{1}{2}(.9555)(\frac{1}{2}\sqrt{\frac{π}{2}} + 1.35ρ) · (𝔼_{R}ϕ(R)(∥𝔼f_{R} − 𝔼h_{R}∥^{2} + ∥𝔼g_{R} − 𝔼h_{R}∥^{2})

− \frac{1}{2}(5ρ + 8ρ^{2}) · (𝔼_{X∼γ}ϕ(∥X∥)(∥f(X) − h(X)∥^{2} + ∥g(X) − h_{−}(X)∥^{2}).

Spherical rearrangement with Definition 1.12 (using e.g. [IT76, Theorem 2] and that t ↦ e^{ρrst/(1−ρ^{2})} is increasing in t) implies that we may assume that Ω_{i} ∩ rS^{1} and Ω′_{i} ∩ rS^{1} are opposing circular arcs for all r > 0. (After this rearrangement, Ω_{i} and Ω_{j} might have an intersection with positive measure for some i, j, but we still have ∑_{i=1}^{3} σ(Ω_{i} ∩ rS^{1}) = 1 for all r > 0. Also, after this rearrangement, we may assume that Ω_{i} ∩ rS^{1} and Θ_{i} ∩ rS^{1} are circular arcs with the same center of mass in rS^{1}.) So, if we write the last 𝔼_{X∼γ} term in polar coordinates, fix ∥X∥, and first average in the angular direction, we find the average of ∥f(X) − h(X)∥^{2} on a sphere of radius ∥X∥ is equal to ∥𝔼f_{∥X∥} − 𝔼h_{∥X∥}∥^{2}. Also, 𝔼h_{R} = 1/3 by definition of h, so that all of the terms involving f − h and g − h can be written in the same way, i.e.

\begin{matrix}∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω′_{i}}(x)γ_{2}(x) dx − ∑_{i=1}^{3} ∫_{ℝ^{2}} 1_{Θ_{i}}(x)T_{ρ}1_{Θ′_{i}}(x)γ_{2}(x) dx ≥ ∥𝔼_{γ}(f − h)∥^{2} \\ + 𝔼_{R}(ϕ(R) · (∥𝔼f_{R} − 1/3∥^{2} + ∥𝔼g_{R} − 1/3∥^{2}) · [.3759 − .3 − .645ρ − 2.5ρ − 4ρ^{2}]). \end{matrix}

(65)

The right side is nonnegative for all 0 < ρ < .0234 …, with equality only when f = h and g = −h.

□

10. Proof of Unique Games Hardness

Proof of Theorem 1.8. From [IM12, Theorem A.9]: assuming the Unique Games Conjecture, for any ε > 0, it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of β_{3} + ε where

β_{3} := lim_{n→∞} inf_{− \frac{1}{2} ≤ρ≤1} sup_{f: ℝ^{n}→Δ_{3}} \frac{3}{2} \frac{1 − ∑_{i=1}^{3} ∫_{ℝ^{n}}⟨f(x), T_{ρ}f(x)⟩ γ_{n}(x) dx}{1 − ρ}.

The main result of [HT21] (as adapted in [Hei22a]) implies that, since k = 3, the quantity β_{3} does not depend on n ≥ 4, i.e. we can write

β_{3} = inf_{− \frac{1}{2} ≤ρ≤1} sup_{f: ℝ^{4}→Δ_{3}} \frac{3}{2} \frac{1 − ∑_{i=1}^{3} ∫_{ℝ^{4}}⟨f(x), T_{ρ}f(x)⟩ γ_{4}(x) dx}{1 − ρ}.

Also, [IM12, Lemma A.4] implies that the infimum is attained when ρ ≤ 0, i.e.

β_{3} = inf_{− \frac{1}{2} ≤ρ≤0} sup_{f: ℝ^{4}→Δ_{3}} \frac{3}{2} \frac{1 − ∑_{i=1}^{3} ∫_{ℝ^{4}}⟨f(x), T_{ρ}f(x)⟩ γ_{4}(x) dx}{1 − ρ}.

Since this is an infimum, we have an upper bound by taking an infimum over a smaller set:

β_{3} ≤ inf_{−.0234≤ρ≤1} sup_{f: ℝ^{4}→Δ_{3}} \frac{3}{2} \frac{1 − ∑_{i=1}^{3} ∫_{ℝ^{4}}⟨f(x), T_{ρ}f(x)⟩ γ_{4}(x) dx}{1 − ρ}.

Now our main result Theorem 1.5 together with an explicit formula for the noise stability of the Plurality function from [KPW04] implies that

β_{3} ≤ inf_{−.0234≤ρ≤0} sup_{f: ℝ^{2}→Δ_{3}} \frac{3}{2} \frac{1 − ∑_{i=1}^{3} ∫_{ℝ^{2}}⟨f(x), T_{ρ}f(x)⟩ γ_{2}(x) dx}{1 − ρ}

= inf_{−.0234≤ρ≤0} \frac{3}{2} · \frac{1 − 3((1/9) + \frac{[arccos(−ρ)]^{2}−[arccos(ρ/2)]^{2}}{4π^{2}} )}{1 − ρ}

= \frac{3}{2} · \frac{1 − 3((1/9) + \frac{[arccos(.0234)]^{2}−[arccos((−.0234)/2)]^{2}}{4π^{2}} )}{1 − (−.0234)} ≈ .98937199597 ….

The above function of ρ is monotone. It attains its minimum at the endpoint ρ = −.0234. □

Acknowledgement. We thank Elchanan Mossel for suggesting that Theorem 1.8 should follow from Theorem 1.5.

References

[AAR99] George E. Andrews, Richard Askey, and Ranjan Roy, Special functions, Encyclopedia of Mathematics and its Applications, vol. 71, Cambridge University Press, Cambridge, 1999. MR 1688958 (2000g:33001) 12, 13

[Amo74] D. E. Amos, Computation of modified bessel functions and their ratios, Mathematics of Computation 28 (1974), no. 125, 239–251. 14

[BKS99] Itai Benjamini, Gil Kalai, and Oded Schramm, Noise sensitivity of boolean functions and applications to percolation, Publications Mathmatiques de l’Institut des Hautes tudes Scientifiques 90 (1999), no. 1, 5–43 (English). 2 [BMMN13] Mark Braverman, Konstantin Makarychev, Yury Makarychev, and Assaf Naor, The Grothendieck

constant is strictly smaller than Krivine’s bound, Forum Math. Pi 1 (2013), e4, 42. MR 3141414 4

[Bob97] S. G. Bobkov, An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in gauss space, Ann. Probab. 25 (1997), no. 1, 206–214. 4

[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) 3, 4

[Bor03] , The Ehrhard inequality, C. R. Math. Acad. Sci. Paris 337 (2003), no. 10, 663–666. MR 2030108 (2004k:60102) 4

[Bou02] J. Bourgain, On the distribution of the fourier spectrum of boolean functions, Israel Journal of Mathematics 131 (2002), no. 1, 269–276. 1

[BS01] A. Burchard and M. Schmuckenschläger, Comparison theorems for exit times, Geometric & Functional Analysis GAFA 11 (2001), no. 4, 651–692 (English). 4

[Cha06] Sourav Chatterjee, A generalization of the Lindeberg principle, Ann. Probab. 34 (2006), no. 6, 2061–2076. MR 2294976 (2008c:60028) 3

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

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

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

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

[Hås01] Johan Håstad, Some optimal inapproximability results, J. ACM 48 (2001), no. 4, 798859. 2 [Hei14] Steven Heilman, Euclidean partitions optimizing noise stability, Electron. J. Probab. 19 (2014),

no. 71, 37. MR 3256871 4, 7, 8, 24, 26

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

[Hei22a] , Hyperstable sets with voting and algorithmic hardness applications, Preprint, arXiv:2209.11216, 2022. 7, 8, 9, 37, 42

[Hei22b] , Noise stability of ranked choice voting, Preprint, arXiv:2209.11183, 2022. 7

[HJN13] Steven Heilman, Aukosh Jagannath, and Assaf Naor, Solution of the propeller conjecture in ℝ^{3}, Discrete & Computational Geometry 50 (2013), no. 2, 263–305 (English). 8

[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. 4, 9

[HNP^{+}21] Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson, and John Wright, Unique games hardness of quantum max-cut, and a vector-valued borell’s inequality, Preprint, arXiv:2111.01254, 2021. 7, 12, 13

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

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

[IT76] Albert Baernstein II and B. A. Taylor, Spherical rearrangements, subharmonic functions, and ∗-functions in n-space, Duke Mathematical Journal 43 (1976), no. 2, 245 – 268. 31, 41

[Kal02] Gil Kalai, A fourier-theoretic perspective on the condorcet paradox and arrow’s theorem, Advances in Applied Mathematics 29 (2002), no. 3, 412 – 426. 2

[Kho02] Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (New York), ACM, 2002, pp. 767–775 (electronic). MR MR2121525 2, 6 [Kho10] , On the unique games conjecture, 25th Annual IEEE Conference on Computa-

tional Complexity—CCC 2010, IEEE Computer Soc., Los Alamitos, CA, 2010, pp. 99–121. MR 2932348 2, 6

[KKLP97] Viggo Kann, Sanjeev Khanna, Jens Lagergren, and Alessandro Panconesi, On the hardness of approximating max k-cut and its dual, Tech. report, 1997. 7

[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) 1, 2, 3, 4, 6, 10

[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. 2, 6

[KPW04] Etienne Klerk, Dmitrii Pasechnik, and J.P. Warners, On approximate graph colouring and max-k-cut algorithms based on the θ-function, Journal of Combinatorial Optimization 8 (2004), 267–294. 6, 42

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

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

[MN15a] Elchanan Mossel and Joe Neeman, Robust dimension free isoperimetry in gaussian space, The Annals of Probability 43 (2015), no. 3, 971–991. 4

[MN15b] , Robust optimality of Gaussian noise stability, J. Eur. Math. Soc. (JEMS) 17 (2015), no. 2, 433–482. MR 3317748 4

[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) 1, 2, 3, 4

[O’D14] Ryan O’Donnell, Analysis of Boolean functions, Cambridge University Press, 2014. 2

[Per02] Grisha Perelman, The entropy formula for the ricci flow and its geometric applications, Preprint, arXiv:math/0211159, 2002. 4

[Rot79] V. I. Rotar′, Limit theorems for polylinear forms, J. Multivariate Anal. 9 (1979), no. 4, 511–530. MR 556909 (81m:60039) 3

[Sim68] James Simons, Minimal varieties in riemannian manifolds, Ann. of Math. (2) 88 (1968), 62–105. MR 0233295 4

[TSSW00] Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson, Gadgets, approximation, and linear programming, SIAM Journal on Computing 29 (2000), no. 6, 2074–2097. 2

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

E-mail address: stevenmheilman@gmail.com