Browse › Convex and metric geometry › 099 The sharp exponential scale of edit-distance distortion
Edit Distance in l1: Matching Bounds up to Constants in the Exponent
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 determine the exponential scale of the least ℓ1 distortion of unit-cost edit distance on all strings of length at most d. For every sufficiently large d, uniformly over finite alphabets of size at least two, the distortion lies between $\exp(c\sqrt{\log d\,\log\log d})$ and $\exp(C\sqrt{\log d\,\log\log d})$ for absolute constants $c,C\gt 0$. The lower bound already holds on binary strings of one common length. Thus the order of logarithmic distortion is sharp up to absolute constants.
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 a comparator statement (EditDistance.lean) for the matching exponential-scale bounds of Theorem 1.1, uniformly over finite alphabets, with a lower-bound witness of binary words of one common length. [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 (strings without repeated symbols), a comparison point for the claim that the constants hold even for alphabets growing with d.
- A. Andoni and K. Onak, Approximating Edit Distance in Near-Linear Time (arXiv:1109.5635, 2011). Gives a near-linear-time 2^{Õ(√log n)} approximation for edit distance; relevant to the paper's remark that its existential upper bound places no restriction on the cost of computing the map.
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
- VibeMathed: Problem record
- Emergent Mind: family 099
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Edit-Distance-in-l1-Matching-Bounds-up-to-Constants-in-the-Exponent-September-27-2026,
author = {{OpenAI}},
title = {{Edit Distance in $\ell_1$: Matching Bounds up to Constants in the Exponent}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Edit-Distance-in-l1-Matching-Bounds-up-to-Constants-in-the-Exponent-September-27-2026/paper.pdf}{OAI:Edit-Distance-in-l1-Matching-Bounds-up-to-Constants-in-the-Exponent-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:
- Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance · September 27, 2026
- Tree Constructions for the l1 Distortion of Binary Edit Distance · September 27, 2026