The pairwise independent correlation gap: an exact worst case 4/3 at n=4 outside the known regions, and a lower bound 416/311 at n=5

Abstract

For a nonnegative nondecreasing submodular set function f on n elements and a marginal vector x ∈ [0,1]ⁿ, let f⁺(x) be the largest expectation of f over all distributions on subsets with marginals x, and f⁺⁺(x) the same maximum over pairwise independent distributions. Ramachandra and Natarajan conjectured that f⁺(x) ≤ 4/3f⁺⁺(x) always; the bound is known for n ≤ 3 and, by their work, for all n when the marginals are all small or all large, and in June 2026 they refuted it at n=5 with a coverage function whose gap is at least 640/479, leaving n=4 open and asking for the tightest bound when n ≥ 5. We prove that at n=4 and x₀=(1/2,1/6,1/6,1/6) – a marginal vector outside every region where the bound was known – the inequality f⁺(x₀) ≤ 4/3f⁺⁺(x₀) holds for every function in the class and is attained by f(S)=min(|S|,1), so the worst-case gap there is exactly 4/3. The proof is a two-part certificate: a modular majorant of f and one explicit pairwise independent distribution with a Farkas multiplier. At n=5 we show that the counterexample function of Ramachandra and Natarajan, at the marginals ((9)/(26),(5)/(13),(5)/(13),(7)/(26),(7)/(26)), has f⁺=4 and f⁺⁺=311/104 exactly, so its gap is 416/311>640/479; this improves their lower bound at n=5, the only one we know of, and padding with zero marginals carries it to every n ≥ 5. We also show that f⁺⁺=479/160 exactly at their original instance. Every theorem is verified in Lean 4 with Mathlib, with all data in exact rational arithmetic. An exhaustive search over the combinatorial part of the n=4 problem, reported separately from the formal development, finds no gap above 4/3.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-09-07 03:53 UTC

   File fingerprint

   d163af8ef6dd38630235e22ad37ea0ab5951df7618199b604aca355c241db98e