Dimension Dependent Correlation Gap Bounds under Restricted Independence

Dimension Dependent Correlation Gap Bounds under Restricted Independence Arjun Ramachandra∗

arXiv:2609.02659v1 [math.PR] 2 Sep 2026

June 2026

Abstract The pairwise independent correlation gap is defined as the ratio of the maximum expected value of a set function under arbitrary dependence to the maximum expected value when the underlying random elements are restricted to be pairwise independent, and hence measures the loss in expected value under this independence restriction. Under the more restrictive assumption of mutual independence, [4] proved that this gap is universally bounded by e/(e − 1) for the class of monotone submodular set functions. With pairwise independence, a tighter upper bound of 4/3 was established in [2] for several special cases, including n = 3, and conjectured to hold universally across all dimensions and marginal probabilities for the class of monotone submodular functions. However, a recent AI-assisted counterexample in [3] disproved this conjecture by showing that the 4/3 bound fails for n = 5, leaving the validity of the bound for n = 4 and the tight worst case bound for pairwise independence open. We resolve both questions in this paper. First, for n = 4, we establish that the 4/3 bound holds universally and is tight using an AI-assisted proof combining theoretical analysis and computational verification. The proof combines a structural characterization of optimal numerator vertices, permutation symmetry, cone certificate systems, Bernstein polynomial representations, recursive simplex subdivision, and a computational verification of 2, 745 Bernstein coefficient systems. Second, we show that the worst case pairwise independent correlation gap attains e/(e − 1) asymptotically by constructing an instance with identical marginal probabilities and defining a monotone submodular union coverage function on a ground set partitioned into m blocks. The key condition is that the number of blocks grows sublinearly with the ground set size, so that both the number of blocks and the size of each block tend to infinity. The result follows by constructing a feasible solution to a scaled asymptotic reduced dual of the pairwise independent linear program with identical marginals. The asymptotic result immediately extends to t-wise independent (t ≥ 2) random elements, since t-wise independence implies pairwise independence. The key insight of this paper is that the pairwise independent correlation gap exhibits a dimension dependent worst case bound, with n = 4 being the largest dimension for which the 4/3 bound holds, while the worst case gap fails to improve upon the classical e/(e − 1) bound, attaining it asymptotically. Thus, pairwise independence, despite being the least restrictive form of independence in the t-wise independence hierarchy can be as restrictive as mutual independence in the worst case.

Keywords: Correlation gap; pairwise independence; monotone submodular functions; coverage functions; concave closure; Bernstein polynomials; linear programming.

1

Introduction

Let N = {1, 2, . . . , n} denote a ground set with n elements and f : 2N → R+ be a nonnegative monotone submodular set function defined on the power set 2N . A function is monotone (non-decreasing) if f (S) ≤ f (T ) for all S ⊆ T and submodular if f (S) + f (T ) ≥ f (S ∩ T ) + f (S ∪ T ) for all S, T ⊆ N or equivalently f (S ∪ {i}) − f (S) ≥ f (T ∪ {i}) − f (T ) for all S ⊆ T , i ∈ N \T. For a given marginal probability vector x = (x1 , . . . , xn ) and a monotone submodular function f , the correlation gap compares the maximum expected ∗

Decision Sciences Area, Indian Institute of Management Bangalore, India. Email: arjun.ramachandra@iimb.ac.in

1

value under arbitrary dependence with the expected value obtained under independence by computing their ratio. The numerator in this ratio is referred to as the concave closure f + : [0, 1]n → R+ and can be viewed as a continous extension of the set function f , defined as the maximum expected value of the function over all joint distributions u in which each element i ∈ N is selected with probability xi , i.e., X f + (x) = max Eu [f ] = uS f (S) u S⊆N

X

s.t.

uS = 1, (1)

S⊆N

X

∀i ∈ N,

uS = xi ,

S∋i

uS ≥ 0,

∀S ⊆ N.

where uS denotes the probability mass assigned to the subset S ⊆ N . Here, the symbol u is used to denote the univariate information specified by the marginal probabilities, with no restrictions imposed on higher order dependence. The P denominatorQ in the correlation gap
ratio is referred to as the multilinear Q extension defined as F (x) = S⊆N f (S) i∈S xi i∈S / (1 − xi ) which is the expected function value assuming the random elements to be mutually independent. The correlation gap f + (x)/F (x) can be interpreted as the loss of optimality incurred by ignoring the higher order dependence (correlations) and imposing independence instead and was shown in [4] to be universally bounded by e/(e − 1) for the class of monotone submodular functions. It has found widespread applications in stochastic optimization including facility location, Steiner tree problems, and social welfare maximization with combinatorial auctions [4], mechanism design [7], distributionally robust bottleneck optimization [2], prophet inequalities [8], matroid theory [9] and several submodular optimization problems [10]. Given the restrictive nature of the mutual independence assumption and motivated by whether relaxing mutual independence to weaker notions of independence can further reduce this gap, [1] introduced the pairwise independent extension of the set function f given by f ++ : [0, 1]n → R+ . In addition to the marginal probability information, this extension assumes that the random elements are pairwise independent and can be expressed as: X f ++ (x) = max Ep [f ] = ps f (S) p S⊆N

s.t.

X

ps = 1,

S⊆N

X

∀i ∈ N,

ps = xi ,

(2)

S∋i

X

ps = xi xj ,

∀i < j, i ∈ N, j ∈ N

S⊇{i,j}

ps ≥ 0,

∀S ⊆ N.

where pS denotes the probability mass assigned to the subset S ⊆ N with the symbol p used to denote the pairwise information specified by the marginal and pairwise probabilities. Pairwise independence is a restrictive notion of independence in the sense that it imposes only pairwise constraints while allowing arbitrary higher order dependencies. The sparse support of these distributions also has proved to be useful in efficient derandomization of algorithms for NP-hard optimization problems [11]. The pairwise independent correlation gap, defined in the same paper of [1] as the ratio f + (x)/f ++ (x), was expected to admit a sharper upper bound than the e/(e − 1) bound on f + (x)/F (x). This is because the pairwise independent extension in (2) includes the mutually independent distribution as a feasible solution, which implies that f + (x)/f ++ (x) ≤ f + (x)/F (x) ≤ e/(e − 1). 2

Unfortunately, computing both f + (x) and f ++ (x) is NP-hard in the worst case for monotone submodular functions (see [4]). In particular, unlike F (x), which is evaluated for the mutually independent distribution irrespective of the function f , the optimal probability distributions that attain the f + (x) and f ++ (x) are not oblivious to the function f wich makes the analysis challenging even for small dimensions such as n = 3 (see [2]). Despite this challenge, a reduced upper bound of 4/3 on f + (x)/f ++ (x) has been proven in special cases. For the specific submodular function f (S) = min(|S|, 1), with arbitrary dimension n and any marginal probabilities x ∈ [0, 1]n , [1] proved that the 4/3 upper bound was tight. The analysis was further extended in [2], showing that the 4/3 bound holds for all monotone submodular functions in two cases: (a) n = 3 with unrestricted marginal probabilities, and (b) general n with restricted marginal probabilities. However, unlike the e/(e − 1) bound, the universal validity of the 4/3 bound for arbitrary monotone submodular functions, dimensions n, and marginal probabilities x remained an open question, leading [2] to conjecture that the 4/3 bound holds universally.

2

Recent Developments and Our Contributions

More recently, the universal 4/3 conjecture was disproved in [3], by constructing an AI-assisted counterexample for n = 5 Bernoulli random elements that attains a pairwise independent correlation gap of 640 4 ≈ 1.336 > 479 3 with a monotone submodular coverage function. The n = 5 counterexample can be extended to every dimension n > 5 by padding it with Bernoulli variables having marginal probability zero. Such variables are identically zero and hence neither appear in the support of the optimal joint distribution nor affect the marginal constraints or the optimal objective. This means that the worst case ratio lies in the interval [640/479, e/(e − 1)] for n ≥ 5. Consequently, as claimed in [3], n = 4 is the only dimension for which the validity of the 4/3 bound remained unresolved. On the other hand, the counterexample for n ≥ 5 raises a broader question: if the 4/3 bound fails for n ≥ 5, what then is a universal upper bound on the pairwise independent correlation gap across dimensions n ? Can it beat the e/(e − 1) bound in the worst case? We resolve both questions in this paper, the first in the affirmative and the second in the negative, by establishing that: 1. The 4/3 upper bound survives for n = 4 using an AI-assisted proof combining theoretical analysis and computational verification, and is tight. 2. The worst case pairwise independent correlation gap attains e/(e − 1) asymptotically as n → ∞, the same worst case bound established in [4] under mutual independence. As an immediate consequence, since every t-wise independent distribution (t ≥ 2) is necessarily pairwise independent, our result implies that the worst case t-wise independent correlation gap is also exactly e/(e − 1). These two results are fundamentally different in nature: The first result for n = 4, involves providing a universal certification showing that the 4/3 bound holds for every monotone submodular function and every marginal probability vector x ∈ [0, 1]4 . The second result, on the other hand, provides an asymptotic worst case construction showing that e/(e−1) is asymptotically attained as n → ∞, implying that pairwise independence, despite being the least restrictive form of independence in the t-wise independence hierarchy, can be as restrictive as mutual independence in the worst case. Together, these results add to the literature on the characterization of the worst case pairwise independent correlation gap across dimensions for the class of monotone submodular functions. Table 1 summarizes the progression of results on the worst case pairwise independent correlation gap and presents the current state of knowledge across dimensions n. The rest of the paper is organized as follows: Section 3 establishes the tightness of the 4/3 bound for n = 4 random elements while Section 4 3

Table 1: Tight worst case pairwise independent correlation gap for monotone submodular functions Dimension

Tight worst case bound

Reference

n = 2, 3

4 3

[2]

n=4

4 3

This paper

 n≥5

640 e , 479 e − 1

n→∞

e e−1

 [3] This paper

establishes the asymptotic attainment of the e/(e − 1) bound as n → ∞ and Section 5 summarizes the key contributions of this work with possible future directions. Proofs are relegated to the appendix whenever possible and are retained in the main body only when they are essential for understanding subsequent results.

3

A 4/3 bound for n = 4 random elements

For n = 4 random elements, denote the ground set as N4 = {1, 2, 3, 4}. Theorem 1 (Worst case pairwise independent correlation gap for n = 4). For every nonnegative monotone submodular function f : 2N4 → R+ and every x ∈ [0, 1]4 , f + (x) 4 ≤ f ++ (x) 3 and the bound is tight. Proof. A brief overview of the proof is outlined in the seven steps below: (i) We first recall a standard result from LP theory in Lemma 1, which states that an optimal numerator vertex in 4 dimensions is supported on at most five subsets. Further, if an optimal vertex is degenerate with smaller support, Corollary 1 shows that it can be extended to a nonsingular five-subset basis. (ii) For a chosen optimal numerator vertex corresponding to one of the 3008 nonsingular five-subset bases, Corollary 2 shows that the marginal vector x lies in the incidence simplex corresponding to the five incidence vectors of this basis. The set of all incidence simplices corresponding to these bases form an overlapping cover of the entire marginal probability space [0, 1]4 . (iii) Lemma 2 provides a sufficient cone certificate condition for the 4/3 bound to hold for every function in the cone of nonnegative monotone submodular functions and every x ∈ [0, 1]4 . The key idea is to consider primal, rather than dual, certificates for the numerator, allowing both the numerator and denominator certificates to be formulated in the same primal space and thereby incorporated into a common cone certificate system. Since the optimal numerator vertex can correspond to any one of the 3008 nonsingular five-subset bases, a certificate of feasibility must be provided for each one of them with marginal probabilities restricted to lie in the corresponding incidence simplex. (iv) To overcome the challenge of generating certificates over the continuum of marginal vectors for each such basis, we use a degree-two Bernstein basis to express the probability distributions and other relevant parameters as quadratic functions of the convex coefficients, yielding 15 coefficient blocks 4

corresponding to the pairs 0 ≤ a ≤ b ≤ 4. For each such coefficient block and a chosen nonsingular five-subset basis, Corollary 4 shows that it is sufficient to check for feasibility of a Bernstein coefficient system defined in Lemma 4 to ensure a feasible cone certificate. (v) Further, we exploit permutation symmetry to show that the 3, 008 nonsingular five-subset bases can be reduced to 183 orbits, where bases in the same orbit are equivalent up to a permutation of the four elements. Lemma 5 shows that it suffices to solve each of the the 15 Bernstein coefficient systems for one representative from each orbit. (vi) To handle representative orbit simplices on which the Bernstein coefficient system is infeasible, we provide an Algorithm 1 that recursively subdivides each such simplex along its longest edge until all terminal leaf simplices admit feasible certificates, thereby providing a certified cover of the entire simplex. (vii) Finally, we implemented Algorithm 1 in code and used linear programming to computationally verify the feasibility of all 15 × 183 = 2, 745 Bernstein coefficient systems corresponding to the 15 coefficient blocks and 183 permutation orbit representatives. All systems were found to be feasible, yielding a total of 4, 476 successful leaf simplices and thereby establishing the 4/3 bound for n = 4 as claimed.

Declaration of AI-assisted research methodology for the n = 4 proof: The n = 4 proof strategy was initially explored through a human-AI workflow involving GPT 5.6 and Fable 5, including the cone certificate formulation and the use of a Bernstein representation to avoid checking certificates separately at every marginal probability vector. The author subsequently verified, corrected, and refined the resulting strategy, in particular by requiring the numerator distribution in the cone certificate to correspond to an optimal primal vertex, and developed the resulting systematic treatment of the possible optimal vertices. The subsequent proof development incorporated permutation symmetry and recursive simplex subdivision along with independent verification of computational results. Remark 1 (Negative dependence is fragile in high dimensions). The structure of submodularity tends to encourage negative dependence, and our n = 4 result resonates with the broader observation in the literature that negative dependence is delicate and need not persist beyond low dimensional regimes. In matroid theory, for example, [12] showed that every rank-3 matroid has the Rayleigh property, which corresponds to pairwise negative correlation, whereas rank-4 matroids need not have this property. [13] provided an example to illustrate a positively correlated pair in a rank-4 transversal matroid. Remark 2 (Advantages of a primal based proof technique). Unlike [2], where the 4/3 bound for n = 3 was proved analytically using the dual of the concave closure for the numerator (see Theorem 5 therein), the primal based approach in our proof of Theorem 1 works directly with 183 representative permutation orbits of the 3, 008 possible optimal primal numerator vertices. The denominator, however, is handled directly through a primal feasible pairwise independent distribution, similar to [2]. The key advantage of a primal based approach for the numerator is that it allows the numerator and denominator certificates to be formulated in the same primal space, so that a common cone certificate system can be used, as in Lemma 2. In contrast, the approach in [2] requires identifying dual feasible solutions for the numerator and primal feasible solutions for the denominator across every interaction between the partition blocks of the marginal probability space and those of the submodular function cone. Remark 3 (Tightness of 4/3 bound for n = 4). The 4/3 bound in Theorem 1 for n = 4 is attained for the submodular function f (S) = min{|S|, 1}, S ⊆ N4 , with marginal probabilities satisfying x1 + x2 + x3 = 1 1 2 , x4 = 2 . This follows directly from Proposition 2.5 in [1], which establishes the same tightness result for general n. The remainder of this section details the proof of Theorem 1 in parts, following the steps outlined above. 5

3.1

Preliminary results leading to proof of Theorem 1

For any S ⊆ N4 , let vS =

1{1∈S} , 1{2∈S} , 1{3∈S} , 1{4∈S} ⊤ ∈ {0, 1}4 ,

denote the incidence vector of S, where 1{·} denotes the indicator function. Define the matrix  1 1 ··· 1 ∈ R5×16 , A= v ∅ v {1} · · · v N4 

where the columns are indexed by the 16 subsets of N4 . Then for any fixed marginal vector x ∈ [0, 1]4 , the feasible region of the concave closure (1) can be expressed as:    1 16 FU (x) := u ∈ R+ : Au = , x Q Q which is non-empty, since the mutually independent distribution uind (S) = i∈S xi i∈S / (1 − xi ) satisfies uind ∈ FU (x). The optimal objective of the concace closure is then: f + (x) =

max f ⊤ u u∈FU (x)

where f ∈ R16 + denotes the vector representation of the non-negative monotone submodular set function f : 2N4 → R. Denote by 2N4 the power set of N4 containing 16 possible subsets. Let J = supp(u) ⊆ 2N4 denote the support of the feasible distribution u, i.e., the collection of subsets S ⊆ N4 to which u assigns positive probability. The next lemma recalls a standard result from linear programming theory characterizing the support of a vertex distribution u ∈ FU (x). Lemma 1 (Vertex characterization by support). A feasible distribution u ∈ FU (x) is a vertex if and only if the columns of A corresponding to supp(u) are linearly independent. In particular, every vertex of FU (x) is supported on at most five subsets of N4 . Proof. The proof is relegated to Appendix A.1. We call a collection of five subsets B = {S0 , S1 , S2 , S3 , S4 }, Si ⊆ N4 , a nonsingular five subset basis if the corresponding incidence vectors v 0 , v 1 , v 2 , v 3 , v 4 ∈ {0, 1}4 are affinely independent, or equivalently, the associated submatrix   1 1 1 1 1 ∈ R5×5 AB = v0 v1 v2 v3 v4 is nonsingular. We next establish that the support of a degenerate vertex can be extended to a nonsingular five subset basis. Corollary 1 (Extension of a degenerate vertex to a nonsingular five subset basis). Let u be a degenerate vertex of FU (x) with | supp(u)| < 5. Then the corresponding columns of A can be extended to a set of five linearly independent columns of A, corresponding to a nonsingular five subset basis. Proof. By Lemma 1, for any vertex u, the columns corresponding to supp(u) are linearly independent. Since rank(A) = 5, they can be extended to five linearly independent columns of A, yielding a nonsingular five subset basis. Let V = {v 0 , . . . , v 4 } be a set of affinely independent incidence vectors v 0 , . . . , v 4 ∈ {0, 1}4 . Define the corresponding incidence simplex as ∆V = conv{v 0 , . . . , v 4 }. The next result shows that the optimal numerator vertex u⋆ (x, f ) corresponding to a given marginal probability vector x and monotone submodular function vector f induces a nonsingular five subset basis B whose incidence simplex ∆V (B) contains the marginal probability vector x. 6

Corollary 2 (Marginal probability vector in the convex hull of an optimal basis). Given x ∈ [0, 1]4 and a monotone submodular function vector f , let u⋆ (x, f ) denote an optimal vertex of F U (x). Then there exists a nonsingular five subset basis B = {S0 , S1 , S2 , S3 , S4 }, Si ⊆ N4 , with Pcorresponding affinely independent incidence vectors v 0 , . . . , v 4 ∈ {0, 1}4 and convex coefficients ηi ≥ 0, 4i=0 ηi = 1, such that ⋆

u (x, f ) =

4 X

ηi eSi ,

i=0

x=

4 X

ηi v i .

i=0

where eS ∈ R16 denote the unit vector corresponding to S ⊆ N4 . In particular, x ∈ ∆V (B) = conv{v 0 , . . . , v 4 }. Proof. Since FU (x) ̸= ∅, an optimal vertex must exist for any x ∈ [0, 1]4 . By Lemma 1, the optimal vertex u⋆ (x, f ) is supported on at most five subsets. By Corollary P 1, this support can be extended to a ⋆ nonsingular five subset basis B = {S0 , . . . , S4 }. Hence u (x, f ) = 4i=0 ηi eSi for convex coefficients ηi , with ηi = 0 for any added subset in the extension. Since Au⋆ (x, f ) = (1, x)⊤ and AeSi = (1, v i )⊤ , we obtain   X   4 1 1 = , ηi x vi i=0 P and therefore x = 4i=0 ηi v i , implying that x ∈ ∆V (B). Corollary 3 (Coverage and overlap of nonsingular five-subset simplices). Let BNS denote the collection of all nonsingular five-subset bases, and let ∆V (B) denote the incidence simplex corresponding to each B ∈ BNS . Then the set of all such incidences simplices form an overlapping cover of the entire marginal probability space, i.e., [ [0, 1]4 = ∆V (B), B∈BNS

and distinct nonsingular incidence simplices can have non-empty intersections. Proof. The proof is relegated to Appendix A.2. We next turn to the denominator of the correlation gap and characterize pairwise independent distributions by appending the six pairwise moment constraints to the total probability and marginal constraints. For S ⊆ N4 , let
⊤ wS = 1{1,2}∈S , 1{1,3}∈S , 1{1,4}∈S , 1{2,3}∈S , 1{2,4}∈S , 1{3,4}∈S ∈ {0, 1}6 . denote the vector of pairwise incidences of S. For a marginal vector x = (x1 , x2 , x3 , x4 )⊤ ∈ [0, 1]4 , define the pairwise product vector y(x) = (x1 x2 , x1 x3 , x1 x4 , x2 x3 , x2 x4 , x3 x4 )⊤ ∈ R6 . and the appended matrix 

 1 1 ··· 1 AP =  v ∅ v {1} · · · v N4  ∈ R11×16 . w∅ w{1} · · · wN4 Then, for any fixed marginal vector x ∈ [0, 1]4 , the feasible region of the pairwise independent extension (2) can be expressed as:    1   P  x  . FP (x) := p ∈ R16 (3) + :A p=   y(x) which is non-empty, since the mutually independent distribution is also pairwise independent. The corresponding optimal objective is fP+ (x) = max f ⊤ p. p∈FP (x) We next characterize the cone of normalized monotone submodular functions on N4 . 7

3.2

Cone certificate equation

Let f ∈ R16 denote the vector representation of a non-negative monotone submodular set function f : 2N4 → R+ , with one component corresponding to each subset of N4 . Monotonicity requires f (S ∪ {i}) − f (S) ≥ 0, ∀i ∈ N4 , ∀S ⊆ N4 \ {i}, P which can be represented by i∈N4 |2N4 \{i} | = 4 · 23 = 32 inequalities (where 2S denotes the power set of S), since each element i ∈ N4 can be added to any subset of the remaining three elements. Submodularity requires f (S ∪ {i}) + f (S ∪ {j}) − f (S) − f (S ∪ {i, j}) ≥ 0, ∀i, j ∈ N4 , ∀S ⊆ N4 \ {i, j}, i < j, P which can similarly be represented by i,j∈N4 , i<j |2N4 \{i,j} | = 6 · 22 = 24 inequalities. Thus, any monotone submodular function can be represented by 32 + 24 = 56 inequalities, compactly written as Gf ≥ 0,

G ∈ {−1, 0, 1}56×16 ,

where each row of G is the coefficient vector of one of the monotonicity or submodularity inequalities above. The cone of monotone submodular functions normalized at the empty set is therefore  C = f ∈ R16 : Gf ≥ 0, f (∅) = 0 . We next establish a cone certificate equation that provides a sufficient condition for the desired 4/3 bound on the correlation gap. Lemma 2 (Cone certificate equation). Fix x ∈ [0, 1]4 and a normalized monotone submodular function f ∈ C. Let u⋆ (x, f ) denote an optimal vertex of FU (x). Suppose there exists a certificate (p, γ, c) with p ∈ FP (x),

γ ∈ R56 +,

c ∈ R,

satisfying 4 p − u⋆ = G⊤ γ + c e∅ . 3 where e∅ ∈ R16 denotes the unit vector corresponding to the empty set. Then

(4)

4 f + (x) ≤ f ++ (x). 3 Proof. We refer to (4) as the cone certificate equation, since G⊤ γ, with γ ≥ 0, belongs to the conic hull of the columns of G⊤ (equivalently, the rows of G). Taking the inner product of (4) with f gives 4 ⊤ ⊤ p f − u⋆ f = γ ⊤ Gf + cf (∅). 3 Since f is monotone submodular, we have Gf ≥ 0 and since γ ≥ 0, we have γ ⊤ Gf ≥ 0. Moreover, since f is normalized, f (∅) = 0. Hence 4 4 ⊤ f + (x) = u⋆ f ≤ p⊤ f ≤ f ++ (x), 3 3 where the second inequality follows from p ∈ FP (x). Remark 4. The scalar c provides an additional degree of freedom in the cone certificate equation (4), without which, the vector 43 p − u⋆ would be forced to lie in the cone generated by the columns of G⊤ . The term c e∅ relaxes the first coordinate of the 16-dimensional vector equation, while having no effect on the resulting inequality because f (∅) = 0 for every normalized submodular function. 8

Corollary 4 (Sufficiency of cone certificates for each nonsingular five-subset basis). Let BNS denote the
collection of all nonsingular five-subset bases in four dimensions. There are 16 = 4, 368 five-subset bases 5 in four dimensions, of which it can be verified that |BNS | = 3, 008 are nonsingular. Then: (i) Every possible combination of x and u⋆ (x, f ) is associated with some B ∈ BNS , with x ∈ ∆V (B) and u⋆ (x, f ) supported on the corresponding five subsets. (ii) To prove a 4/3 bound on the pairwise independent correlation gap, it suffices to establish a feasible certificate (p, γ, c) satisfying (4) for every possible combination of x and optimal numerator vertex u⋆ (x, f ), which together correspond to some B ∈ BNS . Proof. For any x ∈ [0, 1]4 and f ∈ C, let u⋆ (x, f ) denote the optimal numerator vertex. By Lemma 1, every vertex of FU (x), and hence u⋆ (x, f ), corresponds to a nonsingular five-subset basis. If u⋆ (x, f ) is degenerate, Corollary 1 allows its support to be extended to a nonsingular five-subset basis B ∈ BNS , with zero probability assigned to any added subsets. By Corollary 2, the same convex coefficients representing u⋆ (x, f ) on this basis represent x as a convex combination of the corresponding incidence vectors and hence x ∈ ∆V (B). Since the incidence simplices ∆V (B), B ∈ BNS , cover [0, 1]4 by Corollary 3, every possible combination of x and u⋆ (x, f ) is covered by some B ∈ BNS . Therefore, it suffices to establish the certificate for every such combination corresponding to a nonsingular five subset basis. Remark 5. We note that in item (ii) of Corollary 4, no separate verification over f ∈ C is necessary to prove the 4/3 bound. This follows from the inner product argument in the proof of Lemma 2, which ensures that any certificate satisfying (4) for the corresponding x and u⋆ (x, f ) automatically establishes the 4/3 bound for every normalized monotone submodular function f ∈ C. Although BNS is finite, each simplex ∆V (B) contains a continuum of marginal probability vectors and hence infinitely many possible combinations of x and u⋆ (x, f ), each of which, by Corollary 4, would need a cone certificate. We overcome this challenge by using a Bernstein basis representation, which allows the cone certificate to be verified simultaneously for every x in the simplex, avoiding verification for each x separately.

3.3

Bernstein basis functions

For any x ∈ [0, 1]4 and corresponding optimal numerator vertex u⋆ (x, f ), Corollary 2 ensures the existence of a nonsingular five-subset basis B = {S0 , . . . , S4 } with the corresponding incidence simplex ∆V (B) = conv{v 0 , . . . , v 4 } and common convex coefficients η0 , . . . , η4 such that x(η) =

4 X

ηi v i ∈ ∆V ,

u⋆ (η) =

i=0

4 X

ηi eSi ,

i=0

4 X

ηi = 1,

ηi ≥ 0.

i=0

Thus, each marginal xi is affine in η, each pairwise moment xi xj is quadratic in η, and the optimal numerator distribution u⋆ is affine in η. This polynomial dependence on η allows the cone certificate to be represented and verified using Bernstein basis functions. A degree-two Bernstein basis (see [6, 14]) provides a convenient way to express this dependence and reduce verification over an entire simplex ∆V to finitely many coefficient conditions. Specifically, any polynomial h(η) of degree at most two can be written as X h(η) = hab Bab (η), 0≤a≤b≤4

where Baa (η) = ηa2 ,

Bab (η) = 2ηa ηb ,

9

0 ≤ a ≤ b ≤ 4.

are the 15 Bernstein basis functions with Bernstein coefficients hab . Thus, for each simplex ∆V and x ∈ ∆V , the marginal and pairwise moment vector   1 r(η) = x(η) y(η) in the moment equations of (3) and the optimal vertex distribution u∗ (η) in the cone certificate equation (4) can both be represented in this basis, with the Bernstein coefficients as derived in the next Lemma. Lemma 3 (Bernstein coefficients of the marginal moments, pairwise moments, and optimal vertex). For a given x ∈ [0, 1]4 and a corresponding optimal numerator vertex u⋆ (x, f ), let B = {S0 , . . . , S4 } denote the corresponding nonsingular five-subset basis, with incidence vectors v 0 , . . . , v 4 . Then the degreetwo Bernstein coefficients of x(η), y(η), and u⋆ (η) satisfying x(η) =

4 X

u⋆ (η) =

ηi v i ,

i=0

are given by xaa aa yij aa

u⋆ Proof. Since

4 X

4 X

ηi eSi ,

i=0

va + vb , 2 v v + vbi vaj ai bj ab = = vai vaj , yij , 2 e + e ab S Sb , = e Sa , u⋆ = a 2 xab =

= va,

ηi = 1,

ηi ≥ 0

i=0

a < b, a < b,

1 ≤ i < j ≤ 4,

(5)

a < b.

P4

i=0 ηi = 1, the affine representation of x can be written as

x(η) =

4 X

 ! 4 4 X X X ηi v i  ηj  = ηi2 v i + ηi ηj (v i + v j ).

i=0

j=0

i=0

i<j

Using Bii (η) = ηi2 and Bij (η) = 2ηi ηj for i < j gives x(η) =

4 X

Bii (η)v i +

i=0

X

Bij (η)

i<j

vi + vj , 2

which yields the stated coefficients of x. Similarly, yij = xi xj =

4 X

! ηk vki

k=0

4 X

! ηℓ vℓj

,

ℓ=0

and collecting the diagonal and off-diagonal terms gives the stated coefficients of y. Finally, similar to x, the coefficients of u⋆ follow from  ! 4 4 X X u⋆ (η) = ηi eSi  ηj  , i=0

j=0

which yields the stated coefficients of u⋆ . We next seek Bernstein coefficients pab , γ ab , and cab such that the moment equations in (3) and the cone certificate equation in (4) hold coefficientwise for each 0 ≤ a ≤ b ≤ 4. This coefficientwise feasibility is a sufficient condition for the corresponding polynomial identities to hold for every η in the simplex. Specifically, we represent the certificate variables as 10

X

p(η) =

pab Bab (η),

X

γ(η) =

0≤a≤b≤4

γ ab Bab (η),

c(η) =

0≤a≤b≤4

X

cab Bab (η),

(6)

0≤a≤b≤4

where pab ∈ R16 +,

γ ab ∈ R56 +,

cab ∈ R.

Lemma 4 (Bernstein coefficient system). Fix x ∈ [0, 1]4 and a corresponding optimal numerator vertex u⋆ (x, f ), represented on its associated nonsingular five-subset basis by x(η) =

4 X

⋆

ηi v i ,

u (η) =

i=0

4 X

ηi eSi ,

i=0

4 X

ηi = 1,

ηi ≥ 0.

i=0

For each 0 ≤ a ≤ b ≤ 4, let pab , γ ab , and cab denote the Bernstein coefficients of p(η), γ(η), and c, respectively from (6). A sufficient condition for the moment equations in (3) and the cone certificate equation (4) to hold for every η is that, for every 0 ≤ a ≤ b ≤ 4, AP pab = r ab , 4 ab ab p − G⊤ γ ab − cab e∅ = u⋆ 3 pab , γ ab ≥ 0.

(7)

ab

where r ab and u⋆ are the degree-two Bernstein coefficients of r(η) and u⋆ (η) respectively from (5). Thus, for each pair (a, b), the coefficient system consists of 11 + 16 = 27 linear equations in 16 + 56 + 1 = 73 unknowns (pab , γ ab , cab ). Proof. Substituting the Bernstein representations of p(η), γ(η), c(η), r(η), and u⋆ (η), and using the coefficient equations in (7), we obtain X X AP p(η) = AP pab Bab (η) = r ab Bab (η) = r(η), 0≤a≤b≤4

4 p(η) − G⊤ γ(η) − c(η)e∅ = 3 =

X 0≤a≤b≤4

X

0≤a≤b≤4



 4 ab ⊤ ab ab p − G γ − c e∅ Bab (η) 3 ab

u⋆ Bab (η) = u⋆ (η).

0≤a≤b≤4

Hence, the first two equation systems in (7) along with the non-negativity conditions pab , γ ab ≥ 0 are sufficient to ensure that p(η) ∈ F P (x) and γ(η) ∈ R56 + . This ensures that the moment equations in (3) and the cone certificate equation (4) hold for every η and therefore for every marginal probability vector x in the corresponding simplex ∆V whose optimal numerator vertex is u⋆ . The Bernstein coefficient system need not be solved separately for all 3, 008 nonsingular five-subset bases, since many bases are equivalent up to a permutation of the elements of N4 . We next introduce the concept of an orbit to capture this equivalence.

3.4

Permutation Orbits

Definition 1. Let Π4 denote the symmetric group of all 4! = 24 permutations of the elements of N4 . An orbit is a collection of nonsingular five-subset bases that are equivalent under permutations π ∈ Π4 . Specifically, two bases B = {S0 , . . . , S4 } and B ′ = {S0′ , . . . , S4′ } belong to the same orbit if there exists a permutation π of N4 such that B ′ = {π(S0 ), . . . , π(S4 )}, where π(S) = {π(i) : i ∈ S}.

11

For example, the bases B = {∅, {1}, {1, 2}, {1, 2, 3}, N4 } and B ′ = {∅, {2}, {1, 2}, {1, 2, 3}, N4 } are equivalent under the permutation π ∈ Π4 defined by π(1) = 2, π(2) = 1, π(3) = 3, π(4) = 4, and hence belong to the same orbit. The next lemma shows that the Bernstein coefficient system is invariant under permutations in Π4 , so that a feasible coefficient system for one basis induces a feasible coefficient system for every basis in the same orbit. Lemma 5 (Permutation invariance of the Bernstein coefficient system). Let O be an orbit of nonsingular five-subset bases, and let ∆O denote a representative simplex of the orbit. For any π ∈ Π4 , let ∆O π denote O the simplex obtained from ∆ by applying π. Then the Bernstein coefficient system (7) is invariant under permutation. In particular, if (pab , γ ab , cab ) is a
feasible solution of the coefficient system for ∆O , then the ab ab provide a feasible solution for ∆O . appropriately permuted coefficients pab π , γπ , c π Proof. The proof is relegated to Appendix A.3. Corollary 5 (Reduction to permutation orbits). The 3, 008 nonsingular five-subset bases in BNS partition into 183 representative orbits under permutations π ∈ Π4 , as shown in Table 7 of Appendix B. Hence, for each coefficient block (a, b), by Lemma 5, it suffices to establish the Bernstein coefficient system (7) for one representative basis from each of the 183 orbits. Proof. Two bases belong to the same orbit if one can be obtained from the other by a permutation of the four ground set elements in N4 . By Lemma 5, a feasible coefficient system for one basis induces a feasible coefficient system for every basis in its orbit. Since the 3, 008 nonsingular bases partition into 183 such orbits, it suffices to verify one representative from each orbit. With 15 Bernstein coefficient blocks (a, b), this amounts to solving 15 × 183 = 2, 745 linear coefficient systems of the form (7). Having reduced the problem to one representative basis from each of the 183 permutation orbits, we next address the possibility that the Bernstein coefficient system is infeasible on the entire representative simplex ∆O for a given coefficient block (a, b) by providing a recursive subdivision strategy in Algorithm 1.

3.5

Infeasibility and recursive subdivision algorithm

Algorithm 1 Recursive Simplex subdivision for Bernstein coefficient feasibility Require: Representative simplex ∆O , coefficient block (a, b), and maximum depth Dmax = 10 Ensure: A collection of leaf simplices covering ∆O , together with, for each feasible leaf, its depth and a certificate (pab , γ ab , cab ) satisfying (7) 1: Initialize a queue with the root simplex ∆O at depth 0. 2: Initialize the set of feasible leaf certificates as empty. 3: while the queue is nonempty do 4: Remove a simplex ∆ and its depth d from the queue. 5: Solve the coefficient system (7) for ∆ and block (a, b). 6: if the coefficient system is feasible then 7: Store the leaf simplex ∆, its depth d, and the certificate (pab , γ ab , cab ). 8: else if d < Dmax then 9: Identify the longest edge of ∆. 10: Bisect the longest edge of ∆ to obtain two child simplices ∆1 and ∆2 that differ in exactly one vertex. 11: Add ∆1 and ∆2 to the queue with depth d + 1. 12: else 13: Declare ∆ unresolved. 14: end if 15: end while 16: return The feasible leaf simplices, their depths, and the associated certificates (pab , γ ab , cab ).

12

Algorithm 1 describes a recursive subdivision strategy that splits an infeasible simplex using its longest edge. A child simplex for which the coefficient system is feasible is retained as a leaf, while an infeasible child is further subdivided. The procedure terminates when all resulting leaf simplices admit a feasible certificate, thereby providing a certificate over the entire original simplex, since the collection of leaf simplices cover ∆O . We note that each subdivision in Algorithm 1 bisects an edge and produces two child simplices, each obtained by replacing one of the two endpoints of the bisected edge by its midpoint. Hence every child simplex has vertices that are affine combinations of the vertices of the root simplex ∆O . Table 2 presents six representative permutation orbits spanning the ranges of the number of terminating leaves and subdivision depth across the 183 orbits. Orbits 31 and 164 terminate with the smallest number of leaves 4 with a maximum depth 2, orbits 83 and 50 terminate with the largest number of leaves 89 and 103 with depth 10, and orbits 61 and 109 represent intermediate cases near the median, both with depth 6. The subdivision statistics for the remaining orbits are reported in Table 7 of Appendix B. Table 2: Representative permutation orbits illustrating the range of subdivision Orbit Representative basis 31 {∅, {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}}

3.6

Leaves Depth 4 2

164

{{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, {1, 2, 3, 4}}

4

2

61

{∅, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {1, 2, 3, 4}}

20

6

109

{{1}, {2}, {1, 2, 3}, {1, 2, 4}, {1, 2, 3, 4}}

25

6

83

{{1}, {2}, {3}, {4}, {1, 2, 3, 4}}

89

10

50

{∅, {1, 2}, {1, 3}, {1, 4}, {2, 3, 4}}

103

10

Computational experiments

We implemented Algorithm 1 in Python 3.10.0 and used linear programming to test the feasibility of the 2, 745 Bernstein coefficient systems. All computational experiments were conducted on a MacBook Pro equipped with an Apple M4 Pro processor and 24 GB of memory, running macOS Sequoia 15.2. All 2, 745 coefficient systems were found to be feasible, with a total of 4476 successful leaf simplices, which proves that the 4/3 bound holds for n = 4 as claimed in Theorem 1. Table 7 reports the corresponding subdivision statistics, including the number of terminal leaf simplices and the maximum subdivision depth. Complete output details, including a JSON file for each of the 183 permutation orbits containing the terminal leaf simplices, subdivision depths, and Bernstein coefficients for each coefficient block, together with the Python implementation of the subdivision procedure, are available at the accompanying GitHub repository1 . To illustrate the complete recursive subdivision procedure, we next consider a representative permutation orbit, derive cone certificates for the resulting leaf simplices, and reconstruct the corresponding numerator and denominator distributions from their Bernstein coefficients.

3.7

Illustrative subdivision example

By the symmetry established in Lemma 5, it is sufficient to construct certificates for each coeficient block (a, b) using one representative simplex from each orbit. To illustrate the subdivision procedure, we consider the representative simplex for Orbit 164 from Table 7, denoted by ∆O = conv{v ∗0 , v ∗1 , v ∗2 , v ∗3 , v ∗4 }, where v ∗0 = e1 + e2 , 1

v ∗1 = e1 + e3 ,

v ∗2 = e2 + e3 ,

github.com/ArjunKRamachandra/CorrelationGap 4dimensions

13

v ∗3 = e1 + e2 + e3 ,

v ∗4 = 1.

are the incidence vectors corresponding to the five-subset basis B ⋆ = {{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, N4 }. P4 Since x = i=0 ηi v ∗i , we have x1 = η0 + η1 + η3 + η4 , x2 = η0 + η2 + η3 + η4 , x3 = η1 + η2 + η3 + η4 , P Since 4i=0 ηi = 1, we obtain x1 = 1 − η2 , x2 = 1 − η1 , x3 = 1 − η0 , x4 = η4 , and

x4 = η4 ,

x1 + x2 + x3 − x4 = 3 − (η0 + η1 + η2 ) − η4 = 3 − (1 − η3 ) = 2 + η3 ≥ 2, where the last equality follows from η3 ≥ 0. Hence the marginal vector x whose optimal numerator vertex u⋆ (x, f ) is supported on B ⋆ must satisfy x1 + x2 + x3 − x4 ≥ 2. throughout the simplex ∆O . The computational results in Table 7 show that the representative simplex for Orbit 164 is certified by four leaf simplices, with a maximum subdivision depth two. Since subdivision is performed only when the coefficient system is infeasible, the root simplex and both of its depth-one children are infeasible. Following the recursive subdivision procedure in Algorithm 1, the first bisection is performed along the longest failed edge (0, 1) of the root simplex, while the subsequent bisections are along the longest failed edge (1, 2) producing ∆1 , ∆2 and edge (0, 2) producing ∆3 , ∆4 at depth two. Table 3 lists the four leaf simplices together with their vertices v ji , where v ji denotes the ith vertex of the jth leaf simplex and their convex hull representations in terms of the representative vertices v ⋆0 , . . . , v ⋆4 . Each leaf-simplex vertex is either a representative vertex or the midpoint of an edge of the representative simplex. Table 3: Vertices of the root, intermediate, and leaf simplices for Orbit 164. Simplex

v j0

v j1

v j2

v j3

v j4

∆1

1, 12 , 12 , 0

1 1 2 , 2 , 1, 0

(0, 1, 1, 0)

(1, 1, 1, 0)

(1, 1, 1, 1)

∆2

1, 12 , 12 , 0

(1, 0, 1, 0)

1 1 2 , 2 , 1, 0

(1, 1, 1, 0)

(1, 1, 1, 1)

∆3

1 1 2 , 1, 2 , 0

1, 12 , 12 , 0

(0, 1, 1, 0)

(1, 1, 1, 0)

(1, 1, 1, 1)

∆4

(1, 1, 0, 0)

1, 12 , 12 , 0

1 1 2 , 1, 2 , 0

(1, 1, 1, 0)

(1, 1, 1, 1)

convex representation n hull o v ⋆0 +v ⋆1 v ⋆1 +v ⋆2 ⋆ ⋆ ⋆ conv , , v , v , v 2 3 4 2 2 n ⋆ ⋆ o ⋆ ⋆ v 0 +v 1 ⋆ v 1 +v 2 ⋆ ⋆ conv , v , , v , v 1 3 4 2 2 o n ⋆ ⋆ ⋆ ⋆ v 0 +v 2 v 0 +v 1 ⋆ ⋆ ⋆ , , v , v , v conv 2 3 4 2 2 o n ⋆ ⋆ ⋆ ⋆ v +v v +v conv v ⋆0 , 0 2 1 , 0 2 2 , v ⋆3 , v ⋆4

The four leaf simplices can alternatively be described through the convex coordinates of x with respect to their five vertices. Table 4 gives the corresponding convex coefficients ηij , where ηij denotes the convex coefficient of the ith vertex of the jth leaf simplex and should be distinguished from the coefficients ηi associated with the vertices of the representative simplex ∆O . These coefficients are obtained P4 j j from x = i=0 ηi v i for each j = 1, 2, 3, 4 and are affine functions of the marginal probabilities. The marginal probability conditions in the last column are obtained by requiring all five convex coefficients to be nonnegative, together with the root-simplex conditions. These restrictions characterize the four regions in which the corresponding optimal numerator vertex u⋆ (x, f ) is supported on the five vertices of the respective leaf simplex. Each subdivision corresponds to slicing the current parent simplex by a hyperplane. Specifically, the original representative simplex is first split by x2 = x3 . The branch x2 ≤ x3 is then split by x1 + x3 = 1 + x2 , yielding ∆1 and ∆2 , while the branch x2 ≥ x3 is split by x1 + x2 = 1 + x3 , yielding ∆3 and ∆4 . Equivalently, each leaf is the intersection of the representative simplex with the two corresponding half spaces. These four regions are mutually exclusive and cover ∆O as shown in Figure 1. Hence, every x ∈ ∆O belongs to one of the four leaf simplices, and the corresponding Bernstein certificates suffice to certify the entire representative simplex.

14

Table 4: Convex coefficients and marginal conditions for the four feasible leaf simplices of ∆O sub-simplex

η0j

η1j

η2j

∆1

2(1 − x3 )

2(x3 − x2 )

∆2

2(1 − x3 )

x1 − x 2 + x 3 − 1

∆3

2(x2 − x3 )

2(1 − x2 )

∆4

x1 + x 2 − x 3 − 1

2(1 − x2 )

η3j

η4j Marginal conditions x2 ≤ x3 , 1 − x 1 + x 2 − x 3 x1 + x 2 + x 3 − x 4 − 2 x4 x1 + x 3 ≤ 1 + x 2 x1 + x 2 + x 3 − x 4 − 2 x4

x2 ≤ x3 , x1 + x 3 ≥ 1 + x 2

1 − x 1 − x 2 + x 3 x1 + x 2 + x 3 − x 4 − 2 x4

x2 ≥ x3 , x1 + x 2 ≤ 1 + x 3

2(1 − x1 )

2(1 − x1 )

x2 ≥ x3 , x1 + x 2 ≥ 1 + x 3

x1 + x 2 + x 3 − x 4 − 2 x4

x ∈ ∆O x1 + x 2 + x 3 ≥ 2 + x 4

x2 ≤ x3

x2 ≥ x3

x1 + x 3 ≤ 1 + x 2

x1 + x 3 ≥ 1 + x 2

x1 + x 2 ≤ 1 + x 3

x1 + x 2 ≥ 1 + x 3

∆1

∆2

∆3

∆4

Figure 1: Subdivision of the representative simplex ∆O for Orbit 164 into four certified leaf simplices. To illustrate the construction of the cone certificate, we next highlight one of the leaf sub-simplices, namely sub-simplex 4. Table 5 reports, for each block (a, b), the Bernstein coefficient vectors pab and γ ab , together with the associated constant cab for sub-simplex 4. The corresponding Bernstein coefficient tables for the other three sub-simplices are provided in Appendix C. Table 6 illustrates the reconstructed optimal numerator and feasible denominator distributions for sub-simplex 4 in terms of the marginal probabilities. The numerator distribution is optimal whenever u∗ (x, f ) = arg maxu∈FU (x) f ⊤ u is supported on B ⋆ = {{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, N4 } for a given monotone submodular function vector f and a marginal probability vector x ∈ [0, 1]4 satisfying x1 + x 2 + x 3 ≥ 2 + x 4 ,

x2 ≥ x3 ,

x1 + x2 ≥ 1 + x3 .

(8)

It is obtained directly from u⋆ (x) =

4 X

ηi4 (x)ρi ,

 ρi =

eS0 ,

i=0

eS0 + eS1 eS0 + eS2 , , eS3 , eS4 2 2

 , i

where eSi is the 16-dimensional unit vector corresponding to the incidence vector of the ith vertex of the original representative simplex ∆O , and the convex coefficients ηi4 (x) are obtained from the last row of Table 4.

15

Table 5: Bernstein coefficients for sub-simplex 4. Block

pab

(0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (1, 1) (1, 2)

{3 : 1} { 0 : 1/3 4 : 1/3 } { 1 : 1/4 3 : 1/2 7 : 1/4 } { 0 : 1/3 10 : 1/12 15 : 1/4 } { 2 : 1/4 3 : 1/2 7 : 1/4 } { 1 : 1/3 10 : 1/12 17 : 1/4 } { 3 : 1/2 7 : 1/2 } { 0 : 1/3 4 : 1/3 10 : 1/6 } { 7 : 1/2 11 : 1/2 } { 0 : 1/3 4 : 1/3 10 : 1/6 11 : 1/6 44 : 1/2 } { 1 : 1/4 3 : 1/4 5 : 1/4 7 : 1/4 } { 0 : 1/3 10 : 1/6 15 : 1/6 } { 0 : 1/8 3 : 3/8 5 : 1/8 6 : { 0 : 1/6 4 : 1/6 10 : 1/6 15 : 1/12 17 : 1/12 } 1/8 7 : 1/4 } { 3 : 1/4 5 : 1/4 7 : 1/2 } { 0 : 1/3 4 : 1/4 5 : 1/12 10 : 1/6 } { 7 : 1/2 11 : 1/4 13 : 1/4 } { 1 : 1/12 2 : 1/4 14 : 1/12 15 : 1/6 16 : 1/12 17 : 1/4 25 : 1/12 43 : 1/12 44 : 1/4 47 : 1/6 55 : 1/4 } { 2 : 1/4 3 : 1/4 6 : 1/4 7 : 1/4 } { 1 : 1/3 10 : 1/6 17 : 1/6 } { 3 : 1/4 6 : 1/4 7 : 1/2 } { 0 : 1/4 1 : 1/12 4 : 1/4 8 : 1/12 10 : 1/6 } { 7 : 1/2 11 : 1/4 14 : 1/4 } { 0 : 1/12 2 : 1/12 14 : 1/12 15 : 1/4 17 : 1/6 18 : 1/12 22 : 1/6 23 : 1/12 34 : 1/6 40 : 1/4 44 : 1/4 55 : 1/4 } {7 : 1} { 0 : 1/3 4 : 1/3 10 : 1/3 } { 7 : 1/2 15 : 1/2 } { 0 : 1/3 4 : 1/3 10 : 1/3 19 : 1/6 } { 15 : 1 } { 0 : 1/3 4 : 1/3 10 : 1/3 19 : 1/3 }

(1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)

γ ab

cab 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3

The pairwise distribution, on the other hand, is not necessarily optimal for the given x and is reconstructed from X p(x) = pab Bab (η(x)), 0≤a≤b≤4

using the Bernstein coefficient distributions pab reported in Table 5 for each block (a, b). By Lemma 2, the distributions in Table 6 ensure that the cone certificate equation in (4) is satisfied for any monotone submodular function vector f and any x satisfying (8). It can be observed that the numerator distribution is supported on five points, precisely corresponding to the five vertices of the sub-simplex, while the pairwise distribution is supported on eleven points. Table 6: Optimal numerator and feasible denominator distributions for sub-simplex 4. Subset S

u∗S (x)

Subset S

pS (x)

{1, 2}

1 − x3

∅

(1 − x1 )(1 − x2 )

{1, 3}

1 − x2

{1}

(x1 − x3 )(1 − x2 )

{2, 3}

1 − x1

{2}

(1 − x1 )(x2 − x3 )

{1, 2, 3}

x1 + x 2 + x 3 − x 4 − 2

{1, 2}

x1 (x2 − x3 ) + x3 (1 − x2 ) − x4 (1 − x3 )

N4

x4

{1, 3}

(1 − x2 )(x3 − x4 )

{2, 3}

(1 − x1 )(x3 − x4 )

{1, 2, 3}

(x1 + x2 − 1)x3 − x4 (x1 + x2 + x3 − 2)

{1, 2, 4}

x4 (1 − x3 )

{1, 3, 4}

x4 (1 − x2 )

{2, 3, 4}

x4 (1 − x1 )

N4

x4 (x1 + x2 + x3 − 2)

16

4

Worst case asymptotic pairwise independent correlation gap

In this section, we prove that the worst case pairwise independent correlation gap attains e/(e − 1) asymptotically as n → ∞, the same worst case bound established in [4] under mutual independence. As an immediate consequence, since every t-wise independent distribution (t ≥ 2) is necessarily pairwise independent, our result implies that the worst case t-wise independent correlation gap is also exactly e/(e − 1). We first define a specific class of coverage functions that are monotone and submodular by definition that will be used to prove the main result.

Coverage functions Let Hm = {H ⊆ 2N : |H| = m} be a family of m-subsets of N , called features. Each feature H ∈ H is assigned a nonnegative weight wH ≥ 0. Define a corresponding nonnegative set function gm : 2N → R+ as: X gm (S) = wH 1{S ∩ H ̸= ∅}, S ⊆ N. H∈Hm

The function gm is a weighted coverage function and for a given S, equals the total weight of the features covered by S. Such a weighted coverage function is known to be nonnegative, nondecreasing and submodular (see [16]). Theorem 2. [Asymptotically tight bound] For any n, any nonnegative monotone submodular function f : 2N → R+ and any x ∈ [0, 1]n : f + (x) e ≤ f ++ (x) e−1 Moreover, the bound is asymptotically attained when: i) The ground set is partitioned into m blocks as N = A1 ∪ A2 ∪ · · · ∪ Am−1 ∪ Am , where jnk |Ar | = ℓ = , ∀r ∈ M \ {m}, |Am | = ℓm = n − (m − 1)ℓ, m and the feature family is defined as Hm = A1 × A2 × · · · × Am−1 × Am , consisting of all m-tuples obtained by selecting one element from each set of the partition. ii) The asymptotic regime considers the number of partition blocks m as a function of n, denoted by m = m(n), with both n and m(n) tending to infinity and m(n) growing sublinearly in n, i.e., n → ∞,

m(n) → ∞,

m(n) = o(n).

1 iii) The marginal probabilities are set to be identical with xi = m , ∀i ∈ N .

iv) The function f (S) is the coverage function gm (S) with unit feature weights wH = 1 for every H ∈ Hm and counts the number of features covered by at least one element of S.
1 1 1 Proof. We describe the key idea first. Let xid = m , m, . . . , m denote the identical marginal probability ++ id ++ id vector. For any upper bound f (x ) ≥ f (x ), we have f + (xid ) f

++

(xid )

≤

f + (xid ) . f ++ (xid )

Since [4] proved that f + (x) e ≤ , f ++ (x) e−1 17

for every marginal probability vector x, it is sufficient to construct an upper bound f f + (xid ) f

++

(xid )

++

(xid ) satisfying

e , e−1

−→

(9)

under the conditions (i) − (iv), forcing both ratios to converge to the common limit e/(e − 1). For the rest of the proof, we proceed step by step, first establishing the necessary preliminaries, beginning with the setup and definitions in Section 4.1.1. This is followed by the optimal concave closure value with identical marginals in Section 4.1.2, and an upper bound on the pairwise extension with identical marginals through a scaled asymptotic reduced dual formulation in Section 4.1.3, culminating in the detailed proof in Section 4.2. Remark 6. It was proved in [2] that the correlation gap is upper bounded by 4/3 for identical marginal probabilities satisfying n−2 1 or x ≥ . x≤ n−1 n−1 1 In the present construction, xi = m , where m = m(n) satisfies m(n) = o(n), m(n) → ∞ as n → ∞. Consequently, for all sufficiently large n, 2 ≤ m ≤ n − 2 and therefore

1 1 n−2 < < . n−1 m n−1 Therefore, the regime considered in Theorem 2 lies strictly outside the parameter ranges covered in [2], and leads to a different upper bound of e/(e − 1). Remark 7. Under the assumption m = m(n) → ∞, m = o(n), both the number of partition blocks and the size of each partition block diverge as n → ∞. Indeed, jnk n m → ∞, ℓ = → ∞, ℓm = n − (m − 1)ℓ ≥ → ∞ as n → ∞ (10) m m n → ∞,

A1

m → ∞, n ···

A2

m − 1 blocks,

ℓ→∞

Am−1

|Ar | = ℓ

Am

|Am | = n − (m − 1)ℓ

Figure 2: Schematic representation of the partition of the ground set N into m − 1 blocks of cardinality ℓ and a final block Am of cardinality n − (m − 1)ℓ in the asymptotic regime. The next result shows that the asymptotic result in Theorem 2 immediately extends to t-wise independent random elements (t ≥ 2), since t-wise independence implies pairwise independence. Corollary 6 (Extension to t-wise independence). Let f (t) (x), for t > 2, denote the optimal value of the t-wise independence formulation obtained by replacing the pairwise independence constraints in (2) with X S⊇{i1 ,...,ir }

Then

pS =

r Y

x ij ,

∀ i1 < · · · < ir ,

i1 , . . . , ir ∈ N,

∀ 1 ≤ r ≤ t.

j=1

f + (x) e ≤ . (t) e−1 f (x)

and the bound is attained under the the exact same conditions (i) − (iv) in Theorem 2. 18

Proof. Every t-wise independent distribution is, in particular, pairwise independent. Hence the feasible region defining f (t) is contained in that defining f ++ in formulation (2), implying f (t) (xid ) ≤ f ++ (xid ). Therefore, f + (xid ) f + (xid ) e f + (xid ) ≤ ≤ , ≤ e−1 f ++ (xid ) f (t) (xid ) f (n) (xid ) where the last inequality follows from the e/(e − 1) upper bound with mutual independence in [4]. The + id result then follows from Theorem 2, since ff++((xxid)) attains the bound e/(e − 1) asymptotically, forcing all ratios to converge to the common limit e/(e − 1).

4.1

Preliminaries leading to proof of Theorem 2

We now proceed to prove tightness of the e/(e − 1) bound in Theorem 2. In preparation, we next reiterate the tightness conditions (i) − (iv) in Theroem 2 along with some additional definitions needed to set up the tight instance. 4.1.1

Setup and definitions

In line with the tightness conditions (i) − (iv) in Theroem 2, we setup the problem instance as follows: i) The ground set is partitioned into m blocks as N = A1 ∪ A2 ∪ · · · ∪ Am−1 ∪ Am where the first m − 1 n blocks have equal cardinality |Ar | = ℓ = ⌊ m ⌋, r ∈ M \ {m}, and the last block consisting of the remaining elements has cardinality |Am | = ℓm = n − (m − 1)ℓ. ii) Further, let M = {1, 2, . . . , m}. Then for every subset S ⊆ N , definePthe block count ar = |S∩Ar |, r ∈ M as the number of elements from block Ar contained in S. Then m r=1 ar = |S|, since {Ar : r ∈ M } partitions the ground set N . iii) The feature family Hm = A1 × A2 × · · · × Am−1 × Am , consists of all m-tuples obtained by selecting one element from each set of the partition. iv) Define the set function f : 2N → R+ as the monotone submodular union coverage function f (S) = gm (S) P = H∈Hm 1{S ∩ H ̸= ∅}, Q = ℓm−1 ℓm − m−1 r=1 (ℓ − ar )(ℓm − am ).

(11)

for each S ⊆ N where ℓm−1 ℓm is the totalQ number of features in the feature family Hm = A1 × A2 × · · · × Am−1 × Am and the subtracted term m−1 r=1 (ℓ − ar )(ℓm − am ) represents the number of uncovered features. Thus, f (S) counts the total number of features covered by at least one element of S. v) For a subset S ⊆ N , define u(S) = (u1 (S), . . . , um (S)) ∈ [0, 1]m where ar am , r ∈ M \ {m}, um (S) = ℓ ℓm P denote the normalized block counts of S, and satisfy ℓ m−1 r=1 ur (S) + Qum (S) = |S|. Then the set function f (S) in (11) can be transformed into a normalized coverage polynomial F : [0, 1]m → [0, 1] as ur (S) =

m

F (u(S)) =

Y f (S) =1− (1 − ur (S)), m−1 ℓ ℓm r=1

19

∀S ⊆ N

(12)

We assume that all expectations in the definitions of f + (x) and f ++ (x) in (1) and (2) are henceforth computed with respect to F (u(S)) instead of f (S). Additionally, for notational convenience,Qwe drop the dependence on S (unless necessary in the context of a statement) and write F (u) = 1 − m r=1 (1 − ur ). 1 for every i ∈ N . m We next derive the optimal solution with identical marginals to the concave closure in (1) by identifying a worst case distribution. vi) Set the marginal probabilities to xi =

4.1.2

Concave closure with identical probabilities and normalized coverage function

Since the normalized block counts satisfy ur (Ar ) = 1 for every r ∈ M , the normalized coverage function defined in (12) satisfies F (u(Ar )) = 1 for every r ∈ M . Consequently, the concave closure in (1) satisfies f + (xid ) = 1, attained by the distribution   1 , S ∈ {A1 , A2 , . . . , Am }, ∗ p (S) = m  0, otherwise. Thus, it suffices to show that f ++ (xid ) −→ 1 −

1 e

as n → ∞ with m = m(n) → ∞ and m = o(n), so that f + (xid ) e −→ . ++ id e−1 f (x ) In the next section, we construct an asymptotic reduced dual formulation with identical marginals whose optimal value upper bounds f ++ (xid ) and asymptotically converges to 1 − 1e . 4.1.3

Pairwise independent asymptotic reduced dual formulation with identical marginals

The dual of the pairwise independent extension in (2) with the normalized submodular function in (12) can be written as: X X f ++ (x) = min λ0 + λ i xi + λij xi xj s.t.

λ0 +

i∈N X

λi +

i∈S

i<j X

λij ≥ F (u(S)),

∀S ⊆ N.

(13)

{i,j}⊆S

where all dual variables are unrestricted due to the equality constraints in (2). We next derive a reduced dual formulation of (13) for identical marginals x = xid by imposing symmetry restrictions on the dual variables λi , λij , followed by an asymptotic reduction after appropriate scaling of the dual variables . Lemma 6 (Reduced dual formulation). The dual formulation in (13) reduces to         n D ℓ ℓm E m−1 2 ++ id + + 2 ℓ + (m − 1)ℓℓm fRD (x ) = min A + B + 2 (m − 1) A,B,C,D m m 2 2 m 2 m m   X X X ar s.t. A+B ar + D +E ar as ≥ F (u(S)), ∀S ⊆ N. 2 r=1

r=1

1≤r<s≤m

which provides an upper bound on f ++ (xid ) i.e., ++ id f ++ (xid ) ≤ fRD (x ).

20

(14)

Proof. Let λ0 = A and impose the following symmetry restrictions on the remaining dual variables: ( D, i, j ∈ Ar , for some r ∈ M, λi = B, ∀i ∈ N, λij = (15) E, i ∈ Ar , j ∈ As , r ̸= s. 1 for each i ∈ N , Substituting these restricted dual variables into the objective of (13) along with xi = m we obtain         X X E Bn ℓ ℓm m−1 2 D + 2 λ0 + λ i xi + λij xi xj = A + + ℓ + (m − 1)ℓℓm + 2 (m − 1) 2 m m 2 m 2 i∈N

i<j

2

ℓ + since there are (m − 1) 2ℓ + ℓ2m pairs of elements belonging to the same partition block and m−1 2 (m − 1)ℓℓm pairs belonging to different partition blocks. Similarly, for the constraints, let S ⊆ N be an arbitrary subset. Recalling that ar = |S ∩ Ar | and {Ar : r ∈ M } forms a partition of N , we have X

λi = B

X

λij = D

{i,j}⊆S

ar ,

r=1

i∈S

and

m X

m   X ar r=1

2

+E

X

ar as ,

1≤r<s≤m

since every pair of elements of S either belongs to the same partition block or to two distinct partition blocks. Substituting these expressions into the constraints of (13) yields (14). Since the reduced dual is obtained from the original dual by imposing the symmetry restrictions in (15), the feasible region of the ++ id (x ). reduced dual is a subset of that of the original dual, implying f ++ (xid ) ≤ fRD We next scale the reduced dual variables B, D, E by n, n2 , n2 respectively and derive an asymptotic reduced dual as n → ∞ with the number of partition blocks m growing sublinearly with n i.e., m(n) = o(n) → ∞. Lemma 7 (Scaled asymptotic reduced dual (SARD) formulation). Under the asymptotic regime n → ∞, m(n) = o(n) → ∞, introduce the scaled dual variables e = B, B n

e = D, D n2

e= E, E n2

(16)

e D, e E e as B, D, E. Then the reduced dual (14) is and, for notational convenience, subsequently relabel B, asymptotically equivalent to   B D 1 1 ++ id A+ fSARD (x ) = min + + 1− E A,B,C,D m 2m3 2m2 m m

s.t.

A+

m

BX D X 2 E ur + ur + 2 2 m 2m m r=1

r=1

X 1≤r<s≤m

ur us ≥ 1 −

m Y

(1 − ur ), ∀ u ∈ [0, 1]m .

r=1

(17) Proof. The objective in (14) can be written in terms of the scaled variables in 16 as:         B n D ℓ ℓm E m−1 2 Φn = A + + 2 2 (m − 1) + + 2 2 ℓ + (m − 1)ℓℓm . nm n m 2 2 n m 2

21

(18)

n n + O(1), it follows that ℓm = n − (m − 1)ℓ = + O(m), and hence, under the condition m m m m(n) = o(n), we have :         1 1 1 ℓm 1 ℓ 1 1 = = , +O +O n2 2 2m2 mn n2 2 2m2 n

Since ℓ =

jnk

=

  1 1 ℓ2 = 2 +O , n2 m mn

  ℓℓm 1 1 = 2 +O 2 n m n

Substituting these expansions into (18) under the asymptotic regime n → ∞, m(n) = o(n) → ∞ yields:       B 1 E 1 B 1 E D D Φn = A + + 1− +O =A+ + 1− + o(1). + + 3 2 3 m 2m m 2m mn m 2m m 2m2 For the constraints, substituting the scaled variables into the reduced dual constraint (14) gives m m   X E BX f (S) D X ar + 2 A+ ar as ≥ m−1 , ∀S ⊆ N. ar + 2 2 ℓm n n n ℓ r=1

r=1

(19)

1≤r<s≤m

n n Since |Ar | = ℓ = +O(1), for r ∈ M \{m} and |Am | = ℓm = +O(m), under the condition m(n) = o(n), m m it follows that for any r ∈ M ,     |Ar | 1 1 ur |Ar | ur 1 = +O and = +O , since ur ∈ [0, 1] n m n n m n Therefore, since ar = |Ar |ur and ur ∈ [0, 1], we have       ur 1 1 ar |Ar |2 u2r 1 ar = +O , = +O n m n n2 2 2n2 mn and

1 1 1 ar as = 2 |Ar ||As |ur us = 2 ur us + O 2 n n m

  1 . n

Substituting these expansions into (19)yields: m

m

BX D X 2 E A+ ur + ur + 2 2 m 2m m r=1

r=1



X

ur us + O

1≤r<s≤m

m2 n

 ≥

f (S) ℓm−1 ℓm

∀S ⊆ N.

,

and hence under the asymptotic regime n → ∞, m(n) = o(n) → ∞, we have m

=A+

m

E D X 2 BX ur + ur + 2 m 2m2 m r=1

r=1

X 1≤r<s≤m

ur us + o(1) ≥ 1 −

m Y

(1 − ur )

(20)

r=1

where the inequality in (20) is required to hold for all subsets S ⊆ N . The family of occupancy vectors u(S) = (u1 (S), . . . , um (S)) induced by all subsets S ⊆ N becomes dense as n → ∞. Indeed, for any u ∈ [0, 1]m , choosing ar = ⌊ur |Ar |⌋, r ∈ M, it is always possible to assemble a subset S by choosing any arelements from each set Ar and taking their  ar : r ∈ M approximates u arbitrarily closely. Hence, union so that the normalized occupancy vector |Ar | for all r ∈ M , we have ar 1 0 ≤ ur − ≤ , |Ar | |Ar | 22

where the difference converges to zero since |Ar | → ∞ for all r ∈ M from (10). Consequently, the set of constraints in (20) can be equivalently expressed as m

m

D X 2 BX E ur + =A+ ur + 2 2 m 2m m r=1

r=1

X

ur us ≥ 1 −

m Y

(1 − ur ), ∀ u ∈ [0, 1]m .

(21)

r=1

1≤r<s≤m

For a fixed S ⊆ N , the RHS term in (21) is the normalized coverage polynomial defined in (12) and can be viewed as the multilinear extension (defined earlier) of the submodular set function f (R) = min{|R|, 1} with R ⊆ M and marginal probabilities ur (S). This completes the proof.

4.2

Proof of Theorem 2

We are now ready to prove the main result of this section in Theorem 2 by utilizing an upper bound on f ++ (x) provided by the scaled asymptotic reduced dual (SARD) formulation in Lemma 7. Proof. By Lemma’s 6 and 7, as n → ∞, we have: ++ f ++ (xid ) ≤ fSARD (xid ).

From (9), it is thus sufficient to construct a feasible solution for the scaled asymptotic reduced dual in (17) such that 1 ++ (xid ) −→ 1 − . fSARD e We express the (uncountably infinite) set of constraints in (17) as: ∀ u ∈ [0, 1]m ,

Q(u) ≥ F (u), m

where

Q(u) = A +

m

BX D X 2 E ui + ui + 2 m 2m2 m i=1

i=1

X

ui uj , and F (u) = 1 −

m Y

(1 − ur )

(22)

r=1

1≤i<j≤m

are quadratic and mth degree polynomials in u respectively. We next construct an explicit feasible solution that satisfy these constraints by imposing the following conditions at the symmetric point of the normalized
1 1 occupancy vector u⋆ = m ,..., m by: Q(u⋆ ) = F (u⋆ ), ∇Q(u⋆ ) = ∇F (u⋆ ), ∂2Q ∂ui ∂uj

(u⋆ ) =

∂2F ∂ui ∂uj

(u⋆ ),

(23) i ̸= j.

These conditions require Q and F to agree in their value, first derivatives, and mixed second derivatives at u⋆ . Solving these equations yields expressions for the dual variables A, B, E in terms of D as follows:   1 m−2 2 , E = −m 1 − m       D 1 m 1 m−1 3 (24) A = + 1− 1− − 2 1− , 2m3 m m   D 1 m−1 B = − 2 + 2m 1 − . m m It now remains to prove that the resulting quadratic polynomial Q(u, D) satisfies (22) for a finite free parameter D, i.e., ∃D ∈ R : G(u, D) = Q(u, D) − F (u) ≥ 0, ∀u ∈ [0, 1]m 23

Since A, B are affine in D while F is independent of D, we have:  m m m  ∂G ∂Q ∂A ∂Q ∂B ∂Q 1 1 X 1 2 1 X 2 1 X = + + = − ui − . ui + ui = ∂D ∂A ∂D ∂B ∂D ∂D 2m3 m3 2m2 2m2 m i=1

i=1

i=1

Hence G(u, D) is bi-affine in u, D and can be expressed as:  m  1 X 1 2 G(u, D) = DL(u) + R(u), where L(u) = ui − 2m2 m

(25)

i=1

since R is independent of D and D is independent of u. The dual feasibility conditions in (22) can now be expressed equivalently as   R(u) m ⋆ G(u, D) = DL(u) + R(u) ≥ 0 ∀ u ∈ [0, 1] ⇐⇒ D ≥ D = sup − (26) L(u) u∈[0,1]m where the existence of D⋆ < ∞ is sufficient to ensure feasibility since the dual variable D is unrestricted in (17). The conditions imposed in (23) imply that G(u, D) must satisfy: G(u⋆ , D) = 0,

∇u G(u⋆ , D) = 0,

From (25), we have L(u⋆ ) = 0, ∇L(u⋆ ) = 0, R(u⋆ ) = 0,

For the diagonal second derivatives,

∂ 2 G(u⋆ , D) = 0, ∂ui ∂uj

∇R(u⋆ ) = 0,

∂ 2 R(u⋆ ) = 0, i ̸= j. ∂ui ∂uj

(28)

∂2L 1 = 2 and hence for each i ∈ M , we have: 2 m ∂ui (29)

∂2Q D ∂2F = 2 and = 0 leading to 2 m ∂ui ∂u2i ∂ 2 G(u, D) ∂2Q ∂2F D = − = 2. 2 2 2 m ∂ui ∂ui ∂ui

From (29) and (30), we have

(27)

∂2L (u⋆ ) = 0, i ̸= j, which along with (27) implies ∂ui ∂uj

∂ 2 G(u, D) ∂ 2 L(u) ∂ 2 R(u) D ∂ 2 R(u) = D + = + . m2 ∂u2i ∂u2i ∂u2i ∂u2i Further, from (22), we have

i ̸= j

(30)

∂ 2 R(u) = 0, which together with (28) implies: ∂u2i R(u⋆ ) = 0,

∇R(u⋆ ) = 0,

∇2 R(u⋆ ) = 0.

(31)

Since L(u) and R(u) both vanish at u = u⋆ and L(u) > 0 otherwise, we need to show that the ratio −R(u)/L(u) in (26), although not defined at u = u⋆ , remains bounded both near and away from u⋆ . In particular, it suffices to establish the following two properties of the absolute ratio: 1.

R(u) lim ⋆ < ∞, u→u L(u)

24

2.

R(u) sup < ∞, u∈Kϵ L(u)

where Kϵ := {u ∈ [0, 1]m : ∥u − u⋆ ∥ ≥ ϵ} , for any ϵ > 0.

The first property follows from (31) since it implies that the Taylor’s expansion of R about u = u⋆ satisfies R(u⋆ + v) = O(∥v∥3 ). where v = u − u⋆ denotes the perturbation around u⋆ . From (25), we have L(u⋆ + v) = Θ(∥v∥2 ) and thus R(u⋆ + v) = O(∥v∥) −→ 0 L(u⋆ + v)

as v → 0.

To establish the second property, we note that L(u) =

1 ϵ2 ⋆ 2 ∥u − u ∥ ≥ , 2m2 2m2

∀ u ∈ Kϵ .

Moreover, R(u) = G(u, D) − DL(u) is a polynomial in u and hence is continuous on [0, 1]m . By the Extreme Value Theorem, there exists a finite constant M such that |R(u)| ≤ M, ∀ u ∈ [0, 1]m . Therefore, for all u ∈ Kϵ , 2m2 M R(u) ≤ < ∞. L(u) ϵ2 Combining the two properties, we obtain ⋆

D =

 sup u∈[0,1]m \{u⋆ }

R(u) − L(u)

 < ∞.

Substituting the expressions for A, B, E from (24) into the objective yields:   B D 1 1 ++ id fSARD (x ) ≤ A + + + 1− E m 2m3 2m2 m   1 m =1− 1− m

(32)

(33)

where the free parameter D cancels identically. For the m-partition instance with identity marginals xid , the feasible solution constructed above gives f + (xid ) 1 e
m −→ ≥ 1 ++ id e−1 f (x ) 1− 1− m

as m → ∞.

Since f + (xid ) = 1, it consequently follows that f ++ (xid ) −→ 1 − 1e in the asymptotic regime n → ∞, m(n) → ∞, m(n) = o(n) and the proof is completed.

4.3

Structure of the Asymptotic worst case Pairwise Independent Distribution

The asymptotic dual construction in Section (4.1.3) was sufficient to establish Theorem 2. However, it does not reveal the structure of the pairwise independent distribution attaining the asymptotic worst case. The following result, based on the construction of Boros and Prékopa in [15], shows that the extremal distribution that attains the limit 1 f ++ (xid ) −→ 1 − e is asymptotically supported on subsets of two adjacent cardinalities, both of the form n/m + O(1). Moreover, this distribution induces an expected occupancy of 1/m in each partition block Ar , r ∈ M , matching the identical marginal probabilities xi = 1/m. 25

Lemma 8 (Asymptotic worst case distribution for f ++ (xid )). Let x =

1 , m

 j = ⌈(n − 1)x⌉ =

 n−1 . m

Then, under the asymptotic regime n → ∞, m(n) = o(n) → ∞, there exists a pairwise independent distribution p⋆n supported on subsets of size j − 1 and j, i.e.,   |S| = j − 1, αn , ⋆ pn (S) = 1 − αn , |S| = j,   0, otherwise,

where αn =

1 1− m



j − (n−1) m
n−1

 ∈ [0, 1], such that

j−1

f

++

  1 m (x ) = Ep⋆n [f (S)/|Hm |] = 1 − 1 − + o(1). m id

Proof of Lemma 8. The worst case distribution p⋆n is derived from an asymptotic reduction of the optimal distribution of an aggregated linear program with given first and second moments in [15]. This distribution was shown to be feasible for pairwise independent identical random elements in [1] (see Theorem 4.1 therein). In other words, 
(1 − x) j − (n − 1)x   
, |S| = j − 1,  n−1    j−1 
   (1 − x) 1 + (n − 1)x − j  
, |S| = j, n−1 (34) p⋆n (S) = j   2  n(n − 1)x + (j − 1)(j − 2nx)   , |S| = n,    (n − j)2 + (n − j)     0, otherwise. satisfies pairwise independence with identical marginals x = 1/m when j = ⌈(n − 1)/m⌉. For a fixed feature H ∈ Hm with |H| = m, the distribution in (34) is symmetric within each cardinality layer. Hence, conditional on |S| = k, it is uniform over all k-subsets of N , and n−m k
n k

Prp⋆n (H ∩ S = ∅ | |S| = k) = Since

we have

=

m−1 Y

1−

r=0

k n−r

 .

n−1 n−1 ≤j< + 1, m m n j= + O(1), m

  j 1 1 = +O , n m n

  j−1 1 1 = +O . n m n

Thus, for k ∈ {j − 1, j} and uniformly for 0 ≤ r ≤ m − 1,   k 1 1 = +O . n−r m n

26

(35)

Therefore, log

m−1 Y r=0

k 1− n−r

!

m−1 X

   1 1 log 1 − +O m n r=0   m 1 +O = m log 1 − m n   1 = m log 1 − + o(1), m =

1 where the second equality follows from a first-order Taylor expansion of log around 1 − m and the third equality follows from the asymptotic regime n → ∞, m(n) = o(n). Exponentiating, m−1 Y r=0

1 since 1 − m

m

k 1− n−r



   
1 m o(1) 1 m = 1− e = 1− 1 + o(1) m m  m 1 = 1− + o(1), m

→ 1/e. Hence,   1 m Prp⋆n (H ∩ S = ∅ | |S| = k) = 1 − + o(1), m

k ∈ {j − 1, j}.

We next show that the mass on |S| = n vanishes. Using x = 1/m and j = (n − 1)x + O(1), we can write j = (n − 1)x + δ with 0 ≤ δ < 1. Then

n(n − 1)x2 + (j − 1)(j − 2nx) = n(n − 1)x2 + (n − 1)x + δ − 1 δ − (n + 1)x = (n − 1)x2 + (n + 1 − 2δ)x + δ(δ − 1) = O(n). Thus, the quadratic terms cancel. Moreover, since m ≥ 2, j = ⌈(n − 1)/m⌉ ≤ n/2 + 1, so n − j = Θ(n) and (n − j)2 + (n − j) = Θ(n2 ). Therefore,   O(n) 1 Prp⋆n (|S| = n) = =O = o(1). 2 Θ(n ) n Consequently, asymptotically all probability mass is concentrated on subsets of sizes j −1 and j. Hence, for any fixed feature H,   1 m Prp⋆n (H ∩ S = ∅) = 1 − + o(1), m and therefore

  1 m Prp⋆n (H ∩ S ̸= ∅) = 1 − 1 − + o(1). m

Since every feature in Hm is statistically identical, the expected contribution of each feature to the objective is   1 m 1− 1− + o(1). m By linearity of expectation, summing over |Hm | = ℓm−1 ℓm features yields     1 m m−1 Ep⋆n [f (S)] = ℓ ℓm 1 − 1 − + o(ℓm−1 ℓm ), m
1 m and hence Ep⋆n [f (S)/|Hm |] = 1 − 1 − m + o(1), as claimed. 27

We next show that the asymptotically extremal pairwise independent distribution in Lemma 8 induces an expected occupancy of 1/m in each partition block, matching the identity marginals xi = 1/m. Corollary 7 (Asymptotic occupancy of the partition blocks). Under the asymptotic regime n → ∞,

m = m(n) → ∞,

m(n) = o(n),

the distribution p⋆n in (34) induces an asymptotic occupancy of 1/m in each partition block Ar , r ∈ M , matching the identical marginal probabilities xi = 1/m, i.e., Ep⋆n [ur (S) | |S| = k] −→ where ur (S) =

1 , m

k ∈ {j − 1, j},

|S ∩ Ar | denotes the normalized occupancy of block Ar defined earlier. |Ar |

Proof. The proof is relegated to Appendix A.4.

5

Conclusion

This paper resolves two open questions concerning the worst case pairwise independent correlation gap for monotone submodular functions. First, we establish that the 4/3 bound indeed holds for n = 4, thereby confirming the conjecture of [2] for the only dimension left unresolved after the counterexample for n ≥ 5 in [3]. Using an AI-assisted proof combining theoretical analysis and computational verification, we develop a primal based approach that combines a structural characterization of optimal numerator vertices with permutation symmetry, cone certificate systems, Bernstein polynomial representations, recursive simplex subdivision, and computational verification. By treating both the numerator and denominator through their primal formulations, our approach allows a common cone certificate system to be constructed. In particular, 2, 745 Bernstein coefficient systems were computationally verified to be feasible, yielding 4, 476 successful leaf certificates and establishing the 4/3 bound universally for n = 4, and the bound is tight. Second, we complement the counterexample in [3] by showing that although the 4/3 bound fails for n ≥ 5, the worst case pairwise independent correlation gap fails to improve upon the classical e/(e − 1) bound established in [4] under mutual independence. We do so by partitioning the ground set into m blocks and defining features that select one element from each block, together with a monotone submodular union coverage function that counts the features covered by a given set S ⊆ N . The key condition is that the number of blocks grows sublinearly with the ground set size, so that both the number of blocks and the size of each block tend to infinity. The proof technique uses a scaled asymptotic reduced dual (SARD) of the pairwise independent extension and constructs a feasible solution that ensures that the pairwise independent extension is asymptotically no larger than 1 − 1/e. On the primal side, we characterize the corresponding asymptotically extremal pairwise independent distribution, showing that it is supported on subsets of two adjacent cardinalities, both of order n/m, and induces an expected occupancy of 1/m in each partition block, matching the identity marginals xi = 1/m. In particular, the key insight from this result is that, despite constraining only pairwise marginals and allowing arbitrary higher order dependencies, pairwise independence can be as restrictive as mutual independence in the worst case. The asymptotic result immediately extends to t-wise independent random elements (t ≥ 2), since t-wise independence implies pairwise independence. These two results together add to the theory of the correlation gap by showing that the pairwise independent correlation gap exhibits a dimension dependent worst case bound, with n = 4 being the largest dimension for which the 4/3 bound holds, while the worst case gap asymptotically attains the e/(e − 1) bound. For dimensions 5 ≤ n < ∞, the precise worst case pairwise independent correlation gap remains unknown and is bounded below by the current best known lower bound 640/479 > 4/3 and above by e/(e − 1). Another natural direction for future work is to consider positive correlations, which, being less restrictive, allow a larger set of feasible distributions thus increasing the denominator, suggesting that the 4/3 bound may continue to hold under positive correlations. 28

Acknowledgment: The author would like to thank Gustav Malmqvist2 , an AI enthusiast, who, inspired by our explicit identification of the n = 4 case as an open problem in [3], attempted to solve it using a human-AI workflow. Using GPT 5.6 and Fable 5, he developed a high level proof idea that ultimately led to the approach pursued in this paper.

References [1] A. Ramachandra and K. Natarajan, Tight probability bounds with pairwise independence, SIAM Journal on Discrete Mathematics, 37(2), 2023. doi:10.1137/21M1408294. [2] A. Ramachandra and K. Natarajan, Pairwise independent correlation gap, Operations Research Letters, 2025, 107255. doi:10.1016/j.orl.2025.107255. [3] A. Ramachandra and K. Natarajan, Counterexample to a conjecture on the pairwise independent correlation gap using AI, arXiv:2606.19663, 2026. [4] S. Agrawal, Y. Ding, A. Saberi, and Y. Ye, Price of correlations in stochastic optimization, Operations Research, 60(1), 150–162, 2012. doi:10.1287/opre.1110.1011. [5] H. W. Kuhn, Some combinatorial lemmas in topology, IBM Journal of Research and Development, 4(5), 518–524, 1960. doi:10.1147/rd.45.0518. [6] S. Bernstein, Démonstration du théorème de Weierstrass fondée sur le calcul des probabilités, Communications de la Société Mathématique de Kharkov, 2e série, 13, 1–2, 1912. [7] Q. Yan, Mechanism design via correlation gap, Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 710–719, 2011. doi:10.1137/1.9781611973082.56. [8] C. Chekuri and V. Livanos, On submodular prophet inequalities and correlation gap, Theoretical Computer Science, 1019, 114814, 2024. doi:10.1016/j.tcs.2024.114814. [9] E. Husić, Z. K. Koh, G. Loho, and L. A. Végh, On the correlation gap of matroids, Mathematical Programming, 210, 407–456, 2025. doi:10.1007/s10107-024-02116-w. [10] C. Chekuri, J. Vondrák, and R. Zenklusen, Submodular function maximization via the multilinear relaxation and contention resolution schemes, SIAM Journal on Computing, 43(6), 2014. doi:10.1137/110839655. [11] M. Luby and A. Wigderson, Pairwise independence and derandomization, Foundations and Trends in Theoretical Computer Science, 1, no. 4, 237–301, 2006. doi:10.1561/0400000009. [12] D. G. Wagner, Rank three matroids are Rayleigh, arXiv:math/0403216, 2004. [13] J. Huh, B. Schröter, and B. Wang, Correlation bounds for fields and matroids, Journal of the European Mathematical Society, 24, 1335–1351, 2022. doi:10.4171/JEMS/1119. [14] R. T. Farouki, The Bernstein polynomial basis: A centennial retrospective, Computer Aided Geometric Design, 29(6–7), 379–419, 2012. doi:10.1016/j.cagd.2012.03.001. [15] E. Boros and A. Prékopa, Closed form two-sided bounds for probabilities that at least r and exactly r out of n events occur, Mathematics of Operations Research, 14, 317–342, 1989. doi:10.1287/moor.14.2.317. [16] F. Bach, Learning with submodular functions: A convex optimization perspective, Foundations and Trends in Machine Learning, 6, no. 2–3, 145–373, 2013. doi:10.1561/2200000039. 2

Gustav Malmqvist, AI enthusiast. LinkedIn: https://se.linkedin.com/in/gmalmqvist.

29

A

Proofs of Results

Proof A.1 (Proof of Lemma 1.) First suppose that u is a vertex with J = supp(u). Suppose, to the contrary that the columns of A (in R5 ) corresponding to the subsets in J are linearly dependent. Then, there exists a vector d ∈ R16 with d ̸= 0 and supp(d) = J, such that Ad = 0. Since uj > 0 for every j ∈ J, choose uj 0 < ϵ < min . j∈J: dj ̸=0 |dj | Then u + ϵd ≥ 0, u − ϵd ≥ 0, and   1 A(u ± ϵd) = Au = . x Thus both perturbed points belong to FU (x), with 1 1 u = (u + ϵd) + (u − ϵd), 2 2 contradicting the extremality of u. Hence the corresponding columns of A (in R5 ) are linearly independent and hence |J| ≤ 5. Thus every vertex of u ∈ FU (x) is supported on at most five subsets of N4 . Conversely, suppose that the columns of A corresponding to J are linearly independent. Then |J| ≤ 5. If u were not a vertex, there would exist u+ , u− ∈ FU (x) such that 1 u = (u+ + u− ), 2

u+ ̸= u−

Since u is zero outside J and u+ , u− ≥ 0, both u+ and u− must also be zero outside J. Hence there exists a vector d such that: d = u+ − u− ̸= 0, supp(d) ⊆ J, and

Ad = Au+ − Au− = 0.

which contradicts the linear independence of the columns indexed by J. Therefore u is a vertex. Proof A.2 (Proof of Corollary 3). The covering property follows immediately from Corollary 2, since every x ∈ [0, 1]4 belongs to the incidence simplex corresponding to the nonsingular five-subset basis induced by an optimal numerator vertex. To see that the covering is overlapping, consider the two nonsingular bases B1 = {∅, {4}, {3, 4}, {2, 3, 4}, {1, 2, 3, 4}},

B2 = {∅, {1}, {2}, {3}, {4}}

. whose corresponding incidence simplices are ∆V (B1 ) = conv{0, e4 , e3 + e4 , e2 + e3 + e4 , 1},

∆V (B2 ) = conv{0, e1 , e2 , e3 , e4 }.

The first simplex is characterized by x1 ≤ x2 ≤ x3 ≤ x4 , while the second is characterized by x1 + x2 + x3 + x4 ≤ 1. Hence their intersection contains all x satisfying both conditions and is therefore non-empty containing a continuum of points. Thus, the set of nonsingular five-subset simplices cover [0, 1]4 but do not form a partition. Proof A.3 (Proof of Lemma 5). A permutation π of the four ground set elements induces permutations of the 16 subsets of N4 , the 56 submodularity constraints, and the 11 moment equations. Let Rπ ∈ R16×16 ,

Lπ ∈ R56×56 ,

Tπ ∈ R11×11

denote the corresponding permutation matrices that act on the Bernstein coefficient vectors according to Rπ pab = pab π ,

Rπ u⋆

ab

ab

= u⋆π ,

Rπ e∅ = e∅ , 30

Lπ γ ab = γ ab π ,

Tπ r ab = r ab π .

(36)

where, Rπ e∅ = e∅ follows from the first row and first column of Rπ being (1, 0, . . . , 0), since the empty set ab is fixed under every permutation. Thus Rπ acts on the 16-dimensional distribution vectors u⋆ and pab , Lπ acts on the 56-dimensional vector γ ab , and Tπ acts on the 11-dimensional right-hand side r ab in (7). Since relabeling the ground set elements only relabels the marginal and pairwise moment equations, the moment matrix satisfies AP Rπ = Tπ AP . (37) Likewise, relabeling the ground set elements only relabels the submodularity constraints. Hence the rows and columns of G⊤ are permuted consistently, giving Rπ G⊤ = G⊤ Lπ .

(38)

From (36), (37), (38), the moment equation for the permuted simplex is satisfied since ab ab ab AP pab = r ab π = AP (Rπ p ) = Tπ AP p = Tπ r π .

and the cone certificate equation for the permuted simplex is satisfied since 4 Rπ pab − G⊤ Lπ γ ab − cab e∅ 3 4 Rπ pab − Rπ G⊤ γ ab − cab Rπ e∅ 3   4 ab ⊤ ab ab p − G γ − c e∅ = Rπ 3 ab ab = Rπ u⋆ = u⋆π .

4 ab ab p − G⊤ γ ab π − c e∅ = 3 π =

Thus, permutation of a feasible coefficient solution for the representative simplex yields a feasible coefficient solution for every simplex in the same orbit. Proof A.4 (Proof of Corollary 7). For k ∈ {j − 1, j}, the distribution in (34) is uniform within the k-layer. Hence, for any i ∈ N ,
  n−1 k 1 1 k−1 Prp⋆n (i ∈ S | |S| = k) = n
= = +O . n m n k P For each partition block Ar , r ∈ M , we have |S∩Ar | = i∈Ar 1{i∈S} , and hence, by linearity of expectation, Ep⋆n [ur (S) | |S| = k] =

1 X k 1 Prp⋆n (i ∈ S | |S| = k) = −→ |Ar | n m i∈Ar

under the asymptotic regime considered. Thus, the expected occupancy of each partition block Ar , r ∈ M , which is the average probability that an element of Ar is included in S, equals the identical marginal probability Pr(i ∈ S) = 1/m.

B

Orbit representatives and subdivision statistics from Section 3.4

31

Table 7: Subdivision statistics for the 183 permutation orbit representatives. Orbit 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92

Representative basis {∅, {1}, {2}, {3}, {4}} {∅, {1}, {2}, {3}, {1, 4}} {∅, {1}, {2}, {3}, {1, 2, 4}} {∅, {1}, {2}, {3}, {1, 2, 3, 4}} {∅, {1}, {2}, {1, 3}, {1, 4}} {∅, {1}, {2}, {1, 3}, {2, 4}} {∅, {1}, {2}, {1, 3}, {1, 2, 4}} {∅, {1}, {2}, {1, 3}, {3, 4}} {∅, {1}, {2}, {1, 3}, {1, 3, 4}} {∅, {1}, {2}, {1, 3}, {2, 3, 4}} {∅, {1}, {2}, {1, 3}, {1, 2, 3, 4}} {∅, {1}, {2}, {1, 2, 3}, {1, 2, 4}} {∅, {1}, {2}, {1, 2, 3}, {3, 4}} {∅, {1}, {2}, {1, 2, 3}, {1, 3, 4}} {∅, {1}, {2}, {1, 2, 3}, {1, 2, 3, 4}} {∅, {1}, {1, 2}, {1, 3}, {1, 4}} {∅, {1}, {1, 2}, {1, 3}, {2, 4}} {∅, {1}, {1, 2}, {1, 3}, {1, 2, 4}} {∅, {1}, {1, 2}, {1, 3}, {2, 3, 4}} {∅, {1}, {1, 2}, {1, 3}, {1, 2, 3, 4}} {∅, {1}, {1, 2}, {2, 3}, {2, 4}} {∅, {1}, {1, 2}, {2, 3}, {1, 2, 4}} {∅, {1}, {1, 2}, {2, 3}, {3, 4}} {∅, {1}, {1, 2}, {2, 3}, {1, 3, 4}} {∅, {1}, {1, 2}, {2, 3}, {2, 3, 4}} {∅, {1}, {1, 2}, {2, 3}, {1, 2, 3, 4}} {∅, {1}, {1, 2}, {1, 2, 3}, {1, 2, 4}} {∅, {1}, {1, 2}, {1, 2, 3}, {3, 4}} {∅, {1}, {1, 2}, {1, 2, 3}, {1, 3, 4}} {∅, {1}, {1, 2}, {1, 2, 3}, {2, 3, 4}} {∅, {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}} {∅, {1}, {2, 3}, {2, 4}, {3, 4}} {∅, {1}, {2, 3}, {2, 4}, {1, 3, 4}} {∅, {1}, {2, 3}, {2, 4}, {2, 3, 4}} {∅, {1}, {2, 3}, {2, 4}, {1, 2, 3, 4}} {∅, {1}, {2, 3}, {1, 2, 4}, {1, 3, 4}} {∅, {1}, {2, 3}, {1, 2, 4}, {2, 3, 4}} {∅, {1}, {2, 3}, {1, 2, 4}, {1, 2, 3, 4}} {∅, {1}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}} {∅, {1}, {1, 2, 3}, {1, 2, 4}, {2, 3, 4}} {∅, {1}, {1, 2, 3}, {1, 2, 4}, {1, 2, 3, 4}} {∅, {1, 2}, {1, 3}, {2, 3}, {1, 4}} {∅, {1, 2}, {1, 3}, {2, 3}, {1, 2, 4}} {∅, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3, 4}} {∅, {1, 2}, {1, 3}, {1, 2, 3}, {1, 4}} {∅, {1, 2}, {1, 3}, {1, 2, 3}, {2, 4}} {∅, {1, 2}, {1, 3}, {1, 2, 3}, {1, 2, 4}} {∅, {1, 2}, {1, 3}, {1, 2, 3}, {2, 3, 4}} {∅, {1, 2}, {1, 3}, {1, 2, 3}, {1, 2, 3, 4}} {∅, {1, 2}, {1, 3}, {1, 4}, {2, 3, 4}} {∅, {1, 2}, {1, 3}, {1, 4}, {1, 2, 3, 4}} {∅, {1, 2}, {1, 3}, {2, 4}, {1, 3, 4}} {∅, {1, 2}, {1, 3}, {1, 2, 4}, {2, 3, 4}} {∅, {1, 2}, {1, 3}, {1, 2, 4}, {1, 2, 3, 4}} {∅, {1, 2}, {1, 3}, {2, 3, 4}, {1, 2, 3, 4}} {∅, {1, 2}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}} {∅, {1, 2}, {1, 2, 3}, {3, 4}, {1, 3, 4}} {∅, {1, 2}, {1, 2, 3}, {1, 3, 4}, {2, 3, 4}} {∅, {1, 2}, {1, 2, 3}, {1, 3, 4}, {1, 2, 3, 4}} {∅, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}} {∅, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {1, 2, 3, 4}} {{1}, {2}, {1, 2}, {3}, {4}} {{1}, {2}, {1, 2}, {3}, {1, 4}} {{1}, {2}, {1, 2}, {3}, {1, 2, 4}} {{1}, {2}, {1, 2}, {3}, {3, 4}} {{1}, {2}, {1, 2}, {3}, {1, 3, 4}} {{1}, {2}, {1, 2}, {3}, {1, 2, 3, 4}} {{1}, {2}, {1, 2}, {1, 3}, {1, 4}} {{1}, {2}, {1, 2}, {1, 3}, {2, 4}} {{1}, {2}, {1, 2}, {1, 3}, {1, 2, 4}} {{1}, {2}, {1, 2}, {1, 3}, {3, 4}} {{1}, {2}, {1, 2}, {1, 3}, {1, 3, 4}} {{1}, {2}, {1, 2}, {1, 3}, {2, 3, 4}} {{1}, {2}, {1, 2}, {1, 3}, {1, 2, 3, 4}} {{1}, {2}, {1, 2}, {1, 2, 3}, {1, 2, 4}} {{1}, {2}, {1, 2}, {1, 2, 3}, {3, 4}} {{1}, {2}, {1, 2}, {1, 2, 3}, {1, 3, 4}} {{1}, {2}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}} {{1}, {2}, {3}, {1, 2, 3}, {4}} {{1}, {2}, {3}, {1, 2, 3}, {1, 4}} {{1}, {2}, {3}, {1, 2, 3}, {1, 2, 4}} {{1}, {2}, {3}, {1, 2, 3}, {1, 2, 3, 4}} {{1}, {2}, {3}, {4}, {1, 2, 3, 4}} {{1}, {2}, {3}, {1, 4}, {1, 2, 4}} {{1}, {2}, {3}, {1, 4}, {2, 3, 4}} {{1}, {2}, {3}, {1, 4}, {1, 2, 3, 4}} {{1}, {2}, {3}, {1, 2, 4}, {1, 2, 3, 4}} {{1}, {2}, {1, 3}, {1, 2, 3}, {1, 4}} {{1}, {2}, {1, 3}, {1, 2, 3}, {2, 4}} {{1}, {2}, {1, 3}, {1, 2, 3}, {1, 2, 4}} {{1}, {2}, {1, 3}, {1, 2, 3}, {3, 4}} {{1}, {2}, {1, 3}, {1, 2, 3}, {1, 3, 4}}

Leaves Depth 32 7 33 6 10 4 24 6 29 7 6 3 16 5 42 8 5 3 14 5 14 5 27 7 50 7 16 6 12 5 32 7 13 5 12 5 28 6 10 4 55 9 17 6 31 8 31 6 18 5 17 5 12 5 13 5 17 6 13 5 4 2 80 8 51 7 32 8 40 8 38 7 23 5 23 5 38 7 28 6 20 6 48 8 42 7 20 6 48 9 20 6 18 6 31 6 10 5 103 10 40 8 33 6 43 7 15 6 30 6 25 6 23 5 36 7 14 5 38 7 20 6 72 9 31 7 10 5 35 7 18 5 27 6 13 5 8 3 11 4 22 8 7 3 15 5 16 5 15 5 30 7 9 5 8 4 40 8 54 7 23 6 24 6 89 10 30 7 55 7 59 7 26 6 15 5 13 5 28 7 37 7 9 4

Orbit 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183

Representative basis Leaves Depth {{1}, {2}, {1, 3}, {1, 2, 3}, {2, 3, 4}} 15 6 {{1}, {2}, {1, 3}, {1, 2, 3}, {1, 2, 3, 4}} 13 5 {{1}, {2}, {1, 3}, {1, 4}, {3, 4}} 37 8 {{1}, {2}, {1, 3}, {1, 4}, {1, 2, 3, 4}} 25 6 {{1}, {2}, {1, 3}, {2, 4}, {3, 4}} 36 8 {{1}, {2}, {1, 3}, {2, 4}, {1, 2, 3, 4}} 22 5 {{1}, {2}, {1, 3}, {1, 2, 4}, {3, 4}} 54 8 {{1}, {2}, {1, 3}, {1, 2, 4}, {1, 3, 4}} 17 5 {{1}, {2}, {1, 3}, {1, 2, 4}, {2, 3, 4}} 28 6 {{1}, {2}, {1, 3}, {3, 4}, {1, 3, 4}} 21 8 {{1}, {2}, {1, 3}, {3, 4}, {2, 3, 4}} 30 8 {{1}, {2}, {1, 3}, {3, 4}, {1, 2, 3, 4}} 41 7 {{1}, {2}, {1, 3}, {1, 3, 4}, {1, 2, 3, 4}} 13 5 {{1}, {2}, {1, 3}, {2, 3, 4}, {1, 2, 3, 4}} 23 5 {{1}, {2}, {1, 2, 3}, {1, 2, 4}, {3, 4}} 75 8 {{1}, {2}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}} 31 6 {{1}, {2}, {1, 2, 3}, {1, 2, 4}, {1, 2, 3, 4}} 25 6 {{1}, {2}, {1, 2, 3}, {3, 4}, {1, 3, 4}} 39 7 {{1}, {2}, {1, 2, 3}, {3, 4}, {1, 2, 3, 4}} 50 7 {{1}, {2}, {1, 2, 3}, {1, 3, 4}, {1, 2, 3, 4}} 16 5 {{1}, {1, 2}, {1, 3}, {2, 3}, {1, 4}} 12 4 {{1}, {1, 2}, {1, 3}, {2, 3}, {2, 4}} 18 6 {{1}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 4}} 16 5 {{1}, {1, 2}, {1, 3}, {2, 3}, {2, 3, 4}} 15 5 {{1}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3, 4}} 20 5 {{1}, {1, 2}, {1, 3}, {1, 4}, {2, 3, 4}} 24 6 {{1}, {1, 2}, {1, 3}, {2, 4}, {1, 2, 4}} 6 3 {{1}, {1, 2}, {1, 3}, {2, 4}, {1, 3, 4}} 14 5 {{1}, {1, 2}, {1, 3}, {2, 4}, {1, 2, 3, 4}} 14 5 {{1}, {1, 2}, {1, 3}, {1, 2, 4}, {2, 3, 4}} 14 5 {{1}, {1, 2}, {1, 3}, {2, 3, 4}, {1, 2, 3, 4}} 12 5 {{1}, {1, 2}, {2, 3}, {1, 2, 3}, {2, 4}} 18 6 {{1}, {1, 2}, {2, 3}, {1, 2, 3}, {1, 2, 4}} 13 5 {{1}, {1, 2}, {2, 3}, {1, 2, 3}, {3, 4}} 14 5 {{1}, {1, 2}, {2, 3}, {1, 2, 3}, {1, 3, 4}} 17 6 {{1}, {1, 2}, {2, 3}, {1, 2, 3}, {2, 3, 4}} 7 3 {{1}, {1, 2}, {2, 3}, {1, 2, 3}, {1, 2, 3, 4}} 10 4 {{1}, {1, 2}, {2, 3}, {2, 4}, {3, 4}} 33 7 {{1}, {1, 2}, {2, 3}, {2, 4}, {1, 3, 4}} 38 7 {{1}, {1, 2}, {2, 3}, {2, 4}, {2, 3, 4}} 20 6 {{1}, {1, 2}, {2, 3}, {2, 4}, {1, 2, 3, 4}} 30 6 {{1}, {1, 2}, {2, 3}, {1, 2, 4}, {1, 3, 4}} 27 6 {{1}, {1, 2}, {2, 3}, {1, 2, 4}, {1, 2, 3, 4}} 19 5 {{1}, {1, 2}, {2, 3}, {3, 4}, {1, 3, 4}} 23 5 {{1}, {1, 2}, {2, 3}, {3, 4}, {1, 2, 3, 4}} 26 6 {{1}, {1, 2}, {2, 3}, {1, 3, 4}, {2, 3, 4}} 23 5 {{1}, {1, 2}, {2, 3}, {2, 3, 4}, {1, 2, 3, 4}} 13 5 {{1}, {1, 2}, {1, 2, 3}, {1, 2, 4}, {3, 4}} 24 6 {{1}, {1, 2}, {1, 2, 3}, {1, 2, 4}, {2, 3, 4}} 12 4 {{1}, {1, 2}, {1, 2, 3}, {3, 4}, {1, 3, 4}} 18 5 {{1}, {1, 2}, {1, 2, 3}, {3, 4}, {1, 2, 3, 4}} 14 5 {{1}, {1, 2}, {1, 2, 3}, {1, 3, 4}, {2, 3, 4}} 17 5 {{1}, {1, 2}, {1, 2, 3}, {2, 3, 4}, {1, 2, 3, 4}} 5 3 {{1}, {2, 3}, {1, 2, 3}, {2, 4}, {3, 4}} 41 7 {{1}, {2, 3}, {1, 2, 3}, {2, 4}, {1, 3, 4}} 38 7 {{1}, {2, 3}, {1, 2, 3}, {2, 4}, {2, 3, 4}} 15 5 {{1}, {2, 3}, {1, 2, 3}, {2, 4}, {1, 2, 3, 4}} 28 6 {{1}, {2, 3}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}} 36 7 {{1}, {2, 3}, {1, 2, 3}, {1, 2, 4}, {2, 3, 4}} 18 6 {{1}, {2, 3}, {1, 2, 3}, {1, 2, 4}, {1, 2, 3, 4}} 21 6 {{1}, {2, 3}, {2, 4}, {3, 4}, {2, 3, 4}} 25 7 {{1}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3, 4}} 56 8 {{1}, {2, 3}, {2, 4}, {1, 3, 4}, {1, 2, 3, 4}} 37 6 {{1}, {2, 3}, {2, 4}, {2, 3, 4}, {1, 2, 3, 4}} 18 6 {{1}, {2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}} 27 6 {{1}, {2, 3}, {1, 2, 4}, {1, 3, 4}, {1, 2, 3, 4}} 29 6 {{1}, {2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 2, 3, 4}} 15 5 {{1}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}} 24 6 {{1}, {1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 2, 3, 4}} 12 5 {{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, {1, 4}} 12 5 {{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, {1, 2, 4}} 11 4 {{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, {1, 2, 3, 4}} 4 2 {{1, 2}, {1, 3}, {2, 3}, {1, 4}, {1, 2, 4}} 18 5 {{1, 2}, {1, 3}, {2, 3}, {1, 4}, {2, 3, 4}} 27 6 {{1, 2}, {1, 3}, {2, 3}, {1, 4}, {1, 2, 3, 4}} 12 5 {{1, 2}, {1, 3}, {2, 3}, {1, 2, 4}, {1, 2, 3, 4}} 13 5 {{1, 2}, {1, 3}, {1, 2, 3}, {1, 4}, {2, 3, 4}} 27 6 {{1, 2}, {1, 3}, {1, 2, 3}, {2, 4}, {1, 2, 4}} 8 3 {{1, 2}, {1, 3}, {1, 2, 3}, {2, 4}, {1, 3, 4}} 15 5 {{1, 2}, {1, 3}, {1, 2, 3}, {2, 4}, {1, 2, 3, 4}} 5 3 {{1, 2}, {1, 3}, {1, 2, 3}, {1, 2, 4}, {2, 3, 4}} 16 5 {{1, 2}, {1, 3}, {1, 2, 3}, {2, 3, 4}, {1, 2, 3, 4}} 9 4 {{1, 2}, {1, 3}, {1, 4}, {2, 3, 4}, {1, 2, 3, 4}} 24 6 {{1, 2}, {1, 3}, {2, 4}, {1, 3, 4}, {2, 3, 4}} 23 5 {{1, 2}, {1, 3}, {2, 4}, {1, 3, 4}, {1, 2, 3, 4}} 11 5 {{1, 2}, {1, 3}, {1, 2, 4}, {2, 3, 4}, {1, 2, 3, 4}} 13 5 {{1, 2}, {1, 2, 3}, {1, 2, 4}, {3, 4}, {1, 3, 4}} 15 5 {{1, 2}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}} 20 5 {{1, 2}, {1, 2, 3}, {3, 4}, {1, 3, 4}, {1, 2, 3, 4}} 6 3 {{1, 2}, {1, 2, 3}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}} 10 4 {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}} 8 3

C

Sample Bernstein Coefficients for Orbit 164 in Section 3.7 Table 8: Bernstein coefficients for sub-simplex 1.

Block

pab

γ ab

cab

(0, 0) (0, 1)

{ 0 : 1/3 10 : 1/6 15 : 1/6 } { 0 : 1/6 4 : 1/6 10 : 1/4 17 : 1/12 }

1/3 1/3

(0, 2) (0, 3) (0, 4)

{ 1 : 1/4 3 : 1/4 5 : 1/4 7 : 1/4 } { 0 : 1/8 3 : 1/8 5 : 3/8 6 : 1/8 7 : 1/4 } { 2 : 1/4 4 : 1/4 7 : 1/2 } { 3 : 1/4 5 : 1/4 7 : 1/2 } { 7 : 1/2 11 : 1/4 13 : 1/4 }

1/3 1/3 1/3

(1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)

{ 4 : 1/4 5 : 1/4 6 : 1/4 7 : 1/4 } { 4 : 1/4 6 : 1/2 7 : 1/4 } { 5 : 1/4 6 : 1/4 7 : 1/2 } { 7 : 1/2 13 : 1/4 14 : 1/4 } {6 : 1} { 6 : 1/2 7 : 1/2 } { 7 : 1/2 14 : 1/2 } {7 : 1} { 7 : 1/2 15 : 1/2 } { 15 : 1 }

{ 10 : 1/4 15 : 1/4 17 : 1/6 35 : 1/3 } { 0 : 1/3 4 : 1/4 5 : 1/12 10 : 1/6 } { 1 : 1/12 2 : 1/4 14 : 1/12 15 : 1/6 16 : 1/12 17 : 1/4 25 : 1/12 43 : 1/12 44 : 1/4 47 : 1/6 55 : 1/4 } { 2 : 1/3 15 : 1/6 17 : 1/6 } { 2 : 1/3 15 : 1/4 17 : 1/12 } { 0 : 1/4 1 : 1/12 4 : 1/6 5 : 1/12 8 : 1/12 10 : 1/6 } { 2 : 1/6 14 : 1/6 15 : 1/4 17 : 1/4 22 : 1/6 34 : 1/6 40 : 1/6 48 : 1/6 55 : 1/3 } { 1 : 1/3 8 : 1/3 } { 0 : 1/6 1 : 1/6 4 : 1/6 8 : 1/6 10 : 1/6 } { 17 : 1/6 18 : 1/6 21 : 1/3 26 : 1/3 34 : 1/3 39 : 1/3 44 : 1/3 49 : 1/6 } { 0 : 1/3 4 : 1/3 10 : 1/3 } { 0 : 1/3 4 : 1/3 10 : 1/3 19 : 1/6 } { 0 : 1/3 4 : 1/3 10 : 1/3 19 : 1/3 }

1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3

Table 9: Bernstein coefficients for sub-simplex 2. Block

pab

γ ab

cab

(0, 0) (0, 1) (0, 2)

{ 0 : 1/3 10 : 1/6 15 : 1/6 } { 0 : 1/3 10 : 1/4 15 : 1/12 } { 0 : 1/6 4 : 1/6 10 : 1/4 17 : 1/12 }

1/3 1/3 1/3

(0, 3) (0, 4)

{ 1 : 1/4 3 : 1/4 5 : 1/4 7 : 1/4 } { 1 : 1/4 5 : 1/2 7 : 1/4 } { 0 : 1/8 3 : 1/8 5 : 3/8 6 : 1/8 7 : 1/4 } { 3 : 1/4 5 : 1/4 7 : 1/2 } { 7 : 1/2 11 : 1/4 13 : 1/4 }

1/3 1/3

(1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)

{5 : 1} { 4 : 1/4 5 : 1/2 7 : 1/4 } { 5 : 1/2 7 : 1/2 } { 7 : 1/2 13 : 1/2 } { 4 : 1/4 5 : 1/4 6 : 1/4 7 : 1/4 } { 5 : 1/4 6 : 1/4 7 : 1/2 } { 7 : 1/2 13 : 1/4 14 : 1/4 } {7 : 1} { 7 : 1/2 15 : 1/2 } { 15 : 1 }

{ 0 : 1/3 4 : 1/4 5 : 1/12 10 : 1/6 } { 1 : 1/12 2 : 1/4 14 : 1/12 15 : 1/6 16 : 1/12 17 : 1/4 25 : 1/12 43 : 1/12 44 : 1/4 47 : 1/6 55 : 1/4 } { 0 : 1/3 5 : 1/3 } { 2 : 1/3 15 : 1/12 17 : 1/4 } { 0 : 1/3 4 : 1/6 5 : 1/6 10 : 1/6 } { 0 : 1/3 15 : 1/6 16 : 1/6 24 : 1/3 39 : 1/3 44 : 1/3 48 : 1/6 } { 2 : 1/3 15 : 1/6 17 : 1/6 } { 0 : 1/4 1 : 1/12 4 : 1/6 5 : 1/12 8 : 1/12 10 : 1/6 } { 2 : 1/6 14 : 1/6 15 : 1/4 17 : 1/4 22 : 1/6 34 : 1/6 40 : 1/6 48 : 1/6 55 : 1/3 } { 0 : 1/3 4 : 1/3 10 : 1/3 } { 0 : 1/3 4 : 1/3 10 : 1/3 19 : 1/6 } { 0 : 1/3 4 : 1/3 10 : 1/3 19 : 1/3 }

1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3

Table 10: Bernstein coefficients for sub-simplex 3. Block

pab

γ ab

cab

(0, 0) (0, 1)

{ 1 : 1/3 10 : 1/6 17 : 1/6 } { 0 : 1/6 4 : 1/6 10 : 1/6 15 : 1/12 17 : 1/12 }

1/3 1/3

(0, 2) (0, 3) (0, 4)

{ 2 : 1/4 3 : 1/4 6 : 1/4 7 : 1/4 } { 0 : 1/8 3 : 3/8 5 : 1/8 6 : 1/8 7 : 1/4 } { 2 : 1/4 6 : 1/2 7 : 1/4 } { 3 : 1/4 6 : 1/4 7 : 1/2 } { 7 : 1/2 11 : 1/4 14 : 1/4 }

1/3 1/3 1/3

(1, 1) (1, 2) (1, 3) (1, 4)

{ 1 : 1/4 3 : 1/4 5 : 1/4 7 : 1/4 } { 2 : 1/4 4 : 1/4 7 : 1/2 } { 3 : 1/4 5 : 1/4 7 : 1/2 } { 7 : 1/2 11 : 1/4 13 : 1/4 }

(2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)

{6 : 1} { 6 : 1/2 7 : 1/2 } { 7 : 1/2 14 : 1/2 } {7 : 1} { 7 : 1/2 15 : 1/2 } { 15 : 1 }

{ 1 : 1/3 10 : 1/4 17 : 1/12 } { 0 : 1/4 1 : 1/12 4 : 1/4 8 : 1/12 10 : 1/6 } { 0 : 1/12 2 : 1/12 14 : 1/12 15 : 1/4 17 : 1/6 18 : 1/12 22 : 1/6 23 : 1/12 34 : 1/6 40 : 1/4 44 : 1/4 55 : 1/4 } { 0 : 1/3 10 : 1/6 15 : 1/6 } { 10 : 1/4 15 : 1/4 17 : 1/6 35 : 1/3 } { 0 : 1/3 4 : 1/4 5 : 1/12 10 : 1/6 } { 1 : 1/12 2 : 1/4 14 : 1/12 15 : 1/6 16 : 1/12 17 : 1/4 25 : 1/12 43 : 1/12 44 : 1/4 47 : 1/6 55 : 1/4 } { 1 : 1/3 8 : 1/3 } { 0 : 1/6 1 : 1/6 4 : 1/6 8 : 1/6 10 : 1/6 } { 17 : 1/6 18 : 1/6 21 : 1/3 26 : 1/3 34 : 1/3 39 : 1/3 44 : 1/3 49 : 1/6 } { 0 : 1/3 4 : 1/3 10 : 1/3 } { 0 : 1/3 4 : 1/3 10 : 1/3 19 : 1/6 } { 0 : 1/3 4 : 1/3 10 : 1/3 19 : 1/3 }

1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3

Related documents

• The Hidden Topology of Network Entanglement#1144428
• Random independent sets and local sparsity#927922
• Correlation comparisons and critical curves for disordered XY models#1083661
• Disorder Thresholds and Free Energy of Brownian Directed Polymers with Product and Radial Spatial Correlations#790260
• Carrier-Weighted Networks: Separating Coherent Minority Structure from Incoherent Edges with Matched Pooled Correlations#617144