Dimension Dependent Correlation Gap Bounds under Restricted Independence
Abstract
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≥2), 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.
Related
- Linear Independence of Random Boolean Tensor Powers at the Dimension Threshold
- The Generative Mechanism of Dimension: An Axiomatic Construction of Dimensional Conventions (Constructive Mathematics Series, Paper 6; Lean formalization, model-pair independence, numerical evidence)
- Spatial Kernel Restricted Canonical Correlation Analysis: Population Targets, Identifiability, and Stability
- Improved Subexponential Upper Bounds for $3$-Restricted Matching Vector Families
- Optimization and complexity of inertia-type bounds on the independence and chromatic numbers of graph powers
BibTeX
@misc{ramachandra2026dimension,
title = {{Dimension Dependent Correlation Gap Bounds under Restricted Independence}},
author = {Arjun Ramachandra},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.02659},
eprint = {2609.02659},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.02659},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Dimension Dependent Correlation Gap Bounds under Restricted Independence
AU - Arjun Ramachandra
PY - 2026
DA - 2026/09/02
PB - arXiv
DO - 10.48550/arxiv.2609.02659
UR - https://arxiv.org/abs/2609.02659
AB - 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≥2), 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.
ER -