The sharp exponential scale of edit-distance distortion

1 · The essentials

How faithfully can differences between words be represented by distances between lists of real numbers? Here, the difference between two words is the fewest single-symbol insertions, deletions, and substitutions needed to turn one into the other, each costing one. The distance between two lists is the sum of the absolute differences between their corresponding entries. The result identifies how much the relative distances must change, even with the best possible representation. For words of length at most $d$ , the necessary change grows on the scale $exp (Θ (lo g d lo g lo g d))$ , where the notation allows fixed positive constants in the exponent. The bounds apply for sufficiently large length limits and use the same constants for every finite alphabet with at least two symbols, even if its size grows with the length limit. Words using just two symbols, all of one common length, already force the lower bound.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine replacing every word with a shopping list of numerical quantities and measuring differences by adding up the absolute changes in those quantities. You want those totals to track how many edits separate the words, but some relative stretching is unavoidable; these results bound the smallest possible worst-case stretching.

Why it matters

The matching bounds settle the exponential scale of the best possible representation, rather than merely describing one construction. They also separate two aspects of the problem: a two-symbol alphabet already contains the obstruction, while the upper bound handles every finite alphabet without changing the constants.

2 · Going further

Let the domain consist of all words of length at most $d$ over a finite alphabet with at least two symbols, equipped with unit-cost edit distance. The target is real $ℓ_{1}$ , where distance is the sum of absolute coordinate differences. Distortion measures the multiplicative spread in how an embedding changes distances, after allowing an overall rescaling. The main manuscript gives absolute constants $c, C > 0$ such that, for every sufficiently large $d$ , the least distortion lies between $exp (c lo g d lo g lo g d)$ and $exp (C lo g d lo g lo g d)$ . Thus the logarithm of the least distortion is determined up to absolute constant factors, not necessarily the distortion itself up to a constant factor.

The companion manuscript on finite circles supplies two constructions of binary words that force the lower-bound scale. Both yield words of one common length for every sufficiently large length cap. It also describes two direct binary coding arguments that transfer the constructions with absolute distortion and logarithmic block width. On the upper-bound side, it develops the overlapping-substring method of Ostrovsky and Rabani into a complete finite histogram embedding at the same exponential scale. That embedding covers all words of length at most $d$ , including the empty word, uniformly over finite alphabets.

The tree-construction companion supplies two independent constructions of binary words of a single length at most $d$ with the same lower-bound scale. A constant-distortion binary conversion for one prescribed input length is also shown in that manuscript. Together with the companion upper embedding theorem, these constructions give the stated order of logarithmic distortion. The abstracts identify these construction methods but do not provide the detailed estimates behind them.

Useful notions

Words over a finite alphabet
Unit-cost edit distance
Distances defined by sums of absolute differences
Multiplicative distortion and rescaling
Logarithms and exponential growth

What was known before / what is new

Before

The source identifies an overlapping-substring method of Ostrovsky and Rabani as the method developed in the histogram-embedding companion. It does not specify earlier quantitative bounds or give a broader history of the problem.

New

The main result gives matching upper and lower exponential scales, with absolute constants uniform over finite alphabets of size at least two. Binary words of a common length already force the lower bound. The companions supply finite-circle and tree constructions for the lower bounds, binary conversion arguments, and a finite histogram embedding for the upper bound.

Limits and assumptions

The bounds concern sufficiently large $d$ , finite alphabets with at least two symbols, and insertions, deletions, and substitutions each assigned cost one. They determine the logarithm of the least distortion up to absolute constants, not exact constants in the exponent. The main result has a Lean formalization, but the supplied material does not specify its detailed scope, so formal verification should not be attributed to every companion construction or auxiliary claim. The source does not identify further open problems.

Mini glossary

Edit distance: The minimum number of single-symbol insertions, deletions, and substitutions required to transform one word into another when each operation costs one.
Real ℓ1: A space of real coordinates in which distance is the sum of the absolute coordinate differences.
Embedding: A representation of the words as points in another space whose distances are compared with the original edit distances.
Distortion: The multiplicative spread between the largest and smallest distance-change factors of an embedding, independent of overall rescaling.
Absolute constants: Fixed constants that do not depend on the length cap or the finite alphabet.
Binary words: Words formed from an alphabet containing two symbols.

Keywords : Edit distance · ℓ1 distortion · Binary constructions

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

Determines the least distortion of embedding edit distance on words of length at most d into real ℓ₁: it is $exp (Θ (lo g d lo g lo g 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.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/099.md

Manuscripts in this family

★

Edit Distance in l1: Matching Bounds up to Constants in the Exponent

27/09/2026

To be verified

We determine the exponential scale of the least ℓ₁ 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 lo g d lo g lo g d)$ and $exp (C lo g d lo g lo g d)$ for absolute constants $c, C > 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.

PDF GitHub folder

Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance

27/09/2026

To be verified

We give two finite-circle constructions of binary strings whose least ℓ₁ distortion is $exp (Ω (lo g d lo g lo g d))$ , where d bounds their length. Both constructions supply words of one common length for every sufficiently large cap. Two direct binary coding arguments transfer the constructions with absolute distortion and logarithmic block width. We also develop the overlapping-substring method of Ostrovsky and Rabani into a complete finite histogram embedding at the same exponential scale, uniformly over all finite alphabets and all words of length at most d, including the empty word.

PDF GitHub folder

Tree Constructions for the l1 Distortion of Binary Edit Distance

27/09/2026

To be verified

We give two independent constructions of binary words of one length at most d whose ordinary edit-distance metrics require ℓ₁ distortion $exp (Ω (lo g d lo g lo g 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.

PDF GitHub folder