For every integer n≥ 1, every monotone submodular function f:2^[n]→R_≥ 0, and every marginal vector x∈[0,1]^n with f^++(x)>0, the correlation gap under pairwise independence is at most 4/3: fracf^+(x)f^++(x)≤frac43. Here f^+(x)=maxE[f(S)]:S=i:X_i=1, X∈0,1^n, E[X_i]=x_i, while f^++(x) is the same maximum restricted to jointly distributed random variables X_1,…,X_n that are pairwise independent.

Pairwise independent correlation gap conjecture

For every integer $n\ge 1$ , every monotone submodular function $f:2^{[n]}\to\mathbb{R}_{\ge 0}$ , and every marginal vector $x\in[0,1]^n$ with $f^{++}(x)>0$ , the correlation gap under pairwise independence is at most $4/3$ : $\frac{f^{+}(x)}{f^{++}(x)}\le\frac{4}{3}$ . Here $f^{+}(x)=\max\{\mathbb{E}[f(S)]:S=\{i:X_i=1\},\ X\in\{0,1\}^n,\ \mathbb{E}[X_i]=x_i\}$ , while $f^{++}(x)$ is the same maximum restricted to jointly distributed random variables $X_1,\ldots,X_n$ that are pairwise independent.

References

Primary source

arXiv

Additional references

Dimension Dependent Correlation Gap Bounds under Restricted Independence — arXiv

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A new preprint claims to settle the four-variable case and the limiting worst case, while the earlier five-variable counterexample remains valid.

Ramachandra and Natarajan (2025) conjectured that the correlation-gap ratio is at most $4/3$ for every dimension. A June 2026 preprint disproved this for $n\geq 5$ , leaving $n=4$ open until the latest claimed development.

Known results

$n=2$ and $n=3$ : the $4/3$ bound was known to hold.
The bound was also known for certain marginal probabilities and specific submodular functions.
For $n\geq 5$ , a coverage-function example gives $f^{+}(x)/f^{++}(x)\geq 640/479>4/3$ ; the example was found with assistance from GPT5.5 Pro.

September 2, 2026 claimed resolution

A new preprint claims the $4/3$ bound for $n=4$ , proves that bound is tight, and constructs asymptotic examples attaining $e/(e-1)$ , with an extension to $t$ -wise independence. This is a claimed resolution, not yet independently verified.

Current status (as of September 2026): The $n\geq 5$ counterexample and the cases $n=2,3$ are reported, while the $n=4$ proof, its tightness, and the asymptotic constant $e/(e-1)$ are claimed by a new preprint but remain unverified.

Sources

No solutions have been posted yet.