Dimension Dependent Correlation Gap Bounds under Restricted Independence
math.PR · cs.LG · math.CO
Quick verdict
Proves the open 4/3 bound for n=4 via certified computation and shows the pairwise-independent gap hits e/(e-1) asymptotically; solid, minor asymptotic slack.
Summary
This paper resolves the two open questions left by a recent counterexample concerning the pairwise independent correlation gap of monotone submodular set functions — the ratio of the concave closure f+(x) to the pairwise independent extension f++(x). First, it proves that for n=4 the 4/3 upper bound holds universally and is tight. The proof enumerates the 3,008 nonsingular five-subset LP bases (reduced to 183 permutation orbits), formulates primal cone certificates valid over the whole monotone submodular cone, encodes them with degree-2 Bernstein polynomials, and computationally verifies 2,745 LP feasibility systems (15 coefficient blocks × 183 orbits) after recursive simplex subdivision, obtaining 4,476 leaf certificates at depths up to 10. Second, it shows the worst-case gap attains e/(e−1) asymptotically: a union coverage function on m ground-set blocks (m=o(n), identical marginals 1/m) gives f+=1, and a scaled asymptotic reduced dual yields f++ ≤ 1−(1−1/m)^m → 1−1/e; the result extends to t-wise independence for all t≥2. Main limitations: the asymptotic proof carries a stated O(m²/n) error term that does not vanish under the announced m=o(n) regime; the n=4 verification is floating-point LP with no stated exact-arithmetic certification; and the AI-assisted derivation, though transparently disclosed, awaits independent verification.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 4 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- For every nonnegative monotone submodular function f and every x ∈ [0,1]^4, the pairwise independent correlation gap satisfies f+(x)/f++(x) ≤ 4/3, and the bound is tight (Theorem 1, via 2,745 computationally verified Bernstein certificate systems).
- The worst-case pairwise independent correlation gap over monotone submodular functions attains e/(e−1) asymptotically as n→∞ (Theorem 2), so pairwise independence offers no worst-case improvement over mutual independence in high dimensions.
- The same asymptotic worst case e/(e−1) holds for t-wise independence for every t ≥ 2 (Corollary 6).
- n=4 is the largest dimension for which the 4/3 bound holds; for 5 ≤ n < ∞ the exact worst case remains open within [640/479, e/(e−1)].
Strengths
Resolves the two precisely-posed open questions
After [3]'s n=5 counterexample (gap 640/479 ≈ 1.336 > 4/3), n=4 was the only dimension where the 4/3 bound remained unresolved; Theorem 1 closes it and Theorem 2 pins the n→∞ worst case, giving the clean dimension-by-dimension picture of Table 1.
Correct-by-design certificate architecture
Lemma 2's primal cone certificate (4/3·p − u* = Gᵀγ + c·e∅) makes a single LP certificate cover the entire 56-inequality monotone submodular cone; Lemma 4 (coefficientwise Bernstein sufficiency, 27 equations × 73 unknowns per system) and Lemma 5 (permutation invariance, 3,008 bases → 183 orbits) reduce a continuum of marginal vectors to 2,745 finite LPs.
Unusual artifact transparency for a mathematics paper
Dual and primal views of the asymptotic extremal instance agree
Honest scoping against prior work
Weaknesses
Asymptotic regime/error mismatch
Floating-point certification without exact re-verification
No analytic termination guarantee for the subdivision
Presentation defects impede auditing
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper studies the pairwise independent correlation gap f+(x)/f++(x) for nonnegative monotone submodular set functions, where f+ is the concave closure (LP (1)) and f++ the pairwise independent extension (LP (2)). Following [1,2] (4/3 bound in special cases, universal conjecture) and [3] (AI-assisted n=5 counterexample with gap 640/479 ≈ 1.336 > 4/3), two questions were open: does 4/3 hold for n=4, and what is the true worst case? The paper claims both (Theorems 1–2): (i) for n=4 the 4/3 bound holds universally and is tight; (ii) the worst case attains e/(e−1) ≈ 1.582 asymptotically as n→∞, hence pairwise — and any t-wise with t≥2 (Corollary 6) — independence is asymptotically as restrictive as mutual independence. Table 1 neatly summarizes the resulting state of knowledge: 4/3 for n≤4, gap in [640/479, e/(e−1)] for 5≤n<∞, and e/(e−1) as n→∞.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 4 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is the pairwise independent correlation gap?
For a monotone submodular set function and marginal probabilities x, it is the ratio f+(x)/f++(x): the maximum expected function value over all joint distributions with those marginals (the concave closure) divided by the maximum when the random elements are only required to be pairwise independent. It measures the expected-value loss from knowing only first- and second-order moments. Under full mutual independence the classical worst-case bound is e/(e−1) ≈ 1.582 (Agrawal et al.).
Does the 4/3 bound hold for four variables (n=4)?
Yes. This paper proves that for every monotone submodular function and every marginal vector in [0,1]^4 the pairwise independent correlation gap is at most 4/3, and the bound is tight (attained by f(S)=min{|S|,1} with suitable marginals). For n≥5 a counterexample with gap 640/479 ≈ 1.336 > 4/3 exists, so n=4 is the last dimension where 4/3 holds.
What is the worst-case correlation gap under pairwise independence?
Asymptotically e/(e−1) ≈ 1.582, the same as under full mutual independence. The paper constructs a union coverage function on a ground set partitioned into m blocks (m growing sublinearly in n) with identical marginals 1/m whose gap tends to e/(e−1), so pairwise independence gives no worst-case improvement in high dimensions; the same holds for any t-wise independence with t ≥ 2.
Is the proof computer-assisted or AI-assisted?
Both. The n=4 proof verifies 2,745 linear-programming certificate systems computationally after automatic simplex subdivision (4,476 leaf certificates, depth up to 10), and the proof strategy was initially developed in a human-AI workflow using GPT 5.6 and 'Fable 5', as transparently disclosed by the author. Python code and per-orbit JSON certificate files are released on GitHub.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Mathematical notation is lossy in the extraction (fraction bars, subscripts and binomial coefficients are garbled in places, e.g., eq. (34) and Lemma 8's α_n), so fine-grained algebra was checked only where the rendering was unambiguous.
- The claimed GitHub repository (code and 183 JSON certificate files) could not be inspected from this review environment (no network); the reproducibility assessment relies on the paper's description of the artifacts.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.