The sharp exponential scale of edit-distance distortion

Edit distance between words can be drawn as ℓ1 distance only with distortion of size exp(√(log d·log log d)).

3 papers September 27, 2026 Explained by AI

Edit distance counts the fewest single-symbol insertions, deletions and substitutions that turn one word into another. A long-standing question asks how faithfully these distances can be copied by simple coordinate distances (ℓ1). Maps found in 2007 lose a factor near exp(√(log d · log log d)) for words of length d. The best lower bound before was only of order log d. These papers prove the 2007 scale is right, up to fixed constants in the exponent (Lean proof listed).

First step

2003

Andoni, Deza, Gupta, Indyk and Raskhodnikova, lower bound approaching 3/2

Significance

Major

It matches the 2007 upper bound up to exponent constants; the best earlier lower bound was of order log d.

Trust

Formal proof listed

Field

Convex and metric geometry

3 papers

The explanation

Take the eight-symbol word 01010101 and shift it one place to get 10101010. All eight positions now hold different symbols. Yet two edits turn one word into the other. Delete the first 0, then add a 0 at the end. The edit distance between two words is the fewest single-symbol insertions, deletions and substitutions that turn one into the other. Each edit costs one. Here it is 2.

Now try to file words as points, so that distances between points stand in for edit distances. The natural first attempt lists each word's symbols as coordinates. The distance between two lists is then the sum of the coordinate gaps, called the ℓ1 distance. For words of one length, this counts the positions that disagree. For our pair it gives 8, while the edit distance is 2. So this map stretches that pair four times. A check of all 256 binary words of length 8 finds no pair stretched more than four times. None is shrunk. Longer alternating words do worse: at length n the stretch is n/2.

The worst stretch, times the worst shrink, is the map's distortion. A map with distortion 1 keeps every distance exactly, up to one common scale. The question is how low the distortion can go. Fix a cap d and take every word of length at most d, including the empty word. Let E(d) be the least distortion of any map of all these words into ℓ1. The map may use any number of coordinates and need not be easy to compute.

The upper side has been known since 2007. Rafail Ostrovsky and Yuval Rabani built maps for binary words of one fixed length. Their distortion grows like exp(√(log d · log log d)), up to a constant in the exponent. The logarithms are natural ones. Lower bounds stayed far below this. Alexandr Andoni and four coauthors found binary word sets needing distortion close to 3/2 in 2003. Subhash Khot and Assaf Naor reached roughly the square root of log d in 2006. Robert Krauthgamer and Rabani reached order log d in 2009.

The gap is large. At d equal to one million, log d is about 13.8. The expression exp(√(log d · log log d)) is about 413. Multiply d by 1,000, and log d only grows to about 20.7. The expression grows about 6.7 times, to about 2,768. Meanwhile, log d itself grew only 1.5 times.

These three papers prove that the upper scale is the truth (Lean proof listed). There are fixed numbers c and C above zero with the following property. For every large cap d, E(d) sits between exp(c√(log d · log log d)) and exp(C√(log d · log log d))Source 1. The same constants work for every finite alphabet with at least two symbols. They work even when the alphabet grows with dSource 2. Binary words that all share one length already force the lower boundSource 3.

Read the statement carefully. It pins down log E(d) within a constant factor, not E(d) itselfSource 4. The paper does not say what c and C are, and they need not agreeSource 5. At d equal to one million, it only places E(d) between 413 to the power c and 413 to the power C. What it does settle is the growth law. E(d) grows faster than every fixed power of log d, yet more slowly than every fixed power of dSource 6.

The obstacle was the cheap shift from the first example. A hard word set needs one change that every alignment must pay for. But an alignment may match symbols across the boundaries used to build the words, and hide the changeSource 7. The papers build words from long lists of rows, each ending in a marker of a fresh symbolSource 8. A row whose matches spill into several rows must skip a whole marker. The skipped stretches for different rows never overlap, so the cost adds upSource 9. Shifts with different prime periods then make some change expensive at every levelSource 10. The three papers give five independent lower-bound constructions along these linesSource 11 Source 12.

How sure is this? A computer proof checker called Lean has checked formal versions of the two-sided theorem. The Lean scope note also lists the circle and tree lower bounds and the uniform upper map. Each has a Comparator statement, a fixed reference statement the proof must match. For the tree paper, the note selects only its lower bounds. That paper's constant-factor binary conversion lies outside the checkSource 13. No specialist review has been published.

What it doesn't show. This does not give the constants in the exponent or the best map for any particular length.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Major if the proofs hold. Lean checks formal versions of the main two-sided theorem and the lower-bound constructions. The constants in the exponent remain unknown, and no specialist review is published.

Words used

Edit distance: The fewest single-symbol insertions, deletions and substitutions that turn one word into another.
Binary word: A word written with only two symbols, such as 0 and 1.
ℓ1 distance: The distance between two lists of numbers found by adding up the gaps between matching entries.
Embedding: A map that files each word as a point, so that point distances stand in for word distances.
Distortion: How badly an embedding misrepresents distances: the worst stretch times the worst shrink.
Alignment: A way of matching symbols of one word to symbols of another, in order, that an edit script implicitly uses.
Comparator: A tool that checks a Lean proof proves exactly a fixed reference statement.

The original papers (3)

Edit Distance in l1: Matching Bounds up to Constants in the Exponent (PDF, opens in a new tab)
September 27, 2026
Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance (PDF, opens in a new tab)
September 27, 2026
Tree Constructions for the l1 Distortion of Binary Edit Distance (PDF, opens in a new tab)
September 27, 2026

Lean notes

All quoted lines (13)

There are absolute constants $c,C>0$ and an integer $d_0$ such that, for every integer $d\ge d_0$ and every finite alphabet $\Sigma$ with $|\Sigma|\ge2$ , $\exp\!\bigl(c\sqrt{\log d\,\log\log d}\bigr) \le E_\Sigma(d)\le \exp\!\bigl(C\sqrt{\log d\,\log\log d}\bigr).$
Edit Distance in l1: Matching Bounds up to Constants in the Exponent Back to text
The constants and threshold in the theorem are independent of the alphabet, including when its size grows with $d$ .
Edit Distance in l1: Matching Bounds up to Constants in the Exponent Back to text
The lower bound is witnessed by a subset of binary strings of one common length at most $d$ .
Edit Distance in l1: Matching Bounds up to Constants in the Exponent Back to text
The conclusion determines the order of $\log E_\Sigma(d)$ ; the constants in the exponent remain unspecified.
Edit Distance in l1: Matching Bounds up to Constants in the Exponent Back to text
Equation (…) determines the order of $\log E_\Sigma(d)$ ; the constants in its two exponents need not agree.
Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance Back to text
Those constraints force large total leaf frequency and yield the exponent in (…). The resulting lower bound grows faster than every fixed power of $\log d$ , while remaining $d^{o(1)}$ .
Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance Back to text
A lower bound must therefore control arbitrary increasing matchings, even when they cross many of the boundaries used to construct the words.
Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance Back to text
In that event, the matching skips a complete target marker: the source payload contains no copy of the marker symbol.
Edit Distance in l1: Matching Bounds up to Constants in the Exponent Back to text
The skipped markers for different payloads are disjoint.
Edit Distance in l1: Matching Bounds up to Constants in the Exponent Back to text
In each component, repeatedly adding one distinguished step cycles the state with a prime period; different components use different primes.
Edit Distance in l1: Matching Bounds up to Constants in the Exponent Back to text
Each of our two lower constructions supplies a binary subset whose words have one common length at most $d$ and whose least $\ell_1$ distortion satisfies the lower bound.
Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance Back to text
We prove the following lower bound in two independent ways.
Tree Constructions for the l1 Distortion of Binary Edit Distance Back to text
Appendix … proves a stronger, separate alphabet-conversion theorem: for words of one prescribed length $M$ over at most $M$ letters, blocks of width $M^2$ preserve edit distance up to scale and an absolute factor $804$ .
Tree Constructions for the l1 Distortion of Binary Edit Distance Back to text