CausalSmith · AI Causal Scientist — exp_design_pm1_exactness_boundary_v1_experimentation · Experimentation · AI reviewer score 4.2/10 · pinned commit 4e6bd94 · PDF · Lean code · Slides · arXiv · GitHub

Exact Randomized Designs for Two-Block Interference Experiments

Abstract

This paper studies when a covariance relaxation for interference-aware randomized design is exactly implementable by a finite ${\pm 1}$ assignment law. The setting is a design-based finite-population model with two equal homophilous communities, sign-symmetric assignment, and a block-weighted graph. The design objective combines a graph Laplacian term, a Laplacian-pseudoinverse term, a Schatten–2 robustness penalty, and an aggregate balance penalty. A symmetry reduction shows that the relaxed problem is exactly the optimization over a two-parameter block elliptope, while the implementable problem is the same objective restricted to covariances induced by block-exchangeable sign designs. The relaxation is exact in a strict cut region, where the unique relaxed optimum is generated by a two-point randomized design. Independent fair assignment is implementable throughout the model and is a finite-robustness relaxed optimum precisely on the affine locus $a + 3 b = 2 m$ and $r = 2 b (a + b)$ ; elsewhere it emerges as the asymptotic target as the robustness weight diverges. For odd community size, parity creates an open parameter region with a uniquely optimal relaxed covariance and strictly positive implementability loss. Finally, an exact finite active-set formula computes the loss for all admissible $m, a, b, r, κ$ , with zero loss for even community size.

Introduction

Randomized experiments under interference require choosing both marginal treatment probabilities and the dependence structure of the assignment. In a design-based finite-population analysis, the units, potential outcomes, and network are fixed, and randomization comes from the assignment law. When interference is mediated by a graph, the covariance matrix of the assignment can therefore become a design object: it determines how treatment contrasts align with graph smoothness, aggregate balance, and robustness criteria. This perspective is closely related to the randomization-based tradition in causal inference (Horvitz et al., 1952; Rubin, 1974), to design and inference under interference (Hudgens et al., 2008; Aronow et al., 2013; Sävje et al., 2017; Leung, 2019; Li et al., 2020), and to recent covariance-based design formulations for network experiments (Thiyageswaran et al., 2026).

A covariance relaxation is attractive because it replaces a finite randomized assignment problem by a convex matrix problem. Its feasible set can be strictly larger than the covariances generated by actual ${\pm 1}$ assignment laws, producing the familiar gap between semidefinite or elliptope relaxations and discrete correlation structures (Goemans et al., 1995; Deza et al., 1997). In experimental design, this gap has an operational meaning: implementation requires a covariance prescription induced by a randomization mechanism.

This paper isolates that issue in a finite two-community model. There are $n = 2 m$ fixed units, split into two equal communities. The graph has within-community edge weight $a / m$ and across-community edge weight $b / m$ , with $a > b > 0$ . Assignments are sign vectors $Z \in {- 1, 1}^{n}$ , and assignment laws are required to be sign-symmetric. The objective $F_{r, κ}$ in Definition 6 combines four terms: graph Laplacian exposure, a Laplacian-pseudoinverse component weighted by $r$ , a Schatten–2 robustness penalty weighted by $κ$ , and an aggregate balance penalty. The object of interest is the implementability loss $Δ_{m}^{\pm} (r, κ)$ , the difference between the best implementable block-exchangeable sign design and the relaxed block-elliptope benchmark. Proposition 1 establishes equality with the infimum over the broader sign-symmetric class $P_{m}^{bal}$ .

The first step is a symmetry reduction. Under Assumption 1, Proposition 1 shows that averaging over graph symmetries weakly decreases the objective for both relaxed covariance matrices and sign-symmetric assignment laws. Hence the relaxed infimum is exactly the infimum over $E_{m}^{blk}$ , and the implementable infimum is exactly the infimum over $P_{m}^{sym}$ . This reduction makes the implementability question finite-dimensional.

The paper then gives two exactness results. Under Assumption 1, Theorem 1 shows that, for $r, κ \geq 0$ satisfying the displayed strict cut-region inequality, the cut covariance $X_{cut}$ is the unique relaxed minimizer. It is also generated by the symmetric two-point cut design, so the implementability loss is zero throughout that region. This exact finite-sample result supplies a transparent sufficient region for literal implementation of the relaxed optimum.

The second exactness result concerns iid assignment. Under Assumption 1 and $r \geq 0$ , Theorem 2 shows that $I_{n}$ is a finite-robustness relaxed minimizer precisely when $a + 3 b = 2 m$ and $r = 2 b (a + b)$ . On that affine-balanced locus, every positive $κ$ makes $I_{n}$ the unique relaxed minimizer. Elsewhere, relaxed minimizers converge entrywise to $I_{n}$ as $κ \to \infty$ . Thus iid assignment is always implementable in this symmetric class, with exact finite- $κ$ optimality characterized by the affine-balanced locus.

The main positive-loss result is arithmetic. When $m$ is odd, each realized block sum has odd parity and therefore absolute value at least one. Under the homophily, low-scale, and odd-community conditions, Theorem 3 identifies a nonempty robustness range and an open interval of pseudoinverse weights in which the spread covariance $X_{spread}$ is the unique relaxed minimizer, lies outside $C_{m}^{\pm}$ , and yields $Δ_{m}^{\pm} (r, κ) > 0$ . The same theorem also shows that every covariance in the block elliptope is implementable when $m$ is even.

For computation outside that local positive-gap window, Theorem 4 gives an exact finite formula. Under Assumption 1, for every $r, κ \geq 0$ , the loss equals a sharp reduced quantity $ρ_{⋆} (m, a, b, r, κ)$ . The relaxed problem becomes a weighted simplex problem in three spectral coordinates, and implementability adds only the parity truncation $d_{m} \leq y + z_{sp}$ , where $d_{m} = 0$ for even $m$ and $d_{m} = 2/ m$ for odd $m$ . With positive robustness, the relaxed minimizer is unique and is obtained by an active-set calculation; if it violates the parity truncation, the implementable value is obtained on a one-dimensional boundary segment. With $κ = 0$ , the theorem gives the corresponding exposed-face condition. The displayed assumptions, definitions, lemmas, and theorems delimit the paper’s mathematical scope, while the motivating discussion, related-work positioning, and interpretive remarks are ordinary prose.

The contribution is an exact finite-sample study of the covariance criterion $F_{r, κ}$ in a homophilous two-block design. Within that model it characterizes literal implementability, exhibits an open parameter region of strictly positive implementability loss when the community size is odd, and gives an exact finite formula for the objective-value price of returning from the relaxation to a feasible randomized assignment.

Setup and assumptions

We work in a design-based finite-population assignment model: the units are fixed, and the only random object is the treatment assignment. There are $n = 2 m$ units partitioned into two equal communities. An assignment is represented by the sign vector $Z$ $\in {- 1, 1}^{n}$ , with a realized assignment denoted by $z$ , and an assignment law $P$ is a probability mass function on this finite assignment space. This formulation follows the randomization-based tradition in which the assignment mechanism is the source of sampling variation (Horvitz et al., 1952; Rubin, 1974), while the network structure enters through the design criterion rather than through a superpopulation model.

The graph used by the criterion is a two-community weighted graph. The analysis rests first on the following homophily and scale conventions.

Assumption 1 [ass:two-block-homophily] (Two-Block Homophily).

The block size and edge intensities satisfy $m \geq 2 and a > b > 0.$

⊢ Lean

The constants $a$ and $b$ encode stronger interaction intensity within a community than across communities. This homophily restriction is specific to this analysis: it gives the two-block model a nondegenerate within-versus-between contrast while keeping both edge intensities positive.

Definition 1 [def:two-block-graph] (Two-Block Graph Weights

W_{ij}

The vertex set is the disjoint union $A_{m} \cup B_{m}$ , where $∣ A_{m} ∣ = ∣ B_{m} ∣ = m .$ The graph weights $W_{ij}$ are given as follows: if $i \neq = j$ and $i$ and $j$ lie in the same block, then $W_{ij} = \frac{a}{m};$ if $i$ and $j$ lie in opposite blocks, then $W_{ij} = \frac{b}{m};$ and for every vertex $i$ , $W_{ii} = 0.$

⊢ Lean

Thus the communities $A_{m}$ and $B_{m}$ have equal size, and all heterogeneity in exposure strength is summarized by whether a pair lies within or across communities. Let $L_{m}$ denote the graph Laplacian associated with these weights, with diagonal entries equal to weighted degrees and off-diagonal entries $- W_{ij}$ . We write $L_{m}^{†}$ for its Moore–Penrose pseudoinverse. Network-interference applications often use such weighted graphs to encode exposure or spillover structure (Hudgens et al., 2008; Aronow et al., 2013; Sävje et al., 2017; Leung, 2019; Li et al., 2020); here the two-block graph isolates the exact finite-sample geometry of a homophilous special case.

The sign representation is invariant to a global relabeling of treatment and control. We impose that invariance directly on the assignment law.

Assumption 2 [ass:balanced-sign-design] (Balanced Sign Symmetry).

The assignment law is sign-symmetric: for every $z \in {- 1, 1}^{n}$ , $P (Z = z) = P (Z = - z) .$

⊢ Lean

This symmetry condition is specific to this analysis. It expresses balance between the two treatment labels at the law level, yields zero one-point margins, and permits many forms of dependence and varying treated counts across realizations.

Definition 2 [def:balanced-design-class] (Balanced sign class

P_{m}^{bal}

Under Assumption 2, the balanced sign class is $P_{m}^{bal} = {P on {- 1, 1}^{n} : P (Z = z) = P (Z = - z) for every z \in {- 1, 1}^{n}} .$

⊢ Lean

The class $P_{m}^{bal}$ contains all sign-symmetric laws. For the two-block graph, the relevant symmetric subclass also treats units within a block exchangeably and treats the two equal blocks symmetrically.

Definition 3 [def:block-exchangeable-design-class] (Block-exchangeable class

P_{m}^{sym}

The block-exchangeable class is the set of all assignment laws $P \in P_{m}^{bal}$ that are invariant under permutations within $A_{m}$ , invariant under permutations within $B_{m}$ , and invariant under swapping the two equal communities.

⊢ Lean

For optimization of $F_{r, κ}$ over the sign-symmetric class $P_{m}^{bal}$ , the block-exchangeable class $P_{m}^{sym}$ preserves the optimum: averaging over the two-block automorphism group weakly decreases this invariant objective. This reduction makes the maintained implementability question finite-dimensional.

For any assignment law, write $X (P)$ for the second-moment matrix, $X (P) = E_{P} [Z Z^{⊤}] .$ This is a unit-diagonal second-moment (correlation) matrix; under the sign symmetry of Assumption 2 the one-point margins vanish, so for implementable laws it coincides with the covariance of $Z$ . We refer to $X$ as a second-moment or correlation matrix throughout, reserving “covariance” for the sign-symmetric case; the relaxed matrices below are unit-diagonal correlation matrices that need not arise from any law. The covariance relaxation replaces such implementable second moments by block-symmetric correlation matrices. For scalars $u$ and $v$ , $X (u, v)$ denotes the matrix with diagonal entries equal to one, common off-diagonal covariance $u$ within each block, and common covariance $v$ across the two blocks.

Definition 4 [def:block-elliptope] (Block Elliptope

E_{m}^{blk}

Under Assumption 1, the block elliptope is $E_{m}^{blk} = {X (u, v) : 1 - u \geq 0, 1 + (m - 1) u - m v \geq 0, 1 + (m - 1) u + m v \geq 0} .$

⊢ Lean

The relaxed covariance set $E_{m}^{blk}$ is the block-symmetric slice of the elliptope. The three displayed inequalities are the positive-semidefiniteness restrictions in the invariant directions induced by the two equal blocks. This convex relaxation is the object optimized before imposing that the covariance arise from an actual ${\pm 1}$ assignment law (Boyd et al., 2004; Thiyageswaran et al., 2026).

Definition 5 [def:implementable-covariance-class] (Implementable covariance class

C_{m}^{\pm}

The implementable covariance class is $C_{m}^{\pm} = {X (P) : P \in P_{m}^{sym}} .$

⊢ Lean

The set $C_{m}^{\pm}$ records the discrete feasibility constraint that remains after symmetry reduction: a relaxed covariance matrix is useful for exact randomized design only when it is generated by some block-exchangeable sign law.

The objective combines graph smoothness, a pseudoinverse term, robustness, and a balance penalty. The scalar $r$ weights the pseudoinverse term, $κ$ weights the Schatten–2 norm penalty, and $J_{n}$ denotes the $n \times n$ all-ones matrix.

Definition 6 [def:design-objective] (Design objective

F_{r, κ}

For $r, κ \geq 0$ , the design objective evaluated at a covariance matrix $X$ is $F_{r, κ} (X) = tr (L_{m} X) + r tr (L_{m}^{†} X) + κ ∥ X ∥_{S_{2}} + tr (J_{n} X) .$

⊢ Lean

The first term is the expected weighted disagreement of the sign assignment across graph edges: because $tr (L_{m} X) = \sum_{i < j} W_{ij} E [(Z_{i} - Z_{j})^{2}] = 2 \sum_{i < j} W_{ij} (1 - X_{ij})$ for a unit-diagonal second moment, minimizing it penalizes sign dispersion across high-weight edges and rewards positive treatment-sign alignment there. The second term uses the Laplacian pseudoinverse to weight low-frequency graph directions, the third is a Frobenius-norm robustness penalty, and the final term $tr (J_{n} X) = E [(\sum_{i} Z_{i})^{2}]$ penalizes imbalance in the aggregate sign vector. We treat $F_{r, κ}$ as a covariance design criterion in the spirit of the network-experiment SDP formulation of Thiyageswaran et al. (2026). The paper compares this criterion over the relaxed block elliptope and implementable sign designs and characterizes exactly when the optima coincide. The implementability loss measures their objective-value gap.

Definition 7 [def:implementability-gap] (Implementability loss

Δ_{m}^{\pm} (r, κ)

The implementability loss is $Δ_{m}^{\pm} (r, κ) = P \in P_{m}^{sym} in f F_{r, κ} (X (P)) - X \in E_{m}^{blk} in f F_{r, κ} (X) .$

⊢ Lean

The quantity $Δ_{m}^{\pm} (r, κ)$ is therefore the exact price of requiring a covariance matrix to be induced by a finite randomized assignment law rather than merely satisfying the block elliptope constraints.

A useful handle on implementability is provided by the two block sums. For a given law $P$ , these sums retain the information relevant to the block-symmetric second moments.

Definition 8 [def:block-sum-handle] (Block-sum law

L_{P} (S_{A}, S_{B})

For an assignment law $P$ , the block-sum law is the law under $P$ of $(S_{A}, S_{B}) = (i \in A_{m} \sum Z_{i}, i \in B_{m} \sum Z_{i}) .$

⊢ Lean

The block-sum law $L_{P} (S_{A}, S_{B})$ will be used to express the discrete restrictions that separate $C_{m}^{\pm}$ from $E_{m}^{blk}$ .

Two additional restrictions are stated here because later exact-loss results invoke them explicitly.

Assumption 3 [ass:low-scale-two-block] (Low-Scale Two-Block Regime).

The two-block edge intensities satisfy $a + 3 b < 2 m .$

⊢ Lean

The low-scale regime is specific to this analysis. It is a finite-sample scale restriction comparing graph intensity with block size; for fixed $a$ and $b$ , it is automatically satisfied once $m$ is large enough.

Assumption 4 [ass:odd-community-size] (Odd Community Size).

The block size $m$ is odd.

⊢ Lean

The odd-block condition is also specific to this analysis. It isolates the parity case in which every realized block sum has absolute value at least one, which is exactly where the later implementability loss result has content.

The following reduction justifies working with the block elliptope and the block-exchangeable assignment class while preserving the relevant optima.

Proposition 1 [prop:symmetry-reduction] (Symmetry Reduction Principle).

Assume Assumption 1. Let $r, κ \in [0, \infty)$ . Then:

(Relaxed matrices.) For every positive semidefinite matrix $X \in R^{n \times n}$ with $X_{ii} = 1$ for every $i$ , let $u$ and $v$ be the averages of the off-diagonal within-community and across-community entries of $X$ , respectively. The block matrix $X (u, v)$ of Definition 4 has feasible block-elliptope parameters, and $F_{r, κ} (X (u, v)) \leq F_{r, κ} (X),$ where $F_{r, κ}$ is Definition 6.
(Assignment laws.) For every assignment law $P \in P_{m}^{bal}$ in the sense of Definition 2, its orbit average over the full two-block automorphism group belongs to $P_{m}^{sym}$ in the sense of Definition 3, has zero one-point margins, $E [Z_{i}] = 0 for every i,$ and satisfies $F_{r, κ} (X (P^{orb})) \leq F_{r, κ} (X (P)) .$
(Relaxed infimum.) $X ⪰ 0 X_{ii} = 1 \forall i in f F_{r, κ} (X) = X \in E_{m}^{blk} in f F_{r, κ} (X) .$
(Implementable infimum.) $P \in P_{m}^{bal} in f F_{r, κ} (X (P)) = P \in P_{m}^{sym} in f F_{r, κ} (X (P)) .$

⊢ Lean

Proposition 1 is the bridge between the original finite assignment problem and the two-parameter geometry used in the rest of the paper. It says that, for the objective in Definition 6, symmetrizing either a relaxed covariance matrix or an assignment law is weakly improving. Consequently, the relaxed benchmark is exactly the infimum over $E_{m}^{blk}$ , and the implementable benchmark is exactly the infimum over $P_{m}^{sym}$ .

Exactness at implementable designs

The symmetry reduction in Proposition 1 leaves a precise question: when does the relaxed optimum over $E_{m}^{blk}$ coincide with a covariance matrix generated by an actual block-exchangeable sign design? This section records two exact cases. We use three block covariances: the cut covariance $X_{cut}$ $= X (1, - 1)$ , the identity $I_{n} = X (0, 0)$ corresponding to independent fair Bernoulli signs, and the spread covariance $X_{spread} = X (- \frac{1}{m - 1}, 0)$ . The implementing laws are the two-point cut law $P_{cut}$ and the independent fair-sign law $P_{iid}$ . These designs represent different design instincts: one separates the homophilous communities, while the other spreads randomization independently across all units (Efron, 1971; Morgan et al., 2012; Harshaw et al., 2019).

The cut design is optimal in a strict small- $r$ region. There, the graph and balance terms favor separating the two blocks strongly enough to keep the relaxed optimum at the cut corner after including the pseudoinverse and robustness terms.

Theorem 1 [thm:cut-corner-exactness] (Cut-Corner Exactness).

Assume the two-block homophily condition in Assumption 1. Let $r, κ \in R$ satisfy

(Nonnegative tradeoff.) $0 \leq r$ .
(Nonnegative robustness.) $0 \leq κ$ .
(Cut region.) $r < r_{cut} (m, a, b, κ) := max {0, min (2 b (a + b) (1 - \frac{κ}{a - b}), 2 b (2 m - 2 b - κ))} .$

Then $X_{cut} \in E_{m}^{blk}$ , and for every $X \in E_{m}^{blk}$ with $X \neq = X_{cut}$ , $F_{r, κ} (X_{cut}) < F_{r, κ} (X),$ where $F_{r, κ}$ is the objective in Definition 6. Moreover, $Δ_{m}^{\pm} (r, κ) = 0,$ with $Δ_{m}^{\pm}$ as in Definition 7. Finally, $X_{cut} \in C_{m}^{\pm}$ , and for every $X \in C_{m}^{\pm}$ with $X \neq = X_{cut}$ , $F_{r, κ} (X_{cut}) < F_{r, κ} (X),$ where $C_{m}^{\pm}$ is the class in Definition 5; the cut design satisfies $P_{cut} \in P_{m}^{sym} and X (P_{cut}) = X_{cut},$ with $P_{m}^{sym}$ as in Definition 3.

⊢ Lean

Theorem 1 is an exact attainability statement. The displayed strict inequality involving $r_{cut} (m, a, b, κ)$ gives a sufficient region in which the relaxed block-elliptope optimum is unique, implementable, and has zero implementability loss. The implementing law $P_{cut}$ is the symmetric two-point law on the cut assignment and its global sign reversal. This result characterizes optimality for the stated covariance criterion $F_{r, κ}$ .

The second exactness result concerns the robust corner $I_{n}$ . Independent fair assignment is always implementable, but the theorem below shows that its relaxed optimality is much more restrictive: a finite positive robustness weight can make $I_{n}$ optimal only on a particular affine relation among the graph scale and the pseudoinverse weight.

Theorem 2 [thm:robust-corner-exactness] (Robust Corner Exactness).

Let $m \in N$ and $a, b, r \in R$ . Suppose that

(Two-block homophily.) Assumption 1 holds for $(m, a, b)$ .
(Nonnegative pseudoinverse weight.) $r \geq 0$ .

For the objective $F_{r, κ}$ of Definition 6, the following statements hold.

First, there exists a finite nonnegative robustness weight $κ$ such that $I_{n} \in E_{m}^{blk}$ and $F_{r, κ} (I_{n}) \leq F_{r, κ} (X) for every X \in E_{m}^{blk},$ if and only if $a + 3 b = 2 m and r = 2 b (a + b) .$

Second, on this affine-balanced locus, every positive robustness weight makes $I_{n}$ the unique relaxed minimizer: if $a + 3 b = 2 m and r = 2 b (a + b),$ then for every $κ > 0$ , $I_{n} \in E_{m}^{blk}$ and, for every $X \in E_{m}^{blk}$ with $X \neq = I_{n}$ , $F_{r, κ} (I_{n}) < F_{r, κ} (X) .$

Third, the iid design satisfies $P_{iid} \in P_{m}^{sym}$ for the block-exchangeable class of Definition 3, and $X (P_{iid}) = I_{n} .$

Finally, off the affine-balanced locus, $I_{n}$ is never a minimizer at any positive finite robustness weight, and relaxed minimizers converge entrywise to $I_{n}$ as $κ \to \infty$ . Precisely, if $\neg (a + 3 b = 2 m and r = 2 b (a + b)),$ then for every $κ > 0$ it is not the case that $F_{r, κ} (I_{n}) \leq F_{r, κ} (X) for every X \in E_{m}^{blk} .$ Moreover, for any family $(X_{κ})_{κ \in R}$ such that, for every $κ > 0$ , $X_{κ} \in E_{m}^{blk} and F_{r, κ} (X_{κ}) \leq F_{r, κ} (X) for every X \in E_{m}^{blk},$ each matrix entry converges to the corresponding entry of $I_{n}$ : $(X_{κ})_{ij} ⟶ (I_{n})_{ij} as κ \to \infty$ for every $i, j \in {1, \dots, n}$ .

⊢ Lean

Theorem 2 separates implementability from optimality. The iid law $P_{iid}$ belongs to the block-exchangeable design class and attains $I_{n}$ , but this implementable covariance is a relaxed minimizer at finite robustness only when $a + 3 b = 2 m$ and $r = 2 b (a + b)$ . Off that affine-balanced locus, relaxed minimizers converge entrywise to $I_{n}$ as $κ \to \infty$ , yet no positive finite value of $κ$ makes $I_{n}$ itself optimal. Thus robustness can make iid assignment an asymptotic limiting target without making it an exact finite- $κ$ solution.

Together, Theorem 1 and Theorem 2 identify two implementable covariances whose roles are sharply different. The cut covariance is exactly optimal throughout the stated strict cut region, yielding zero implementability loss there. The iid covariance is implementable everywhere under the maintained homophily conditions, with exact relaxed optimality on the stated affine-balanced locus and limiting optimality elsewhere as robustness diverges. The next section turns to parameter regions with strictly positive implementability loss.

Positive loss and sharp computation

The preceding section identifies two implementable covariances that can solve the relaxed problem exactly. We now study relaxed points in $E_{m}^{blk}$ lying beyond the covariances attainable by balanced ${\pm 1}$ assignment laws. This is the same basic tension that appears in correlation and semidefinite relaxations more broadly: the convex benchmark can contain exposed points beyond the original discrete objects (Goemans et al., 1995; Deza et al., 1997). In the present two-block design problem, the obstruction is finite and arithmetical. When $m$ is odd, each realized block sum has odd parity, imposing a positive-mass restriction away from the pure within-block spectral direction.

The next result gives a parameter region in which this obstruction is binding. It uses two-block homophily from Assumption 1, the low-scale condition from Assumption 3, and the odd-block condition from Assumption 4. For robustness weights in the stated range, the relevant relaxed covariance is the spread covariance $X_{spread}$ , the vertex with spectral coordinates $(m / (m - 1), 0, 0)$ . The theorem states that, in a nonempty interval of pseudoinverse weights, this relaxed point is uniquely optimal but not implementable.

Theorem 3 [thm:gap-window] (Positive-Gap Window).

Suppose Assumption 1 and Assumption 3 hold for the two-block model with block size $m$ and weights $a, b$ . Let $q = 2 (m - 1), κ_{gap} (m, a, b) = \frac{( 2 m - a - 3 b ) ( a - b ) q}{a + b},$ and $r_{cut, gap} (m, a, b, κ) = max {0, 2 b (a + b) (1 - \frac{κ}{a - b})} .$ Define $R_{x}^{-} (m, a, b, κ) = 2 b (a + b) (1 + \frac{κ}{( a - b ) q}), R_{x}^{+} (m, a, b, κ) = (a + b) (2 m - a - b - \frac{κ}{q}),$ and $r_{gap}^{-} (m, a, b, κ) = \frac{R _{x}^{-} ( m , a , b , κ ) + R _{x}^{+} ( m , a , b , κ )}{2}, r_{gap}^{+} (m, a, b, κ) = R_{x}^{+} (m, a, b, κ) .$

Then the following two statements hold.

(Odd block size.) If Assumption 4 holds, then for every $κ$ satisfying $0 \leq κ < κ_{gap} (m, a, b),$ one has $r_{cut, gap} (m, a, b, κ) < r_{gap}^{-} (m, a, b, κ) < r_{gap}^{+} (m, a, b, κ) .$ Moreover, for every $r_{gap}^{-} (m, a, b, κ) < r < r_{gap}^{+} (m, a, b, κ),$ the spread covariance $X_{spread}$ belongs to $E_{m}^{blk}$ , and it is the unique strict minimizer of the design objective $F_{r, κ}$ from Definition 6 over $E_{m}^{blk}$ : for every $X \in E_{m}^{blk}$ with $X \neq = X_{spread}$ , $F_{r, κ} (X_{spread}) < F_{r, κ} (X) .$ At the same time, $X_{spread} \in / C_{m}^{\pm},$ where $C_{m}^{\pm}$ is the implementable covariance class of Definition 5, and the implementability loss of Definition 7 satisfies $Δ_{m}^{\pm} (r, κ) > 0.$
(Even block size.) If $m$ is even, then every covariance in the block elliptope is implementable: $E_{m}^{blk} \subseteq C_{m}^{\pm} .$

⊢ Lean

Theorem 3 is the paper’s positive-loss statement. Under its two-block homophily, low-scale, and odd-community hypotheses, the upper bound $κ_{gap} (m, a, b)$ defines a robustness range in which the interval $(r_{gap}^{-}, r_{gap}^{+})$ is nonempty and lies strictly beyond the cut-side comparison threshold $r_{cut, gap}$ . Inside that interval, the relaxed optimum is not merely one unattainable minimizer among many; it is the unique strict minimizer over $E_{m}^{blk}$ . Since $X_{spread} \in / C_{m}^{\pm}$ , imposing implementability necessarily raises the objective value, giving $Δ_{m}^{\pm} (r, κ) > 0$ .

The even- $m$ clause marks the opposite parity case. When each block can have zero sign sum, every relaxed covariance in the block elliptope slice is generated by some block-exchangeable sign law. Thus Theorem 3 ties positive loss specifically to the odd-block parity restriction.

The interval result is deliberately local. It identifies one open region where the spread covariance is the relaxed optimum and the loss is strictly positive, but it does not assert a closed-form global boundary for exact attainability outside that region. For computation at arbitrary $r$ and $κ$ , the relevant object is instead the sharp finite active-set formula below.

The formula works in the reduced spectral simplex $T_{m}$ , obtained from Lemma 1: the block symmetry diagonalizes every $X (u, v)$ into three eigendirections, with coordinates $x = 1 - u$ on the within-block contrast space (multiplicity $q = 2 (m - 1)$ ), $y = 1 + (m - 1) u - m v$ on the between-block contrast direction, and $z_{sp} = 1 + (m - 1) u + m v$ on the all-ones (aggregate) direction; the subscript “ $sp$ ” marks this last, spread-across-all-units coordinate and distinguishes it from an ambient sign index. In these coordinates $F_{r, κ}$ becomes the scalar objective $ϕ_{r, κ} (x, y, z_{sp}) = c_{x} x + c_{y} y + c_{z} z_{sp} + κ q x^{2} + y^{2} + z_{sp}^{2}$ , and implementability adds only the parity truncation $d_{m} \leq y + z_{sp}$ , with $d_{m} = 0$ for even block sizes and $d_{m} = 2/ m$ for odd block sizes. The theorem’s remaining ingredients are the following finite objects, established in Section C (Lemma 6 and Lemma 7). For linear coefficients $α^{♯} = (c_{x} / q, c_{y}, c_{z})$ and norm weights $β^{♯} = (1/ q, 1, 1)$ , the weighted-simplex objective is $Φ_{α^{♯}, β^{♯}, κ} (t) = \sum_{i} α_{i}^{♯} t_{i} + κ \sum_{i} β_{i}^{♯} t_{i}^{2}$ on the simplex of mass $2 m$ ; an admissible active support–multiplier pair $(S, λ)$ is a nonempty $S \subseteq {x, y, z_{sp}}$ and $λ \in R$ with $\sum_{i \in S} (λ - α_{i}^{♯})^{2} / β_{i}^{♯} = κ^{2}$ , $α_{i}^{♯} < λ$ on $S$ , and $λ \leq α_{j}^{♯}$ off $S$ ; the associated active-set point $t^{S, λ}$ puts mass $2 m ((λ - α_{i}^{♯}) / β_{i}^{♯}) / \sum_{h \in S} (λ - α_{h}^{♯}) / β_{h}^{♯}$ on each $i \in S$ and zero off $S$ ; $truncSelector$ returns the endpoint or interior optimizer of $Φ$ restricted to the truncation segment ${y + z_{sp} = d_{m}}$ ; and $ρ_{⋆} (m, a, b, r, κ)$ is the resulting constrained-minus-unconstrained reduced value, i.e. the minimum of $ϕ_{r, κ}$ over $T_{m} \cap {y + z_{sp} \geq d_{m}}$ minus its minimum over $T_{m}$ . The theorem shows this $ρ_{⋆}$ equals the implementability loss and gives its finite case split.

Theorem 4 [thm:sharp-rho-star] (Sharp Rounding Loss).

Under Assumption 1, fix $r, κ \in [0, \infty)$ . Let $q = 2 (m - 1), c_{x} = q ((a + b) + \frac{r}{a + b}), c_{y} = 2 b + \frac{r}{2 b}, c_{z} = 2 m,$ let $T_{m} = {(x, y, z_{sp}) : x, y, z_{sp} \geq 0, q x + y + z_{sp} = 2 m},$ let $ϕ_{r, κ} (x, y, z_{sp}) = c_{x} x + c_{y} y + c_{z} z_{sp} + κ q x^{2} + y^{2} + z_{sp}^{2},$ and let $d_{m} = 0$ if $m$ is even and $d_{m} = 2/ m$ if $m$ is odd. Then:

(Sharp equality and range.) $ρ_{⋆} (m, a, b, r, κ) = Δ_{m}^{\pm} (r, κ), ρ_{⋆} (m, a, b, r, κ) \geq 0, Δ_{m}^{\pm} (r, κ) \geq 0,$ where $Δ_{m}^{\pm}$ is the implementability gap of Definition 7.
(Zero loss.) $ρ_{⋆} (m, a, b, r, κ) = 0$ if and only if there exists $(x, y, z_{sp}) \in T_{m}$ such that $ϕ_{r, κ} (x, y, z_{sp}) \leq ϕ_{r, κ} (x^{'}, y^{'}, z_{sp}^{'}) for every (x^{'}, y^{'}, z_{sp}^{'}) \in T_{m},$ and $d_{m} \leq y + z_{sp} .$
(Strict robustness.) If $κ > 0$ , then there is a unique relaxed minimizer of $ϕ_{r, κ}$ over $T_{m}$ . Moreover, $ρ_{⋆} (m, a, b, r, κ) = 0$ if and only if every relaxed minimizer $(x, y, z_{sp}) \in T_{m}$ satisfies $d_{m} \leq y + z_{sp} .$
(Linear case.) If $κ = 0$ , then for every $(x, y, z_{sp}) \in T_{m}$ , the point $(x, y, z_{sp})$ minimizes $ϕ_{r, 0}$ over $T_{m}$ if and only if $x \neq = 0 \Rightarrow \frac{c _{x}}{q} \leq c_{y} and \frac{c _{x}}{q} \leq c_{z},$ $y \neq = 0 \Rightarrow c_{y} \leq \frac{c _{x}}{q} and c_{y} \leq c_{z},$ and $z_{sp} \neq = 0 \Rightarrow c_{z} \leq \frac{c _{x}}{q} and c_{z} \leq c_{y} .$
(Active-set formula.) If $κ > 0$ , then there exist an active support $S \subseteq {x, y, z_{sp}}$ and a multiplier $λ \in R$ such that $S$ and $λ$ are admissible for $α^{♯} = (\frac{c _{x}}{q}, c_{y}, c_{z}), β^{♯} = (\frac{1}{q}, 1, 1), κ .$ Writing $t^{S, λ} = (t_{x}^{S, λ}, t_{y}^{S, λ}, t_{z}^{S, λ})$ for the associated active-set point on the simplex of mass $2 m$ , the reduced point $(\frac{t _{x}^{S, λ}}{q}, t_{y}^{S, λ}, t_{z}^{S, λ})$ belongs to $T_{m}$ , minimizes $ϕ_{r, κ}$ over $T_{m}$ , and the relaxed reduced value is $2 m λ .$
(Truncation correction.) If no relaxed minimizer $(x, y, z_{sp}) \in T_{m}$ satisfies $d_{m} \leq y + z_{sp}$ , then the implementable reduced value equals the weighted-simplex objective with coefficients $α^{♯}$ , weights $β^{♯}$ , and robustness weight $κ$ , evaluated at the point on the truncation segment $H_{d_{m}} = {(2 m - d_{m}, s, d_{m} - s) : 0 \leq s \leq d_{m}}$ selected by $truncSelector (2 m, d_{m}, α^{♯}, β^{♯}, κ)$ : $val_{impl} (m, a, b, r, κ) = Φ_{α^{♯}, β^{♯}, κ} (2 m - d_{m}, s_{⋆}, d_{m} - s_{⋆}),$ where $s_{⋆} = truncSelector (2 m, d_{m}, α^{♯}, β^{♯}, κ) .$
(Even block size.) If $m$ is even, then $ρ_{⋆} (m, a, b, r, κ) = 0.$

⊢ Lean

Theorem 4 turns the implementability question into a finite calculation. The sharp loss $ρ_{⋆} (m, a, b, r, κ)$ is exactly the implementability loss $Δ_{m}^{\pm} (r, κ)$ , so the formula is not an approximation to the rounding penalty. Zero loss occurs precisely when at least one relaxed minimizer satisfies the parity-induced lower bound $d_{m} \leq y + z_{sp}$ . When $κ > 0$ , the active-set result yields a unique relaxed minimizer, and the zero-loss condition can be checked at that point alone.

The active-set part supplies the promised finite case split. The coefficients $α^{♯} = (c_{x} / q, c_{y}, c_{z})$ and weights $β^{♯} = (1/ q, 1, 1)$ convert the reduced objective into a weighted simplex problem over total mass $2 m$ . For positive robustness, an admissible support $S$ and multiplier $λ$ identify the relaxed minimizer and its value. If that minimizer violates the implementability truncation, the remaining optimization is one-dimensional: the implementable value is obtained on the segment $H_{d_{m}}$ by the selector appearing in Theorem 4. The theorem thereby gives a complete finite procedure for computing $Δ_{m}^{\pm} (r, κ)$ for any admissible $m, a, b, r, κ$ .

The two main results in this section therefore play complementary roles. Theorem 3 provides an interpretable open region in which the relaxation has a strictly unattainable optimum for odd block sizes. Theorem 4 gives the exact loss everywhere under Assumption 1, including the linear case $κ = 0$ , the unique-minimizer case $κ > 0$ , and the even-block case where the loss vanishes. For interference-aware randomized design, the practical implication is a two-step calculation: solve the covariance relaxation, then check its optimizer against the finite sign-assignment restrictions and apply the exact active-set adjustment when needed.

A worked example and parameter map.

Take $m = 3$ , $a = 2$ , $b = 1$ , and $κ = 0$ ; these satisfy homophily ( $a > b > 0$ ) and the low-scale regime ( $a + 3 b = 5 < 2 m = 6$ ). Here $q = 4$ , the parity truncation is $d_{3} = 2/3$ , and the reduced coefficients are $c_{x} = q ((a + b) + r / (a + b)) = 4 (3 + r /3)$ , $c_{y} = 2 b + r / (2 b) = 2 + r /2$ , and $c_{z} = 2 m = 6$ . The gap-window robustness bound is $κ_{gap} = (2 m - a - 3 b) (a - b) q / (a + b) = 2/3$ , so $κ = 0$ lies in the admissible range. Mapping over $r \geq 0$ then exhibits all three regimes of the theory. For $r < r_{cut} = min {2 b (a + b), 2 b (2 m - 2 b)} = min {6, 8} = 6$ , the cut covariance $X_{cut} = (0, 6, 0)$ is the unique relaxed optimum and is implementable, so $Δ_{3}^{\pm} = 0$ (Theorem 1). For $r$ in the gap window $(r_{gap}^{-}, r_{gap}^{+}) = (7.5, 9)$ , the spread covariance $X_{spread} = (3/2, 0, 0)$ is the unique relaxed optimum but is not implementable (Theorem 3). At $r = 8$ , for instance, the unconstrained reduced optimum is at $X_{spread}$ with value $c_{x} \cdot \frac{3}{2} = 34$ , while the implementable optimum lies on the parity slice $y + z_{sp} = 2/3$ at $(x, y, z_{sp}) = (4/3, 2/3, 0)$ with value $308/9$ ; hence $Δ_{3}^{\pm} (8, 0) = \frac{308}{9} - 34 = \frac{2}{9} \approx 0.222,$ a strictly positive but, in this instance, modest price relative to the optimal value $34$ (about $0.65%$ ). For even community size the picture collapses: $d_{m} = 0$ , the parity truncation is vacuous, and $Δ_{m}^{\pm} \equiv 0$ throughout. This single example only illustrates the three regimes for one parameter choice; it does not establish that the loss is generally small or generally negligible, and Theorem 4 should be used to compute $Δ_{m}^{\pm}$ at any specific $(m, a, b, r, κ)$ of interest. How large the loss can become as $a, b, r, κ$ scale is not settled here and is left open.

Table 1 summarizes the regimes and the result that governs each.

Regimes of the two-block implementability problem. Coordinates are the reduced spectral coordinates $(x, y, z_{sp})$ ; “low-scale” abbreviates $a + 3 b < 2 m$ with the robustness range of Theorem 3.
Regime	Relaxed optimum	Implementable?	Loss $Δ_{m}^{\pm}$
Cut ( $r < r_{cut}$ )	$X_{cut} = (0, 2 m, 0)$	yes (via $P_{cut}$ )	$0$ (Thm Theorem 1)
Robust locus ( $a + 3 b = 2 m$ , $r = 2 b (a + b)$ )	$I_{n} = (1, 1, 1)$	yes (via $P_{iid}$ )	$0$ (Thm Theorem 2)
Odd-parity window ( $m$ odd, low-scale)	$X_{spread} = (\frac{m}{m - 1}, 0, 0)$	no	$> 0$ (Thm Theorem 3)
Even $m$	—	every $X \in E_{m}^{blk}$	$0$ (Thm Theorem 4)
General $(m, a, b, r, κ)$	active-set point	iff parity slice met	$ρ_{⋆}$ (Thm Theorem 4)

Discussion and extensions

Relation to covariance-based network design.

The design criterion and elliptope relaxation build on covariance-based experimental design for network interference, particularly the semidefinite formulation of Thiyageswaran et al. (2026); Boyd et al. (2004) supplies convex-optimization background, and Goemans et al. (1995); Deza et al. (1997) provide canonical elliptope and cut-polytope context. This paper contributes an exact implementability theory for the homophilous two-block family: a joint symmetry reduction of relaxed covariances and implementable laws, an odd-parity obstruction producing positive loss, and a finite active-set correction computing $Δ_{m}^{\pm}$ exactly.

Viewed abstractly, $C_{m}^{\pm}$ is a moment set for block-exchangeable Rademacher vectors and a two-coordinate projection of the correlation polytope. The paper pins down the exact boundary of this low-dimensional exchangeable slice through the odd-block parity truncation $y + z_{sp} \geq 2/ m$ , then converts that boundary into the exact rounding loss. Future work can connect this family-specific characterization more fully to general correlation-polytope and exchangeable-moment results.

The results above give a finite-sample account of when a covariance relaxation can be read literally as a randomized design. In the two-block homophily model, the relaxed block elliptope $E_{m}^{blk}$ serves both as a computational device and as a benchmark for exact implementability by a sign-symmetric, block-exchangeable ${\pm 1}$ assignment law. Theorem 1 gives a region in which the relaxed optimum is generated by an assignment law, whereas Theorem 3 gives a region with a uniquely optimal relaxed covariance and strictly positive implementability loss.

For experimental design under interference, the covariance matrix is a property of the assignment mechanism, and implementation requires a covariance induced by a randomization law. The implementability loss $Δ_{m}^{\pm} (r, κ)$ therefore has a direct design interpretation: it is the exact objective-value price of returning from the relaxed covariance problem to feasible randomized assignment. Theorem 4 computes that price through a finite active-set calculation.

The iid result points in the opposite direction. Independent fair assignment is always available as a randomized design and has a familiar role in design-based inference. Theorem 2 identifies exact finite-robustness optimality on the affine-balanced locus $a + 3 b = 2 m$ and $r = 2 b (a + b)$ , while relaxed minimizers elsewhere converge to $I_{n}$ as $κ$ grows. Thus robustness rationalizes iid assignment either as an exact solution on the locus or as a limiting target elsewhere.

The positive-loss result is arithmetic. For odd $m$ , each realized block sum has absolute value at least one. Under the hypotheses and robustness range stated in Theorem 3, this parity restriction binds and places the uniquely optimal spread covariance outside $C_{m}^{\pm}$ . For even $m$ , every relaxed block covariance is implementable in the maintained symmetric model. The theorem therefore isolates odd-block parity as the source of positive loss.

Limitations and future work

The two-block structure is deliberately stylized, but it captures a common empirical feature of networked populations: ties and exposures are often stronger within social groups than between them. Homophily and community structure are central themes in social network analysis (McPherson et al., 2001; Newman, 2002), and stochastic block models provide a canonical probabilistic language for such clustered networks (Holland et al., 1983; Abbe, 2018). Field and policy experiments with interference often face analogous clustering through villages, schools, households, online neighborhoods, or other exposure groups (Banerjee et al., 2013; Baird et al., 2018; Ugander et al., 2020; Li et al., 2021). The present model abstracts from those empirical details in order to isolate an exact design question: after symmetry reduction, which relaxed covariance matrices are generated by actual sign assignments?

Several extensions follow naturally, but they require additional arguments beyond the statements in this paper. The present results do not cover unequal block sizes, where both the spectral reduction and the block-sum lattice would require new arguments. The present results also do not cover more than two communities; the three-coordinate reduction $(x, y, z_{sp})$ and the implementability characterization would require modification. In those settings, one should not expect the parity correction $d_{m}$ or the active-set formula in Theorem 4 to carry over without modification.

A second extension concerns additional restrictions on the randomization scheme. The class $P_{m}^{sym}$ imposes sign symmetry and block exchangeability, but it does not require a fixed treated count in every realization, nor does it impose covariate balance, rerandomization acceptance rules, or cluster-level assignment constraints. Such restrictions are common in empirical practice and can be important for finite-sample precision and credibility (Sävje, 2021; Zigler et al., 2018). They would shrink the implementable covariance class and could introduce losses even in cases where $E_{m}^{blk} \subseteq C_{m}^{\pm}$ under the present assumptions.

A third issue is that the graph itself is treated as fixed. In applications, measured networks may be incomplete, exposure weights may be estimated, and the relevant interference neighborhood may be uncertain. The objective $F_{r, κ}$ can be interpreted conditionally on the chosen graph weights, but the results here do not address robustness to network measurement error or to alternative exposure mappings. Those questions are important for empirical deployment because different plausible graphs can imply different design priorities, especially when homophily is strong.

Finally, the analysis is finite-sample throughout. The exact formulas are indexed by $m, a, b, r, κ$ , and the odd-block obstruction is stated at the finite block size used by the design. Although the parity truncation becomes numerically smaller as $m$ grows, the consequences for objective values depend on the full set of coefficients in Theorem 4. Any asymptotic simplification should therefore be derived from the finite active-set expression rather than assumed from the geometry alone.

Appendices

Reduced geometry and proof ingredients

This appendix makes visible the auxiliary geometry behind the two main optimization statements: the reduced coordinates, vertex certificates, parity restriction, and finite active-set calculation used in Theorem 3 and Theorem 4. The reduction is a low-dimensional convex-analytic one: the block symmetry turns the covariance problem into a weighted simplex problem, in the same general spirit as convex optimization (Boyd et al., 2004) and elliptope relaxations for discrete optimization (Goemans et al., 1995; Deza et al., 1997).

The first ingredient identifies the spectral coordinates in which the block elliptope becomes a simplex and the objective becomes a scalar function.

Lemma 1 [lem:block-spectral-coordinates] (Block Spectral Coordinates).

For any real numbers $r, κ, u, v$ , assume:

(Homophily.) Assumption 1 holds for the block size $m$ and weights $a, b$ .
(Spectral coordinates.) Set $q = 2 (m - 1), x = 1 - u, y = 1 + (m - 1) u - m v, z_{sp} = 1 + (m - 1) u + m v .$
(Reduced coefficients.) Set $c_{x} = q ((a + b) + \frac{r}{a + b}), c_{y} = 2 b + \frac{r}{2 b}, c_{z} = 2 m .$

Then the block covariance matrix $X (u, v)$ belongs to the block elliptope $E_{m}^{blk}$ if and only if $x \geq 0, y \geq 0, z_{sp} \geq 0, q x + y + z_{sp} = 2 m .$ Moreover, for the design objective of Definition 6, $F_{r, κ} (X (u, v)) = c_{x} x + c_{y} y + c_{z} z_{sp} + κ q x^{2} + y^{2} + z_{sp}^{2} .$ Finally, $X_{cut} = X (1, - 1) and (1 - 1, 1 + (m - 1) \cdot 1 - m (- 1), 1 + (m - 1) \cdot 1 + m (- 1)) = (0, 2 m, 0),$ while $I_{n} = X (0, 0) and (1 - 0, 1 + (m - 1) \cdot 0 - m \cdot 0, 1 + (m - 1) \cdot 0 + m \cdot 0) = (1, 1, 1) .$

⊢ Lean

Proof of Lemma 1.

Throughout write $n = 2 m$ , $q = 2 (m - 1)$ , and $x = 1 - u, y = 1 + (m - 1) u - m v, z_{sp} = 1 + (m - 1) u + m v .$ Assumption 1 gives $m \geq 2$ , hence $q > 0$ and $m > 0$ , and it gives $a > b > 0$ , hence $a + b > 0$ and $2 b > 0$ ; these are the only nonvanishing denominators used below.

Step 1 (the two parameters are read off from the matrix). Since $∣ A_{m} ∣ = m \geq 2$ , we may pick two distinct indices $i, j \in A_{m}$ , and since $∣ B_{m} ∣ = m \geq 1$ we may pick $k \in B_{m}$ . By the entry description of $X (u, v)$ , $X (u, v)_{ij} = u, X (u, v)_{ik} = v .$ Consequently $X (u, v) = X (u^{'}, v^{'})$ forces $u^{'} = u$ and $v^{'} = v$ : the block-symmetric parameterization is injective. Therefore the only representation of $X (u, v)$ as a member of $E_{m}^{blk}$ in the sense of Definition 4 is the one with parameters $(u, v)$ , and $X (u, v) \in E_{m}^{blk} ⟺ 1 - u \geq 0, 1 + (m - 1) u - m v \geq 0, 1 + (m - 1) u + m v \geq 0,$ that is, $x \geq 0$ , $y \geq 0$ , $z_{sp} \geq 0$ . Moreover the affine identity $q x + y + z_{sp} = 2 (m - 1) (1 - u) + (1 + (m - 1) u - m v) + (1 + (m - 1) u + m v) = 2 m$ holds for all $u, v$ , the $u$ -terms and the $v$ -terms cancelling. Hence block-elliptope membership is equivalent to $(x, y, z_{sp}) \in T_{m}$ , which is the first assertion.

Step 2 (two pair-counting identities). Call a matrix $w \in R^{n \times n}$ block-patterned with data $(d, σ, c)$ if $w_{ii} = d$ for every $i$ , $w_{ij} = σ$ whenever $i \neq = j$ lie in the same community, and $w_{ij} = c$ whenever $i$ and $j$ lie in opposite communities. Among the $n^{2}$ ordered index pairs there are $n = 2 m$ diagonal pairs, $2 m (m - 1)$ same-community off-diagonal pairs, and $2 m \cdot m$ opposite-community pairs, so $i = 1 \sum n j = 1 \sum n w_{ij} = 2 m d + 2 m (m - 1) σ + 2 m^{2} c .$

With the community sign vector $s \in R^{n}$ defined by $s_{i} = 1$ for $i \in A_{m}$ and $s_{i} = - 1$ for $i \in B_{m}$ , the sign product $s_{i} s_{j}$ equals $+ 1$ on diagonal and same-community pairs and $- 1$ on opposite-community pairs, so the same count with the sign weight gives $i = 1 \sum n j = 1 \sum n s_{i} s_{j} w_{ij} = 2 m d + 2 m (m - 1) σ - 2 m^{2} c .$

Step 3 (the four terms of the objective). The matrix $X (u, v)$ is block-patterned with data $(1, u, v)$ . Applying the unsigned count with $(d, σ, c) = (1, u, v)$ gives the balance term $tr (J_{n} X (u, v)) = i, j \sum X (u, v)_{ij} = 2 m + 2 m (m - 1) u + 2 m^{2} v = 2 m (1 + (m - 1) u + m v) = 2 m z_{sp} .$

The entrywise square of $X (u, v)$ is block-patterned with data $(1, u^{2}, v^{2})$ , so the same count gives $∥ X (u, v) ∥_{S_{2}}^{2} = 2 m + 2 m (m - 1) u^{2} + 2 m^{2} v^{2}$ ; on the other hand, expanding the three spectral coordinates, $q x^{2} + y^{2} + z_{sp}^{2} = 2 (m - 1) (1 - u)^{2} + 2 (1 + (m - 1) u)^{2} + 2 m^{2} v^{2} = 2 m + 2 m (m - 1) u^{2} + 2 m^{2} v^{2},$ the linear-in- $u$ terms $- 4 (m - 1) u$ and $+ 4 (m - 1) u$ cancelling. Hence $∥ X (u, v) ∥_{S_{2}} = q x^{2} + y^{2} + z_{sp}^{2} .$

Next, $tr X (u, v) = n = 2 m$ because the diagonal is constant equal to one. Let $Π_{1} = \frac{1}{n} J_{n}, Π_{s} = \frac{1}{n} s s^{⊤}$ be the orthogonal projections onto the all-ones direction and onto the community-sign direction. Dividing the two displays of Step 2 (applied with $(d, σ, c) = (1, u, v)$ ) by $n = 2 m$ gives $tr (Π_{1} X (u, v)) = z_{sp}, tr (Π_{s} X (u, v)) = \frac{2 m + 2 m ( m - 1 ) u - 2 m ^{2} v}{2 m} = y .$

The pseudoinverse $L_{m}^{†}$ enters the objective only through its spectral action, which on the two-block graph is $L_{m}^{†} = \frac{1}{a + b} (I_{n} - Π_{1} - Π_{s}) + \frac{1}{2 b} Π_{s},$ i.e. eigenvalue $1/ (a + b)$ on the within-community contrast space, $1/ (2 b)$ on the community-sign direction, and $0$ on the all-ones direction. Therefore, using $tr X (u, v) = 2 m$ and the affine identity $2 m - y - z_{sp} = q x$ of Step 1, $tr (L_{m}^{†} X (u, v)) = \frac{2 m - z _{sp} - y}{a + b} + \frac{y}{2 b} = \frac{q x}{a + b} + \frac{y}{2 b} .$ For the graph term, every vertex has the same weighted degree $j \sum W_{ij} = (m - 1) \frac{a}{m} + m \frac{b}{m} = \frac{( m - 1 ) a}{m} + b,$ because each vertex has $m - 1$ same-community neighbours of weight $a / m$ and $m$ opposite-community neighbours of weight $b / m$ . Thus $L_{m}$ is block-patterned with data $((m - 1) a / m + b, - a / m, - b / m)$ , and the matrix with entries $(L_{m})_{ij} X (u, v)_{ij}$ is block-patterned with data $((m - 1) a / m + b, - (a / m) u, - (b / m) v)$ . Since $X (u, v)$ is symmetric, the unsigned count gives $tr (L_{m} X (u, v)) = 2 m (\frac{( m - 1 ) a}{m} + b) - 2 m (m - 1) \frac{a}{m} u - 2 m^{2} \frac{b}{m} v = 2 (m - 1) a (1 - u) + 2 mb (1 - v),$

and expanding both sides shows that this equals the reduced form $2 (m - 1) a (1 - u) + 2 mb (1 - v) = q (a + b) x + 2 b y .$

Step 4 (assembling the objective). Substituting the four displays of Step 3 into Definition 6, $F_{r, κ} (X (u, v)) = (q (a + b) x + 2 b y) + r (\frac{q x}{a + b} + \frac{y}{2 b}) + κ q x^{2} + y^{2} + z_{sp}^{2} + 2 m z_{sp} = q ((a + b) + \frac{r}{a + b}) x + (2 b + \frac{r}{2 b}) y + 2 m z_{sp} + κ q x^{2} + y^{2} + z_{sp}^{2} = c_{x} x + c_{y} y + c_{z} z_{sp} + κ q x^{2} + y^{2} + z_{sp}^{2},$ which is the asserted reduced form.

Step 5 (the two corner readings). The cut covariance is $X_{cut} = s s^{⊤}$ , whose entries are $s_{i}^{2} = 1$ on the diagonal, $+ 1$ on same-community pairs, and $- 1$ on opposite-community pairs; hence $X_{cut} = X (1, - 1)$ , and substituting $u = 1$ , $v = - 1$ , $(1 - 1, 1 + (m - 1) - m (- 1), 1 + (m - 1) + m (- 1)) = (0, 2 m, 0) .$

Likewise $I_{n}$ has entries $1$ on the diagonal and $0$ off it, so $I_{n} = X (0, 0)$ , and substituting $u = v = 0$ , $(1 - 0, 1 + (m - 1) \cdot 0 - m \cdot 0, 1 + (m - 1) \cdot 0 + m \cdot 0) = (1, 1, 1) .$

∎

Lemma 1 is the coordinate change used throughout the main text. It replaces the two covariance parameters $u, v$ by nonnegative spectral coordinates satisfying one affine constraint. In these coordinates, the cut covariance is the vertex $(0, 2 m, 0)$ , the iid covariance is the center-like point $(1, 1, 1)$ , and the objective separates into a linear part plus a weighted Euclidean norm.

The next two statements are vertex certificates. They give simple coefficient inequalities under which either the cut vertex or the spread vertex is the unique minimizer of the reduced problem.

Lemma 2 [lem:cut-vertex-certificate] (Cut Vertex Certificate).

Let $m$ be fixed and write $q = 2 (m - 1)$ . Suppose that

(Positive spectral multiplicity.) $q > 0$ .
(Nonnegative robustness.) $κ \geq 0$ .
(Cut-side coefficient separation.) The coefficients satisfy $\frac{c _{x}}{q} > c_{y} + κ and c_{z} > c_{y} + κ .$

Then $(0, 2 m, 0) \in T_{m}$ , where $T_{m} = {(x, y, z_{sp}) : x \geq 0, y \geq 0, z_{sp} \geq 0, q x + y + z_{sp} = 2 m} .$ Moreover, for every $(x, y, z_{sp}) \in T_{m}$ with $(x, y, z_{sp}) \neq = (0, 2 m, 0)$ , $c_{x} \cdot 0 + c_{y} (2 m) + c_{z} \cdot 0 + κ q \cdot 0^{2} + (2 m)^{2} + 0^{2} < c_{x} x + c_{y} y + c_{z} z_{sp} + κ q x^{2} + y^{2} + z_{sp}^{2} .$ Thus $(0, 2 m, 0)$ is the unique minimizer on $T_{m}$ of the reduced objective.

⊢ Lean

Proof of Lemma 2.

Write $q = 2 (m - 1)$ and $M = 2 m$ , and abbreviate the reduced objective by $ϕ (x, y, z_{sp}) = c_{x} x + c_{y} y + c_{z} z_{sp} + κ q x^{2} + y^{2} + z_{sp}^{2},$ so that the claim is that $(0, M, 0)$ is the unique minimizer of $ϕ$ on $T_{m}$ . The hypothesis $q > 0$ means $m > 1$ , so $M = 2 m > 0$ .

Step 1 (feasibility). The point $(0, M, 0)$ has nonnegative coordinates and satisfies $q \cdot 0 + M + 0 = M = 2 m$ ; hence $(0, M, 0) \in T_{m}$ .

Step 2 (the value at the cut vertex). Since $M > 0$ , $q \cdot 0^{2} + M^{2} + 0^{2} = M^{2} = M$ , so $ϕ (0, M, 0) = c_{y} M + κ M = (c_{y} + κ) M .$

Step 3 (a lower bound for the norm term). Let $(x, y, z_{sp}) \in T_{m}$ . Because $q > 0$ , both $q x^{2} \geq 0$ and $z_{sp}^{2} \geq 0$ , so $y^{2} \leq q x^{2} + y^{2} + z_{sp}^{2}, hence y \leq q x^{2} + y^{2} + z_{sp}^{2},$ and multiplying by $κ \geq 0$ gives $κ y \leq κ q x^{2} + y^{2} + z_{sp}^{2}$ . Therefore $c_{x} x + c_{y} y + c_{z} z_{sp} + κ y \leq ϕ (x, y, z_{sp}) .$

Step 4 (the coefficient separation in cleared form). Multiplying the hypothesis $c_{x} / q > c_{y} + κ$ by $q > 0$ , and taking the hypothesis $c_{z} > c_{y} + κ$ as it stands, gives $c_{x} - q c_{y} - q κ > 0, c_{z} - c_{y} - κ > 0.$

Step 5 (some off- $y$ mass is present). Suppose now in addition $(x, y, z_{sp}) \neq = (0, M, 0)$ . If $x = 0$ and $z_{sp} = 0$ , the simplex equation $q x + y + z_{sp} = M$ would force $y = M$ , i.e. the point would be $(0, M, 0)$ ; hence $x > 0$ or $z_{sp} > 0$ . Since $x \geq 0$ and $z_{sp} \geq 0$ and both coefficients in Step 4 are strictly positive, the sum of the two products has a strictly positive term and a nonnegative one: $0 < (c_{x} - q c_{y} - q κ) x + (c_{z} - c_{y} - κ) z_{sp} .$

Step 6 (the difference identity). Substituting $M = q x + y + z_{sp}$ into $(c_{y} + κ) M$ and cancelling the $y$ -terms gives the identity $(c_{x} x + c_{y} y + c_{z} z_{sp} + κ y) - (c_{y} + κ) M = (c_{x} - q c_{y} - q κ) x + (c_{z} - c_{y} - κ) z_{sp} .$ Combining it with Step 5, $(c_{y} + κ) M < c_{x} x + c_{y} y + c_{z} z_{sp} + κ y .$

Step 7 (conclusion). Chaining Steps 2, 6 and 3, $ϕ (0, M, 0) = (c_{y} + κ) M < c_{x} x + c_{y} y + c_{z} z_{sp} + κ y \leq ϕ (x, y, z_{sp}),$ which is the asserted strict inequality $c_{x} \cdot 0 + c_{y} (2 m) + c_{z} \cdot 0 + κ q \cdot 0^{2} + (2 m)^{2} + 0^{2} < c_{x} x + c_{y} y + c_{z} z_{sp} + κ q x^{2} + y^{2} + z_{sp}^{2}$ for every $(x, y, z_{sp}) \in T_{m}$ other than $(0, 2 m, 0)$ . In particular no other point of $T_{m}$ attains the value $ϕ (0, 2 m, 0)$ , so the cut vertex is the unique minimizer.

∎

Lemma 2 is the reduced certificate underlying the cut exactness result. The coefficient separation says that moving mass away from the $y$ -coordinate toward either the within-block spectral coordinate or the aggregate coordinate is too costly, even after accounting for the robustness term.

Lemma 3 [lem:spread-vertex-certificate] (Spread Vertex Certificate).

Let $m \in N$ , let $c_{x}, c_{y}, c_{z}, κ \in R$ , and set $q = 2 (m - 1)$ . Suppose that

(Positive multiplicity.) $q > 0$ .
(Nonnegative robustness.) $κ \geq 0$ .
(The $y$ -coefficient is large.) $c_{y} > c_{x} / q + κ / q$ .
(The $z_{sp}$ -coefficient is large.) $c_{z} > c_{x} / q + κ / q$ .

Define $T_{m} = {(x, y, z_{sp}) : x \geq 0, y \geq 0, z_{sp} \geq 0, q x + y + z_{sp} = 2 m}$ and $ϕ (x, y, z_{sp}) = c_{x} x + c_{y} y + c_{z} z_{sp} + κ q x^{2} + y^{2} + z_{sp}^{2} .$ Then $(2 m / q, 0, 0) \in T_{m}$ , and for every $(x, y, z_{sp}) \in T_{m}$ with $(x, y, z_{sp}) \neq = (2 m / q, 0, 0)$ , $ϕ (2 m / q, 0, 0) < ϕ (x, y, z_{sp}) .$

⊢ Lean

Proof of Lemma 3.

Put $q = 2 (m - 1)$ , $M = 2 m$ and $σ = q$ . Since $q > 0$ we have $σ > 0$ , $σ^{2} = q$ , and $M = q + 2 > 0$ .

Step 1 (feasibility of the spread vertex). The point $(M / q, 0, 0)$ has nonnegative coordinates and satisfies $q (M / q) + 0 + 0 = M = 2 m$ , so $(M / q, 0, 0) \in T_{m}$ .

Step 2 (the value at the spread vertex). Since $M / q \geq 0$ , $q (M / q)^{2} + 0^{2} + 0^{2} = (σ (M / q))^{2} = σ \frac{M}{q},$ hence $ϕ (\frac{M}{q}, 0, 0) = c_{x} \frac{M}{q} + κσ \frac{M}{q} .$

Step 3 (a lower bound for the norm term). Let $(x, y, z_{sp}) \in T_{m}$ . From $σ^{2} = q$ and $y^{2}, z_{sp}^{2} \geq 0$ , $(σ x)^{2} = q x^{2} \leq q x^{2} + y^{2} + z_{sp}^{2}, hence σ x \leq q x^{2} + y^{2} + z_{sp}^{2},$ and multiplying by $κ \geq 0$ gives $κσ x \leq κ q x^{2} + y^{2} + z_{sp}^{2}$ . Therefore $c_{x} x + c_{y} y + c_{z} z_{sp} + κσ x \leq ϕ (x, y, z_{sp}) .$

Step 4 (the coefficient separation in cleared form). Multiplying the hypotheses $c_{y} > c_{x} / q + κ / σ$ and $c_{z} > c_{x} / q + κ / σ$ by $σ > 0$ gives $(c_{y} - \frac{c _{x}}{q}) σ - κ > 0, (c_{z} - \frac{c _{x}}{q}) σ - κ > 0.$

Step 5 (some off- $x$ mass is present). Assume in addition $(x, y, z_{sp}) \neq = (M / q, 0, 0)$ . If $y = z_{sp} = 0$ , the simplex equation $q x + y + z_{sp} = M$ would force $x = M / q$ , i.e. the point would be the spread vertex; hence $y > 0$ or $z_{sp} > 0$ . Since $y, z_{sp} \geq 0$ and both coefficients of Step 4 are strictly positive, $0 < ((c_{y} - \frac{c _{x}}{q}) σ - κ) y + ((c_{z} - \frac{c _{x}}{q}) σ - κ) z_{sp} .$

Step 6 (the difference identity). Write $M / q = x + (y + z_{sp}) / q$ , which is the simplex equation divided by $q$ . Then $(c_{x} x + c_{y} y + c_{z} z_{sp} + κσ x) - (c_{x} \frac{M}{q} + κσ \frac{M}{q}) = c_{y} y + c_{z} z_{sp} - \frac{c _{x}}{q} (y + z_{sp}) - \frac{κσ}{q} (y + z_{sp}),$ and multiplying by $σ$ and using $σ^{2} = q$ turns the last term into $κ (y + z_{sp})$ , giving $(c_{x} x + c_{y} y + c_{z} z_{sp} + κσ x - c_{x} \frac{M}{q} - κσ \frac{M}{q}) σ = ((c_{y} - \frac{c _{x}}{q}) σ - κ) y + ((c_{z} - \frac{c _{x}}{q}) σ - κ) z_{sp} .$

By Step 5 the right-hand side is strictly positive, and $σ > 0$ , so the bracket on the left is strictly positive: $c_{x} \frac{M}{q} + κσ \frac{M}{q} < c_{x} x + c_{y} y + c_{z} z_{sp} + κσ x .$

Step 7 (conclusion). Chaining Steps 2, 6 and 3, $ϕ (\frac{M}{q}, 0, 0) = c_{x} \frac{M}{q} + κσ \frac{M}{q} < c_{x} x + c_{y} y + c_{z} z_{sp} + κσ x \leq ϕ (x, y, z_{sp})$ for every $(x, y, z_{sp}) \in T_{m}$ other than $(2 m / q, 0, 0)$ , which is the asserted strict inequality.

∎

Lemma 3 plays the corresponding role for the spread vertex. In the notation of Theorem 3, this vertex is the reduced representation of $X_{spread}$ . The coefficient inequalities make the $x$ -direction uniquely cheapest, so the relaxed optimizer concentrates all simplex mass there.

The iid result uses a different geometric fact: the point $(1, 1, 1)$ is the unique minimizer of the Frobenius part on the simplex, but it minimizes the full objective only when the linear coefficients are balanced across the three spectral directions.

Lemma 4 [lem:frobenius-center-certificate] (Frobenius Center Certificate).

Let $m \in N$ , set $q = 2 (m - 1)$ , and suppose $q > 0$ . For any real coefficients $c_{x}, c_{y}, c_{z}$ and any real $κ$ , define $T_{m} = {(x, y, z_{sp}) : x, y, z_{sp} \geq 0, q x + y + z_{sp} = 2 m}$ and $ϕ_{r, κ} (x, y, z_{sp}) = c_{x} x + c_{y} y + c_{z} z_{sp} + κ q x^{2} + y^{2} + z_{sp}^{2} .$ Then:

(Frobenius center.) The point $(1, 1, 1)$ belongs to $T_{m}$ , and for every $(x, y, z_{sp}) \in T_{m}$ with $(x, y, z_{sp}) \neq = (1, 1, 1)$ , $q \cdot 1^{2} + 1^{2} + 1^{2} < q x^{2} + y^{2} + z_{sp}^{2} .$
(Certificate necessity.) If $(1, 1, 1)$ minimizes $ϕ_{r, κ}$ over $T_{m}$ , that is, if $ϕ_{r, κ} (1, 1, 1) \leq ϕ_{r, κ} (x, y, z_{sp}) for all (x, y, z_{sp}) \in T_{m},$ then $\frac{c _{x}}{q} = c_{y} and c_{y} = c_{z} .$
(Strict optimality.) If $κ > 0$ , $\frac{c _{x}}{q} = c_{y}$ , and $c_{y} = c_{z}$ , then for every $(x, y, z_{sp}) \in T_{m}$ with $(x, y, z_{sp}) \neq = (1, 1, 1)$ , $ϕ_{r, κ} (1, 1, 1) < ϕ_{r, κ} (x, y, z_{sp}) .$

⊢ Lean

Proof of Lemma 4.

Throughout $q = 2 (m - 1) > 0$ , so that $q + 2 = 2 m .$

Step 1 (the center is feasible). The point $(1, 1, 1)$ has nonnegative coordinates and satisfies $q \cdot 1 + 1 + 1 = q + 2 = 2 m$ , hence $(1, 1, 1) \in T_{m}$ .

Step 2 (a bias–variance decomposition of the weighted norm on $T_{m}$ ). Let $(x, y, z_{sp}) \in T_{m}$ . Expanding the squares, $q (x - 1)^{2} + (y - 1)^{2} + (z_{sp} - 1)^{2} = (q x^{2} + y^{2} + z_{sp}^{2}) - 2 (q x + y + z_{sp}) + (q + 2),$ and substituting the simplex equation $q x + y + z_{sp} = 2 m$ together with $q + 2 = 2 m$ gives $- 2 (2 m) + (q + 2) = - (q + 2)$ . Hence $q x^{2} + y^{2} + z_{sp}^{2} = (q \cdot 1^{2} + 1^{2} + 1^{2}) + q (x - 1)^{2} + (y - 1)^{2} + (z_{sp} - 1)^{2} .$

Step 3 (strict minimality of the center for the norm). Suppose $(x, y, z_{sp}) \in T_{m}$ with $(x, y, z_{sp}) \neq = (1, 1, 1)$ . Each of $q (x - 1)^{2}$ , $(y - 1)^{2}$ , $(z_{sp} - 1)^{2}$ is nonnegative, and if their sum vanished then, since $q > 0$ , each would vanish and the point would be $(1, 1, 1)$ . Therefore $0 < q (x - 1)^{2} + (y - 1)^{2} + (z_{sp} - 1)^{2},$ so by Step 2, $q \cdot 1^{2} + 1^{2} + 1^{2} < q x^{2} + y^{2} + z_{sp}^{2}$ , and taking square roots (both arguments being nonnegative and the square root strictly increasing) $q \cdot 1^{2} + 1^{2} + 1^{2} < q x^{2} + y^{2} + z_{sp}^{2} .$ This is the Frobenius-center assertion.

Step 4 (necessity of $c_{x} / q = c_{y}$ ). Assume $ϕ_{r, κ} (1, 1, 1) \leq ϕ_{r, κ} (x, y, z_{sp})$ for all $(x, y, z_{sp}) \in T_{m}$ , and consider the curve $t ⟼ (1 + t, 1 - q t, 1) .$ It is feasible for $∣ t ∣ < min {1, 1/ q}$ : the coordinates $1 + t$ and $1 - q t$ are then positive, the third is $1$ , and $q (1 + t) + (1 - q t) + 1 = q + 2 = 2 m$ for every $t$ , so the curve stays in $T_{m}$ . Consequently $t = 0$ is a local minimum of $g (t) = ϕ_{r, κ} (1 + t, 1 - q t, 1) = c_{x} (1 + t) + c_{y} (1 - q t) + c_{z} + κ q (1 + t)^{2} + (1 - q t)^{2} + 1 .$ The radicand has derivative $\frac{d}{d t} (q (1 + t)^{2} + (1 - q t)^{2} + 1)_{t = 0} = 2 q (1 + t) - 2 q (1 - q t)_{t = 0} = 2 q - 2 q = 0,$ and its value at $t = 0$ is $q + 2 > 0$ , so the chain rule makes the derivative of the square-root term vanish at $t = 0$ . Hence $g^{'} (0) = c_{x} - q c_{y}$ , and local minimality at an interior point forces $c_{x} - q c_{y} = 0, i.e. \frac{c _{x}}{q} = c_{y} .$

Step 5 (necessity of $c_{y} = c_{z}$ ). Consider likewise $t ⟼ (1, 1 + t, 1 - t),$ feasible for $∣ t ∣ < 1$ since then all three coordinates are nonnegative and $q \cdot 1 + (1 + t) + (1 - t) = q + 2 = 2 m$ . Writing $h (t) = ϕ_{r, κ} (1, 1 + t, 1 - t)$ , the radicand $q + (1 + t)^{2} + (1 - t)^{2}$ has derivative $2 (1 + t) - 2 (1 - t)$ , which vanishes at $t = 0$ , and its value there is $q + 2 > 0$ ; so again the square-root term contributes nothing to $h^{'} (0)$ and $h^{'} (0) = c_{y} - c_{z} = 0, i.e. c_{y} = c_{z} .$

Step 6 (strict optimality under the balance conditions). Suppose finally $κ > 0$ , $c_{x} / q = c_{y}$ and $c_{y} = c_{z}$ ; thus $c_{x} = q c_{y}$ and $c_{z} = c_{y}$ . For every $(x, y, z_{sp}) \in T_{m}$ the linear part is then constant: $c_{x} x + c_{y} y + c_{z} z_{sp} = c_{y} (q x + y + z_{sp}) = c_{y} \cdot 2 m = c_{y} (q + 2) = c_{x} \cdot 1 + c_{y} \cdot 1 + c_{z} \cdot 1.$ For $(x, y, z_{sp}) \neq = (1, 1, 1)$ , Step 3 gives a strictly larger norm term, and multiplying that strict inequality by $κ > 0$ preserves strictness. Adding the equal linear parts to the strict norm comparison yields $ϕ_{r, κ} (1, 1, 1) < ϕ_{r, κ} (x, y, z_{sp}),$ so $(1, 1, 1)$ is the strict minimizer.

∎

Lemma 4 explains why the iid covariance has a knife-edge exactness condition in Theorem 2. The norm term alone favors the point $(1, 1, 1)$ , but the linear coefficients must be equal after accounting for the $q$ -multiplicity of the $x$ -coordinate. When that equality fails, the linear part tilts the objective away from the iid point at every finite positive robustness weight.

The next statement is the implementability restriction in reduced form. It is where the parity of the block size enters the geometry.

Lemma 5 [lem:pm-reduced-slice-characterization] (Parity-Truncated Reduced Slice).

Let $m \geq 2$ be an integer and let $u, v \in R$ . Write $x = 1 - u, y = 1 + (m - 1) u - m v, z_{sp} = 1 + (m - 1) u + m v,$ and let $d_{m} = 0$ when $m$ is even and $d_{m} = 2/ m$ when $m$ is odd. Then the block covariance matrix $X (u, v)$ belongs to the implementable covariance class $C_{m}^{\pm}$ of Definition 5 if and only if $x \geq 0, y \geq 0, z_{sp} \geq 0, 2 (m - 1) x + y + z_{sp} = 2 m,$ and $y + z_{sp} \geq d_{m} .$

⊢ Lean

Proof of Lemma 5.

Write $q = 2 (m - 1)$ and keep the abbreviations $x = 1 - u$ , $y = 1 + (m - 1) u - m v$ , $z_{sp} = 1 + (m - 1) u + m v$ of the statement, so that $y + z_{sp} = 2 + 2 (m - 1) u, z_{sp} - y = 2 m v, q x + y + z_{sp} = 2 m,$ the last identity holding for all $u, v$ because the $u$ - and $v$ -terms cancel. Throughout, $(S_{A}, S_{B})$ are the two community sums of Definition 8.

Part I: necessity. Suppose $X (u, v) \in C_{m}^{\pm}$ , i.e. $X (u, v) = X (P) = E_{P} [Z Z^{⊤}]$ for some $P \in P_{m}^{sym}$ . Reading the entries of $X (P)$ off the block pattern of $X (u, v)$ gives $E [Z_{i} Z_{j}] = 1$ if $i = j$ , $= u$ if $i \neq = j$ lie in the same community, and $= v$ if they lie in opposite communities.

(I.1) The three second-moment identities. Expanding $S_{A}^{2} = \sum_{i, j \in A_{m}} Z_{i} Z_{j}$ , there are $m$ diagonal pairs and $m (m - 1)$ off-diagonal same-community pairs, and likewise for $S_{B}^{2}$ ; expanding $S_{A} S_{B} = \sum_{i \in A_{m}} \sum_{j \in B_{m}} Z_{i} Z_{j}$ , all $m^{2}$ pairs are cross-community. Hence $E [S_{A}^{2}] = E [S_{B}^{2}] = m + m (m - 1) u, E [S_{A} S_{B}] = m^{2} v .$

(I.2) Nonnegativity of $y$ and $z_{sp}$ . Combining the three identities, $E [(S_{A} - S_{B})^{2}] = 2 m + 2 m (m - 1) u - 2 m^{2} v = 2 m y, E [(S_{A} + S_{B})^{2}] = 2 m + 2 m (m - 1) u + 2 m^{2} v = 2 m z_{sp} .$ Both left-hand sides are expectations of squares, hence nonnegative, and $m > 0$ ; therefore $y \geq 0$ and $z_{sp} \geq 0$ .

(I.3) Nonnegativity of $x$ . Since $∣ A_{m} ∣ = m \geq 2$ , pick distinct $i, j \in A_{m}$ . Because $Z_{i}^{2} = Z_{j}^{2} = 1$ pointwise, $0 \leq E [(Z_{i} - Z_{j})^{2}] = 2 - 2 E [Z_{i} Z_{j}] = 2 - 2 u,$ so $u \leq 1$ , i.e. $x = 1 - u \geq 0$ .

Together with the identity $q x + y + z_{sp} = 2 m$ recorded above, this gives the reduced-triangle conditions $x \geq 0, y \geq 0, z_{sp} \geq 0, 2 (m - 1) x + y + z_{sp} = 2 m .$

(I.4) The parity bound. If $m$ is even then $d_{m} = 0 \leq y + z_{sp}$ by (I.2), and there is nothing more to prove. If $m$ is odd, then $S_{A}$ is a sum of $m$ terms each equal to $\pm 1$ with $m$ odd, so $S_{A}$ is an odd integer; in particular $S_{A} \neq = 0$ and, being an integer, $S_{A}^{2} \geq 1$ . The same holds for $S_{B}$ . Taking expectations, $E [S_{A}^{2}] \geq 1, E [S_{B}^{2}] \geq 1.$

On the other hand, by (I.1), $E [S_{A}^{2}] + E [S_{B}^{2}] = 2 m + 2 m (m - 1) u = m (y + z_{sp}),$ so $m (y + z_{sp}) \geq 2$ and hence $y + z_{sp} \geq 2/ m = d_{m}$ .

Part II: sufficiency. Conversely, assume $x, y, z_{sp} \geq 0$ , $q x + y + z_{sp} = 2 m$ and $y + z_{sp} \geq d_{m}$ . We exhibit a law in $P_{m}^{sym}$ whose second moment is $X (u, v)$ .

Two general facts are used. First, the block parameterization is affine: for weights $w_{k} \geq 0$ with $\sum_{k} w_{k} = 1$ , $k \sum w_{k} X (u_{k}, v_{k}) = X (k \sum w_{k} u_{k}, k \sum w_{k} v_{k}),$ because every diagonal entry of the left side is $\sum_{k} w_{k} = 1$ and the within- and across-community entries average separately. Second, if $P = \sum_{k} w_{k} P_{k}$ is a convex mixture of laws $P_{k} \in P_{m}^{sym}$ , then $P \in P_{m}^{sym}$ (sign symmetry and invariance under the two-block automorphism group are preserved by convex combinations) and, by linearity of expectation, $X (P) = \sum_{k} w_{k} X (P_{k})$ .

The building blocks are uniform laws on supports that are invariant under global sign reversal and under the two-block automorphism group; each such law lies in $P_{m}^{sym}$ , and its second moment is therefore block-symmetric, say $X (u_{∙}, v_{∙})$ , with $u_{∙}, v_{∙}$ determined through (I.1) by $E [S_{A}^{2}]$ and $E [S_{A} S_{B}]$ : $u_{∙} = \frac{E [ S _{A}^{2} ] - m}{m ( m - 1 )}, v_{∙} = \frac{E [ S _{A} S _{B} ]}{m ^{2}} .$

(II.1) Even $m$ : a three-vertex mixture. Take

$P_{cut}$ , uniform on the cut assignment ( $+ 1$ on $A_{m}$ , $- 1$ on $B_{m}$ ) and its global sign reversal, for which $S_{A}^{2} = m^{2}$ and $S_{A} S_{B} = - m^{2}$ , hence $X (P_{cut}) = X (1, - 1)$ ;
$P_{all}$ , uniform on the two constant assignments (all $+ 1$ , all $- 1$ ), for which $S_{A}^{2} = m^{2}$ and $S_{A} S_{B} = m^{2}$ , hence $X (P_{all}) = X (1, 1)$ ;
$P_{spr}$ , uniform on ${z : S_{A} (z) = S_{B} (z) = 0}$ , a nonempty support when $m$ is even, for which $E [S_{A}^{2}] = E [S_{A} S_{B}] = 0$ and hence $X (P_{spr}) = X (- \frac{1}{m - 1}, 0)$ .

Assign the weights $w_{cut} = \frac{y}{2 m}, w_{all} = \frac{z _{sp}}{2 m}, w_{spr} = \frac{( m - 1 ) x}{m} .$ They are nonnegative because $x, y, z_{sp} \geq 0$ and $m \geq 2$ , and they sum to one because $\frac{y}{2 m} + \frac{z _{sp}}{2 m} + \frac{( m - 1 ) x}{m} = \frac{y + z _{sp} + 2 ( m - 1 ) x}{2 m} = \frac{2 m}{2 m} = 1.$ Their barycentre in the $(u, v)$ parameters is $w_{cut} \cdot 1 + w_{all} \cdot 1 + w_{spr} \cdot (- \frac{1}{m - 1}) = \frac{y + z _{sp}}{2 m} - \frac{x}{m} = \frac{2 m - 2 ( m - 1 ) x}{2 m} - \frac{x}{m} = 1 - x = u$ and $w_{cut} \cdot (- 1) + w_{all} \cdot 1 + w_{spr} \cdot 0 = \frac{z _{sp} - y}{2 m} = v .$ Hence the mixture $P = w_{cut} P_{cut} + w_{all} P_{all} + w_{spr} P_{spr}$ lies in $P_{m}^{sym}$ and has $X (P) = X (u, v)$ , so $X (u, v) \in C_{m}^{\pm}$ .

(II.2) Odd $m$ : a four-vertex mixture. For odd $m$ the support ${S_{A} = S_{B} = 0}$ is empty, so $P_{spr}$ is unavailable and the two parity vertices replace it:

$P_{cut}^{par}$ , uniform on ${z : (S_{A}, S_{B}) = (1, - 1) or (- 1, 1)}$ — a nonempty support for odd $m$ — for which $S_{A}^{2} = 1$ and $S_{A} S_{B} = - 1$ , hence $X (P_{cut}^{par}) = X (- \frac{1}{m}, - \frac{1}{m ^{2}});$
$P_{all}^{par}$ , uniform on ${z : (S_{A}, S_{B}) = (1, 1) or (- 1, - 1)}$ , for which $S_{A}^{2} = 1$ and $S_{A} S_{B} = 1$ , hence $X (P_{all}^{par}) = X (- \frac{1}{m}, \frac{1}{m ^{2}}) .$

In reduced coordinates these two points are $(\frac{m + 1}{m}, \frac{2}{m}, 0)$ and $(\frac{m + 1}{m}, 0, \frac{2}{m})$ , i.e. they sit on the parity boundary $y + z_{sp} = 2/ m$ , whereas $X (1, - 1)$ and $X (1, 1)$ are the outer vertices $(0, 2 m, 0)$ and $(0, 0, 2 m)$ .

Put $s = y + z_{sp}$ and $μ = \frac{y}{s}, λ = \frac{s - 2/ m}{2 m - 2/ m},$ which are well defined because $s \geq 2/ m > 0$ and $2 m - 2/ m > 0$ for $m \geq 2$ . Then $0 \leq μ \leq 1$ since $0 \leq y \leq s$ , and $0 \leq λ \leq 1$ since $2/ m \leq s \leq 2 m$ , the upper bound coming from $s = 2 m - q x \leq 2 m$ with $q x \geq 0$ . Take the four weights $(λ μ, λ (1 - μ), (1 - λ) μ, (1 - λ) (1 - μ))$ on $(P_{cut}, P_{all}, P_{cut}^{par}, P_{all}^{par})$ ; they are nonnegative and sum to one. Their barycentre in the $u$ -parameter is $λ \cdot 1 + (1 - λ) (- \frac{1}{m}) = \frac{( m + 1 ) λ - 1}{m} = u,$ where the last equality is the definition of $λ$ rewritten through $s = 2 m - 2 (m - 1) (1 - u)$ , which gives $λ = (1 + m u) / (m + 1)$ . For the $v$ -parameter, the two $μ$ -pairs collapse to $λ μ (- 1) + λ (1 - μ) (1) + (1 - λ) μ (- \frac{1}{m ^{2}}) + (1 - λ) (1 - μ) \frac{1}{m ^{2}} = (1 - 2 μ) (λ + \frac{1 - λ}{m ^{2}}),$ and the two factors evaluate to $1 - 2 μ = \frac{z _{sp} - y}{s}, λ + \frac{1 - λ}{m ^{2}} = \frac{1}{m ^{2}} + λ \frac{m ^{2} - 1}{m ^{2}} = \frac{s}{2 m},$ the second using $λ = (m s - 2) / (2 (m^{2} - 1))$ . Their product is $(z_{sp} - y) / (2 m) = v$ . Hence the four-point mixture lies in $P_{m}^{sym}$ and has second moment $X (u, v)$ , so $X (u, v) \in C_{m}^{\pm}$ .

Parts I and II are the two implications of the asserted equivalence.

∎

Lemma 5 gives implementability a transparent low-dimensional form. Relative to the relaxed simplex, the implementable slice adds the lower bound $y + z_{sp} \geq d_{m}$ . For even $m$ , $d_{m} = 0$ , so this lower bound is already implied by nonnegativity. For odd $m$ , the positive lower bound records the positive squared magnitude of the realized block sums.

It remains to solve the reduced optimization problem. The next lemma gives the unconstrained weighted-simplex solution as a finite active-set calculation.

Lemma 6 [lem:weighted-simplex-active-set] (Weighted Simplex Active Set).

Let $m \geq 2$ , let $M > 0$ satisfy $M = 2 m$ , and let $I = {x, y, z_{sp}}$ . Let $α = (α_{i})_{i \in I}$ , let $κ \geq 0$ , and let $β = (β_{i})_{i \in I}$ have strictly positive entries with $β_{x} = \frac{1}{2 ( m - 1 )}, β_{y} = β_{z_{sp}} = 1.$ For $t \in R^{I}$ , write $Δ_{M} = {t : t_{i} \geq 0 for all i \in I, i \in I \sum t_{i} = M},$ and $Φ (t) = i \in I \sum α_{i} t_{i} + κ i \in I \sum β_{i} t_{i}^{2} .$ Then the following hold.

(Positive robustness.) If $κ > 0$ , there is a unique pair $(S, λ)$ , where $S \subseteq I$ is nonempty and $λ \in R$ , such that $i \in S \sum \frac{( λ - α _{i} ) ^{2}}{β _{i}} = κ^{2}, α_{i} < λ for every i \in S, λ \leq α_{j} for every j \in / S .$ For this unique pair, define $t_{i}^{⋆} = ⎩ ⎨ ⎧ M \frac{( λ - α _{i} ) / β _{i}}{\sum _{h \in S} ( λ - α _{h} ) / β _{h}}, 0, i \in S, i \in / S .$ Then $t^{⋆} \in Δ_{M}$ , and $t^{⋆}$ is the unique minimizer of $Φ$ over $Δ_{M}$ in the strict sense that, for every $s \in Δ_{M}$ with $s \neq = t^{⋆}$ , $Φ (t^{⋆}) < Φ (s) .$ Its value is $Φ (t^{⋆}) = M λ .$
(Zero robustness.) If $κ = 0$ , then for every $t \in R^{I}$ , $(t \in Δ_{M} and Φ (t) \leq Φ (s) for every s \in Δ_{M}) ⟺ t \in Δ_{M} and whenever t_{i} \neq = 0, α_{i} \leq α_{j} for every j \in I .$ Equivalently, the minimizer set is exactly the exposed $α$ -minimizing face of $Δ_{M}$ .

Proof of Lemma 6.

Throughout $M = 2 m > 0$ and every $β_{i} > 0$ .

Part A: $κ > 0$ .

Step A1 (an admissible pair exists). Define the threshold function $G (λ) = i \in I \sum \frac{( max { λ - α _{i} , 0 } ) ^{2}}{β _{i}}, λ \in R,$ which is continuous because it is a finite sum of continuous functions of $λ$ . Let $α_{m i n} = min_{i} α_{i}$ and $α_{m a x} = max_{i} α_{i}$ , attained at indices $k_{m i n}$ and $k_{m a x}$ . At $λ = α_{m i n}$ every positive part vanishes, so $G (α_{m i n}) = 0 \leq κ^{2} .$ At $λ_{+} = α_{m a x} + κ β_{k_{m a x}}$ the single summand at $k_{m a x}$ already equals $\frac{( κ β _{k_{m a x}} ) ^{2}}{β _{k_{m a x}}} = κ^{2},$ and all summands are nonnegative, so $G (λ_{+}) \geq κ^{2}$ . Since $α_{m i n} \leq λ_{+}$ , the intermediate value theorem yields $λ \in [α_{m i n}, λ_{+}]$ with $G (λ) = κ^{2}$ . Put $S = {i \in I : α_{i} < λ} .$ Off $S$ the positive part $max {λ - α_{i}, 0}$ vanishes, so $i \in S \sum \frac{( λ - α _{i} ) ^{2}}{β _{i}} = G (λ) = κ^{2},$ and $S$ is nonempty (otherwise the left side would be $0 \neq = κ^{2}$ ). By construction $α_{i} < λ$ on $S$ and $λ \leq α_{j}$ off $S$ , so $(S, λ)$ is admissible.

Step A2 (the active-set point lies in $Δ_{M}$ ). Write $D = h \in S \sum \frac{λ - α _{h}}{β _{h}} .$ Each summand is strictly positive ( $λ > α_{h}$ on $S$ , $β_{h} > 0$ ) and $S \neq = \emptyset$ , so $D > 0$ . Hence each $t_{i}^{⋆} = M ((λ - α_{i}) / β_{i}) / D$ with $i \in S$ is nonnegative — indeed strictly positive — while $t_{j}^{⋆} = 0$ off $S$ ; and $i \in I \sum t_{i}^{⋆} = \frac{M}{D} i \in S \sum \frac{λ - α _{i}}{β _{i}} = \frac{M}{D} \cdot D = M .$ Thus $t^{⋆} \in Δ_{M}$ , and moreover $t_{i}^{⋆} > 0 ⟺ i \in S .$

Step A3 (norm and stationarity at $t^{⋆}$ ). Using $t_{i}^{⋆} = 0$ off $S$ and the admissibility equation, $i \in I \sum β_{i} (t_{i}^{⋆})^{2} = \frac{M ^{2}}{D ^{2}} i \in S \sum β_{i} \frac{( λ - α _{i} ) ^{2}}{β _{i}^{2}} = \frac{M ^{2}}{D ^{2}} i \in S \sum \frac{( λ - α _{i} ) ^{2}}{β _{i}} = (\frac{M κ}{D})^{2},$ so, writing $N = \sum_{i} β_{i} (t_{i}^{⋆})^{2}$ , $N = \frac{M κ}{D} > 0.$

Consequently, for every $i \in S$ , $\frac{κ β _{i} t _{i}^{⋆}}{N} = \frac{κ β _{i}}{N} \cdot \frac{M ( λ - α _{i} )}{β _{i} D} = \frac{κ M}{N D} (λ - α_{i}) = λ - α_{i},$ which is the stationarity relation on the active support.

Step A4 (the optimal value). Multiplying the stationarity relation of Step A3 by $t_{i}^{⋆}$ , summing over $i \in S$ (equivalently over all of $I$ , since $t^{⋆}$ vanishes off $S$ ), and using $\sum_{i} β_{i} (t_{i}^{⋆})^{2} = N^{2}$ and $\sum_{i} t_{i}^{⋆} = M$ , $i \in I \sum α_{i} t_{i}^{⋆} + κ N = i \in I \sum α_{i} t_{i}^{⋆} + \frac{κ}{N} i \in I \sum β_{i} (t_{i}^{⋆})^{2} = λ i \in I \sum t_{i}^{⋆} = M λ,$ i.e. $Φ (t^{⋆}) = M λ .$

Step A5 (strict optimality). Let $s \in Δ_{M}$ with $s \neq = t^{⋆}$ , and write $N (s) = \sum_{i} β_{i} s_{i}^{2}$ . Since $β$ is strictly positive, $\sum_{i} s_{i} = \sum_{i} t_{i}^{⋆} = M \neq = 0$ and $s \neq = t^{⋆}$ , the strict weighted Cauchy–Schwarz inequality gives $i \in I \sum β_{i} t_{i}^{⋆} s_{i} < N N (s) .$

Subtracting $\sum_{i} β_{i} (t_{i}^{⋆})^{2} = N^{2}$ from both sides and multiplying by $κ / N > 0$ , $\frac{κ}{N} i \in I \sum β_{i} t_{i}^{⋆} (s_{i} - t_{i}^{⋆}) < κ (N (s) - N) .$ By the stationarity relation of Step A3 (and $t_{j}^{⋆} = 0$ off $S$ ) the left side equals $\sum_{i \in S} (λ - α_{i}) (s_{i} - t_{i}^{⋆})$ , so $Φ (s) - Φ (t^{⋆}) = i \in I \sum α_{i} (s_{i} - t_{i}^{⋆}) + κ (N (s) - N) > i \in I \sum α_{i} (s_{i} - t_{i}^{⋆}) + i \in S \sum (λ - α_{i}) (s_{i} - t_{i}^{⋆}) .$ Setting $γ_{i} = λ$ for $i \in S$ and $γ_{i} = α_{i}$ for $i \in / S$ , the right-hand side is $\sum_{i} γ_{i} (s_{i} - t_{i}^{⋆})$ ; since $γ_{i} t_{i}^{⋆} = λ t_{i}^{⋆}$ for every $i$ (on $S$ by definition of $γ$ , off $S$ because $t_{i}^{⋆} = 0$ ) and $\sum_{i} t_{i}^{⋆} = M$ , it equals $i \in I \sum γ_{i} s_{i} - λ M .$ Finally $γ_{i} \geq λ$ for every $i$ — with equality on $S$ and by admissibility $α_{j} \geq λ$ off $S$ — and $s_{i} \geq 0$ , so $\sum_{i} γ_{i} s_{i} \geq λ \sum_{i} s_{i} = λ M$ and the last display is nonnegative. Hence $Φ (t^{⋆}) < Φ (s) for every s \in Δ_{M} with s \neq = t^{⋆} .$

Step A6 (uniqueness of $(S, λ)$ ). Let $(S^{'}, λ^{'})$ be another admissible pair, with active-set point $t^{⋆'}$ . Steps A2 and A5 apply to it as well, so both $t^{⋆}$ and $t^{⋆'}$ are strict minimizers of $Φ$ over $Δ_{M}$ ; if they differed, each would have strictly smaller value than the other, which is impossible. Hence $t^{⋆} = t^{⋆'}$ . By the support identity of Step A2, $i \in S ⟺ t_{i}^{⋆} > 0 ⟺ t_{i}^{⋆'} > 0 ⟺ i \in S^{'},$ so $S = S^{'}$ . By Step A4, $M λ = Φ (t^{⋆}) = Φ (t^{⋆'}) = M λ^{'}$ , and $M > 0$ gives $λ = λ^{'}$ .

Part B: $κ = 0$ . Here $Φ (t) = \sum_{i} α_{i} t_{i}$ is linear. Fix $k$ with $α_{k} = min_{j} α_{j}$ .

If $t \in Δ_{M}$ minimizes $Φ$ over $Δ_{M}$ , compare it with the vertex of $Δ_{M}$ that places all the mass on coordinate $k$ , i.e. the point $w$ with $w_{k} = M$ and $w_{j} = 0$ for $j \neq = k$ , whose value is $Φ (w) = M α_{k}$ : $i \in I \sum α_{i} t_{i} \leq M α_{k} = α_{k} i \in I \sum t_{i}, i.e. i \in I \sum (α_{i} - α_{k}) t_{i} \leq 0.$ Every summand is nonnegative ( $α_{i} \geq α_{k}$ , $t_{i} \geq 0$ ), so every summand vanishes; hence $t_{i} \neq = 0$ forces $α_{i} = α_{k} \leq α_{j}$ for every $j$ . That is exactly membership in the exposed $α$ -minimizing face.

Conversely, if $t \in Δ_{M}$ is supported only on $α$ -minimizing coordinates, then $α_{i} t_{i} = α_{k} t_{i}$ for every $i$ and $Φ (t) = α_{k} i \in I \sum t_{i} = M α_{k},$ whereas every $s \in Δ_{M}$ satisfies $Φ (s) = \sum_{i} α_{i} s_{i} \geq α_{k} \sum_{i} s_{i} = M α_{k}$ . So $t$ is a minimizer. The two implications give the stated equivalence, and the minimizer set is precisely the exposed $α$ -minimizing face of $Δ_{M}$ .

∎

Lemma 6 is the finite case split behind the active-set formula in Theorem 4. For $κ > 0$ , the support and multiplier determine both the optimizer and the value. For $κ = 0$ , the norm term drops out and the minimizers form the exposed face associated with the smallest linear coefficient.

The implementable problem may add the parity lower bound. The following truncation statement records how the solution changes when the unconstrained active-set point lies outside that truncated simplex.

Lemma 7 [lem:weighted-simplex-truncation] (Weighted Simplex Truncation).

Let $m \geq 2$ , let $M, d \in R$ , and let $α = (α_{x}, α_{y}, α_{z})$ , $β = (β_{x}, β_{y}, β_{z})$ , and $κ \in R$ . Suppose:

(Mass and truncation.) $M > 0$ , $M = 2 m$ , and $0 \leq d \leq M$ .
(Weights.) Each $β_{i}$ is strictly positive and $β = (\frac{1}{2 ( m - 1 )}, 1, 1),$ so in particular $β_{y} = β_{z} = 1$ .
(Robustness.) $κ \geq 0$ .

Write $K_{d} = {t \in Δ_{M} : t_{y} + t_{z} \geq d}, Φ (t) = i \sum α_{i} t_{i} + κ i \sum β_{i} t_{i}^{2} .$ For $κ > 0$ , for every nonempty active support $S \subseteq {x, y, z}$ and multiplier $λ$ satisfying $i \in S \sum \frac{( λ - α _{i} ) ^{2}}{β _{i}} = κ^{2}, α_{i} < λ for i \in S, λ \leq α_{j} for j \in / S,$ let $t^{rel}$ be the active-set point $t_{i}^{rel} = ⎩ ⎨ ⎧ \frac{M (( λ - α _{i} ) / β _{i} )}{\sum _{h \in S} ( λ - α _{h} ) / β _{h}}, 0, i \in S, i \in / S .$ If $t^{rel} \in K_{d}$ , then $Φ (t^{rel}) \leq Φ (s) for every s \in K_{d} .$ If $t_{y}^{rel} + t_{z}^{rel} < d$ , then $t^{⋆} = (M - d, s^{⋆}, d - s^{⋆}) \in K_{d}$ and $Φ (t^{⋆}) \leq Φ (s) for every s \in K_{d},$ where $s^{⋆} = truncSelector (M, d, α, β, κ)$ , namely with $δ = α_{y} - α_{z}, A = β_{x} (M - d)^{2},$ $s^{⋆} = ⎩ ⎨ ⎧ 0, d, \frac{d - δ ( A + d ^{2} /2 ) / ( κ ^{2} - δ ^{2} /2 )}{2}, δ \geq \frac{κ d}{A + d ^{2}}, δ \leq - \frac{κ d}{A + d ^{2}}, otherwise.$

For $κ = 0$ , let $t^{rel}$ be a point of the exposed $α$ -minimizing face ${t \in Δ_{M} : t_{i} \neq = 0 \Rightarrow α_{i} \leq α_{j} for every j} .$ Assume the tie convention that, if this exposed face contains at least one point of $K_{d}$ , then the selected point $t^{rel}$ lies in $K_{d}$ . If $t^{rel} \in K_{d}$ , then $Φ (t^{rel}) \leq Φ (s) for every s \in K_{d} .$ If $t_{y}^{rel} + t_{z}^{rel} < d$ , then $t^{⋆} = (M - d, s^{⋆}, d - s^{⋆}) \in K_{d}$ and $Φ (t^{⋆}) \leq Φ (s) for every s \in K_{d},$ where $s^{⋆} = truncSelector (M, d, α, β, 0)$ , equivalently, in the ordered selector convention, $s^{⋆} = 0$ if $α_{y} - α_{z} \geq 0$ and $s^{⋆} = d$ if $α_{y} - α_{z} < 0$ .

Proof of Lemma 7.

Write $δ = α_{y} - α_{z}$ , $A = β_{x} (M - d)^{2} \geq 0$ , and for $σ \in R$ let $h (σ) = (M - d, σ, d - σ)$ be the point of the boundary segment $H_{d}$ with second coordinate $σ$ . Since $β_{y} = β_{z} = 1$ , evaluating the objective there gives the one-dimensional slice $g_{d} (σ) := Φ (h (σ)) = α_{x} (M - d) + α_{y} σ + α_{z} (d - σ) + κ r (σ), r (σ) = A + σ^{2} + (d - σ)^{2} .$

Step 1 (two-point convexity of $Φ$ ). For $u, w \in R^{I}$ and $θ \in [0, 1]$ , $Φ ((1 - θ) u + θ w) \leq (1 - θ) Φ (u) + θ Φ (w) .$ Indeed the linear part is exactly additive, and $t \mapsto \sum_{i} β_{i} t_{i}^{2}$ is the Euclidean norm of the vector with coordinates $β_{i} t_{i}$ , so it obeys the triangle inequality and positive homogeneity; multiplying by $κ \geq 0$ preserves the inequality.

Step 2 (the dichotomy from a relaxed minimizer). Let $t^{rel} \in Δ_{M}$ satisfy $Φ (t^{rel}) \leq Φ (s)$ for every $s \in Δ_{M}$ .

If $t^{rel} \in K_{d}$ , then since $K_{d} \subseteq Δ_{M}$ the same inequality holds for every $s \in K_{d}$ ; this is the first alternative in both robustness regimes.

Assume from now on $t_{y}^{rel} + t_{z}^{rel} < d$ . Because $t_{y}^{rel}, t_{z}^{rel} \geq 0$ , this forces $d > 0$ .

Step 3 (every feasible point is dominated on the face $H_{d}$ ). Let $s \in K_{d}$ and put $Σ = s_{y} + s_{z} \geq d$ and $Σ^{rel} = t_{y}^{rel} + t_{z}^{rel} < d$ . If $Σ = d$ then $s$ already lies on $H_{d}$ : its first coordinate is $M - d$ by the mass constraint, so $s = h (s_{y})$ with $0 \leq s_{y} \leq d$ , and we may take $σ = s_{y}$ . If $Σ > d$ , set $θ = \frac{Σ - d}{Σ - Σ ^{rel}} \in [0, 1], t^{b} = (1 - θ) s + θ t^{rel},$ which is well defined since $Σ - Σ^{rel} > 0$ . Then $t^{b} \in Δ_{M}$ (a convex combination of simplex points) and $t_{y}^{b} + t_{z}^{b} = (1 - θ) Σ + θ Σ^{rel} = Σ - θ (Σ - Σ^{rel}) = d,$ so $t^{b} = h (σ)$ with $σ = t_{y}^{b} \in [0, d]$ . By Step 1 and $Φ (t^{rel}) \leq Φ (s)$ , $Φ (h (σ)) = Φ (t^{b}) \leq (1 - θ) Φ (s) + θ Φ (t^{rel}) \leq Φ (s) .$ In either case there is $σ \in [0, d]$ with $Φ (h (σ)) \leq Φ (s)$ .

Step 4 (the selector lies in $[0, d]$ ). In the two endpoint branches $s^{⋆} \in {0, d} \subseteq [0, d]$ because $d > 0$ . In the interior branch both guards fail, $∣ δ ∣ < \frac{κ d}{A + d ^{2}}, equivalently δ^{2} (A + d^{2}) < κ^{2} d^{2},$ which forces $κ > 0$ and, since $δ^{2} d^{2} \leq δ^{2} (A + d^{2})$ , also $δ^{2} < κ^{2}$ , so $κ^{2} - δ^{2} /2 > 0$ and $W := \frac{A + d ^{2} /2}{κ ^{2} - δ ^{2} /2}$ is well defined with $s^{⋆} = (d - δ W) /2$ . Moreover $δ^{2} W^{2} = \frac{2 δ ^{2} A + δ ^{2} d ^{2}}{2 κ ^{2} - δ ^{2}} < d^{2} ⟺ δ^{2} (A + d^{2}) < κ^{2} d^{2},$ so $∣ δ W ∣ < d$ and hence $0 < s^{⋆} < d$ . In all branches $h (s^{⋆}) = (M - d, s^{⋆}, d - s^{⋆})$ has nonnegative coordinates (using $d \leq M$ ), total mass $M$ , and $s^{⋆} + (d - s^{⋆}) = d$ ; therefore $t^{⋆} = h (s^{⋆}) \in K_{d} .$

Step 5 (the selector’s sign condition). We claim that for every $σ \in [0, d]$ , $0 \leq (σ - s^{⋆}) (r (s^{⋆}) δ + κ (2 s^{⋆} - d)) .$ If $s^{⋆} = 0$ , the branch guard reads $δ A + d^{2} \geq κ d$ , and $r (0) = A + d^{2}$ , so the bracket $δ A + d^{2} - κ d$ is nonnegative while $σ - 0 \geq 0$ . If $s^{⋆} = d$ , the guard reads $δ A + d^{2} \leq - κ d$ , and $r (d) = A + d^{2}$ , so the bracket $δ A + d^{2} + κ d$ is nonpositive while $σ - d \leq 0$ . In the interior branch the bracket vanishes: with $W$ as in Step 4 we have $2 s^{⋆} - d = - δ W$ and $r (s^{⋆})^{2} = A + (s^{⋆})^{2} + (d - s^{⋆})^{2} = A + \frac{d ^{2}}{2} + \frac{δ ^{2} W ^{2}}{2} = (κ^{2} - \frac{δ ^{2}}{2}) W^{2} + \frac{δ ^{2} W ^{2}}{2} = (κW)^{2},$ using $W^{2} (κ^{2} - δ^{2} /2) = A + d^{2} /2$ ; both $r (s^{⋆})$ and $κW$ are nonnegative, so $r (s^{⋆}) = κW$ and $r (s^{⋆}) δ + κ (2 s^{⋆} - d) = κW δ - κ δ W = 0.$

Step 6 (the selector minimizes the slice). Fix $σ \in [0, d]$ . By Cauchy–Schwarz applied to the vectors $(A, s^{⋆}, d - s^{⋆})$ and $(A, σ, d - σ)$ , $A + s^{⋆} σ + (d - s^{⋆}) (d - σ) \leq r (s^{⋆}) r (σ) .$

Subtracting $r (s^{⋆})^{2} = A + (s^{⋆})^{2} + (d - s^{⋆})^{2}$ from both sides and using the algebraic identity $A + s^{⋆} σ + (d - s^{⋆}) (d - σ) - r (s^{⋆})^{2} = (σ - s^{⋆}) (2 s^{⋆} - d),$ we obtain $(σ - s^{⋆}) (2 s^{⋆} - d) \leq r (s^{⋆}) (r (σ) - r (s^{⋆}))$ ; multiplying by $κ \geq 0$ and adding $r (s^{⋆}) δ (σ - s^{⋆})$ to both sides gives, together with Step 5, $0 \leq (σ - s^{⋆}) (r (s^{⋆}) δ + κ (2 s^{⋆} - d)) \leq r (s^{⋆}) (δ (σ - s^{⋆}) + κ (r (σ) - r (s^{⋆}))) .$ Since $r (s^{⋆}) > 0$ (because $d > 0$ makes $(s^{⋆})^{2} + (d - s^{⋆})^{2} > 0$ ), $δ (σ - s^{⋆}) + κ (r (σ) - r (s^{⋆})) \geq 0, i.e. g_{d} (s^{⋆}) \leq g_{d} (σ),$ because $g_{d} (σ) - g_{d} (s^{⋆}) = δ (σ - s^{⋆}) + κ (r (σ) - r (s^{⋆}))$ .

Combining Steps 3 and 6: for every $s \in K_{d}$ there is $σ \in [0, d]$ with $Φ (t^{⋆}) = g_{d} (s^{⋆}) \leq g_{d} (σ) = Φ (h (σ)) \leq Φ (s)$ , so $t^{⋆} = (M - d, s^{⋆}, d - s^{⋆}) \in K_{d} and Φ (t^{⋆}) \leq Φ (s) for every s \in K_{d} .$

Step 7 (the two robustness regimes). For $κ > 0$ , an admissible pair $(S, λ)$ has active-set point $t^{rel}$ lying in $Δ_{M}$ and minimizing $Φ$ over $Δ_{M}$ by Lemma 6; Steps 2–6 then give exactly the two stated alternatives.

For $κ = 0$ , a point $t^{rel}$ of the exposed $α$ -minimizing face minimizes the linear objective $Φ$ over $Δ_{M}$ , again by Lemma 6, so Steps 2–6 apply verbatim. Under the stated tie convention the first alternative is selected whenever the face meets $K_{d}$ . Finally, at $κ = 0$ the two selector guards read $0 \leq δ$ and $δ \leq 0$ , so the interior branch is never taken and $s^{⋆} = {0, d, α_{y} - α_{z} \geq 0, α_{y} - α_{z} < 0,$ which is the ordered endpoint rule.

∎

Lemma 7 reduces the constrained implementable calculation to a one-dimensional boundary segment whenever the relaxed optimizer violates the lower bound. The selector chooses either an endpoint of that segment or the unique interior point identified by the displayed expression. This is the source of the truncation correction in Theorem 4.

The final ingredient ties the reduced optimization problems back to the implementability loss defined in the main text.

Lemma 8 [lem:rounding-gap-reduction] (Reduced Gap Identity).

For any real $r$ and any $κ \geq 0$ , under Assumption 1, the implementability loss of Definition 7 satisfies $Δ_{m}^{\pm} (r, κ) = (x, y, z_{sp}) \in T_{m} y + z_{sp} \geq d_{m} in f ϕ_{r, κ} (x, y, z_{sp}) - (x, y, z_{sp}) \in T_{m} in f ϕ_{r, κ} (x, y, z_{sp}) .$

⊢ Lean

Proof of Lemma 8.

Set $q = 2 (m - 1)$ ; Assumption 1 gives $m \geq 2$ , so $m \neq = 0$ and $q > 0$ . By Definition 7 it suffices to identify the two image sets $F_{r, κ} (E_{m}^{blk}) = {F_{r, κ} (X) : X \in E_{m}^{blk}}, F_{r, κ} (C_{m}^{\pm}) = {F_{r, κ} (X) : X \in C_{m}^{\pm}}$ with the corresponding sets of reduced objective values, since an infimum depends only on the set of attained values.

Step 1 (the coordinate change is invertible on $T_{m}$ ). Given $(x, y, z_{sp}) \in T_{m}$ , put $u = 1 - x, v = \frac{z _{sp} - y}{2 m} .$ Then $1 - u = x$ by construction. The simplex equation $q x + y + z_{sp} = 2 m$ gives $(m - 1) x = m - \frac{1}{2} (y + z_{sp})$ , hence $1 + (m - 1) u = m - (m - 1) x = \frac{1}{2} (y + z_{sp})$ , and therefore $1 + (m - 1) u - m v = \frac{y + z _{sp}}{2} - \frac{z _{sp} - y}{2} = y, 1 + (m - 1) u + m v = \frac{y + z _{sp}}{2} + \frac{z _{sp} - y}{2} = z_{sp} .$ So every point of $T_{m}$ is the spectral-coordinate image of the block matrix $X (u, v)$ with these parameters.

Step 2 (the relaxed image). We claim ${F_{r, κ} (X) : X \in E_{m}^{blk}} = {ϕ_{r, κ} (x, y, z_{sp}) : (x, y, z_{sp}) \in T_{m}} .$ For the inclusion $\subseteq$ : every $X \in E_{m}^{blk}$ is of the form $X (u, v)$ by Definition 4, and Lemma 1 places its spectral coordinates in $T_{m}$ and identifies $F_{r, κ} (X (u, v)) = ϕ_{r, κ} (x, y, z_{sp})$ . For $\supseteq$ : given $(x, y, z_{sp}) \in T_{m}$ , Step 1 produces $(u, v)$ with these spectral coordinates, and Lemma 1 then gives both $X (u, v) \in E_{m}^{blk}$ and $F_{r, κ} (X (u, v)) = ϕ_{r, κ} (x, y, z_{sp})$ .

Step 3 (the implementable image). We claim ${F_{r, κ} (X) : X \in C_{m}^{\pm}} = {ϕ_{r, κ} (x, y, z_{sp}) : (x, y, z_{sp}) \in T_{m}, y + z_{sp} \geq d_{m}} .$ For $\subseteq$ : let $X = X (P)$ with $P \in P_{m}^{sym}$ . Because $P$ is invariant under the two-block automorphism group and $m \geq 2$ , all within-community off-diagonal second moments coincide and all across-community ones coincide, so there are $u, v$ with $X (P) = X (u, v);$

Lemma 5 then gives $(x, y, z_{sp}) \in T_{m}$ together with $y + z_{sp} \geq d_{m}$ , and Lemma 1 identifies $F_{r, κ} (X) = ϕ_{r, κ} (x, y, z_{sp})$ . For $\supseteq$ : given $(x, y, z_{sp}) \in T_{m}$ with $y + z_{sp} \geq d_{m}$ , Step 1 produces $(u, v)$ realizing these coordinates, Lemma 5 places $X (u, v) \in C_{m}^{\pm}$ , and Lemma 1 again matches the objective values.

Step 4 (conclusion). Substituting the two image identities of Steps 2 and 3 into Definition 7, $Δ_{m}^{\pm} (r, κ) = (x, y, z_{sp}) \in T_{m} y + z_{sp} \geq d_{m} in f ϕ_{r, κ} (x, y, z_{sp}) - (x, y, z_{sp}) \in T_{m} in f ϕ_{r, κ} (x, y, z_{sp}),$ as claimed.

∎

Lemma 8 is the bridge from geometry back to design. The relaxed benchmark is the infimum over $T_{m}$ , while the implementable benchmark is the same reduced objective with the parity truncation imposed. Consequently, the loss is exactly the value difference between these two scalar problems, which is the quantity evaluated by the active-set and truncation formulas above.

Verification note

This appendix records the verification boundary for the mathematical claims used in the paper. The formal statements take the assignment law, its induced second moments, the two-block weighted graph, the block elliptope relaxation, and the finite comparison between relaxed and implementable covariance optima as their load-bearing objects. The design-based finite-population potential-outcome framework supplies the surrounding motivation.

The verified mathematical layer consists of the assumptions, definitions, lemmas, and theorems stated in the paper. In particular, it includes the two-block homophily, sign-symmetry, low-scale, and odd-block conditions in Assumption 1–Assumption 4; the graph, design-class, covariance, objective, loss, and block-sum definitions in Definition 1–Definition 8; the symmetry reduction in Proposition 1; the exactness results in Theorem 1 and Theorem 2; and the positive-loss and sharp-computation results in Theorem 3 and Theorem 4. The auxiliary reductions collected in Appendix A are part of the same mathematical layer.

The econometric motivation, related-work positioning, and interpretation are prose surrounding that layer. The displayed assumptions in the paper give exactly the conditions used to derive the formal conclusions, which are finite-dimensional and design based.

For reproducibility, the theorem statements and proofs are machine-checked in Lean 4. The assumed inputs to the checked arguments are the explicitly stated mathematical hypotheses, including the two-block homophily, sign-symmetry, low-scale, odd-block, and nonnegativity conditions where they appear; standard finite-dimensional real matrix primitives for traces, positive semidefiniteness, the Moore–Penrose pseudoinverse, and the Schatten–2 norm; and the usual classical real-analysis and finite-set principles available in the underlying library. The Lean verification discharges the algebraic, convex-geometric, spectral, parity, and active-set claims stated in the formal environments, while the historical, empirical, and interpretive material remains prose.

The formalization was checked against Lean toolchain leanprover/lean4:v4.29.0-rc3 with mathlib at revision bf8875c7. All declarations live under the module namespace CausalSmith.Experimentation.EXP_DesignPm1ExactnessBoundaryV1_Research, and each carries a @node tag matching its manuscript label; every stated result is sorry-free. The five main results map to Lean declarations as follows.

Manuscript label	Lean file	Declaration
Proposition 1	`Helpers/SymmetryReduction.lean`	`symmetry_reduction`
Theorem 1	`Tcut.lean`	`cut_corner_exactness`
Theorem 2	`Trobust.lean`	`robust_corner_exactness`
Theorem 3	`Tgap.lean`	`gap_window`
Theorem 4	`Tsharp.lean`	`sharp_rho_star`

The auxiliary lemmas of Appendix A are declared in the sibling Helpers/ files under the same namespace, with declaration names matching their manuscript labels (for example block_spectral_coordinates, weighted_simplex_active_set, weighted_simplex_truncation, and rounding_gap_reduction).

Proofs of the main results

Proof of Proposition 1.

Write $n = 2 m$ and, for a matrix $X \in R^{n \times n}$ , introduce the two off-diagonal block sums and the two pair counts $S_{w} (X) = i \neq = j i, j same community \sum X_{ij}, S_{a} (X) = i, j opposite communities \sum X_{ij},$ $N_{w} = 2 m (m - 1), N_{a} = 2 m^{2},$ the counts being the numbers of ordered index pairs of each kind. Call $G (d, w, c)$ the block-constant matrix with $d$ on the diagonal, $w$ on within-community off-diagonal entries, and $c$ on across-community entries. Assumption 1 gives $m \geq 2$ , so $N_{w}, N_{a} > 0$ .

Step 1 (a master trace identity). If $X$ is symmetric, then grouping the $n^{2}$ ordered pairs into diagonal, within-community, and across-community pairs gives $tr (G (d, w, c) X) = d i \sum X_{ii} + w S_{w} (X) + c S_{a} (X) .$

The three matrices $L_{m}$ , $L_{m}^{†}$ and $J_{n}$ are block-constant: $L_{m}$ has the constant weighted degree $(m - 1) a / m + b$ on its diagonal and entries $- a / m$ , $- b / m$ off it; $J_{n} = G (1, 1, 1)$ ; and $L_{m}^{†}$ is a linear combination of the identity and the two rank-one projections onto the all-ones and community-sign directions, all three of which are block-constant. Consequently, if $X$ and $Y$ are symmetric with unit diagonal and $S_{w} (Y) = S_{w} (X), S_{a} (Y) = S_{a} (X),$ then $tr (L_{m} Y) = tr (L_{m} X)$ , $tr (L_{m}^{†} Y) = tr (L_{m}^{†} X)$ and $tr (J_{n} Y) = tr (J_{n} X)$ ; if in addition $∥ Y ∥_{S_{2}} \leq ∥ X ∥_{S_{2}}$ , then, since $κ \geq 0$ , $F_{r, κ} (Y) \leq F_{r, κ} (X) .$

This comparison is the common engine of the two symmetrization claims.

Step 2 (relaxed matrices: the block average is feasible). Let $X$ be positive semidefinite with $X_{ii} = 1$ for all $i$ , and set $u = \frac{S _{w} ( X )}{N _{w}}, v = \frac{S _{a} ( X )}{N _{a}},$ the averages of the within- and across-community off-diagonal entries. By construction $X (u, v)$ is symmetric with unit diagonal and $S_{w} (X (u, v)) = N_{w} u = S_{w} (X), S_{a} (X (u, v)) = N_{a} v = S_{a} (X) .$

Membership in $E_{m}^{blk}$ requires the three inequalities of Definition 4. First, testing positive semidefiniteness against $e_{i} - e_{j}$ and $e_{i} + e_{j}$ and using the unit diagonal gives $0 \leq (e_{i} - e_{j})^{⊤} X (e_{i} - e_{j}) = 2 - 2 X_{ij}, 0 \leq (e_{i} + e_{j})^{⊤} X (e_{i} + e_{j}) = 2 + 2 X_{ij},$ so $∣ X_{ij} ∣ \leq 1$ for all $i, j$ . Averaging the bound $X_{ij} \leq 1$ over the $N_{w}$ within-community off-diagonal pairs gives $u \leq 1$ , i.e. $1 - u \geq 0$ . Second, with $s$ the community sign vector ( $+ 1$ on $A_{m}$ , $- 1$ on $B_{m}$ ) the sign product $s_{i} s_{j}$ is $+ 1$ on diagonal and within-community pairs and $- 1$ on across-community pairs, so $0 \leq s^{⊤} X s = i \sum X_{ii} + S_{w} (X) - S_{a} (X) = 2 m + 2 m (m - 1) u - 2 m^{2} v = 2 m (1 + (m - 1) u - m v),$ and dividing by $2 m > 0$ gives $1 + (m - 1) u - m v \geq 0$ . Third, testing against the all-ones vector, whose quadratic form is the total entry sum, $0 \leq i, j \sum X_{ij} = i \sum X_{ii} + S_{w} (X) + S_{a} (X) = 2 m (1 + (m - 1) u + m v),$ giving $1 + (m - 1) u + m v \geq 0$ . With Assumption 1 this is exactly $X (u, v) \in E_{m}^{blk}$ .

Step 3 (relaxed matrices: the objective does not increase). The block sums already match by Step 2, so by Step 1 only the Frobenius term has to be compared. Squaring entrywise and grouping pairs as before, $∥ X ∥_{S_{2}}^{2} = 2 m + within \sum X_{ij}^{2} + across \sum X_{ij}^{2}, ∥ X (u, v) ∥_{S_{2}}^{2} = 2 m + N_{w} u^{2} + N_{a} v^{2} .$ Cauchy–Schwarz over each of the two pair families gives $(\sum_{within} X_{ij})^{2} \leq N_{w} \sum_{within} X_{ij}^{2}$ , i.e. $N_{w} u^{2} \leq within \sum X_{ij}^{2}, and likewise N_{a} v^{2} \leq across \sum X_{ij}^{2} .$ Hence $∥ X (u, v) ∥_{S_{2}} \leq ∥ X ∥_{S_{2}}$ , and Step 1 yields $F_{r, κ} (X (u, v)) \leq F_{r, κ} (X) .$

Step 4 (assignment laws: the orbit average). Let $H$ be the finite, nonempty group of two-block automorphisms: permutations $σ$ of the units that either preserve both communities setwise or swap them. For $P \in P_{m}^{bal}$ define the orbit average $P^{orb} (Z = z) = \frac{1}{∣ H ∣} σ \in H \sum P (Z = z \circ σ) .$ It is a probability law, it is sign-symmetric because each summand is, and it is $H$ -invariant because precomposing $z$ with $τ \in H$ permutes the summation over $H$ ; hence $P^{orb} \in P_{m}^{sym}$ . Sign symmetry gives zero one-point margins: replacing $z$ by $- z$ leaves the law unchanged and flips the sign of $Z_{i}$ , so $E [Z_{i}] = - E [Z_{i}]$ and therefore $E [Z_{i}] = 0 for every i .$

Step 5 (assignment laws: the objective does not increase). The same change of variables in the expectation gives the entrywise orbit-averaging identity $X (P^{orb})_{ij} = \frac{1}{∣ H ∣} σ \in H \sum X (P)_{σ (i) σ (j)} .$

Every $σ \in H$ maps within-community ordered pairs to within-community ordered pairs and across-community pairs to across-community pairs, and does so bijectively; hence summing the display over each family gives $S_{w} (X (P^{orb})) = S_{w} (X (P)), S_{a} (X (P^{orb})) = S_{a} (X (P)) .$

For the Frobenius term, Cauchy–Schwarz applied to the average over $H$ gives entrywise $X (P^{orb})_{ij}^{2} \leq \frac{1}{∣ H ∣} σ \in H \sum X (P)_{σ (i) σ (j)}^{2},$ and summing over all $(i, j)$ , each inner sum being a permutation of the full square sum, yields $X (P^{orb})_{S_{2}} \leq X (P)_{S_{2}} .$

Both second moments are symmetric with unit diagonal ( $X (P)_{ii} = E [Z_{i}^{2}] = 1$ ), so Step 1 applies and gives $F_{r, κ} (X (P^{orb})) \leq F_{r, κ} (X (P)) .$

Step 6 (an infimum-reduction principle). Let $f$ be a real function on a set $S$ , let $T \subseteq S$ be nonempty, suppose $f$ is bounded below on $S$ , and suppose every $x \in S$ admits $y \in T$ with $f (y) \leq f (x)$ . Then $S in f f = T in f f .$ Indeed $in f_{S} f \leq in f_{T} f$ because $T \subseteq S$ , and conversely each value $f (x)$ , $x \in S$ , dominates some $f (y) \geq in f_{T} f$ .

Step 7 (the two infimum identities). On the relaxed side take $S_{rel} = {X : X ⪰ 0, X_{ii} = 1 \forall i}, T_{blk} = E_{m}^{blk} .$ The inclusion $T_{blk} \subseteq S_{rel}$ follows from the projection decomposition used for block matrices. Let $P_{1} = J_{n} / (2 m)$ , let $P_{s} = s s^{⊤} / (2 m)$ , and let $P_{⊥} = I_{n} - P_{1} - P_{s}$ . For every $u, v$ , $X (u, v) = (1 - u) P_{⊥} + (1 + (m - 1) u - m v) P_{s} + (1 + (m - 1) u + m v) P_{1} .$ The matrices $P_{1}$ and $P_{s}$ are positive semidefinite rank-one projections. Also, for any vector $ξ$ , if $A = i \in A_{m} \sum ξ_{i}, B = i \in B_{m} \sum ξ_{i}, Q_{A} = i \in A_{m} \sum ξ_{i}^{2}, Q_{B} = i \in B_{m} \sum ξ_{i}^{2},$ then $ξ^{⊤} P_{⊥} ξ = Q_{A} + Q_{B} - \frac{A ^{2} + B ^{2}}{m} \geq 0$ by Cauchy–Schwarz on the two communities, so $P_{⊥}$ is positive semidefinite. Thus the three nonnegative coordinates in Definition 4 make $X (u, v)$ positive semidefinite, and the definition of $X (u, v)$ gives unit diagonal. The set $T_{blk}$ is nonempty because $I_{n} = X (0, 0) \in E_{m}^{blk}$ .

It remains to record the lower bound on the relaxed objective. Choose block-constant representations $L_{m} = G (d_{L}, w_{L}, c_{L}), L_{m}^{†} = G (d_{†}, w_{†}, c_{†}), J_{n} = G (1, 1, 1),$ and set $B_{L} = ∣ d_{L} ∣ 2 m + ∣ w_{L} ∣ N_{w} + ∣ c_{L} ∣ N_{a}, B_{†} = ∣ d_{†} ∣ 2 m + ∣ w_{†} ∣ N_{w} + ∣ c_{†} ∣ N_{a},$ $B_{J} = 2 m + N_{w} + N_{a} .$ For $X \in S_{rel}$ , Step 2 gives $∣ X_{ij} ∣ \leq 1$ ; hence $∣ S_{w} (X) ∣ \leq N_{w}$ and $∣ S_{a} (X) ∣ \leq N_{a}$ . The trace identity in Step 1 then gives, for every block-constant $G (d, w, c)$ , $tr (G (d, w, c) X) \leq ∣ d ∣ 2 m + ∣ w ∣ N_{w} + ∣ c ∣ N_{a} .$ Therefore $F_{r, κ} (X) \geq - B_{L} - ∣ r ∣ B_{†} + κ ∥ X ∥_{S_{2}} - B_{J} \geq - (B_{L} + ∣ r ∣ B_{†} + B_{J}),$ because $κ \geq 0$ and $∥ X ∥_{S_{2}} \geq 0$ . Steps 2–3 supply, for every $X \in S_{rel}$ , the point $X (u, v) \in T_{blk}$ with no larger objective. Step 6 gives $X ⪰ 0 X_{ii} = 1 \forall i in f F_{r, κ} (X) = X \in E_{m}^{blk} in f F_{r, κ} (X) .$

On the implementable side take $S_{bal} = P_{m}^{bal}, T_{sym} = P_{m}^{sym}, f (P) = F_{r, κ} (X (P)) .$ Then $T_{sym} \subseteq S_{bal}$ by Definition 3; $T_{sym} \neq = \emptyset$ because the iid fair-sign law is block-exchangeable; and $f$ is bounded below because every second moment $X (P) = E_{P} [Z Z^{⊤}]$ is positive semidefinite with unit diagonal, hence belongs to $S_{rel}$ and satisfies the lower bound just displayed. Steps 4–5 supply, for every $P \in S_{bal}$ , the law $P^{orb} \in T_{sym}$ with no larger objective. Step 6 gives $P \in P_{m}^{bal} in f F_{r, κ} (X (P)) = P \in P_{m}^{sym} in f F_{r, κ} (X (P)) .$

∎

Proof of Theorem 1.

By the two-block homophily assumption, $m \geq 2$ , $0 < b < a$ . Hence $q = 2 (m - 1) > 0, a - b > 0, a + b > 0, 2 b > 0.$ Set $A = 2 b (a + b) (1 - \frac{κ}{a - b}), B = 2 b (2 m - 2 b - κ) .$ From $r < max {0, min (A, B)}$ and $0 \leq r$ , we first get $r < min (A, B) .$ Indeed, if $min (A, B) \leq 0$ , then the outer maximum is $0$ , contradicting $0 \leq r < 0$ . Otherwise the outer maximum is $min (A, B)$ . Thus $r < A, r < B .$
We now convert these two inequalities into the coefficient separations needed at the cut vertex. From $r < A$ , division by the positive number $2 b (a + b)$ gives $\frac{r}{2 b ( a + b )} < 1 - \frac{κ}{a - b} .$ Multiplying by $a - b > 0$ and rearranging gives $κ < (a - b) (1 - \frac{r}{2 b ( a + b )}) .$ Using $(a + b) + \frac{r}{a + b} - (2 b + \frac{r}{2 b} + κ) = (a - b) (1 - \frac{r}{2 b ( a + b )}) - κ$ and $c_{x} / q = (a + b) + r / (a + b)$ , $c_{y} = 2 b + r / (2 b)$ , we obtain $\frac{c _{x}}{q} > c_{y} + κ .$ Similarly, from $r < B$ , division by $2 b > 0$ gives $\frac{r}{2 b} < 2 m - 2 b - κ,$ and hence $2 b + \frac{r}{2 b} + κ < 2 m .$ Since $c_{z} = 2 m$ , this is $c_{z} > c_{y} + κ .$
The hypotheses of Lemma 2 are therefore satisfied: $q > 0$ , $κ \geq 0$ , and the two coefficient separations above hold. Hence $(0, 2 m, 0) \in T_{m},$ and every other point of $T_{m}$ has strictly larger reduced objective value.

By Lemma 1, the cut covariance is $X_{cut} = X (1, - 1),$ and its spectral coordinates are $(1 - 1, 1 + (m - 1) \cdot 1 - m (- 1), 1 + (m - 1) \cdot 1 + m (- 1)) = (0, 2 m, 0) .$ Thus $X_{cut} \in E_{m}^{blk}$ , and $F_{r, κ} (X_{cut}) = ϕ_{r, κ} (0, 2 m, 0) .$
Let $X \in E_{m}^{blk}$ and suppose $X \neq = X_{cut}$ . Write $X = X (u, v)$ . By Lemma 1, the associated coordinates $x = 1 - u, y = 1 + (m - 1) u - m v, z_{sp} = 1 + (m - 1) u + m v$ belong to $T_{m}$ , and $F_{r, κ} (X) = ϕ_{r, κ} (x, y, z_{sp}) .$ These coordinates cannot equal $(0, 2 m, 0)$ : if $x = 0$ , then $u = 1$ , and if also $z_{sp} = 0$ , then $0 = 1 + (m - 1) \cdot 1 + m v = m (1 + v),$ so $v = - 1$ since $m > 0$ , giving $X = X_{cut}$ , a contradiction. The strict part of Lemma 2 therefore gives $F_{r, κ} (X_{cut}) = ϕ_{r, κ} (0, 2 m, 0) < ϕ_{r, κ} (x, y, z_{sp}) = F_{r, κ} (X) .$ Thus $X_{cut}$ is the unique minimizer over $E_{m}^{blk}$ .
The cut design $P_{cut}$ puts mass $1/2$ on the cut assignment $z^{+}$ ( $+ 1$ on $A_{m}$ , $- 1$ on $B_{m}$ ) and mass $1/2$ on its global sign reversal $z^{-} = - z^{+}$ . It is therefore sign-symmetric, i.e. $P_{cut} (Z = z) = P_{cut} (Z = - z)$ for all $z$ . Its two-point support is invariant under the two-block automorphism group: a permutation preserving both communities fixes each of $z^{+}$ and $z^{-}$ , and the community swap exchanges them. Hence $P_{cut} \in P_{m}^{sym} .$

Moreover $z_{i}^{+} z_{j}^{+} = z_{i}^{-} z_{j}^{-}$ for all $i, j$ , so both atoms contribute the same product and $X (P_{cut})_{ij} = E [Z_{i} Z_{j}] = z_{i}^{+} z_{j}^{+} = (X_{cut})_{ij}, i.e. X (P_{cut}) = X_{cut} .$

Consequently $X_{cut} \in C_{m}^{\pm}$ .

Next, every $X \in C_{m}^{\pm}$ is the second moment of a design $P \in P_{m}^{sym}$ . Because $P$ is invariant under the two-block automorphism group and $m \geq 2$ , all within-community off-diagonal second moments coincide and all across-community ones coincide, so $X = X (u, v) for some u, v,$

and Lemma 5 places its spectral coordinates in the reduced triangle $T_{m}$ . By Lemma 1 this membership is exactly block-elliptope membership, so $C_{m}^{\pm} \subseteq E_{m}^{blk} .$

Therefore, if $X \in C_{m}^{\pm}$ and $X \neq = X_{cut}$ , the strict relaxed optimality already proved yields $F_{r, κ} (X_{cut}) < F_{r, κ} (X) .$ Thus $X_{cut}$ is also the unique minimizer over $C_{m}^{\pm}$ .
It remains to identify the gap. From the strict inequalities above, with equality allowed only at $X_{cut}$ , we have the non-strict minimizing inequalities $F_{r, κ} (X_{cut}) \leq F_{r, κ} (X) for all X \in E_{m}^{blk},$ and $F_{r, κ} (X_{cut}) \leq F_{r, κ} (X) for all X \in C_{m}^{\pm} .$ Since $X_{cut}$ belongs to both feasible classes, each of the two infima is attained at $X_{cut}$ : $X \in E_{m}^{blk} in f F_{r, κ} (X) = F_{r, κ} (X_{cut}) = X \in C_{m}^{\pm} in f F_{r, κ} (X) .$ Hence, by the definition of the implementability gap in Definition 7, $Δ_{m}^{\pm} (r, κ) = F_{r, κ} (X_{cut}) - F_{r, κ} (X_{cut}) = 0.$ This proves all asserted conclusions.

∎

Proof of Theorem 2.

We first prove the finite-weight equivalence. Write $q = 2 (m - 1), c_{x} = q ((a + b) + \frac{r}{a + b}), c_{y} = 2 b + \frac{r}{2 b}, c_{z} = 2 m .$ Suppose that some $κ \geq 0$ makes $I_{n}$ a relaxed minimizer over $E_{m}^{blk}$ . For an arbitrary $(x, y, z_{sp}) \in T_{m}$ , set $u = 1 - x, v = \frac{z _{sp} - y}{2 m} .$ The simplex equation $q x + y + z_{sp} = 2 m$ gives $1 + (m - 1) u = \frac{1}{2} (y + z_{sp})$ , so these formulas recover $1 - u = x, 1 + (m - 1) u - m v = y, 1 + (m - 1) u + m v = z_{sp} .$

Using Lemma 1, this inverse change of variables sends $(x, y, z_{sp})$ to a feasible block matrix $X (u, v)$ , and the matrix objective equals the reduced objective at $(x, y, z_{sp})$ . Since $I_{n} = X (0, 0)$ corresponds to $(1, 1, 1)$ , so that $F_{r, κ} (I_{n}) = ϕ_{r, κ} (1, 1, 1),$

the assumed matrix minimality says that $(1, 1, 1)$ minimizes $c_{x} x + c_{y} y + c_{z} z_{sp} + κ q x^{2} + y^{2} + z_{sp}^{2}$ on $T_{m}$ . The certificate-necessity part of Lemma 4 therefore gives $\frac{c _{x}}{q} = c_{y}, c_{y} = c_{z} .$

The first equality is $a + b + \frac{r}{a + b} = 2 b + \frac{r}{2 b},$ and by the identity $(a + b + \frac{r}{a + b}) - (2 b + \frac{r}{2 b}) = (a - b) (1 - \frac{r}{2 b ( a + b )})$ this is equivalent to $(a - b) (1 - \frac{r}{2 b ( a + b )}) = 0.$ By two-block homophily, $a > b > 0$ , so $a - b \neq = 0$ and the second factor vanishes: $r = 2 b (a + b) .$

Substituting this into $c_{y} = c_{z}$ gives $2 b + \frac{2 b ( a + b )}{2 b} = 2 m,$ that is $a + 3 b = 2 m$ . Thus the affine-balanced locus holds. Conversely, if $a + 3 b = 2 m, r = 2 b (a + b),$ then substituting $r = 2 b (a + b)$ into the three coefficients gives $\frac{c _{x}}{q} = (a + b) + \frac{2 b ( a + b )}{a + b} = a + 3 b, c_{y} = 2 b + \frac{2 b ( a + b )}{2 b} = a + 3 b, c_{z} = 2 m = a + 3 b,$ so $c_{x} / q = c_{y} = c_{z}$ . Taking $κ = 1$ , the strict optimality part of Lemma 4, transported through Lemma 1, gives $I_{n} \in E_{m}^{blk}$ and strict optimality against every $X \neq = I_{n}$ . For $X = I_{n}$ the desired inequality is equality, while for $X \neq = I_{n}$ it follows from strict optimality. Hence a finite nonnegative robustness weight exists exactly on the stated locus.
On the affine-balanced locus, let $κ > 0$ . As above, $\frac{c _{x}}{q} = c_{y} = c_{z} .$ The point $I_{n} = X (0, 0)$ has reduced coordinates $(1, 1, 1)$ by Lemma 1. The Frobenius-center certificate, Lemma 4, gives strict reduced optimality of $(1, 1, 1)$ on $T_{m}$ . Translating back by Lemma 1, $I_{n} \in E_{m}^{blk}$ , and for any $X = X (u, v) \in E_{m}^{blk}$ with $X \neq = I_{n}$ , the associated reduced coordinates are not $(1, 1, 1)$ : if they were, then $x = 1$ gives $u = 0$ , and then $z_{sp} = 1$ reads $1 + m v = 1$ , so $v = 0$ since $m > 0$ , i.e. $X = I_{n}$ . Therefore $F_{r, κ} (I_{n}) < F_{r, κ} (X) .$
The iid law assigns mass $2^{- n}$ to every sign vector, so it is invariant under sign flip, under within-block permutations, and under the block swap, whence $P_{iid} \in P_{m}^{sym} .$ Its second moments are diagonal: the diagonal entries are $E [Z_{i}^{2}] = 1$ , and for $i \neq = j$ the involution $z \mapsto z^{'}$ that flips only the $i$ -th sign is a bijection of the assignment space preserving the uniform law and sending $Z_{i} Z_{j}$ to $- Z_{i} Z_{j}$ , so $E [Z_{i} Z_{j}] = - E [Z_{i} Z_{j}] = 0 (i \neq = j) .$ Thus all off-diagonal moments vanish and $X (P_{iid}) = I_{n} .$
Now assume the affine-balanced locus fails. If for some $κ > 0$ the matrix $I_{n}$ were a relaxed minimizer, then the same center-coefficient necessity argument from the first step would give $\frac{c _{x}}{q} = c_{y}, c_{y} = c_{z},$ and the same algebra would force $a + 3 b = 2 m, r = 2 b (a + b),$ contradicting the assumption. Hence $I_{n}$ is not a relaxed minimizer at any positive finite robustness weight off the locus.
Finally, let $(X_{κ})_{κ \in R}$ be any family of relaxed minimizers for positive $κ$ . Since $r \geq 0$ , $a > b > 0$ and $m \geq 2$ , the reduced linear coefficients satisfy $c_{x}, c_{y}, c_{z} \geq 0$ ; and every point of $T_{m}$ has nonnegative coordinates, so the linear part $c_{x} x + c_{y} y + c_{z} z_{sp}$ is nonnegative on $T_{m}$ . Put $L = c_{x} + c_{y} + c_{z} .$ The reduced coordinates of $I_{n}$ are $(1, 1, 1)$ , whose weighted squared norm is $q \cdot 1 + 1 + 1 = q + 2 = 2 m$ ; hence, by Lemma 1, $F_{r, κ} (I_{n}) = L + κ 2 m for every κ .$ Comparing each minimizer with the feasible point $I_{n}$ gives $F_{r, κ} (X_{κ}) \leq F_{r, κ} (I_{n}) = L + κ 2 m .$ Writing $X_{κ} = X (u_{κ}, v_{κ})$ and setting $N_{w} = 2 m (m - 1) > 0, N_{a} = 2 m^{2} > 0,$ the reduced squared norm decomposes as $q (1 - u_{κ})^{2} + (1 + (m - 1) u_{κ} - m v_{κ})^{2} + (1 + (m - 1) u_{κ} + m v_{κ})^{2} = 2 m + N_{w} u_{κ}^{2} + N_{a} v_{κ}^{2} .$

Suppose some within-community off-diagonal entry stayed at distance at least $ε > 0$ from its target for arbitrarily large $κ$ ; that entry equals $u_{κ}$ , so $∣ u_{κ} ∣ \geq ε$ and the displayed squared norm is at least $2 m + N_{w} ε^{2}$ . Setting $δ = 2 m + N_{w} ε^{2} - 2 m > 0,$ the robustness term at $X_{κ}$ is therefore at least $κ (2 m + δ)$ , and, the linear part being nonnegative, $κ (2 m + δ) \leq F_{r, κ} (X_{κ}) \leq L + κ 2 m,$ which forces $κ δ \leq L$ ; this fails for every $κ > L / δ$ , a contradiction. Hence $u_{κ} \to 0$ . The same argument with $N_{a}$ in place of $N_{w}$ , applied to an across-community entry (which equals $v_{κ}$ ), shows $v_{κ} \to 0$ . Diagonal entries of $X_{κ}$ are identically $1$ , matching $I_{n}$ exactly, while off-diagonal entries are either $u_{κ}$ or $v_{κ}$ and the corresponding entries of $I_{n}$ are $0$ . Hence every entry of $X_{κ}$ converges to the corresponding entry of $I_{n}$ as $κ \to \infty$ .

∎

Proof of Theorem 3.

1. Assumption 1 gives $m \geq 2$ , $b < a$ , and $b > 0$ . Hence $q = 2 (m - 1) > 0, q > 0, a + b > 0, a - b > 0.$ Assumption 3 gives $2 m - a - 3 b > 0.$ These inequalities are the standing sign facts used below for division and multiplication by positive quantities.

2. Assume now that Assumption 4 holds, and fix $0 \leq κ < κ_{gap} (m, a, b) = \frac{( 2 m - a - 3 b ) ( a - b ) q}{a + b} .$ Multiplying this strict inequality by the positive factor $(a + b) / ((a - b) q)$ , $\frac{κ ( a + b )}{( a - b ) q} < 2 m - a - 3 b .$ Next, from $1 + \frac{2 b}{a - b} = \frac{a + b}{a - b}$ we get the identity $R_{x}^{+} - R_{x}^{-} = (a + b) (2 m - a - b - \frac{κ}{q}) - 2 b (a + b) (1 + \frac{κ}{( a - b ) q}) = (a + b) ((2 m - a - 3 b) - \frac{κ ( a + b )}{( a - b ) q}),$ whose right-hand side is positive by the previous display and $a + b > 0$ . Thus $R_{x}^{-} < R_{x}^{+} = r_{gap}^{+}$ , and since $r_{gap}^{-} = \frac{R _{x}^{-} + R _{x}^{+}}{2}$ is the midpoint of $R_{x}^{-}$ and $R_{x}^{+}$ , $R_{x}^{-} < r_{gap}^{-} < r_{gap}^{+} .$ Also $R_{x}^{-} \geq 0$ , because $2 b (a + b) > 0$ and $κ / ((a - b) q) \geq 0$ ; and since $1 - κ / (a - b) \leq 1 \leq 1 + κ / ((a - b) q)$ and $2 b (a + b) > 0$ , $2 b (a + b) (1 - \frac{κ}{a - b}) \leq R_{x}^{-},$ so, the maximum of two quantities each at most $R_{x}^{-}$ being at most $R_{x}^{-}$ , $r_{cut, gap} (m, a, b, κ) = max {0, 2 b (a + b) (1 - \frac{κ}{a - b})} \leq R_{x}^{-} .$ Combining these inequalities yields $r_{cut, gap} (m, a, b, κ) < r_{gap}^{-} (m, a, b, κ) < r_{gap}^{+} (m, a, b, κ) .$

3. Let $r_{gap}^{-} < r < r_{gap}^{+}$ . From the preceding step, $R_{x}^{-} < r .$ After division by $2 b (a + b) > 0$ , this says $1 + \frac{κ}{( a - b ) q} < \frac{r}{2 b ( a + b )} .$ Multiplying by $a - b > 0$ gives $\frac{κ}{q} < (a - b) (\frac{r}{2 b ( a + b )} - 1) .$ Using the identity $2 b + \frac{r}{2 b} - (a + b + \frac{r}{a + b}) = (a - b) (\frac{r}{2 b ( a + b )} - 1),$ and $c_{x} / q = a + b + r / (a + b)$ , this proves $c_{y} > \frac{c _{x}}{q} + \frac{κ}{q} .$ Similarly, the upper bound $r < r_{gap}^{+} = R_{x}^{+} = (a + b) (2 m - a - b - κ / q)$ , divided by $a + b > 0$ , gives $\frac{r}{a + b} < 2 m - a - b - \frac{κ}{q},$ hence, since $c_{z} = 2 m$ and $c_{x} / q = a + b + r / (a + b)$ , $c_{z} > \frac{c _{x}}{q} + \frac{κ}{q} .$ By Lemma 3, the point $(\frac{2 m}{q}, 0, 0) = (\frac{m}{m - 1}, 0, 0)$ belongs to $T_{m}$ and is the strict unique minimizer of the reduced objective on $T_{m}$ .

4. The spread covariance is $X (- 1/ (m - 1), 0)$ , whose spectral coordinates are $x = 1 - (- \frac{1}{m - 1}) = \frac{m}{m - 1} = \frac{2 m}{q}, y = 1 - \frac{m - 1}{m - 1} = 0, z_{sp} = 0.$ By Lemma 1, the membership of this triple in $T_{m}$ gives $X_{spread} \in E_{m}^{blk},$ and the value of $F_{r, κ}$ at $X_{spread}$ is the reduced objective at $(2 m / q, 0, 0)$ . If $X \in E_{m}^{blk}$ , write $X = X (u, v)$ . Lemma 1 sends it to a point of $T_{m}$ and identifies $F_{r, κ} (X)$ with the reduced objective there. If this reduced point equals $(2 m / q, 0, 0)$ , then $y = z_{sp} = 0$ , so $z_{sp} - y = 2 m v = 0 and y + z_{sp} = 2 + 2 (m - 1) u = 0,$ forcing $v = 0$ and $u = - 1/ (m - 1)$ , hence $X = X_{spread}$ . Therefore every $X \neq = X_{spread}$ corresponds to a different point of $T_{m}$ , and the strict reduced optimality just proved gives $F_{r, κ} (X_{spread}) < F_{r, κ} (X) .$

5. Since $m$ is odd, Lemma 5 gives $d_{m} = 2/ m > 0$ for the implementable reduced slice. The spread point has $y + z_{sp} = 0 < d_{m},$ so $X_{spread} \in / C_{m}^{\pm} .$ For the loss, pass from $(x, y, z_{sp}) \in T_{m}$ to the simplex variable $t = (q x, y, z_{sp}), t_{x} + t_{y} + t_{z} = q x + y + z_{sp} = 2 m = M,$ with inverse $(t_{x}, t_{y}, t_{z}) \mapsto (t_{x} / q, t_{y}, t_{z})$ . With the coefficients and weights $α = (\frac{c _{x}}{q}, c_{y}, c_{z}), β = (\frac{1}{q}, 1, 1),$ this change of variables matches the two objectives exactly: $i \sum α_{i} t_{i} = \frac{c _{x}}{q} q x + c_{y} y + c_{z} z_{sp} = c_{x} x + c_{y} y + c_{z} z_{sp}, i \sum β_{i} t_{i}^{2} = \frac{( q x ) ^{2}}{q} + y^{2} + z_{sp}^{2} = q x^{2} + y^{2} + z_{sp}^{2},$ so $Φ_{α, β, κ} (t) = ϕ_{r, κ} (x, y, z_{sp})$ , and the parity constraint reads $t_{y} + t_{z} \geq d_{m} .$ Under this dictionary the relaxed minimizer displayed above is $t^{rel} = (2 m, 0, 0), t_{y}^{rel} + t_{z}^{rel} = 0 < d_{m} .$ It is in $Δ_{M}$ and minimizes $Φ_{α, β, κ}$ over $Δ_{M}$ , because the corresponding reduced point minimizes $ϕ_{r, κ}$ over $T_{m}$ . The data for the relaxed-minimizer truncation argument are therefore in place: $d_{m} \leq M = 2 m$ , $β_{x} = 1/ q \geq 0$ , $β_{y} = β_{z} = 1$ , $κ \geq 0$ , and $t^{rel}$ is a global minimizer on $Δ_{M}$ . That argument says the following. If a relaxed minimizer satisfies $t_{y} + t_{z} \geq d_{m}$ , it remains minimizing after truncation; if it satisfies $t_{y} + t_{z} < d_{m}$ , then the boundary-selector point $t^{⋆} = (M - d_{m}, s^{⋆}, d_{m} - s^{⋆}), s^{⋆} = truncSelector (M, d_{m}, α, β, κ),$ belongs to $K_{d_{m}} = {t \in Δ_{M} : t_{y} + t_{z} \geq d_{m}}$ and minimizes $Φ_{α, β, κ}$ over $K_{d_{m}}$ . Indeed, the feasible case is immediate from relaxed optimality; in the infeasible case, every truncated feasible point is reduced to a point on the boundary segment $(M - d_{m}, s, d_{m} - s)$ , and the selector $s^{⋆}$ minimizes the resulting one-dimensional objective on $[0, d_{m}]$ .

Since $t_{y}^{rel} + t_{z}^{rel} < d_{m}$ , the second alternative supplies such a minimizer $t^{⋆}$ . Translating back, $(x^{⋆}, y^{⋆}, z_{sp}^{⋆}) = (\frac{t _{x}^{⋆}}{q}, t_{y}^{⋆}, t_{z}^{⋆}) \in T_{m}$ satisfies $y^{⋆} + z_{sp}^{⋆} \geq d_{m}$ and minimizes $ϕ_{r, κ}$ over the parity-truncated slice. In particular both infima in Lemma 8 are attained: $(x, y, z_{sp}) \in T_{m} in f ϕ_{r, κ} = ϕ_{r, κ} (\frac{2 m}{q}, 0, 0), (x, y, z_{sp}) \in T_{m} y + z_{sp} \geq d_{m} in f ϕ_{r, κ} = ϕ_{r, κ} (x^{⋆}, y^{⋆}, z_{sp}^{⋆}) .$ The truncated minimizer is feasible for the relaxed problem but differs from the relaxed minimizer, because $y^{⋆} + z_{sp}^{⋆} \geq d_{m} > 0$ while the relaxed minimizer has $y + z_{sp} = 0$ ; the strict reduced uniqueness above therefore gives $ϕ_{r, κ} (\frac{2 m}{q}, 0, 0) < ϕ_{r, κ} (x^{⋆}, y^{⋆}, z_{sp}^{⋆}) .$ Finally Lemma 8 identifies $Δ_{m}^{\pm} (r, κ)$ with the truncated reduced infimum minus the relaxed reduced infimum, so $Δ_{m}^{\pm} (r, κ) > 0.$

6. It remains to prove the even case. Assume $m$ is even and let $X \in E_{m}^{blk}$ . Write $X = X (u, v)$ , and let $(x, y, z_{sp})$ be its spectral coordinates. By Lemma 1, this point lies in $T_{m}$ , so $y, z_{sp} \geq 0$ . For even $m$ , the parity threshold in Lemma 5 is $d_{m} = 0$ , and hence $y + z_{sp} \geq 0$ automatically. The same lemma therefore gives $X \in C_{m}^{\pm}$ . Thus $E_{m}^{blk} \subseteq C_{m}^{\pm} .$

∎

Proof of Theorem 4.

Throughout Assumption 1 gives $m \geq 2$ , hence $q = 2 (m - 1) > 0$ , $a + b > 0$ , and $2 b > 0$ ; together with $r \geq 0$ , this makes the reduced linear coefficients nonnegative, $c_{x} = q ((a + b) + \frac{r}{a + b}) \geq 0, c_{y} = 2 b + \frac{r}{2 b} \geq 0, c_{z} = 2 m \geq 0.$ Write $M = 2 m$ and record the change of variables used below: $t = (q x, y, z_{sp}), α^{♯} = (\frac{c _{x}}{q}, c_{y}, c_{z}), β^{♯} = (\frac{1}{q}, 1, 1) .$ Since $q > 0$ , this map carries $T_{m}$ to the simplex $Δ_{M}$ and the inverse formula $t \mapsto (t_{x} / q, t_{y}, t_{z})$ carries $Δ_{M}$ back to $T_{m}$ . The mass equation $q x + y + z_{sp} = 2 m$ becomes $t_{x} + t_{y} + t_{z} = M$ , the parity constraint becomes $t_{y} + t_{z} \geq d_{m}$ , and the objectives match: $i \sum α_{i}^{♯} t_{i} = \frac{c _{x}}{q} q x + c_{y} y + c_{z} z_{sp} = c_{x} x + c_{y} y + c_{z} z_{sp}, i \sum β_{i}^{♯} t_{i}^{2} = \frac{( q x ) ^{2}}{q} + y^{2} + z_{sp}^{2} = q x^{2} + y^{2} + z_{sp}^{2},$ so that $Φ_{α^{♯}, β^{♯}, κ} (t) = ϕ_{r, κ} (x, y, z_{sp}) .$ We also use $0 \leq d_{m} \leq M$ , since $d_{m} \in {0, 2/ m}$ and $m \geq 2$ .

Equality and range. By definition, $ρ_{⋆} (m, a, b, r, κ)$ is the reduced implementable-minus-relaxed value, $ρ_{⋆} (m, a, b, r, κ) = (x, y, z_{sp}) \in T_{m} y + z_{sp} \geq d_{m} in f ϕ_{r, κ} (x, y, z_{sp}) - (x, y, z_{sp}) \in T_{m} in f ϕ_{r, κ} (x, y, z_{sp}) .$ The reduced gap identity in Lemma 8 identifies $Δ_{m}^{\pm} (r, κ)$ with this same difference. Hence $ρ_{⋆} (m, a, b, r, κ) = Δ_{m}^{\pm} (r, κ) .$

For the range, every point of $T_{m}$ has nonnegative coordinates, and $κ \geq 0$ ; with the coefficient inequalities above, $ϕ_{r, κ} (x, y, z_{sp}) = c_{x} x + c_{y} y + c_{z} z_{sp} + κ q x^{2} + y^{2} + z_{sp}^{2} \geq 0.$ The truncated feasible set is nonempty because $(1, 1, 1) \in T_{m}$ and $1 + 1 \geq d_{m}$ . Since the truncated feasible set is contained in $T_{m}$ , the constrained reduced infimum is at least the unconstrained one, and therefore $ρ_{⋆} (m, a, b, r, κ) \geq 0.$ Together with the equality just proved, this gives $Δ_{m}^{\pm} (r, κ) \geq 0$ .

Zero loss. The reduced minima used in the zero-loss argument are attained by the simplex construction above. For the relaxed problem, if $κ > 0$ , the positive-robustness clause of Lemma 6 supplies an active-set minimizer of $Φ_{α^{♯}, β^{♯}, κ}$ on $Δ_{M}$ ; if $κ = 0$ , the zero-robustness clause identifies the exposed $α^{♯}$ -minimizing face, and placing the mass $M$ on a coordinate where $α_{i}^{♯}$ is minimal gives a relaxed minimizer. Transporting this point back gives $ξ^{rel} \in T_{m}$ such that $ϕ_{r, κ} (ξ^{rel}) \leq ϕ_{r, κ} (x, y, z_{sp}) for all (x, y, z_{sp}) \in T_{m} .$ For the truncated problem, apply the truncation dichotomy in Lemma 7 to the image of a relaxed minimizer. If that image lies in $K_{d_{m}} = {t \in Δ_{M} : t_{y} + t_{z} \geq d_{m}}$ , it remains minimizing on $K_{d_{m}}$ ; otherwise the selector point on the segment $t_{y} + t_{z} = d_{m}$ minimizes on $K_{d_{m}}$ . Transporting the selected point back gives $ξ^{impl} \in T_{m}$ with $d_{m} \leq ξ_{y}^{impl} + ξ_{z}^{impl}$ and $ϕ_{r, κ} (ξ^{impl}) \leq ϕ_{r, κ} (x, y, z_{sp}) whenever (x, y, z_{sp}) \in T_{m} and d_{m} \leq y + z_{sp} .$ Thus the two reduced values are the objective values at $ξ^{rel}$ and $ξ^{impl}$ , and $ρ_{⋆} = ϕ_{r, κ} (ξ^{impl}) - ϕ_{r, κ} (ξ^{rel}) .$

If $ρ_{⋆} = 0$ , the two displayed objective values are equal. Since $ξ^{impl}$ is feasible for the relaxed problem and attains the relaxed value, it is a relaxed minimizer satisfying $d_{m} \leq ξ_{y}^{impl} + ξ_{z}^{impl}$ . Conversely, if some $(x, y, z_{sp}) \in T_{m}$ minimizes $ϕ_{r, κ}$ over $T_{m}$ and satisfies $d_{m} \leq y + z_{sp}$ , then it is feasible for the truncated problem, so $ϕ_{r, κ} (ξ^{rel}) \leq ϕ_{r, κ} (ξ^{impl}) \leq ϕ_{r, κ} (x, y, z_{sp}) = ϕ_{r, κ} (ξ^{rel}),$ forcing equality throughout and $ρ_{⋆} = 0$ . This proves $ρ_{⋆} = 0 ⟺ some relaxed minimizer of ϕ_{r, κ} on T_{m} satisfies d_{m} \leq y + z_{sp} .$

Strict robustness. Assume $κ > 0$ . Under the same change of variables, the positive-robustness clause of Lemma 6 gives a strictly unique minimizer of $Φ_{α^{♯}, β^{♯}, κ}$ on $Δ_{M}$ . Transporting it back gives exactly one minimizer of $ϕ_{r, κ}$ on $T_{m}$ . With uniqueness in hand, the assertion that some relaxed minimizer satisfies $d_{m} \leq y + z_{sp}$ is equivalent to the assertion that every relaxed minimizer satisfies it. The zero-loss criterion therefore becomes $ρ_{⋆} = 0 ⟺ every minimizer (x, y, z_{sp}) of ϕ_{r, κ} on T_{m} has d_{m} \leq y + z_{sp} .$

Linear case. Assume $κ = 0$ , and fix $(x, y, z_{sp}) \in T_{m}$ . Passing to $t = (q x, y, z_{sp})$ , the reduced objective is the linear weighted-simplex objective $\sum_{i} α_{i}^{♯} t_{i}$ . The zero-robustness clause of Lemma 6 says that $t$ minimizes it over $Δ_{M}$ exactly when $t_{i} \neq = 0 ⟹ α_{i}^{♯} \leq α_{j}^{♯} for every j .$ Since $q > 0$ , $t_{x} \neq = 0$ is equivalent to $x \neq = 0$ , while $t_{y} = y$ and $t_{z} = z_{sp}$ ; and $α^{♯} = (c_{x} / q, c_{y}, c_{z})$ . Reading the three coordinates in turn, this condition is exactly $x \neq = 0 \Rightarrow \frac{c _{x}}{q} \leq c_{y} and \frac{c _{x}}{q} \leq c_{z}, y \neq = 0 \Rightarrow c_{y} \leq \frac{c _{x}}{q} and c_{y} \leq c_{z}, z_{sp} \neq = 0 \Rightarrow c_{z} \leq \frac{c _{x}}{q} and c_{z} \leq c_{y},$ as asserted.

Active-set formula. Assume $κ > 0$ . The active-set construction from Lemma 6 supplies an admissible support $S \subseteq {x, y, z_{sp}}$ and multiplier $λ$ for $α^{♯}, β^{♯}, κ$ . Write the associated simplex point as $t^{S, λ}$ . It is nonnegative and satisfies $t_{x}^{S, λ} + t_{y}^{S, λ} + t_{z}^{S, λ} = M = 2 m$ ; therefore its preimage has nonnegative coordinates and satisfies $q (\frac{t _{x}^{S, λ}}{q}) + t_{y}^{S, λ} + t_{z}^{S, λ} = 2 m, (\frac{t _{x}^{S, λ}}{q}, t_{y}^{S, λ}, t_{z}^{S, λ}) \in T_{m} .$ The weighted-simplex minimizer property transfers back through the objective identity, so this reduced point minimizes $ϕ_{r, κ}$ over $T_{m}$ . The value formula in Lemma 6 gives $Φ_{α^{♯}, β^{♯}, κ} (t^{S, λ}) = M λ$ , and hence the relaxed reduced value is $(x, y, z_{sp}) \in T_{m} in f ϕ_{r, κ} = 2 m λ .$

Truncation correction. Suppose no relaxed minimizer in $T_{m}$ satisfies $d_{m} \leq y + z_{sp}$ . Let $ξ^{rel}$ be a relaxed minimizer supplied by the simplex construction, and let $t^{rel} = (q ξ_{x}^{rel}, ξ_{y}^{rel}, ξ_{z}^{rel})$ . Then $t^{rel} \in Δ_{M}$ , it minimizes $Φ_{α^{♯}, β^{♯}, κ}$ over $Δ_{M}$ , and the hypothesis gives $t_{y}^{rel} + t_{z}^{rel} < d_{m}$ . In the case $κ = 0$ , the tie convention in Lemma 7 is vacuous under this hypothesis, because the exposed relaxed face is disjoint from $K_{d_{m}}$ . Since $0 \leq d_{m} \leq M$ , Lemma 7 puts a minimizer of $Φ_{α^{♯}, β^{♯}, κ}$ over $K_{d_{m}} = {t \in Δ_{M} : t_{y} + t_{z} \geq d_{m}}$ on the boundary segment $H_{d_{m}} = {(2 m - d_{m}, s, d_{m} - s) : 0 \leq s \leq d_{m}}$ at $s_{⋆} = truncSelector (2 m, d_{m}, α^{♯}, β^{♯}, κ) .$ Define the reduced implementable value by $val_{impl} (m, a, b, r, κ) := (x, y, z_{sp}) \in T_{m} d_{m} \leq y + z_{sp} in f ϕ_{r, κ} (x, y, z_{sp}) .$ The change of variables carries $K_{d_{m}}$ onto the parity-truncated slice of $T_{m}$ and preserves objective values. Therefore $val_{impl} (m, a, b, r, κ) = Φ_{α^{♯}, β^{♯}, κ} (2 m - d_{m}, s_{⋆}, d_{m} - s_{⋆}) .$

Even block size. If $m$ is even, then $d_{m} = 0$ . A relaxed minimizer exists by the simplex construction, and every point of $T_{m}$ has $y, z_{sp} \geq 0$ , hence $0 = d_{m} \leq y + z_{sp}$ . The zero-loss criterion gives $ρ_{⋆} (m, a, b, r, κ) = 0.$

∎

References

Thiyageswaran, Vydhourie and Kokot, Alex and Brennan, Jennifer and Meila, Marina and Yu, Christina Lee and Fazel, Maryam (2026). Optimal Design under Interference, Homophily, and Robustness Trade-offs. . arXiv
Horvitz, Daniel G. and Thompson, Donovan J. (1952). A Generalization of Sampling Without Replacement from a Finite Universe. Journal of the American Statistical Association. doi
Rubin, Donald B. (1974). Estimating Causal Effects of Treatments in Randomized and Nonrandomized Studies. Journal of Educational Psychology. doi
Hudgens, Michael G. and Halloran, M. Elizabeth (2008). Toward Causal Inference with Interference. Journal of the American Statistical Association. doi
Aronow, Peter M. and Samii, Cyrus (2013). Estimating Average Causal Effects Under General Interference, with Application to a Social Network Experiment. . arXiv
Fredrik Sävje and Peter M. Aronow and Michael G. Hudgens (2017). Average treatment effects in the presence of unknown interference. . arXiv
Ugander, Johan and Yin, Hao (2020). Randomized Graph Cluster Randomization. . arXiv
Baird, Sarah and Bohren, J. Aislinn and McIntosh, Craig and {\"O}zler, Berk (2018). Optimal Design of Experiments in the Presence of Interference. Review of Economics and Statistics. doi
Li, Wenrui and Sussman, Daniel L. and Kolaczyk, Eric D. (2021). Causal Inference under Network Interference with Noise. . arXiv
Fredrik Sävje (2021). Causal inference with misspecified exposure mappings: separating definitions and assumptions. . arXiv
Leung, Michael P. (2019). Causal Inference Under Approximate Neighborhood Interference. . arXiv
Li, Shuangning and Wager, Stefan (2020). Random Graph Asymptotics for Treatment Effect Estimation under Network Interference. . arXiv
Zigler, Corwin M. and Papadogeorgou, Georgia (2018). Bipartite Causal Inference with Interference. . arXiv
Efron, Bradley (1971). Forcing a Sequential Experiment to Be Balanced. Biometrika. doi
Morgan, Kari Lock and Rubin, Donald B. (2012). Rerandomization to Improve Covariate Balance in Experiments. The Annals of Statistics. doi
Harshaw, Christopher and S{\"a}vje, Fredrik and Spielman, Daniel and Zhang, Peng (2019). Balancing Covariates in Randomized Experiments with the Gram-Schmidt Walk Design. . arXiv
Goemans, Michel X. and Williamson, David P. (1995). Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. Journal of the ACM. doi
Deza, Michel M. and Laurent, Monique (1997). Geometry of Cuts and Metrics. Springer.
Boyd, Stephen and Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press.
McPherson, Miller and Smith-Lovin, Lynn and Cook, James M. (2001). Birds of a Feather: Homophily in Social Networks. Annual Review of Sociology. doi
Holland, Paul W. and Laskey, Kathryn Blackmond and Leinhardt, Samuel (1983). Stochastic Blockmodels: First Steps. Social Networks. doi
Newman, M. E. J. (2002). Assortative Mixing in Networks. Physical Review Letters. doi
Abbe, Emmanuel (2018). Community Detection and Stochastic Block Models. Foundations and Trends in Communications and Information Theory. doi
Banerjee, Abhijit and Chandrasekhar, Arun G. and Duflo, Esther and Jackson, Matthew O. (2013). The Diffusion of Microfinance. Science. doi

Formal layer — Lean correspondence

Every object below is formalized in Lean 4. Click a verified row to view its statement; the rest link to the Lean source.

Setups (2)

Setup S-1 — design-based finite-population potential-outcome system on n=2m units: the only randomness is a sign assignment law P (a PMF on the finite space {-1,1}^n); potential outcomes Y_i(z) and the GATE estimand tau are fixed finite-population objects — FiniteDesign Ω is exactly a PMF (p, p_nonneg, p_sum) over a finite assignment space with finite-sum E/Var/Cov; instantiate Ω := (Fin n -> Sign) i.e. {-1,1}^n so P : FiniteDesign Ω. Sign-symmetry / block-exchangeability (P_m^bal, P_m^sym) are predicates ON such a design (built by BalancedDesignClass / blockExchangeableDesignClass nodes). Y_i(z):(Ω)->Fin n->R and tau=n^{-1} sum (Y_i(1_n)-Y_i(-1_n)) are plain ambient functions (no dedicated Causalean PO structure; lean_local_search PotentialOutcome -> none, only Panel.Exposure exists) and are motivational: no proved statement references them, so they are trivial Mathlib functions carried in this world.
Setup S-2 — real n x n symmetric-matrix / Euclidean objective-geometry world (Mathlib): traces, PSD cone, Frobenius (Schatten-2) norm, the balanced two-block spectral decomposition, and the two-parameter block-symmetric slice X(u,v) with its reduced triangle T_m — Built over Mathlib matrices: Matrix.trace, Matrix.PosSemidef, the Frobenius norm, EuclideanSpace/inner products and the spectral theorem for symmetric matrices supply every primitive. L_m^dagger (Moore-Penrose pseudoinverse) is only ever consumed through its eigenvalues (1/(a+b),1/(2b),0) via lem:block-spectral-coordinates, so it is realized by its spectral action, not a general pseudoinverse theory. bypass-justified: the Causalean analogue for the ambient probability layer (FiniteDesign, S1) is at the design-law abstraction, whereas E_m^blk/F/Delta are purely algebraic over R^{n x n}; lean_local_search {elliptope, assignmentCovariance, Laplacian, Frobenius} returned none, so this world is a Mathlib-matrix bypass. The derived scalar frontiers (kappa_cut, r_cut, kappa_iid, r_gap^{+-}, r_star) are R-valued closed forms living in this world; r_star has no statement node (honest open scope) and is bound here only as a symbol.

Definitions (8)

Definition P-1 verified CausalSmith.Experimentation.DesignPm1.twoBlockGraph Vertex set A_m union B_m with |A_m|=|B_m|=m; for i != j in the same block set W_ij = a/m, for i and j in opposite blocks set W_ij = b/m, and set W_ii = 0.
Definition P-2 verified CausalSmith.Experimentation.DesignPm1.BlockElliptopeMem { X(u,v) : 1-u >= 0, 1 + (m-1)u - m v >= 0, 1 + (m-1)u + m v >= 0 }
Definition P-3 verified CausalSmith.Experimentation.DesignPm1.BalancedDesignClass { P on {-1,1}^n : P(Z=z)=P(Z=-z) for every z }
Definition P-4 verified CausalSmith.Experimentation.DesignPm1.blockExchangeableDesignClass { P in P_m^bal : P is invariant under permutations within A_m, within B_m, and under swapping the two equal communities }
Definition P-5 verified CausalSmith.Experimentation.DesignPm1.implementableCovarianceClass { X(P) : P in P_m^sym }
Definition P-6 verified CausalSmith.Experimentation.DesignPm1.designObjective Tr(L_m X) + r Tr(L_m^dagger X) + kappa ||X||_{S_2} + Tr(J_n X)
Definition P-7 verified CausalSmith.Experimentation.DesignPm1.implementabilityGap inf_{P in P_m^sym} F_{r,kappa}(X(P)) - inf_{X in E_m^blk} F_{r,kappa}(X)
Definition P-8 verified CausalSmith.Experimentation.DesignPm1.blockSumHandle Law of (sum_{i in A_m} Z_i, sum_{i in B_m} Z_i) under P.

Assumptions (4)

Assumption A-1 verified CausalSmith.Experimentation.DesignPm1.TwoBlockHomophily m >= 2 and a > b > 0.
Assumption A-2 verified CausalSmith.Experimentation.DesignPm1.BalancedSignDesign P(Z = z) = P(Z = -z) for all z in {-1,1}^n.
Assumption A-3 verified CausalSmith.Experimentation.DesignPm1.LowScaleTwoBlock a+3b<2m.
Assumption A-4 verified CausalSmith.Experimentation.DesignPm1.OddCommunitySize m is odd.

Lemmas (9)

Lemma L-1 verified CausalSmith.Experimentation.DesignPm1.symmetry_reduction Assume ass:two-block-homophily, with r in [0,infty) and kappa in [0,infty) by their definitional domains. Orbit-averaging over the full two-block automorphism group generated by permutations within A_m, permutations within B_m, and the swap of the two equal communities maps each elliptope point X with diag(X)=1 to a point in E_m^blk with weakly smaller F_{r,kappa}. The same averaging maps each law P in P_m^bal to a block-exchangeable law with the same zero one-point margins and weakly smaller F_{r,kappa}(X(P)). Consequently inf_{X : X is positive semidefinite and diag(X)=1} F_{r,kappa}(X) = inf_{X in E_m^blk} F_{r,kappa}(X) and inf_{P in P_m^bal} F_{r,kappa}(X(P)) = inf_{P in P_m^sym} F_{r,kappa}(X(P)).
Lemma L-2 verified CausalSmith.Experimentation.DesignPm1.block_spectral_coordinates Let q=2(m-1). For X(u,v), define x=1-u, y=1+(m-1)u-mv, and z=1+(m-1)u+mv. Then X(u,v) belongs to E_m^blk if and only if x,y,z>=0 and qx+y+z=2m. In these coordinates X_cut=(0,2m,0), I_n=(1,1,1), and F_{r,kappa}(X(u,v))=c_x x+c_y y+c_z z+kappa sqrt(qx^2+y^2+z^2), where c_x=q((a+b)+r/(a+b)), c_y=2b+r/(2b), and c_z=2m.
Lemma L-3 verified CausalSmith.Experimentation.DesignPm1.cut_vertex_certificate On T_m={x,y,z>=0: qx+y+z=2m}, if c_x/q>c_y+kappa and c_z>c_y+kappa, then (0,2m,0) is the unique minimizer of c_x x+c_y y+c_z z+kappa sqrt(qx^2+y^2+z^2).
Lemma L-4 verified CausalSmith.Experimentation.DesignPm1.spread_vertex_certificate On T_m={x,y,z>=0: qx+y+z=2m}, if c_y>c_x/q+kappa/sqrt(q) and c_z>c_x/q+kappa/sqrt(q), then (2m/q,0,0) is the unique minimizer of c_x x+c_y y+c_z z+kappa sqrt(qx^2+y^2+z^2).
Lemma L-5 verified CausalSmith.Experimentation.DesignPm1.frobenius_center_certificate On T_m, the point (1,1,1) is the unique minimizer of sqrt(qx^2+y^2+z^2). It is a minimizer of c_x x+c_y y+c_z z+kappa sqrt(qx^2+y^2+z^2) for finite kappa only if c_x/q=c_y=c_z; under this equality and kappa>0 it is the unique minimizer.
Lemma L-6 verified CausalSmith.Experimentation.DesignPm1.pm_reduced_slice_characterization After full two-block symmetrization, the plus-minus-one covariance image in spectral coordinates is T_m when m is even and is T_m intersect {y+z>=2/m} when m is odd. In particular, for odd m the spread vertex (m/(m-1),0,0) is not implementable, while for even m every point of E_m^blk is implementable.
Lemma L-7 verified CausalSmith.Experimentation.DesignPm1.weighted_simplex_active_set Let I={x,y,z}, M=2m, beta_x=1/q, beta_y=beta_z=1, and alpha=(alpha_x,alpha_y,alpha_z). On Delta_M={t_i>=0: sum_i t_i=M}, minimize Phi(t)=sum_i alpha_i t_i+kappa sqrt(sum_i beta_i t_i^2). If kappa>0, the minimizer is unique and is obtained by the following active-set formula. For each nonempty S subset I set A_S=sum_{i in S} beta_i^{-1}, mu_S=A_S^{-1} sum_{i in S} alpha_i beta_i^{-1}, and V_S=sum_{i in S}(alpha_i-mu_S)^2 beta_i^{-1}. If lambda_S=mu_S+sqrt((kappa^2-V_S)/A_S) is real, lambda_S>max_{i in S} alpha_i, and alpha_j>=lambda_S for every j notin S, then t_i=M((lambda_S-alpha_i)/beta_i)/sum_{h in S}((lambda_S-alpha_h)/beta_h) for i in S and t_j=0 for j notin S. Exactly one S satisfies these conditions, and the displayed point is the unique minimizer with value M lambda_S. Singleton S gives a vertex, two-point S gives an edge minimizer, and S=I gives the interior minimizer. If kappa=0, the minimizer set is the exposed face conv{M e_i: alpha_i=min_j alpha_j}; a closed-form selector may be chosen from that face without changing the value.
Lemma L-8 verified CausalSmith.Experimentation.DesignPm1.weighted_simplex_truncation In the notation of lem:weighted-simplex-active-set, let K_d={t in Delta_M: t_y+t_z>=d} with 0<=d<=M. Use the kappa=0 tie convention that the relaxed selector is chosen in K_d when the relaxed argmin face meets K_d. If the selected relaxed minimizer t_rel belongs to K_d, it is also a minimizer over K_d. If t_rel is not in K_d, then every constrained optimum may be chosen on the segment H_d={t_x=M-d, t_y=s, t_z=d-s, 0<=s<=d}. On H_d the objective is g_d(s)=alpha_x(M-d)+alpha_z d+(alpha_y-alpha_z)s+kappa sqrt((M-d)^2/q+s^2+(d-s)^2). For kappa>0, writing A_d=(M-d)^2/q and delta=alpha_y-alpha_z, the minimizer is s=0 if delta>=kappa d/sqrt(A_d+d^2), s=d if delta<=-kappa d/sqrt(A_d+d^2), and otherwise s=(d-delta sqrt((A_d+d^2/2)/(kappa^2-delta^2/2)))/2. For kappa=0, any endpoint minimizing the linear function is selected: s=0 if delta>=0 and s=d if delta<=0.
Lemma L-9 verified CausalSmith.Experimentation.DesignPm1.rounding_gap_reduction Let q=2(m-1), T_m={x,y,z>=0: qx+y+z=2m}, phi_{r,kappa}(x,y,z)=c_x x+c_y y+c_z z+kappa sqrt(qx^2+y^2+z^2), and d_m=0 if m is even and d_m=2/m if m is odd. Then Delta_m^pm(r,kappa)=min_{(x,y,z) in T_m, y+z>=d_m} phi_{r,kappa}(x,y,z)-min_{(x,y,z) in T_m} phi_{r,kappa}(x,y,z).

Theorems (4)

Theorem T-1 verified CausalSmith.Experimentation.DesignPm1.cut_corner_exactness Assume ass:two-block-homophily. Set r_cut(m,a,b,kappa)=min{2b(a+b)(1-kappa/(a-b)), 2b(2m-2b-kappa)}. If 0<=r<r_cut(m,a,b,kappa), then X_cut is the unique minimizer of F_{r,kappa} over E_m^blk. Hence Delta_m^pm(r,kappa)=0, X_cut is the unique minimizer over C_m^pm, and P_cut attains that implementable optimum. (The range 0<=r<r_cut(m,a,b,kappa) is nonempty exactly when 0<=kappa<min{a-b,2(m-b)}, which in particular requires b<m; this is a non-vacuity remark, not a hypothesis.) At the boundary r=r_cut uniqueness can fail already when kappa=0, so the theorem uses the strict inequality r<r_cut.
Theorem T-2 verified CausalSmith.Experimentation.DesignPm1.robust_corner_exactness Assume ass:two-block-homophily. Finite-kappa iid exactness holds only on the affine-balanced locus. More precisely, I_n is a minimizer of F_{r,kappa} over E_m^blk for some finite kappa if and only if a+3b=2m and r=2b(a+b), equivalently r=4b(m-b). On this locus, for every kappa>0, I_n is the unique relaxed minimizer and the implementable optimum is attained by P_iid, with P_iid in P_m^sym by def:block-exchangeable-design-class and X(P_iid)=I_n. Off this locus, I_n is not a minimizer for any finite kappa, although minimizers converge to I_n as kappa tends to infinity.
Theorem T-3 verified CausalSmith.Experimentation.DesignPm1.gap_window Assume ass:two-block-homophily, ass:low-scale-two-block, and ass:odd-community-size. With q=2(m-1), define kappa_gap(m,a,b):=((2m-a-3b)(a-b)sqrt(q))/(a+b) and r_cut_gap(m,a,b,kappa):=2b(a+b)(1-kappa/(a-b)). Define R_x^-(m,a,b,kappa)=2b(a+b)(1+kappa/((a-b)sqrt(q))) and R_x^+(m,a,b,kappa)=(a+b)(2m-a-b-kappa/sqrt(q)). Define r_gap^-(m,a,b,kappa)=(R_x^-(m,a,b,kappa)+R_x^+(m,a,b,kappa))/2 and r_gap^+(m,a,b,kappa)=R_x^+(m,a,b,kappa). Then for every 0 <= kappa < kappa_gap(m,a,b), r_cut_gap(m,a,b,kappa) < r_gap^-(m,a,b,kappa) < r_gap^+(m,a,b,kappa), and for every r in (r_gap^-,r_gap^+) the spread vertex X_spread in E_m^blk with spectral coordinates (m/(m-1),0,0) is the unique relaxed minimizer but is not plus-minus-one implementable. Consequently Delta_m^pm(r,kappa)>0 throughout that interval. The oddness restriction is necessary: if m is even, the whole block elliptope slice is implementable and the claimed positive gap is false.
Theorem T-4 verified CausalSmith.Experimentation.DesignPm1.sharp_rho_star Under ass:two-block-homophily, with r,kappa in [0,infty), the theorem asserts EXACTLY the following conjunction (mirroring the Lean statement): (i) rho_star(m,a,b,r,kappa) = Delta_m^pm(r,kappa); (ii) 0 <= rho_star and 0 <= Delta_m^pm (definitional domain [0,infty)); (iii) rho_star=0 iff there is a relaxed minimizer over T_m (a point of T_m minimizing the reduced objective) with y+z >= d_m; (iv) for kappa>0 the relaxed minimizer over T_m is UNIQUE, and rho_star=0 iff that unique minimizer satisfies y+z >= d_m; (v) for kappa=0 a point of T_m is a relaxed minimizer iff it lies on the exposed face of the alpha=(c_x/q,c_y,c_z)-minimizing coordinates; (vi) for even m (d_m=0) rho_star=0 throughout; (vii) ACTIVE-SET COMPUTATION (lem:weighted-simplex-active-set): for kappa>0 the unique relaxed minimizer is the active-set point of an admissible support/multiplier (S,lambda) under the change of variables t=(qx,y,z) (alpha=sharpAlpha, beta=sharpBeta), and the relaxed value equals 2m*lambda; (viii) TRUNCATION CORRECTION (lem:weighted-simplex-truncation): when the relaxed argmin set is disjoint from {y+z >= d_m}, the implementable value is attained on the truncation segment {y+z=d_m} at the endpoint/interior selector truncSelector. No r_star frontier/boundary is asserted (honest open scope).

Auxiliary Lean lemmas (machine-checked) (38)

Definition CausalSmith.Experimentation.DesignPm1.IsSharpExactnessBoundary verified
Assumption CausalSmith.Experimentation.DesignPm1.cut_vertex_certificate verified
Assumption CausalSmith.Experimentation.DesignPm1.spread_vertex_certificate verified
Lemma CausalSmith.Experimentation.DesignPm1.spreadObjectiveDiff_mul_sqrt —
Lemma CausalSmith.Experimentation.DesignPm1.frobeniusCenterTangentXY_deriv —
Lemma CausalSmith.Experimentation.DesignPm1.frobeniusCenterTangentYZ_deriv —
Definition CausalSmith.Experimentation.DesignPm1.IsIidExactnessFrontier verified
Lemma CausalSmith.Experimentation.DesignPm1.cutDesign_eq_cutVDesign —
Lemma CausalSmith.Experimentation.DesignPm1.sInf_image_eq_of_minimizer —
Lemma CausalSmith.Experimentation.DesignPm1.sum_if_eq_else_self_real —
Lemma CausalSmith.Experimentation.DesignPm1.block_pair_sum —
Lemma CausalSmith.Experimentation.DesignPm1.block_signed_pair_sum —
Lemma CausalSmith.Experimentation.DesignPm1.blockSymMatrix_mem_blockElliptope_iff_reducedTriangle —
Lemma CausalSmith.Experimentation.DesignPm1.roundingLossCertificate_nonneg —
Lemma CausalSmith.Experimentation.DesignPm1.implementabilityGap_nonneg —
Lemma CausalSmith.Experimentation.DesignPm1.reducedTriangle_to_simplex —
Lemma CausalSmith.Experimentation.DesignPm1.simplex_to_reducedTriangle —
Lemma CausalSmith.Experimentation.DesignPm1.reducedObjective_eq_wsObj —
Lemma CausalSmith.Experimentation.DesignPm1.wsObj_eq_reducedObjective —
Lemma CausalSmith.Experimentation.DesignPm1.spread_certificate_relaxed_minimizer_and_gap —
Lemma CausalSmith.Experimentation.DesignPm1.sharp_reduced_active_set_and_unique —
Lemma CausalSmith.Experimentation.DesignPm1.sharp_truncation_value_of_no_reduced_argmin_in_slice —
Lemma CausalSmith.Experimentation.DesignPm1.sharp_roundingLoss_zero_of_even —
Lemma CausalSmith.Experimentation.DesignPm1.sharp_roundingLoss_zero_iff_argmin_meets_slice —
Lemma CausalSmith.Experimentation.DesignPm1.sharp_roundingLoss_zero_iff_unique_argmin_subset_slice —
Lemma CausalSmith.Experimentation.DesignPm1.sharp_kappa_zero_reduced_min_iff —
Lemma CausalSmith.Experimentation.DesignPm1.reduced_norm_sq_block_coords —
Lemma CausalSmith.Experimentation.DesignPm1.robust_minimizers_tendsto_identity_entries —
Lemma CausalSmith.Experimentation.DesignPm1.iidDesign_sign_pair_sum_zero —
Lemma CausalSmith.Experimentation.DesignPm1.iidDesign_secondMoment —
Lemma CausalSmith.Experimentation.DesignPm1.identity_mem_blockElliptope —
Lemma CausalSmith.Experimentation.DesignPm1.robust_coeff_r_eq_of_center —
Lemma CausalSmith.Experimentation.DesignPm1.robust_locus_of_center_coeffs —
Lemma CausalSmith.Experimentation.DesignPm1.robust_center_coeffs_of_locus —
Lemma CausalSmith.Experimentation.DesignPm1.reduced_coord_inverse —
Lemma CausalSmith.Experimentation.DesignPm1.identity_objective_eq_reduced_center —
Lemma CausalSmith.Experimentation.DesignPm1.center_coeffs_of_identity_relaxed_min —
Lemma CausalSmith.Experimentation.DesignPm1.identity_strict_relaxed_min_of_locus —

Symbol realizations (Lean @realizes) (52)

X(u,v) verified realized by InReducedTriangle, blockSymMatrix
F_{r,kappa}(X) verified realized by reducedObjective, cX, cY, cZ, frobeniusNorm, designObjective
kappa(carrier ℝ; robustness weight on the Frobenius term κ√(q x²+y²+z²); range verified realized by reducedObjective
r verified realized by cX, cY, designObjective
a verified realized by cX, twoBlockGraph, TwoBlockHomophily
b verified realized by cX, cY, twoBlockGraph, TwoBlockHomophily
J_n verified realized by allOnesMatrix
s_m verified realized by signVec
G_m(a,b) verified realized by twoBlockGraph
A_m verified realized by twoBlockGraph, blockSumA, blockSumB
B_m verified realized by twoBlockGraph, blockSumA, blockSumB
L_m verified realized by twoBlockLaplacian
L_m^dagger verified realized by twoBlockLaplacianPinv
X_cut verified realized by cutCovariance
kappa(carrier ℝ; robustness weight on the Schatten-2 penalty `κ‖X‖_{S_2}`; range verified realized by designObjective
E_m^blk verified realized by blockElliptope
P(AUTHORITATIVE CARRIER: `FiniteDesign (Fin (2*m) → Bool)`; the space verified realized by blockElliptope
P` tags pinning the same law argument.) verified realized by blockElliptope
Z verified realized by signOf
X(P) verified realized by assignmentSecondMoment
P(design-law argument `D : FiniteDesign (Fin (2*m) → Bool)`, the law over which verified realized by assignmentSecondMoment
P_cut verified realized by cutDesign
P(cluster member — CONCRETE CARRIER+CONSTRAINTS instance: a `FiniteDesign verified realized by cutDesign, iidDesign
P verified realized by cutDesign, iidDesign
P_iid verified realized by iidDesign
P(design-law argument `D : FiniteDesign (Fin (2*m) → Bool)`, the probability verified realized by BalancedSignDesign
P_m^bal verified realized by BalancedDesignClass
P(cluster member: the bundled law `D : FiniteDesign (Fin (2*m) → Bool)`, a verified realized by BalancedDesignClass
P_m^sym verified realized by blockExchangeableDesignClass
P(cluster member: this `Set (FiniteDesign (Fin (2*m) → Bool))` is the class of verified realized by blockExchangeableDesignClass
C_m^pm verified realized by implementableCovarianceClass
P(cluster member: the bound design law `D ∈ blockExchangeableDesignClass m` verified realized by implementableCovarianceClass
B(P) verified realized by blockSumHandle
Delta_m^pm(r,kappa) verified realized by implementabilityGap, implementabilityGap_nonneg, sharp_rho_star
P(cluster member — AUTHORITATIVE link into the `sharp_rho_star` target block: verified realized by implementabilityGap
kappa(carrier ℝ; robustness argument of the gap; range [0,∞) pinned by the verified realized by implementabilityGap
rho_star(m,a,b,r,kappa) verified realized by roundingLossCertificate, roundingLossCertificate_nonneg, sharp_rho_star
r_star(m,a,b,kappa) verified realized by IsSharpExactnessBoundary
r_star(range 0 ≤ r_⋆ pins the boundary object into its [0,∞) space) verified realized by IsSharpExactnessBoundary
r_star verified realized by IsSharpExactnessBoundary
kappa_iid(m,a,b,r) verified realized by IsIidExactnessFrontier, robust_corner_exactness
kappa_iid(range 0 ≤ κ_iid pins the frontier into its [0,∞) space) verified realized by IsIidExactnessFrontier
kappa_iid verified realized by IsIidExactnessFrontier
r_cut(m,a,b,kappa) verified realized by rCut, cut_corner_exactness, rCutGap, gap_window
kappa(carrier ℝ argument `kappa`; robustness weight entering both branches of the verified realized by rCut
kappa_cut(m,a,b) verified realized by kappaCut
r(range 0 ≤ r pins r ∈ [0,∞)) verified realized by cut_corner_exactness, robust_corner_exactness, sharp_rho_star
kappa(range 0 ≤ κ pins κ ∈ [0,∞), its definitional domain) verified realized by cut_corner_exactness, sharp_rho_star
r_gap^-(m,a,b,kappa) verified realized by rGapMinus, rGapPlus, rGapFrontiers_nonneg
r_gap^+(m,a,b,kappa) verified realized by rGapMinus, rGapPlus, rGapFrontiers_nonneg
r(bound within the gap window rGapMinus < r < rGapPlus ⊂ [0,∞)) verified realized by gap_window
P`-tagged). verified realized by sharp_rho_star

Proof map 11 statements · 12 edges

Exact Randomized Designs for Two-Block Interference Experiments

Abstract

Introduction

Setup and assumptions

Exactness at implementable designs

Positive loss and sharp computation

A worked example and parameter map.

Discussion and extensions

Relation to covariance-based network design.

Limitations and future work

Appendices

Reduced geometry and proof ingredients

Verification note

Proofs of the main results

References