VibeMathedMath problems solved with AI
Sign in

The Goemans-Linial integrality gap for uniform sparsest cut is nearly square-root logarithmic

The Goemans-Linial relaxation of uniform sparsest cut minimizes ∑i<jcijd(i,j)\sum_{i<j}c_{ij}d(i,j) over negative-type semimetrics dd with ∑i<jd(i,j)=1\sum_{i<j}d(i,j)=1. Arora, Rao and Vazirani showed its integrality gap with uniform demands is O(log⁡n)O(\sqrt{\log n}). Devanur, Khot, Saket and Vishnoi refuted the conjecture that the uniform gap is bounded, with an Ω(log⁡log⁡n)\Omega(\log\log n) lower bound, and Kane and Meka raised it to exp⁡(Ω(log⁡log⁡n))\exp(\Omega(\sqrt{\log\log n})). For general demands the gap is Θ(log⁡n)\Theta(\sqrt{\log n}) up to lower-order factors (Naor-Young, Chang-Naor-Ren), but those constructions have constant average distortion and give nothing for uniform demands. What is the order of growth of the Goemans-Linial integrality gap for uniform sparsest cut, and does it reach log⁡n\sqrt{\log n}?

Result
Proved(see note)
Status
Partial result
AI contribution
AI-discovered
Method
Construction
Field
Approximation algorithms; semidefinite relaxations and metric embeddings
Posed by
Open after Arora, Rao and Vazirani (2004) and Devanur, Khot, Saket and Vishnoi (2006); see also Kane and Meka (2013)
Year posed
—
Years open
—
Solved
2026-09-24
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
28 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: there are an absolute c>0c>0 and uniform-demand instances on nj→∞n_j\to\infty vertices with Goemans-Linial integrality gap at least clog⁡nj/(log⁡log⁡nj)3c\sqrt{\log n_j}/(\log\log n_j)^3. This improves the Kane-Meka bound exp⁡(Ω(log⁡log⁡n))\exp(\Omega(\sqrt{\log\log n})) to within (log⁡log⁡n)3(\log\log n)^3 of the ARV upper bound. It is an existential sequence of sizes, not a bound at every nn; it does not determine whether the gap is exactly Θ(log⁡n)\Theta(\sqrt{\log n}), and it concerns the basic SDP, not Sherali-Adams or Lasserre strengthenings.

What the AI did

The release README says the results were produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored 'OpenAI' and names no human author. The family has two manuscripts dated September 24, 2026: this integrality-gap construction and a separate NP-hardness reduction (its own entry). This manuscript is the formalised one.

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1.1 was read against the question; it gives OPT/GL≥clog⁡n/(log⁡log⁡n)3\mathrm{OPT}/\mathrm{GL}\ge c\sqrt{\log n}/(\log\log n)^3 along a sequence n→∞n\to\infty, which matches ARV up to a power of log⁡log⁡n\log\log n but does not settle the exact order. lean/formalization.yaml lists a main result for this manuscript (comparator UniformSparsestCut, declaration OAI.UniformSparsestCut.mainGap). The comparator statement was read here: it asserts an absolute c>0c>0 and instances on nj→∞n_j\to\infty vertices with symmetric nonnegative capacities, positive Goemans-Linial value (negative-type distances realised in Rn\mathbb R^n with all triangle inequalities, normalised to total 1) and clog⁡nj/(log⁡log⁡nj)3≤OPT/GLc\sqrt{\log n_j}/(\log\log n_j)^3\le\mathrm{OPT}/\mathrm{GL} eventually, where OPT uses the denominator ∣B∣(n−∣B∣)|B|(n-|B|). That is the headline claim. Not rebuilt here. Permitted axioms: propext, Quot.sound, Classical.choice.

Sources

Changelog1 change

Discussion