Source-linked AI summary
Dimension Dependent Correlation Gap Bounds under Restricted Independence
Arjun Ramachandra
TL;DR
The paper addresses the unresolved n = 4 case and the universal worst-case bound for pairwise independent correlation gaps. It proves the tight 4/3 bound for n = 4 and shows that the worst-case gap asymptotically reaches e/(e −1).
Problem
The paper resolves the remaining n = 4 question and asks whether pairwise independence admits a universal bound below e/(e −1) after the 4/3 conjecture failed for n ≥5.
Method
The paper combines primal structural analysis, permutation symmetry, cone certificates, Bernstein representations, recursive simplex subdivision, and computational verification, then uses a scaled asymptotic reduced dual with block-based union coverage instances.
Results
The 4/3 bound holds tightly for n = 4, while the worst-case pairwise independent correlation gap asymptotically attains e/(e −1).
Takeaways & Limitations
Pairwise independence has a dimension-dependent bound: 4/3 is the largest-dimension guarantee established here, but the asymptotic worst case matches the mutual-independence bound.
Takeaways & Limitations
The n = 4 theorem is stated for nonnegative monotone submodular functions and marginal vectors x ∈ [0,1]^4, with feasibility ensured by mutual independence.
Abstract
from arXiv · showhide
The pairwise independent correlation gap is the ratio of the maximum expected value of a set function under arbitrary dependence to that under pairwise independence, measuring the loss from this independence restriction. Under mutual independence, this gap is universally bounded by $e/(e-1)$ for monotone submodular functions. With pairwise independence, a tighter $4/3$ upper bound was established for several special cases, including $n=3$, and conjectured to hold universally. A recent AI-assisted counterexample disproved this conjecture for $n=5$, leaving the validity of the $n=4$ bound and the tight worst case bound open. We resolve both questions. 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 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 a monotone submodular union coverage function on a ground set partitioned into $m$ blocks. The number of blocks grows sublinearly with the ground set size. The result follows by constructing a feasible solution to a scaled asymptotic reduced dual of the pairwise independent linear program and immediately extends to $t$-wise independent random elements ($t\ge2$), since $t$-wise independence implies pairwise independence. 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.
1 Introduction
The section defines the pairwise independent correlation gap as the loss from imposing pairwise independence and reviews its computational difficulty and known 4/3 results.
- Definitions: The correlation gap compares the maximum expected value under arbitrary dependence with the expected value under mutual independence.The numerator is the concave closure f+(x), while the denominator is the multilinear extension F(x).
- Known bounds: The mutual-independence correlation gap for monotone submodular functions is universally bounded by e/(e−1).The ratio measures the loss incurred by ignoring higher-order dependence and imposing independence.
- Definitions: Pairwise independence imposes marginal and pairwise-probability constraints while permitting arbitrary higher-order dependencies.Its feasible distributions can have sparse support, which is useful for derandomization of NP-hard optimization algorithms.
- Challenges: Computing the concave closures f+(x) and f++(x) is NP-hard in the worst case, unlike evaluating F(x).The optimal distributions for the closures depend on the function, complicating analysis even for n = 3.
- Known bounds: The 4/3 upper bound is tight for the rank-one function f(S) = min(|S|, 1) and holds for all monotone submodular functions when n = 3.The bound also holds in a separate general-dimensional case with restricted marginal probabilities.
2 Recent Developments and Our Contributions
The paper resolves the remaining n = 4 question and determines the asymptotic worst-case bound after the universal 4/3 conjecture was disproved for n = 5.
- Recent developments: The n = 5 counterexample disproved the universal 4/3 conjecture and established a lower-bound interval for all n ≥ 5.Padding with zero-marginal Bernoulli variables extends the counterexample to every dimension n > 5.
- Contributions: The 4/3 upper bound survives for n = 4 and is tight.This result applies universally to the relevant monotone submodular setting.
- Contributions: The asymptotic worst-case pairwise independent correlation gap attains e/(e−1), matching the mutual-independence worst-case bound.The result uses a monotone submodular union coverage function on a ground set partitioned into sublinear-growth blocks.
- Implications: The asymptotic result extends to every t-wise independent distribution with t ≥ 2 because t-wise independence implies pairwise independence.Thus the worst-case t-wise independent correlation gap is also exactly e/(e−1).
- Contributions: The n = 4 result provides universal certification, whereas the asymptotic result provides a worst-case construction as n →∞.Together they characterize the dimension-dependent behavior at n = 4 and asymptotically.
3 A 4/3 bound for n = 4 random elements
For n = 4, the paper proves that the pairwise independent correlation gap is universally at most 4/3 and that this bound is tight. The proof combines structural, symmetry-based, Bernstein, subdivision, and computational certificates.
- 4/3 is a universal upper bound for every nonnegative monotone submodular function and every x ∈[0, 1]4.
- Structural characterization: Every optimal numerator vertex in four dimensions is supported on at most five subsets and can be represented by a nonsingular five-subset basis.
- Permutation symmetry: Permutation symmetry reduces 3,008 nonsingular bases to 183 representative orbits, with 15 Bernstein coefficient systems checked for each orbit.
- Certified subdivision: Recursive longest-edge subdivision covers infeasible representative simplices with leaf simplices admitting feasible cone certificates.
- Computational verification: 2,745 Bernstein coefficient systems were verified feasible, yielding 4,476 successful leaf simplices and establishing the n = 4 bound.
- The 4/3 bound is tight for f(S) = min{|S|, 1} with x1 + x2 + x3 = 1/2 and x4 = 1/2.
4 Worst case asymptotic pairwise independent correlation gap
The worst-case pairwise independent correlation gap asymptotically reaches e/(e−1) using block-partitioned coverage functions with identical marginals, and the result extends to t-wise independence.
- Theorem 2 establishes that the worst-case pairwise independent correlation gap asymptotically attains e/(e−1), matching the mutual-independence bound.
- The construction partitions the ground set into m blocks and defines features by selecting one element from each block.The block count satisfies m(n)→∞ and m(n)=o(n), so both the number and sizes of blocks diverge.
- The instance uses identical marginal probabilities xi=1/m and a monotone submodular union coverage function counting features covered by a selected set.Unit-weight features are formed from all m-tuples containing one element from each partition block.
- Because t-wise independence implies pairwise independence, the same asymptotic bound and attainment extend to every t≥2.The t-wise feasible region is contained in the pairwise-independent feasible region, and the constructed instance attains the common limit.
- The concave closure equals 1 for the constructed identical-marginal instance, while the pairwise-independent extension converges to 1−1/e.Their ratio therefore converges to e/(e−1).
- A scaled asymptotic reduced dual supplies an upper bound on the pairwise-independent extension, while a matching asymptotically extremal distribution has support on two adjacent cardinalities.The distribution induces expected occupancy 1/m in every block, matching the identical marginals.
5 Conclusion
The paper resolves the two open questions by proving the tight 4/3 bound for n=4 and showing that the worst-case gap asymptotically reaches e/(e−1).
- For n=4, the 4/3 bound holds universally for monotone submodular functions and marginal vectors, and is tight.The proof verifies 2,745 Bernstein coefficient systems and obtains 4,476 successful leaf certificates.
- The asymptotic construction shows that pairwise independence can be as restrictive as mutual independence in the worst case.It uses block-partitioned coverage functions with sublinearly growing block count and identical marginals.
- For 5≤n<∞, the precise worst-case pairwise independent correlation gap remains unknown, bounded below by 640/479 and above by e/(e−1).
A Proofs of Results
The proofs characterize optimal numerator vertices, cover the marginal space with overlapping incidence simplices, and certify the n=4 bound through symmetry and Bernstein systems.
- Certificate construction: Recursive longest-edge subdivision supplies certificates when a Bernstein coefficient system is infeasible on an entire representative simplex.Feasible child simplices become leaves, while infeasible children are subdivided until the leaves cover the original simplex.
- Structural characterization: Every vertex of the feasible region is supported on at most five subsets of N4.This follows from linear independence of the corresponding constraint-matrix columns; conversely, linear independence also certifies vertexhood.
- Permutation symmetry: Permutation symmetry transfers a feasible coefficient solution from one representative simplex to every simplex in its permutation orbit.The induced permutations consistently relabel distributions, moment equations, and submodularity constraints.
- Asymptotic construction: The asymptotic construction gives every partition block the identical marginal probability 1/m through its expected occupancy.For each block Ar, the average inclusion probability of its elements equals Pr(i ∈S) = 1/m.
B Orbit representatives and subdivision statistics from Section 3.4
Table 7 reports subdivision statistics for the 183 permutation orbit representatives, while the accompanying listing enumerates representative basis data and associated values.
- Subdivision statistics: 183 permutation orbit representatives are the organizing units for the subdivision statistics in Table 7.The table caption identifies the representatives and the statistics being reported.
- Subdivision statistics: The proof’s subdivision output includes terminal leaf counts and maximum subdivision depth for the orbit representatives.These are the subdivision statistics explicitly identified in the surrounding proof text.
- Representative records: The listed representative records pair subset bases with numerical entries, but the supplied passage does not identify those entries’ column meanings.The basis listings include collections of subsets and adjacent numeric values.
C Sample Bernstein Coefficients for Orbit 164 in Section 3.7
The supplied captions identify sample Bernstein-coefficient tables for three sub-simplices associated with the orbit analysis.
- Sample Bernstein coefficients: Table 8 presents Bernstein coefficients for sub-simplex 1.
- Sample Bernstein coefficients: Table 9 presents Bernstein coefficients for sub-simplex 2.
- Sample Bernstein coefficients: Table 10 presents Bernstein coefficients for sub-simplex 3.