EUCLIDEAN PARTITIONS OPTIMIZING NOISE STABILITY

STEVEN HEILMAN

Abstract. The Standard Simplex Conjecture of Isaksson and Mossel [12] asks for the partition {A_{i}}_{i=1}^{k} of ℝ^{n} into k ≤ n + 1 pieces of equal Gaussian measure of optimal noise stability. That is, for ρ > 0, we maximize

∑_{i=1}^{k} ∫_{ℝ^{n}} ∫_{ℝ^{n}} 1_{A_{i}}(x)1_{A_{i}}(xρ + y\sqrt{1 − ρ^{2}})e^{−(x_{1}^{2}+···+x_{n}^{2})/2}e^{−(y_{1}^{2}+···+y_{n}^{2})/2}dxdy.

Isaksson and Mossel guessed the best partition for this problem and proved some applications of their conjecture. For example, the Standard Simplex Conjecture implies the Plurality is Stablest Conjecture. For k = 3, n ≥ 2 and 0 < ρ < ρ_{0}(k, n), we prove the Standard Simplex Conjecture. The full conjecture has applications to theoretical computer science [12, 13, 19] and to geometric multi-bubble problems.

1. Introduction

The Standard Simplex Conjecture [12] asks for the partition {A_{i}}_{i=1}^{k} of ℝ^{n} into k ≤ n + 1 sets of equal Gaussian measure of optimal noise stability. This Conjecture generalizes a seminal result of Borell, [3, 19], which corresponds to the k = 2 case of the Standard Simplex Conjecture. Borell’s result says that the two disjoint regions of fixed Gaussian measures 0 < a < 1 and 1 − a and of optimal noise stability must be separated by a hyperplane. Since two disjoint sets of total Gaussian measure 1 can be described by a single set and its complement, Borell’s result can be stated as follows. Let A ⊆ ℝ^{n} have Gaussian measure 0 < a < 1 and let ρ ∈ (0, 1). Then the following quantity, which is referred to as the noise stability of A, is maximized when A is a half-space.

∫_{ℝ^{n}} ∫_{ℝ^{n}} 1_{A}(x)1_{A}(xρ + y\sqrt{1 − ρ^{2}})e^{−(x_{1}^{2}+···+x_{n}^{2})/2}e^{−(y_{1}^{2}+···+y_{n}^{2})/2}dxdy.  (1)

When we say that A is a half-space, we mean that A is the set of points lying on one side of a hyperplane. If ρ ∈ (−1, 0), then the noise stability (1) of A is minimized among all sets of Gaussian measure a, when A is a half-space. We can rewrite (1) probabilistically as follows. Let X = (X_{1}, …, X_{n}), Y = (Y_{1}, …, Y_{n}) ∈ ℝ^{n} be two standard Gaussian random vectors such that 𝔼(X_{i}Y_{j}) = ρ · 1_{(i=j)}. Then the noise stability (1) of A is equal to ℙ((X, Y) ∈ A × A).

For modern proofs of Borell’s theorem with additional stability statements, see [18, 7]. In the present work, we prove a specific case of the Standard Simplex Conjecture for k = 3, when 0 < ρ < ρ_{0}(n). Already for the case k = 3, the methods used in the case k = 2 do not seem to apply, so new techniques are required to treat the case k = 3. We first discuss consequences of the full conjecture and we then state the conjecture precisely. The Standard Simplex Conjecture appears to be first stated explicitly in [12]. If true, this conjecture implies:

2010 Mathematics Subject Classification. 68Q25.

Key words and phrases. Standard simplex, plurality, optimization, MAX-k-CUT, Γ-MAX2LIN(k).

This research is supported by NSF Graduate Research Fellowship DGE-0813964. Part of this work was carried out while visiting the Quantitative Geometry program at MSRI.

• Optimal hardness results for approximating the MAX-k-CUT problem [12, Theorem 1.13], a generalization of the MAX-CUT problem. (These hardness results are optimal, assuming the Unique Games Conjecture).

• The Plurality is Stablest Conjecture [13],[12][Theorem 1.10], an extension of the Majority is Stablest Conjecture [19] asserting that: the most noise-stable way to determine the winner of an election between k candidates is to take the plurality. (This result assumes that no one person has too much influence over the election’s outcome, and each candidate has an equal probability of winning).

• The solution of a multi-bubble problem in Gaussian space [6, 12, 17]: in ℝ^{n}, minimize the total Gaussian perimeter of k ≤ n + 1 sets of Gaussian measure 1/k.

The MAX-k-CUT problem asks for the partition of the vertices of any graph into k sets of maximum total edge perimeter. For the precise statement, see Definition 1.3 below. For a graph on n vertices, the MAX-k-CUT problem cannot be solved time polynomial in n, unless P=NP [8]. Yet, we can always find an approximate solution of the MAX-k-CUT problem in time polynomial in n [8]. To create this approximate solution, we label the vertices of the graph by vectors in ℝ^{n}, solve an appropriate semidefinite program for these vectors, and we then “round” these vectors into k bins. In particular, two vectors are rounded into the same bin if they lie in the same subset of a given partition {A_{i}}_{i=1}^{k} of ℝ^{n}. The best way to perform this rounding procedure is then provided by the partition {A_{i}}_{i=1}^{k} of optimal noise stability. That is, the Standard Simplex Conjecture exactly describes the best way to solve the MAXk-CUT problem [12, Theorem A.6]. This connection between combinatorial optimization and geometry has been well-studied; see e.g. [20, 2, 14, 16, 4, 10]. For a survey of the complexity theoretic motivation for problems related to the Standard Simplex Conjecture, see [15], where Grothendieck inequalities are emphasized.

The Plurality is Stablest Conjecture for k = 2 was proven in [19], where it was found to be a consequence of Borell’s theorem, after applying a nonlinear central limit theorem, which is referred to as an invariance principle. For k = 2, this problem is known as the Majority is Stablest Theorem. For more on the invariance principle, see also [5]. The invariance principle of [19] is proven by combining the Lindeberg replacement method with the hypercontractive inequality [9]. The Plurality is Stablest Conjecture says that the Plurality function nearly maximizes discrete noise stability over all functions f: {1, …, k}^{n} → {1, …, k}. In this context, we think of the domain of f as n voters who vote for any one of k candidates. Given n votes (a_{1}, …, a_{n}) ∈ {1, …, k}^{n}, the value f(a_{1}, …, a_{n}) ∈ {1, …, k} is the winner of the election. The Plurality is Stablest conjecture also assumes that each candidate has an equal probability of winning the election, and no one person has too much influence over the outcome of the election. It turns out that the latter assumption means that the function f can be well approximated by a function g: ℝ^{n} → {1, …, k}. That is, the noise stability of f is close to the sum of noise stabilities of the sets g^{−1}(1), …, g^{−1}(k). This approximation procedure, which uses an invariance principle, shows the equivalence of the Plurality is Stablest Conjecture and Standard Simplex Conjecture [12, Theorems 1.10 and 1.11]. We are therefore partially motivated to solve the Standard Simplex Conjecture to attempt to complete the picture set out by the sequence of works [3, 13, 19, 12].

The problem of minimizing Gaussian perimeter arises as an endpoint case of the Standard Simplex Conjecture. The Standard Simplex Conjecture is a statement involving a sum of terms of the form (1), and the Gaussian perimeter is recovered by letting ρ → 1^{−}.

We now precisely state the Standard Simplex Conjecture. Let ρ ∈ (−1, 1), n ≥ 1, n ∈ ℤ, let f: ℝ^{n} → ℝ be bounded and measurable, and define dγ_{n}(y) := e^{−(y_{1}^{2}+···+y_{n}^{2})/2}dy/(2π)^{n/2}, y = (y_{1}, …, y_{n}) ∈ ℝ^{n}. For x ∈ ℝ^{n}, define

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

The operator defined by (2) is known as the noise operator, or Bonami-Beckner operator, or Ornstein-Uhlenbeck operator. In particular, the Ornstein-Uhlenbeck operator is often written with ρ = e^{−t}, t > 0, so that T_{e^{−t}} becomes a semigroup.

Definition 1.1. Let A_{1}, …, A_{k} ⊆ ℝ^{n} be measurable, k ≤ n + 1. We say that {A_{i}}_{i=1}^{k} is a partition of ℝ^{n} if ∪_{i=1}^{k}A_{i} = ℝ^{n}, and γ_{n}(A_{i} ∩ A_{j}) = 0 for i ≠ j, i, j ∈ {1, …, k}. Let {z_{i}}_{i=1}^{k} be the vertices of a regular simplex centered at the origin of ℝ^{n}. For each i ∈ {1, …, k}, define A_{i} := {x ∈ ℝ^{n}: ⟨x, z_{i}⟩ = max_{j∈{1,...,k}}⟨x, z_{j}⟩}, the Voronoi region of z_{i}. We call {A_{i}}_{i=1}^{k} a regular simplicial conical partition.

Conjecture 1 (Standard Simplex Conjecture, [12]). Let n ≥ 2, let ρ ∈ [−1, 1], and let 3 ≤ k ≤ n + 1. Let {A_{i}}_{i=1}^{k} be a partition of ℝ^{n}.

(a) If ρ ∈ (0, 1], and if γ_{n}(A_{i}) = 1/k, ∀ i ∈ {1, …, k}, then among all such partitions of ℝ^{n}, the quantity

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

is maximized by a regular simplicial conical partition.

(b) If ρ ∈ [−1, 0) (with no restriction on the measures of the sets A_{i}, i ∈ {1, …, k}), then among all partitions of ℝ^{n}, the quantity J is minimized by a regular simplicial conical partition.

The following theorem is our main result.

Theorem 1.2 (Main Theorem). Fix n ≥ 2, k = 3. There exists ρ_{0} = ρ_{0}(n, k) > 0 such that Conjecture 1 holds for ρ ∈ (0, ρ_{0}).

Theorem 1.2 seems to have no direct relation to Gaussian isoperimetric problems [6], since these problems are implied by letting ρ → 1^{−} in Conjecture 1. Also, [12, Lemma A.4,Theorem A.6] shows that Theorem 1.2 seems to give no new information about the MAX-k-CUT problem, since in this problem, ρ < 0 is most relevant. Surprisingly, our proof strategy does not work for ρ < 0, as we show in Theorem 7.4.

Let X = (X_{1}, …, X_{n}), Y = (Y_{1}, …, Y_{n}) be jointly standard normal n-dimensional Gaussian random variables such that the covariances satisfy 𝔼(X_{i}Y_{j}) = ρ · 1_{{i=j}}, i, j ∈ {1, …, n}. In [12], the quantity (3) is written as ∑_{i=1}^{k} ℙ((X, Y) ∈ A_{i} × A_{i}). To see that our formulation of Conjecture 1 is equivalent to that of [12], let A ⊆ ℝ^{n} and note that

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

= ∫_{ℝ^{n}} ∫_{ℝ^{n}} 1_{A}(x)1_{A}(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y)dγ_{n}(x) = ℙ((X, Y) ∈ A × A).

1.1. MAX-k-CUT and the Unique Games Conjecture. We now rigorously describe the complexity theoretic notions referenced above.

Definition 1.3 (MAX-k-CUT). Let k, n ∈ ℕ, k ≥ 2. We define the weighted MAX-k-CUT problem. We are given a symmetric matrix {a_{ij}}_{i,j=1}^{n} with a_{ij} ≥ 0 for all i, j ∈ {1, …, n}. The goal of the MAX-k-CUT problem is to find the following quantity:

max_{c: \{1,...,n\}→\{1,...,k\}} ∑_{\begin{matrix}i,j∈\{1,...,n\}: \\ c(i)≠c(j) \end{matrix}} a_{ij}.

Definition 1.4 (Γ-MAX-2LIN(k)). Let k ∈ ℕ, k ≥ 2. We define the Γ-MAX-2LIN(k) problem. In this problem, we are given m ∈ ℕ and 2m variables x_{i} ∈ ℤ/kℤ, i ∈ {1, …, 2m}. We are also given a matrix {a_{ij}}_{i,j=1}^{2m} with a_{ij} ≥ 0 for all i, j ∈ {1, …, 2m}. An element (i, j) corresponds to one of m linear equations of the form x_{i} −x_{j} = c_{ij}(mod k), i, j ∈ {1, …, 2m}, c_{ij} ∈ ℤ/kℤ. The goal of the Γ-MAX-2LIN(k) problem is to find the following quantity:

max_{(x_{1},...,x_{2m})∈(ℤ/kℤ)^{2m}} ∑_{\begin{matrix}(i,j)∈E: \\ x_{i}−x_{j}=c_{ij}(mod k) \end{matrix}} a_{ij}.  (4)

Definition 1.5 (Unique Games Conjecture, [13]). For every ε ∈ (0, 1), there exists a prime number p(ε) such that no polynomial time algorithm can distinguish between the following two cases, for instances of Γ-MAX-2LIN(p(ε)) with w = 1:

(i) (4) is larger than (1 − ε)m, or (ii) (4) is smaller than εm.

If (4) were equal to m, then we could find (x_{1}, …, x_{2m}) achieving the maximum in (4) by linear algebra. One can therefore interpret the Unique Games Conjecture as an assertion that approximate linear algebra is hard.

Theorem 1.6. (Optimal Approximation for MAX-k-CUT, [12][Theorem 1.13],[8]). Let k ∈ ℕ, k ≥ 2. Let {A_{i}}_{i=1}^{k} ⊆ ℝ^{k−1} be a regular simplicial conical partition. Define

α_{k} := inf_{− \frac{1}{k−1} ≤ρ≤1} \frac{k − k^{2} ∑_{i=1}^{k} ∫_{ℝ^{n}} 1_{A_{i}}T_{ρ}1_{A_{i}}dγ_{n}}{(k − 1)(1 − ρ)} = inf_{− \frac{1}{k−1} ≤ρ≤0} \frac{k − k^{2} ∑_{i=1}^{k} ∫_{ℝ^{n}} 1_{A_{i}}T_{ρ}1_{A_{i}}dγ_{n}}{(k − 1)(1 − ρ)} .

Assume Conjecture 1 and the Unique Games Conjecture. Then, for any ε > 0, there exists a polynomial time algorithm that approximates MAX-k-CUT within a multiplicative factor α_{k}−ε, and it is NP-hard to approximate MAX-k-CUT within a multiplicative factor of α_{k}+ε.

1.2. Plurality is Stablest. We now briefly describe the Plurality is Stablest Conjecture. This Conjecture seems to first appear in [13]. The work [13] emphasizes the applications of this conjecture to MAX-k-CUT and to MAX-2LIN(k).

Let n ≥ 2, k ≥ 3 Let (W_{1}, …, W_{k}) be an orthonormal basis for the space of functions \{g: \{1, …, k\} → [0, 1]\} equipped with the inner product ⟨g, h⟩_{k} := \frac{1}{k} ∑_{σ∈\{1,...,k\}} g(σ)h(σ). Assume that W_{1} = 1. By orthonormality, for every σ ∈ {1, …, k}, there exists ĝ(σ) ∈ ℝ such that the following expression holds: g = ∑_{σ∈{1,...,k}} ĝ(σ)W_{σ}. Define

Δ_{k} := {(x_{1}, …, x_{k}) ∈ ℝ^{k}: ∀ 1 ≤ i ≤ k, 0 ≤ x_{i} ≤ 1, ∑_{i=1}^{k} x_{i} = 1}.

Let f: {1, …, k}^{n} → Δ_{k}, f = (f_{1}, …, f_{k}), f_{i}: {1, …, k}^{n} → [0, 1], i ∈ {1, …, k}. Let σ = (σ_{1}, …, σ_{n}) ∈ {1, …, k}^{n}. Define W_{σ} := ∏_{i=1}^{n} W_{σ_{i}}, and let |σ| := |{i ∈ {1, …, n}: σ_{i} ≠ 1}|. Then for every σ ∈ {1, …, k}^{n} there exists f̂_{i}(σ) ∈ ℝ such that f_{i} = ∑_{σ∈{1,...,k}^{n}} f̂_{i}(σ)W_{σ}, i ∈ {1, …, k}. For ρ ∈ [−1, 1] and i ∈ {1, …, k}, define

T_{ρ}f_{i} := ∑_{σ∈{1,...,k}^{n}} ρ^{|σ|}f̂_{i}(σ)W_{σ}, T_{ρ}f := (T_{ρ}f_{1}, …, T_{ρ}f_{k}) ∈ ℝ^{k}.

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

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

Conjecture 2 (Plurality is Stablest Conjecture, [12]). Let n ≥ 2, k ≥ 3, ρ ∈ [−\frac{1}{k−1}, 1], ε > 0. Let ⟨·, ·⟩ denote the standard inner product on ℝ^{n}. Then there exists τ > 0 such that, if f: {1, …, k}^{n} → Δ_{k} satisfies ∑_{σ∈{1,...,k}^{n}: σ_{j}≠1}(f̂_{i}(σ))^{2} ≤ τ for all i ∈ {1, …, k}, j ∈ {1, …, n}, then

(a) If ρ ∈ (0, 1], and if \frac{1}{k^{n}} ∑_{σ∈\{1,...,k\}^{n}} f(σ) = \frac{1}{k} ∑_{i=1}^{k} e_{i}, then

\frac{1}{k^{n}} ∑_{σ∈\{1,...,k\}^{n}}⟨f(σ), T_{ρ}f(σ)⟩ ≤ lim_{m→∞} \frac{1}{k^{m}} ∑_{σ∈\{1,...,k\}^{m}}⟨PLUR_{m,k}(σ), T_{ρ}(PLUR_{m,k})(σ)⟩ + ε.

(b) If ρ ∈ [−1/(k − 1), 0), then

\frac{1}{k^{n}} ∑_{σ∈\{1,...,k\}^{n}}⟨f(σ), T_{ρ}f(σ)⟩ ≥ lim_{m→∞} \frac{1}{k^{m}} ∑_{σ∈\{1,...,k\}^{m}}⟨PLUR_{m,k}(σ), T_{ρ}(PLUR_{m,k})(σ)⟩ − ε.

1.3. A Synopsis of the Main Theorem. We now describe the proof of Theorem 1.2. We first take the derivative d/dρ of the quantity J defined by (3). This procedure is common, and it dates back at least to the the proof of the Log-Sobolev Inequality by Gross [9]. Taking this derivative allows us to relate J to the works [14, 16]. In Section 3, we modify the results of [14, 16] to prove the existence of a partition that maximizes (d/dρ)J. Then, in Section 4, we further modify results of [14, 16] to show that, if ρ > 0 is small, then a partition maximizing (d/dρ)J is close to a partition maximizing (d/dρ)|_{ρ=0}J. And by [14], we know that the partition maximizing (d/dρ)|_{ρ=0}J is a regular simplicial conical partition, for dimension n ≥ 2 and k = 3 partition elements.

So, for small ρ > 0, a partition maximizing (d/dρ)J is close to a regular simplicial conical partition. The structure of the operator T_{ρ} then permits the exploitation of a feedback loop. This feedback loop says: if our partition maximizes (d/dρ)J for small ρ > 0, and if this partition is close to a regular simplicial conical partition, then this partition is even closer to a regular simplicial conical partition. This feedback loop is investigated in Section 5, especially in the crucial Lemma 6.1. A similar feedback loop was already apparent in [14][Lemma 3.3]. The full argument of Theorem 1.2 is then assembled in Section 7. By using this feedback loop, we show in Theorem 7.1 that a regular simplicial conical partition maximizes (d/dρ)J for small ρ > 0, k = 3, n ≥ 2. Then, the Fundamental Theorem of Calculus allows us to relate (d/dρ)J to J, therefore completing the proof of the main theorem, Theorem 1.2.

Since Lemma 6.1 is rather lengthy and crucial to this investigation, we will further describe the idea behind it. If we know that our partition maximizes (d/dρ)J, and if we also know that this partition is close to a regular simplicial conical partition, then the first variation should immediately tell us that our partition is actually a regular simplicial conical partition. Unfortunately, this intuition does not translate into a proof. The main technical problem is that the sets we are dealing with are unbounded, and we need to know precise information about the Ornstein-Uhlenbeck operator applied to these sets, for points that are very far from the origin. Since the Gaussian measure decays exponentially away from the origin, this means that it becomes hard to say something precise about the points in these sets that are very far from the origin. So, we require very precise estimates of the Ornstein-Uhlenbeck operator, and the errors that it accrues when we evaluate it far from the origin. These estimates are performed in Lemmas 5.2 and 5.3. Unfortunately, to use these estimates effectively, we need to slowly enlarge the regions where we use these estimates. The details of enlarging these regions becomes surprisingly complicated, occupying the seven steps of Lemma 6.1.

In Section 7, we also show the surprising fact that our strategy fails for small negative correlation. That is, for small ρ < 0, (d/dρ)J is not maximized by the regular simplicial conical partition. This result does not confirm or deny Conjecture 1 for ρ < 0. However, one may interpret from this result that the case of Conjecture 1 for ρ < 0 could be more difficult than the case ρ > 0.

We should also emphasize the lack of symmetrization in the proof of Theorem 1.2. Symmetrization is one of a few general strategies that solves many optimization problems. In our context, symmetrization would appear as follows. Recall the definition of J from (3). Suppose we have a partition {A_{i}}_{i=1}^{k} ⊆ ℝ^{n}. Change this partition into a “more symmetric” partition {Ã_{i}}_{i=1}^{k} such that J or (d/dρ)J is larger for {Ã_{i}}_{i=1}^{k}. In the proof of the main theorem, it is tempting to use this symmetrization paradigm. The works [3],[19] and [12] use Gaussian symmetrization in a crucial way. However, we find this approach to be less natural for Conjecture 1, so we do not explicitly use symmetrization. Nevertheless, symmetry does play a crucial role in our proof, especially in the estimates of Section 4. It should also be noted that the works [14, 16] do not explicitly use symmetrization, and this lack of symmetrization is one of their novel aspects.

1.4. Preliminaries. We follow the exposition of [17]. Let n ≥ 1, n ∈ ℤ. Let ℕ = {0, 1, 2, 3, …}. For f: ℝ^{n} → ℝ measurable, let ∥f∥_{L_{2}(γ_{n})} := (∫_{ℝ^{n}} |f|^{2} dγ_{n})^{1/2}. Let L_{2}(γ_{n}) := {f: ℝ^{n} → ℝ: ∥f∥_{L_{2}(γ_{n})} < ∞}. Let ℓ_{2}^{n} denote the ℓ_{2} norm on ℝ^{n}. For x ∈ ℝ^{n} and r > 0, define B(x, r) := {y ∈ ℝ^{n}: ∥x − y∥_{ℓ_{2}^{n}} < r}.

For f ∈ L_{2}(γ_{n}), define T_{ρ} as in (2). The operator T_{ρ} is a parametrization of the Ornstein-Uhlenbeck operator. The operator T_{ρ} is not a semigroup, but it satisfies T_{ρ_{1}}T_{ρ_{2}} = T_{ρ_{1}ρ_{2}}, ρ_{1}, ρ_{2} ∈ [−1, 1], by (7) below. We use definition (2) since the usual Ornstein-Uhlenbeck operator is only defined for ρ ∈ [0, 1]. Let λ > 0, x ∈ ℝ. Recall that the Hermite polynomials of one variable are defined by the generating function

e^{λx−λ^{2}/2} =: ∑_{ℓ∈ℕ} λ^{ℓ}h_{ℓ}(x).  (5)

Alternatively, one defines the polynomials H_{ℓ}(x) such that h_{ℓ}(x) = 2^{−ℓ/2}(ℓ!)^{−1}H_{ℓ}(x/\sqrt{2}). This convention is used in [1], where the orthogonality properties of the Hermite polynomials are derived.

Note that ∫_{ℝ} h_{ℓ}^{2}dγ_{1} = 1/ℓ!, and \{\sqrt{ℓ!} h_{ℓ}\}_{ℓ∈ℕ} is an orthonormal basis of L_{2}(γ_{1}). Recall also that h_{0}(x) = 1 and h_{1}(x) = x. Set f(x) := e^{λx−λ^{2}/2}. A routine computation shows that T_{ρ}(f)(x) = e^{(λρ)x−(λρ)^{2}/2}. Indeed

T_{ρ}(f)(x) = ∫_{ℝ^{n}} e^{λ(xρ+y\sqrt{1−ρ^{2}})−λ^{2}/2}dγ_{1}(y) = ∫_{ℝ^{n}} e^{(λρ)x+(λ\sqrt{1−ρ^{2}})y−λ^{2}/2−y^{2}/2} \frac{dy}{\sqrt{2π}}

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

= e^{(λρ)x−(λρ)^{2}/2}.

Therefore, by (5),

T_{ρ}f(x) = ∑_{ℓ∈ℕ} λ^{ℓ}ρ^{ℓ}h_{ℓ}(x).  (6)

So, by linearity, T_{ρ}h_{ℓ}(x) = ρ^{ℓ}h_{ℓ}(x).

We now extend the above observations to higher dimensions. Let f ∈ L_{2}(γ_{n}), so that f = ∑_{ℓ∈ℕ^{n}} a_{ℓ}h_{ℓ}\sqrt{ℓ!}, a_{ℓ} ∈ ℝ, where ℓ = (ℓ_{1}, …, ℓ_{n}) ∈ ℕ^{n} and h_{ℓ}(x) = ∏_{i=1}^{n} h_{ℓ_{i}}(x_{i}). Write |ℓ| := ℓ_{1} + ⋯ + ℓ_{n} and ℓ! := (ℓ_{1}!) ⋯ (ℓ_{n}!). Then T_{ρ} satisfies T_{ρ}h_{ℓ} = ρ^{|ℓ|}h_{ℓ} and for x ∈ ℝ^{n},

T_{ρ}f(x) = ∑_{ℓ∈ℕ^{n}} ρ^{|ℓ|}\sqrt{ℓ!} h_{ℓ}(x) (∫_{ℝ^{n}} \sqrt{ℓ!} h_{ℓ}fdγ_{n})  (7)

Let Δ := ∑_{i=1}^{n} ∂^{2}/∂x_{i}^{2}, and define

L := −Δ + ∑_{i=1}^{n} x_{i} · \frac{∂}{∂x_{i}} .  (8)

A well-known calculation shows the following equality, which we prove in the Appendix, Section 9.

\frac{d}{dρ}T_{ρ}f(x) = ρ^{−1}LT_{ρ}f(x) = \frac{1}{ρ} (⟨x, ∇T_{ρ}f(x)⟩ − ΔT_{ρ}f(x))  (9)

= \frac{1}{\sqrt{1 − ρ^{2}}} [ ⟨x, ∫_{ℝ^{n}} yf(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y)⟩

+ \frac{ρ}{\sqrt{1 − ρ^{2}}} ∫_{ℝ^{n}} (∑_{i=1}^{n}(1 − y_{i}^{2})) f(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y)].  (10)

We say that A ⊆ ℝ^{n} is a cone if A is measurable and ∀ t > 0, tA = A.

Definition 1.7. A simplicial conical partition {A_{i}}_{i=1}^{k} is a partition of ℝ^{n} together with a simplex S ⊆ ℝ^{k−1} with 0 ≤ k −1 ≤ n and a rotation σ of ℝ^{n} such that 0 ∈ S and such that each facet F_{i} of σ(S × ℝ^{n−k+1}) generates a partition element, i.e. A_{i} = {tσ(F_{i} × ℝ^{n−j}): t ∈ [0, ∞)}, i ∈ {1, …, j +1}. Let k −1 ≤ n and let {z_{i}}_{i=1}^{k} ⊆ ℝ^{n} be nonzero vectors that do not all lie in a (k − 1)-dimensional hyperplane. Define a partition such that, for i ∈ {1, …, k}, A_{i} := {x ∈ ℝ^{n}: ⟨x, z_{i}⟩ = max_{j=1,...,k}⟨x, z_{j}⟩}. Such a partition is called the simplicial conical partition induced by {z_{i}}_{i=1}^{k}.

If {A_{i}}_{i=1}^{k} is a simplicial conical partition induced by the vectors {∫_{A_{i}} xdγ_{n}(x)}_{i=1}^{k}, then we say the partition is a balanced conical partition. If {z_{i}}_{i=1}^{k} ⊆ ℝ^{n} are the vertices of a (k − 1)-dimensional regular simplex in ℝ^{n} centered at the origin, then the partition induced by {z_{i}}_{i=1}^{k} is called a regular simplicial conical partition.

Let f ∈ L_{2}(γ_{n}). By Plancherel and (7)

∫_{ℝ^{n}} fT_{ρ}fdγ_{n} = ∑_{ℓ∈ℕ^{n}} ρ^{|ℓ|} |∫_{ℝ^{n}} f\sqrt{ℓ!}h_{ℓ}dγ_{n}|^{2} .  (11)

Substituting (11) into (3) gives

∑_{i=1}^{k} ∫_{ℝ^{n}} 1_{A_{i}}T_{ρ}(1_{A_{i}})dγ_{n} = ∑_{i=1}^{k} [γ_{n}(A_{i})^{2} + ρ ∥∫_{A_{i}} xdγ_{n}(x)∥_{ℓ_{2}^{n}}^{2} + ∑_{\begin{matrix}ℓ∈ℕ^{n} \\ |ℓ|≥2 \end{matrix}} ρ^{|ℓ|} |∫_{A_{i}} \sqrt{ℓ!}h_{ℓ}dγ_{n}|^{2} ]. (12)

Taking the derivative d/dρ of (12) at ρ = 0, we get a quantity studied in [14, 16].

\frac{d}{dρ} ∑_{i=1}^{k} ∫_{ℝ^{n}} 1_{A_{i}}T_{ρ}(1_{A_{i}})dγ_{n} = ∑_{i=1}^{k} [ ∥∫_{A_{i}} xdγ_{n}(x)∥_{ℓ_{2}^{n}}^{2} + ∑_{\begin{matrix}ℓ∈ℕ^{n} \\ |ℓ|≥2 \end{matrix}} |ℓ| ρ^{|ℓ|−1} |∫_{A_{i}} \sqrt{ℓ!}h_{ℓ}dγ_{n}|^{2} ]. (13)

\frac{d}{dρ}|_{ρ=0} ∑_{i=1}^{k} ∫_{ℝ^{n}} 1_{A_{i}}T_{ρ}(1_{A_{i}})dγ_{n} = ∑_{i=1}^{k} ∥∫_{A_{i}} xdγ_{n}(x)∥_{ℓ_{2}^{n}}^{2} .  (14)

2. Noise Stability for Zero Correlation

This section concerns noise stability at the endpoint ρ = 0. Specifically, we will investigate the quantity (14), which has already been studied in [14, 16]. Using our understanding of (14), we will then be able to analyze the left side of (13) when ρ is small, using the equality (13). Before beginning our discussion, we first need to consider partitions of ℝ^{n} within the convex set defined in (15). Definition 2.3 provides the metric allowing an assertion that two partitions are close to each other, and Definition 2.4 allows us to discuss the Gaussian measure restricted to hypersurfaces.

Definition 2.1. Let H := ⊕_{i=1}^{k}L_{2}(γ_{n}) and define

Δ_{k}(γ_{n}) := {(f_{1}, …, f_{k}) ∈ H: ∀ 1 ≤ i ≤ k, 0 ≤ f_{i} ≤ 1, ∑_{i=1}^{k} f_{i} = 1}.  (15)

Definition 2.2. Let ε ≥ 0. Define

Δ_{k}^{ε}(γ_{n}) := \{(f_{1}, …, f_{k}) ∈ Δ_{k}(γ_{n}): \frac{1}{k} − ε ≤ ∫_{ℝ^{n}} f_{i}dγ_{n} ≤ \frac{1}{k} + ε\}.

Definition 2.3. Define a metric d_{2} on partitions {A_{i}}_{i=1}^{k}, {C_{i}}_{i=1}^{k} of ℝ^{n} by the formula

d_{2}({A_{i}}_{i=1}^{k}, {C_{i}}_{i=1}^{k}) := inf_{σ∈SO(n) π a permutation} (∑_{i=1}^{k} ∥1_{A_{i}} − 1_{(σC_{π(i)})}∥_{L_{2}(γ_{n})}^{2})^{1/2} .

Definition 2.4. Let A ⊆ ℝ^{n}, let L denote Lebesgue measure on ℝ^{n}, and define the distance d(x, y) := ∥x − y∥_{ℓ_{2}^{n}}, x, y ∈ ℝ^{n}. Denote δ_{A} as the measure L on ℝ^{n} restricted to A. That is, δ_{A}(B) := lim inf_{δ→0} \frac{1}{2δ}L\{y ∈ ℝ^{n}: ∃ x ∈ A ∩ B with d(x, y) < δ\}, B ⊆ ℝ^{n}. Also, we denote γ_{n}(δ_{A}) := lim inf_{δ→0} \frac{1}{2δ}γ_{n}\{y ∈ ℝ^{n}: ∃ x ∈ A with d(x, y) < δ\}.

The next two lemmas are derived from [14]. Lemma 2.6 is a quantitative variant of Lemma 2.5, and it will be further improved in Lemma 2.8 below. In particular, Lemma 2.6 says that, if the first variation condition for achieving the optimum value of (16) is nearly satisfied, then the partition is close to being simplicial.

Lemma 2.5. [14, Lemma 3.3, Corollary 3.4] Let n ≥ 2 and let {B_{i}}_{i=1}^{3} be a regular simplicial conical partition of ℝ^{n}. Then (1_{B_{1}}, 1_{B_{2}}, 1_{B_{3}}) uniquely achieves the following supremum, up to orthogonal transformation.

sup_{(f_{1},f_{2},f_{3})∈Δ_{3}(γ_{n})} ∑_{i=1}^{3} ∥∫_{ℝ^{n}} xf_{i}(x)dγ_{n}(x)∥_{ℓ_{2}^{n}}^{2} .  (16)

Lemma 2.6. Let n ≥ 2 and let {B_{i}}_{i=1}^{3}, {C_{i}}_{i=1}^{2} ⊆ ℝ^{n} be regular simplicial conical partition. Let {A_{i}}_{i=1}^{3} ⊆ ℝ^{n} be a simplicial conical partition. Let z_{i} := ∫_{A_{i}} xdγ_{n}(x), and let v_{ij} ∈ S^{n−1} ∩ A_{i} ∩ A_{j} ∩ span{z_{i}, z_{j}}. If |⟨z_{i} − z_{j}, v_{ij}⟩| ≤ ε < 10^{−16} ∀ i, j ∈ {1, 2, 3}, i ≠ j, and if d_{2}(\{A_{i}\}_{i=1}^{3}, \{C_{1}, C_{2}, ∅\}) > 1/100, then d_{2}(\{A_{i}\}_{i=1}^{3}, \{B_{i}\}_{i=1}^{3}) ≤ \sqrt{6ε}.

Proof. For i, j ∈ {1, 2, 3}, let 0 ≤ α_{i} ≤ π such that A_{i} is a cone with angle α_{i}. Let σ: ℝ^{n} → ℝ^{n} be a reflection that fixes A_{i} ∩ A_{j}. Without loss of generality, σ(A_{j}) ⊆ A_{i}. Then z_{i} − z_{j} = ∫_{A_{i}\σ(A_{j})} xdγ_{n}(x) and ∥z_{i} − z_{j}∥_{2} = sin((α_{i} − α_{j})/2)/\sqrt{2π}. Let 0 ≤ θ ≤ π such that

∥z_{i} − z_{j}∥_{2} cos(θ) = ⟨z_{i} − z_{j}, v_{ij}⟩. Then either ∥z_{i} − z_{j}∥_{2} ≤ \sqrt{ε/18π}, or |cos θ| ≤ \sqrt{18πε}. In the first case, α_{i} − α_{j} ≤ \sqrt{ε}. So, to complete the proof, it suffices to show that the second case does not occur. We find a contradiction by assuming that the second case occurs.

If |cos θ| ≤ \sqrt{18πε}, then since θ = (α_{i} − α_{j})/2, we must have |α_{i} − α_{j} − π| < 18\sqrt{ε}, so π − 18\sqrt{ε} < α_{i} − α_{j} < π + 18\sqrt{ε}, i.e. π − 18\sqrt{ε} < α_{i} ≤ π and α_{j} ≤ 18\sqrt{ε}. Then for r ≠ i, j, r ∈ \{1, 2, 3\}, we have α_{r} = 2π−α_{i}−α_{j} > 2π−π−18\sqrt{ε} > π−18\sqrt{ε}. Since α_{i}, α_{j} > π−18\sqrt{ε}, we conclude that d_{2}({A_{i}}_{i=1}^{3}, {C_{1}, C_{2}, ∅}) < 18ε^{1/4} < 1/100, a contradiction. □

We require the ensuing explicit calculation from [14] in Lemma 2.8 below. This calculation is reduced to a computation of Lagrange Multipliers in [14, Corollary 3.4]. For any (f_{1}, …, f_{k}) ∈ Δ_{k}(γ_{n}), define ψ_{0}(f_{1}, …, f_{k}) := ∑_{i=1}^{k} ∥∫_{ℝ^{n}} xf_{i}(x)dγ_{n}(x)∥_{ℓ_{2}^{n}}^{2}.

Lemma 2.7. [14, Corollary 3.4]

sup_{(f_{1},f_{2})∈Δ_{2}(γ_{n})} ψ_{0}(f_{1}, f_{2}) = \frac{1}{π} , sup_{(f_{1},f_{2},f_{3})∈Δ_{3}(γ_{n})} ψ_{0}(f_{1}, f_{2}, f_{3}) = \frac{9}{8π} .

The following Lemma is a quantitative improvement of Lemmas 2.5 and 2.6. Combining Lemma 2.8 with (14) will show that an optimizer of (d/dρ) ∑_{i=1}^{k} ∫_{ℝ^{n}} 1_{A_{i}}T_{ρ}1_{A_{i}}dγ_{n} is almost simplicial conical for small ρ > 0.

Lemma 2.8. Let ε > 0, n ≥ 2. Let {A_{i}}_{i=1}^{3} be a partition of ℝ^{n}, and let {B_{i}}_{i=1}^{3} be a regular simplicial conical partition of ℝ^{n}. Assume that ε < 1/100 and

ψ_{0}(1_{A_{1}}, 1_{A_{2}}, 1_{A_{3}}) > sup_{(f_{1},f_{2},f_{3})∈Δ_{3}(γ_{n})} ψ_{0}(f_{1}, f_{2}, f_{3}) − ε.  (17)

Then

d_{2}({A_{i}}_{i=1}^{3}, {B_{i}}_{i=1}^{3}) ≤ 6ε^{1/8}.  (18)

Proof. Assume that (17) holds. For i ∈ {1, 2, 3}, let z_{i} := ∫_{A_{i}} xdγ_{n}(x), w_{i} := ∫_{B_{i}} xdγ_{n}(x). We may assume that, for all i, j ∈ {1, 2, 3} with i ≠ j, ⟨z_{i}, z_{j}⟩ < 0. To see this, we argue by contradiction. Suppose there exist i, j ∈ {1, 2, 3}, i ≠ j with ⟨z_{i}, z_{j}⟩ ≥ 0. For p ∈ {1, 2, 3}, p ≠ i, j, let A′′_{p} := A_{p}, let A′′_{i} := A_{i} ∪ A_{j}, and let A′′_{j} := ∅. For p ∈ {1, 2, 3}, let z′′_{p} := ∫_{A′′_{p}} xdγ_{n}(x). Then

∑_{p=1}^{3} ∥z′′_{p}∥_{ℓ_{2}^{n}}^{2} − ∑_{p=1}^{3} ∥z_{p}∥_{ℓ_{2}^{n}}^{2} = ∥z_{i} + z_{j}∥_{ℓ_{2}^{n}}^{2} − ∥z_{i}∥_{ℓ_{2}^{n}}^{2} − ∥z_{j}∥_{ℓ_{2}^{n}}^{2} ≥ 0.

Rewriting this inequality using the definition of ψ_{0},

ψ_{0}(1_{A_{1}}, 1_{A_{2}}, 1_{A_{3}}) ≤ ψ_{0}(1_{A′′_{1}}, 1_{A′′_{2}}, 1_{A′′_{3}}).  (19)

Since {A′′_{p}}_{p=1}^{3} is a partition of ℝ^{n} with at most two nonempty elements, Lemma 2.7 says

( sup_{(f_{1},f_{2},f_{3})∈Δ_{3}(γ_{n})} ψ_{0}(f_{1}, f_{2}, f_{3})) − ψ_{0}(1_{A′′_{1}}, 1_{A′′_{2}}, 1_{A′′_{3}}) ≥ \frac{1}{8π} > 10^{−2}.  (20)

Combining (19) and (20) contradicts (17). Therefore, ⟨z_{i}, z_{j}⟩ < 0 for all i, j ∈ {1, 2, 3}. We now claim that, for each pair i, j ∈ {1, 2, 3} with i ≠ j, we have

max_{p∈{i,j}} ∥z_{p}∥_{ℓ_{2}^{n}}^{2} ≥ 1/16.  (21)

We again argue by contradiction. Suppose there exist i, j ∈ {1, 2, 3} with i ≠ j and max_{p∈{i,j}} ∥z_{p}∥_{ℓ_{2}^{n}}^{2} < 1/16. Let p ∈ {1, 2, 3}, p ≠ i, j. Then ∥z_{p}∥_{ℓ_{2}^{n}}^{2} ≤ 1/(2π) with equality if and only if 1_{A_{p}} is a half-space whose boundary contains the origin of ℝ^{n}. This follows immediately from rearrangement. Observe, if z_{p} ≠ 0,

∥z_{p}∥_{ℓ_{2}^{n}}^{2} = ⟨z_{p}, ∫_{A_{p}} xdγ_{n}(x)⟩ ≤ ⟨z_{p}, ∫_{A_{p}∩{x: ⟨x,z_{p}⟩≥0}} xdγ_{n}(x)⟩ ≤ ⟨z_{p}, ∫_{{x: ⟨x,z_{p}⟩≥0}} xdγ_{n}(x)⟩

= ⟨ ∫_{A_{p}} xdγ_{n}(x), ∫_{\{x: ⟨x,z_{p}⟩≥0\}} xdγ_{n}(x)⟩ ≤ || ∫_{\{x: ⟨x,z_{p}⟩≥0\}} xdγ_{n}(x)||_{ℓ_{2}^{n}}^{2} = \frac{1}{2π} .

Therefore,

ψ_{0}(1_{A_{1}}, 1_{A_{2}}, 1_{A_{3}}) ≤ 1/8 + 1/(2π) ≤ 1/π.

This inequality contradicts (17) as in (20), since sup_{(f_{1},f_{2},f_{3})∈Δ_{k}(γ_{n})} ψ_{0}(f_{1}, …, f_{k}) = 9/(8π), using Lemma 2.7. We conclude that (21) holds.

Define δ such that

δ := max_{i,j∈{1,2,3},i≠j} γ_{n}({x ∈ ℝ^{n}: ⟨z_{i} − z_{j}, x⟩ ≤ 0} ∩ A_{i}).  (22)

Fix i, j ∈ {1, 2, 3} such that δ = γ_{n}({x ∈ ℝ^{n}: ⟨z_{i}−z_{j}, x⟩ ≤ 0}∩A_{i}). We want to find a bound on δ. Let 0 < h such that ∫_{0}^{h} dγ_{1} = δ. Now, define {A′_{r}}_{r=1}^{3} such that A′_{p} = A_{p} for p ≠ i, j, A′_{i} = A_{i} \ (A_{i} ∩ {x ∈ ℝ^{n}: ⟨z_{i} − z_{j}, x⟩ ≤ 0}) and A′_{j} = A_{j} ∪ (A_{i} ∩ {x ∈ ℝ^{n}: ⟨z_{i} − z_{j}, x⟩ ≤ 0}). Let z′_{p} := ∫_{A′_{p}} xdγ_{n}(x), p = 1, 2, 3. Then

\begin{matrix}∑_{p=1}^{3} ∥z′_{p}∥_{ℓ_{2}^{n}}^{2} − ∑_{p=1}^{3} ∥z_{p}∥_{ℓ_{2}^{n}}^{2} \\ = 2⟨ ∫_{\{y: ⟨z_{i}−z_{j},y⟩≤0\}∩A_{i}} ydγ_{n}(y), z_{j} − z_{i}⟩ + 2∥ ∫_{\{y: ⟨z_{i}−z_{j},y⟩≤0\}∩A_{i}} ydγ_{n}(y)∥_{ℓ_{2}^{n}}^{2} \\ ≥ 2⟨ ∫_{\{y: −h≤⟨z_{i}−z_{j},y⟩≤0\}} ydγ_{n}(y), z_{j} − z_{i}⟩ = 2 ∥z_{i} − z_{j}∥_{ℓ_{2}^{n}} ∫_{0}^{h} ydγ_{1}(y) >^{(21)} δ^{2}/3. \end{matrix} (23)

Here we used rearrangement and also the inequality ∥z_{i} − z_{j}∥_{ℓ_{2}^{n}} > (max_{p∈{i,j}} ∥z_{p}∥_{ℓ_{2}^{n}}^{2})^{1/2}, which itself uses ⟨z_{i}, z_{j}⟩ < 0.

By (17) and (23), δ^{2} < 3ε, i.e.

δ < \sqrt{3ε}.  (24)

Now, for p ∈ {1, 2, 3}, let Ã_{p} := {x ∈ ℝ^{n}: ⟨x, z_{p}⟩ = max_{j=1,2,3}⟨x, z_{j}⟩} and let z̃_{p} := ∫Ã_{p} xdγ_{n}(x). By (24) and (22),

d_{2}(\{A_{i}\}_{i=1}^{3}, \{Ã_{i}\}_{i=1}^{3}) ≤ 3\sqrt{2} ε^{1/4}.  (25)

For p ∈ \{1, 2, 3\}, let y_{p} := z̃_{p} − z_{p} ∈ ℝ^{n}, so that ∥y_{p}∥_{2} ≤ 3\sqrt{2} ε^{1/4} by (25) and Hilbert space duality. Let x ∈ ℝ^{n}. Then for i, j ∈ {1, 2, 3}, i ≠ j,

⟨z̃_{i} − z̃_{j}, x⟩ = ⟨z_{i} − z_{j}, x⟩ + ⟨y_{i} − y_{j}, x⟩.  (26)

For i, j ∈ {1, 2, 3}, i ≠ j, let v_{ij} = S^{n−1} ∩ Ã_{i} ∩ Ã_{j} ∩ span{z̃_{i}}_{i=1}^{3}. By definition of v_{ij} and \{Ã_{i}\}_{i=1}^{3}, ⟨z_{i} − z_{j}, v_{ij}⟩ = 0. So, by (26), |⟨z̃_{i} − z̃_{j}, v_{ij}⟩| ≤ 3\sqrt{2} ε^{1/4}, implying that d_{2}({Ã_{i}}_{i=1}^{3}, {B_{i}}_{i=1}^{3}) ≤ 3 · 2^{3/4}ε^{1/8}, by Lemma 2.6. This inequality together with (25) and the triangle inequality for d_{2} prove (18). □

3. The First Variation

Recall (8). The following existence argument which uses convexity is a variant of [14, Lemma 3.1] and [16, Lemma 2.1].

Lemma 3.1 (First Variation). Let ρ ∈ (0, 1). Then ∃ a partition {A_{i}}_{i=1}^{k} of ℝ^{n} such that

∑_{i=1}^{k} ∫_{ℝ^{n}} 1_{A_{i}} \frac{d}{dρ}T_{ρ}1_{A_{i}}dγ_{n} = sup_{(f_{1},...,f_{k})∈Δ_{k}(γ_{n})} ∑_{i=1}^{k} ∫_{ℝ^{n}} f_{i} \frac{d}{dρ}T_{ρ}f_{i}dγ_{n}  (27)

Also, for each i ∈ {1, …, k}, the following containment holds, less sets of γ_{n} measure zero:

A_{i} ⊇ {x ∈ ℝ^{n}: LT_{ρ}1_{A_{i}}(x) > LT_{ρ}1_{A_{j}}(x), ∀ j ≠ i, j ∈ {1, …, k}}.  (28)

Proof. We show that (3) is maximized over Δ_{k}(γ_{n}), which contains the set of partitions of ℝ^{n}. Note that Δ_{k}(γ_{n}) ⊆ H is norm closed, convex, and norm bounded. Therefore, Δ_{k}(γ_{n}) is weakly closed. Also, Δ_{k}(γ_{n}) is weakly compact by the Banach-Alaoglu Theorem. Using (9), define ψ_{ρ}: Δ_{k}(γ_{n}) → ℝ by

ψ_{ρ}(g_{1}, …, g_{k}) := \frac{d}{dρ} ∑_{i=1}^{k} ∫_{ℝ^{n}} g_{i}T_{ρ}g_{i}dγ_{n} := ρ^{−1} ∑_{i=1}^{k} ∫_{ℝ^{n}} g_{i}LT_{ρ}g_{i}dγ_{n}.  (29)

By (12), ψ_{ρ} is an exponentially decaying sum of uniformly bounded weakly continuous functions. Therefore, ψ_{ρ} is weakly continuous on the weakly compact set Δ_{k}(γ_{n}). So there exists (f_{1}, …, f_{k}) ∈ Δ_{k}(γ_{n}) that maximizes ψ_{ρ}.

Since ρ ∈ (0, 1], (13) implies: ∀ f ∈ L_{2}(γ_{n}), ∫ fLT_{ρ}fdγ_{n} ≥ 0. We now apply this fact to see that ψ_{ρ} is convex. Let λ ∈ [0, 1], (g_{1}, …, g_{k}), (h_{1}, …, h_{k}) ∈ Δ_{k}(γ_{n}). Then

λψ_{ρ}(g_{1}, …, g_{k}) + (1 − λ)ψ_{ρ}(h_{1}, …, h_{k}) − ψ_{ρ}(λg_{1} + (1 − λ)h_{1}, …, λg_{k} + (1 − λ)h_{k})

= \frac{1}{ρ} ∑_{i=1}^{k} [λ ∫_{ℝ^{n}} g_{i}LT_{ρ}g_{i} + (1 − λ) ∫_{ℝ^{n}} h_{i}LT_{ρ}h_{i} − ∫_{ℝ^{n}}(λg_{i} − (1 − λ)h_{i})LT_{ρ}(λg_{i} − (1 − λ)h_{i})]

= λ(1 − λ) ∫_{ℝ^{n}}(g_{i} − h_{i})LT_{ρ}(g_{i} − h_{i}) ≥ 0.

Since ψ_{ρ} is convex on Δ_{k}(γ_{n}), ψ_{ρ} achieves its maximum at an extreme point of Δ_{k}(γ_{n}). Therefore, there exists a partition {A_{i}}_{i=1}^{k} of ℝ^{n} such that (1_{A_{1}}, …, 1_{A_{k}}) ∈ Δ_{k}(γ_{n}) maximizes ψ_{ρ} on Δ_{k}(γ_{n}) [16, Lemma 2.1]. Specifically, it is noted in [16, Lemma 2.1] that the extreme points of Δ_{k}(γ_{n}) are exactly the partitions of ℝ^{n} into k pieces.

We now prove (28) by contradiction. By the Lebesgue density theorem [21][1.2.1, Proposition 1], we may assume that, for all i ∈ {1, …, k}, if y ∈ A_{i}, then we have lim_{r→0} γ_{n}(A_{i} ∩ B(y, r))/γ_{n}(B(y, r)) = 1. Suppose there exist j, m ∈ {1, …, k} and there exists y ∈ ℝ^{n}, r > 0 such that y ∈ A_{j}, γ_{n}(B(y, r) ∩ A_{j}) > 0 and LT_{ρ}1_{A_{j}}(y) < LT_{ρ}1_{A_{m}}(y). By (2),

T_{ρ}1_{A_{j}}(x) = ∫_{ℝ^{n}} 1_{A_{j}}(y)e^{−∥y−xρ∥_{2}^{2}/[2(1−ρ^{2})]} \frac{dy}{(2π(1 − ρ^{2}))^{n/2}} .

So, LT_{ρ}1_{A_{j}} = ρ(d/dρ)T_{ρ}1_{A_{j}}(x) is a continuous function of x.

Therefore, there exists a ball B(y, r), r > 0 such that γ_{n}(B(y, r) ∩ A_{j}) > 0 and such that

sup_{x∈B(y,r)} LT_{ρ}1_{A_{j}}(x) < inf_{x∈B(y,r)} LT_{ρ}1_{A_{m}}(x).

Let ϕ(x) := 1_{B(y,r)∩A_{j}}(x). For λ ∈ [0, 1], note that

(1_{A_{1}}, …, 1_{A_{j}} − λϕ, …, 1_{A} + λϕ, …, 1_{A_{k}}) ∈ Δ_{k}(γ_{n}).  (30)

However,

\frac{d}{dλ}|_{λ=0} ψ_{ρ}(1_{A_{1}}, …, 1_{A_{j}}−λϕ, …, 1_{A_{m}}+λϕ, …, 1_{A_{k}}) = \frac{2}{ρ} ∫ ϕ(x)LT_{ρ}(1_{A_{m}}−1_{A_{j}})(x)dγ_{n}(x) > 0.

(31)

But (31) contradicts the maximality of (1_{A_{1}}, …, 1_{A_{k}}) on Δ_{k}(γ_{n}), so (28) holds.

□

4. Perturbative Estimates

Recalling (29), the following estimates allow us to relate ψ_{ρ} to ψ_{0} for small ρ > 0, for simplicial conical partitions. In particular, we make a close examination of the two quantities of (10). Since lemma 4.2 gives precise estimates of the two quantities of (10), combining Lemma 4.2 with (28) gives precise geometric information about a partition {A_{i}}_{i=1}^{k} ⊆ ℝ^{n} optimizing noise stability. In particular, to see one way that we will apply Lemma 4.2, see (121) below. However, note that (121) below does not give sufficiently precise information to identify the sets optimizing noise stability. So, the real need for Lemma 4.2 will occur in the proof of the Main Lemma 6.1, where the precise estimate (51) is used.

Lemma 4.1. Let A ⊆ ℝ^{n} be a cone. Then

∫_{ℝ^{n}} ( ∑_{i=1}^{n}(1 − y_{i}^{2}))1_{A}(y)dγ_{n}(y) = 0.

Proof. The assertion follows by standard equalities for the moments of a Gaussian random variable. Let α > 0. Define f(α) by the formula

f(α) := ∫_{ℝ^{n}} 1_{A}(y)e^{−α(y_{1}^{2}+···+y_{n}^{2})/2} \frac{dy}{(2π)^{n/2}} .

By changing variables, f(α) = α^{−n/2} ∫_{ℝ^{n}} 1_{A}(y)dγ_{n}(y). So,

−\frac{1}{2} ∫_{ℝ^{n}} ( ∑_{i=1}^{n} y_{i}^{2})1_{A}(y)dγ_{n}(y) = \frac{df(α)}{dα}|_{α=1} = −\frac{n}{2} ∫_{ℝ^{n}} 1_{A}(y)dγ_{n}(y).

□

Lemma 4.2. Fix k = 3, n ≥ 2, ρ ∈ (0, 1). Let {C_{i}}_{i=1}^{k} ⊆ ℝ^{2} be a simplicial conical partition. Let {B_{i}}_{i=1}^{k} := {C_{i} × ℝ^{n−2}}_{i=1}^{k}. Fix i, j ∈ {1, …, k}. Let σ: ℝ^{n} → ℝ^{n} denote reflection across B_{i} ∩ B_{j}. Assume that B_{i} = σB_{j} and that B_{i} ⊆ {x ∈ ℝ^{n}: x_{1} ≥ 0}. Let e_{1} = (1, 0, …, 0), e_{2} = (0, 1, 0, …, 0), e_{1}, e_{2} ∈ ℝ^{n}. For p ∈ {1, …, k}, let z_{p} := ∫_{B_{p}} xdγ_{n}(x). Note that span{z_{i}, z_{j}} = span{e_{1}, e_{2}}. Let n_{j} ∈ ℝ^{n} be the interior unit normal of B_{j} so that n_{j} is normal to the face (∂B_{j}) \ (∂B_{i}), and let n_{i} ∈ ℝ^{n} be the interior unit normal of B_{i} so that n_{i} is normal to the face (∂B_{i}) \ (∂B_{j}).

(i) If x ∈ B_{i} ∩ {x ∈ ℝ^{n}: ⟨x, n_{j}⟩ ≤ 0}, then

\frac{1}{ρ} ⟨x, ∇T_{ρ}(1_{B_{i}} − 1_{B_{j}})(x)⟩ ≥ 2x_{1}γ_{n} (δ_{\frac{(B_{i}∩B_{j})−xρ}{\sqrt{1−ρ^{2}}}} ) + ⟨x, n_{i}⟩γ_{n} (δ_{\frac{((∂B_{i})\B_{j})−xρ}{\sqrt{1−ρ^{2}}}} ) . (32)

13

(ii) If x ∈ B_{i} ∩ {x ∈ ℝ^{n}: ⟨x, n_{j}⟩ ≥ 0}, then

\frac{1}{ρ} ⟨x, ∇T_{ρ}(1_{B_{i}} − 1_{B_{j}})(x)⟩ ≥ 2x_{1}γ_{n} (δ_{\frac{(B_{i}∩B_{j})−xρ}{\sqrt{1−ρ^{2}}}} ) .  (33)

(iii) For x ∈ B_{i},

| ∫_{ℝ^{n}} ( ∑_{ℓ=1}^{n}(1 − y_{ℓ}^{2}))(1_{B_{i}} − 1_{B_{j}})(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y)| ≤ \frac{ρ}{\sqrt{1 − ρ^{2}}} (\sqrt{6} + (n − 1)\sqrt{2})x_{1}.

(34)

(iv) For x ∈ B_{i} with x_{1} > \sqrt{n}\sqrt{1 − ρ^{2}}/ρ,

∫_{ℝ^{n}} ( ∑_{ℓ=1}^{n}(1 − y_{ℓ}^{2}))(1_{B_{i}} − 1_{B_{j}})(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y) ≥ 0.  (35)

Proof of (i). Below, we use differentiation in the distributional sense. Let x ≠ 0. For x ∈ (∂B_{i}) ∩ B_{j}, ∇1_{B_{i}}(x) = e_{1} since B_{i} ⊆ {x ∈ ℝ^{n}: x_{1} ≥ 0}, and for x ∈ (∂B_{i}) \ B_{j}, ∇1_{B_{i}}(x) = n_{i}. Similarly, for x ∈ (∂B_{j}) ∩ B_{i}, −∇1_{B_{j}}(x) = e_{1}, and for x ∈ (∂B_{j}) \ B_{i}, −∇1_{B_{j}}(x) = −n_{j}. Then

\begin{matrix}\frac{1}{ρ}∇T_{ρ}(1_{B_{i}} − 1_{B_{j}})(x) = T_{ρ}(∇(1_{B_{i}} − 1_{B_{j}}))(x) \\ = T_{ρ}[2(e_{1})δ_{B_{i}∩B_{j}} + n_{i}δ_{(∂B_{i})\B_{j}} + (−n_{j})δ_{(∂B_{j})\B_{i}}](x) \\ =^{(2)} 2e_{1}γ_{n} (δ_{\frac{(B_{i}∩B_{j})−xρ}{\sqrt{1−ρ^{2}}}} ) + n_{i}γ_{n} (δ_{\frac{((∂B_{i})\B_{j})−xρ}{\sqrt{1−ρ^{2}}}} ) + (−n_{j})γ_{n} (δ_{\frac{((∂B_{j})\B_{i})−xρ}{\sqrt{1−ρ^{2}}}} ) . \end{matrix}  (36)

Here we used

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

Let x with x ∈ B_{i} and ⟨x, (−n_{j})⟩ ≥ 0. Then (36) immediately proves (32). □

Proof of (ii). Let x ∈ B_{i} ∩ {x ∈ ℝ^{n}: ⟨x, n_{j}⟩ ≥ 0}. By reflecting across B_{i} ∩ B_{j},

γ_{n} (δ_{\frac{((∂B_{i})\B_{j})−xρ}{\sqrt{1−ρ^{2}}}} ) ≥ γ_{n} (δ_{\frac{((∂B_{j})\B_{i})−xρ}{\sqrt{1−ρ^{2}}}} ) .  (37)

Define

w := n_{i}γ_{n} (δ_{\frac{((∂B_{i})\B_{j})−xρ}{\sqrt{1−ρ^{2}}}} ) + (−n_{j})γ_{n} (δ_{\frac{((∂B_{j})\B_{i})−xρ}{\sqrt{1−ρ^{2}}}} ) .

By (37), w is in the convex hull of e_{1} and n_{i}. In particular, ⟨x, w⟩ ≥ 0, since x ∈ B_{i}. Combining ⟨x, w⟩ ≥ 0 with (36) proves (33). □

Proof of (iii). By reflecting across B_{i} ∩ B_{j},

x ∈ B_{i} ∩ B_{j} ⟹ ∫_{ℝ^{n}} ( ∑_{ℓ=1}^{n}(1 − y_{ℓ}^{2}))(1_{B_{i}} − 1_{B_{j}})(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y) = 0.

So, a derivative bound gives (34). Specifically, we apply the Fundamental Theorem of Calculus to the following identity, along with ∥(1 − y_{2}^{2})y_{1}∥_{L_{2}(γ_{n})} = \sqrt{2} and ∥y_{1}^{3} + 3y_{1}∥_{L_{2}(γ_{n})} = \sqrt{6}.

\frac{∂}{∂x_{1}} ∫_{ℝ^{n}} ( ∑_{ℓ=1}^{n}(1 − y_{ℓ}^{2}))(1_{B_{i}} − 1_{B_{j}})(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y)

= \frac{ρ}{\sqrt{1 − ρ^{2}}} ∫_{ℝ^{n}} ( − 3y_{1} − y_{1}^{3} + ∑_{ℓ≠1}(1 − y_{ℓ}^{2})y_{1})(1_{B_{i}} − 1_{B_{j}})(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y).

□

Proof of (iv). Let x with x_{1} > \sqrt{n}\sqrt{1 − ρ^{2}}/ρ and consider the following cone

A := \{0\} ∪ \{y ∈ ℝ^{n}: y ≠ 0 ∧ \sqrt{n}\frac{y}{∥y∥_{2}} ∈ \frac{B_{i} − xρ}{\sqrt{1 − ρ^{2}}} \} .

By Lemma 4.1, ∫_{ℝ^{n}} 1_{A}(y) ∑_{ℓ=1}^{n}(1 − y_{ℓ}^{2})dγ_{n}(y) = 0. If d(x, ∂B_{i}) ≥ \sqrt{n}\sqrt{1 − ρ^{2}}/ρ, then A = ℝ^{n} and 1_{A}(y) ∑_{ℓ=1}^{n}(1 − y_{ℓ}^{2})1_{B_{i}^{c}}(xρ + y\sqrt{1 − ρ^{2}}) ≤ 0, so

∫_{ℝ^{n}} ( ∑_{ℓ=1}^{n}(1 − y_{ℓ}^{2}))(1_{B_{i}} − 1_{B_{j}})(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y)

≥ ∫_{ℝ^{n}} ( ∑_{ℓ=1}^{n}(1 − y_{ℓ}^{2}))1_{B_{i}}(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y) ≥ ∫_{ℝ^{n}} ( ∑_{ℓ=1}^{n}(1 − y_{ℓ}^{2}))dγ_{n}(y) = 0.

So, it remains to consider the case d(x, ∂B_{i}) < \sqrt{n}\sqrt{1 − ρ^{2}}/ρ. In this case A ≠ ℝ^{n}.

Since x_{1} > \sqrt{n}\sqrt{1 − ρ^{2}}/ρ, we have ∑_{ℓ=1}^{n}(1 − y_{ℓ}^{2})1_{B_{j}}(xρ + y\sqrt{1 − ρ^{2}}) ≤ 0. Also, we have ∑_{ℓ=1}^{n}(1 − y_{ℓ}^{2})1_{A^{c}}(y)1_{B_{i}}(xρ + y\sqrt{1 − ρ^{2}}) ≥ 0, ∑_{ℓ=1}^{n}(1 − y_{ℓ}^{2})1_{A}(y)1_{B_{i}^{c}}(xρ + y\sqrt{1 − ρ^{2}}) ≤ 0, so

∫_{ℝ^{n}} ( ∑_{ℓ=1}^{n}(1 − y_{ℓ}^{2}))(1_{B_{i}} − 1_{B_{j}})(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y)

≥ ∫_{ℝ^{n}} ( ∑_{ℓ=1}^{n}(1 − y_{ℓ}^{2}))1_{B_{i}}(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y)

≥ ∫_{ℝ^{n}} ( ∑_{ℓ=1}^{n}(1 − y_{ℓ}^{2}))1_{A}(y)1_{B_{i}}(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y)

≥ ∫_{ℝ^{n}} ( ∑_{ℓ=1}^{n}(1 − y_{ℓ}^{2}))1_{A}(y)dγ_{n}(y) = 0.

□

5. Iterative Estimates

The following estimates control the errors that appear in the proof of Theorem 1.2. Being rather technical in nature, this section could be skipped on a first reading.

Lemma 5.1. For ℓ = (ℓ_{1}, …, ℓ_{n}) ∈ ℕ^{n} and x = (x_{1}, …, x_{n}) ∈ ℝ^{n},

h_{ℓ}(x)\sqrt{ℓ!} ≤ |ℓ|^{n} 3^{|ℓ|} ∏_{i=1}^{n} max\{1, |x_{i}|^{ℓ_{i}}\}.

Proof. Let ℓ ∈ ℕ.

∑_{ℓ=0}^{∞} λ^{ℓ}h_{ℓ}(x) =^{(5)} e^{λx−λ^{2}/2} = ∑_{p=0}^{∞} \frac{x^{p}}{p!} λ^{p} ∑_{q=0}^{∞} \frac{(−1)^{q}(λ)^{2q}(1/2)^{q}}{q!} = ∑_{ℓ=0}^{∞} λ^{ℓ} ∑_{m=0}^{⌊ℓ/2⌋} \frac{x^{ℓ−2m}(−1)^{m}2^{−m}}{m!(ℓ − 2m)!} .

Here we let p + 2q = ℓ, m = q. In particular,

h_{ℓ}(x) = ∑_{m=0}^{⌊ℓ/2⌋} \frac{x^{ℓ−2m}(−1)^{m}2^{−m}}{m!(ℓ − 2m)!} .  (38)

Using Stirling’s formula, \sqrt{2π}ℓ^{ℓ+1/2}e^{−ℓ} ≤ ℓ! ≤ e ℓ^{ℓ+1/2}e^{−ℓ}. Let ℓ, m with m ∈ \{0, …, ℓ/2\}, ℓ ≥ 1. Note that lim_{x→0^{+}} x^{x} = 1 and min_{x∈[0,1]} x^{x} > 2/3. Also, m + ℓ − 2m = ℓ − m ≥ ℓ/2. For m ≠ 0, write m = ℓj, j ∈ [1/ℓ, 1/2]. Note that max{m, ℓ − 2m} ≥ ℓ/3. Then

\frac{\sqrt{ℓ!}}{m!(ℓ − 2m)!}

≤ \frac{\sqrt{e} ℓ^{(1/2)ℓ+1/4}e^{−ℓ/2}}{2πm^{m+1/2}e^{−m}(ℓ − 2m)^{ℓ−2m+1/2}e^{−(ℓ−2m)}} = \frac{\sqrt{e}}{2π} \frac{ℓ^{(1/2)ℓ+1/4}}{m^{m+1/2}(ℓ − 2m)^{ℓ−2m+1/2}} e^{ℓ/2−m}

= \frac{\sqrt{e}}{2π} \frac{ℓ^{1/4}}{\sqrt{m}\sqrt{ℓ − 2m}} \frac{ℓ^{ℓ/2}}{m^{m}(ℓ − 2m)^{ℓ−2m}} e^{ℓ/2−m} = \frac{\sqrt{e}}{2π} \frac{ℓ^{1/4}}{\sqrt{m}\sqrt{ℓ − 2m}} \frac{ℓ^{ℓ/2}}{(ℓj)^{ℓj}(ℓ(1 − 2j))^{ℓ(1−2j)}} e^{\frac{ℓ}{2} −m}

= \frac{\sqrt{e}}{2π} \frac{ℓ^{1/4}}{\sqrt{m}\sqrt{ℓ − 2m}} \frac{ℓ^{ℓ/2}e^{ℓ/2−m}}{ℓ^{ℓ(1−j)}j^{ℓj}(1 − 2j)^{ℓ(1−2j)}} = \frac{\sqrt{e}}{2π} \frac{ℓ^{1/4}}{\sqrt{m}\sqrt{ℓ − 2m}} \frac{ℓ^{ℓ/2}e^{ℓ/2−m}}{ℓ^{ℓ/2}ℓ^{\frac{ℓ}{2} (1−2j)}j^{ℓj}(1 − 2j)^{ℓ(1−2j)}}

= \frac{\sqrt{e}}{2π} \frac{ℓ^{1/4}}{\sqrt{m}\sqrt{ℓ − 2m}} \frac{1}{j^{ℓj}(1 − 2j)^{ℓ(1−2j)}} \frac{e^{\frac{ℓ}{2} (1−2j)}}{ℓ^{\frac{ℓ}{2} (1−2j)}} = \frac{\sqrt{e}}{2π} \frac{ℓ^{1/4}}{\sqrt{m}\sqrt{ℓ − 2m}} \frac{(e/ℓ)^{\frac{ℓ}{2} (1−2j)}}{j^{ℓj}(1 − 2j)^{ℓ(1−2j)}}

≤ \frac{e}{2π} \frac{ℓ^{1/4}}{\sqrt{m}\sqrt{ℓ − 2m}} \frac{1}{j^{ℓj}(1 − 2j)^{ℓ(1−2j)}} ≤ \frac{e}{2π} \frac{ℓ^{1/4}}{\sqrt{m}\sqrt{ℓ − 2m}} \frac{1}{(2/3)^{2ℓ}}

≤ \frac{e\sqrt{3}}{ℓ^{1/4}2π} \frac{1}{(2/3)^{2ℓ}} = \frac{e\sqrt{3}}{ℓ^{1/4}2π} (9/4)^{ℓ} ≤ ℓ^{−1/4}(9/4)^{ℓ}.

Here we used (e/ℓ)^{(ℓ/2)(1−2j)} ≤ \sqrt{e} for ℓ = 1, 2.

Also, for m = 0 we have \frac{\sqrt{ℓ!}}{m!(ℓ−2m)!} = 1, and for m = ℓ/2 we have

\frac{\sqrt{ℓ!}}{m!(ℓ − 2m)!} = \frac{\sqrt{ℓ!}}{(ℓ/2)!} ≤ \frac{\sqrt{e}ℓ^{ℓ/2+1/4}e^{−ℓ/2}}{\sqrt{2π}(ℓ/2)^{ℓ/2+1/2}e^{−ℓ/2}} = \sqrt{e}\frac{ℓ^{1/4}}{\sqrt{2π}ℓ^{1/2}2^{−ℓ/2}2^{−1/2}}

= \sqrt{\frac{e}{π}} ℓ^{−1/4}2^{ℓ/2} ≤ ℓ^{−1/4}2^{ℓ/2}.

So, combining the above estimates with (38),

|h_{ℓ}(x)\sqrt{ℓ!}| ≤ ∑_{m=0}^{⌊ℓ/2⌋} ℓ^{−1/4}(9/4)^{ℓ} |x|^{ℓ−2m} ≤ ∑_{m=0}^{⌊ℓ/2⌋} ℓ^{−1/4}(9/4)^{ℓ} max\{1, |x|^{ℓ−2m}\}
≤ ℓ ℓ^{−1/4}(9/4)^{ℓ} max{1, |x|^{ℓ}} ≤ ℓ 3^{ℓ} max{1, |x|^{ℓ}}.

Therefore, for ℓ = (ℓ_{1}, …, ℓ_{n}) ∈ ℕ^{n},

h_{ℓ}(x)\sqrt{ℓ!} ≤ ℓ_{1} ⋯ ℓ_{n}3^{ℓ_{1}+···+ℓ_{n}} ∏_{i=1}^{k} max\{1, |x_{i}|^{ℓ_{i}}\} ≤ |ℓ|^{n} 3^{|ℓ|} ∏_{i=1}^{n} max\{1, |x_{i}|^{ℓ_{i}}\}.

□

The following Lemma uses standard tail bounds for a Gaussian random variable. We therefore omit the proof.

Lemma 5.2. Let η > 0, t > 0, and let n ≥ 2. Then

| ∫_{[−η,η]×[t,∞]×ℝ^{n−2}} ∑_{\begin{matrix}ℓ∈ℕ^{n}: \\ 0≤|ℓ|≤3 \end{matrix}} ∏_{i=1}^{n} |y_{i}|^{ℓ_{i}} dγ_{n}(y)| ≤ 3000n^{3}η(t^{2} + 2)e^{−t^{2}/2},

| ∫_{B(0,t)^{c}} ∑_{\begin{matrix}ℓ∈ℕ^{n}: \\ 0≤|ℓ|≤3 \end{matrix}} ∏_{i=1}^{n} |y_{i}|^{ℓ_{i}} dγ_{n}(y)| ≤ 4n^{3}2^{−n/2}(Γ(n/2))^{−1}(n + 2)!(t^{n+1} + 1)e^{−t^{2}/2}

≤ 100(n + 2)!(t^{n+1} + 1)e^{−t^{2}/2}.

The following Lemma says, if ∫_{ℝ^{n}} xf(x)dγ_{n}(x) is parallel to the x_{1}-axis, then (d/dρ)T_{ρ}f(x) should be bounded by a constant multiplied by |x_{1}| + O(ρ). The precise error term (39) will be needed in Lemma 6.1 to determine the size of (d/dρ)T_{ρ}(1_{A_{i}} − 1_{A_{j}}). The error term (39) will be estimated by Lemma 5.2, and the resulting estimate will be introduced into (28).

Lemma 5.3. Let ρ ∈ (−1, 1), n ≥ 2. Suppose f ∈ L_{2}(γ_{n}) with ∫_{ℝ^{n}} y_{2}f(y)dγ_{n}(y) = 0. Let x_{1} ≥ 0 and x_{2} ≥ 0. Then

\begin{matrix}|\frac{d}{dρ}T_{ρ}f(x_{1}, x_{2}, 0, …, 0)| ≤ ( |x_{1}| + 2ρ(|x_{2}|^{2} + (n + 1)ρ |x_{2}| + |x_{1}x_{2}| + 2n)) \\ · sup_{\begin{matrix}t_{1}∈[0,x_{1}], t_{2}∈[0,x_{2}] \\ η∈[0,ρ] \end{matrix}} | ∫_{ℝ^{n}} ∑_{\begin{matrix}ℓ∈ℕ^{n}: \\ 0≤|ℓ|≤3 \end{matrix}} ∏_{i=1}^{n} |y_{i}|^{ℓ_{i}} f((t_{1}, t_{2}, 0, …, 0)η + y\sqrt{1 − η^{2}})dγ_{n}(y)|. \end{matrix}

(39)

Proof. By integrating by parts, note that

\frac{d}{dρ} ∫_{ℝ^{n}} y_{2}f(y\sqrt{1 − ρ^{2}})dγ_{n}(y)

= \frac{ρ}{1 − ρ^{2}} ∫_{ℝ^{n}} y_{2}((n + 1) − y_{2}^{2})f(y\sqrt{1 − ρ^{2}})dγ_{n}(y) − ∑_{i≠2} \frac{ρ}{1 − ρ^{2}} ∫_{ℝ^{n}} y_{i}^{2}y_{2}f(y\sqrt{1 − ρ^{2}})dγ_{n}(y).

So, using ∫_{ℝ^{n}} y_{2}f(y)dγ_{n}(y) = 0 and the Fundamental Theorem of Calculus,

\begin{matrix}∫_{ℝ^{n}} y_{2}f(y\sqrt{1 − ρ^{2}})dγ_{n}(y) \\ ≤ \frac{ρ^{2}}{1 − ρ^{2}} sup_{η∈[0,ρ]} (∫_{ℝ^{n}} y_{2}((n + 1) − y_{2}^{2})f(y\sqrt{1 − η^{2}})dγ_{n}(y) \\ − ∑_{i≠2} ∫_{ℝ^{n}} y_{i}^{2}y_{2}f(y\sqrt{1 − η^{2}})dγ_{n}(y)) . \end{matrix}  (40)

By integrating by parts again, note that

\begin{matrix}\frac{∂}{∂x_{2}} ∫_{ℝ^{n}} y_{2}f((0, x_{2}, 0, …, 0)ρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y) \\ = \frac{ρ}{\sqrt{1 − ρ^{2}}} ∫_{ℝ^{n}} f((0, x_{2}, 0, …, 0)ρ + y\sqrt{1 − ρ^{2}})(y_{2}^{2} − 1)dγ_{n}(y). \end{matrix}  (41)

Applying the Fundamental Theorem of Calculus to (41) and then using (40),

\begin{matrix}|∫_{ℝ^{n}} y_{2}f((0, x_{2}, 0, …, 0)ρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y)| \\ ≤ |x_{2}| sup_{t∈[0,x_{2}]} |\frac{ρ}{\sqrt{1 − ρ^{2}}} ∫_{ℝ^{n}} f((0, t, 0, …, 0)ρ + y\sqrt{1 − ρ^{2}})(y_{2}^{2} − 1)dγ_{n}(y)| \\ + \frac{ρ^{2}}{1 − ρ^{2}} sup_{η∈[0,ρ]} (∫_{ℝ^{n}} y_{2}((n + 1) − y_{2}^{2})f(y\sqrt{1 − η^{2}})dγ_{n}(y) \\ − ∑_{i≠2} ∫_{ℝ^{n}} y_{i}^{2}y_{2}f(y\sqrt{1 − η^{2}})dγ_{n}(y)) . \end{matrix}  (42)

By integrating by parts as before,

\begin{matrix}\frac{∂}{∂x_{1}} [x_{2} ∫_{ℝ^{n}} y_{2}f((x_{1}, x_{2}, 0, …, 0)ρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y)] \\ = x_{2} \frac{ρ}{\sqrt{1 − ρ^{2}}} ∫_{ℝ^{n}} y_{2}y_{1}f((x_{1}, x_{2}, 0, …, 0)ρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y). \end{matrix}  (43)

Combining (10), (42) and (43),

|(d/dρ)T_{ρ}f(x)| ≤ |x_{1}| |∫_{ℝ^{n}} y_{1}f((x_{1}, x_{2}, 0, …, 0)ρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y)|

+ |x_{2}|^{2} sup_{t∈[0,x_{2}]} |\frac{ρ}{\sqrt{1 − ρ^{2}}} ∫_{ℝ^{n}} f((0, t, 0, …, 0)ρ + y\sqrt{1 − ρ^{2}})(y_{2}^{2} − 1)dγ_{n}(y)|

+ \frac{ρ^{2} |x_{2}|}{1 − ρ^{2}} sup_{η∈[0,ρ]} (∫_{ℝ^{n}} y_{2}((n + 1) − y_{2}^{2})f(y\sqrt{1 − η^{2}})dγ_{n}(y)

− ∑_{i≠2} ∫_{ℝ^{n}} y_{i}^{2}y_{2}f(y\sqrt{1 − η^{2}})dγ_{n}(y))

+ |x_{1}x_{2}| sup_{t∈[0,x_{1}]} \frac{ρ}{\sqrt{1 − ρ^{2}}} |∫_{ℝ^{n}} y_{2}y_{1}f((t, x_{2}, 0, …, 0)ρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y)|

+ \frac{ρ}{\sqrt{1 − ρ^{2}}} |∫_{ℝ^{n}}(∑_{i=1}^{n}(y_{i}^{2} − 1))f((x_{1}, x_{2}, 0, …, 0)ρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y)| .

(44)

We then deduce (39) from (44). □

6. The Main Lemma

Lemma 6.1 below represents the main tool in the proof of the main theorem. As depicted in Figure 1, Lemma 6.1 says that, if an optimal partition is close to being simplicial conical, then it is actually much closer to being simplicial conical. So, this Lemma can be understood as a feedback loop, or as a contractive mapping type of argument. We first give an intuitive sketch of the proof of the Lemma. Let ρ > 0. We begin with a partition {A_{p}}_{p=1}^{3} ⊆ ℝ^{n} maximizing noise stability (3). We assume that there are disjoint sets {D_{p}}_{p=1}^{3} that resemble a simplicial conical partition, as in the left side of Figure 1. We also assume that A_{p} ⊇ D_{p} for all p = 1, 2, 3. We then find a sequence of sets {D_{p,1}}_{p=1}^{3}, {D_{p,2}}_{p=1}^{3}, … {D_{p,R}}_{p=1}^{3} such that D_{p,r} ⊆ D_{p,r+1} for all 1 ≤ p ≤ 3, for all r ≥ 1. This sequence of sets is chosen so that the following implication can be proven:

A_{p} ⊇ D_{p,r} ⟹ A_{p} ⊇ D_{p,r+1}.  (45)

In order to prove (45), we need to show: if A_{p} ⊇ D_{p,r}, then we can get sufficiently strong estimates on LT_{ρ}1_{D_{p,r+1}} such that (28) can be verified on A_{p} for each p = 1, 2, 3. For example, in Step 1 of the proof of Lemma 6.1, the estimate (54) eventually implies (58). And (58) says that A_{p} must contain more points than the initial information that we assumed in (48).

Finally, we need to choose our sets {D_{p,r}}_{p=1}^{3} appropriately so that, after finitely many implications of the form (45), we eventually get the conclusion (49). That is, the three sets {D_{p,R}}_{p=1}^{3} resemble the right side of Figure 1, and A_{p} ⊇ D_{p,R} for each p = 1, 2, 3. Thus concludes our description of the main strategy of the proof. Within the proof itself, the sets {D_{p,1}}_{p=1}^{3}, {D_{p,2}}_{p=1}^{3}, … will not be explicitly defined. However, portions of these sets will be defined at the end of every Step of the proof. In particular, examine the sets defined by the following sequence of assertions: (48), (58), (63), (68), (78), (88), (95), (101), and finally (49).

Unfortunately, there are many technical obstacles that stand in the way of bringing this strategy to fruition. The first minor issue is that we cannot control small rotations of our sets. At every step of the proof, we therefore need to redefine our simplicial sets B_{i}, B_{j} to account for these small rotations. However, the main technical issue is that it is not at all obvious how to choose the sets {D_{p,r}}_{p=1}^{3} for r = 1, 2, 3, … such that (45) can be proven for each r = 1, 2, 3, . . .. Moreover, the simplest choice of these sets, namely dilations of the sets depicted in Figure 1, do not produce satisfactory estimates.

Ultimately, the sequence of sets defined by (58), (63), (68), (78), (88), (95), (101) succeeds in proving the sequence of implications (45) for r = 1, 2, 3, . . .. Lemma 5.3 allows us to control the errors from our estimates, and we then make around seven modifications of the same error estimate within Lemma 6.1. This error estimate allows us to apply Lemma 4.2, so that we can improve our knowledge of the optimal partition {A_{i}}_{i=1}^{k} via (28).

It would be preferable to write Lemma 6.1 as seven applications of a single Lemma, however the statement of such a Lemma would perhaps be so long and convoluted that its application would become opaque. We therefore use the longer presentation below in the hope of providing greater clarity. Finally, in the statement of Lemma 6.1 below, note that the plane Π exists independently of i, j ∈ {1, …, k}.

Lemma 6.1. Fix n ≥ 2, k = 3. Let 0 < η < ρ < e^{−20(n+1)^{10^{12}n^{3}(n+2)!}}. Let {A_{i}}_{i=1}^{k} be a partition of ℝ^{n} such that (28) holds. Let Π ⊆ ℝ^{n} be a fixed 2-dimensional plane such that 0 ∈ Π. Assume that, for each pair i, j ∈ {1, 2, …, k} with i ≠ j, there exists λ′ > 0 and there exists a regular simplicial conical partition {B′_{p}}_{p=1}^{k} ⊆ ℝ^{n} such that

∫_{ℝ^{n}} y(1_{A_{i}}(y) − 1_{A_{j}}(y))dγ_{n}(y) = λ′ ∫_{ℝ^{n}} y(1_{B′_{i}}(y) − 1_{B′_{j}}(y))dγ_{n}(y),  (46)

such that

∫_{B′_{p}} xdγ_{n}(x) ∈ Π, ∀ p ∈ {i, j},  (47)

and such that

\begin{matrix}\{x ∈ B′_{i} ∪ B′_{j}: 1_{A_{i}}(x) − 1_{A_{j}}(x) ≠ 1_{B′_{i}}(x) − 1_{B′_{j}}(x)\} \\ ⊆ \{x ∈ B′_{i} ∪ B′_{j}: |d(x, (∂B′_{i}) ∪ (∂B′_{j}))| < η ∨ ∥x∥_{2} ≥ \sqrt{−2 log η} + (ρ + η)\sqrt{−2 log ρ}\}. \end{matrix}

(48)

Then, for each pair i, j ∈ {1, 2, …, k} with i ≠ j, there exists λ′′ > 0 and there exists a regular simplicial conical partition {B′′_{p}}_{p=1}^{k} ⊆ ℝ^{n} such that ∫_{ℝ^{n}} y(1_{A_{i}}(y) − 1_{A_{j}}(y))dγ_{n}(y) = λ′′ ∫_{ℝ^{n}} y(1_{B′′_{i}}(y) − 1_{B′′_{j}}(y))dγ_{n}(y), such that ∫_{B′′_{p}} xdγ_{n}(x) ∈ Π, ∀ p ∈ {i, j}, and such that

\begin{matrix}\{x ∈ B′′_{i} ∪ B′′_{j}: 1_{A_{i}}(x) − 1_{A_{j}}(x) ≠ 1_{B′′_{i}}(x) − 1_{B′′_{j}}(x)\} \\ ⊆ \{x ∈ B′′_{i} ∩ B′′_{j}: |d(x, (∂B′′_{i}) ∪ (∂B′′_{j}))| < ρη ∨ ∥x∥_{2} ≥ \sqrt{−2 log(ρη)} + 1\}. \end{matrix}  (49)

Proof. Fix i, j ∈ {1, 2, …, k} with i ≠ j. By applying a rotation to ℝ^{n}, we assume that B′_{i} ∩ B′_{j} ⊆ {x ∈ ℝ^{n}: x_{1} = 0} and B′_{i} ⊆ {x ∈ ℝ^{n}: x_{1} ≥ 0}. Assume that (48) and (46) hold. Let n′_{i} ∈ ℝ^{n} denote the interior unit normal of B′_{i} such that n′_{i} is normal to (∂B′_{i}) \ B′_{j}, and let n′_{j} ∈ ℝ^{n} denote the interior unit normal of B′_{j} such that n′_{j} is normal to (∂B′_{j})\B′_{i}. Define

A_{i}  A_{j} y^{1} y_{2} (48)  A_{i}  A_{j} (49)

Figure 1. Depiction of Lemma 6.1

B_{i}, B_{j} such that

B_{i} = B_{i, \frac{2η}{\sqrt{−2 log η}}} := B′_{i} ∪ \{x ∈ ℝ^{n}: x_{1} ≥ 0 ∧ ⟨n′_{i}, x/ ∥x∥_{2}⟩ ≥ −2η/\sqrt{−2 log η}\},
B_{j} = B_{j, \frac{2η}{\sqrt{−2 log η}}} := B′_{j} ∪ \{x ∈ ℝ^{n}: x_{1} ≤ 0 ∧ ⟨n′_{j}, x/ ∥x∥_{2}⟩ ≥ −2η/\sqrt{−2 log η}\}.

(50)

Let x = (x_{1}, …, x_{n}) ∈ B_{i} ∪ B_{j}. If x_{1} < \sqrt{n}\sqrt{1 − ρ^{2}}/ρ, then

γ_{n} (δ_{\frac{(B_{i}∩B_{j})−xρ}{\sqrt{1−ρ^{2}}}} ) ≥ \frac{e^{−n/2}}{\sqrt{2π}} ∫_{√\overline{n}}^{∞} e^{−t^{2}/2}dt/\sqrt{2π} ≥ \frac{e^{−n/2}}{2π} \frac{1}{2\sqrt{n}}e^{−n/2} ≥ \frac{1}{100\sqrt{n}}e^{−n}.

So, using Lemma 4.2, (9), and ρ < 10^{−5}n^{−3/2}e^{−n}, if x ∈ B_{i} ∪ B_{j} then

ρ^{−1}sign(x_{1}) · LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x) ≥ \begin{cases}\frac{1}{9} |x_{1}| e^{−x_{1}^{2}ρ^{2}/(2(1−ρ^{2}))} & , |x_{1}| ≤ 1 ∨ x_{2} ≥ 0 \\ \frac{1}{9} \frac{|x_{1}|}{ρ|x_{2}|}e^{−∥x∥_{2}^{2}ρ^{2}/(2(1−ρ^{2}))} & , ρx_{2} ≤ −1/\sqrt{3}. \end{cases}  (51)

Let σ: ℝ^{n} → ℝ^{n} be a rotation such that the x_{1}-axis is fixed. For any such rotation, let

g(x) = g_{σ}(x) := 1_{A_{i}}(σx) − 1_{A_{j}}(σx) − (1_{B_{i}}(σx) − 1_{B_{j}}(σx)).  (52)

By (46), and since B_{i} ∪ B_{j} is symmetric with respect to reflection across B_{i} ∩ B_{j} ⊆ {x ∈ ℝ^{n}: x_{1} = 0}, ∃ λ > 0 such that ∫_{ℝ^{n}} y(1_{A_{i}}(y)−1_{A_{j}}(y))dγ_{n}(y) = λ ∫_{ℝ^{n}} y(1_{B_{i}}(y)−1_{B_{j}}(y))dγ_{n}(y). So ∫_{ℝ^{n}} y_{2}g(y)dγ_{n}(y) = 0, for all such rotations σ. For all x ∈ ℝ^{n}, and for all rotations σ: ℝ^{n} → ℝ^{n} fixing the x_{1}-axis,

|LT_{ρ}(1_{A_{i}} − 1_{A_{j}})(σx) − LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(σx)| ≤ |LT_{ρ}g(x)| .  (53)

Step 1. An estimate for large x.

Let σ: ℝ^{n} → ℝ^{n} be any rotation fixing the x_{1}-axis. By (52), |g| ≤ 2. Applying (48) and (50) and the inclusion-exclusion principle, g = 0 on the set

{y ∈ ℝ^{n}: d(σy − ρx, (∂B′_{i}) ∪ (∂B′_{j})) > η + 3η
∧ ∥σy − ρx∥_{2} ≤ \sqrt{−2 log η} + (ρ + η)\sqrt{−2 log ρ}\}.

Let x ∈ ℝ^{n} with ∥x∥_{2}^{2} ≤ −4 log(ηρ). Since 0 < η < ρ, we have ρ ∥x∥_{2} ≤ −4ρ log(ηρ) ≤ −8ρ log η. By (48), (47) and the inclusion-exclusion principle, g ≠ 0 only on the following sets: \{y ∈ ℝ^{n}: |d(σy − ρx, (∂B′_{i}) ∪ (∂B′_{j}))| ≤ 4η/\sqrt{1 − ρ^{2}}\} and \{y ∈ ℝ^{n}: ∥σy − ρx∥_{2} ≥ \sqrt{−2 log η}/\sqrt{1 − ρ^{2}}\}. Then Lemma 5.2 says

sup_{t_{1}∈[min(x_{1},0),max(x_{1},0)] t_{2}∈[min(x_{2},0),max(x_{2},0)] α∈[0,ρ]} | ∫_{ℝ^{n}} ∑_{\begin{matrix}ℓ∈ℕ^{n}: \\ 0≤|ℓ|≤3 \end{matrix}} ∏_{i=1}^{n} |y_{i}|^{ℓ_{i}} g((t_{1}, t_{2}, 0, …, 0)α + y\sqrt{1 − α^{2}})dγ_{n}(y)|

≤ 500000n^{3}4η + 200(n + 2)!((−2(1 − 2ρ) log η)^{(n+1)/2} + 1)η^{1−2ρ}.

Using Lemma 5.3 and (53),

∥x∥_{2}^{2} ≤ −4 log(ρη) ∧ |x_{1}| ≥ (ρη)^{1/3}
⟹ ρ^{−1} |LT_{ρ}(1_{A_{i}} − 1_{A_{j}})(x_{1}, x_{2}, 0, …, 0) − LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x_{1}, x_{2}, 0, …, 0)|
≤ [|x_{1}| + 2ρ(|x_{2}|^{2} + (n + 1)ρ |x_{2}| + |x_{1}x_{2}| + 2n)]
· [500000n^{3}4η + 200(n + 2)!((−2(1 − 2ρ) log η)^{(n+1)/2} + 1)η^{1−2ρ}]
< 10^{7}(n + 2)!(−2 log η)^{(n+5)/2}η^{1−2ρ}.

(54)

Also, by (51), and using that 0 < η < ρ < 10^{−5}n^{−3/2}e^{−n},

\begin{matrix}∥x∥_{2}^{2} ≤ −4 log(ρη) ∧ x ∈ B_{i} ∪ B_{j} \\ ⟹ ρ^{−1}sign(x_{1}) · (LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x)) > \begin{cases}\frac{1}{9} |x_{1}| (ρη)^{2ρ^{2}/(1−ρ^{2})} & , |x_{1}| ≤ 1 ∨ x_{2} ≥ 0 \\ \frac{1}{9} \frac{|x_{1}|}{ρ|x_{2}|}(ρη)^{2ρ^{2}/(1−ρ^{2})} & , ρx_{2} ≤ −1/\sqrt{3} \end{cases} . \end{matrix}

(55)

Combining (54) and (55), using (52) and 0 < η < ρ < e^{−20(n+1)^{10^{12}(n+2)!}},

|x_{1}| ≥ (ρη)^{1/3} ∧ ∥x∥_{2}^{2} ≤ −4 log(ρη) ∧ x ∈ B_{i} ∪ B_{j}

⟹ ρ^{−1} |LT_{ρ}(1_{A_{i}} − 1_{A_{j}})(x) − LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x)| ≤ η^{4/5}

∧ ρ^{−1}sign(x_{1}) · LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x) ≥ (ρη)^{2ρ^{2}/(1−ρ^{2})}(ρη)^{1/3} min (1, \frac{1}{ρ\sqrt{−4 log(ηρ)}}) .

(56)

By (56),

|x_{1}| ≥ (ρη)^{1/3} ∧ ∥x∥_{2}^{2} ≤ −4 log(ρη) ∧ x ∈ B_{i} ∪ B_{j} ⟹ ρ^{−1}sign(x_{1}) · LT_{ρ}(1_{A_{i}} − 1_{A_{j}})(x) > 0.

(57)

Finally, applying (57) to Lemma 3.1 for all i′, j′ ∈ {1, …, k}, i′ ≠ j′, and using (50) together with the inclusion-exclusion principle,

|x_{1}| ≥ (ρη)^{1/3} ∧ ∥x∥_{2}^{2} ≤ −4 log(ρη) ∧ x ∈ B′_{i} ∪ B′_{j} ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0. (58)

Step 2. An estimate for small x.

Let σ: ℝ^{n} → ℝ^{n} be any rotation fixing the x_{1}-axis. For x = (x_{1}, …, x_{n}) ∈ ℝ^{n} with ∥x∥_{2}^{2} ≤ −2 log ρ, we have ρ ∥x∥_{2} ≤ ρ\sqrt{−2 log ρ}. Suppose also that |x_{1}| ≤ η and x ∈ B_{i} ∪ B_{j}. By (50), (48), (58), (47) and the inclusion-exclusion principle, g ≠ 0 only on the following sets:

\{y ∈ ℝ^{n}: |d(σy − ρx, (B_{i} ∩ B_{j}) ∪ [(B_{i} ∪ B_{j}) \ (B′_{i} ∪ B′_{j})])| ≤ η/\sqrt{1 − ρ^{2}}\},
{y ∈ ℝ^{n}: |d(σy − ρx, (B_{i} ∩ B_{j}) ∪ [(B_{i} ∪ B_{j}) \ (B′_{i} ∪ B′_{j})])| ≤ (ρη)^{1/4}
∧ ∥σy − ρx∥_{2} ≥ \sqrt{−2 log η}\},
\{y ∈ ℝ^{n}: ∥σy − ρx∥_{2} ≥ (1 + 1/10)\sqrt{−3 log(ηρ)}/\sqrt{1 − ρ^{2}}\}.

We then apply Lemma 5.2 to get

sup_{t_{1}∈[min(x_{1},0),max(x_{1},0)] t_{2}∈[min(x_{2},0),max(x_{2},0)] α∈[0,ρ]} | ∫_{ℝ^{n}} ∑_{\begin{matrix}ℓ∈ℕ^{n}: \\ 0≤|ℓ|≤3 \end{matrix}} ∏_{i=1}^{n} |y_{i}|^{ℓ_{i}} g((t_{1}, t_{2}, 0, …, 0)α + y\sqrt{1 − α^{2}})dγ_{n}(y)|

≤ 500000n^{3}η + 500000n^{3}(ρη)^{1/4}(−2(1 − ρ)^{2} log η + 1)η^{(1−ρ)^{2}}
+ 200(n + 2)!((−3 log(ρη))^{(n+1)/2} + 1)(ρη)^{3/2} + 1600(n + 2)!2η/\sqrt{−2 log η}.

So, using Lemma 5.3, (53) and 0 < η < ρ < e^{−20(n+1)^{10^{12}n^{3}(n+2)!}},

ρ^{3/4}η ≤ |x_{1}| ≤ η ∧ ∥x∥_{2}^{2} ≤ −2 log ρ ∧ x ∈ B_{i} ∪ B_{j}

⟹ ρ^{−1} |LT_{ρ}(1_{A_{i}} − 1_{A_{j}})(x_{1}, x_{2}, 0, …, 0) − LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x_{1}, x_{2}, 0, …, 0)|

≤ [|x_{1}| + 2ρ(|x_{2}|^{2} + (n + 1)ρ |x_{2}| + |x_{1}x_{2}| + 2n)]

· [500000n^{3}3η + 500000n^{3}(ρη)^{1/4}(−2(1 − ρ)^{2} log η + 1)η^{(1−ρ)^{2}}

+200(n + 2)!((−3 log(ρη))^{(n+1)/2} + 1)(ρη)^{3/2} + 1600(n + 2)!2η/\sqrt{−2 log η}]

< \frac{1}{10}ηρ^{3/4}.

(59)

Also, by (51),

\begin{matrix}ηρ^{3/4} ≤ |x_{1}| ≤ η ∧ ∥x∥_{2}^{2} ≤ −2 log ρ ∧ x ∈ B_{i} ∪ B_{j} \\ ⟹ ρ^{−1}sign(x_{1}) · LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x) > \frac{1}{10} |x_{1}| . \end{matrix}  (60)

Combining (59) and (60), and using (52),

ηρ^{3/4} ≤ |x_{1}| ≤ η ∧ ∥x∥_{2}^{2} ≤ −2 log ρ ∧ x ∈ B_{i} ∪ B_{j} ⟹ ρ^{−1}sign(x_{1}) · LT_{ρ}(1_{A_{i}} − 1_{A_{j}})(x) > 0.

(61)

Similarly, by (59) and (52), we have the following estimate.

η ≤ |x_{1}| ≤ (ρη)^{1/3} ∧ ∥x∥_{2}^{2} ≤ 1 ∧ x ∈ B_{i} ∪ B_{j} ⟹ ρ^{−1}sign(x_{1}) · LT_{ρ}(1_{A_{i}} − 1_{A_{j}})(x) > 0. (62)

Finally, applying (61) to Lemma 3.1 for all i′, j′ ∈ {1, …, k}, and using (50) together with the inclusion-exclusion principle, (57) and (62),

ηρ^{3/4} ≤ |x_{1}| ≤ η ∧ ∥x∥_{2}^{2} ≤ −2 log ρ ∧ x ∈ B′_{i} ∪ B′_{j} ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0. (63)

Step 3. An estimate for intermediate values of x.

In summary, (63) and (58) improve our initial assumption (48). We now repeat the above procedure with the improved assumptions. Before continuing, we need to redefine B_{i}, B_{j}. Via (50), let

B_{i} := B_{i,min( \frac{2ρ^{3/4}η}{\sqrt{−2 log ρ}} , \frac{2η}{\sqrt{−2 log η}} )}, B_{j} := B_{j,min( \frac{2ρ^{3/4}η}{\sqrt{−2 log ρ}} , \frac{2η}{\sqrt{−2 log η}} )}  (64)

\sqrt{−2 log ρ}  ηρ^{3/4}  ^{\sqrt{−2 log η}} ^{\sqrt{−4 log(ρη)}} η (ρη)^{1/4} y_{1} y_{2} (63)  (48)  (58)

Figure 2. Integration regions where g ≠ 0, near B′_{i} ∩ B′_{j} for (65).

Let x with ∥x∥_{2}^{2} ≤ −4 log ρ, ηρ ≤ |x_{1}| ≤ η. Let B := (B_{i} ∩ B_{j}) ∪ [(B_{i} ∪ B_{j}) \ (B′_{i} ∪ B′_{j})]. Suppose x ∈ B_{i} ∪ B_{j} also. By (63), (48), (58), (47) and the inclusion-exclusion principle, g ≠ 0 only on the following sets

\{y ∈ ℝ^{n}: |d(σy − ρx, B)| ≤ ηρ^{3/4}/\sqrt{1 − ρ^{2}}\},
\{y ∈ ℝ^{n}: |d(σy − ρx, B)| ≤ η/\sqrt{1 − ρ^{2}}, ∥σy − ρx∥_{2} > \sqrt{−2 log ρ}/\sqrt{1 − ρ^{2}}\},
\{y ∈ ℝ^{n}: |d(σy − ρx, B)| ≤ (ρη)^{1/4}/\sqrt{1 − ρ^{2}}, ∥σy − ρx∥_{2} ≥ \sqrt{−2 log η}/\sqrt{1 − ρ^{2}}\},
\{y ∈ ℝ^{n}: ∥σy − ρx∥_{2} > (1 + 1/10)\sqrt{−3 log(ρη)}/\sqrt{1 − ρ^{2}}\}.

We then apply Lemma 5.2 to get

sup_{t_{1}∈[min(x_{1},0),max(x_{1},0)] t_{2}∈[min(x_{2},0),max(x_{2},0)] α∈[0,ρ]} | ∫_{ℝ^{n}} ∑_{\begin{matrix}ℓ∈ℕ^{n}: \\ 0≤|ℓ|≤3 \end{matrix}} ∏_{i=1}^{n} |y_{i}|^{ℓ_{i}} g((t_{1}, t_{2}, 0, …, 0)α + y\sqrt{1 − α^{2}})dγ_{n}(y)|

≤ ηρ^{3/4}500000n^{3} + 500000n^{3}η(−2(1 − \sqrt{2}ρ)^{2} log ρ + 1)ρ^{(1−\sqrt{2}ρ)^{2}}
+ 500000n^{3}(ηρ)^{1/4}(−2(1 − \sqrt{2}ρ)^{2} log η + 1)η^{(1−\sqrt{2}ρ)^{2}}
+ 200(n + 2)!((−3 log(ηρ))^{(n+1)/2} + 1)(ρη)^{3/2}
+ 1600(n + 2)! min(2ρ^{3/4}η/\sqrt{−2 log ρ}, 2η/\sqrt{−2 log η}).

(65)

Applying (65) to Lemma 5.3, using (52) and η < ρ < e^{−20(n+1)^{10^{12}n^{3}(n+2)!}},

\begin{matrix}∥x∥_{2}^{2} ≤ −4 log(ρ) ∧ ηρ ≤ |x_{1}| ≤ η ∧ x ∈ B_{i} ∪ B_{j} \\ ⟹ ρ^{−1} |LT_{ρ}(1_{A_{i}} − 1_{A_{j}})(x) − LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x)| < \frac{1}{10}ρη. \end{matrix}  (66)

Also, by (51),

ρη ≤ |x_{1}| ≤ η ∧ ∥x∥_{2}^{2} ≤ −4 log ρ ∧ x ∈ B_{i} ∪ B_{j} ⟹ ρ^{−1}sign(x_{1}) · LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x) > \frac{1}{10}ρη.

(67)

So, combining (66), (67) for all i′, j′ ∈ {1, …, k}, i′ ≠ j′, Lemma 3.1, (64), and by applying the inclusion-exclusion principle, (57) and (62),

ρη ≤ |x_{1}| ≤ η ∧ ∥x∥_{2}^{2} ≤ −4 log ρ ∧ x ∈ B′_{i} ∪ B′_{j} ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0. (68)

Step 4. Iterating the estimate for intermediate values of x.

The estimate (68) now has a cascading effect on the estimates below. From (68),

ρ^{.9}η ≤ |x_{1}| ≤ η ∧ ∥x∥_{2}^{2} ≤ −4 log ρ ∧ x ∈ B′_{i} ∪ B′_{j} ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0.

This estimate can be iterated on itself. Let K ∈ ℕ, K ≥ 1, and let M ∈ ℕ with 0 ≤ M ≤ \sqrt{K}. Suppose ρ^{.9K} > η^{1/5}. We prove by induction on K and M that

\begin{matrix}2^{M^{2}}ηρ^{.9K} ≤ |x_{1}| ≤ η ∧ ∥x∥_{2}^{2} ≤ −2^{M+2} log ρ ∧ x ∈ B′_{i} ∪ B′_{j} \\ ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0. \end{matrix}  (69)

We already verified the case M = 0, K = 1. We assume that, for 0 ≤ m < M,

\begin{matrix}2^{m^{2}}ηρ^{.9K} ≤ |x_{1}| ≤ η ∧ ∥x∥_{2}^{2} ≤ −2^{m+2} log ρ ∧ x ∈ B′_{i} ∪ B′_{j} \\ ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0. \end{matrix}  (70)

Assume also that, for M ≤ m ≤ \sqrt{K − 1} and K ≥ 1,

\begin{matrix}2^{m^{2}}ηρ^{.9(K−1)} ≤ |x_{1}| ≤ η ∧ ∥x∥_{2}^{2} ≤ −2^{m+2} log ρ ∧ x ∈ B′_{i} ∪ B′_{j} \\ ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0. \end{matrix}  (71)

We will conclude that (70) holds for m = M, i.e.

\begin{matrix}2^{M^{2}}ηρ^{.9K} ≤ |x_{1}| ≤ η ∧ ∥x∥_{2}^{2} ≤ −2^{M+2} log ρ ∧ x ∈ B′_{i} ∪ B′_{j} \\ ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0. \end{matrix}  (72)

We repeat the calculations (64) through (68). Redefine B_{i}, B_{j} so that

B_{i} := B_{i,min( \frac{2ηρ^{.9K}}{\sqrt{−4 log ρ}} , \frac{2η}{\sqrt{−2 log η}} )} , B_{j} := B_{j,min( \frac{2ηρ^{.9K}}{\sqrt{−4 log ρ}} , \frac{2η}{\sqrt{−2 log η}} )}.  (73)

If M > 0, we use (70) for m = M − 1. For any M ≥ 0, we use (71) for M ≤ m ≤ \sqrt{K}. Let x, M with ∥x∥_{2}^{2} ≤ −2^{M+2} log ρ ≤ −2^{⌊\sqrt{K}⌋+2} log ρ ≤ −4 log η, 2^{M^{2}}ηρ^{.9K} ≤ |x_{1}| ≤ η, x ∈ B_{i} ∪ B_{j}. Let B := (B_{i} ∩ B_{j}) ∪ [(B_{i} ∪ B_{j}) \ (B′_{i} ∪ B′_{j})]. Combining (70), (71), (48), (58),

(47) and the inclusion-exclusion principle, g ≠ 0 only on the following sets

\{y ∈ ℝ^{n}: |d(σy − ρx, B)| ≤ min(M, 1) · 2^{(M−1)^{2}}ηρ^{.9K}/\sqrt{1 − ρ^{2}}\},

∪_{M≤m≤⌊\sqrt{K−1}⌋} \{y ∈ ℝ^{n}: |d(σy − ρx, B)| ≤ 2^{m^{2}}ηρ^{.9(K−1)}/\sqrt{1 − ρ^{2}},

∥σy − ρx∥_{2} > min(m, 1) · \sqrt{−2^{m+1} log ρ}/\sqrt{1 − ρ^{2}}\},

\{y ∈ ℝ^{n}: |d(σy − ρx, B)| ≤ η, ∥σy − ρx∥_{2} > \sqrt{−2^{⌊\sqrt{K−1}⌋+2} log ρ}/\sqrt{1 − ρ^{2}}\},

\{y ∈ ℝ^{n}: |d(σy − ρx, B)| ≤ (ρη)^{1/4}/\sqrt{1 − ρ^{2}}, ∥σy − ρx∥_{2} ≥ \sqrt{−2 log η}/\sqrt{1 − ρ^{2}}\},

\{y ∈ ℝ^{n}: ∥σy − ρx∥_{2} > (1 + 1/10)\sqrt{−3 log(ρη)}/\sqrt{1 − ρ^{2}}\}.

We then apply Lemma 5.2 to get

sup_{t_{1}∈[min(x_{1},0),max(x_{1},0)] t_{2}∈[min(x_{2},0),max(x_{2},0)] α∈[0,ρ]} | ∫_{ℝ^{n}} ∑_{\begin{matrix}ℓ∈ℕ^{n}: \\ 0≤|ℓ|≤3 \end{matrix}} ∏_{i=1}^{n} |y_{i}|^{ℓ_{i}} g((t_{1}, t_{2}, 0, …, 0)α + y\sqrt{1 − α^{2}})dγ_{n}(y)|

≤ min(M, 1) · 2^{(M−1)^{2}}ηρ^{.9K}500000n^{3}

+ η(−(1 − ρ)^{2}2^{⌊\sqrt{K−1}⌋+2} log ρ + 1)ρ^{(1−ρ)^{2}2^{⌊\sqrt{K−1}⌋+1}}500000n^{3}

+ 500000n^{3} ∑_{m=M}^{⌊\sqrt{K−1}⌋} ηρ^{.9(K−1)}(−(1 − ρ)^{2}2^{m+1} log ρ + 1)2^{m^{2}}ρ^{(1−ρ)^{2}2^{m}·min(m,1)}

+ 500000n^{3}(ηρ)^{1/4}(−2(1 − \sqrt{2}ρ)^{2} log η + 1)η^{(1−\sqrt{2}ρ)^{2}}

+ 200(n + 2)!((−3 log(ηρ))^{(n+1)/2} + 1)(ρη)^{3/2}

+ 1600(n + 2)! min(2ηρ^{.9K}/\sqrt{−4 log ρ}, 2η/\sqrt{−2 log η}).

(74)

Applying (74) to Lemma 5.3, using (52), η < ρ < e^{−20(n+1)^{10^{12}n^{3}(n+2)!}}, and ρ^{.9K} > η^{1/5},

\begin{matrix}∥x∥_{2}^{2} ≤ −2^{M+2} log(ρ) ∧ 2^{M^{2}}ηρ^{.9K} ≤ |x_{1}| ≤ η ∧ x ∈ B_{i} ∪ B_{j} \\ ⟹ ρ^{−1} |LT_{ρ}(1_{A_{i}} − 1_{A_{j}})(x) − LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x)| < \frac{1}{10}2^{M^{2}}ηρ^{.9K}. \end{matrix}  (75)

Also, by (51),

\begin{matrix}2^{M^{2}}ηρ^{.9K} ≤ |x_{1}| ≤ η ∧ ∥x∥_{2}^{2} ≤ −2^{M+2} log ρ ∧ x ∈ B_{i} ∪ B_{j} \\ ⟹ ρ^{−1}sign(x_{1}) · LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x) > \frac{1}{10}2^{M^{2}}ηρ^{.9K}. \end{matrix}  (76)

So, combining (75), (76) for all i′, j′ ∈ {1, …, k}, i′ ≠ j′, Lemma 3.1, (73), and by applying the inclusion-exclusion principle, (57) and (62),

2^{M^{2}}ηρ^{.9K} ≤ |x_{1}| ≤ η ∧ ∥x∥_{2}^{2} ≤ −2^{M+2} log ρ ∧ x ∈ B′_{i}∪B′_{j} ⟹ sign(x_{1})·(1_{A_{i}}(x)−1_{A_{j}}(x)) > 0.

(77)

Thus, the inductive step is completed.

Let K ∈ ℕ with −2 log η ≤ −2^{⌊\sqrt{K}⌋+2} log ρ ≤ −4 log η. Then (77) and (48) say that

2^{K}ηρ^{.9K} ≤ |x_{1}| ≤ 1 ∧ ∥x∥_{2}^{2} ≤ −2 log η ∧ x ∈ B′_{i}∪B′_{j} ⟹ sign(x_{1})·(1_{A_{i}}(x)−1_{A_{j}}(x)) > 0. (78)

Step 5. Another iterative estimate, now for larger values of x.

We perform another induction, though this time we hold K fixed and use the additional ingredient (78). Let M, R ∈ ℕ with 0 ≤ M ≤ \sqrt{K}, R ≥ 0 such that ρ^{.9(K+R)} > η^{1/5}. We will induct on M and R. We assume that, for 0 ≤ m < M,

\begin{matrix}2^{m^{2}}ηρ^{.9(K+R)} ≤ |x_{1}| ≤ η ∧ ∥x∥_{2}^{2} ≤ −2^{m+2} log ρ ∧ x ∈ B′_{i} ∪ B′_{j} \\ ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0. \end{matrix}  (79)

We know that the case R = 0, 0 ≤ M ≤ \sqrt{K} of (79) holds by (72). We therefore assume that R ≥ 1. Assume also that, for M ≤ m ≤ \sqrt{K},

\begin{matrix}2^{m^{2}}ηρ^{.9(K+R−1)} ≤ |x_{1}| ≤ η ∧ ∥x∥_{2}^{2} ≤ −2^{m+2} log ρ ∧ x ∈ B′_{i} ∪ B′_{j} \\ ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0. \end{matrix}  (80)

We will conclude that (79) holds for m = M, i.e.

\begin{matrix}2^{M^{2}}ηρ^{.9(K+R)} ≤ |x_{1}| ≤ η ∧ ∥x∥_{2}^{2} ≤ −2^{M+2} log ρ ∧ x ∈ B′_{i} ∪ B′_{j} \\ ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0. \end{matrix}  (81)

Redefine B_{i}, B_{j} so that

B_{i} := B_{i,min( \frac{2ηρ^{.9(K+R)}}{\sqrt{−4 log ρ}} , \frac{2η}{\sqrt{−2 log η}} )} , B_{j} := B_{j,min( \frac{2ηρ^{.9(K+R)}}{\sqrt{−4 log ρ}} , \frac{2η}{\sqrt{−2 log η}} )}.  (82)

If M > 0, we use (79) for m = M −1. For any M ≥ 0, we also use (80) for M ≤ m ≤ \sqrt{K}. Let x, M with ∥x∥_{2}^{2} ≤ −2^{M+2} log ρ ≤ −2^{⌊\sqrt{K}⌋+2} log ρ ≤ −4 log η, 2^{M^{2}}ηρ^{.9K} ≤ |x_{1}| ≤ η, x ∈ B_{i} ∪ B_{j}. Let B := (B_{i} ∩ B_{j}) ∪ [(B_{i} ∪ B_{j}) \ (B′_{i} ∪ B′_{j})]. Combining (79), (80), (48), (58), (47), and the fact that −2 log η ≤ −2^{⌊\sqrt{K}⌋+2} log ρ ≤ −4 log η, we conclude that g ≠ 0 only on the following sets:

\{y ∈ ℝ^{n}: |d(σy − ρx, B)| ≤ min(M, 1) · 2^{(M−1)^{2}}ηρ^{.9(K+R)}/\sqrt{1 − ρ^{2}}\},
∪_{M≤m≤⌊\sqrt{K}⌋} \{y ∈ ℝ^{n}: |d(σy − ρx, B)| ≤ 2^{m^{2}}ηρ^{.9(K+R−1)}/\sqrt{1 − ρ^{2}},
∥σy − ρx∥_{2} > min(m, 1) · \sqrt{−2^{m+1} log ρ}/\sqrt{1 − ρ^{2}}\},
\{y ∈ ℝ^{n}: |d(σy − ρx, B)| ≤ (ρη)^{1/4}/\sqrt{1 − ρ^{2}}, ∥σy − ρx∥_{2} ≥ \sqrt{−2 log η}/\sqrt{1 − ρ^{2}}\},
\{y ∈ ℝ^{n}: ∥σy − ρx∥_{2} > (1 + 1/10)\sqrt{−3 log(ρη)}/\sqrt{1 − ρ^{2}}\}.

We then apply Lemma 5.2 to get

sup_{t_{1}∈[min(x_{1},0),max(x_{1},0)] t_{2}∈[min(x_{2},0),max(x_{2},0)] α∈[0,ρ]} | ∫_{ℝ^{n}} ∑_{\begin{matrix}ℓ∈ℕ^{n}: \\ 0≤|ℓ|≤3 \end{matrix}} ∏_{i=1}^{n} |y_{i}|^{ℓ_{i}} g((t_{1}, t_{2}, 0, …, 0)α + y\sqrt{1 − α^{2}})dγ_{n}(y)|

≤ min(M, 1) · 2^{(M−1)^{2}}ηρ^{.9(K+R)}500000n^{3}

+ 500000n^{3} ∑_{m=M}^{⌊\sqrt{K}⌋} ηρ^{.9(K+R−1)}(−(1 − ρ)^{2}2^{m+1} log ρ + 1)2^{m^{2}}ρ^{(1−ρ)^{2}2^{m}}

+ 500000n^{3}(ηρ)^{1/4}(−2(1 − \sqrt{2}ρ)^{2} log η + 1)η^{(1−\sqrt{2}ρ)^{2}}

+ 200(n + 2)!((−3 log(ηρ))^{(n+1)/2} + 1)(ρη)^{3/2}

+ 1600(n + 2)! min(2ηρ^{.9(K+R)}/\sqrt{−4 log ρ}, 2η/\sqrt{−2 log η}).

(83)

Applying (83) to Lemma 5.3, using (52), η < ρ < e^{−20(n+1)^{10^{12}n^{3}(n+2)!}}, and ρ^{.9(K+R)} > η^{1/5},

\begin{matrix}∥x∥_{2}^{2} ≤ −2^{M+2} log(ρ) ∧ 2^{M^{2}}ηρ^{.9(K+R)} ≤ |x_{1}| ≤ η ∧ x ∈ B_{i} ∪ B_{j} \\ ⟹ ρ^{−1} |LT_{ρ}(1_{A_{i}} − 1_{A_{j}})(x) − LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x)| < \frac{1}{10}2^{M^{2}}ηρ^{.9(K+R)}. \end{matrix}  (84)

Also, by (51),

\begin{matrix}2^{M^{2}}ηρ^{.9(K+R)} ≤ |x_{1}| ≤ η ∧ ∥x∥_{2}^{2} ≤ −2^{M+2} log ρ ∧ x ∈ B_{i} ∪ B_{j} \\ ⟹ ρ^{−1}sign(x_{1}) · LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x) > \frac{1}{10}2^{M^{2}}ηρ^{.9(K+R)}. \end{matrix}  (85)

So, combining (84), (85) for all i′, j′ ∈ {1, …, k}, i′ ≠ j′, Lemma 3.1, (82), and by applying the inclusion-exclusion principle, (57) and (62),

\begin{matrix}2^{M^{2}}ηρ^{.9(K+R)} ≤ |x_{1}| ≤ η ∧ ∥x∥_{2}^{2} ≤ −2^{M+2} log ρ ∧ x ∈ B′_{i} ∪ B′_{j} \\ ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0. \end{matrix}  (86)

Thus, the inductive step is completed. Let M = ⌊\sqrt{K}⌋. Let R ∈ ℕ such that η^{1/5} ≤ ρ^{.9(K+R)} ≤ η^{1/5}ρ^{−.9}. If no such R exists, then ρ^{.9K} < η^{1/5}, so ρ^{.45K} < η^{1/10}, and (88) below holds by combining (78) and (48). Otherwise, R ≥ 0, so (86) and (48) say that

2^{K}η^{6/5}ρ^{−.9} ≤ |x_{1}| ≤ 1 ∧ ∥x∥_{2}^{2} ≤ −2 log η ∧ x ∈ B′_{i} ∪ B′_{j} ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0.

(87)

Since η^{1/5} ≤ ρ^{.9(K+R)} ≤ η^{1/5}ρ^{−.9}, note that η^{1/10} ≤ ρ^{.45(K+R)} ≤ η^{1/10}ρ^{−.45}, so for R ≥ 2, we have 2^{K}η^{6/5}ρ^{−.9} ≤ 2^{K}ρ^{.45K}ρ^{.45R}η^{11/10}ρ^{−.9} < η^{11/10}. If R = 1, and if K ≥ 2, note that 2^{K}η^{6/5}ρ^{−.9} ≤ 2^{K}ρ^{.2K}ρ^{.25K}ρ^{.45}η^{11/10}ρ^{−.9} < η^{11/10}. If R = 0, K ≥ 3 then 2^{K}η^{6/5}ρ^{−.9} ≤ 2^{K}ρ^{.1K}ρ^{.35K}η^{11/10}ρ^{−.9} < η^{11/10}. If 1 ≤ R + K ≤ 3, then (1/5) log η ≤ 3 log ρ and 2 log ρ ≤ (1/5) log η, so (74) directly implies (88). More specifically, by (74), Lemma 5.3,(57) and (62), sign(x_{1}) · (1_{A_{i}} − 1_{A_{j}})(x) > 0 for x ∈ B′_{i} ∪ B′_{j} with ∥x∥_{2}^{2} ≤ −2 log η and ηρ^{.9K}ρ^{.9} ≤ |x_{1}| ≤ η. Now, ρ^{.45(K+R)} ≤ η^{1/10}ρ^{−.45}, so ηρ^{.9K}ρ^{.9} = ηρ^{.45K}ρ^{.45K}ρ^{.9} ≤ ηρ^{.45K}ρ^{.45(K+R)} ≤ η^{11/10}.

In the latter case, (88) follows, and in the former cases, (87) implies

η^{11/10} ≤ |x_{1}| ≤ 1 ∧ ∥x∥_{2}^{2} ≤ −2 log η ∧ x ∈ B′_{i} ∪ B′_{j} ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0. (88)

In all cases, (88) holds. We can finally use (88) to conclude the proof. Step 6. Using Step 5 to get an estimate for large values of x.

Redefine B_{i}, B_{j} so that

B_{i} := B_{i,2η^{11/10}/\sqrt{−2 log η}} , B_{j} := B_{j,2η^{11/10}/\sqrt{−2 log η}}.  (89)

Let σ: ℝ^{n} → ℝ^{n} be any rotation fixing the x_{1}-axis. Let x with ∥x∥_{2}^{2} ≤ −4 log(ηρ) ≤ −8 log η and η^{21/20}ρ^{1/2} ≤ |x_{1}| ≤ (ηρ)^{1/4}. Let B := (B_{i} ∩B_{j})∪[(B_{i} ∪B_{j})\(B′_{i} ∪B′_{j})]. Suppose x ∈ B_{i} ∪ B_{j} also. Combining (88), (58), and (47), g ≠ 0 only on the following sets:

\{y ∈ ℝ^{n}: |d(σy − ρx, B)| ≤ η^{11/10}/\sqrt{1 − ρ^{2}}\},

\{y ∈ ℝ^{n}: |d(σy − ρx, B)| ≤ (ρη)^{1/4}/\sqrt{1 − ρ^{2}}, ∥σy − ρx∥_{2} ≥ \sqrt{−2 log η}/\sqrt{1 − ρ^{2}}\},

\{y ∈ ℝ^{n}: ∥σy − ρx∥_{2} > (1 + 1/10)\sqrt{−3 log(ρη)}/\sqrt{1 − ρ^{2}}\}.

We then apply Lemma 5.2 to get

sup_{t_{1}∈[min(x_{1},0),max(x_{1},0)] t_{2}∈[min(x_{2},0),max(x_{2},0)] α∈[0,ρ]} | ∫_{ℝ^{n}} ∑_{\begin{matrix}ℓ∈ℕ^{n}: \\ 0≤|ℓ|≤3 \end{matrix}} ∏_{i=1}^{n} |y_{i}|^{ℓ_{i}} g((t_{1}, t_{2}, 0, …, 0)α + y\sqrt{1 − α^{2}})dγ_{n}(y)|

≤ 500000n^{3}η^{11/10} + 500000n^{3}(ρη)^{1/4}(−2(1 − 2ρ)^{2} log η + 1)η^{(1−2ρ)^{2}}

+ 200(n + 2)!((−3 log(ηρ))^{(n+1)/2} + 1)(ρη)^{3/2} + 1600(n + 2)!2η^{11/10}/\sqrt{−2 log η}.

(90)

Applying (90) to Lemma 5.3, using (52) and η < ρ < e^{−20(n+1)^{10^{12}n^{3}(n+2)!}},

\begin{matrix}∥x∥_{2}^{2} ≤ −4 log(ηρ) ∧ η^{21/20}ρ^{1/2} ≤ |x_{1}| ≤ (ηρ)^{1/4} ∧ x ∈ B_{i} ∪ B_{j} \\ ⟹ ρ^{−1} |LT_{ρ}(1_{A_{i}} − 1_{A_{j}})(x) − LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x)| < \frac{1}{10}η^{21/20}ρ^{1/2}. \end{matrix}  (91)

Also, by (51),

\begin{matrix}η^{21/20}ρ^{1/2} ≤ |x_{1}| ≤ (ηρ)^{1/4} ∧ ∥x∥_{2}^{2} − 4 log(ηρ) ∧ x ∈ B_{i} ∪ B_{j} \\ ⟹ ρ^{−1}sign(x_{1}) · LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x) > \frac{1}{10}η^{21/20}ρ^{1/2}. \end{matrix}  (92)

So, combining (91), (92) for all i′, j′ ∈ {1, …, k}, i′ ≠ j′, Lemma 3.1, (89), and by applying the inclusion-exclusion principle, (57) and (62),

\begin{matrix}η^{21/20}ρ^{1/2} ≤ |x_{1}| ≤ (ηρ)^{1/4} ∧ ∥x∥_{2}^{2} ≤ −4 log(ηρ) ∧ x ∈ B′_{i} ∪ B′_{j} \\ ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0. \end{matrix}  (93)

So, (93) and (58) say that

η^{21/20}ρ^{1/2} ≤ |x_{1}| ∧ ∥x∥_{2}^{2} ≤ −4 log(ηρ) ∧ x ∈ B′_{i}∪B′_{j} ⟹ sign(x_{1})·(1_{A_{i}}(x)−1_{A_{j}}(x)) > 0. (94)

Finally, we use (94) in place of (88) and repeat the computations (90) through (93) to get

ηρ ≤ |x_{1}| ∧ ∥x∥_{2}^{2} ≤ −4 log(ηρ) ∧ x ∈ B′_{i} ∪ B′_{j} ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0. (95)

In conclusion, (49) follows from (95) and (46), letting B′′_{i} := B′_{i} and B′′_{j} := B′_{j}. Step 7. Completing the proof.

For completeness, we derive (95). Redefine B_{i}, B_{j} so that

B_{i} := B_{i,2η^{21/20}ρ^{1/2}/\sqrt{−4 log(ηρ)}} , B_{j} := B_{j,2η^{21/20}ρ^{1/2}/\sqrt{−4 log(ηρ)}}.  (96)

Let σ: ℝ^{n} → ℝ^{n} be any rotation fixing the x_{1}-axis. Let x with ∥x∥_{2}^{2} ≤ −4 log(ηρ) ≤ −8 log η and ηρ ≤ |x_{1}| ≤ (ηρ)^{1/3}. Let B := (B_{i} ∩ B_{j}) ∪ [(B_{i} ∪ B_{j}) \ (B′_{i} ∪ B′_{j})]. Suppose x ∈ B_{i} ∪ B_{j} also. Combining (94), (58), and (47), g ≠ 0 only on the following sets:

\{y ∈ ℝ^{n}: |d(σy − ρx, B)| ≤ η^{21/20}ρ^{1/2}/\sqrt{1 − ρ^{2}}\},

\{y ∈ ℝ^{n}: |d(σy − ρx, B)| ≤ (ρη)^{1/3}/\sqrt{1 − ρ^{2}}, ∥σy − ρx∥_{2} ≥ \sqrt{−2 log η}/\sqrt{1 − ρ^{2}}\},

\{y ∈ ℝ^{n}: ∥σy − ρx∥_{2} > (1 + 1/10)\sqrt{−3 log(ρη)}/\sqrt{1 − ρ^{2}}\}.

We then apply Lemma 5.2 to get

sup_{t_{1}∈[min(x_{1},0),max(x_{1},0)] t_{2}∈[min(x_{2},0),max(x_{2},0)] α∈[0,ρ]} | ∫_{ℝ^{n}} ∑_{\begin{matrix}ℓ∈ℕ^{n}: \\ 0≤|ℓ|≤3 \end{matrix}} ∏_{i=1}^{n} |y_{i}|^{ℓ_{i}} g((t_{1}, t_{2}, 0, …, 0)α + y\sqrt{1 − α^{2}})dγ_{n}(y)|

≤ 500000n^{3}η^{21/20}ρ^{1/2} + 500000n^{3}(ρη)^{1/3}(−2(1 − 2ρ)^{2} log η + 1)η^{(1−2ρ)^{2}}

+ 200(n + 2)!((−3 log(ηρ))^{(n+1)/2} + 1)(ρη)^{3/2} + 1600(n + 2)!2η^{6/5}ρ^{1/2}/\sqrt{−4 log(ηρ)}.

(97)

Applying (97) to Lemma 5.3, using (52) and η < ρ < e^{−20(n+1)^{10^{12}n^{3}(n+2)!}},

\begin{matrix}∥x∥_{2}^{2} ≤ −4 log(ηρ) ∧ ηρ ≤ |x_{1}| ≤ (ηρ)^{1/3} ∧ x ∈ B_{i} ∪ B_{j} \\ ⟹ ρ^{−1} |LT_{ρ}(1_{A_{i}} − 1_{A_{j}})(x) − LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x)| < \frac{1}{10}ηρ. \end{matrix}  (98)

Also, by (51),

\begin{matrix}ηρ ≤ |x_{1}| ≤ (ηρ)^{1/3} ∧ ∥x∥_{2}^{2} ≤ −4 log(ηρ) ∧ x ∈ B_{i} ∪ B_{j} \\ ⟹ ρ^{−1}sign(x_{1}) · LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x) > \frac{1}{10}ηρ. \end{matrix}  (99)

So, combining (98), (99) for all i′, j′ ∈ {1, …, k}, i′ ≠ j′, Lemma 3.1, (96), and by applying the inclusion-exclusion principle, (57) and (62),

ηρ ≤ |x_{1}| ≤ (ηρ)^{1/3} ∧ ∥x∥_{2}^{2} ≤ −4 log(ηρ) ∧ x ∈ B′_{i} ∪ B′_{j} ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0.

(100)

Then, (100) and (58) say that

ηρ ≤ |x_{1}| ∧ ∥x∥_{2}^{2} ≤ −4 log(ηρ) ∧ x ∈ B′_{i} ∪ B′_{j} ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0. (101)

Finally, (95) follows from (101), completing the proof. □

7. Proof of the Main Theorem

We now combine the Lemmas of the previous sections, as described in Section 1. The main effort involves verifying the assumption of the Main Lemma 6.1. Once this is done, Lemma 6.1 can be iterated infinitely many times to complete the proof.

Theorem 7.1. Fix k = 3, n ≥ 2. Define Δ_{k}(γ_{n}) as in Definition 2.1 and define ψ_{ρ} as in (29). Let {C_{i}}_{i=1}^{k} ⊆ ℝ^{n} be a regular simplicial conical partition. Then there exists ρ_{0} = ρ_{0}(n, k) > 0 such that, for all ρ ∈ (0, ρ_{0}), (1_{C_{1}}, …, 1_{C_{k}}) uniquely achieves the following supremum, up to rotation

sup_{(f_{1},...,f_{k})∈Δ_{k}(γ_{n})} ρ^{−1} ∑_{i=1}^{k} ∫_{ℝ^{n}} f_{i}LT_{ρ}f_{i}dγ_{n} = sup_{(f_{1},...,f_{k})∈Δ_{k}(γ_{n})} ψ_{ρ}(f_{1}, …, f_{k}).

Proof. Within the proof, we will assert that ρ > 0 satisfies several upper bounds, and then at the end of the proof, we will define ρ_{0} as the minimum of these upper bounds. By Lemma 3.1, let {A_{i}}_{i=1}^{k} be a partition of ℝ^{n} such that

ψ_{ρ}(1_{A_{1}}, …, 1_{A_{k}}) = sup_{(f_{1},...,f_{k})∈Δ_{k}(γ_{n})} ψ_{ρ}(f_{1}, …, f_{k}).  (102)

By (12), write

ρ^{−1} ∑_{i=1}^{k} ∫_{ℝ^{n}} 1_{A_{i}}LT_{ρ}1_{A_{i}}dγ_{n} = ∑_{i=1}^{k} ∑_{ℓ∈ℕ^{n}} |ℓ| |∫_{ℝ^{n}} 1_{A_{i}} \sqrt{ℓ!}h_{ℓ}dγ_{n}|^{2} ρ^{|ℓ|−1}.  (103)

Step 1. The partition {A_{i}}_{i=1}^{k} is close to being simplicial.

For i ∈ {1, …, k}, let z_{i} := ∫_{A_{i}} xdγ_{n}(x) ∈ ℝ^{n}. Subtracting the |ℓ| = 1 term from both sides of (103), treating the remaining terms as error terms, and using that ∥1_{A_{i}}∥_{L_{2}(γ_{n})} ≤ 1 for all i = 1, …, k,

|ρ^{−1} ∑_{i=1}^{k} ∫_{ℝ^{n}} 1_{A_{i}}LT_{ρ}1_{A_{i}}dγ_{n} − ∑_{i=1}^{k} ∥z_{i}∥_{ℓ_{2}^{n}}^{2} | ≤ 3kρ.  (104)

Therefore,

∑_{i=1}^{k} ∥z_{i}∥_{ℓ_{2}^{n}}^{2} =^{(14)} ψ_{0}(1_{A_{1}}, …, 1_{A_{k}}) ≥^{(104)} ψ_{ρ}(1_{A_{1}}, …, 1_{A_{k}}) − 3kρ ≥^{(102)} ψ_{ρ}(1_{B_{1}}, …, 1_{B_{k}}) − 3kρ

≥^{(104)} ψ_{0}(1_{B_{1}}, …, 1_{B_{k}}) − 6kρ =^{(Lemma 2.5)} sup_{(f_{1},...,f_{k})∈Δ_{k}(γ_{n})} ψ_{0}(f_{1}, …, f_{k}) − 6kρ.

Step 2. Applying a small rotation.

For i ∈ {1, …, k}, let w_{i} := ∫_{B_{i}} xdγ_{n}(x). Let ρ > 0 such that 6kρ < 10^{−2}. Then by Lemma 2.8,

d_{2}({A_{i}}_{i=1}^{k}, {B_{i}}_{i=1}^{k}) < 6(6kρ)^{1/8},  (105)
inf_{σ∈SO(n)} (∑_{i=1}^{k} ∥σz_{i} − w_{i}∥_{ℓ_{2}^{n}}^{2})^{1/2} < 6(6kρ)^{1/8}.  (106)

Note that (106) follows from (105) by Hilbert space duality and since the set of functions \{x_{i}\}_{i=1}^{n} are contained in the orthonormal basis \{h_{ℓ}\sqrt{ℓ!}\}_{ℓ∈ℕ^{n}} of L_{2}(γ_{n}).

Let x = (x_{1}, …, x_{n}) ∈ ℝ^{n}, let i, j ∈ {1, …, k}, i ≠ j, and write the following equality of L_{2} functions

1_{A_{i}}(x) − 1_{A_{j}}(x) =: ∑_{ℓ∈ℕ^{n}} c_{ℓ}h_{ℓ}(x)\sqrt{ℓ!}.  (107)

Let ℓ = (ℓ_{1}, …, ℓ_{n}) ∈ ℕ^{n}. By applying an orthogonal change of coordinates to {A_{p}}_{p=1}^{k}, we may assume that c_{ℓ} = 0 when |ℓ| = 1, ℓ_{1} = 0. By (9) and (6), write

ρ^{−1}LT_{ρ}(1_{A_{i}} − 1_{A_{j}})(x) = ∑_{ℓ∈ℕ^{n}} c_{ℓ} |ℓ| ρ^{|ℓ|−1}h_{ℓ}(x)\sqrt{ℓ!}.  (108)

Since d_{2}({A_{p}}_{p=1}^{k}, {B_{p}}_{p=1}^{k}) < 6(6kρ)^{1/8}, there exists {B′′_{p}}_{p=1}^{k} a regular simplicial conical partition, such that (∑_{p=1}^{k} ∥1_{A_{p}} − 1_{B′′_{p}}∥_{L_{2}(γ_{n})}^{2})^{1/2} < 6(6kρ)^{1/8}. In particular, by Hilbert space duality,

|| ∫_{ℝ^{n}} x(1_{A_{i}}(x) − 1_{A_{j}}(x) − (1_{B′′_{i}}(x) − 1_{B′′_{j}}(x)))dγ_{n}(x)||_{ℓ_{2}^{n}} < 6(6kρ)^{1/8},  (109)

|| ∫_{ℝ^{n}} x(1_{(A_{i}∪A_{j})^{c}}(x) − 1_{(B′′_{i}∪B′′_{j})^{c}}(x))dγ_{n}(x)||_{ℓ_{2}^{n}} < 6(6kρ)^{1/8}.  (110)

Since k = 3, and since ∑_{p=1}^{k} ∫_{A_{p}} xdγ_{n}(x) = ∫_{ℝ^{n}} xdγ_{n}(x) = 0, there exists a 2-dimensional plane Π ⊆ ℝ^{n} such that 0 ∈ Π and such that, for all p ∈ {1, …, k}, ∫_{A_{p}} xdγ_{n}(x) ∈ Π. Without loss of generality, Π contains the x_{1} and x_{2} axes.

Let {B′_{p}}_{p=1}^{k} be a regular simplicial conical partition such that

(∑_{p=1}^{k} ∥1_{B′_{p}} − 1_{B′′_{p}}∥_{L_{2}(γ_{n})}^{2})^{1/2} < 10(6kρ)^{1/16},  (111)

such that for fixed i ≠ j, i, j ∈ {1, …, k} and for some λ′ ∈ ℝ,

∫_{ℝ^{n}} x(1_{A_{i}}(x) − 1_{A_{j}}(x))dγ_{n}(x) = λ′ ∫_{ℝ^{n}} x(1_{B′_{i}}(x) − 1_{B′_{j}}(x))dγ_{n}(x),  (112)

and such that

∫_{ℝ^{n}} x(1_{(B′_{i}∪B′_{j})^{c}})dγ_{n}(x) ∈ Π.  (113)

Such {B′_{p}}_{p=1}^{k} exists by (109), letting ρ > 0 such that ρ < (10000k)^{−8}, so that

∥∫_{ℝ^{n}} x(1_{B′′_{i}}(x) − 1_{B′′_{j}}(x))dγ_{n}(x)∥_{ℓ_{2}^{n}} = 3\sqrt{2}/(4\sqrt{π}).

∥∫_{ℝ^{n}} x(1_{(B′′_{i}∪B′′_{j})^{c}}(x))dγ_{n}(x)∥_{ℓ_{2}^{n}} = ∥∫_{ℝ^{n}} x(1_{B′′_{i}}(x))∥_{ℓ_{2}^{n}} = \sqrt{6}/(4\sqrt{π}).

So, by the triangle inequality applied to (109), and (110),

∥∫_{ℝ^{n}} x(1_{A_{i}}(x) − 1_{A_{j}}(x))dγ_{n}(x)∥_{ℓ_{2}^{n}} > 3\sqrt{2}/(4\sqrt{π}) − 10^{−2} > 1/3.  (114)

∥∫_{ℝ^{n}} x(1_{(A_{i}∪A_{j})^{c}}(x))dγ_{n}(x)∥_{ℓ_{2}^{n}} > \sqrt{6}/(4\sqrt{π}) − 10^{−2} > 1/3.  (115)

Specifically, we first apply a rotation to {B′′_{p}}_{p=1}^{k} such that (112) holds. Then, by (110), we then apply another rotation that fixes the x_{1} axis, so that (113) holds. By (109), (110), (114) and (115), each of these two rotations can be chosen so that a given unit vector is moved in ℝ^{n} a distance not more than 12(6kρ)^{1/8}. And since we are rotating three polygonal cones with two facets each, (111) holds.

Using (111) and the triangle inequality,

(∑_{p=1}^{k} ∥1_{A_{p}} − 1_{B′_{p}}∥_{L_{2}(γ_{n})}^{2})^{1/2} < 20(6kρ)^{1/16}.  (116)

Also, using that c_{ℓ} = 0 for |ℓ| = 1, ℓ_{1} = 0, (112) implies that B′_{i} ∩ B′_{j} ⊆ {x ∈ ℝ^{n}: x_{1} = 0}, and we may assume that B′_{i} ⊆ {x ∈ ℝ^{n}: x_{1} ≥ 0}.

Let n′_{i} ∈ ℝ^{n} denote the interior unit normal of B′_{i} such that n′_{i} is normal to (∂B′_{i}) \ B′_{j}, and let n′_{j} ∈ ℝ^{n} denote the interior unit normal of B′_{j} such that n′_{j} is normal to (∂B′_{j}) \ B′_{i}. Then, define B_{i}, B_{j} such that

\begin{matrix}B_{i} := B′_{i} ∪ \{x ∈ ℝ^{n}: x_{1} ≥ 0 ∧ ⟨n′_{i}, x/ ∥x∥_{2}⟩ ≥ −4ρ^{21/20}/\sqrt{−3 log ρ}\}, \\ B_{j} := B′_{j} ∪ \{x ∈ ℝ^{n}: x_{1} ≤ 0 ∧ ⟨n′_{j}, x/ ∥x∥_{2}⟩ ≥ −4ρ^{21/20}/\sqrt{−3 log ρ}\}. \end{matrix}  (117)

Since B_{i} ∪ B_{j} is symmetric with respect to reflection across B_{i} ∩ B_{j} = B′_{i} ∩ B′_{j}, equation (112) implies that there is a λ > 0 such that

∫_{ℝ^{n}} x(1_{A_{i}}(x) − 1_{A_{j}}(x))dγ_{n}(x) = λ ∫_{ℝ^{n}} x(1_{B_{i}}(x) − 1_{B_{j}}(x))dγ_{n}(x).  (118)

Step 3. An estimate for small x.

Combining (6), (9), and (118), there exists |b_{1}| < 50(6kρ)^{1/16} (by Hilbert space duality, eqrefthree7.93 and (117)) such that

ρ^{−1}LT_{ρ}(1_{A_{i}} − 1_{A_{j}})(x) − ρ^{−1}LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x) − x_{1}b_{1} =: ∑_{ℓ∈ℕ^{n}: |ℓ|≥2} b_{ℓ} |ℓ| ρ^{|ℓ|−1}h_{ℓ}(x)\sqrt{ℓ!}. (119)

Choose ρ_{1} so that 0 < ρ < ρ_{1} implies 100k^{1/16} ∑_{m=2}^{∞} m(m+n−1)^{n}ρ^{m−2}m^{n}3^{m}(− log ρ^{3})^{m/2} < ρ^{−1/80}/20. Recall that the number of ℓ ∈ ℕ^{n} such that |ℓ| = m is equal to \frac{m+n−1!}{m!(n−1)!} ≤ (m + n − 1)^{n}. Note that, |b_{ℓ}| < 100k^{1/16}ρ^{1/16}, for all ℓ ∈ ℕ^{n}, |ℓ| ≥ 2, by Hilbert space duality. Let x ∈ ℝ^{n} with ∥x∥_{2}^{2} ≤ − log ρ^{3}. By (119), Lemma 5.1,

\begin{matrix}|ρ^{−1}LT_{ρ}(1_{A_{i}} − 1_{A_{j}})(x) − ρ^{−1}LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x) − x_{1}b_{1}| \\ ≤ 100k^{1/8}ρ^{17/16} ∑_{ℓ∈ℕ^{n}: |ℓ|≥2} |ℓ| ρ^{|ℓ|−2} |h_{ℓ}(x)| \sqrt{ℓ!} \\ ≤ 100k^{1/8}ρ^{17/16} ∑_{ℓ∈ℕ^{n}: |ℓ|≥2} |ℓ| ρ^{|ℓ|−2} |ℓ|^{n} 3^{|ℓ|} ∏_{i=1}^{n} max\{1, |x_{i}|^{ℓ_{i}}\} \\ ≤ 100k^{1/8}ρ^{17/16} ∑_{m=2}^{∞} m(m + n − 1)^{n}ρ^{m−2}m^{n}3^{m}(− log ρ^{3})^{m/2} ≤ ρ^{21/20}/20. \end{matrix}  (120)

From Lemma 4.2 and (9), for x = (x_{1}, …, x_{n}), with B_{i} ∩ B_{j} ⊆ {x ∈ ℝ^{n}: x_{1} = 0},

x ∈ B_{i} ∪ B_{j} ∧ ∥x∥_{2}^{2} ≤ − log ρ^{3} ⟹ ρ^{−1}sign(x_{1}) · LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x) > (1/10) |x_{1}| . (121)

Then (120) and (121) show that

|x_{1}| > ρ^{21/20} ∧ ∥x∥_{2}^{2} ≤ − log ρ^{3} ∧ x ∈ B_{i}∪B_{j} ⟹ ρ^{−1}sign(x_{1})·LT_{ρ}(1_{A_{i}} −1_{A_{j}})(x) > 0. (122)

By (102), Lemma 3.1, and by applying (122) for all i′, j′ ∈ {1, …, k}, i′ ≠ j′, along with the inclusion-exclusion principle,

|x_{1}| > ρ^{21/20} ∧ ∥x∥_{2}^{2} ≤ − log ρ^{3} ∧ x ∈ B′_{i} ∪ B′_{j} ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0. (123)

From (123),

\begin{matrix}x ∈ B′_{i} ∪ B′_{j} ∧ |d(x, (∂B′_{i}) ∪ (∂B′_{j}))| > ρ^{21/20} ∧ ∥x∥_{2}^{2} ≤ − log ρ^{3} \\ ⟹ sign(x_{1}) · (1_{A_{i}}(x) − 1_{A_{j}}(x)) > 0. \end{matrix}  (124)

Step 4. Applying the Main Lemma.

Recall that there exists a 2-dimensional plane Π ⊆ ℝ^{n} such that 0 ∈ Π and such that, for all p ∈ {1, …, k}, ∫_{A_{p}} xdγ_{n}(x) ∈ Π. Define

S := span {∫_{ℝ^{n}}(1_{B′_{i}}(x) − 1_{B′_{j}}(x))xdγ_{n}(x), ∫_{ℝ^{n}}(1_{B′_{i}}(x) − 1_{(B′_{i}∪B′_{j})^{c}}(x))xdγ_{n}(x)
, ∫_{ℝ^{n}}(1_{B′_{j}}(x) − 1_{(B′_{i}∪B′_{j})^{c}}(x))xdγ_{n}(x)} .

Note that S is a 2-dimensional plane and 0 ∈ S. By (112), ∫_{ℝ^{n}}(1_{B′_{i}}(x) − 1_{B′_{j}}(x))dγ_{n}(x) ∈ Π. Moreover, since {B′_{i}, B′_{j}, (B′_{i} ∪ B′_{j})^{c}} is a regular simplicial conical partition,

S = span {∫_{B′_{i}} xdγ_{n}(x), ∫_{B′_{j}} xdγ_{n}(x), ∫_{(B′_{i}∪B′_{j})^{c}} xdγ_{n}(x)} .

From (113), S and Π are 2-dimensional planes that both contain the linearly independent vectors ∫_{(B′_{i}∪B′_{j})^{c}} xdγ_{n}(x) and ∫_{ℝ^{n}}(1_{B′_{i}}(x)−1_{B′_{j}}(x))xdγ_{n}(x). We therefore conclude that S = Π. In particular,

∫_{B′_{p}} xdγ_{n}(x) ∈ Π, ∀ p ∈ {i, j}.  (125)

Let ρ_{0} := min(ρ_{1}, 10^{−2}/6k, e^{−20(n+1)^{10^{12}n^{3}(n+2)!}}). Using (124), (112) and (125), we can iteratively apply Lemma 6.1 an infinite number of times. In particular, any time we know the conclusion (49), we use (49) in the assumption (48). That is, we first apply Lemma 6.1 with η = ρ^{21/20}. In this case, since η = ρ^{21/20}, (124) implies (48), (125) implies (47), and (118) implies (46). Now, using the conclusion (49) of Lemma 6.1, we can then apply Lemma 6.1 with η = ρ^{1+21/20}. Once again, using the conclusion (49) of Lemma 6.1, we can apply Lemma 6.1 with η = ρ^{2+21/20}, and so on. Repeating this process infinitely many times shows that there exists a regular simplicial conical partition {C_{i}}_{i=1}^{k} which is equal to {A_{i}}_{i=1}^{k}. □

The Main Theorem now follows from Theorem 7.1 and the Fundamental Theorem of Calculus.

Theorem 7.2 (Main Theorem). Let n ≥ 2, k = 3. There exists ρ_{0} = ρ_{0}(n, k) > 0 such that Conjecture 1 holds for ρ ∈ (0, ρ_{0}). Moreover, up to orthogonal transformation, the regular simplicial conical partition uniquely achieves the maximum of (3) in Conjecture 1.

Proof. Choose ρ_{0} via Theorem 7.1 and let 0 < ρ < ρ_{0}. Let {B_{i}}_{i=1}^{k} ⊆ ℝ^{n} be a regular simplicial conical partition. By Theorem 7.1 and the fact that Δ_{k}^{0}(γ_{n}) ⊆ Δ_{k}(γ_{n}),

ψ_{ρ}(1_{B_{1}}, …, 1_{B_{k}}) = sup_{(f_{1},...,f_{k})∈Δ_{k}^{0}(γ_{n})} ψ_{ρ}(f_{1}, …, f_{k}).  (126)

Let (f_{1}, …, f_{k}) ∈ Δ_{k}^{0}(γ_{n}). By (12), ∑_{i=1}^{k} ∫_{ℝ^{n}} f_{i}T_{0}f_{i}dγ_{n} = k(1/k^{2}) = 1/k. By the Fundamental Theorem of Calculus and (126),

∑_{i=1}^{k} ∫_{ℝ^{n}} f_{i}T_{ρ}f_{i}dγ_{n} = ∫_{0}^{ρ} [\frac{d}{dα} ∑_{i=1}^{k} ∫_{ℝ^{n}} f_{i}T_{α}f_{i}dγ_{n}]dα + \frac{1}{k} = ∫_{0}^{ρ} ψ_{α}(f_{1}, …, f_{k})dα + \frac{1}{k}

≤ ∫_{0}^{ρ} ψ_{α}(1_{B_{1}}, …, 1_{B_{k}})dα + \frac{1}{k} = ∫_{0}^{ρ} [\frac{d}{dα} ∑_{i=1}^{k} ∫_{ℝ^{n}} 1_{B_{i}}T_{α}1_{B_{i}}dγ_{n}]dα + \frac{1}{k}

= ∑_{i=1}^{k} ∫_{ℝ^{n}} 1_{B_{i}}T_{ρ}1_{B_{i}}dγ_{n}.

□

By using the invariance principle of [12, Theorem 1.10,Theorem 3.6,Theorem 7.1,Theorem 7.4] which transfers results from partitions of Euclidean space to low-influence discrete functions, Theorem 7.2 implies a weak form of the Plurality is Stablest Conjecture. While the following result is quite far from Conjecture 2 and might not be of immediate use to complexity theory, it is included to indicate a possible application of Theorem 7.2. Essentially, if we modify the exact application of the invariance principle that is used in [12, Theorem 7.1], then Conjecture 2 follows. However, by avoiding [12, Theorem 7.1], we must make very restrictive assumptions on the function f in Conjecture 2. Nevertheless, [12, Theorem 7.4] shows that the class of functions f described in Corollary 7.3 is nonempty.

Note that the most straightforward application of Theorem 7.2 only gives vacuous cases of Conjecture 2, in which 0 < ρ < ρ_{0}(n, k). In particular, since Theorem 7.2 requires 0 < ρ < ρ_{0}(n, k), by (12) we must take ε < 3kρ to get a nontrivial statement in Conjecture 2. In this case, the invariance principle [12, Theorem 3.6] gives τ with log τ = −C(log(ε))^{2}(1/ε), so that τ becomes a function of ρ. Since we provide a ρ with inverse exponential dependence on n, then τ also has inverse exponential dependence on n. Thus, no function f can satisfy the assumptions of Conjecture 2 in this case. To avoid this issue, we modify Conjecture 2 as follows.

Corollary 7.3 (Weak Form of Plurality is Stablest). Let ρ_{0}(n, k) be given by Theorem 7.2. Fix n ≥ 2, k = 3, and Let N := log log log log log(n) ≥ 1. Let 0 < ρ < ρ_{0}(N, k) < 1/2, ε > 0, τ = τ(ε, k) > 0. Let f: {1, …, k}^{n} → Δ_{k} with ∑_{σ∈{1,...,k}^{n}: σ_{j}≠0}(f̂_{i}(σ))^{2} ≤ τ for all i ∈ {1, …, k}, j ∈ {1, …, n}. Assume that there exists 0 < m < N and g: ℝ^{m} → Δ_{k} with ∫_{ℝ^{m}} gdγ_{m} = \frac{1}{k^{n}} ∑_{σ∈\{1,...,k\}^{n}} f(σ), and such that

| ∫_{ℝ^{n}}⟨ g, T_{ρ}g⟩dγ_{n} − \frac{1}{k^{n}} ∑_{σ∈\{1,...,k\}^{n}}⟨f(σ), T_{ρ}f(σ)⟩| < ε.

Then part (a) of Conjecture 2 holds. From [12][Theorem 7.4], this class of f is nontrivial.

Unfortunately, the proof of Theorem 7.2 fails for small negative ρ, as we now show.

Theorem 7.4. Fix k = 3, n ≥ 2. Define Δ_{k}^{0}(γ_{n}) as in Definition 2.2 and define ψ_{ρ} as in (29). Let {B_{i}}_{i=1}^{k} ⊆ ℝ^{n} be a regular simplicial conical partition. Then there exists ρ_{2} = ρ_{2}(n, k) > 0 such that, for ρ ∈ (−ρ_{2}, 0), (1_{B_{1}}, …, 1_{B_{k}}) does not achieve the following supremum.

sup_{(f_{1},...,f_{k})∈Δ_{k}^{0}(γ_{n})} ρ^{−1} ∑_{i=1}^{k} ∫_{ℝ^{n}} f_{i}LT_{ρ}f_{i}dγ_{n} = sup_{(f_{1},...,f_{k})∈Δ_{k}^{0}(γ_{n})} ψ_{ρ}(f_{1}, …, f_{k}).

Proof. Let e_{1} = (1, 0, …, 0), e_{2} = (0, 1, 0, …, 0). Fix i, j ∈ {1, …, k}, i ≠ j. Let σ: ℝ^{n} → ℝ^{n} denote reflection across B_{i} ∩ B_{j}. Since B_{i} = σ(B_{j}), by (31), it suffices to find i, j ∈ {1, …, k} and x ∈ B_{i} such that ρ^{−1}LT_{ρ}1_{B_{i}}(x) < ρ^{−1}LT_{ρ}1_{B_{j}}(x). By replacing {B_{i}}_{i=1}^{k} with {τB_{i}}_{i=1}^{k} for τ: ℝ^{n} → ℝ^{n} a rotation, we may assume that span{z_{i}}_{i=1}^{k} = span{e_{1}, e_{2}}. Moreover, we may assume B_{i} ∩ B_{j} ⊆ {x ∈ ℝ^{n}: x_{1} = 0} and B_{i} ⊆ {x ∈ ℝ^{n}: x_{1} ≥ 0}. Let y := (\sqrt{3}/2)e_{1} + (1/2)e_{2}, ỹ:= −(1/2)e_{1} + (\sqrt{3}/2)e_{2}. Fix x ∈ B_{i} with ⟨x, ỹ⟩ > 0 also fixed. From (36) and the fact that ρ < 0, there exists c = c(⟨x, ỹ⟩) > 0 such that

⟨x, \frac{1}{ρ}∇T_{ρ}(1_{B_{i}} − 1_{B_{j}})(x)⟩ = −⟨x, ỹ⟩(c + O(e^{−⟨x,y⟩^{2}/2})).  (127)

For x ∈ ℝ^{n} with ⟨x, ỹ⟩ = 0, we have, as in Lemma 5.2, and Lemma 4.1,

| ∫_{ℝ^{n}} ( ∑_{i=1}^{n}(1 − y_{i}^{2})(1_{B_{i}} − 1_{B_{j}})(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y))|

≤ 2| ∫_{B(0,ρ∥x∥_{2})} ∑_{i=1}^{n}(1 − y_{i}^{2})dγ_{n}(y)| ≤ 200(n + 1)!((ρ ∥x∥_{2})^{n} + 1)e^{−ρ^{2}∥x∥_{2}^{2}}.

So, a derivative bound as in the proof of (34) shows

\begin{matrix}| ∫_{ℝ^{n}} ( ∑_{i=1}^{n}(1 − y_{i}^{2})(1_{B_{i}} − 1_{B_{j}})(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y))| \\ ≤ ρ⟨x, ỹ⟩200(n + 2)! + 200(n + 1)!((ρ ∥x∥_{2})^{n} + 1)e^{−ρ^{2}∥x∥_{2}^{2}}. \end{matrix}  (128)

Then,

\begin{matrix}ρ^{−1}LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x) =^{(9)} \frac{1}{ρ}(⟨x, ∇T_{ρ}(1_{B_{i}} − 1_{B_{j}})(x)⟩ − ΔT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x)) \\ = ⟨x, T_{ρ}(∇(1_{B_{i}} − 1_{B_{j}}))(x)⟩ + \frac{ρ}{1 − ρ^{2}} ∫_{ℝ^{n}} ( ∑_{i=1}^{n}(1 − y_{i}^{2})(1_{B_{i}} − 1_{B_{j}})(xρ + y\sqrt{1 − ρ^{2}}))dγ_{n}(y). \end{matrix}

(129)

So, choose ρ < (c/8)(200(n + 2)!)^{−1}, then choose ⟨x, y⟩ sufficiently large, and then combine (127),(128) and (129) to get

ρ^{−1}LT_{ρ}(1_{B_{i}} − 1_{B_{j}})(x) < −⟨x, ỹ⟩\frac{c}{4}.

□

8. Open Problems

There are two problems that are left open in this work. First, Conjecture 1 remains entirely open for k ≥ 4 partition elements. Some of the results of this work hold for the case k ≥ 4, and some do not. The first variation in Lemma 3.1 holds for all k ≥ 4. Strictly speaking, the argument of Lemma 3.1 may not hold for ρ < 0 since it is not clear whether or not the functional (29) is convex. Also, the technical error estimate from Lemma 5.3 holds. One of the main issues for the case k ≥ 4 is that Lemma 2.5 is no longer available. Moreover, the stability estimate in Lemma 2.8 would be needed for k ≥ 4. The following conjecture summarizes the main technical issue in proving an analogue of Lemma 2.5 for k = 4, n = 3. If we could have a stability estimate for Conjecture 3 below, resembling the estimate of Lemma 2.8, then in principle the proof of the Main Lemma, Lemma 6.1 would go through, and therefore Theorem 7.2 would hold for k ≥ 4 as well. Before we state the conjecture, recall Definition 2.2, (29) and (14).

Conjecture 3. Let k = 4, n = 3. Suppose {A_{i}}_{i=1}^{k} ⊆ ℝ^{n} satisfies

ψ_{0}(1_{A_{1}}, …, 1_{A_{k}}) = sup_{(f_{1},...,f_{k})∈Δ_{k}^{0}(γ_{n})} ψ_{0}(f_{1}, …, f_{k}).

Then {A_{i}}_{i=1}^{k} is a simplicial conical partition.

This result is known to be true if we replace Δ_{k}^{0}(γ_{n}) with Δ_{k}(γ_{n}), by [14, Lemma 3.3]. However, the volume constraint of Δ_{k}^{0}(γ_{n}) causes difficulties for the methods of [14, 16].

The second problem that remains open is Conjecture 1 for ρ < 0 or for ρ positive and much larger than 0. We have already discussed the issues for ρ < 0 in Theorem 7.4, where it is shown that our proof strategy surprisingly fails for ρ < 0. For ρ with, e.g. ρ ∈ (1/2, 1), the error bounds that we use in the proof of Theorem 7.2 seem to break down, especially when we apply Lemma 6.1, Lemma 4.2, and (34). There is nothing special about our choice of 1/2 here, other than that it is a positive number that is sufficiently far from 0. So, it seems that our method is not applicable for ρ ∈ (1/2, 1). For example, Lemma 5.3 has an error term which is estimated by Lemma 5.2. However, the error estimate of Lemma 5.2 grows exponentially in n. And to compensate for this error, we need to choose ρ to decrease exponentially in n. Even before we apply the Main Lemma 6.1, there is also a loss in (120), where we essentially need a very specific L_{∞} bound on the Gaussian heat kernel (or Mehler kernel). We used the rather crude method of bounding each Hermite polynomial separately in Lemma 5.1, and then summing up these polynomials. In principle, both of these losses could be avoided with dimension independent error estimates in Lemmas 5.3 and Lemma 5.2. However, this seems to be a difficult task.

However, since the case ρ ∈ (1/2, 1) relates to geometric multi-bubble problems, whereas the case of small ρ seems to concern entirely different geometric information, it is unclear whether or not a single method could simultaneously solve or interpolate between different values of ρ in Conjecture 1.

Finally, a new open problem has emerged subsequent to this work. It turns out that if we modify the measure restriction in Conjecture 1 in any way, then the analogue of Conjecture 1 is false [11]. To be precise, in the statement of Conjecture 1, let (a_{1}, …, a_{k}) with 0 < a_{i} < 1 for all i = 1, …, k, and such that ∑_{i=1}^{k} a_{i} = 1. Assume that (a_{1}, …, a_{k}) ≠ (1/k, …, 1/k). Then, the partition {A_{i}}_{i=1}^{k} ⊆ ℝ^{n} which optimizes the noise stability (3) subject to the constraint γ_{n}(A_{i}) = a_{i} for all i = 1, …, k is not any translation of a regular simplicial conical partition. In fact, the optimal partition {A_{i}}_{i=1}^{k} has essentially no elementary description using simplices. See [11, Theorem 2.6] for a precise statement. So, for example, the following question is open.

Question 1. Let ρ > 0, k = 3, n = 2, and let (a_{1}, a_{2}, a_{3}) ∈ (0, 1)^{3} with ∑_{i=1}^{3} a_{i} = 1. What is the partition {A_{i}}_{i=1}^{3} maximizing the noise stability (3) subject to the constraint γ_{2}(A_{i}) = a_{i} for all i = 1, 2, 3?

Acknowledgement. Thanks to Assaf Naor for guidance and encouragement, and for helpful comments concerning Corollary 7.3. Thanks to Elchanan Mossel for helpful comments concerning the details of Corollary 7.3 and the vacuous cases of Conjecture 2. Thanks to Oded Regev for reading the manuscript thoroughly and providing helpful comments. Thanks also to the anonymous reviewers’ thorough reading and helpful comments.

References

[1] G. E. Andrews, R. Askey, and R. Roy. Special functions, volume 71 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1999.

[2] P. Austrin. Towards sharp inapproximability for any 2-CSP. SIAM J. Comput., 39(6):2430–2463, 2010.

[3] C. Borell. Geometric bounds on the Ornstein-Uhlenbeck velocity process. Z. Wahrsch. Verw. Gebiete, 70(1):1–13, 1985.

[4] M. Braverman, K. Makarychev, Y. Makarychev, and A. Naor. The Grothendieck constant is strictly smaller than Krivine’s bound. Forum Math. Pi, 1:e4, 42, 2013.

[5] S. Chatterjee. A generalization of the Lindeberg principle. Ann. Probab., 34(6):2061–2076, 2006.

[6] J. Corneli, I. Corwin, S. Hurder, V. Sesum, Y. Xu, E. Adams, D. Davis, M. Lee, R. Visocchi, and N. Hoffman. Double bubbles in Gauss space and spheres. Houston J. Math., 34(1):181–204, 2008.

[7] R. Eldan. A two-sided estimate for the Gaussian noise stability deficit. Preprint, arXiv:1307.2781, 2013.

[8] A. Frieze and M. Jerrum. Improved approximation algorithms for MAX k-CUT and MAX BISECTION. In Integer programming and combinatorial optimization (Copenhagen, 1995), volume 920 of Lecture Notes in Comput. Sci., pages 1–13. Springer, Berlin, 1995.

[9] L. Gross. Logarithmic Sobolev inequalities. Amer. J. Math., 97(4):1061–1083, 1975.

[10] S. Heilman, A. Jagannath, and A. Naor. Solution of the propeller conjecture in ℝ^{3}. Discrete & Computational Geometry, 50(2):263–305, 2013.

[11] S. Heilman, E. Mossel, and J. Neeman. Standard simplices and pluralities are not the most noise stable. preprint, arXiv:1403.0885, 2014.

[12] M. Isaksson and E. Mossel. Maximally stable Gaussian partitions with discrete applications. Israel J. Math., 189:347–396, 2012.

[13] S. Khot, G. Kindler, E. Mossel, and R. O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357, 2007.

[14] S. Khot and A. Naor. Approximate kernel clustering. Mathematika, 55(1-2):129–165, 2009.

[15] S. Khot and A. Naor. Grothendieck-type inequalities in combinatorial optimization. Comm. Pure Appl. Math., 65(7):992–1035, 2012.

[16] S. Khot and A. Naor. Sharp kernel clustering algorithms and their associated grothendieck inequalities. Random Structures & Algorithms, 42(3):269–300, 2013.

[17] M. Ledoux. Isoperimetry and Gaussian analysis. In Lectures on probability theory and statistics (Saint-Flour, 1994), volume 1648 of Lecture Notes in Math., pages 165–294. Springer, Berlin, 1996.

[18] E. Mossel and J. Neeman. Robust optimality of Gaussian noise stability. Preprint, arXiv:1210.4126, 2012.

[19] E. Mossel, R. O’Donnell, and K. Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. Ann. of Math. (2), 171(1):295–341, 2010.

[20] P. Raghavendra and D. Steurer. Towards computing the Grothendieck constant. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 525–534, Philadelphia, PA, 2009. SIAM.

[21] E. M. Stein. Singular integrals and differentiability properties of functions. Princeton Mathematical Series, No. 30. Princeton University Press, Princeton, N.J., 1970.

9. Appendix: Differentiation of the Ornstein Uhlenbeck Semigroup

We prove (9) and (10). Let ρ ∈ (−1, 1) and let f: ℝ^{n} → ℝ. In the following calculations, we use integration by parts freely, and we use differentiation in the distributional sense. We first calculate derivatives of T_{ρ}f(x) with respect to x ∈ ℝ^{n}, and then we calculate the derivative of T_{ρ}f(x) with respect to ρ.

\frac{∂}{∂x_{i}} T_{ρ}f(x) =^{(2)} ∫ \frac{∂}{∂x_{i}} [f(xρ + y\sqrt{1 − ρ^{2}})]dγ_{n}(y)

= ∫ \frac{∂f(xρ + y\sqrt{1 − ρ^{2}})}{∂z_{i}}dγ_{n}(y)ρ

= ∫ \frac{∂}{∂y_{i}} [f(xρ + y\sqrt{1 − ρ^{2}})]dγ_{n}(y)\frac{ρ}{\sqrt{1 − ρ^{2}}}

= − ∫ f(xρ + y\sqrt{1 − ρ^{2}})\frac{∂}{∂y_{i}} [dγ_{n}(y)]\frac{ρ}{\sqrt{1 − ρ^{2}}}

= \frac{ρ}{\sqrt{1 − ρ^{2}}} ∫ y_{i}f(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y).  (130)

\frac{∂^{2}}{∂x_{i}^{2}} T_{ρ}f(x) =^{(130)} \frac{ρ}{\sqrt{1 − ρ^{2}}} ∫ \frac{∂}{∂x_{i}} [f(xρ + y\sqrt{1 − ρ^{2}})]y_{i}dγ_{n}(y)

= \frac{ρ}{\sqrt{1 − ρ^{2}}} ∫ \frac{∂f(xρ + y\sqrt{1 − ρ^{2}})}{∂z_{i}}y_{i}dγ_{n}(y)ρ

= \frac{ρ^{2}}{1 − ρ^{2}} ∫ \frac{∂}{∂y_{i}} [f(xρ + y\sqrt{1 − ρ^{2}})]y_{i}dγ_{n}(y)

= −\frac{ρ^{2}}{1 − ρ^{2}} ∫ f(xρ + y\sqrt{1 − ρ^{2}})\frac{∂}{∂y_{i}} [y_{i}dγ_{n}(y)]

= −\frac{ρ^{2}}{1 − ρ^{2}} ∫ f(xρ + y\sqrt{1 − ρ^{2}})(−y_{i}^{2} + 1)dγ_{n}(y)

= \frac{ρ^{2}}{1 − ρ^{2}} ∫ (y_{i}^{2} − 1)f(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y).  (131)

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

= ∫_{ℝ^{n}} ∑_{i=1}^{n} \frac{∂f(xρ + y\sqrt{1 − ρ^{2}})}{∂z_{i}} (x_{i} − y_{i} \frac{ρ}{\sqrt{1 − ρ^{2}}} ) dγ_{n}(y)

= ∫_{ℝ^{n}} ∑_{i=1}^{n} \frac{∂}{∂y_{i}} [f(xρ + y\sqrt{1 − ρ^{2}})] (x_{i} − y_{i} \frac{ρ}{\sqrt{1 − ρ^{2}}} ) \frac{dγ_{n}(y)}{\sqrt{1 − ρ^{2}}}

= − ∫_{ℝ^{n}} f(xρ + y\sqrt{1 − ρ^{2}}) ∑_{i=1}^{n} \frac{∂}{∂y_{i}} [(x_{i} − y_{i} \frac{ρ}{\sqrt{1 − ρ^{2}}} ) \frac{dγ_{n}(y)}{\sqrt{1 − ρ^{2}}} ]

= − ∫_{ℝ^{n}} f(xρ + y\sqrt{1 − ρ^{2}}) ∑_{i=1}^{n} [(x_{i} − y_{i} \frac{ρ}{\sqrt{1 − ρ^{2}}} ) (−y_{i}) − \frac{ρ}{\sqrt{1 − ρ^{2}}} ] \frac{dγ_{n}(y)}{\sqrt{1 − ρ^{2}}}

= − ∫_{ℝ^{n}} f(xρ + y\sqrt{1 − ρ^{2}}) ∑_{i=1}^{n} [(y_{i}^{2} − 1)\frac{ρ}{\sqrt{1 − ρ^{2}}} − x_{i}y_{i}] \frac{dγ_{n}(y)}{\sqrt{1 − ρ^{2}}}

= \frac{1}{ρ}[\frac{ρ}{\sqrt{1 − ρ^{2}}} ⟨x, ∫_{ℝ^{n}} yf(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y)⟩

+ \frac{ρ^{2}}{1 − ρ^{2}} ∫_{ℝ^{n}} (∑_{i=1}^{n}(1 − y_{i}^{2})) f(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y)]

=^{(130)∧(131)} \frac{1}{ρ} (⟨x, ∇T_{ρ}f(x)⟩ − ΔT_{ρ}f(x)) .

Courant Institute, New York University, New York NY 10012

E-mail address: heilman@cims.nyu.edu