VibeMathedMath problems solved with AI
Sign in

The least distortion of embedding edit distance into l1

Let EΣ(d)E_\Sigma(d) be the least distortion of an embedding into ℓ1\ell_1 of the strings of length at most dd over an alphabet Σ\Sigma, with unit-cost edit distance (insertions, deletions, substitutions). Ostrovsky and Rabani (2007) embedded binary strings with distortion exp⁡(O(log⁡dlog⁡log⁡d))\exp(O(\sqrt{\log d\log\log d})). Lower bounds rose from 3/23/2 (Andoni-Deza-Gupta-Indyk-Raskhodnikova 2003) to (log⁡d)1/2−o(1)(\log d)^{1/2-o(1)} (Khot-Naor 2006) and Ω(log⁡d)\Omega(\log d) (Krauthgamer-Rabani 2009), leaving an exponential gap. What is the order of growth of EΣ(d)E_\Sigma(d); in particular, is the Ostrovsky-Rabani bound exp⁡(O(log⁡dlog⁡log⁡d))\exp(O(\sqrt{\log d\log\log d})) optimal?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Argument
Field
Metric embeddings; edit distance
Posed by
Open since the Ostrovsky-Rabani upper bound (J. ACM 2007) and the Krauthgamer-Rabani lower bound (2009); the manuscripts cite no explicit statement of the question
Year posed
—
Years open
—
Solved
2026-09-27
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
32 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: there are absolute c,C>0c,C>0 and d0d_0 with exp⁡(clog⁡dlog⁡log⁡d)≤EΣ(d)≤exp⁡(Clog⁡dlog⁡log⁡d)\exp(c\sqrt{\log d\log\log d})\le E_\Sigma(d)\le\exp(C\sqrt{\log d\log\log d}) for all d≥d0d\ge d_0 and all finite ∣Σ∣≥2|\Sigma|\ge2, so the Ostrovsky-Rabani scale is sharp up to constants in the exponent. The upper bound is Ostrovsky-Rabani's method made uniform over alphabets and lengths; the new content is the matching lower bound, given by three constructions across the family. The constants c,Cc,C are not determined, and nothing is said about computational efficiency.

What the AI did

The release README says every result in openai/math was produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result. This result is not one of the README's two 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 companion manuscripts of the same date giving independent finite-circle and tree constructions for the lower bound and a uniform histogram embedding for the upper bound.

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1.1 was read against the question: absolute c,Cc,C with exp⁡(clog⁡dlog⁡log⁡d)≤EΣ(d)≤exp⁡(Clog⁡dlog⁡log⁡d)\exp(c\sqrt{\log d\log\log d})\le E_\Sigma(d)\le\exp(C\sqrt{\log d\log\log d}) for all large dd, uniformly over finite alphabets of size at least two, the lower bound witnessed by binary strings of one length. The challenge is not in lean/formalization.yaml; lean/ComparatorChallenges/EditDistance.json exists with solution_module OAI.Combinatorics.EditDistance.Main, whose file exists at the pinned commit. The statement EditDistance.lean was read here; not rebuilt here. It defines edit distance by unrestricted unit-step scripts with substitutions, distortion as the product of the two extreme ratios over injective maps into ℓ1(N)\ell^1(\mathbb N), and states the two-sided bounds for every finite alphabet type, the binary witness and the alphabet supremum. This states the headline. Permitted axioms: propext, Quot.sound, Classical.choice.

Sources

Changelog1 change

Discussion