Counterexample to a conjecture on the pairwise independent correlation gap using AI

Arjun Ramachandra; Karthik Natarajan

arxiv: 2606.19663 · v1 · pith:V35Q4FJUnew · submitted 2026-06-18 · 🧮 math.OC · math.PR

Counterexample to a conjecture on the pairwise independent correlation gap using AI

Arjun Ramachandra , Karthik Natarajan This is my paper

Pith reviewed 2026-06-26 16:48 UTC · model grok-4.3

classification 🧮 math.OC math.PR

keywords counterexamplepairwise independent correlation gapconjectureoperations researchAI-assisted discovery

0 comments

The pith

A counterexample disproves the conjecture on the pairwise independent correlation gap.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a counterexample to the conjecture on the pairwise independent correlation gap made by the same authors in their 2025 paper. Aided by GPT5.5 Pro, they identify an instance where the gap exceeds the conjectured bound. This matters because the gap describes performance differences between fully independent and pairwise independent distributions in optimization settings. If the conjecture held, it would have supplied a universal bound simplifying analysis of such problems. The counterexample shows the bound does not apply in general.

Core claim

Aided by the AI tool GPT5.5 Pro, we provide a counterexample to a conjecture made by Ramachandra and Natarajan (2025) on the pairwise independent correlation gap.

What carries the argument

The counterexample instance that violates the conjectured bound on the pairwise independent correlation gap.

If this is right

The conjectured upper bound on the pairwise independent correlation gap does not hold.
Any optimization bounds or algorithms derived from the conjecture require revision.
The actual supremum of the correlation gap under pairwise independence is strictly larger than previously conjectured.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

AI tools can help locate counterexamples to open conjectures in optimization theory.
New work is needed to determine the correct bound or to characterize when the gap achieves its maximum.
The same AI-assisted search approach could be tested on related open questions about correlation structures.

Load-bearing premise

The counterexample generated or identified with GPT5.5 Pro is mathematically valid and correctly falsifies the conjecture, with no errors in the AI-assisted construction or verification process.

What would settle it

Direct computation of the correlation gap value on the identified counterexample instance, confirming it exceeds the conjectured bound.

read the original abstract

Aided by the AI tool GPT5.5 Pro, we provide a counterexample to a conjecture made by Ramachandra and Natarajan (2025) [Pairwise independent correlation gap, Operations Research Letters, 107255, 6040].

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper announces an AI-assisted counterexample to the authors' own 2025 conjecture but supplies no construction or verification details.

read the letter

The paper reports that GPT5.5 Pro helped locate a counterexample to the Ramachandra-Natarajan conjecture on the pairwise independent correlation gap. If the instance is valid, it corrects their prior claim.

The work is new in the narrow sense that this specific counterexample did not appear before. The authors deserve credit for revisiting and overturning their own result rather than letting it stand.

The central weakness is the complete absence of supporting material. The abstract states the existence of the counterexample but gives no random variables, no check that they are pairwise independent, and no calculation showing the correlation gap exceeds the conjectured value. The stress-test note is correct: everything rests on unverified construction steps that could contain modeling or arithmetic errors introduced during the AI search. Without those steps or an independent certificate, the claim cannot be assessed.

This is for a small group of specialists working on correlation bounds in operations research. A reader already deep in that literature might want the explicit instance if it turns out to be correct.

I would not bring the paper to a reading group. I would not cite it. It does not deserve peer review until the authors supply the actual counterexample and the verification that it satisfies the required conditions.

Referee Report

2 major / 0 minor

Summary. The manuscript claims to provide a counterexample, discovered with the assistance of GPT5.5 Pro, to the conjecture of Ramachandra and Natarajan (2025) on the pairwise independent correlation gap.

Significance. A correctly constructed and verified counterexample would falsify the conjecture and be of interest to the community working on correlation gaps and optimization. The manuscript, however, contains no details on the instance, its construction, or verification, so the result cannot be assessed and no credit can be assigned for machine-checked proofs or reproducible code.

major comments (2)

[Abstract] Abstract: the claim that 'we provide a counterexample' is unsupported because the manuscript supplies neither the random variables, the joint distribution, nor any calculation showing pairwise independence together with a correlation gap strictly exceeding the conjectured bound.
[Full manuscript] The manuscript as a whole: no section, equation, table, or appendix presents the candidate instance, the verification that the variables are pairwise independent, or the numerical evaluation of the gap; the central claim therefore rests entirely on an unverified assertion.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their report. We agree that the submitted manuscript is extremely brief and contains no explicit details, instance, or verification of the claimed counterexample, which prevents assessment of the result.

read point-by-point responses

Referee: [Abstract] Abstract: the claim that 'we provide a counterexample' is unsupported because the manuscript supplies neither the random variables, the joint distribution, nor any calculation showing pairwise independence together with a correlation gap strictly exceeding the conjectured bound.

Authors: We agree that the abstract asserts the existence of a counterexample without any supporting material appearing in the manuscript. The current text is limited to a single sentence. We will revise the manuscript to include the specific random variables, joint distribution, verification of pairwise independence, and the numerical evaluation demonstrating that the correlation gap exceeds the conjectured bound. revision: yes
Referee: [Full manuscript] The manuscript as a whole: no section, equation, table, or appendix presents the candidate instance, the verification that the variables are pairwise independent, or the numerical evaluation of the gap; the central claim therefore rests entirely on an unverified assertion.

Authors: The referee correctly observes that the manuscript provides none of these elements and consists only of the bare claim. This leaves the result unverified. In revision we will add the required section or appendix containing the candidate instance discovered with GPT5.5 Pro, the pairwise-independence checks, and the gap calculation. revision: yes

Circularity Check

0 steps flagged

No circularity: counterexample stands as independent refutation

full rationale

The manuscript's central claim is the explicit construction of a counterexample that falsifies the authors' own 2025 conjecture. This does not reduce by definition or construction to the conjecture itself; the counterexample is offered as an external witness that violates the claimed bound. The single self-citation merely identifies the target conjecture and carries no load-bearing justification for the new result. No fitted-parameter predictions, self-definitional equalities, uniqueness theorems imported from prior work, or ansatz smuggling appear. The AI tool is described only as an aid to discovery, not as part of any mathematical reduction. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No information on free parameters, axioms, or invented entities is available from the abstract.

pith-pipeline@v0.9.1-grok · 5557 in / 914 out tokens · 35540 ms · 2026-06-26T16:48:23.444811+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

9 extracted references · 1 linked inside Pith

[1]

Abouzaid, A

M. Abouzaid, A. J. Blumberg, M. Hairer, J. Kileel, T. G. Kolda, P. D. Nelson, D. Spielman, N. Srivastava, R. Ward, S. Weinberger, L. Williams, First Proof, Preprint at http://arxiv.org/abs/2602.05192, 2026

arXiv 2026
[2]

Agrawal, Y

S. Agrawal, Y . Ding, A. Saberi and Y . Ye, Price of cor- relations in stochastic optimization, Operations Research, 60, no. 1, 150-162, 2012

2012
[3]

N. Alon, T. F. Bloom, W. T. Gowers, D. Litt, W. Sawin, A. Shankar, J. Tsimerman, V . Wang, M. M. Wood. Remarks on the disproof of the unit distance conjecture, Preprint at https://arxiv.org/abs/2605.20695, 2026

Pith/arXiv arXiv 2026
[4]

Bach, Learning with submodular functions: A convex optimization perspective, Foundations and Trends in Ma- chine Learning, 6, no.2-3, 145-373, 2013

F. Bach, Learning with submodular functions: A convex optimization perspective, Foundations and Trends in Ma- chine Learning, 6, no.2-3, 145-373, 2013

2013
[5]

Calinescu, C

G. Calinescu, C. Chekuri, M. Pál and J. V ondrák, Maxi- mizing a monotone submodular function subject to a ma- troid constraint, SIAM Journal on Computing, 40, no. 6, 1740-1766, 2011

2011
[6]

Chekuri, J V ondrák, R

C. Chekuri, J V ondrák, R. Zenklusen Submodular func- tion maximization via the multilinear relaxation and con- tention resolution schemes, SIAM Journal on Computing 43 (6), 1831-1879, 2014

2014
[7]

OpenAI, Planar point sets with many unit distances, Paper available at https://cdn.openai.com/pdf/74c24085-19b0- 4534-9c90-465b8e29ad73/unit-distance-proof.pdf, 2026

2026
[8]

Ramachandra and K

A. Ramachandra and K. Natarajan, Tight probability bounds with pairwise independence, SIAM Journal on Discrete Mathematics, 37, no. 2, 516-555, 2023

2023
[9]

Ramachandra and K

A. Ramachandra and K. Natarajan, Pairwise independent correlation gap, Operations Research Letters, 107255, 6040, 2025. 4

2025

[1] [1]

Abouzaid, A

M. Abouzaid, A. J. Blumberg, M. Hairer, J. Kileel, T. G. Kolda, P. D. Nelson, D. Spielman, N. Srivastava, R. Ward, S. Weinberger, L. Williams, First Proof, Preprint at http://arxiv.org/abs/2602.05192, 2026

arXiv 2026

[2] [2]

Agrawal, Y

S. Agrawal, Y . Ding, A. Saberi and Y . Ye, Price of cor- relations in stochastic optimization, Operations Research, 60, no. 1, 150-162, 2012

2012

[3] [3]

N. Alon, T. F. Bloom, W. T. Gowers, D. Litt, W. Sawin, A. Shankar, J. Tsimerman, V . Wang, M. M. Wood. Remarks on the disproof of the unit distance conjecture, Preprint at https://arxiv.org/abs/2605.20695, 2026

Pith/arXiv arXiv 2026

[4] [4]

Bach, Learning with submodular functions: A convex optimization perspective, Foundations and Trends in Ma- chine Learning, 6, no.2-3, 145-373, 2013

F. Bach, Learning with submodular functions: A convex optimization perspective, Foundations and Trends in Ma- chine Learning, 6, no.2-3, 145-373, 2013

2013

[5] [5]

Calinescu, C

G. Calinescu, C. Chekuri, M. Pál and J. V ondrák, Maxi- mizing a monotone submodular function subject to a ma- troid constraint, SIAM Journal on Computing, 40, no. 6, 1740-1766, 2011

2011

[6] [6]

Chekuri, J V ondrák, R

C. Chekuri, J V ondrák, R. Zenklusen Submodular func- tion maximization via the multilinear relaxation and con- tention resolution schemes, SIAM Journal on Computing 43 (6), 1831-1879, 2014

2014

[7] [7]

OpenAI, Planar point sets with many unit distances, Paper available at https://cdn.openai.com/pdf/74c24085-19b0- 4534-9c90-465b8e29ad73/unit-distance-proof.pdf, 2026

2026

[8] [8]

Ramachandra and K

A. Ramachandra and K. Natarajan, Tight probability bounds with pairwise independence, SIAM Journal on Discrete Mathematics, 37, no. 2, 516-555, 2023

2023

[9] [9]

Ramachandra and K

A. Ramachandra and K. Natarajan, Pairwise independent correlation gap, Operations Research Letters, 107255, 6040, 2025. 4

2025