Browse › Convex and metric geometry › 099 The sharp exponential scale of edit-distance distortion
Tree Constructions for the l1 Distortion of Binary Edit Distance
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We give two independent constructions of binary words of one length at most d whose ordinary edit-distance metrics require ℓ1 distortion $\exp(\Omega(\sqrt{\log d\,\log\log d}))$ for every sufficiently large d. We also prove a constant-distortion binary conversion for one prescribed input length. Together with the companion upper embedding theorem, these lower bounds determine the order of logarithmic distortion uniformly over finite alphabets with at least two symbols.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI, The sharp exponential scale of edit-distance distortion: Lean scope note (OpenAI Math release, lean/docs/099.md, 2026). The release's scope note lists comparator statements (BinaryEditLower.lean, TreeEdit.lean) for the two binary lower-bound constructions of Theorem 1.1, and states that the paper's constant-distortion binary conversion and the companion upper embedding theorem are outside the selected statements. [family-level]
Possibly relevant literature (found by the agent, not checked)
- M. Charikar and R. Krauthgamer, Embedding the Ulam metric into ℓ1 (Theory of Computing 2, Article 11, 2006). Proves O(log n) ℓ1 distortion for edit distance on permutations, a comparison point for the binary lower bound and for the appendix's alphabet conversion of words over at most M letters.
Digests and expositions
- Latent Seminar, Edit distance in L1: alignment obstructions and matching exponential scales (6 October 2026). This exposition compares the three manuscripts' alignment obstructions, Fourier arguments, binary transfers, and upper embeddings, explicitly stating that it does not independently verify the complete proofs. [family-level]
Elsewhere
- Emergent Mind: family 099
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Tree-Constructions-for-the-l1-Distortion-of-Binary-Edit-Distance-September-27-2026,
author = {{OpenAI}},
title = {{Tree Constructions for the $\ell_1$ Distortion of Binary Edit Distance}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Tree-Constructions-for-the-l1-Distortion-of-Binary-Edit-Distance-September-27-2026/paper.pdf}{OAI:Tree-Constructions-for-the-l1-Distortion-of-Binary-Edit-Distance-September-27-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/099.md. The Lean statements have not been checked by people against the paper's claims.
Family 099: The sharp exponential scale of edit-distance distortion
Determines the least distortion of embedding edit distance on words of length at most d into real ℓ1: it is $\exp(\Theta(\sqrt{\log d\,\log\log d}))$. Insertions, deletions and substitutions have unit cost. The constants are uniform over all finite alphabets with at least two symbols, even when the alphabet grows with d; binary words already force the lower bound.
Other papers in this family:
- Edit Distance in l1: Matching Bounds up to Constants in the Exponent · September 27, 2026
- Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance · September 27, 2026