DIMENSION-FREE NONINTERACTIVE SIMULATION FROM GAUSSIAN SOURCES

STEVEN HEILMAN AND ALEX TARTER

Abstract. Let X and Y be two real-valued random variables. Let (X_{1}, Y_{1}), (X_{2}, Y_{2}), … be independent identically distributed copies of (X, Y). Suppose there are two players A and B. Player A has access to X_{1}, X_{2}, … and player B has access to Y_{1}, Y_{2}, . . .. Without communication, what joint probability distributions can players A and B jointly simulate? That is, if k, m are fixed positive integers, what probability distributions on {1, …, m}^{2} are equal to the distribution of (f(X_{1}, …, X_{k}), g(Y_{1}, …, Y_{k})) for some f, g: ℝ^{k} → {1, …, m}?

When X and Y are standard Gaussians with fixed correlation ρ ∈ (−1, 1), we show that the set of probability distributions that can be noninteractively simulated from k Gaussian samples is the same for any k ≥ m^{2}. Previously, it was not even known if this number of samples m^{2} would be finite or not, except when m ≤ 2.

Consequently, a straightforward brute-force search deciding whether or not a probability distribution on {1, …, m}^{2} is within distance 0 < ε < |ρ| of being noninteractively simulated from k correlated Gaussian samples has run time bounded by (5/ε)^{m(log(ε/2)/ log |ρ|)^{m^{2}}} , improving a bound of Ghazi, Kamath and Raghavendra.

A nonlinear central limit theorem (i.e. invariance principle) of Mossel then generalizes this result to decide whether or not a probability distribution on {1, …, m}^{2} is within distance 0 < ε < |ρ| of being noninteractively simulated from k samples of a given finite discrete distribution (X, Y) in run time that does not depend on k, with constants that again improve a bound of Ghazi, Kamath and Raghavendra.

Contents

1. Introduction  1
2. Existence and Regularity  12
3. First and Second Variation  21
4. Noise Stability and the Calculus of Variations  23
5. Proof of the Main Dimension Reduction Theorem  30
References  32

1. Introduction

Let (X, Y) ∈ ℝ × ℝ be a random vector. Let (X_{1}, Y_{1}), (X_{2}, Y_{2}), … be independent identically distributed (i.i.d.) copies of (X, Y). Suppose there are two players A and B. Player A has access to X_{1}, X_{2}, … and player B has access to Y_{1}, Y_{2}, . . .. Without communication,

Date: February 21, 2022. Key words and phrases. information theory, noninteractive simulation, correlated random variables, noise

stability.

S. H. is Supported by NSF Grant CCF 1911216.

what joint distributions can players A and B jointly simulate? That is, what joint distributions can be noninteractively simulated by the two players? Put another way, if k, m are fixed positive integers, what probability distributions on {1, …, m}^{2} can be written as the distribution of (f(X_{1}, …, X_{k}), g(Y_{1}, …, Y_{k})), where f, g: ℝ^{k} → {1, …, m}? Put another way, how can the “correlation information” of random samples from (X, Y) be reformulated using functions of those random samples?

The statement of this noninteractive simulation problem was attributed to Slepian by [?] without reference, perhaps as a reference to [?]. As a preliminary example, note that if X is independent of Y, then (f(X_{1}, …, X_{k}), g(Y_{1}, …, Y_{k})) has a product distribution, so we cannot write any non-product distribution as (f(X_{1}, …, X_{k}), g(Y_{1}, …, Y_{k})) in this case. But if X is not independent of Y, then it can be much harder to determine which distributions can or cannot be written as (f(X_{1}, …, X_{k}), g(Y_{1}, …, Y_{k})) for any k ≥ 2, for some f, g: ℝ^{k} → {1, …, m}. Recall also that if W is a uniformly distributed random variable in [0, 1], then for any m > 0, any probability distribution on {1, …, m}^{2} can be written as h(W) using a function h: [0, 1] → {1, …, m}^{2} by defining h so that ℙ(h(W) = (i, j)) is its specified value for all 1 ≤ i, j ≤ m. That is, it is always possible to simulate correlated discrete random variables using shared randomness. In noninteractive simulation, perfect shared randomness means that X = Y, i.e. X and Y are perfectly correlated.

The purpose of the noninteractive simulation problem is to limit the amount of correlated random variables that players A and B can sample, while any amount of independent randomness should be allowed to the players. For this reason, the following formulation of the noninteractive simulation problem is considered morally equivalent to our first formulation: if k, m are fixed positive integers, what probability distributions on {1, …, m}^{2} can be written as the distribution of (f(X_{1}, …, X_{k}, W), g(Y_{1}, …, Y_{k}, Z)), where f, g: ℝ^{k+1} → {1, …, m}? Here W, Z are uniform random variables on [0, 1] independent of each other and independent of X_{1}, …, X_{k}, Y_{1}, …, Y_{k}, representing any private (independent) randomness that players A and B each have.

If we interpret the independent randomness of W, Z as giving random choices among values of f, g, we can equivalently remove the W, Z and just enlarge the range of f, g from {1, …, m} to the simplex with m vertices. (Recall that any element of the simplex Δ_{m} := {(z_{1}, …, z_{m}) ∈ ℝ^{m}: z_{i} ≥ 0 ∀ 1 ≤ i ≤ m, ∑_{i=1}^{m} z_{i} = 1} can be interpreted as a probability distribution on {1, …, m}. So, given f: ℝ^{k} → Δ_{m}, then we can associate to f some f̃: ℝ^{k+1} → {1, …, m} such that for any x_{1}, …, x_{k} ∈ ℝ^{k} f̃(x_{1}, …, x_{k}, W) is a random variable on {1, …, m} whose distribution is equal to f(x_{1}, …, x_{k}), which is a distribution induced on the standard basis {e_{1}, …, e_{m}} ⊆ ℝ^{m}. Conversely, if f̃: ℝ^{k+1} → {1, …, m} is given, then define f: ℝ^{k} → Δ_{m} so that f(x_{1}, …, x_{k}) is equal to the distribution of f̃(x_{1}, …, x_{k}, W) on {1, …, m}.)

We therefore arrive at the formulation of the noninteractive simulation problem we will use most often below: if k, m are fixed positive integers, what probability distributions on {1, …, m}^{2} can be written as the expected value of the matrix

[f(X_{1}, …, X_{k})_{i}g(Y_{1}, …, Y_{k})_{j}]_{1≤i,j≤m},

where f, g: ℝ^{k} → Δ_{m}?

Applications of the noninteractive simulation problem include: cryptography, design of error-correcting codes [?, ?], and design of autonomous agents [?]. For example, an autonomous drone delivering a package might have to make decisions, using randomness, without consulting its dispatcher, due to a nonexistent cell-phone signal.

Generally speaking, noninteractive simulation asks how much “correlation information” between two random variables can be transferred to another pair of random variables. Let f, g: ℝ^{k} → Δ_{m} and let 𝔼 denote the expected value of a random variable. At one extreme, if X, Y are independent, then 𝔼f(X_{1}, …, X_{k})_{i}g(Y_{1}, …, Y_{k})_{j} = 𝔼f(X_{1}, …, X_{k})_{i}𝔼g(Y_{1}, …, Y_{k})_{j} for all 1 ≤ i, j ≤ m, i.e. one can only noninteractively simulate product distributions using a source of independent random variables X, Y. At the other extreme, if X = Y, i.e. X and Y are perfectly correlated, and if there exist x, x′ ∈ ℝ, x ≠ x′ with ℙ(X = x) > 0, ℙ(X = x′) > 0, then we can noninteractively simulate non-product distributions supported on two diagonal points. For example, define f, g: ℝ^{2} → Δ_{2} by

f(X_{1}, X_{2}) = g(X_{1}, X_{2}) := (1_{{X_{1}=x}} , 1_{{X_{1}≠x}}).

Then

𝔼f(X_{1}, X_{2})_{i}g(Y_{1}, Y_{2})_{j} = \begin{cases}ℙ(X_{1} = x) & , if i = j = 1 \\ ℙ(X_{1} ≠ x) & , if i = j = 2 \\ 0 & , otherwise. \end{cases}

Evidently, this probability distribution on {1, 2}^{2} is not a product distribution.

In between these two extremes (independence of X and Y versus perfectly correlated X = Y), one would like to have some notion of the “correlation amount” of random variables, and then deduce what distributions can or cannot be noninteractively simulated from a specific distribution (X, Y).

Various notions of “correlation amount” between two random variables (such as mutual information, common information, etc.) attempt to express the intrinsic amount of correlation that two random variables have. Note that the covariance of two random variables is not an “intrinsic” notion of their “amount of correlation” since applying a function to the random variables (such as multiplying one of them by −1) might increase their covariance. Apparently introduced to the subject by Witsenhausen [?], one useful notion of amount of correlation of real-valued random variables X, Y is the Hirschfeld-Gebelein-Rényi maximal correlation [?, ?, ?], defined to be

ρ_{M}(X, Y) := sup_{ϕ,ψ: ℝ→ℝ measurable : 𝔼ϕ(X)=0, 𝔼(ϕ(X))^{2}=1, 𝔼ψ(Y)=0, 𝔼(ψ(Y))^{2}=1} 𝔼ϕ(X)ψ(Y).  (1)

(In the case that no function ϕ satisfies 𝔼ϕ(X) = 0 and 𝔼(ϕ(X))^{2} = 1, i.e. when X is constant almost surely, we define ρ_{M}(X, Y) to be zero, and similarly for Y.) As shown in [?], the supremum in the definition of ρ_{M}(X, Y) might not be attained. In particular, it could occur that ρ_{M}(X, Y) = 1 while there do not exist f, g: ℝ → ℝ such that f(X) = g(Y). Nevertheless, in the noninteractive simulation problem, we will typically assume that ρ_{M}(X, Y) < 1.

It is observed e.g. in [?] that noninteractive simulation of (U, V) from (X, Y) is only possible when

ρ_{M}(X, Y) ≥ ρ_{M}(U, V).

That is, noninteractive simulation cannot increase the Hirschfeld-Gebelein-Rényi maximal correlation. For a formal statement of this fact, see Definition 1.1 and Proposition 1.2 below. If X, Y are A-valued random variables, recall that their total variation distance is defined to be

d_{TV}(X, Y) := sup_{D⊆A} |ℙ(X ∈ D) − ℙ(Y ∈ D)| .

Definition 1.1. Let (X, Y) and (U, V) be two pairs of real-valued random variables. We say that (U, V) can be noninteractively simulated from an infinite number of samples of (X, Y) if the following condition holds. Let (X_{1}, Y_{1}), (X_{2}, Y_{2}), … be i.i.d. copies of (X, Y). For any positive integer n, there exist positive integers k_{n}, m_{n}, there exist f_{n}, g_{n}: ℝ^{k_{n}} × {1, …, m_{n}} → ℝ such that, if W_{n}, Z_{n} are uniformly distributed in {1, …, m_{n}}, independent of each other, and independent of (X_{1}, Y_{1}), …, (X_{k_{n}}, Y_{k_{n}}), and if

U_{n} := f_{n}(X_{1}, …, X_{k_{n}}, W_{n}),  V_{n} := g_{n}(Y_{1}, …, Y_{k_{n}}, Z_{n}),  ∀ n ≥ 1.

Then

lim_{n→∞} d_{TV}((U, V), (U_{n}, V_{n})) = 0.

Proposition 1.2 ([?, Observation 1]). If (U, V) can be noninteractively simulated from an infinite number of samples of (X, Y), then

ρ_{M}(X, Y) ≥ ρ_{M}(U, V).

(See also [?, Observation 2] for an analogue of Proposition 1.2 with hypercontractivity constants in place of the Hirschfeld-Gebelein-Rényi maximal correlation.)

Our main problem of interest is the following.

Problem 1.3 (Noninteractive Simulation Problem). Determine which real-valued pair of random variables (U, V) can be noninteractively simulated from an infinite number of samples of a given pair of real-valued random variables (X, Y).

Despite results such as Proposition 1.2, the noninteractive simulation problem can be difficult to solve even in very simple cases [?, ?, ?, ?, ?, ?]. For example, if (X, Y) is uniform on the set of three points {(0, 0), (0, 1), (1, 0)} ⊆ ℝ^{2}, then it is an open problem if a pair (U, V) of uniform {−1, 1}-valued random variables with correlation .49 can be noninteractively simulated by sampling from (X, Y) [?, ?]. (Note that ρ_{M}(U, V) = .49 while ρ_{M}(X, Y) = 1/2, using 𝔼X = 𝔼Y = 1/3 and 𝔼(\sqrt{9/2}(X − 1/3))^{2} = 1, 𝔼(\sqrt{9/2}(X − 1/3))(\sqrt{9/2}(Y − 1/3)) = 1/2, so Proposition 1.2 does not exclude the possibility that (X, Y) can noninteractively simulate (U, V).)

The case that (X, Y) ∈ ℝ × ℝ is a ρ-correlated standard Gaussian for some −1 < ρ < 1 has been studied extensively [?, ?, ?], and we will focus on this case of the noninteractive simulation problem. (That is, 𝔼X = 𝔼Y = 0, 𝔼X^{2} = 𝔼Y^{2} = 1 and 𝔼XY = ρ ∈ (−1, 1).)

When (X, Y) are ρ-correlated standard Gaussians, it follows from Hermite-Fourier analysis that ρ_{M}(X, Y) = |ρ|. So, if (U, V) is a pair of real-valued random variables such that |ρ| < ρ_{M}(U, V) ≤ 1, then (U, V) cannot be noninteractively simulated from (X, Y) by Proposition 1.2. This fact gives many examples of (U, V) that cannot be noninteractively simulated from (X, Y), but it still does not indicate exactly what distributions can be noninteractively simulated by correlated Gaussians. In principle, one could find what (U, V) could be noninteractively simulated from correlated Gaussians using the algorithms of [?, ?, ?], but such algorithms seem quite inefficient. On the other hand, the main result of the current paper improves on the efficiency (i.e. run time) of those algorithms.

A basic question considered, but not resolved, in [?, ?, ?] is: if the players want to simulate a correlated distribution on {1, …, m}^{2} where m > 0 is a fixed integer, is there a certain number k of samples (X_{1}, Y_{1}), …, (X_{k}, Y_{k}) such that, taking more than k samples does not change the set of distributions that can be noninteractively simulated from (X, Y)? Put another way, does the “expressive power” of sampling from correlated Gaussians strictly increase with the number k of samples used in the noninteractive simulation problem?

The case m = 2 of this problem is well understood [?]. If we fix 0 < a, b < 1, and we only consider f, g: ℝ → Δ_{2} such that 𝔼f(X) = (a, 1 − a) and 𝔼g(Y) = (b, 1 − b), then the matrix (𝔼f(X)_{i}g(Y)_{j})_{1≤i,j≤2} has only one free parameter since f_{2} = 1 − f_{1} and g_{2} = 1 − g_{1}. Let Φ(t) := ∫_{−∞}^{t} e^{−s^{2}/2}ds/\sqrt{2π} for all t ∈ ℝ. From Borell’s Inequality [?], for any 0 < ρ < 1 we have

𝔼1_{−[−∞,Φ^{−1}(a))}(X)1_{[−∞,Φ^{−1}(b))}(Y) ≤ 𝔼f(X)_{1}g(Y)_{1} ≤ 𝔼1_{[−∞,Φ^{−1}(a))}(X)1_{[−∞,Φ^{−1}(b))}(Y).

So, the set of all probability distributions on {1, 2}^{2} that can be noninteractively simulated from a pair (X, Y) of standard ρ-correlated Gaussians can be written as the set of matrices of the form

(\begin{matrix}c & a − c \\ b − c & 1 − a − b + c \end{matrix}) ,

where and 0 ≤ a, b ≤ 1 are arbitrary and

𝔼1_{−[−∞,Φ^{−1}(a))}(X)1_{[−∞,Φ^{−1}(b))}(Y) ≤ c ≤ 𝔼1_{[−∞,Φ^{−1}(a))}(X)1_{[−∞,Φ^{−1}(b))}(Y).

Moreover, one sample from (X, Y) suffices to simulate such a distribution. Similarly, when −1 < ρ < 0, Borell’s inequality reverses compared to before:

𝔼1_{−[−∞,Φ^{−1}(a))}(X)1_{[−∞,Φ^{−1}(b))}(Y) ≥ 𝔼f(X)_{1}g(Y)_{1} ≥ 𝔼1_{[−∞,Φ^{−1}(a))}(X)1_{[−∞,Φ^{−1}(b))}(Y).

So, the set of all probability distributions on {1, 2}^{2} that can be noninteractively simulated from a pair (X, Y) of standard ρ-correlated Gaussians can be written as the set of matrices of the form

(\begin{matrix}c & a − c \\ b − c & 1 − a − b + c \end{matrix}) ,

where and 0 ≤ a, b ≤ 1 are arbitrary and

𝔼1_{−[−∞,Φ^{−1}(a))}(X)1_{[−∞,Φ^{−1}(b))}(Y) ≥ c ≥ 𝔼1_{[−∞,Φ^{−1}(a))}(X)1_{[−∞,Φ^{−1}(b))}(Y).

Unfortunately, determining which probability distributions on {1, …, m}^{2} can be noninteractively simulated from correlated Gaussians is much more difficult when m > 2. In particular, it was not known whether a finite or an infinite number of samples was needed to noninteractively simulate anything that could be noninteractively simulated from correlated Gaussians. When X, Y are standard Gaussians with fixed correlation ρ ∈ (−1, 1), it was shown in [?, ?] and [?] that a large number of samples closely approximates the noninteractive simulation ability of an infinite number of samples. Moreover, the number of samples required to decide whether or not a target distribution is ε-close to being noninteractively simulatable from (X, Y) is bounded by exp(poly(m, \frac{1}{1−ρ}, ε)) [?, Theorem 1.4]. We cannot find a run time bound in [?] for the associated algorithm, but presumably it would be at least as large as exp exp(poly(m, \frac{1}{1−ρ}, \frac{1}{ε})).

In this work, we show that the set of distributions on {1, …, m}^{2} that can be noninteractively simulated from k Gaussian samples is the same for any k ≥ m^{2} − 1. That is, m^{2} −1 samples suffices to exhaust the noninteractive simulation ability of ρ-correlated Gaussians (see Corollary 1.10). As a corollary, the run time required to decide whether or not a target distribution is ε-close to being noninteractively simulatable from (X, Y) is at most (1 + 4/ε)^{m(log(ε/2)/ log|ρ|)^{m^{2}−1}}, as shown in Section 1.4.1.

(In order to obtain the statement in the abstract for m^{2} samples in place of m^{2} − 1, we use one additional sample to randomize the outcome, i.e. to express f, g: ℝ^{k} → Δ_{m} as an average of f̃, g̃: ℝ^{k} → {e_{1}, …, e_{m}}.)

As shown in [?, ?], the case that (X, Y) are correlated Gaussians implies a similar result for distributions (X, Y) ∈ {1, …, p}^{2} for arbitrary p ≥ 1. A nonlinear central limit theorem (i.e. invariance principle) implies that the noninteractive simulation problem can be solved for arbitrary finite discrete sources with a run time that does not depend on the dimension k. The run time required to decide whether or not a target distribution is ε-close to being noninteractively simulatable from (X, Y) is at most

(5/ε)^{mp^{(100·2^{m}/ε) \frac{3600m log(m/ε) log(1/α)}{(1−ρ)ε}}} ,

where ρ < 1 is the Herschfeld-Gebelein-Rényi maximal entropy of (X, Y), and α is the smallest nonzero probability that (X, Y) takes a particular value. For the formal statement, see Theorem 1.12. In contrast, the run time of the algorithm of [?, Theorem 1.6] is implicitly stated as exp exp exp(poly(m, \frac{1}{1−ρ}, \frac{1}{ε}, log \frac{1}{α})), though it is mentioned that this bound could be made explicit.

1.1. More Detailed Introduction. Unless otherwise stated, all functions and sets considered in this paper are measurable. Define

⟨x, y⟩ := ∑_{i=1}^{n+1} x_{i}y_{i}, ∀ x = (x_{1}, …, x_{n+1}), y = (y_{1}, …, y_{n+1}) ∈ ℝ^{n+1}.

∥x∥ := ⟨x, x⟩^{1/2}, ∀ x ∈ ℝ^{n+1}.
γ_{n+1}(x) := (2π)^{−(n+1)/2} exp(− ∥x∥^{2} /2), ∀ x ∈ ℝ^{n+1}.

Δ_{m} := {a = (a_{1}, …, a_{m}) ∈ ℝ^{m}: ∑_{i=1}^{m} a_{i} = 1, ∀ 1 ≤ i ≤ m, a_{i} ≥ 0}.  (2)

For any f: ℝ^{n+1} → Δ_{m}, we denote the components of f as f = (f_{1}, …, f_{m}), so that f_{i}(x) = ⟨f(x), e_{i}⟩, ∀ x ∈ ℝ^{n+1} and ∀ 1 ≤ i ≤ m, where e_{i} ∈ ℝ^{n+1} is a vector with a 1 in its i^{th} entry and zeros in its other entries.

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

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

If X is a real-valued standard Gaussian random variable, it is well-known that (X, T_{ρ}(X)) is a pair of ρ-correlated standard Gaussians, and we will use this fact freely throughout the paper. The noise stability of Ω ⊆ ℝ^{n+1} with correlation ρ ∈ (−1, 1) is ℙ((X, Y) ∈ Ω×Ω) = ∫_{ℝ^{n+1}} 1_{Ω}(x)T_{ρ}1_{Ω}(x)γ_{n+1}(x) dx.

For any measurable f, g: ℝ^{n+1} → Δ_{m}, define C_{ρ}(f, g) ∈ ℝ^{m×m} such that

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

Definition 1.4 (Simulatable Probability Distribution Matrices). Let ρ ∈ (−1, 1). Let m ≥ 3. Define the set of discrete probability distributions on {1, …, m}^{2} from ρ-correlated Gaussian sources of dimension n + 1 to be

S_{ρ,m}(n + 1) := {C_{ρ}(f, g) ∈ ℝ^{m×m}: f, g: ℝ^{n+1} → Δ_{m}}.  (5)

The following special case of Problem 1.3 asks if a finite number of samples from correlated Gaussians suffices to express the set of probability distributions on {1, …, m}^{2} that can be noninteractively simulated from an arbitrary number of samples.

Problem 1.5 (Non-Interactive Simulation, Gaussian Sources, [?, ?]). Let m ≥ 3. Fix −1 < ρ < 1. How closely does S_{ρ,m}(n + 1) approximate the closure of ∪_{j=1}^{∞}S_{ρ,m}(j)? In particular, is it true that

S_{ρ,m}(n + 1) = \overline{∪_{j=1}^{∞}S_{ρ,m}(j)}

for sufficiently large n?

Below, we refer to the boundary of S_{ρ,m}(n + 1) as the (m^{2} − 2)-dimensional boundary of S_{ρ,m}(n+1), noting that S_{ρ,m}(n+1) is an (m^{2}−1)-dimensional set contained in {(M_{ij})_{1≤i,j≤m} ⊆ ℝ^{m×m}: ∑_{i,j=1}^{m} M_{ij} = 1, M_{ij} ≥ 0, ∀ 1 ≤ i, j ≤ m}.

Definition 1.6 (Simulatable Probability Distribution Matrices, Extreme Points). Let ρ ∈ (−1, 1). Let m ≥ 3. Fix a, b ∈ Δ_{m}. Define the boundary set of extreme points of probability distributions on {1, …, m}^{2} from ρ-correlated Gaussian sources of dimension n + 1 to be

ExtS_{ρ,m}(n + 1) := {C_{ρ}(f, g) ∈ ∂S_{ρ,m}(n + 1): f, g: ℝ^{n+1} → {e_{1}, …, e_{m}} ⊆ Δ_{m}}. (6)

This set is nonempty since for any 1 ≤ i ≤ m, f = g = e_{i} satisfies C_{ρ}(f, g) ∈ ∂S_{ρ,m}(n + 1), since C_{ρ}(f, g) is a matrix of zeros with a single 1 entry.

Since S_{ρ,m}(n+1) is the bilinear image of a convex set, we might say that the set S_{ρ,m}(n+1) is a biconvex set [?, ?]. Since S_{ρ,m}(n + 1) is not convex, we cannot characterize its boundary points as the extrema of linear functionals. (One can show that extrema of linear functions on S_{ρ,m}(n + 1) are the same for all n + 1 ≥ m^{2}, but we will not explicitly show this since it is insufficient to solve Problem 1.5.)

Still, since S_{ρ,m}(n+1) is the bilinear image of a convex set, we can characterize its boundary as the local minima of quadratic functions. We will then show that minima of quadratic functions of noise stability are low-dimensional. We therefore arrive at the following problem.

Problem 1.7 (Quadratic Minimization of Bilinear Noise Stability). Let m ≥ 3. Fix −1 < ρ < 1. Fix D, Z ∈ ℝ^{m×m} such that d_{ij} > 0 for all 1 ≤ i, j ≤ m. Find measurable sets Ω_{1}, … Ω_{m}, Ω′_{1}, … Ω′_{m} ⊆ ℝ^{n+1} with ∪_{i=1}^{m}Ω_{i} = ∪_{i=1}^{m}Ω′_{i} = ℝ^{n+1} that minimize

∑_{i=1}^{m} ∑_{j=1}^{m} d_{ij}( ∫_{ℝ^{n+1}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω′_{j}}(x)γ_{n+1}(x) dx − z_{ij})^{2},

Certain choices of D, Z will lead to a trivial minimum in Problem 1.7. So, we will need to make some extra assumptions on Z in order to get a nontrivial minimum in Problem 1.7. We will return to this point later in Lemma 2.5, since the considerations are a bit technical. The issue here is analogous to a similar issue for linear functions of the noise stability. For example, since ∑_{i,j=1}^{m} ∫_{ℝ^{n+1}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω′_{j}}(x)γ_{n+1}(x) dx = 1 always holds, if we view the quantity ∑_{i,j=1}^{m} ∫_{ℝ^{n+1}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω′_{j}}(x)γ_{n+1}(x) dx as a linear function of pairs of arbitrary partitions, then all partitions maximize this linear function. But any other linear function of noise stability of the form (7) (with (d_{ij})_{1≤i,j≤m} not all equal) will have nontrivial maximizers. Put another way, there is one particular linear function of noise stability whose optima do not tell us anything interesting. Analogously, there are some quadratic functions of noise stability whose optima do not tell us anything interesting.

1.2. Previous Related Work. In [?], it was shown that linear functions of noise stability of two partitions of the form

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

have maximizers that are low dimensional (i.e. there exist optimal sets of the form: some sets in ℝ^{2m−2} crossed with ℝ^{n−2m+3}), subject to a volume constraint that γ_{n+1}(Ω_{i}) = a_{i}, γ_{n+1}(Ω′_{i}) = b_{i} for all 1 ≤ i ≤ m, where a, b ∈ Δ_{m} are fixed. This result resolved an open problem from [?, ?, ?]. One could call such a result a “dimension reduction.” The same dimension reduction result could also apply to maximizers of more general linear functions of the form

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

where (d_{ij})_{1≤i,j≤m} are arbitrary real constants (that are not all equal), though the proof written in [?] does not incorporate this generality.

It was also shown in [?] that the quadratic function of a single partition

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

has maximizers that are low dimensional, subject to a volume constraint that γ_{n+1}(Ω_{i}) = a_{i} for all 1 ≤ i ≤ m, where a ∈ Δ_{m} is fixed.

Both of these results used the same calculus of variations strategy. For both results, the key step of the proof is to consider an infinitesimal translation of the optimizing sets. If the partitions are not low-dimensional, then one can obtain a positive second derivative with respect to this infinitesimal translation, contradicting the maximality of the partitions.

In particular, [?] provided the first variational proof of Borell’s inequality, i.e. specifying which sets maximize (8) in the case m = 2. Later, we showed in [?] that this strategy could be extended to prove a robust version of Borell’s inequality, proving some conjectures of Eldan [?]. In that result, we consider noise stability plus a “penalty term,” and we show that if this penalty term is sufficiently small, then the sets maximizing noise stability still maximize the noise stability plus a penalty term.

The strategy of [?, ?] was recently adapted in [?] to the setting of functions taking values in spheres, rather than functions taking values in the simplex.

In this work, we carry this calculus of variations strategy forward for quadratic functions of the noise stability of two partitions, as in Problem 1.7. In this setting, we did not seem to use any special property of quadratic functions in Problem 1.7. Indeed, it could be the case that any local optima of functions of noise stability could be low-dimensional (except in trivial cases, such as maximizing ∑_{i=1}^{m} ∑_{j=1}^{m} ∫_{ℝ^{n+1}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω′_{j}}(x)γ_{n+1}(x) dx, since this quantity is always one for partitions {Ω_{i}}_{i=1}^{m} and {Ω′_{j}}_{j=1}^{m} of ℝ^{n+1}.)

1.3. Outline of the Proof of the Structure Theorem. The proof elaborates upon the strategy of [?], originating in a corresponding argument for the Gaussian surface area from [?, ?, ?, ?]). For didactic purposes, we will postpone a discussion of technical difficulties (such as existence and regularity of a minimizer) to Section 2.1.

Suppose there exist measurable Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} ⊆ ℝ^{n+1} locally minimizing Problem 1.7. Suppose we call the quantity in Problem 1.7

F_{ρ}(Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m}).

A second variation argument (Lemma 4.2 below) implies that, if \overline{X}, \overline{Y} : ℝ^{n+1} → ℝ^{n+1} are vector fields, then there is a particular quadratic form Q_{ρ}: ℝ^{n+1} × ℝ^{n+1} → ℝ such that

\frac{d^{2}}{ds^{2}} |_{s=0}F_{ρ}(Ω_{1} + s\overline{X}(Ω_{1}), …, Ω_{m} + s\overline{X}(Ω_{m}), Ω′_{1} + s\overline{Y} (Ω′_{1}), …, Ω′_{m} + s\overline{Y} (Ω′_{m})) = Q_{ρ}(\overline{X}, \overline{Y}).

The key lemma, Lemma 4.3, shows that when \overline{X} = \overline{Y} = v ∈ ℝ^{n+1} is the constant vector, then we get an eigenfunction of the quadratic form Q with a negative eigenvalue, for any v ∈ V, where V is a linear subspace of codimension m^{2} − 1, unless v is perpendicular to all normal vectors of all boundaries of Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m}. That is, Q_{ρ}(v, v) < 0 when ρ > 0 for all v ∈ V, unless v is perpendicular to all normal vectors of all boundaries of Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m}. (And Q_{ρ}(v, −v) < 0 when ρ < 0.)

1.4. Our Contribution. Our first main Theorem 1.8 shows that if we have a pair of partitions whose image under C_{ρ} is in the boundary of S_{ρ,m}(n + 1), then these sets can be written (in a nontrivial way) as minimizers of Problem 1.7, and these sets are (m^{2} − 1)-dimensional.

Theorem 1.8 (Main Structure Theorem/ Dimension Reduction). Fix −1 < ρ < 1. Let m ≥ 2. Let n > 0 with n + 1 ≥ m^{2} − 1. Let Ω_{1}, … Ω_{m}, Ω′_{1}, … Ω′_{m} ⊆ ℝ^{n+1} be a pair of partitions of ℝ^{n+1}. Assume that C_{ρ}(1_{Ω_{1}}, …, 1_{Ω_{m}}, 1_{Ω′_{1}}, …, 1_{Ω′_{m}}) ∈ ExtS_{ρ,m}(n + 1). Then there exists Z ∈ ℝ^{m×m} such that Ω_{1}, … Ω_{m}, Ω′_{1}, … Ω′_{m} ⊆ ℝ^{n+1} minimizes Problem 1.7 and such that, after rotating the sets Ω_{1}, … Ω_{m}, Ω′_{1}, … Ω′_{m} and applying Lebesgue measure zero changes to these sets, there exist measurable sets Θ_{1}, … Θ_{m}, Θ′_{1}, … Θ′_{m} ⊆ ℝ^{m^{2}−1} such that,

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

Remark 1.9. The case ρ = 0 of Theorem 1.8 is easy, so we always assume ρ ≠ 0 below, unless otherwise stated.

The main corollary below answers Problem 1.5 affirmatively.

Corollary 1.10 (Main Corollary, Gaussian Case). Let −1 < ρ < 1 and let m ≥ 2 be an integer. Then the set of m × m probability distribution matrices from ρ-correlated Gaussian sources of dimension k is the same for any k ≥ m^{2} − 1, i.e.

S_{ρ,m}(m^{2} − 1) = \overline{∪_{j=1}^{∞}S_{ρ,m}(j)}.

Proof. From Theorem 1.8, the boundary extreme points ExtS_{ρ,m}(k) of S_{ρ,m}(k) satisfy

ExtS_{ρ,m}(k) = ExtS_{ρ,m}(m^{2} − 1), ∀ k ≥ m^{2} − 1.

Since S_{ρ,m}(k) is the bilinear image of a convex set, this “low-dimensionality” property extends also to the set of all extreme points, and then the interior of S_{ρ,m}, so that

S_{ρ,m}(k) = S_{ρ,m}(m^{2} − 1), ∀ k ≥ m^{2} − 1.

(We now justify the previous sentence. Since C_{ρ}(·, ·) is a bilinear function, a point in the boundary of S_{ρ,m}(k) that is not an extreme point can be written as a convex combination of points in ExtS_{ρ,m}(k). For example, if C_{ρ}(f_{1}, …) satisfies ℙ(|f_{1}| ∈ {0, 1}) < 1, then we can write C_{ρ}(f_{1}, …) as a convex combination of C_{ρ}(tg_{1}, …) + C_{ρ}((1 − t)g′_{1}, …) = tC_{ρ}(g_{1}, …) + (1 − t)C_{ρ}(g′_{1}, …) for some g_{1}, g′_{1} : ℝ^{k} → {0, 1}.) □

1.4.1. An Efficient Algorithm for Noninteractive Simulation from Gaussian Sources. Corollary 1.10 has an algorithm associated to it, for computing which probability distributions can be noninteractively simulated from correlated Gaussians. Such algorithms have already been implicitly provided in [?, ?, ?] albeit with a dependence on the ambient dimension of the Gaussian random variables. Corollary 1.10 removes this dimension-dependence, thereby improving the run time of these algorithms.

We briefly describe this algorithm. Let ε > 0 with 0 < ε < |ρ|. Let f: ℝ^{n+1} → Δ_{m}. Let {h_{j}}_{j∈ℕ^{n+1}} denote the Hermite polynomials, which are an orthonormal basis of L_{2}(γ_{n+1}) with respect to the inner product (f, g) ↦ ∫_{ℝ^{n+1}} f(x)g(x)γ_{n+1}(x) dx. Consider the map H(f) := (∫_{ℝ^{n+1}} f(x)h_{j}(x)γ_{n+1}(x) dx)_{j∈ℕ^{n+1} : ∥j∥_{1}≤ \frac{log(ε/2)}{log|ρ|}}. Let \{f^{(i)}\} be a maximal ε-separated

set for functions from ℝ^{n+1} to N with respect to the metric ∥H(f)∥_{2}, where N is an ε/2-net for Δ_{m}. Since an ε/2-net for Δ_{m} has size at most (1+4/ε)^{m}, and the dimension of the range of H is at most (log(ε/2)/ log |ρ|)^{n+1}, the set {f^{(i)}} has cardinality at most

(1 + 4/ε)^{m(log(ε/2)/ log|ρ|)^{n+1}}.

Corollary 1.10 says we may assume that n + 1 = m^{2} − 1, so the maximal separated set has cardinality

(1 + 4/ε)^{m(log(ε/2)/ log|ρ|)^{m^{2}−1}},

and this provides a bound on the run time of the algorithm. This run time should be compared with [?, Theorem 1.4], which does not explicitly state a run time bound in this case, but presumably their methods give an implicit run time at least as large as exp exp(poly(m, \frac{1}{1−ρ}, \frac{1}{ε})).

1.4.2. Noninteractive Simulation from Discrete Finite Sources. Theorem 1.8 and Corollary 1.10 concern the noninteractive simulation problem where (X, Y) are correlated Gaussian random variables with correlation ρ ∈ (−1, 1). Let p > 0, p ∈ ℤ. As shown in [?], if (X, Y) are random variables in {1, …, p}^{2}, then Problem 1.3 reduces to the case that (X, Y) are correlated Gaussians in Problem 1.3. (A similar statement was shown in [?], though Theorem 1.8 and Corollary 1.10 do not seem to substantially improve upon the methods of [?].)

Before stating the main noninteractive simulation result, we state the Gap version of Problem 1.3. The problem below decides if (U, V) can be well approximated using a noninteractive simulation with source (X, Y).

Problem 1.11 (Gap Noninteractive Simulation Problem). Let (X, Y) be random variables with values in {1, …, p}^{2}. Let (U, V) be random variables with values in {1, …, m}^{2}. Let (X_{1}, Y_{1}), (X_{2}, Y_{2}), … be i.i.d. copies of (X, Y). Let 0 < ε < 1. Distinguish between the following two cases.

• (Case 1) There exists n > 0 and there exist f, g: {1, …, p}^{n} → Δ_{m} such that

d_{TV}(f(X_{1}, …, X_{n}), g(Y_{1}, …, Y_{n}), (U, V)) < ε.
• (Case 2) For all n > 0 and for all f, g: {1, …, p}^{n} → Δ_{m}, we have
d_{TV}(f(X_{1}, …, X_{n}), g(Y_{1}, …, Y_{n}), (U, V)) > 10ε.

Theorem 1.12 (Improved Dimension-Free Noninteractive Simulation). Let ρ := ρ_{M}(X, Y) using (1) and α := min_{x,y∈{1,...,p}: ℙ((X,Y)=(x,y))≠0} ℙ((X, Y) = (x, y)). Assume ρ < 1 and α > 0. Then there exists an algorithm that solves Problem 1.11 in time

(5/ε)^{mp^{(100·2^{m}/ε) \frac{3600m log(m/ε) log(1/α)}{(1−ρ)ε}}} .

In particular, this algorithm does not depend on the dimension n.

This run time should be compared with [?, Theorem 1.6], which gives a similar bound that is not explicit, although it is remarked in [?] that an explicit bound could be written.

Since the argument of Theorem 1.12 was already shown in [?] on the final page, we briefly describe how our result fits into the argument of [?].

The final page of [?] uses the invariance principle from Section 6 of [?] or [?, Theorem 3.6]. We begin with f, g: {1, …, p}^{n} → Δ_{m}. Corollary 1.10 implies that [?, Theorem 1.5, Theorem 5] hold with n_{0} := m^{2}. (We note a few differences in notation: our {1, …, p} is Z in [?], and our m is k in [?].) In their notation, we then associate f, g with new functions with domain ℝ^{m_{0}} where m_{0} := n_{0}/κ^{2} = m^{2}/κ^{2}, where κ > 0 is an upper bound on the influences of the new functions. Denote ρ := ρ_{M}(X, Y) from (1), and assume that ρ < 1. Lemma 6.2 in [?] says, we may choose

γ := \frac{(1 − ρ)ε}{100m log(m/ε)}  (9)

to get a bound of ε/m in that Lemma. Then the invariance principle [?, Theorem 3.6] requires an influence bound of the form

κ < (\frac{ε}{100 · 2^{m}} )^{\frac{18 log(1/α)}{γ}} ≤^{(9)} (\frac{ε}{100 · 2^{m}} )^{\frac{1800m log(m/ε) log(1/α)}{(1−ρ)ε}} .  (10)

So, the number of variables that suffice for the last page of [?] is

m_{0}/κ^{2} =^{(10)} (100 · 2^{m}/ε)^{\frac{3600m log(m/ε) log(1/α)}{(1−ρ)ε}} .  (11)

We now have two functions f̃, g̃: {1, …, p}^{m_{0}/κ^{2}} → Δ_{m} that closely approximate the original discrete functions f, g in total variation distance. We can then apply a brute-force algorithm similar to that of Section 1.4.1 for f̃, g̃, as mentioned in [?].

Let N be an ε/2-net for Δ_{m} with size at most (1 + 4/ε)^{m}. The set of all functions from {1, …, p}^{m_{0}/κ^{2}} → N then has cardinality at most

(1 + 4/ε)^{mp^{m_{0}/κ^{2}}}.

So, searching over all pairs of functions from {1, …, p}^{m_{0}/κ^{2}} to N solves Problem 1.11 in run time

(1 + 4/ε)^{mp^{m_{0}/κ^{2}}} ≤^{(11)} (5/ε)^{mp^{(100·2^{m}/ε) \frac{3600m log(m/ε) log(1/α)}{(1−ρ)ε}}} .

We emphasize that this run time does not depend on the dimension n.

2. Existence and Regularity

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Below, when appropriate, we let dx denote Lebesgue measure, restricted to a surface Σ ⊆ ℝ^{n+1}. Let F := {f: ℝ^{n+1} → {e_{1}, …, e_{m}} ⊆ Δ_{m}}. Define

L_{2}(γ_{n+1}) := {f: ℝ^{n+1} → ℝ: ∥f∥_{L_{2}(γ_{n+1})} := ∫_{ℝ^{n+1}} |f(x)|^{2} γ_{n+1}(x) dx < ∞}.

Lemma 2.3 (Existence of a Minimizer). Let −1 < ρ < 1 and let m ≥ 2. Let Ω_{1}, … Ω_{m} and Ω′_{1}, … Ω′_{m} be measurable partitions of ℝ^{n+1} such that C_{ρ}(1_{Ω_{1}}, …, 1_{Ω_{m}}, 1_{Ω′_{1}}, …, 1_{Ω′_{m}}) is in the boundary of S_{ρ,m}(n + 1). Then ∃ Z ∈ ℝ^{m×m} with Z ≠ C_{ρ}(1_{Ω_{1}}, …, 1_{Ω_{m}}, 1_{Ω′_{1}}, …, 1_{Ω′_{m}}) such that, Problem 1.7 has a local minimum at Ω_{1}, … Ω_{m}, Ω′_{1}, … Ω′_{m}. That is, there exists a neighborhood U ⊆ F × F of Ω_{1}, … Ω_{m}, Ω′_{1}, … Ω′_{m} with respect to the weak topology of ∏_{i=1}^{2m} L_{2}(γ_{n+1}) such that f_{1} = 1_{Ω_{1}}, …, f_{m} = 1_{Ω_{m}}, g_{1} = 1_{Ω′_{1}}, …, g_{m} = 1_{Ω′_{m}} minimizes

∑_{i=1}^{m} ∑_{j=1}^{m} d_{ij}( ∫_{ℝ^{n+1}} f_{i}(x)T_{ρ}g_{j}(x)γ_{n+1}(x) dx − z_{ij})^{2},

over all (f_{1}, …, f_{m}), (g_{1}, …, g_{m}) ∈ U.

Proof. Let {h_{j}}_{j∈ℕ^{n+1}} denote the Hermite polynomials, which are an orthonormal basis of L_{2}(γ_{n+1}) with respect to the inner product (f, g) ↦ ∫_{ℝ^{n+1}} f(x)g(x)γ_{n+1}(x) dx. For any f, g ∈ F, define a metric

d_{ρ}(f, g) := ( ∑_{j∈ℕ^{n}} |ρ|^{∥j∥^{1}} ( ∫_{ℝ^{n+1}} h_{j}(x)(f(x) − g(x))γ_{n+1}(x) dx)^{2})^{1/2}.

This metric metrizes the weak topology of ∏_{i=1}^{2m} L_{2}(γ_{n+1}) restricted to F × F. Also C_{ρ} is a bilinear function, and it is equal to its second order Taylor series, since for all ε_{1}, ε_{2} : ℝ^{n+1} → {e_{1}, …, e_{m}}, we have

C_{ρ}((f, g) + (ε_{1}, ε_{2})) = C_{ρ}(f, g) + [C_{ρ}(ε_{1}, g) + C_{ρ}(f, ε_{2})] + C_{ρ}(ε_{1}, ε_{2}).  (15)

Moreover, this second order Taylor expansion satisfies, using ∥T\sqrt{|ρ|}h∥_{L_{2}(γ_{n+1})} ≤ ∥h∥_{L_{2}(γ_{n+1})},

∥C_{ρ}(ε_{1}, g)∥_{2} ≤ ∑_{i,j=1}^{m} ∥T\sqrt{|ρ|}ε_{1,i}∥_{L_{2}(γ_{n+1})} ∥T\sqrt{|ρ|}g_{j}∥_{L_{2}(γ_{n+1})} ≤ ∑_{i,j=1}^{m} d_{ρ}(ε_{1,i}, 0).

∥C_{ρ}(f, ε_{2})∥_{2} ≤ ∑_{i,j=1}^{m} ∥T\sqrt{|ρ|}ε_{2,j}∥_{L_{2}(γ_{n+1})} ∥T\sqrt{|ρ|}f_{i}∥_{L_{2}(γ_{n+1})} ≤ ∑_{i,j=1}^{m} d_{ρ}(ε_{2,j}, 0).

∥C_{ρ}(ε_{1}, ε_{2})∥_{2} ≤ ∑_{i,j=1}^{m} ∥T\sqrt{|ρ|}ε_{1,i}∥_{L_{2}(γ_{n+1})} ∥T\sqrt{|ρ|}ε_{2,j}∥_{L_{2}(γ_{n+1})} = ∑_{i,j=1}^{m} d_{ρ}(ε_{1,i}, 0)d_{ρ}(ε_{2,j}, 0).

Here ∥·∥_{2} denotes the matrix ℓ_{2} norm, i.e. the square root of the sum of the squared entries of a matrix.

Since the second order Taylor expansion of C is “compatible” (i.e. continuous) with respect to the metric d_{ρ} in this way, and the quadratic term C_{ρ}(ε_{1}, ε_{2}) satisfies the above uniform bound, we deduce that there exists a neighborhood U of (f, g) in the weak topology of ∏_{i=1}^{2m} L_{2}(γ_{n+1}) restricted to F × F such that C_{ρ}(U) satisfies an exterior ball condition. That is, each matrix M ∈ C_{ρ}(U) ∩ ∂S_{ρ,m}(n + 1) has some Z ≠ M, Z ∈ ℝ^{m×m} such that there exists some radius r > 0 and there exists some closed Euclidean ball B = {N ∈ ℝ^{m×m}: ∥N − Z∥_{2} ≤ r} centered at Z such that B ∩ C_{ρ}(U) = M. It follows that Problem 1.7 for this Z has a local minimum at the partitions Ω_{1}, … Ω_{m}, Ω′_{1}, … Ω′_{m}.

□

Example 2.4. Define u_{ijk} := d_{ki}(s_{ki} − z_{ki}) − d_{kj}(s_{kj} − z_{kj}), where d_{ij}, z_{ij} are defined in Problem 1.7, and s_{ij} := ∫_{ℝ^{n+1}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω′_{j}}(x)γ_{n+1}(x) dx, ∀ 1 ≤ i, j, k ≤ m, and define u′_{ijk} := d_{ik}(s_{ik} − z_{ik}) − d_{jk}(s_{jk} − z_{jk}), ∀ 1 ≤ i, j, k ≤ m.

It is instructive to consider the following example in which Lemma 2.3 has no content. Let f_{1} = ⋯ = f_{m} = g_{1} = ⋯ = g_{m} = 1/m, so that C_{ρ}(f, g)_{ij} = s_{ij} = 1/m^{2} for all 1 ≤ i, j ≤ m and for all ρ ∈ (−1, 1). Then let z_{ij} := 2s_{ij} for all 1 ≤ i, j ≤ m, d_{ij} := 1 for all 1 ≤ i, j ≤ m. Then u_{ijk} = 0 for all 1 ≤ i, j, k ≤ m, and the first variation argument in (16) below has no content, i.e. the regularity Lemma 2.5 and the first variation condition in Lemma 3.2 do not hold. In fact, any element (s_{ij})_{1≤i,j≤m} of S_{ρ,m}(n + 1) can be written as a quadratic minimization in Problem 1.7, with z_{ij} := s_{ij} + 1 for all 1 ≤ i, j ≤ m.

If u_{ijk} = 0 for all 1 ≤ i, j, k ≤ m as in this example, then the following Lemma 2.5 cannot hold. Indeed, we should not expect arbitrary measurable partitions to have any regularity. It is then an important technical issue to rule out the case that u_{ijk} = 0 for all 1 ≤ i, j, k ≤ m. If s_{ij} − z_{ij} is nonconstant for all 1 ≤ i, j ≤ m, then we can rule out this situation, though this issue adds an extra layer of complication to the proof of Lemma 2.5.

Lemma 2.5 (Regularity of a Minimizer). There exists a set Λ in the boundary of S_{ρ,m}(n+ 1) such that Λ has measure zero in ExtS_{ρ,m}(n + 1), and such that the following holds. Let Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} ⊆ ℝ^{n+1} be measurable partitions that locally minimize Problem 1.7, such that C_{ρ}(1_{Ω_{1}}, …, 1_{Ω_{m}}, 1_{Ω′_{1}}, …, 1_{Ω′_{m}}) is in ∂S_{ρ,m}(n+1)\Λ and such that {s_{ij} −z_{ij}}_{1≤i,j≤m} are not all equal. Then Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} have locally finite surface area. Moreover, for all 1 ≤ i ≤ m and for all x ∈ ∂Ω_{i} (or for all x ∈ ∂Ω′_{i}), there exists a neighborhood U ⊆ ℝ^{n+1} of x such that U ∩ ∂Ω_{i} (or U ∩ ∂Ω′_{i}) is a finite union of C^{∞} n-dimensional manifolds with boundary.

Proof. Step 1. We begin with some a priori statements about the partitions. Since C_{ρ}(1_{Ω_{1}}, …, 1_{Ω_{m}}, 1_{Ω′_{1}}, …, 1_{Ω′_{m}}) is in the boundary of S_{ρ,m}(n+1), there exists c, t ∈ ℝ and there exists some matrix R ∈ ℝ^{m×m} (a “normal” vector/matrix) that is normal to the all ones matrix, so that ∑_{i,j=1}^{m} r_{ij} = 0, R ≠ 0, and such that, if ε > 0 is given, then every f, g ∈ F with d_{ρ}(f, (1_{Ω_{1}}, …, 1_{Ω_{m}})) < ε and d_{ρ}(g, (1_{Ω′_{1}}, …, 1_{Ω′_{m}})) < ε satisfies | ∑_{i,j=1}^{m} R_{ij}[C_{ρ}(f, g)]_{ij}| ≤ cε^{2}. This matrix R exists by (15).

Note now that we could use R := S − Z ≠ 0 in Problem 1.7 (recall that we choose Z ≠ S, otherwise Problem 1.7 becomes trivial since the sum is automatically zero), so the equation ∑_{i,j=1}^{m} r_{ij} = 0 implies that there exists some 1 ≤ i, j, k ≤ m such that r_{ik} − r_{jk} ≠ 0. Define u_{ijk} := d_{ki}(s_{ki} − z_{ki}) − d_{kj}(s_{kj} − z_{kj}), where d_{ij}, z_{ij} are defined in Problem 1.7, and s_{ij} := ∫_{ℝ^{n+1}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω′_{j}}(x)γ_{n+1}(x) dx, ∀ 1 ≤ i, j, k ≤ m, and define u′_{ijk} := d_{ik}(s_{ik} − z_{ik}) − d_{jk}(s_{jk} − z_{jk}), ∀ 1 ≤ i, j, k ≤ m. We will particularly use d_{ij} := 1 for all 1 ≤ i, j ≤ m.

We have shown that u′_{ijk} ≠ 0 for some 1 ≤ i, j, k ≤ m. Note that u′_{ijk} = u′_{iℓk} + u′_{ℓjk} = u′_{iℓk} − u′_{jℓk}, for all 1 ≤ ℓ ≤ m, so either u′_{iℓk} or u′_{jℓk} are nonzero, for all 1 ≤ ℓ ≤ m. In summary, there exists some 1 ≤ i, k ≤ m such that u′_{ijk} ≠ 0 for all 1 ≤ j ≤ m. (We mention in passing that we can similarly deduce that: there exists some 1 ≤ v, w ≤ m such that u_{vjw} ≠ 0 for all 1 ≤ j ≤ m.)

Step 2. From Step 1, fix 1 ≤ i, k ≤ m such that u_{ijk} ≠ 0 for all 1 ≤ j ≤ m. We now claim that there exist constants (c_{ij})_{1≤j≤m} such that

Ω′_{i} ⊇ {x ∈ ℝ^{n+1} : T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x) > c_{ij}, ∀ j ∈ {1, …, m} \ {i}},  (16)

Similarly, ∃ (c′_{ij})_{1≤i<j≤m} such that

Ω_{v} ⊇ {x ∈ ℝ^{n+1} : T_{ρ}( ∑_{k=1}^{m} u′_{vjk}1_{Ω′_{k}})(x) > c′_{ij}, ∀ j ∈ {1, …, m} \ {i}},  (17)

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

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

T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(y) < c, T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(z) > c.

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

T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(y′) < c, ∀ y′ ∈ U_{i},  T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(y′) > c, ∀ y′ ∈ U_{j}. (18)

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

∑_{i=1}^{m} ∑_{j=1}^{m} d_{ij}( ∫_{ℝ^{n+1}} 1_{Ω_{i}}(x)T_{ρ}1Ω̃′_{j}(x)γ_{n+1}(x) dx − z_{ij})^{2}

− ∑_{i=1}^{m} ∑_{j=1}^{m} d_{ij}( ∫_{ℝ^{n+1}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω′_{j}}(x)γ_{n+1}(x) dx − z_{ij})^{2}

= ∑_{k=1}^{m} d_{ki}( ∫_{ℝ^{n+1}} 1_{Ω_{k}}(x)T_{ρ}1Ω̃′_{i}(x)γ_{n+1}(x) dx − z_{ki})^{2}

+ ∑_{k=1}^{m} d_{kj}( ∫_{ℝ^{n+1}} 1_{Ω_{k}}(x)T_{ρ}1Ω̃′_{j}(x)γ_{n+1}(x) dx − z_{kj})^{2}

− ∑_{k=1}^{m} d_{ki}( ∫_{ℝ^{n+1}} 1_{Ω_{k}}(x)T_{ρ}1_{Ω′_{i}}(x)γ_{n+1}(x) dx − z_{ki})^{2}

− ∑_{k=1}^{m} d_{kj}( ∫_{ℝ^{n+1}} 1_{Ω_{k}}(x)T_{ρ}1_{Ω′_{j}}(x)γ_{n+1}(x) dx − z_{kj})^{2}.

Substituting the definitions of the sets Ω̃′_{i} gives

∑_{k=1}^{m} d_{ki}( ∫_{ℝ^{n+1}} 1_{Ω_{k}}(x)T_{ρ}[1_{Ω′_{i}} + 1_{U_{j}} − 1_{U_{i}}](x)γ_{n+1}(x) dx − z_{ki})^{2}

+ ∑_{k=1}^{m} d_{kj}( ∫_{ℝ^{n+1}} 1_{Ω_{k}}(x)T_{ρ}[1_{Ω′_{j}} + 1_{U_{i}} − 1_{U_{j}}](x)γ_{n+1}(x) dx − z_{kj})^{2}

− ∑_{k=1}^{m} d_{ki}( ∫_{ℝ^{n+1}} 1_{Ω_{k}}(x)T_{ρ}(1_{Ω′_{i}})(x)γ_{n+1}(x) dx − z_{ki})^{2}

− ∑_{k=1}^{m} d_{kj}( ∫_{ℝ^{n+1}} 1_{Ω_{k}}(x)T_{ρ}(1_{Ω′_{j}})(x)γ_{n+1}(x) dx − z_{kj})^{2}.

Cancelling some terms yields

∑_{k=1}^{m} d_{ki}2(s_{ki} − z_{ki})( ∫_{ℝ^{n+1}} 1_{Ω_{k}}(x)T_{ρ}[1_{U_{j}} − 1_{U_{i}}](x)γ_{n+1}(x) dx)

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

+ ∑_{k=1}^{m} d_{kj}2(s_{kj} − z_{kj})( ∫_{ℝ^{n+1}} 1_{Ω_{k}}(x)T_{ρ}[1_{U_{i}} − 1_{U_{j}}](x)γ_{n+1}(x) dx)

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

Rearranging gives

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

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

Moving the sum inside the first integral, we get

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

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

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

Choosing U_{i}, U_{j} smaller if necessary, the first term is nonzero by (18) and it dominates the other two terms, contradicting the minimality of the sets. We conclude that (16) holds. (We also repeat the above argument with Ω_{1}, …, Ω_{m} interchanged with Ω′_{1}, …, Ω′_{m}.)

Step 3. We retain 1 ≤ i, k ≤ m chosen from Step 1. We then fix 1 ≤ i < j ≤ m and we upgrade (16) by examining the level sets of

T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x),  ∀ x ∈ ℝ^{n+1}.  (19)

We will for now assume that γ_{n+1}(Ω_{i}) > 0 and γ_{n+1}(Ω′_{i}) > 0 for all 1 ≤ i ≤ m. Recall that, as shown in Step 2, the i, k from Step 1 satisfies u_{ijk} ≠ 0 for all 1 ≤ j ≤ m, so the quantity (19) is nonconstant in x since γ_{n+1}(Ω_{i}) > 0 and γ_{n+1}(Ω′_{i}) > 0 for all 1 ≤ i ≤ m.

For simplicity of notation we now denote u_{k} := u_{ijk} for all 1 ≤ k ≤ m. Fix c ∈ ℝ and consider the level set

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

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

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

U ∩ Σ = ∪_{p=1}^{ℓ}{y ∈ U: D^{p}( ∑_{ℓ=1}^{m} u_{ℓ}1_{Ω_{ℓ}})(x) ≠ 0, D^{q}T_{ρ}( ∑_{ℓ=1}^{m} u_{ℓ}1_{Ω_{ℓ}})(x) = 0, ∀ 1 ≤ q ≤ p − 1}.

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

∂Ω′_{i} ∩ ∂Ω′_{j} ⊆ {x ∈ ℝ^{n+1} : T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x) = c_{ij}},  ∀ j ∈ {1, …, m} \ {i}, (20)

and the Lemma follows for the set Ω′_{i}. (By repeating all above steps, the Lemma also holds for Ω_{j} for some 1 ≤ j ≤ m.)

Step 4. The Lemma holds for a single set Ω′_{i} and for another set Ω_{j}. It remains to extend the conclusion of the Lemma for all sets Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m}. Let v, w ∈ {1, …, m} with v ≠ i and w ≠ j such that ∂Ω_{i} ∩ ∂Ω_{v} contains an open set in an n-dimensional C^{∞} manifold and such that ∂Ω′_{j} ∩ ∂Ω′_{w} contains an open set in an n-dimensional C^{∞} manifold.

A priori, it could occur that u_{ivk} = 0 and u′_{jwk} = 0 for all 1 ≤ k ≤ m, in which case the argument from Steps 2 and 3 does not work when we replace Ω′_{j} with Ω′_{w}, or we replace Ω_{i} with Ω_{v}. However, by perturbing Ω_{i} into Ω_{v}, or perturbing Ω′_{j} into Ω′_{w}, and viewing the resulting image under C_{ρ} while keeping the other sets fixed, we see there exists a neighborhood U of C_{ρ}(1_{Ω_{1}}, …, 1_{Ω_{m}}, 1_{Ω′_{1}}, …, 1_{Ω′_{m}}) such that either a = b = m^{2} − 2 or a > b, where:

• We let a be the dimension of the set of matrices in ExtS_{ρ,m}(n + 1) where there exists a pair of partitions Θ_{1}, …, Θ_{m}, Θ′_{1}, …, Θ′_{m} of ℝ^{n+1} such that u_{ivk} ≠ 0 or u′_{jwk} ≠ 0, and

• Let b be the dimension of the set of matrices in ExtS_{ρ,m}(n+1) such that, for all pairs of partitions Θ_{1}, …, Θ_{m}, Θ′_{1}, …, Θ′_{m} of ℝ^{n+1}, we have u_{ivk} = 0 and u′_{jwk} = 0.

That is, except for a set of measure zero in ExtS_{ρ,m}(n + 1), we can then apply Steps 2 and 3 to either Ω_{v} or Ω′_{w}. Iterating this process one set at a time, we conclude that the Lemma holds for all of the sets Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m}, except for a set of measure zero in the boundary of S_{ρ,m}(n + 1).

(Note that perturbing e.g. Ω_{i} into Ω_{v} maintains the condition of being in ExtS_{ρ,m}(n + 1) since C_{ρ} is a bilinear function, i.e. it satisfies (15).)

(Note also that S_{ρ,m}(n + 1) has Hausdorff dimension m^{2} − 1 since it is a subset of ℝ^{m×m} satisfying a single linear equality, and the boundary of S_{ρ,m}(n + 1) has Hausdorff dimension m^{2} − 2.)

We prove the above claim below. Without loss of generality, by relabeling the sets, suppose i = 1, v = 2 and j = 1, w = 2. Suppose we perturb Ω_{1} into Ω_{2}, resulting in a new partition Ω̃_{1}, Ω̃_{2}, Ω_{3}, …, Ω_{m}. Then the change under the image of C_{ρ} is of the form

C_{ρ}(1_{Ω_{1}}, …, 1_{Ω_{m}}, 1_{Ω′_{1}}, …, 1_{Ω′_{m}}) −C_{ρ}(1Ω̃_{1}, 1Ω̃_{2}, 1_{Ω_{3}}, …, 1_{Ω_{m}}, 1_{Ω′_{1}}, …, 1_{Ω′_{m}}) = (\begin{matrix}a_{1} & a_{2} & ⋯ & a_{m} \\ −a_{1} & −a_{2} & ⋯ & −a_{m} \\ 0 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ⋯ & ⋮ \\ 0 & 0 & ⋯ & 0 \end{matrix}) .

for some a_{1}, …, a_{m} ∈ ℝ with a_{1} ≠ 0. Moreover, if we choose the perturbation to be localized in an ε-neighborhood of a point x ∈ ∂Ω_{1} ∩ ∂Ω_{2} ≠ ∅, then we have

C_{ρ}(1_{Ω_{1}}, …, 1_{Ω_{m}}, 1_{Ω′_{1}}, …, 1_{Ω′_{m}}) − C_{ρ}(1Ω̃_{1}, 1Ω̃_{2}, 1_{Ω_{3}}, …, 1_{Ω_{m}}, 1_{Ω′_{1}}, …, 1_{Ω′_{m}})

= ε (\begin{matrix}T_{ρ}1_{Ω′_{1}}(x) & T_{ρ}1_{Ω′_{2}}(x) & ⋯ & T_{ρ}1_{Ω′_{m}}(x) \\ −T_{ρ}1_{Ω′_{1}}(x) & −T_{ρ}1_{Ω′_{2}}(x) & ⋯ & −T_{ρ}1_{Ω′_{m}}(x) \\ 0 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ⋯ & ⋮ \\ 0 & 0 & ⋯ & 0 \end{matrix}) + O(ε^{2}).

Recall that R ∈ ℝ^{m×m} is the normal vector in the sense that ∑_{i,j=1}^{m} r_{ij}C_{ρ}(1_{Ω_{1}}, …, 1_{Ω_{m}})_{ij} = 0 and R ≠ 0. We now consider some constraints on what the normal vector R can be, by finding some vectors perpendicular to R, i.e. in the tangent space Tan_{ρ} of S_{ρ,m}(n + 1) at C_{ρ}(1_{Ω_{1}}, …, 1_{Ω_{m}}). Letting ε → 0 in the above expression and using the definition of R, we have

0 = ∑_{i,j=1}^{m} r_{ij}[C_{ρ}(1_{Ω_{1}}, …, 1_{Ω_{m}}) − C_{ρ}(1Ω̃_{1}, 1Ω̃_{2}, 1_{Ω_{3}}, …, 1_{Ω_{m}}, 1_{Ω′_{1}}, …, 1_{Ω′_{m}})]_{ij}

= ∑_{j=1}^{m}[r_{1j} − r_{2j}]T_{ρ}1_{Ω′_{j}}(x).

(21)

Similarly, perturbing Ω_{1} into Ω_{2} and Ω′_{1} into Ω′_{2} simultaneously and using bilinearity of C_{ρ} as in (15),

0 = ∑_{i,j=1}^{m} r_{ij}[C_{ρ}(1_{Ω_{1}}, …, 1_{Ω_{m}}) − C_{ρ}(1Ω̃_{1}, 1Ω̃_{2}, 1_{Ω_{3}}, …, 1_{Ω_{m}}, 1Ω̃′_{1}, 1Ω̃′_{2}, 1_{Ω′_{3}}, …, 1_{Ω′_{m}})]_{ij}
= r_{11} + r_{22} − r_{12} − r_{21}.

(22)

Note: perturbing two sets as in (22) might exit the tangent space Tan_{ρ} by (15), since there is a second order (quadratic) term in (15). So (22) only holds in the case that Tan_{ρ} remains unchanged by perturbing Ω_{1} into Ω_{2} and Ω′_{1} into Ω′_{2}.

We wish to extend these observations to the other sets as well. The boundary between two of the sets might not be a piecewise smooth manifold, but we can still use the same construction above using points of density of the sets. By the Lebesgue density theorem [?, 1.2.1, Proposition 1], by making measure zero changes to the sets, we may assume that, if y ∈ Ω_{i}, then we have lim_{r→0} γ_{n+1}(Ω_{i} ∩ B(y, r))/γ_{n+1}(B(y, r)) = 1, for all 1 ≤ i ≤ m, and similarly for Ω′_{1}, …, Ω′_{m}. Suppose s > 0 and 1 ≤ i < v ≤ m satisfy

inf_{x∈Ω_{i},y∈Ω_{v}: ∥x∥,∥y∥≤s} ∥x − y∥ = 0.

(If this infimum is nonzero for all s > 0, then Ω_{i} and Ω_{v} have no common boundary.) Let x_{1}, x_{2}, … ∈ Ω_{i} and y_{1}, y_{2}, …, ∈ Ω_{v} such that ∥x_{k}∥ , ∥y_{k}∥ ≤ s ∀ k ≥ 1, lim_{k→∞} ∥x_{k} − y_{k}∥ = 0, and s_{1}, s_{2}, … > 0 with lim_{k→∞} s_{k} = 0 such that

lim_{k→∞} \frac{γ_{n+1}(Ω_{i} ∩ B(x_{k}, s_{k}))}{γ_{n+1}(B(x_{k}, s_{k}))} = lim_{k→∞} \frac{γ_{n+1}(Ω_{v} ∩ B(x_{k}, s_{k})))}{γ_{n+1}(B(y_{k}, s_{k}))} = 1.

Then we can use the sequence of balls {B(x_{k}, s_{k})}_{k=1}^{∞}, {B(y_{k}, s_{k})}_{k=1}^{∞} to perturb Ω_{i} into Ω_{v} (and Ω′_{j} into Ω′_{w}) and conclude that (22) holds for any 1 ≤ i < v ≤ m and 1 ≤ j < w ≤ m such that there exists s > 0 such that

inf_{x∈Ω_{i},y∈Ω_{v}: ∥x∥,∥y∥≤s} ∥x − y∥ = 0,  inf_{x∈Ω′_{j},y∈Ω′_{w}: ∥x∥,∥y∥≤s} ∥x − y∥ = 0.

That is, for any k ≥ 1, we consider the perturbation of the sets such that Ω̃_{i} := Ω_{i}∪B(y_{k}, s_{k}), Ω̃_{v} := Ω_{v} \ B(y_{k}, s_{k}), and we also consider the perturbation of the sets such that Ω̃_{i} := Ω_{i} \ B(x_{k}, s_{k}), Ω̃_{v} := Ω_{v} ∪ B(y_{k}, s_{k}). We then let k → ∞ and note that, crucially both of these perturbations result in the same first derivative of C_{ρ} as k → ∞, otherwise we would not be able to assert that these perturbations remain in the tangent space Tan_{ρ}. Performing a similar procedure for Ω′_{j} and Ω′_{w}, we conclude that (22) holds, i.e. under these assumptions, we have

0 = r_{ij} + r_{vw} − r_{iw} − r_{jv}.  (23)

And similarly

0 = ∑_{k=1}^{m}[r_{ik} − r_{vk}]T_{ρ}1_{Ω′_{k}}(x).  (24)

Recall that our main concern is e.g. if there exists 1 ≤ i < j ≤ m such that u_{ijk} = 0 for all 1 ≤ k ≤ m, i.e. if two columns of R are identical. Similarly, if there exists 1 ≤ i < j ≤ m such that u′_{ijk} = 0 for all 1 ≤ k ≤ m, then two rows of R are identical. Let n_{r} be the number of integers 1 ≤ i ≤ m such that row i of R has another row of R identical to row i. Let n_{c} be the number of integers 1 ≤ i ≤ m such that column i of R has another column of R identical to column i. We will show that n_{r} = n_{c} = 0 by induction on n_{r} + n_{c}. For the base case, note that it cannot occur that n_{r} = n_{c} = m since if all rows and columns are identical, this contradicts R ≠ 0 and ∑_{i,j=1}^{m} r_{ij} = 0. Now, if we have found that 0 < n_{r} + n_{c} < 2m, then we can find e.g. two duplicate rows r_{j} and r_{w} of R. Then moving Ω_{i} into Ω_{v} and Ω′_{j} into Ω′_{x} as described above with x ≠ w in (23), shows that, in a neighborhood of the original sets, we have that r_{j} ≠ r_{w}, thereby completing the inductive step.

We therefore conclude that R has no identical rows or columns (except perhaps on a set of measure zero). Consequently, except for a set of measure zero, we have: for all 1 ≤ i, j ≤ m, there exists 1 ≤ k ≤ m such that u_{ijk} ≠ 0. Similarly, for all 1 ≤ i, j ≤ m, there exists 1 ≤ k ≤ m such that u′_{ijk} ≠ 0. That is, Steps 2 and 3 apply to all of the set Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m}.

Final Remark. In the above proof, in Step 3, we assumed that γ_{n+1}(Ω_{i}) > 0 and γ_{n+1}(Ω′_{i}) > 0 for all 1 ≤ i ≤ m. To handle the case that e.g. γ_{n+1}(Ω_{m}) = 0, we can just assert that r_{mj} = 0 for all 1 ≤ j ≤ m in Step 1, and then the remaining parts of the proof go through unchanged. Alternatively, we could note that such sets contribute measure zero to ExtS_{ρ,m}(n + 1). □

Remark 2.6. In the course of the proof of Lemma 2.5, we showed that, except for a set of measure zero in ExtS_{ρ,m}(n + 1), we have: for all 1 ≤ i, j ≤ m, there exists 1 ≤ k ≤ m such that u_{ijk} ≠ 0. Similarly, for all 1 ≤ i, j ≤ m, there exists 1 ≤ k ≤ m such that u′_{ijk} ≠ 0.

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

\begin{aligned}N′_{ij}(x) & = ±\frac{\overline{∇}T_{ρ}(∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x)}{∥\overline{∇}T_{ρ}(∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x)∥},  ∀ x ∈ Σ′_{ij}. \\ N_{ij}(x) & = ±\frac{\overline{∇}T_{ρ}(∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x)}{∥\overline{∇}T_{ρ}(∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x)∥},  ∀ x ∈ Σ_{ij}. \end{aligned}  (25)

In Lemma 4.2 below we will show that the positive sign holds in (25) for sets minimizing Problem 1.7.

3. First and Second Variation

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

Summary of Notation.

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

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

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

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

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

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

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

• Z = (z_{ij})_{1≤i,j≤m} denotes a real m × m matrix, used in Problem 1.7.

• s_{ij} := ∫_{ℝ^{n+1}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω′_{j}}(x)γ_{n+1}(x) dx, ∀ 1 ≤ i, j ≤ m.

• d_{ij} > 0 ∀ 1 ≤ i, j ≤ m are constants defined in Problem 1.7.

• u_{ijk} = d_{ki}(s_{ki} − z_{ki}) − d_{kj}(s_{kj} − z_{kj}), ∀ 1 ≤ i, j, k ≤ m

• u′_{ijk} = d_{ik}(s_{ik} − z_{ik}) − d_{jk}(s_{jk} − z_{jk}), ∀ 1 ≤ i, j, k ≤ m. Throughout the paper, unless otherwise stated, we define G: ℝ^{n+1} × ℝ^{n+1} → ℝ to be the following function. For all x, y ∈ ℝ^{n+1}, ∀ ρ ∈ (−1, 1), define

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

We can then rewrite the noise stability from Equation 3 as

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

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

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

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

The following Lemma is a consequence of (27) and Lemma 2.5.

Let X, X′ ∈ C_{0}^{∞}(ℝ^{n+1}, ℝ^{n+1}). Let {Ω_{i}^{(s)}}_{s∈(−1,1)} be the variation of Ω_{i} corresponding to X for all 1 ≤ i ≤ m. Let {Ω_{i}^{′(s)}}_{s∈(−1,1)} be the variation of Ω′_{i} corresponding to X′ for all 1 ≤ i ≤ m. Denote f_{ij}(x) := ⟨X(x), N_{ij}(x)⟩ for all x ∈ Σ_{ij} and f′_{ij}(x) := ⟨X′(x), N′_{ij}(x)⟩ for all x ∈ Σ′_{ij}. We let N denote the exterior pointing unit normal vector to ∂^{∗}Ω_{i} for any 1 ≤ i ≤ m and we let N′ denote the exterior pointing unit normal vector to ∂^{∗}Ω′_{i} for any 1 ≤ i ≤ m.

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

T_{ρ}( ∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x) = c′_{ij}, ∀ x ∈ Σ_{ij}.

T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x) = c_{ij}, ∀ x ∈ Σ′_{ij}.

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

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

= ∫_{Σ_{ij}}⟨X(x), N_{ij}(x)⟩ ∑_{k=1}^{m} d_{ik} ∫_{Ω′_{k}} G(x, y) dydx( ∫_{ℝ^{n+1}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω′_{k}}(x)γ_{n+1}(x) dx − z_{ik})

+ ∫_{Σ_{ij}}⟨X(x), N_{ji}(x)⟩ ∑_{k=1}^{m} d_{jk} ∫_{Ω′_{k}} G(x, y) dydx( ∫_{ℝ^{n+1}} 1_{Ω_{j}}(x)T_{ρ}1_{Ω′_{k}}(x)γ_{n+1}(x) dx − z_{jk})

=^{(3)∧(26)} ∫_{Σ_{ij}} T_{ρ}( ∑_{k=1}^{m}(d_{ik}(s_{ik} − z_{ik}) − d_{jk}(s_{jk} − z_{jk}))1_{Ω′_{k}})(x)f_{ij}(x) dx.

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

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

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

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

4. Noise Stability and the Calculus of Variations

We now further refine the first and second variation formulas from the previous section. Let X ∈ C_{0}^{∞}(ℝ^{n+1}, ℝ^{n+1}). Let {Ω_{i}^{(s)}}_{s∈(−1,1)} be the corresponding variation of Ω_{i} for all 1 ≤

i ≤ m, and let {Ω_{i}^{′(s)}}_{s∈(−1,1)} be the variation of Ω′_{i} corresponding to X′ ∈ C_{0}^{∞}(ℝ^{n+1}, ℝ^{n+1}). Denote f_{ij}(x) := ⟨X(x), N_{ij}(x)⟩, for all x ∈ Σ_{ij} := (∂^{∗}Ω_{i}) ∩ (∂^{∗}Ω_{j}). We let N denote the exterior pointing unit normal vector to ∂^{∗}Ω_{i} for any 1 ≤ i ≤ m. Denote f′_{ij}(x) := ⟨X′(x), N′_{ij}(x)⟩, for all x ∈ Σ′_{ij} := (∂^{∗}Ω′_{i}) ∩ (∂^{∗}Ω′_{j}). We let N′ denote the exterior pointing unit normal vector to ∂^{∗}Ω′_{i} for any 1 ≤ i ≤ m.

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

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

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

+ ∫_{Σ_{ij}} [( ∑_{k=1}^{m} u′_{ijk} ∫_{∂^{∗}Ω′_{k}} )G(x, y)⟨X′(y), N′(y)⟩ dy]f_{ij}(x) dx

+ ∫_{Σ_{ij}} ⟨\overline{∇}T_{ρ}( ∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x), X(x)⟩f_{ij}(x)γ_{n+1}(x) dx

+ ∫_{Σ_{ij}} T_{ρ}( ∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x)(div(X(x)) − ⟨X(x), x⟩)f_{ij}(x)γ_{n+1}(x) dx

+ ∫_{Σ′_{ij}} ⟨\overline{∇}T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x), X′(x)⟩f′_{ij}(x)γ_{n+1}(x) dx

+ ∫_{Σ′_{ij}} T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x)(div(X′(x)) − ⟨X′(x), x⟩)f′_{ij}(x)γ_{n+1}(x) dx

+ ∑_{i,j=1}^{m} d_{ij}[ ∫_{∂^{∗}Ω_{i}} T_{ρ}1_{Ω′_{j}}(x)f_{ij}(x)γ_{n+1}(x) dx + ∫_{∂^{∗}Ω′_{j}} T_{ρ}1_{Ω_{i}}(x)f′_{ij}(x)γ_{n+1}(x) dx]^{2}.

(28)

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

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

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

+ ∫_{Σ}(∑_{i=1}^{n+1} T_{ρ}1_{Ω}(x)\frac{∂}{∂x_{i}} X_{i}(x) − x_{i}T_{ρ}1_{Ω}(x)X_{i}(x) + \frac{∂}{∂x_{i}} T_{ρ}1_{Ω}(x)X_{i}(x))⟨X(x), N(x)⟩γ_{n+1}(x) dx

= ∫_{Σ} ∫_{Σ} G(x, y)⟨X(x), N(x)⟩⟨X(y), N(y)⟩ dxdy + ∫_{Σ} T_{ρ}1_{Ω}(x)(div(X(x)) − ⟨X(x), x⟩) + ⟨∇T_{ρ}1_{Ω}(x), X(x)⟩⟩⟨X(x), N(x)⟩γ_{n+1}(x) dx. Using the polarization identity in the form

∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}} 1_{Ω^{(s)}}(y)G(x, y)1_{Ω^{′(s)}}(x) dxdy

= \frac{1}{4}( ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}}(1_{Ω^{(s)}} + 1_{Ω^{′(s)}})(y)G(x, y)(1_{Ω^{(s)}} + 1_{Ω^{′(s)}})(x) dxdy

− ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}}(1_{Ω^{(s)}} − 1_{Ω^{′(s)}})(y)G(x, y)(1_{Ω^{(s)}} − 1_{Ω^{′(s)}})(x) dxdy),

we then get, denoting f(x) := ⟨X(x), N(x)⟩ ∀ x ∈ Σ, f′(x) := ⟨X(x), N′(x)⟩ ∀ x ∈ Σ′,

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

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

We then use the chain rule to get

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

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

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

Here s_{0} := ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}} 1_{Ω}(y)G(x, y)1_{Ω′}(x) dxdy. Summing over i, j then concludes the proof, using also Lemma 3.2 to get

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

= ∑_{i,j=1}^{m} d_{ij}[ ∫_{∂^{∗}Ω_{i}} T_{ρ}1_{Ω′_{j}}(x)f_{ij}(x)γ_{n+1}(x) dx + ∫_{∂^{∗}Ω′_{j}} T_{ρ}1_{Ω_{i}}(x)f′_{ij}(x)γ_{n+1}(x) dx]^{2}.

□

Lemma 4.2 (Second Variation of Minimizers, Extended). Suppose we have two partitions Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} ⊆ ℝ^{n+1} of ℝ^{n+1} into measurable sets such that ∂Ω_{i}, ∂Ω′_{i} are a locally finite union of C^{∞} manifolds ∀ 1 ≤ i ≤ m. Suppose we extend X|_{∪_{i=1}^{m}∂Ω_{i}} such that div(X)(x) = ⟨X(x), x⟩ and we extend X′|_{∪_{i=1}^{m}∂Ω′_{i}} such that div(X′)(x) = ⟨X′(x), x⟩. Then

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

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

+ ∫_{Σ_{ij}} [( ∑_{k=1}^{m} u′_{ijk} ∫_{∂^{∗}Ω′_{k}} )G(x, y)⟨X′(y), N′(y)⟩ dy]f_{ij}(x) dx

+ ∫_{Σ_{ij}} ∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x)∥ |f_{ij}(x)|^{2} γ_{n+1}(x) dx

+ ∫_{Σ′_{ij}} ∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x)∥ |f′_{ij}(x)|^{2} γ_{n+1}(x) dx

+ ∑_{i,j=1}^{m} d_{ij}[ ∫_{∂^{∗}Ω_{i}} T_{ρ}1_{Ω′_{j}}(x)f_{ij}(x)γ_{n+1}(x) dx + ∫_{∂^{∗}Ω′_{j}} T_{ρ}1_{Ω_{i}}(x)f′_{ij}(x)γ_{n+1}(x) dx]^{2}.

(29)

Also,

\begin{matrix}\overline{∇}T_{ρ}( ∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x) = N_{ij}(x)∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x)∥,  ∀ x ∈ Σ_{ij}. \\ \overline{∇}T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x) = N′_{ij}(x)∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x)∥,  ∀ x ∈ Σ′_{ij}. \end{matrix}  (30)

Moreover, ∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x)∥ > 0 for all x ∈ Σ_{ij}, except on a set of Hausdorff dimension at most n − 1, and ∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x)∥ > 0 for all x ∈ Σ′_{ij}, except on a set of Hausdorff dimension at most n − 1.

Proof. We extend X such that div(X(x)) = ⟨X(x), x⟩ for all x in a neighborhood of ∪_{i=1}^{m}∂Ω_{i}, and we extend X′ such that div(X′(x)) = ⟨X′(x), x⟩ for all x in a neighborhood of ∪_{i=1}^{m}∂Ω′_{i}, so that the two integrals with divergence terms in Lemma 4.1 vanish. Equation 30 follows by taking the gradient of the First Variation condition from Lemma 3.2, though there is an ambiguity in the sign of the right side of (30) which will be eliminated below.

If there exists 1 ≤ i < j ≤ m such that ∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x)∥ = 0 on an open set in Σ′_{ij}, then choose X′ supported in this open set so that the fifth term of (28) is zero. Then, choose X such that sum of the first two terms in (28) is negative. And choose X, X′ such that the last term is zero. Multiplying then X by a small positive constant, and noting that the fourth term in (28) has quadratic dependence on X while the first two terms have linear dependence on X, we can create a negative second derivative of the noise stability, giving a contradiction. We can similarly justify the positive signs appearing in (30).

We then arrive at

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

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

+ ∫_{Σ_{ij}} [( ∑_{k=1}^{m} u′_{ijk} ∫_{∂^{∗}Ω′_{k}} )G(x, y)⟨X′(y), N′(y)⟩ dy]f_{ij}(x) dx

+ ∫_{Σ_{ij}} ⟨\overline{∇}T_{ρ}( ∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x), X(x)⟩f_{ij}(x)γ_{n+1}(x) dx

+ ∫_{Σ′_{ij}} ⟨\overline{∇}T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x), X′(x)⟩f′_{ij}(x)γ_{n+1}(x) dx

+ d_{ij}[ ∫_{∂^{∗}Ω_{i}} T_{ρ}1_{Ω′_{j}}(x)f_{ij}(x)γ_{n+1}(x) dx + ∫_{∂^{∗}Ω′_{j}} T_{ρ}1_{Ω_{i}}(x)f′_{ij}(x)γ_{n+1}(x) dx]^{2}.

Substituting (30) into this equality completes the proof. □

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

\begin{matrix}S_{ij}(⟨v, N⟩)(x) := (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2} ∑_{k=1}^{m} u_{ijk} ∫_{∂^{∗}Ω_{k}}⟨v, N(y)⟩e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy, ∀ x ∈ Σ′_{ij}. \\ S′_{ij}(⟨v, N′⟩)(x) := (1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2} ∑_{k=1}^{m} u′_{ijk} ∫_{∂^{∗}Ω′_{k}}⟨v, N′(y)⟩e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy, ∀ x ∈ Σ_{ij}. \end{matrix}

(31)

Both quantities on the right are finite a priori by the divergence theorem and Remark 4.4.

Lemma 4.3 (Key Lemma, m ≥ 2, Translations as Almost Eigenfunctions). Let Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} minimize Problem 1.7. Assume that ∂Ω_{i}, ∂Ω′_{i} are locally finite unions of C^{∞} manifolds for all 1 ≤ i ≤ m. Fix 1 ≤ i < j ≤ m. Let v, w ∈ ℝ^{n+1}. Then

S_{ij}(⟨v, N⟩)(x) = −⟨v, N′_{ij}(x)⟩\frac{1}{ρ}∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x)∥, ∀ x ∈ Σ′_{ij}.

S′_{ij}(⟨w, N′⟩)(x) = −⟨w, N_{ij}(x)⟩\frac{1}{ρ}∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x)∥, ∀ x ∈ Σ_{ij}.

Proof. From Lemma 4.2, i.e. (30),

\overline{∇}T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x) = N′_{ij}(x)∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x)∥,  ∀ x ∈ Σ′_{ij}.  (32)

From Definition 3, and then using the divergence theorem, ∀ x ∈ Σ_{ij},

⟨v, \overline{∇}T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x)⟩

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

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

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

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

(33)

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

⟨v, N′_{ij}(x)⟩∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x)∥ =^{(32)} ⟨v, \overline{∇}T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x)⟩

=^{(33)} −(1 − ρ^{2})^{−(n+1)/2}(2π)^{−(n+1)/2}ρ ∑_{k=1}^{m} u_{ijk} ∫_{∂^{∗}Ω_{k}}⟨v, N(y)⟩e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy

=^{(31)} −ρ S_{ij}(⟨v, N⟩)(x), ∀ x ∈ Σ′_{ij}.

□

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

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

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

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

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

(34)

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

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

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

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

Lemma 4.5 (Second Variation of Translations). Let v ∈ ℝ^{n+1}. Let Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} minimize Problem 1.7. Assume that ∂Ω_{i}, ∂Ω′_{i} are locally finite unions of C^{∞} manifolds for all 1 ≤ i ≤ m. For each 1 ≤ i ≤ m, let {Ω_{i}^{(s)}}_{s∈(−1,1)} be the variation of Ω_{i} corresponding to the constant vector field X := v and let {Ω_{i}^{′(s)}}_{s∈(−1,1)} be the variation of Ω_{i} corresponding to X′ := v for all 1 ≤ i ≤ m (When ρ < 0, we choose X′ := −v.) Then

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

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

+ ∫_{Σ_{ij}} |⟨v, N_{ij}(x)⟩|^{2} ∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x)∥γ_{n+1}(x) dx

+ ∑_{i,j=1}^{m} d_{ij}[ ∫_{∂^{∗}Ω_{i}} T_{ρ}1_{Ω′_{j}}(x)⟨v, N(x)⟩γ_{n+1}(x) dx + sign(ρ) ∫_{∂^{∗}Ω′_{j}} T_{ρ}1_{Ω_{i}}(x)⟨v, N′(x)⟩γ_{n+1}(x) dx]^{2}.

Proof. For any 1 ≤ i < j ≤ m, let f_{ij}(x) := ⟨v, N_{ij}(x)⟩ for all x ∈ Σ_{ij} and let f′_{ij}(x) := ⟨v, N′_{ij}(x)⟩ for all x ∈ Σ′_{ij}. From Lemma 4.2, if ρ > 0, then

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

=^{(31)∧(26)} ∑_{1≤i<j≤m} ∫_{Σ′_{ij}} [S_{ij}(⟨v, N⟩)(x) + ∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x)∥f′_{ij}(x)]f′_{ij}(x)γ_{n+1}(x) dx

+ ∫_{Σ_{ij}} [S′_{ij}(⟨v, N′⟩)(x) + ∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x)∥f_{ij}(x)]f_{ij}(x)γ_{n+1}(x) dx

+ d_{ij}[ ∫_{∂^{∗}Ω_{i}} T_{ρ}1_{Ω′_{j}}(x)f_{ij}(x)γ_{n+1}(x) dx + ∫_{∂^{∗}Ω′_{j}} T_{ρ}1_{Ω_{i}}(x)f′_{ij}(x)γ_{n+1}(x) dx]^{2}.

Applying Lemma 4.3,

S_{ij}(⟨v, N⟩)(x) = −⟨v, N′_{ij}(x)⟩\frac{1}{ρ}∥\overline{∇}T_{ρ}(∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x)∥, ∀ x ∈ Σ′_{ij},

S′_{ij}(⟨v, N′⟩)(x) = −⟨v, N_{ij}(x)⟩\frac{1}{ρ}∥\overline{∇}T_{ρ}(∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x)∥, ∀ x ∈ Σ_{ij},

proving the Lemma in the case ρ > 0. In the case ρ < 0, we instead have f′_{ij}(x) = ⟨−v, N′_{ij}(x)⟩ ∀ x ∈ Σ′_{ij}, so

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

= ∑_{1≤i<j≤m} ∫_{Σ′_{ij}} [S_{ij}(⟨v, N⟩)(x) + ∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x)∥f′_{ij}(x)]f′_{ij}(x)γ_{n+1}(x) dx

+ ∫_{Σ_{ij}} [S′_{ij}(⟨−v, N′⟩)(x) + ∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x)∥f_{ij}(x)]f_{ij}(x)γ_{n+1}(x) dx

+ d_{ij}[ ∫_{∂^{∗}Ω_{i}} T_{ρ}1_{Ω′_{j}}(x)f_{ij}(x)γ_{n+1}(x) dx + ∫_{∂^{∗}Ω′_{j}} T_{ρ}1_{Ω_{i}}(x)f′_{ij}(x)γ_{n+1}(x) dx]^{2}.

S_{ij}(⟨v, N⟩)(x) = ⟨−v, N′_{ij}(x)⟩\frac{1}{ρ}∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x)∥, ∀ x ∈ Σ′_{ij},

S′_{ij}(⟨−v, N′⟩)(x) = ⟨v, N_{ij}(x)⟩\frac{1}{ρ}∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x)∥, ∀ x ∈ Σ_{ij},

The Lemma then follows for ρ < 0.

Note also that ∑_{1≤i<j≤m} ∫_{Σ_{ij}} ∥\overline{∇}T_{ρ}(∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x)∥⟨v, N_{ij}(x)⟩^{2}γ_{n+1}(x) dx is finite a priori by the divergence theorem since ∀ 1 ≤ i ≤ m,

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

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

Summing over 1 ≤ i, j, k ≤ m then gives

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

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

□

5. Proof of the Main Dimension Reduction Theorem

Proof of Theorem 1.8. Let m ≥ 2. Let −1 < ρ < 1 with ρ ≠ 0. Let Ω_{1}, … Ω_{m}, Ω′_{1}, … Ω′_{m} ⊆ ℝ^{n+1} be two partitions of ℝ^{n+1} into measurable sets that minimize Problem 1.7, with Z chosen as in Lemma 2.5 (i.e. so that {s_{ij} − z_{ij}}_{1≤i,j≤m} are not all equal.) It suffices to verify Theorem 1.8 in the complement of the set Λ defined in Lemma 2.5, since the conclusion of Theorem 1.8 is preserved by weak limits. These sets exist by Lemma 2.3 and from Lemma 2.5 their boundaries are locally finite unions of C^{∞} n-dimensional manifolds. Define Σ_{ij} := (∂^{∗}Ω_{i}) ∩ (∂^{∗}Ω_{j}), Σ′_{ij} := (∂^{∗}Ω′_{i}) ∩ (∂^{∗}Ω′_{j}) for all 1 ≤ i < j ≤ m.

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

∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x)∥ > 0 ∀ x ∈ Σ_{ij} \ σ_{ij}, ∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u_{ijk}1_{Ω_{k}})(x)∥ > 0 ∀ x ∈ Σ′_{ij} \ σ′_{ij}.

(35)

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

V := {v ∈ ℝ^{n+1} : ∫_{∂^{∗}Ω_{i}} T_{ρ}1_{Ω′_{j}}(x)⟨v, N(x)⟩γ_{n+1}(x) dx

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

From Lemma 4.5,

v ∈ V ⟹ \frac{1}{2} \frac{d^{2}}{ds^{2}} |_{s=0} ∑_{i,j=1}^{m} d_{ij}( ∫_{ℝ^{n+1}} ∫_{ℝ^{n+1}} 1_{Ω_{i}^{(s)}}(y)G(x, y)1_{Ω_{j}^{′(s)}}(x) dxdy − z_{ij})^{2}

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

+ ∫_{Σ_{ij}} |⟨v, N_{ij}(x)⟩|^{2} ∥\overline{∇}T_{ρ}( ∑_{k=1}^{m} u′_{ijk}1_{Ω′_{k}})(x)∥γ_{n+1}(x) dx.

This second derivative must be zero, since Ω_{1}, …, Ω_{m}, Ω′_{1}, …, Ω′_{m} minimize Problem 1.7. Since 0 < |ρ| < 1, (35) implies

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

(36)

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

(M(v))_{ij} := ∫_{∂^{∗}Ω_{i}} T_{ρ}1_{Ω′_{j}}(x)⟨v, N(x)⟩γ_{n+1}(x) dx

+ sign(ρ) ∫_{∂^{∗}Ω′_{j}} T_{ρ}1_{Ω_{i}}(x)⟨v, N′(x)⟩γ_{n+1}(x) dx, ∀ 1 ≤ i, j ≤ m

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

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

Acknowledgement. Thanks to Pritish Kamath for helpful discussions, including pointing out that the set of probability distribution matrices from Gaussian sources is not convex.

Thanks for Larry Goldstein for helpful discussions, particularly on the abstract and introduction.

References

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

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