Dimension Dependent Correlation Gap Bounds under Restricted Independence

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.