SPHERE VALUED NOISE STABILITY AND QUANTUM MAX-CUT HARDNESS

STEVEN HEILMAN

Abstract. We prove a vector-valued inequality for the Gaussian noise stability (i.e. we prove a vector-valued Borell inequality) for Euclidean functions taking values in the twodimensional sphere, for all correlation parameters at most 1/10 in absolute value. This inequality was conjectured (for all correlation parameters at most 1 in absolute value) by Hwang, Neeman, Parekh, Thompson and Wright. Such an inequality is needed to prove sharp computational hardness of the product state Quantum MAX-CUT problem, assuming the Unique Games Conjecture. In fact, assuming the Unique Games Conjecture, we show that the product state of Quantum MAX-CUT is NP-hard to approximate within a multiplicative factor of .9859. In contrast, a polynomial time algorithm is known with approximation factor .956 . . ..

1. Introduction

The noise stability of a measurable Euclidean set A with correlation ρ is the probability that (X, Y) ∈ A × A, where X, Y are standard Gaussian random vectors with correlation ρ ∈ (−1, 1). Borell’s inequality asserts that half spaces have the largest noise stability among all Euclidean sets of fixed Gaussian measure. Borell’s inequality [Bor85] generalizes the Gaussian isoperimetric inequality, since letting ρ → 1^{−} in Borell’s inequality recovers the Gaussian isoperimetric inequality [Led94]. The Gaussian isoperimetric inequality says that a half space has the smallest Gaussian surface area among all Euclidean sets of fixed Gaussian volume.

Besides its intrinsic interest, Borell’s inequality has been applied to social choice theory [MOO10], the Unique Games Conjecture [KKMO07, MOO10, KM16], to semidefinite programming algorithms such as MAX-CUT [KKMO07, IM12], to learning theory [FGRW12], etc. For some surveys on this and related topics, see [O’D, Kho, Hei21].

A Corollary of Borell’s inequality is the Majority is Stablest Theorem [MOO10]. Moreover, Borell’s inequality was the main technical ingredient used to prove sharp computational hardness of the MAX-CUT problem, assuming the Unique Games Conjecture [KKMO07].

The MAX-CUT problem asks for the partition of the vertices of an undirected finite graph into two disjoint sets that maximizes the number of edges going between the two sets. The MAX-CUT problem is a well-studied NP-complete constraint satisfaction problem with wellunderstood hardness of approximation [GW95, KKMO07]. The Unique Games Conjecture implies that the Goemans-Williamson semidefinite program is the best quality polynomial time algorithm for approximately solving MAX-CUT.

The quantum analogue of a constraint satisfaction problem is a local Hamiltonian problem, which is QMA-complete [GK12]. The Quantum MAX-CUT problem is a special case of the local Hamiltonian problem, that in some sense generalizes the usual MAX-CUT problem. As with MAX-CUT, it is natural to ask for approximation algorithms for Quantum MAX-CUT, and to try to prove sharp computational hardness of those algorithms [HNP^{+}21, Kin22]. Below, we only discuss classical algorithms for Quantum MAX-CUT, i.e. we do not discuss quantum algorithms for Quantum MAX-CUT.

Date: August 31, 2023.

Key words and phrases. noise stability, Borell inequality, MAX-CUT, Quantum MAX-CUT.

For the product state Quantum MAX-CUT problem, there is a conjecturally optimal approximation algorithm. Assuming the Unique Games Conjecture and Conjecture 1.3 below (a vector-valued Borell inequality), we would then have a sharp hardness of approximation for the product state of Quantum MAX-CUT. The vector-valued Borell inequality, Conjecture 1.3 [HNP^{+}21] is a sphere-valued generalization of the Borell inequality [Bor85].

The main result of this paper is a proof the vector-valued Borell Inequality (Conjecture 1.3) for all correlations ρ satisfying |ρ| < .104. It remains a challenge to prove Conjecture 1.3 for all |ρ| < 1.

Our focus in this paper is proving the inequality conjectured in [HNP^{+}21] for functions f: ℝ^{n} → S^{2}. Our methods work equally well for functions taking values in S^{k} for any k ≥ 2, but the values of ρ for which our proof works would then depend on k. Since the case k = 2 is the only one needed for the product state Quantum MAX-CUT problem, we have therefore only focused on the case k = 2 in this paper.

1.1. Quantum MAX-CUT. Below we describe the Quantum MAX-CUT problem by analogy with MAX-CUT. When M is a 2 × 2 matrix and j is a positive integer, we denote

M^{⊗j} := \underbrace{M ⊗ ⋯ ⊗ M}_{j times} .

If n is a positive integer and 1 ≤ j ≤ n, denote

Z_{j} := I_{2}^{⊗(j−1)} ⊗ (\begin{matrix}1 & 0 \\ 0 & −1 \end{matrix}) ⊗ I_{2}^{⊗(n−j)},  ∀ 1 ≤ j ≤ n,  I_{2} := (\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}) .

The (weighted) MAX-CUT problem can be equivalently stated as [GP19, HNP^{+}21]: given w: {1, …, n}^{2} → [0, ∞) satisfying w_{ij} = w_{ji} and w_{ii} = 0 for all 1 ≤ i, j ≤ n, compute the following quantity

max_{u∈(ℂ^{2})^{⊗n}: ∥u∥≤1} u^{∗}( ∑_{i,j=1}^{n} w_{ij}(I_{2}^{⊗n} − Z_{i}Z_{j}))u.

Define now

X_{j} := I_{2}^{⊗(j−1)} ⊗ (\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}) ⊗ I_{2}^{⊗(n−j)}, ∀ 1 ≤ j ≤ n,

Y_{j} := I_{2}^{⊗(j−1)} ⊗ (\begin{matrix}0 & −\sqrt{−1} \\ \sqrt{−1} & 0 \end{matrix}) ⊗ I_{2}^{⊗(n−j)}, ∀ 1 ≤ j ≤ n.

The Quantum MAX-CUT problem is [GP19, Kin22, HNP^{+}21]: given w: {1, …, n}^{2} → [0, ∞) satisfying w_{ij} = w_{ji} and w_{ii} = 0 for all 1 ≤ i, j ≤ n, compute the following quantity

max_{u∈ℂ^{2n}: ∥u∥≤1} u^{∗}( ∑_{i,j=1}^{n} w_{ij}(I_{2}^{⊗n} − X_{i}X_{j} − Y_{i}Y_{j} − Z_{i}Z_{j}))u.

The product state of Quantum MAX-CUT is the more restricted optimization problem of computing

max_{\begin{matrix}u=u_{1}⊗···⊗u_{n}: \\ u_{i}∈ℂ^{2}, ∥u_{i}∥≤1, ∀ 1≤i≤n \end{matrix}} u^{∗}( ∑_{i,j=1}^{n} w_{ij}(I_{2}^{⊗n} − X_{i}X_{j} − Y_{i}Y_{j} − Z_{i}Z_{j}))u.

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}\overline{y_{i}}, ∥x∥ := ⟨x, x⟩^{1/2}.

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

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

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

Definition 1.2 (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.

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

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

1.3. Vector-Valued Borell Inequality. For any positive integer k, denote

f_{opt}(x) := \frac{x}{∥x∥},  ∀ x ∈ ℝ^{k} \ \{0\}.  (1)

Conjecture 1.3 ([HNP^{+}21]). Let n ≥ k be positive integers. Let f: ℝ^{n} → S^{k−1} be measurable. Then

• If 0 < ρ < 1 and if ∫_{ℝ^{n}} f(x)γ_{n}(x) dx = 0, then

∫_{ℝ^{n}}⟨f(x), T_{ρ}f(x)⟩γ_{n}(x) dx ≤ ∫_{ℝ^{k}}⟨f_{opt}(x), T_{ρ}f_{opt}(x)⟩γ_{k}(x) dx.
• If −1 < ρ < 0, then
∫_{ℝ^{n}}⟨f(x), T_{ρ}f(x)⟩γ_{n}(x) dx ≥ ∫_{ℝ^{k}}⟨f_{opt}(x), T_{ρ}f_{opt}(x)⟩γ_{k}(x) dx.

Moreover, equality holds only when there exists a real orthogonal k×n matrix M (MM^{T} = I) such that f(x) = f_{opt}(Mx) for a.e. x ∈ ℝ^{n}.

Remark 1.4. The case k = 1 of Conjecture 1.3 is known to be true, since it is Borell’s inequality [Bor85].

1.4. Our Result.

Theorem 1.5 (Main). Conjecture 1.3 holds for all n ≥ k = 3 and for all −.104 < ρ < .104.

In fact, we prove a stronger “stable” version of Conjecture 1.3 when n = k = 3, in (22),

(29) below:

• If 0 < ρ < .104 and if ∫_{ℝ^{k}} f(x)γ_{k}(x) dx = 0, then

∫_{ℝ^{k}}⟨f(x), T_{ρ}f(x)⟩γ_{k}(x) dx ≤ ∫_{ℝ^{k}}⟨f_{opt}(x), T_{ρ}f_{opt}(x)⟩γ_{k}(x) dx
+ (9.4ρ − .98) ∫_{ℝ^{k}} ϕ(x) ∥∫_{y∈∥x∥S^{k−1}} f(y) dσ(y)∥^{2} γ_{k}(x) dx.

• If −.104 < ρ < 0, then

∫_{ℝ^{k}}⟨f(x), T_{ρ}f(x)⟩γ_{k}(x) dx ≥ ∫_{ℝ^{k}}⟨f_{opt}(x), T_{ρ}f_{opt}(x)⟩γ_{k}(x) dx
+ (.98 − 9.4 |ρ|) ∫_{ℝ^{k}} ϕ(x) ∥∫_{y∈∥x∥S^{k−1}} f(y) dσ(y)∥^{2} γ_{k}(x) dx.

Here ϕ(x) = 1− \frac{1}{ρ∥x∥} + \frac{2}{e^{2ρ∥x∥}−1} for all x ∈ ℝ^{k} \\{0\} and dσ denotes normalized (Haar) measure on the sphere.

We can also prove Theorem 1.5 when k > 3, but with different dependence on ρ. Since the k = 3 case is the only relevant case for computational hardness of the product state of Quantum MAX-CUT, we only state a result for k = 3.

As shown in [HNP^{+}21, Theorem 6.11] by adapting the argument of [HT21], the case n = k = 3 of Theorem 1.5 (when ρ > 0) implies the case n > k = 3 of Theorem 1.5 (when ρ > 0). That is, the dimension of the domain can be a priori reduced to the case n = k, at least when ρ > 0. In this paper, we show that a similar statement holds in the case ρ < 0. This “dimension reduction” argument works differently in the case ρ < 0. For technical reasons, we need to instead deal with a bilinear version of the noise stability. With this change, we show that the bilinear noise stability has a similar dimension reduction argument. That is, we verify that the case n = k = 3 of Theorem 1.5 (when ρ < 0) implies the case n > k = 3 of Theorem 1.5 (when ρ < 0). The bilinear inequality we prove in the case n = k = 3 is the following. Suppose 0 < ρ < .104 and n = k = 3. We then show in (29) below that

∫_{ℝ^{k}}⟨f(x), T_{ρ}g(x)⟩γ_{k}(x) dx ≥ − ∫_{ℝ^{k}}⟨f_{opt}(x), T_{ρ}f_{opt}(x)⟩γ_{k}(x) dx,

∀ f, g: ℝ^{k} → S^{k−1} when k = 3, if ∫_{ℝ^{k}} f(x)γ_{k}(x) dx = ∫_{ℝ^{k}} g(x)γ_{k}(x) dx, or more generally,

∫_{ℝ^{k}}⟨f(x), T_{ρ}g(x)⟩γ_{k}(x) dx ≥ − ∫_{ℝ^{k}}⟨f_{opt}(x), T_{ρ}f_{opt}(x)⟩γ_{k}(x) dx

+ (.98 − 9.4ρ) ∫_{ℝ^{k}} ϕ(x)\frac{1}{2}( ∥∫_{y∈∥x∥S^{k−1}} f(y) dσ(y)∥^{2} + ∥∫_{y∈∥x∥S^{k−1}} g(y) dσ(y)∥^{2} )γ_{k}(x) dx.

Without considering this bilinear noise stability, [HNP^{+}21, Theorem 5.1] proved only the case n = k of Conjecture 1.3 when ρ < 0. The case n = k in Conjecture 1.3 does not imply the cases n > k, and this is why we considered the more general bilinear noise stability inequality above. (Although one can e.g. regard a function f: ℝ^{4} → S^{2} as a function \overline{f}: ℝ^{4} → S^{3} by considering S^{2} as a subset of S^{3}, the inequality satisfied by \overline{f} proven in [HNP^{+}21, Theorem 5.1] is not a sharp inequality for f.)

Applications to Quantum MAX-CUT require Conjecture 1.3 to hold for all n ≥ k. So, we have managed to prove a result that is independent of the dimension of the domain, since it holds for any n ≥ k when k = 3, though not for the full range of ρ parameters. Also, the proof method of [HNP^{+}21] does not directly apply in the case ρ > 0, and attempting to prove Conjecture 1.3 in that case led us towards Theorem 1.5, although the case ρ > 0 is irrelevant for applications to Quantum MAX-CUT.

Conjecture 1.3 should hold for all −1 < ρ < 1 and for all functions n ≥ k = 3. If such a conjecture holds, then we would be able to conclude sharp hardness of approximation for the product state of Quantum MAX-CUT problem, assuming the Unique Games Conjecture.

Conjecture 1.6 (Sharp Hardness for Quantum MAX-CUT, [HNP^{+}21]). Assume that the Unique Games Conjecture is true [Kho02, Kho10, KMS18]. Assume Conjecture 1.3 holds for all n ≥ k = 3. Then, for any ε > 0, it is NP-hard to approximate the product state of Quantum MAX-CUT within a multiplicative factor of α_{BOV} + ε.

As shown in [BdOFV10, HNP^{+}21], we have

α_{BOV} := inf_{−1≤ρ≤1} \frac{1 − F^{∗}(3, ρ)}{1 − ρ} ≈ .956.  (2)
F^{∗}(3, ρ) := \frac{2}{3}(\frac{Γ((3 + 1)/2)}{Γ(3/2)})^{2}ρ · _{2}F_{1}(1/2, 1/2, 3/2 + 1, ρ^{2}),  ∀ − 1 < ρ < 1. (3)

Here _{2}F_{1}(·, ·, ·, ·) is the Gaussian hypergeometric function.

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

A corollary of our main result Theorem 1.5 is a weaker version of Conjecture 1.6 that replaces the sharp constant .956 … with a larger constant.

Theorem 1.7 (Unique Games Hardness for Product State Quantum MAX-CUT). Assume that the Unique Games Conjecture is true. Then it is NP-hard to approximate the product state of Quantum MAX-CUT within a multiplicative factor of .9859.

To the author’s knowledge, Theorem 1.7 is the only computational hardness result for the product state of Quantum MAX-CUT besides Conjecture 1.6.

1.5. Some Notation and Definitions.

Definition 1.8 (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.9 (Correlated Random Variables on the Sphere). Let −1 < ρ < 1 and let r, s > 0. 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.10 (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 (7). 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).

The spherical noise stability has a decomposition into spherical harmonics by the Funk-Hecke Formula [HNP^{+}21, Theorem 4.3]

∫_{S^{n−1}} f(x)U_{g}f(x) dσ(x) = ∥ ∫_{S^{n−1}} f(x)dσ(x)∥^{2} + ∑_{d=1}^{∞} λ_{d,n}^{r,s}∥Proj_{d}(f)∥^{2}.  (5)

Here Proj_{d}(f) is the L_{2}(dσ) projection of f onto spherical harmonics of degree d, and λ_{d,n}^{r,s} are specified in (10)

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

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) =^{(6)} 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].  (7)

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

From [AAR99, p. 302],

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

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} =^{(7)} \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}

=^{(8)∧(9)} \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}.

(10)

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

In the case d = 1 we have

\begin{aligned}λ_{1,n}^{r,s} & = (\frac{ρrs}{1 − ρ^{2}} )\frac{(2)(\frac{n}{2} − 1)}{(n − 1)} \frac{1}{(n − 2)} \frac{∫_{−1}^{1}(1 − t^{2})^{\frac{n}{2} − \frac{1}{2}} e^{\frac{ρrst}{1−ρ^{2}}} dt}{∫_{−1}^{1}(1 − t^{2})^{\frac{n}{2} − \frac{3}{2}} e^{\frac{ρrst}{1−ρ^{2}}} dt} \\ & = (\frac{ρrs}{1 − ρ^{2}} )(\frac{1}{n − 1})\frac{∫_{−1}^{1}(1 − t^{2})^{\frac{n}{2} − \frac{1}{2}} e^{\frac{ρrst}{1−ρ^{2}}} dt}{∫_{−1}^{1}(1 − t^{2})^{\frac{n}{2} − \frac{3}{2}} e^{\frac{ρrst}{1−ρ^{2}}} dt}. \end{aligned}  (11)

The following Lemma follows from the Cauchy-Schwarz inequality, and from the spherical harmonic decomposition (5).

Lemma 1.11 ([HNP^{+}21, Lemma 5.4]). Let r, s > 0. Let ρ > 0. Let f_{r}, f_{s}: S^{n−1} → S^{n−1}. Then

𝔼_{(U,V)∼N_{ρ}^{r,s}}⟨f_{r}(U), f_{s}(V)⟩ ≤ ⟨𝔼f_{r}, 𝔼f_{s}⟩ + λ_{1,n}^{r,s}\sqrt{𝔼 ∥f_{r} − 𝔼f_{r}∥^{2}}\sqrt{𝔼 ∥f_{s} − 𝔼f_{s}∥^{2}}.

Equality holds only when f_{r}(x) = f_{s}(x) = Mx for all x ∈ S^{n−1}, where M is an n × n real orthogonal matrix.

𝔼_{(U,V)∼N_{ρ}^{r,s}}⟨f_{r}(U), f_{s}(V)⟩ ≥ ⟨𝔼f_{r}, 𝔼f_{s}⟩ − λ_{1,n}^{r,s}\sqrt{𝔼 ∥f_{r} − 𝔼f_{r}∥^{2}}\sqrt{𝔼 ∥f_{s} − 𝔼f_{s}∥^{2}}.

Equality holds only when f_{r}(x) = −f_{s}(x) = Mx for all x ∈ S^{n−1}, where M is an n × n real orthogonal matrix.

1.6. 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.9.

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

• 𝔼_{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.8.

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

2. Preliminaries: Quadratic Case

Our first step towards proving Theorem 1.5 with ρ > 0 will be modifying Lemma 1.11. Lemmas 2.1 and 2.2 below demonstrate that optimizing the noise stability 𝔼_{X∼_{ρ}Y} ⟨f(X), f(Y)⟩

involves an interplay between 𝔼f_{∥X∥} having norm 0 or norm 1.

Lemma 2.1. Let f: ℝ^{n} → S^{n−1} be continuous. For any r > 0, denote f_{r} := f|_{rS^{n−1}} and denote 𝔼f_{r} as the expected value of f_{r} on rS^{n−1} with respect to the uniform probability (Haar) measure on S^{n−1}. Then

𝔼_{X∼_{ρ}Y} ⟨f(X), f(Y)⟩ ≤ 𝔼_{X∼_{ρ}Y} (⟨𝔼f_{∥X∥}, 𝔼f_{∥Y ∥}⟩ + λ_{1,n}^{∥X∥,∥Y ∥}\sqrt{1 − ∥𝔼f_{∥X∥}∥^{2}}\sqrt{1 − ∥𝔼f_{∥Y ∥}∥^{2}}).

Equality holds only when f(x) = Mx/ ∥Mx∥ for a.e. x ∈ S^{n−1}, where M is an n × n real orthogonal matrix.

Proof. We first write (recalling the notation of Section 1.6)

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

Applying Lemma 1.11 and averaging over R, S, and also using that f takes values in S^{n−1}, so 𝔼 ∥f_{S} − 𝔼f_{S}∥^{2} = 1 + ∥𝔼f_{S}∥^{2} − 2⟨𝔼f_{S}, 𝔼f_{S}⟩ = 1 − ∥𝔼f_{S}∥^{2},

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

≤ 𝔼_{R,S}⟨𝔼f_{R}, 𝔼f_{S}⟩ + 𝔼_{R,S}λ_{1,n}^{R,S}\sqrt{𝔼 ∥f_{R} − 𝔼f_{R}∥^{2}}\sqrt{𝔼 ∥f_{S} − 𝔼f_{S}∥^{2}}

= 𝔼_{R,S}⟨𝔼f_{R}, 𝔼f_{S}⟩ + 𝔼_{R,S}λ_{1,n}^{R,S}\sqrt{𝔼(1 − ∥𝔼f_{R}∥^{2})}\sqrt{𝔼(1 − ∥𝔼f_{S}∥^{2})}

= 𝔼_{X∼_{ρ}Y} (⟨𝔼f_{∥X∥}, 𝔼f_{∥Y ∥}⟩ + λ_{1,n}^{∥X∥,∥Y ∥}\sqrt{1 − ∥𝔼f_{∥X∥}∥^{2}}\sqrt{1 − ∥𝔼f_{∥Y ∥}∥^{2}}).

The equality case follows from the equality case of Lemma 1.11 □

Using again the notation of Lemma 2.1, we have

Lemma 2.2. Let f: ℝ^{n} → S^{n−1}. Then

𝔼_{X∼_{ρ}Y} ⟨f(X), f(Y)⟩ ≤ 𝔼_{X∼_{ρ}Y} (λ_{1,n}^{∥X∥,∥Y ∥} + ⟨𝔼f_{∥X∥}, 𝔼f_{∥Y ∥}⟩ − ∥𝔼f_{∥X∥}∥^{2} λ_{1,n}^{∥X∥,∥Y ∥}).

Equality holds only when f(x) = Mx/ ∥Mx∥ for a.e. x ∈ S^{n−1}, where M is an n × n real orthogonal matrix.

Proof. Applying the inequality |ab| ≤ (1/2)(a^{2} + b^{2}) ∀ a, b ∈ ℝ, we have

𝔼_{X∼_{ρ}Y} λ_{1,n}^{∥X∥,∥Y ∥}\sqrt{1 − ∥𝔼f_{∥X∥}∥^{2}}\sqrt{1 − ∥𝔼f_{∥Y ∥}∥^{2}}

≤ 𝔼_{X∼_{ρ}Y} λ_{1,n}^{∥X∥,∥Y ∥}(1 − ∥𝔼f_{∥X∥}∥^{2})

= 𝔼_{X∼_{ρ}Y} λ_{1,n}^{∥X∥,∥Y ∥} − 𝔼_{X∼_{ρ}Y} λ_{1,n}^{∥X∥,∥Y ∥} ∥𝔼f_{∥X∥}∥^{2} .

Combining with Lemma 2.1 concludes the proof. □

3. Preliminaries: Bilinear Case

As in the previous section, our first step towards proving Theorem 1.5 with ρ < 0 will be modifying Lemma 1.11. Lemmas 3.1 and 3.2 below demonstrate that optimizing the bilinear noise stability 𝔼_{X∼_{ρ}Y} ⟨f(X), g(Y)⟩ involves an interplay between 𝔼f_{∥X∥} having norm 0 or norm

1, and similarly for 𝔼g_{∥Y ∥}.

Lemma 3.1. Let f, g: ℝ^{n} → S^{n−1} be continuous. For any r > 0, denote f_{r} := f|_{rS^{n−1}} and denote 𝔼f_{r} as the expected value of f_{r} on rS^{n−1} with respect to the uniform probability (Haar) measure on S^{n−1}. Then

𝔼_{X∼_{ρ}Y} ⟨f(X), g(Y)⟩ ≥ 𝔼_{X∼_{ρ}Y} (⟨𝔼f_{∥X∥}, 𝔼g_{∥Y ∥}⟩ − λ_{1,n}^{∥X∥,∥Y ∥}\sqrt{1 − ∥𝔼f_{∥X∥}∥^{2}}\sqrt{1 − ∥𝔼g_{∥Y ∥}∥^{2}}).

Equality holds only when f(x) = −g(x) = Mx/ ∥Mx∥ for a.e. x ∈ S^{n−1}, where M is an n × n real orthogonal matrix.

Proof. We first write (recalling the notation of Section 1.6)

𝔼_{X∼_{ρ}Y} ⟨f(X), g(Y)⟩ = 𝔼_{R,S}𝔼_{(U,V)∼N_{ρ}^{R,S}}⟨f_{R}(U), g_{S}(V)⟩.

Applying Lemma 1.11 and averaging over R, S, and also using that f takes values in S^{n−1}, so 𝔼 ∥f_{S} − 𝔼f_{S}∥^{2} = 1 + ∥𝔼f_{S}∥^{2} − 2⟨𝔼f_{S}, 𝔼f_{S}⟩ = 1 − ∥𝔼f_{S}∥^{2}, and similarly for g,

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

≥ 𝔼_{R,S}⟨𝔼f_{R}, 𝔼g_{S}⟩ − 𝔼_{R,S}λ_{1,n}^{R,S}\sqrt{𝔼 ∥f_{R} − 𝔼f_{R}∥^{2}}\sqrt{𝔼 ∥g_{S} − 𝔼g_{S}∥^{2}}

= 𝔼_{R,S}⟨𝔼f_{R}, 𝔼g_{S}⟩ − 𝔼_{R,S}λ_{1,n}^{R,S}\sqrt{𝔼(1 − ∥𝔼f_{R}∥^{2})}\sqrt{𝔼(1 − ∥𝔼g_{S}∥^{2})}

= 𝔼_{X∼_{ρ}Y} (⟨𝔼f_{∥X∥}, 𝔼g_{∥Y ∥}⟩ + λ_{1,n}^{∥X∥,∥Y ∥}\sqrt{1 − ∥𝔼f_{∥X∥}∥^{2}}\sqrt{1 − ∥𝔼g_{∥Y ∥}∥^{2}}).

The equality case follows from the equality case of Lemma 1.11. □

Using again the notation of Lemma 3.1. Then Lemma 3.2. Let f, g: ℝ^{n} → S^{n−1}. Then

𝔼_{X∼_{ρ}Y} ⟨f(X), g(Y)⟩ ≥ 𝔼_{X∼_{ρ}Y} (−λ_{1,n}^{∥X∥,∥Y ∥} +⟨𝔼f_{∥X∥}, 𝔼g_{∥Y ∥}⟩+ \frac{1}{2}(∥𝔼f_{∥X∥}∥^{2} +∥𝔼g_{∥X∥}∥^{2})λ_{1,n}^{∥X∥,∥Y ∥}).

Equality holds only when f(x) = −g(x) = Mx/ ∥Mx∥ for a.e. x ∈ S^{n−1}, where M is an n × n real orthogonal matrix. Proof. Applying the inequality |ab| ≤ (1/2)(a^{2} + b^{2}) ∀ a, b ∈ ℝ, we have

− 𝔼_{X∼_{ρ}Y} λ_{1,n}^{∥X∥,∥Y ∥}\sqrt{1 − ∥𝔼f_{∥X∥}∥^{2}}\sqrt{1 − ∥𝔼g_{∥Y ∥}∥^{2}}

≥ − 𝔼_{X∼_{ρ}Y} λ_{1,n}^{∥X∥,∥Y ∥}(1 − [∥𝔼f_{∥X∥}∥^{2} + ∥𝔼g_{∥X∥}∥^{2}]/2)

= − 𝔼_{X∼_{ρ}Y} λ_{1,n}^{∥X∥,∥Y ∥} + 𝔼_{X∼_{ρ}Y} λ_{1,n}^{∥X∥,∥Y ∥}(∥𝔼f_{∥X∥}∥^{2} + ∥𝔼g_{∥X∥}∥^{2})/2.

Combining with Lemma 3.1 concludes the proof. □

4. Eigenvalue Bounds

In this section, we derive some bounds on the first eigenvalue λ_{1,n}^{r,s} as defined in (5). From (11), we therefore need to control the function

\frac{∫_{−1}^{1}(1 − t^{2})^{\frac{n}{2} − \frac{1}{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)

This is a ratio of modified Bessel functions of the first kind. To recall their definition, first recall the Bessel function J_{α} of the first kind of order α ≥ 0 is [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 [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_{α+1}(a)}{I_{α}(a)} = \frac{(a/2)}{α + 1/2} \frac{∫_{−1}^{1} e^{at}(1 − t^{2})^{α+1/2}dt}{∫_{−1}^{1} e^{at}(1 − t^{2})^{α−1/2}dt}, ∀ a ∈ ℝ, ∀ α ≥ 0.

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

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

Combining with (11), we have

λ_{1,n}^{r,s} = \frac{ρrs}{1 − ρ^{2}} \frac{1}{n − 1} \frac{n − 1}{2}(\frac{2(1 − ρ^{2})}{ρrs})\frac{I_{n/2}(ρrs/[1 − ρ^{2}])}{I_{(n/2)−1}(ρrs/[1 − ρ^{2}])} = \frac{I_{n/2}(ρrs/[1 − ρ^{2}])}{I_{(n/2)−1}(ρrs/[1 − ρ^{2}])}. (13)

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

Therefore,

λ_{1,n}^{r,s} ≥ \frac{ρrs/[1 − ρ^{2}]}{n/2 + \sqrt{(n/2)^{2} + [ρrs/[1 − ρ^{2}]]^{2}}} ,  ∀ r, s > 0, ∀ ρ ∈ (0, 1).  (15)

In order to use our lower bounds on λ_{1,n}^{r,s} in Lemma 2.2, we must average λ_{1,n}^{r,s} over r > 0. Let a > 0. Then

∫_{0}^{∞} \frac{r^{3}e^{−r^{2}/2a^{2}}}{1 + \sqrt{1 + r^{2}}} dr = e^{1/2a^{2}}a^{3} ∫_{1/a}^{∞} e^{−t^{2}/2}dt.

Setting n = 3 in (13), we get

∫_{0}^{∞} r^{n−1} \frac{I_{n/2}(ar)}{I_{(n/2)−1}(ar)}e^{−r^{2}/2}dr ≥^{(14)} ∫_{0}^{∞} r^{n−1} \frac{ar}{n/2 + \sqrt{(n/2)^{2} + a^{2}r^{2}}} e^{−r^{2}/2}dr

= ∫_{0}^{∞} r^{n−1} \frac{2ar/n}{1 + \sqrt{1 + 4a^{2}r^{2}/n^{2}}} e^{−r^{2}/2}dr = (n/2a) ∫_{0}^{∞}(nr/[2a])^{n−1} \frac{r}{1 + \sqrt{1 + r^{2}}} e^{−n^{2}r^{2}/8a^{2}}dr

= (3/2a)^{3} ∫_{0}^{∞} \frac{r^{3}}{1 + \sqrt{1 + r^{2}}} e^{−n^{2}r^{2}/8a^{2}}dr = (3/2a)^{3}e^{9/8a^{2}}(2/3)^{3}a^{3} ∫_{3/2a}^{∞} e^{−t^{2}/2}dt

= e^{9/8a^{2}} ∫_{3/2a}^{∞} e^{−t^{2}/2}dt.

(16)

4.1. First Eigenvalue, Dimension 3. When d = 1 and n = 3, we have an explicit expression for λ_{1,n}^{r,s}.

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

for all r, s > 0, and for all 0 < ρ < 1. Here we used, with a = ρrs/(1 − ρ^{2}),

∫_{−1}^{1} e^{at}dt = \frac{1}{a}[e^{a} − e^{−a}].

∫_{−1}^{1}(1 − t^{2})e^{at}dt = \frac{1}{a} ∫_{−1}^{1}(1 − t^{2})\frac{d}{dt}e^{at}dt = \frac{1}{a} ∫_{−1}^{1} 2te^{at}dt

= \frac{1}{a^{2}} ∫_{−1}^{1} 2t\frac{d}{dt}e^{at}dt = \frac{1}{a^{2}} [2te^{at}|_{t=−1}^{t=1} − ∫_{−1}^{1} 2e^{at}dt]

= \frac{1}{a^{2}} [2(e^{a} + e^{−a}) − \frac{2}{a}[e^{a} − e^{−a}]].

\frac{∫_{−1}^{1}(1 − t^{2})e^{at}dt}{∫_{−1}^{1} e^{at}dt} = \frac{1}{a}(2\frac{e^{a} + e^{−a}}{e^{a} − e^{−a}} − \frac{2}{a}) = \frac{1}{a}(2 + 4\frac{e^{−a}}{e^{a} − e^{−a}} − \frac{2}{a}) = \frac{1}{a}(2 + 4\frac{1}{e^{2a} − 1} − \frac{2}{a}).

5. Change of Measure

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

Lemma 5.1. Let f: ℝ^{3} → S^{2} be a radial function (for any r > 0, the function f|_{rS^{2}} is constant). Let ϕ: ℝ^{3} → (0, ∞). Then

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

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

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

|∫_{ℝ^{3}}⟨f(x) − 𝔼_{γ}f, T_{ρ}[f − 𝔼_{γ}f](x)⟩γ_{3}(x) dx| ≤ (9.4ρ) ∫_{ℝ^{3}} ϕ(x) ∥f(x)∥^{2} γ_{3}(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)!} 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)γ_{3}(x) dx. For any k ∈ ℕ^{2}, define k! := k_{1}! · k_{2}!, and define ∥k∥_{1} := |k_{1}| + |k_{2}|.

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

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

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

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

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

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

Using the inequality

\frac{r^{2}}{ϕ(r)} ≤ \frac{3}{ρ}r + r^{2}, ∀ r > 0,

which can e.g. be verified in Matlab

rho=.1;
r=linspace(.1,20,1000);
rsqphi = r.^2 ./ (1 - 1./(rho*r) + 2./(exp(2*rho*r) -1));
plot(r, rsqphi , r, 3*r/rho +  r.^2);
legend('r^2 / phi','upper bound');
if sum( rsqphi - (3*r/rho + r.^2)>0)==0, fprintf('Verified\r'), end

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

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

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

= \sqrt{\frac{2}{π}} ∫_{r=0}^{∞} (\frac{3}{ρ}r + r^{2})\frac{1}{2(1 − ρ^{2})^{3/2}}

· ( − 2(1 − ρ^{2})^{3/2}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

= \sqrt{\frac{2}{π}} ∫_{r=0}^{∞} (\frac{3}{ρ}r + r^{2})\frac{1}{2(1 − ρ^{2})^{3/2}}

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

= \sqrt{\frac{2}{π}} \frac{1}{2(1 − ρ^{2})^{3/2}} \frac{3}{ρ}( − 2(1 − ρ^{2})^{3/2} + \frac{1}{2[\frac{1}{1+ρ} − \frac{1}{2}]} + \frac{1}{2[\frac{1}{1−ρ} − \frac{1}{2}]})

+ \sqrt{\frac{2}{π}} \frac{1}{(1 − ρ^{2})^{3/2}} \frac{\sqrt{π}}{8} ( − 2 · 2^{3/2}(1 − ρ^{2})^{3/2} + \frac{1}{[\frac{1}{1+ρ} − \frac{1}{2}]^{3/2}} + \frac{1}{[\frac{1}{1−ρ} − \frac{1}{2}]^{3/2}} ).

When ρ < 1/9, this quantity is upper bounded by 9.4ρ.

□

For the negative correlation case of the main result, we require a bilinear version of Lemma 5.1 above. Lemma 5.2 follows from Lemma 5.1 and the Cauchy-Schwarz inequality.

Lemma 5.2. Let f, g: ℝ^{3} → S^{2} be radial functions (for any r > 0, the function f|_{rS^{2}} is constant). Let ϕ(x) = 1 − \frac{1}{ρ∥x∥} + \frac{2}{e^{2ρ∥x∥}−1} for all x ∈ ℝ^{3}. If 0 < ρ < 1/9, then

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

6. Proof of Main Theorem: Quadratic Case

Proof of Theorem 1.5 when ρ > 0. The dimension reduction Theorem [HNP^{+}21, Theorem 6.11] implies that we may assume n = k = 3. From Lemma 2.2

𝔼_{X∼_{ρ}Y} ⟨f(X), f(Y)⟩ − 𝔼_{X∼_{ρ}Y} λ_{1,n}^{∥X∥,∥Y ∥} ≤ 𝔼_{X∼_{ρ}Y} (⟨𝔼f_{∥X∥}, 𝔼f_{∥Y ∥}⟩ − ∥𝔼f_{∥X∥}∥^{2} λ_{1,n}^{∥X∥,∥Y ∥}). (18)

It remains to show that the right side is nonpositive. Since 𝔼_{γ}f := ∫_{ℝ^{n}} f(x)γ_{n}(x) dx = 0, we have by Lemma 5.1 that

\begin{aligned}𝔼_{X∼_{ρ}Y} ⟨𝔼f_{∥X∥}, 𝔼f_{∥Y ∥}⟩ & = 𝔼_{X∼_{ρ}Y} ⟨𝔼f_{∥X∥} − 𝔼_{γ}f, 𝔼f_{∥Y ∥} − 𝔼_{γ}f⟩ \\ & ≤ 9.4ρ ∫_{ℝ^{n}} ϕ(x) ∥𝔼f_{∥x∥}∥^{2} γ_{n}(x) dx. \end{aligned}  (19)

Here ϕ(x) := 1 − \frac{1}{ρ∥x∥} + \frac{2}{exp^{2ρ∥x∥} −1} =^{(17)} λ_{1,n}^{∥x∥,1}. Meanwhile, the last term in (18) satisfies

𝔼_{X∼_{ρ}Y} ∥𝔼f_{∥X∥}∥^{2} λ_{1,n}^{∥X∥,∥Y ∥} =^{(1.1)} ∫_{ℝ^{3}} ∥𝔼f_{∥x∥}∥^{2} ( ∫_{ℝ^{3}} λ_{1,n}^{∥ρx+y\sqrt{1−ρ^{2}}∥,∥x∥}γ_{n}(y) dy)γ_{n}(x) dx

= ∫_{ℝ^{3}} ∥𝔼f_{∥x∥}∥^{2} (\sqrt{\frac{2}{π}} \frac{1}{4π} ∫_{u∈S^{2}} ∫_{r=0}^{∞} r^{2}λ_{1,n}^{∥ρx+ru\sqrt{1−ρ^{2}}∥,∥x∥}e^{−∥r∥^{2}/2} drdu)γ_{n}(x) dx

≥^{(17)} ∫_{ℝ^{3}} ∥𝔼f_{∥x∥}∥^{2} (\sqrt{\frac{2}{π}} \frac{1}{4π} ∫_{u∈S^{2}} ∫_{r=0}^{∞} r^{2}λ_{1,n}^{∥ru\sqrt{1−ρ^{2}}∥,∥x∥}e^{−∥r∥^{2}/2} drdu)γ_{n}(x) dx

= ∫_{ℝ^{3}} ∥𝔼f_{∥x∥}∥^{2} (\sqrt{\frac{2}{π}} ∫_{r=0}^{∞} λ_{1,n}^{r\sqrt{1−ρ^{2}},∥x∥}e^{−∥r∥^{2}/2} dr)γ_{n}(x) dx.

(20)

The inequality used that λ_{1,2}^{a,b} is an increasing function of a > 0 by (17), so the average over r, u is smallest when ρx = 0.

From (16) when n = 3 and a = ρrs/(1 − ρ^{2}) with (13), if s > 0 and 0 < ρ < 1/5, then

\sqrt{\frac{2}{π}} ∫_{r=0}^{∞} r^{2}λ_{1,n}^{r\sqrt{1−ρ^{2}},s}e^{−∥r∥^{2}/2} dr ≥^{(16)∧(13)} \sqrt{\frac{2}{π}} e^{\frac{9(1−ρ^{2})}{8s^{2}ρ^{2}}} ∫ ∞_{\frac{3\sqrt{1−ρ^{2}}}{2ρs}} e^{−t^{2}/2}dt

≥ (.98)(1 − \frac{1}{ρs} + \frac{2}{e^{2ρs} − 1}).

The last inequality can be verified e.g. with Matlab

rho=.03;
r=linspace(0,1000,1000);
phi=.98*(1 -  1./(rho * r ) +2./(exp(2* rho *r ) -1));
y=exp(  9*(1-rho^2) ./ (8* r.^2 * rho^2))  ...
 .* erfc( 3*sqrt(1-rho^2) ./ (2*sqrt(2) * rho *r));
plot(r, phi, r, y);
legend('lambda lower bd','integral quant (larger)');
if sum(y-phi<0)==0, fprintf('Verified\r'), end

Substituting this into (20), we get

𝔼_{X∼_{ρ}Y} ∥𝔼f_{∥X∥}∥^{2} λ_{1,n}^{∥X∥,∥Y ∥} ≥ .98 ∫_{ℝ^{3}} ϕ(x) ∥𝔼f_{∥x∥}∥^{2} γ_{n}(x) dx.  (21)

Combining (18), (21) and (19), we have

𝔼_{X∼_{ρ}Y} ⟨f(X), f(Y)⟩ − 𝔼_{X∼_{ρ}Y} λ_{1,n}^{∥X∥,∥Y ∥} ≤ (9.4ρ − .98) ∫_{ℝ^{n}} ϕ(x) ∥𝔼f_{∥x∥}∥^{2} γ_{n}(x) dx.  (22)

If ρ < .104, the right side is nonpositive, and it is equal to zero only when 𝔼f_{∥x∥} = 0 for a.e. x ∈ ℝ^{3}. That is,

𝔼_{X∼_{ρ}Y} ⟨f(X), f(Y)⟩ ≤^{(22)} 𝔼_{X∼_{ρ}Y} λ_{1,n}^{∥X∥,∥Y ∥} =^{(1)∧(5)} 𝔼_{X∼_{ρ}Y} ⟨f_{opt}(X), f_{opt}(Y)⟩.

with equality only when 𝔼f_{∥x∥} = 0 for a.e. x ∈ ℝ^{3}. Finally, if 𝔼f_{∥x∥} = 0 for a.e. x ∈ ℝ^{3}, then Lemma 2.1 implies that we must have f = f_{opt}(M·) for some real 3 × 3 orthogonal matrix M. □

7. Proof of Main Theorem: Bilinear Case

Proof of Theorem 1.5 when ρ < 0. In order to prove Theorem 1.5 for negative ρ, we consider instead ρ > 0 but with a bilinear variant of the noise stability over functions f, g: ℝ^{n} → S^{2} under the constraint that 𝔼_{γ}f = 𝔼_{γ}g = 0.

So, within the proof below, we have ρ > 0, and we will show that

𝔼_{X∼_{ρ}Y} ⟨f(X), g(Y)⟩ ≥ − 𝔼_{X∼_{ρ}Y} ⟨f_{opt}(X), f_{opt}(Y)⟩.  (23)

Dimension Reduction (Theorem 9.1 below) implies that we may assume n = k = 3 in order to prove (23). Equation (23) proves Theorem 1.5 for negative correlations, since

𝔼_{X∼_{(−ρ)}Y} ⟨f(X), f(Y)⟩ =^{(4)} 𝔼_{X∼_{ρ}Y} ⟨f(X), f(−(Y))⟩ ≥^{(23)} − 𝔼_{X∼_{ρ}Y} ⟨f_{opt}(X), f_{opt}(Y)⟩

=^{(4)} 𝔼_{X∼_{(−ρ)}Y} ⟨f_{opt}(X), f_{opt}(−Y)⟩ =^{(1)} 𝔼_{X∼_{(−ρ)}Y} ⟨f_{opt}(X), −f_{opt}(Y)⟩.

So, it remains to prove (23). From Lemma 3.2

𝔼_{X∼_{ρ}Y} (⟨f(X), g(Y)⟩+λ_{1,n}^{∥X∥,∥Y ∥}) ≥ 𝔼_{X∼_{ρ}Y} (⟨𝔼f_{∥X∥}, 𝔼g_{∥Y ∥}⟩+ \frac{1}{2}(∥𝔼f_{∥X∥}∥^{2} +∥𝔼g_{∥X∥}∥^{2})λ_{1,n}^{∥X∥,∥Y ∥}).

(24)

It remains to show that the right side is nonnegative. Since 𝔼_{γ}f = 𝔼_{γ}g by assumption,

𝔼_{X∼_{ρ}Y} ⟨𝔼f_{∥X∥}, 𝔼g_{∥Y ∥}⟩ = ∥𝔼_{γ}f∥^{2} + 𝔼_{X∼_{ρ}Y} ⟨𝔼f_{∥X∥} − 𝔼_{γ}f, 𝔼g_{∥Y ∥} − 𝔼_{γ}g⟩

≥ 𝔼_{X∼_{ρ}Y} ⟨𝔼f_{∥X∥} − 𝔼_{γ}f, 𝔼g_{∥Y ∥} − 𝔼_{γ}g⟩.

So, by Lemma 5.2,

\begin{aligned}𝔼_{X∼_{ρ}Y} ⟨𝔼f_{∥X∥}, 𝔼g_{∥Y ∥}⟩ & ≥ 𝔼_{X∼_{ρ}Y} ⟨𝔼f_{∥X∥} − 𝔼_{γ}f, 𝔼g_{∥Y ∥} − 𝔼_{γ}g⟩ \\ & ≥ −9.4ρ ∫_{ℝ^{n}} ϕ(x)\frac{1}{2}(∥𝔼f_{∥x∥}∥^{2} + ∥𝔼g_{∥x∥}∥^{2})γ_{n}(x) dx. \end{aligned}  (25)

Here ϕ(x) := 1 − \frac{1}{ρ∥x∥} + \frac{2}{exp^{2ρ∥x∥} −1} =^{(17)} λ_{1,n}^{∥x∥,1}. Meanwhile, (21) says that

𝔼_{X∼_{ρ}Y} ∥𝔼f_{∥X∥}∥^{2} λ_{1,n}^{∥X∥,∥Y ∥} ≥ .98 ∫_{ℝ^{3}} ϕ(x) ∥𝔼f_{∥x∥}∥^{2} γ_{n}(x) dx.  (26)
𝔼_{X∼_{ρ}Y} ∥𝔼g_{∥X∥}∥^{2} λ_{1,n}^{∥X∥,∥Y ∥} ≥ .98 ∫_{ℝ^{3}} ϕ(x) ∥𝔼g_{∥x∥}∥^{2} γ_{n}(x) dx.  (27)

Adding these together, we get

𝔼_{X∼_{ρ}Y} \frac{1}{2}(∥𝔼f_{∥X∥}∥^{2} + ∥𝔼g_{∥X∥}∥^{2})λ_{1,n}^{∥X∥,∥Y ∥} ≥ .98 ∫_{ℝ^{3}} ϕ(x)\frac{1}{2}(∥𝔼f_{∥x∥}∥^{2} + ∥𝔼g_{∥x∥}∥^{2})γ_{n}(x) dx. (28)

Combining (24), (28) and (25), we have

\begin{matrix}𝔼_{X∼_{ρ}Y} ⟨f(X), g(Y)⟩ + 𝔼_{X∼_{ρ}Y} λ_{1,n}^{∥X∥,∥Y ∥} \\ ≥ (.98 − 9.4ρ) ∫_{ℝ^{n}} ϕ(x)\frac{1}{2}(∥𝔼f_{∥x∥}(x)∥^{2} + ∥𝔼g_{∥x∥}(x)∥^{2})γ_{n}(x) dx. \end{matrix} (29)

If ρ < .104, the right side is nonnegative, and it is equal to zero only when 𝔼f_{∥x∥} = 𝔼g_{∥x∥} = 0 for a.e. x ∈ ℝ^{3}. That is,

𝔼_{X∼_{ρ}Y} ⟨f(X), g(Y)⟩ ≥^{(29)} − 𝔼_{X∼_{ρ}Y} λ_{1,n}^{∥X∥,∥Y ∥} =^{(1)∧(5)} − 𝔼_{X∼_{ρ}Y} ⟨f_{opt}(X), f_{opt}(Y)⟩.

with equality only when 𝔼f_{∥x∥} = 𝔼g_{∥x∥} = 0 for a.e. x ∈ ℝ^{3}.

If 𝔼f_{∥x∥} = 𝔼g_{∥x∥} = 0 for all x ∈ ℝ^{3}, then Lemma 3.1 implies that we must have f = −g = f_{opt}(M·) almost surely, for some real 3 × 3 orthogonal matrix M. So, (23) is proven, and the negative correlation case of Theorem 1.5 follows. □

8. Proof of Unique Games Hardness

Proof of Theorem 1.7. From [HNP^{+}21, Theorem 11.3]: assuming the Unique Games Conjecture, for any −1 < ρ < 0 and for any ε > 0, it is NP-hard to approximate the product state of Quantum MAX-CUT within a multiplicative factor of α_{ρ,BOV} + ε, where

α_{ρ,BOV} := lim_{n→∞} sup_{f: ℝ^{n}→S^{2}} \frac{1 − ∫_{ℝ^{n}}⟨f(x), T_{ρ}f(x)⟩ γ_{n}(x) dx}{1 − ρ}.

Theorem 1.5 says, if −.104 < ρ < 0, then

α_{ρ,BOV} = \frac{1 − ∫_{ℝ^{3}}⟨f_{opt}(x), T_{ρ}f_{opt}(x)⟩ γ_{3}(x) dx}{1 − ρ}.  (30)

An explicit formula for the noise stability of f_{opt} from [HNP^{+}21, Proposition 7.17] implies

α_{ρ,BOV} =^{(1)∧(30)} \frac{1 − F^{∗}(3, ρ)}{1 − ρ} =^{(3)} \frac{1 − \frac{2}{3}(\frac{Γ((3+1)/2)}{Γ(3/2)})^{2}ρ · _{2}F_{1}(1/2, 1/2, 3/2 + 1, ρ^{2})}{1 − ρ}.

Since NP hardness then applies from [HNP^{+}21, Theorem 11.3] for any −.104 < ρ < 0, we then have NP-hardness for the infimum of α_{ρ,BOV} over all −.104 < ρ < 0. That is, it is NP-hard to approximate the product state of Quantum MAX-CUT within a multiplicative factor of

inf_{−.104<ρ<0} α_{ρ,BOV} = α_{(−.104),BOV} = \frac{1 − \frac{2}{3}(\frac{Γ((3+1)/2)}{Γ(3/2)})^{2}(−.104) · _{2}F_{1}(1/2, 1/2, 3/2 + 1, (.104)^{2})}{1 − (−.104)}
= .98584579 ….

The above function of ρ is monotone, with minimum at the endpoint ρ = −.104. □

9. Appendix: Dimension Reduction

Theorem 9.1 (Bilinear Dimension Reduction). Let ρ > 0. Define

s_{n} := inf_{\begin{matrix}f,g: ℝ^{n}→S^{k−1} \\ 𝔼_{γ}f=𝔼_{γ}g=0 \end{matrix}} 𝔼_{X∼_{ρ}Y} ⟨f(X), g(Y)⟩.

Then

s_{n} = s_{k}, ∀ n ≥ k.

The inequality s_{n} ≤ s_{k} easily holds for all n ≥ k, so the content of Theorem 9.1 is that s_{n} ≥ s_{k} for all n ≥ k.

Theorem 9.1 is a fairly straightforward adaptation of [HNP^{+}21, Theorem 6.11] to the bilinear setting (itself an adaptation of [HT21] to the sphere-valued setting). In order to emphasize the relation between the argument below and that of [HNP^{+}21, Theorem 6.11], we will match the notation from [HNP^{+}21], where appropriate.

We say a vector field W: ℝ^{n} → ℝ^{k} is a tame vector field if W is bounded and C^{∞}, and all of the partial derivatives of W of any order exists and are bounded.

For any f: ℝ^{n} → ℝ^{k}, for any t ∈ ℝ, denote

V_{t,W} f(x) := \frac{f(x) + tW (x)}{max(1, ∥f(x) + tW (x)∥)},  ∀ x ∈ ℝ^{n}.  (31)

Denote also

B^{k} := {x ∈ ℝ^{k}: ∥x∥ ≤ 1}.

Definition 9.2. Let f, g: ℝ^{n} → B^{k} satisfy 𝔼_{γ}f = 𝔼_{γ}g = 0. Fix 0 < ρ < 1. We say that f, g are optimally stable with correlation ρ if, for all h, k: ℝ^{n} → B^{k} with 𝔼_{γ}h = 𝔼_{γ}k = 0,

∫_{ℝ^{k}}⟨f(x), T_{ρ}g(x)⟩γ_{k}(x) dx ≤ ∫_{ℝ^{k}}⟨h(x), T_{ρ}k(x)⟩γ_{k}(x) dx.

Lemma 9.3. If f, g are optimally stable with correlation ρ, then g = −f.

Proof. Since f = g = 0 has 𝔼_{γ}⟨f, T_{ρ}g⟩ = 0, if f, g are optimally stable, then 𝔼_{γ}⟨f, T_{ρ}g⟩ ≤ 0. So, the Cauchy-Schwarz inequality implies that

𝔼_{γ}⟨f, T_{ρ}g⟩ = − |𝔼_{γ}⟨f, T_{ρ}g⟩| ≥ − |𝔼_{γ}⟨f, T_{ρ}f⟩|^{1/2} |𝔼_{γ}⟨g, T_{ρ}g⟩|^{1/2}
≥ − max ( |𝔼_{γ}⟨f, T_{ρ}f⟩| , |𝔼_{γ}⟨g, T_{ρ}g⟩| ).

All of these inequalities become equalities when g = −f, since 𝔼_{γ}⟨f, T_{ρ}f⟩ ≥ 0, so

𝔼_{γ}⟨f, T_{ρ}(−f)⟩ = −𝔼_{γ}⟨f, T_{ρ}f⟩ = − |𝔼_{γ}⟨f, T_{ρ}f⟩| .
□

Lemma 9.4 (Lemma 6.8, [HNP^{+}21]). Let f: ℝ^{n} → ℝ^{k} be measurable. Then there exists vectors fields W_{1}, …, W_{k}: ℝ^{n} → ℝ^{k} such that

span\{\frac{d}{dt}|_{t=0}𝔼_{γ}[V_{t,W} f]: 1 ≤ i ≤ k\} = ℝ^{k}.

Lemma 9.5 (Lemma 6.9, [HNP^{+}21]). Let f, g: ℝ^{n} → ℝ^{k} be optimally stable. Then, for any bounded measurable vector fields W, Z: ℝ^{n} → ℝ^{k} such that \frac{d}{dt}|_{t=0}𝔼_{γ}V_{t,W} f = \frac{d}{dt}|_{t=0}𝔼_{γ}V_{t,Z}g = 0, we have

\frac{d}{dt}|_{t=0} 𝔼_{X∼_{ρ}Y} ⟨V_{t,W} f(X), V_{t,Z}g(Y)⟩ = 0.

Proof.

f_{α,β} := \frac{f(x) + βW (x) + ∑_{i=1}^{k} α_{i}W_{i}(x)}{max (1, ∥f(x) + βW (x) + ∑_{i=1}^{k} α_{i}W_{i}(x)∥)}.

g_{α,β} := \frac{g(x) + βZ(x) + ∑_{i=1}^{k} α_{i}W_{i}(x)}{max (1, ∥g(x) + βZ(x) + ∑_{i=1}^{k} α_{i}W_{i}(x)∥)}.

Define L: ℝ^{2k+1} → ℝ^{2k} by

L(α, θ, β) := (𝔼_{γ}f_{α,β}, 𝔼_{γ}g_{θβ}) , ∀ α, θ ∈ ℝ^{k}, ∀ β ∈ ℝ.

Then by assumption, we have

\frac{∂L}{∂β}(0, 0) =^{(31)} (\frac{d}{dt}|_{t=0}𝔼_{γ}V_{t,W} f, \frac{d}{dt}|_{t=0}𝔼_{γ}V_{t,Z}g) = 0.  (32)

And by definition of L, we have, for all 1 ≤ i ≤ k,

\begin{aligned}\frac{∂L}{∂α_{i}} (0, 0) & = (\frac{d}{dt}|_{t=0}𝔼_{γ}V_{t,W_{i}}f, 0) . \\ \frac{∂L}{∂θ_{i}} (0, 0) & = (0, \frac{d}{dt}|_{t=0}𝔼_{γ}V_{t,W_{i}}g) . \end{aligned}  (33)

From Lemma 9.4, we conclude that the matrix of partial derivatives DL of L is a (2k + 1) × 2k matrix of rank 2k. So, by the Implicit Function Theorem, there exists ε > 0 and a differentiable curve η: (−ε, ε) → ℝ^{2k+1} with η(0) = 0, η′(0) ≠ 0 and L(η(t)) = 0 for all t ∈ (−ε, ε). The last property implies, by the Chain Rule, that

0 = \frac{d}{dt}|_{t=0}L(η(t)) = ∑_{i=1}^{k} \frac{∂L}{∂α_{i}} (0, 0)η′_{i}(0) + ∑_{i=1}^{k} \frac{∂L}{∂θ_{i}} (0, 0)η′_{k+i}(0)  + \frac{∂L}{∂β}(0, 0)η′_{2k+1}(0). (34)

The last term is zero by (32). Lemma 9.4 and (33) imply that set \{\frac{∂L}{∂α_{i}} (0, 0), \frac{∂L}{∂θ_{i}} (0, 0)\}_{i=1}^{k} consists of 2k linearly independent vectors. We conclude from (34) that η′_{i}(0) = η′_{i+k}(0) = 0 for all 1 ≤ i ≤ k. Since η′(0) ≠ 0, we conclude that η′_{2k+1}(0) ≠ 0. Let J(t) :=

𝔼_{X∼_{ρ}Y} ⟨f_{(η_{i}(t))_{i=1}^{k},η_{2k+1}(t)}(X), g_{(η_{i+k}(t))_{i=1}^{k},η_{2k+1}(t)}(Y)⟩ for all t ∈ (−ε, ε). Since L(η(t)) = 0 for

all t ∈ (−ε, ε), (f, g) satisfy 𝔼_{γ}f = 𝔼_{γ}g = 0 for all t ∈ (−ε, ε). Since (f, g) are optimally stable, we therefore have (d/dt)J(t) = 0. Using the previous facts and the chain rule,

0 = \frac{d}{dt}|_{t=0}J(t) = ∑_{i=1}^{k} η′_{i}(t)\frac{∂}{∂α_{i}} 𝔼_{X∼_{ρ}Y} ⟨f_{α,β}(X), g_{θ,β}(Y)⟩ + ∑_{i=1}^{k} η′_{i+k}(t)\frac{∂}{∂θ_{i}} 𝔼_{X∼_{ρ}Y} ⟨f_{α,β}(X), g_{θ,β}(Y)⟩

+ η′_{2k+1}(0)\frac{d}{dt}|_{t=0} 𝔼_{X∼_{ρ}Y} ⟨f_{α,η_{2k+1}(t)}(X), g_{θ,η_{2k+1}(t)}(Y)⟩

= η′_{2k+1}(0)\frac{d}{dt}|_{t=0} 𝔼_{X∼_{ρ}Y} ⟨f_{α,η_{2k+1}(t)}(X), g_{θ,η_{2k+1}(t)}(Y)⟩

=^{(31)} η′_{2k+1}(0)\frac{d}{dt}|_{t=0} 𝔼_{X∼_{ρ}Y} ⟨V_{t,W} f(X), V_{t,Z}g(Y)⟩.

Since η′_{2k+1}(0) ≠ 0, the last term is zero, i.e. the proof is concluded. □

Lemma 9.6 ([HNP^{+}21, Lemma 6.10]). Let f, g be optimally stable. ∃ λ ∈ ℝ^{2k} such that

\frac{d}{dt}|_{t=0} 𝔼_{X∼_{ρ}Y} ⟨V_{t,W} f(X), V_{t,Z}g(Y)⟩ = ⟨(\frac{d}{dt}|_{t=0}𝔼_{γ}V_{t,W} f, \frac{d}{dt}|_{t=0}𝔼_{γ}V_{t,Z}g), λ⟩.

Proof. Let W, Z: ℝ^{n} → ℝ^{n}, and define ϕ_{1}, ϕ_{2}, ψ by

ϕ_{1}(W) := \frac{d}{dt}|_{t=0}𝔼_{γ}V_{t,W} f.

ϕ_{2}(Z) := \frac{d}{dt}|_{t=0}𝔼_{γ}V_{t,Z}g.

ψ(W, Z) := \frac{d}{dt}|_{t=0} 𝔼_{X∼_{ρ}Y} ⟨V_{t,W} f(X), V_{t,Z}g(Y)⟩.

Note that ϕ_{1}, ϕ_{2}, ψ are linear functions of (W, Z). Let X be a finite-dimensional subspace of bounded measurable vectors fields such that {(ϕ_{1}(W), ϕ_{2}(Z)): W, Z ∈ X } spans ℝ^{2k}. Define L: X → ℝ^{2k+1} by

L(W, Z) := (ϕ_{1}(W), ϕ_{2}(Z), ψ(W, Z)).

From Lemma 9.4, (0, …, 0, 1) is not in the range of L. So, there exists λ = λ(X) ∈ ℝ^{2k} such that (−λ, 1) is orthogonal to the range of L (with respect to the standard inner product in ℝ^{2k+1}.) That is, ⟨L(W, Z), (−λ, 1)⟩ = 0 for all W, Z ∈ X. That is, ψ(W, Z) = ⟨(ϕ_{1}(W), ϕ_{2}(Z)), λ⟩. As in [HNP^{+}21, Lemma 6.10], λ does not depend on X. □

For any t ∈ ℝ, denote t_{+} := max(t, 0).

Lemma 9.7 (Lemma 6.7, [HNP^{+}21]). Let f: ℝ^{n} → B^{k} be measurable. Let W: ℝ^{n} → ℝ^{k} be a bounded measurable vector field. For any x ∈ ℝ^{n},

V_{t,W} f(x) = f(x) + tW (x) − t⟨W (x), f(x)⟩_{+}f(x) + O(t^{2}),

where the O(t^{2}) term is uniform in x. Also,

\frac{d}{dt}|_{t=0}𝔼_{γ}V_{t,W} f = 𝔼_{γ}[W − ⟨f, W ⟩_{+}f1_{\{∥f∥=1\}}].

We write λ from Lemma 9.5 as λ = (λ^{(1)}, λ^{(2)}) ∈ ℝ^{2k} so that λ^{(i)} ∈ ℝ^{k} for i = 1, 2.

Lemma 9.8 (First Variation, Lemma 6.11, [HNP^{+}21]). Let f, g be optimally stable. Then

∥T_{ρ}f − λ^{(1)}∥g = T_{ρ}f − λ^{(1)}, ∥T_{ρ}g − λ^{(2)}∥f = T_{ρ}g − λ^{(2)}. a.s.

Proof. Combining Lemmas 9.7 and 9.6, Definition 1.1, Lemma 9.7 again, and Definition 1.8, ⟨(𝔼_{γ}[W − ⟨f, W ⟩_{+}f1_{{∥f∥=1}}], 𝔼_{γ}[Z − ⟨g, Z⟩_{+}g1_{{∥g∥=1}}]), λ⟩

= ⟨(\frac{d}{dt}|_{t=0}𝔼_{γ}V_{t,W} f, \frac{d}{dt}|_{t=0}𝔼_{γ}V_{t,Z}g), λ⟩

= \frac{d}{dt}|_{t=0} 𝔼_{X∼_{ρ}Y} ⟨V_{t,W} f(X), V_{t,Z}g(Y)⟩

= 𝔼_{X∼_{ρ}Y} ⟨f(X), Z(Y) − ⟨Z(Y), g(Y)⟩_{+}g(Y)⟩ + 𝔼_{X∼_{ρ}Y} ⟨W (X) − ⟨W (X), f(X)⟩_{+}f(X), g(Y)⟩

= 𝔼_{γ}⟨T_{ρ}f, Z − ⟨Z, g⟩_{+}g⟩ + 𝔼_{γ}⟨W − ⟨W, f⟩_{+}f, T_{ρ}g⟩. The above equality can be rearranged to be

𝔼_{γ}⟨T_{ρ}f − λ^{(1)}, Z − ⟨Z, g⟩_{+}g⟩ + 𝔼_{γ}⟨T_{ρ}g − λ^{(2)}, W − ⟨W, f⟩_{+}f⟩ = 0.

The proof then concludes as in [HNP^{+}21, Lemma 6.11]. □

Let W: ℝ^{n} → ℝ^{n} be a tame vector field. Define

F_{0}(x) := x, \frac{d}{dt}F_{t}(x) = W (F_{t}(x)), ∀ t ∈ ℝ, ∀ x ∈ ℝ^{n}.

Denote F_{t} = F_{t,W}, where appropriate.

S_{t,W} f(x) := f(F_{t}^{−1}(x)), ∀ t ∈ ℝ, ∀ x ∈ ℝ^{n}. (35)
div_{γ}W (x) := divW (x) − ⟨W (x), x⟩.

Lemma 9.9 (First Variation, Lemma 6.13, [HNP^{+}21]). Let f, g: ℝ^{n} → ℝ^{k} and let W, Z: ℝ^{n} → ℝ^{n} be tame vector fields. Then

\frac{d}{dt}|_{t=0} 𝔼_{X∼_{ρ}Y} ⟨S_{t,W} f(X), S_{t,Z}g(Y)⟩ = 𝔼_{γ}[⟨f, T_{ρ}f⟩div_{γ}W + ⟨f, D_{W} T_{ρ}f⟩]
+ 𝔼_{γ}[⟨g, T_{ρ}g⟩div_{γ}Z + ⟨g, D_{Z}T_{ρ}g⟩].

Let λ ∈ ℝ^{2k} from Lemma 9.6. Define

Q(W, Z) := \frac{d^{2}}{dt^{2}} |_{t=0} 𝔼_{X∼_{ρ}Y} ⟨S_{t,W} f(X), S_{t,Z}g(Y)⟩ − ⟨λ, (\frac{d^{2}}{dt^{2}} |_{t=0}𝔼_{γ}S_{t,W} f, \frac{d^{2}}{dt^{2}} |_{t=0}𝔼_{γ}S_{t,Z}g)⟩.

(36)

Lemma 9.10 (Second Variation, Lemma 6.15, [HNP^{+}21]). Let W, Z: ℝ^{n} → ℝ^{n} be tame vector fields such that

\frac{d}{dt}|_{t=0}𝔼_{γ}S_{t,W} f = \frac{d}{dt}|_{t=0}𝔼_{γ}S_{t,Z}g = 0.

Let f, g be optimally stable. Then

Q(W, Z) ≥ 0.

Proof. Similar to Lemma 9.5, for any α ∈ ℝ^{k} and β ∈ ℝ, define

f_{α,β} := \frac{f(F_{β,W} (x)) + ∑_{i=1}^{k} α_{i}W_{i}(x)}{max (1, ∥f(F_{β,W} (x)) + ∑_{i=1}^{k} α_{i}W_{i}(x)∥)}.

g_{α,β} := \frac{g(F_{β,Z}(x)) + ∑_{i=1}^{k} α_{i}W_{i}(x)}{max (1, ∥g(F_{β,Z}(x)) + ∑_{i=1}^{k} α_{i}W_{i}(x)∥)}.

Define L: ℝ^{2k+1} → ℝ^{2k} by

L(α, θ, β) := (𝔼_{γ}f_{α,β}, 𝔼_{γ}g_{θβ}) , ∀ α, θ ∈ ℝ^{k}, ∀ β ∈ ℝ.

Then by assumption, we have

\frac{∂L}{∂β}(0, 0) = (\frac{d}{dt}|_{t=0}𝔼_{γ}S_{t,W} f, \frac{d}{dt}|_{t=0}𝔼_{γ}S_{t,Z}g) = 0.  (37)

And by definition of L, we have, for all 1 ≤ i ≤ k,

\begin{aligned}\frac{∂L}{∂α_{i}} (0, 0) & = (\frac{d}{dt}|_{t=0}𝔼_{γ}S_{t,W_{i}}f, 0) . \\ \frac{∂L}{∂θ_{i}} (0, 0) & = (0, \frac{d}{dt}|_{t=0}𝔼_{γ}S_{t,W_{i}}g) . \end{aligned}  (38)

From Lemma 9.4, we conclude that the matrix of partial derivatives DL of L is a (2k + 1) × 2k matrix of rank 2k. So, by the Implicit Function Theorem, there exists ε > 0 and a differentiable curve η: (−ε, ε) → ℝ^{2k+1} with η(0) = 0, η′(0) ≠ 0 and L(η(t)) = 0 for all t ∈ (−ε, ε). The last property implies, by the Chain Rule, that

0 = \frac{d}{dt}|_{t=0}L(η(t)) = ∑_{i=1}^{k} \frac{∂L}{∂α_{i}} (0, 0)η′_{i}(0) + ∑_{i=1}^{k} \frac{∂L}{∂θ_{i}} (0, 0)η′_{k+i}(0)  + \frac{∂L}{∂β}(0, 0)η′_{2k+1}(0). (39)

The last term is zero by (37). Lemma 9.4 and (38) imply that set \{\frac{∂L}{∂α_{i}} (0, 0), \frac{∂L}{∂θ_{i}} (0, 0)\}_{i=1}^{k} consists of 2k linearly independent vectors. We conclude from (39) that η′_{i}(0) = η′_{i+k}(0) = 0 for all 1 ≤ i ≤ k. Since η′(0) ≠ 0, we conclude that η′_{2k+1}(0) ≠ 0. (Observe L(η(t)) = 0 for all t ∈ (−ε, ε), i.e. 𝔼_{γ}f = 𝔼_{γ}g = 0 for all t ∈ (−ε, ε), so the desired constraints hold for f, g for all t ∈ (−ε, ε).)

Taking another derivative of (39) and using η′_{i}(0) = η′_{i+k}(0) = 0 for all 1 ≤ i ≤ k along with L(η(t)) = 0 for all t ∈ (−ε, ε) and (37),

0 = \frac{d^{2}}{dt^{2}} |_{t=0}L(η(t)) = ∑_{i=1}^{k} \frac{∂L}{∂α_{i}} (0, 0)η′′_{i}(0) + ∑_{i=1}^{k} \frac{∂L}{∂θ_{i}} (0, 0)η′′_{k+i}(0) + \frac{∂^{2}L}{∂β^{2}}(0, 0)(η′_{2k+1}(0))^{2}.

(40)

Define J_{0}(α, θ, β) := 𝔼_{X∼_{ρ}Y} ⟨f_{α,β}(X), g_{θ,β}(Y)⟩ and J_{1}(t) := J_{0}(η(t)). Then, since f, g are

optinally stable and L(η(t)) = 0 for all t ∈ (−ε, ε), we have J′_{1}(0) = 0. Since η′_{i}(0) = η′_{i+k}(0) = 0 for all 1 ≤ i ≤ k, we have 0 = J′_{1}(0) = η′_{2k+1}(0)\frac{∂J_{0}}{∂β} (0, 0). Since η′_{2k+1}(0) ≠ 0, we have \frac{∂J_{0}}{∂β} (0, 0) = 0. Taking another derivative of J_{1} and using optimality of f, g, we have

0 ≤ J′′_{1}(0) = ∑_{i=1}^{k} \frac{∂J_{0}}{∂α_{i}} (0, 0)η′′_{i}(0) + ∑_{i=1}^{k} \frac{∂J_{0}}{∂θ_{i}} (0, 0)η′′_{k+i}(0)  + \frac{∂^{2}J_{0}}{∂β^{2}} (0, 0)(η′_{2k+1}(0))^{2}. (41)

Here we again used η′_{i}(0) = η′_{i+k}(0) = 0 for all 1 ≤ i ≤ k. Lemma 9.9 says \frac{∂}{∂α_{i}} J_{0} = ⟨λ, \frac{∂}{∂α_{i}} L⟩ for all 1 ≤ i ≤ k and \frac{∂}{∂θ_{i}} J_{0} = ⟨λ, \frac{∂}{∂θ_{i}} L⟩ for all 1 ≤ i ≤ k. So, we can rewrite (41) as

\begin{aligned}0 ≤ J′′_{1}(0) & = ∑_{i=1}^{k} η′′_{i}(0)⟨λ, \frac{∂}{∂α_{i}} L⟩ + ∑_{i=1}^{k} η′′_{k+i}(0)⟨λ, \frac{∂}{∂θ_{i}} L⟩  + \frac{∂^{2}J_{0}}{∂β^{2}} (0, 0)(η′_{2k+1}(0))^{2} \\ & =^{(40)} −(η′_{2k+1}(0))^{2}⟨λ, \frac{∂^{2}L}{∂β^{2}}(0, 0)⟩ + \frac{∂^{2}J_{0}}{∂β^{2}} (0, 0)(η′_{2k+1}(0))^{2}. \end{aligned} (42)

Since (η′_{2k+1}(0))^{2} > 0, we can factor it out of (42) to get

0 ≤ −⟨λ, \frac{∂^{2}L}{∂β^{2}}(0, 0)⟩ + \frac{∂^{2}J_{0}}{∂β^{2}} (0, 0).

This inequality concludes the proof, since the right side is Q(W, Z). □

Lemma 9.11 (Second Variation of Translations, adapted from Lemma 6.17, [HNP^{+}21]). Fix w ∈ ℝ^{n}. Let W: ℝ^{n} → ℝ^{n} be the constant vector field W := w. Let f, g be optimally stable. Assume that

\frac{d}{dt}|_{t=0}𝔼_{γ}S_{t,W} f = \frac{d}{dt}|_{t=0}𝔼_{γ}S_{t,Z}g = 0.

Then

Q(W, W) = 2(1 − 1/ρ)𝔼_{γ}∥D_{w}T\sqrt{ρ}f∥^{2}.

Proof. Let z ∈ ℝ^{n}. Let Z: ℝ^{n} → ℝ^{n} be the constant vector field Z := z. From (35), S_{t,W} f(x) = f(x − tw) for all t ∈ ℝ, x ∈ ℝ^{n}. So,

\frac{d^{2}}{dt^{2}} |_{t=0}𝔼_{γ}S_{t,W} f = 𝔼[D_{w}(D_{w}f)],  \frac{d^{2}}{dt^{2}} |_{t=0}𝔼_{γ}S_{t,Z}g = 𝔼[D_{z}(D_{z}g)].  (43)

Using the product rule and Definition 1.1,

\frac{d^{2}}{dt^{2}} |_{t=0} 𝔼_{X∼_{ρ}Y} ⟨S_{t,W} f(X), S_{t,Z}g(Y)⟩

= 𝔼_{X∼_{ρ}Y} ⟨D_{w,w}^{2}f(X), g(Y)⟩ + 𝔼_{X∼_{ρ}Y} ⟨f(X), D_{z,z}^{2}g(Y)⟩ + 2 𝔼_{X∼_{ρ}Y} ⟨D_{w}f(X), D_{z}g(Y)⟩

= 𝔼_{γ}⟨D_{w,w}^{2}f, T_{ρ}g⟩ + 𝔼_{γ}⟨T_{ρ}f, D_{z,z}^{2}g⟩ + 2𝔼_{γ}⟨D_{w}f, T_{ρ}D_{z}g⟩

= 𝔼_{γ}⟨D_{w,w}^{2}f, T_{ρ}g⟩ + 𝔼_{γ}⟨T_{ρ}f, D_{z,z}^{2}g⟩ + \frac{2}{ρ}𝔼_{γ}⟨D_{w}f, D_{z}T_{ρ}g⟩.

Substituting the definition of Q (36), using (43), then integrating by parts twice,

Q(W, Z) = 𝔼_{γ}⟨D_{w,w}^{2}f, T_{ρ}g − λ^{(2)}⟩ + 𝔼_{γ}⟨T_{ρ}f − λ^{(1)}, D_{z,z}^{2}g⟩ + \frac{2}{ρ}𝔼_{γ}⟨D_{w}f, D_{z}T_{ρ}g⟩

= − ∑_{i=1}^{k} 𝔼_{γ}D_{w}f_{i}div_{γ}(w(T_{ρ}g_{i} − λ_{i}^{(2)})) − ∑_{i=1}^{k} 𝔼_{γ}D_{z}g_{i}div_{γ}(z(T_{ρ}f_{i} − λ_{i}^{(1)}))

− \frac{2}{ρ} ∑_{i=1}^{k} 𝔼_{γ}f_{i}div_{γ}(wD_{z}T_{ρ}g_{i})⟩

= ∑_{i=1}^{k} 𝔼_{γ}f_{i}div_{γ}(wdiv_{γ}(w(T_{ρ}g_{i} − λ_{i}^{(2)}))) + ∑_{i=1}^{k} 𝔼_{γ}g_{i}div_{γ}(zdiv_{γ}(z(T_{ρ}f_{i} − λ_{i}^{(1)})))

− \frac{2}{ρ} ∑_{i=1}^{k} 𝔼_{γ}f_{i}div_{γ}(wD_{z}T_{ρ}g_{i})⟩.

(44)

We examine the penultimate terms. From the First Variation Lemma 9.8, a.s.

∥T_{ρ}f − λ^{(1)}∥g = T_{ρ}f − λ^{(1)}, ∥T_{ρ}g − λ^{(2)}∥f = T_{ρ}g − λ^{(2)}.

So, using first the product rule then Lemma 9.8,

∑_{i=1}^{k} 𝔼_{γ}f_{i}div_{γ}(wdiv_{γ}(w(T_{ρ}g_{i} − λ_{i}^{(2)}))) = ∑_{i=1}^{k} 𝔼_{γ}f_{i}div_{γ}((T_{ρ}g_{i} − λ_{i}^{(2)})wdiv_{γ}(w) + wD_{w}T_{ρ}g_{i})

= ∑_{i=1}^{k} 𝔼_{γ}f_{i}div_{γ}(∥T_{ρ}g_{i} − λ_{i}^{(2)}∥f_{i}wdiv_{γ}(w) + wD_{w}T_{ρ}g_{i}).

The penultimate term here is zero by [HNP^{+}21, Lemma 6.4], and a similar calculation for the other term in (44) allows us to rewrite (44) as

Q(W, Z) = ∑_{i=1}^{k} 𝔼_{γ}f_{i}div_{γ}(wD_{w}T_{ρ}g_{i}) + ∑_{i=1}^{k} 𝔼_{γ}g_{i}div_{γ}(zD_{z}T_{ρ}f_{i})

− \frac{2}{ρ} ∑_{i=1}^{k} 𝔼_{γ}f_{i}div_{γ}(wD_{z}T_{ρ}g_{i})⟩.

Lemma 9.12, rewrites this as

Q(W, Z) = −𝔼_{γ}⟨D_{w}T\sqrt{ρ}f, D_{w}T\sqrt{ρ}g⟩ − 𝔼_{γ}⟨D_{z}T\sqrt{ρ}f, D_{z}T\sqrt{ρ}g⟩ + \frac{2}{ρ}𝔼_{γ}⟨D_{w}T\sqrt{ρ}f, D_{z}T\sqrt{ρ}g⟩.

Using now Lemma 9.3, we may assume that g = −f, so that

Q(W, Z) = 𝔼_{γ}⟨D_{w}T\sqrt{ρ}f, D_{w}T\sqrt{ρ}f⟩ + 𝔼_{γ}⟨D_{z}T\sqrt{ρ}f, D_{z}T\sqrt{ρ}f⟩ − \frac{2}{ρ}𝔼_{γ}⟨D_{w}T\sqrt{ρ}f, D_{z}T\sqrt{ρ}f⟩.

Choosing w = z, we get

Q(W, W) = 2(1 − 1/ρ)𝔼_{γ}∥D_{w}T\sqrt{ρ}f∥^{2}.
□

Lemma 9.12 (Lemma 6.6, [HNP^{+}21]). Let w ∈ ℝ^{n}. Then

∑_{i=1}^{k} 𝔼_{γ}f_{i}div_{γ}(wD_{z}T_{ρ}g_{i}) = −𝔼_{γ}⟨D_{w}T\sqrt{ρ}g, D_{z}T\sqrt{ρ}f⟩.

Proof of Theorem 9.1. Let f, g: ℝ^{n} → S^{k−1} be optimally stable. Let w ∈ ℝ^{n}. Define W: ℝ^{n} → ℝ^{n} so that W (x) := w for all x ∈ ℝ^{n}. Let W satisfy

\frac{d}{dt}|_{t=0}𝔼_{γ}S_{t,W} f = \frac{d}{dt}|_{t=0}𝔼_{γ}S_{t,W} g = 0.  (45)

Since f = −g by Lemma 9.3, (45) is equivalent to

\frac{d}{dt}|_{t=0}𝔼_{γ}S_{t,W} f = 0.  (46)

Define L: ℝ^{n} → ℝ^{k} by L(w) := \frac{d}{dt}|_{t=0}𝔼_{γ}S_{t,W} f. Let ker(L) := \{w ∈ ℝ^{n}: L(w) = 0\} denote the kernel of L. Since L is a linear map, the rank-nullity theorem implies that ker(L) has dimension at least n − k.

Let w ∈ ker(L). Then Lemma 9.10 says Q(W, W) ≥ 0, while Lemma 9.11 says

Q(W, W) = 2(1 − 1/ρ)𝔼_{γ}∥D_{w}T\sqrt{ρ}f∥^{2} ≤ 0.

We conclude that there exists a linear subspace ker(L) ⊆ ℝ^{n} of dimension at least n−k with

𝔼_{γ}∥D_{w}T\sqrt{ρ}f∥^{2} = 0, ∀ w ∈ ker(L).

That is, we may assume that f is constant on ker(L), as noted e.g. in [HNP^{+}21, Lemma 6.6]. That is, we may assume a priori that f: ℝ^{k} → ℝ^{k−1}. Theorem 9.1 follows. □

Acknowledgement. We acknowledge and thank Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson and John Wright for helpful discussions.

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) 7, 10, 11

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

[BdOFV10] Jop Briët, Fernando Mário de Oliveira Filho, and Frank Vallentin, The positive semidefinite grothendieck problem with rank constraint, Automata, Languages and Programming (Berlin, Heidelberg) (Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, eds.), Springer Berlin Heidelberg, 2010, pp. 31–42. 5

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

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

[GK12] Sevag Gharibian and Julia Kempe, Approximation algorithms for qma-complete problems, SIAM J. Comput. 41 (2012), no. 4, 1028–1050. 1

[GP19] Sevag Gharibian and Ojas D. Parekh, Almost optimal classical approximation algorithms for a quantum generalization of max-cut, Preprint, arXiv:1909.08846, 2019. 2

[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) 1 [Hei14] Steven Heilman, Euclidean partitions optimizing noise stability, Electron. J. Probab. 19 (2014),

no. 71, 37. MR 3256871 12

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

[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. 2, 3, 4, 5, 6, 7, 8, 14, 17, 18, 19, 20, 21, 23, 24, 25

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

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

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

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

[Kho10] , On the unique games conjecture, 25th Annual IEEE Conference on Computational Complexity—CCC 2010, IEEE Computer Soc., Los Alamitos, CA, 2010, pp. 99–121. MR 2932348 5

[Kin22] Robbie King, An improved approximation algorithm for quantum max-cut, Preprint, arXiv:2209.02589, 2022. 2

[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

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

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

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

[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

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

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

Email address: stevenmheilman@gmail.com