Embedding edit distance into L1
From OpenAI Aftermath
Embedding edit distance into L1 asks how faithfully the edit distance between strings, the least number of single-symbol insertions, deletions and substitutions turning one string into another, can be represented by distances in the sequence space ℓ1. The measure is the least distortion E(d) of an injective map on all strings of length at most d. Ostrovsky and Rabani gave an upper bound of order eO(√(log d log log d)), while the best lower bound was of order log d. Three manuscripts in OpenAI's public mathematics collection (github.com/openai/math), dated 27 September 2026 and grouped as its result 099, claim that the Ostrovsky–Rabani exponent is sharp up to constant factors, with a Lean formalization of the matching bounds and of four lower-bound constructions. This page summarizes the published claims and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper is not presented here as independent verification.
Background
- As recounted in the introductions of the manuscripts:
- Levenshtein studied codes correcting insertions, deletions and substitutions, and Wagner and Fischer described edit scripts through increasing traces; because an insertion or deletion shifts a whole suffix, the distance depends on the best alignment of the two strings.
- Ostrovsky and Rabani proved the upper scale eO(√(log d log log d)) for binary strings of a fixed length by recursively comparing overlapping substrings, and noted extensions to larger alphabets and varying lengths.
- For lower bounds, Andoni, Deza, Gupta, Indyk and Raskhodnikova constructed binary sets with distortion approaching 3/2, Khot and Naor obtained order √(log d/log log d) through cuts and Fourier analysis of noisy shifts, and Krauthgamer and Rabani proved order log d for binary strings of length d.
The original result
- Claim. Theorem 1.1 of Edit Distance in ℓ1: Matching Bounds up to Constants in the Exponent states that there are absolute constants c, C > 0 such that for every sufficiently large d and every finite alphabet with at least two symbols, the least ℓ1 distortion of edit distance on the strings of length at most d, including the empty string, lies between ec√(log d log log d) and eC√(log d log log d). The lower bound is witnessed by binary strings of one common length at most d, and the constants do not depend on the alphabet. The manuscript states that only the order of the logarithm of the distortion is determined and that the constants in the exponent remain unspecified.
- The companion Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance states the same theorem with two further lower-bound constructions and a self-contained histogram embedding for the upper bound, realized by a deterministic finite-dimensional map. The companion Tree Constructions for the ℓ1 Distortion of Binary Edit Distance proves the binary lower bound in two further ways and combines it with the circle companion's upper embedding.
- Method, as described: in the main manuscript a word is a long list of rows, each holding tagged slots of lower-level words followed by a long marker of a fresh symbol. The lower-level words depend on states in several components, each cycled with a different prime period; advancing every component shifts the row list by one row and costs little, whereas advancing one distinguished component forces a cost in every alignment, since an alignment that spreads a payload over several rows skips disjoint markers. On the ℓ1 side a finite ℓ1 metric is written as a nonnegative sum of cut metrics, and each cut is expanded in Fourier characters; distinct prime periods prevent the phase of a character involving few components from being an integer, and characters involving many components are detected by the average of the single-component steps. Over k levels this gives distortion eΩ(k log k) at logarithmic word length O(k2 log k), and a delimiter code transfers the words to binary. The upper bound uses the Ostrovsky–Rabani theorem, extended by hashing the alphabet, padding to one binary length and averaging over the hash maps.
- Sources (openai/math repository, commit
7ef5c0c): Edit Distance in ℓ1: Matching Bounds up to Constants in the Exponent; Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance; Tree Constructions for the ℓ1 Distortion of Binary Edit Distance; all dated 27 September 2026. - Formalization, as described by the repository. The scope note lean/docs/099.md states that the formalization determines the exponential scale of the least ℓ1 distortion uniformly over finite alphabets, gives the two finite-circle lower constructions with their binary coding transfers and a finite histogram embedding for the upper bound, and gives the two tree lower constructions; the tree paper's constant-distortion binary conversion and the companion upper embedding theorem are outside the selected tree statements. It links four Comparator challenges: EditDistance.lean, FiniteCircle.lean, BinaryEditLower.lean and TreeEdit.lean.
- The tree manuscript notes that an embedding represents every pair of a domain at once, a different task from estimating the distance of one supplied pair, for which it cites the approximation scheme of the collection's result 121 (see Approximating edit distance in almost-linear time).
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 30 October 2026) |
|---|---|---|---|---|
| 2026-10-06 | Edit distance in L1: alignment obstructions and matching exponential scales, an article of the Latent Seminar blog at lowrank.github.io | Reading (exposition) | Explains edit distance and a common ℓ1 representation, the matching logarithmic scales, alignments and the split-row obstruction, cuts, frequencies and cheap shifts, the depth calculation with the binary transfer and the upper construction, with proof outlines on why split rows force disjoint losses in every alignment, the Fourier inequality for cut images, the different arithmetic problems of the companion hierarchies, binary codes that survive shifted matching and histograms that absorb alignment shifts. | Blog article; it states that its review covers statements, introductions and selected proof mechanisms and is not an independent verification of the complete proofs. |
| 2026-10-08 | MathVet (GitHub; review of openai/math, tables at repository commit 94c6630, 28 October 2026) |
Review (fidelity of the formal statements) | Rates this family "full" with no review note. As the definition to check it names the formalization's own distortion, the product of the two suprema of distance ratios, with the least distortion taken as an infimum over injective maps into ℓ1, which it calls the standard notion, with junk values only for sets of fewer than two points. It records a sandboxed Comparator pass for EditDistance, FiniteCircle, BinaryEditLower and TreeEdit. |
MathVet states that it does not claim any theorem false and reports what was machine-checked as stated. |
| 2026-10-10 | cert-machine, openai/math lane K: run 38019899278, EditDistance and TreeEdit; run 38017370880, BinaryEditLower; run 38051470892, FiniteCircle | Verification (two kernels) | Records that Lean's default kernel and the nanoda kernel accept all four solutions, in 446 s, 232 s, 234 s and 386 s. The project reports two-kernel certification of 398 of 416 challenges of the collection. | Repository. |
| 2026-10-10 to 2026-10-14 | con-leche development journal (task #348) | Verification (second kernel) | In its run over all Comparator challenges of the collection at commit fd4aeeb, the journal's table of exceptions (time-outs, memory, errors) lists none of the four challenges, so all were accepted by con-leche and by Lean's official kernel. |
Development journal. |
| 2026-10-14 | AI Proved What?, episode 099 Sharp at last?, remade version of 26 October 2026 | Reading (exposition) | Video explainer of the claims and their history. The episode states that only the exponent is determined, so that the distortion itself could still change by a factor growing with d, that nothing is claimed about computing the embedding quickly, and that the main paper takes the Ostrovsky–Rabani fixed-length theorem as an input. It reports that the Lean proof of the two-sided bound proves its own histogram upper embedding instead of citing Ostrovsky and Rabani and fixes the constants at c = 1/1200 and C = 32 beyond a threshold that it does not compute. | Web page and video; the site states that its scripts and animations are produced with AI assistance and that the narration is an AI-generated voice. Status record last checked 27 October 2026: posted as preprints: OpenAI, three preprints dated September 27, 2026, released October 6; under expert review: not yet; peer reviewed: not yet; checked in Lean: OpenAI published Lean proofs of the two-sided bound and the four further lower-bound constructions, which the site states it has not run. The page states that it found no unproved steps and has seen no expert review. |
Notes
- The background summarizes the manuscripts' own account of earlier work.
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.
