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

Introduction

We study how faithfully distances between strings can be represented by distances in $\ell_1$. The distance on strings is ordinary edit distance: $\operatorname{ED}(x,y)$ is the least number of single-symbol insertions, deletions and substitutions that transform $x$ into $y$, with every operation costing one. An insertion or deletion changes the positions of an entire suffix. As a result, the distance depends on the best alignment of the two strings, and a useful representation must account for alignments over all scales.

For a finite alphabet $\Sigma$ and an integer $d \ge1$, let $\Sigma^{\le d}$ be the set of all strings of length at most $d$, including the empty string. The cap restricts the endpoints; intermediate strings in an edit script may have any length. Write $\ell_1$ for the real space of absolutely summable sequences and define

The infimum is over injective maps. It imposes no restriction on target dimension or on the cost of computing the map. Equivalently, an embedding has distortion at most $D$ when it can be rescaled so that every image distance lies between $\operatorname{ED}(x,y)/D$ and $\operatorname{ED}(x,y)$.

Theorem 1.1. 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$,

The lower bound is witnessed by a subset of binary strings of one common length at most $d$. The same bounds hold for $\sup_{2\le|\Sigma|<\infty}E_\Sigma(d)$.

Logarithms are natural unless a base is specified. The constants and threshold in the theorem are independent of the alphabet, including when its size grows with $d$. The conclusion determines the order of $\log E_\Sigma(d)$; the constants in the exponent remain unspecified.

The earlier bounds

The single-symbol error model is classical. Levenshtein studied codes correcting insertions, deletions and substitutions [4], and Wagner and Fischer described edit scripts through increasing traces [10]. Their alignment language will be useful below: any lower bound must control every increasing matching of equal symbols, including matchings that cross the boundaries used to construct the strings.

Ostrovsky and Rabani [8] proved the upper scale in Theorem 1.1 for fixed-length binary strings by recursively comparing collections of overlapping substrings. They also noted extensions to larger alphabets and varying lengths. We use their fixed-length theorem and give complete reductions with constants uniform over all finite alphabets and with the empty string included.

For lower bounds, Andoni, Deza, Gupta, Indyk and Raskhodnikova [1] constructed binary subsets whose $L_1$ distortion approaches 3/2. Khot and Naor [2] obtained an $\Omega(\sqrt{\log d}/\log\log d)$ lower bound by studying cuts and Fourier analysis of noisy shifts. Their insertion–deletion metric is within a factor of two of the convention used here. Krauthgamer and Rabani [3] then proved an $\Omega(\log d)$ lower bound for binary strings of length $d$. The construction below reaches the scale of the Ostrovsky–Rabani exponent.

How the lower bound works

The construction joins a geometric fact about strings to an analytic fact about $\ell_1$. At the geometric level, a word is a long list of rows. Each row contains a payload made of lower-level words, followed by a long marker consisting of a fresh symbol. The payload has fixed slots; each slot has its own alphabet tag, so different slots cannot match. The lower-level words depend on states. In each component, repeatedly adding one distinguished step cycles the state with a prime period; different components use different primes. Advancing every component by one state step shifts the row list by one, which costs only the deletion and insertion of one row.

Advancing the distinguished component behaves differently. We repeat that component in many separately tagged slots. For any proposed pair of rows, either those repeated slots remain separated or the row shift that aligns them leaves many of the other prime-period components separated. A global alignment can still send one source payload into several target rows. In that event, the matching skips a complete target marker: the source payload contains no copy of the marker symbol. The skipped markers for different payloads are disjoint. This turns the row comparison into a lower bound for arbitrary alignments.

The analytic comparison concerns the average image distance produced by a group displacement. Proposition 2.2 bounds the displacement in the distinguished component by the simultaneous step and the average component steps. The proof expresses a finite $\ell_1$ metric as a nonnegative sum of cut metrics, then expands each cut in Fourier characters. A character involving few components is detected by the simultaneous step: distinct prime denominators prevent its phase from being an integer. A character involving many components is detected by the sum of the component averages.

Relative to word length, the guaranteed pointwise separation decreases by a fixed factor at each level. Under the same normalization, the analytic inequality forces the allowed averaged image displacement to decrease much faster: after $k$ levels, the ratio between these two bounds is $\exp(\Omega(k\log k))$. Meanwhile, the logarithmic word length is $O(k^2\log k)$. A delimiter code transfers the words to binary with a loss polynomial in $k$, and choosing $k$ directly from the cap $d$ supplies a witness for every sufficiently large $d$.

Section 2 proves the alignment facts and the prime-product displacement inequality. Section 3 builds the words and proves their separation and analytic recurrence together. Section 4 supplies the delimiter at the binary transfer and completes the parameter calculation. Section 5 derives the uniform upper bound by hashing the alphabet, padding to one binary length, and averaging over all hash maps.

The companion manuscripts on circle constructions [6] and tree constructions [7] give independent lower-bound mechanisms and additional binary coding results. No result from a companion manuscript is used; the upper bound uses the stated external theorem.

Alignments and a displacement inequality

The word construction will be measured first by insertion–deletion distance. Its advantage is that every possible comparison has a concrete description as an increasing matching. We then state the analytic inequality that will be applied at each level of the construction.

Distances from increasing matchings

Write $\Delta(x,y)$ for the minimum number of single-symbol insertions and deletions transforming $x$ into $y$. An increasing matching is a list of pairs of equal-symbol positions, strictly increasing in both coordinates. Let $\operatorname{LCS}(x,y)$ be its maximum size. These are the classical trace and subsequence descriptions of string correction [10].

Lemma 2.1. For arbitrary finite strings, including the empty string,

For two strings of the same length $n$, define their one-sided deficit by

A matching of size $n-E$ leaves exactly $E$ unmatched positions on each side.

Proof. An insertion–deletion script is an edit script, and replacing each substitution by one deletion and one insertion proves the two inequalities. Deleting the unmatched source positions in an increasing matching and inserting the unmatched target positions realizes its total loss $\lvert x\rvert+ \lvert y\rvert- 2\lvert M\rvert$. Conversely, the original positions that survive an insertion–deletion script form an increasing matching; its loss is at most the number of operations. Minimizing the loss gives the identity. The equal-length assertions follow directly.

The comparison to be proved

For a finite abelian group $G$ and a map $H:G \to\ell_1$, set

Every expectation over a finite set uses the uniform probability measure. The following proposition compares a shift in one component with a simultaneous shift and with shifts averaged inside the separate components. In the word construction, the simultaneous shift will move the row list by one; the component averages will be bounded at the preceding level.

Proposition 2.2 (Prime-product displacement inequality). Let $b,h \ge1$ be integers, let $P \ge1$, and let $G_1,\ldots,G_b$ be finite abelian groups. Suppose $v_j \in G_j$ has order $p_j$, where $p_1,\ldots,p_b$ are distinct primes in $[P,2P]$. In $G=\prod_{j=1}^{b}G_j$, use the same notation $v_j$ for the element acting only in coordinate $j$, and put $\tau=\sum_{j=1}^{b}v_j$. Then every $H:G\to\ell_1$ and every integer $u$ satisfy

We prove the proposition after recording two elementary forms of the cut and Fourier methods. The cut representation is standard [5], Section 4. Its summability statement below permits an unrestricted sequence-space target.

Lemma 2.3 (Finite cut decomposition). Let $X$ be finite and $H:X\to\ell_1$. There are finite numbers $c_A\ge0$, indexed by the nonempty proper subsets of $X$, such that

Moreover,

where the right sum is over unordered pairs.

Proof. For $\lvert X\rvert\le1$ all the sums are empty. Otherwise, for coordinate $n$ of $H$, list its distinct values on $X$ as $t_{n,1}<\cdots<t_{n,k_n}$. Put

The consecutive gaps telescope:

Group all terms with the same cut by setting $c_A=\sum_{n,r:A_{n,r}=A}a_{n,r}$, initially allowing the value $+\infty$. Nonnegativity allows the coordinate series to be interchanged with the finite sum over unordered pairs. Hence

Each indexed cut separates at least one pair, so $\lvert A\rvert\lvert X\setminus A\rvert\ge1$. The displayed equality proves that all the weights are finite and bounds their total. Summing the coordinate identity and grouping its nonnegative terms now gives (2.4). $\square$

Lemma 2.4 (Finite Fourier displacement identity). Let $T=\prod_{j=1}^{b}\mathbb{Z}/p_j\mathbb{Z}$, where the integers $p_j$ are at least two. For $\lambda\in T$, set

For every $F:T\to\mathbb{C}$ and $l\in T$,

The squared sine is independent of the chosen integer representatives.

Proof. The geometric-series identity

shows, coordinate by coordinate, that the $\lvert T\rvert$ characters are orthonormal for the inner product $\langle F_1,F_2\rangle=\mathbb{E}_tF_1(t)\overline{F_2(t)}$. They form a basis because the function space has dimension $\lvert T\rvert$. Thus $F(t)=\sum_{\lambda}\widehat{F}(\lambda)\chi_\lambda(t)$, and the squared norm equals the sum of squared Fourier coefficients. Apply this to

and use $\lvert e^{2\pi i\theta}-1\rvert^2=4\sin^2(\pi\theta)$.

Proof of Proposition 2.2. By Lemma 2.3, each displacement of $H$ is a nonnegative linear combination of displacements of Boolean cut maps. It is enough to prove (3) for one such map $H=1_A$.

Let $K=\prod_j\langle v_j\rangle\leq G$. Every shift in the desired inequality preserves every coset of $K$. On a fixed coset, choose a representative $c$ and identify $T=\prod_j\mathbb{Z}/p_j\mathbb{Z}$ with that coset through $t\mapsto c+\sum_jt_jv_j$. The cut becomes $F(t)=1_A(c+\sum_jt_jv_j)$. For Boolean values, absolute difference equals squared difference. With $D_F(l)=\mathbb{E}_t\lvert F(t+l)-F(t)\rvert$, it remains to prove

where $\mathbf{1}=(1,\ldots,1)$ and $e_j$ is the $j$th coordinate vector.

We compare the multipliers in Lemma 2.4 one frequency at a time. Fix $\lambda\in T$, write $S=\{j:\lambda_j\neq0\}$ and $r=\lvert S\rvert$. When $\lambda_1=0$, the left multiplier vanishes. Assume therefore that $\lambda_1\neq0$. The left multiplier is at most four.

First suppose $r<h$. Choose $0\leq\lambda_j<p_j$ and put

For any $i\in S$, distinctness of the primes gives $q\theta\equiv\lambda_i(q/p_i)\not\equiv0\pmod{p_i}$. Thus $\theta$ is not an integer. Since its denominator divides $q$, its distance $\delta$ from the nearest integer satisfies

Concavity of sine on $[0,\pi/2]$ gives $\sin(\pi\delta)\geq2\delta$. Consequently the simultaneous-shift multiplier on the right of (6) is at least

which bounds the left multiplier. Now suppose $r \ge h$. For each coordinate, the same geometric-series identity gives

The component terms on the right therefore have combined multiplier $(2/h)^{2r} \ge4$, again bounding the left. This case includes $h=1$. Multiplication by $|\widehat{F}(\lambda)|^2$ and summation over $\lambda$ proves (6). Averaging over the equal-size cosets gives the uniform average over $G$. Finally, summing the nonnegative cut weights proves the proposition for $H$.

The two cases explain the role of distinct periods. A low-support frequency pays for a nonintegral simultaneous phase; a high-support frequency pays for many component variations. The next section turns these two payments into an iterated obstruction.

Recursive words with incompatible displacements

We now build the words to which Proposition 2.2 will be applied. The row list must be long enough that its one-row shift remains inexpensive after multiplication by $(2P)^{2h}$ in that inequality. At the same time, it must be shorter than the product of many component periods, so that a row shift cannot cancel too many prime-period differences. The following choices provide both properties.

Fix a sufficiently large integer $k$ and set

Choose $b$ distinct primes in $[P,2P]$, and call their set $\mathcal{P}$. The prime number theorem gives $\pi(2P)-\pi(P)\sim P/\log P>b$ for all sufficiently large $k$; the explicit interval estimate of Rosser and Schoenfeld [9] also gives this consequence. We use this one pool and the same parameters at every level.

The recursive family and its cheap steps

For every $0\le s\le k$ and $p\in\mathcal{P}$, the construction supplies a finite abelian state group $G_{s,p}$, a distinguished element $v_{s,p}$ of order $p$, and a word map

It also supplies a finite list $S_{s,p}$ of pairs $(e,r)$, where $e\in G_{s,p}$ is a step and $r>0$ is its displacement budget. The word map itself need not be injective. Define

Proposition 3.1 (Recursive properties). The families can be chosen with

so that the following assertions hold.

1. Every listed step is cheap at every state:

2. Every nonzero distinguished shift is separated at every state:

3. If $H:G_{s,p}\to\ell_1$ satisfies the averaged budgets $V_H(e)\le r$ for all $(e,r)\in S_{s,p}$, then

The first two assertions describe the geometry of the words. The third says that any $\ell_1$ map respecting the same cheap-step budgets has small average displacement in the separated direction. We prove the proposition by simultaneous induction on $s$, constructing the word maps and the cheap-step lists together.

At level zero, take

The single symbols are distinct. Their insertion–deletion distance is two, so the first two assertions hold with $n_0=1$ and $\alpha_0=1$. The listed budgets give the third assertion with $Q_0=2$. The alphabet has $p\le2P$ symbols.

Suppose the families at level $s-1$ have been constructed. To build the family indexed by $p$, enumerate the pool as $p_1,\ldots,p_b$ with $p_1=p$, and abbreviate

Set $G_{s,p}=\prod_{j=1}^{b}G_j$ and $v_{s,p}=(v_1,0,\ldots,0)$, which has order $p$.

For $z=(z_1,\ldots,z_b)$, the new word is a concatenation of $L$ rows, indexed by $i=0,\ldots,L-1$. Row $i$ begins with a payload of $2b-1$ slots. Its first $b$ slots contain separately tagged copies of $W_1(z_1+i v_1)$; its remaining slots contain tagged copies of $W_j(z_j+i v_j)$ for $j=2,\ldots,b$, in that order. Each slot has its own tag, fixed across all rows and different from every other slot tag. The payload length is $B=(2b-1)m$. Append a marker $\#^B$, where $\#$ is absent from all payloads.

More formally, the new alphabet is the disjoint union of $\{\#\}$ and one set $\{r\}\times A_{s-1,p_j}$ for each slot $r$ carrying component $j$. This also tags every lower-level marker, so none becomes the new symbol $\#$. The full length and alphabet bounds are

There are two kinds of cheap steps. First include the simultaneous step $\tau=(v_1,\ldots,v_b)$ with budget $2/L$. Row $i$ of the word at $z+\tau$ is row $i+1$ of the word at $z$ whenever $0\le i<L-1$. Deleting the first row and inserting one final row costs at most $4B=2n_s/L$.

For the other steps, let $c_1=b$ and $c_j=1$ for $j\ge2$, and put

The number $\omega_j$ is the fraction of the full word occupied by component $j$; markers occupy the other half. For each $(e,r)\in S_{s-1,p_j}$ include its lift $\tilde e$ to coordinate $j$ with budget $\omega_jr$. The preceding level’s bound holds at every translated state $z_j+i v_j$. Editing the $Lc_j$ affected slots separately therefore costs at most $Lc_jmr=n_s\omega_jr$. This proves (8).

Separation across row boundaries

We first isolate the matching argument supplied by the fresh markers. It will convert a comparison of every pair of payloads into a comparison of the full row lists.

Lemma 3.2 (Marked payloads). Let $T,p,q \ge1$ be integers, let $\Gamma$ be an alphabet, and let $\# \notin\Gamma$. For $U_a,V_b \in\Gamma^p$ with $1 \le a,b \le T$, put

If $d \ge0$ and $r_p(U_a,V_b) \ge d$ for every $a,b$, then

In particular, $d \le q$ implies $\Delta(X,Y) \ge Td$.

Proof. Fix an increasing matching, with $E$ unmatched positions on each side. No source payload symbol can match a target marker. Let $s$ be the number of source payloads whose matches reach at least two target payloads.

A source payload whose matches lie in one target payload loses at least $d$ source positions. A payload with no matches loses $p \ge d$ positions. Summing over these $T-s$ payloads gives $E \ge d(T-s)$.

For each of the other $s$ payloads, choose a target marker between two of its matches, as in Figure 1. The entire marker is unmatched: a matched target position between the two chosen matches would have its source partner between their source partners, inside this source payload, where $\#$ does not occur. The target matched spans of different source payloads are ordered and disjoint, so the chosen markers are distinct. Thus $E \ge sq$.

Combining the two estimates gives $E \ge d(T-E/q)$ and hence $E \ge Tdq/(d+q)$. The latter is at least $(T/2)\min(d,q)$. This holds for every matching, including when $d=0$, and proves (12). Finally $\Delta(X,Y)=2r_N(X,Y)$. □

We apply the lemma to the words at $z$ and $z+uvs_{v,p}$, where $1 \le u < p_1$. Compare source payload $i$ with target payload $i'$ and write $\delta=i'-i$. Their relative shifts are $(\delta+u)v_1$ in component 1 and $\delta v_j$ in component $j \ge2$.

At least $b/3$ slots have a nonzero shift. If $p_1 \nmid\delta+u$, all $b$ copies of component 1 do. Otherwise $\delta\ne0$, since $1 \le u < p_1$. Now $0 < |\delta| < L=P^{b/2}$, whereas the product of $b/2$ distinct primes from the pool is at least $P^{b/2}$. Fewer than $b/2$ pool primes can therefore divide $\delta$. Among components $2,\ldots,b$, at least $b-1-b/2 \ge b/3$ have a nonzero shift.

In each such slot the induction hypothesis gives insertion–deletion distance at least $m\alpha_{s-1}$. A matching of the two complete length-$m$ slot words therefore leaves at least $m\alpha_{s-1}/2$ source positions unmatched. Since the slot tags are disjoint, every matching between the two payloads restricts to a matching of the corresponding complete slot words. Its size is bounded by their LCS even if other source payloads use some positions of the same target slot. Thus every pair of payloads has one-sided deficit at least

We have $d_s \le B$. Lemma 3.2, with $T = L$ and marker length $B$, gives $\Delta(W_{s,p}(z), W_{s,p}(z+uv_{s,p})) \ge Ld_s$. Dividing by (10),

This proves the pointwise separation (9).

The averaged analytic recurrence

Suppose $H : G_{s,p} \to\ell_1$ meets the listed averaged budgets. We need the preceding level’s assertion for one component, but its hypotheses concern averages over that component’s entire state group. The right map is a direct sum over all settings of the other components.

For fixed $j$, let $Y_j = \prod_{\ell\ne j} G_\ell$ and define

Here $H(x,y)$ means that $x$ occupies coordinate $j$, and the finite direct sum of sequence spaces is identified with $\ell_1$. For every $e \in G_j$, additivity of the sum norm gives

The lifted step budgets therefore make $T_j$ satisfy all the preceding level’s hypotheses at once. The induction assertion yields

where $a = 0$ is immediate. No individual slice of $H$ is required to satisfy those hypotheses.

Apply Proposition 2.2 to the factors $G_j$ and their distinguished elements. The simultaneous budget, component control and (11) give

This proves (3.5) and completes the simultaneous induction in Proposition 3.1.

The quotient $\alpha_s/Q_s$ measures the resulting obstruction to embedding the word image. Indeed, let $f : W_{s,p}(G_{s,p}) \to\ell_1$ have distortion $D$, normalized so that $\mathbb{E}D(x,y)/D \le |f(x)-f(y)|_1 \le $\operatorname{ED}(x,y)$. Then $H=f\circ W_{s,p}/n_s$ satisfies the listed budgets by $\operatorname{ED}\le\Delta$ and (8). On the other hand, (9) and $\operatorname{ED}\ge\Delta/2$ give

Thus pointwise word separation can be compared directly with averaged $\ell_1$ displacement. It remains to estimate this quotient and retain it when the growing alphabet is replaced by binary symbols.

Binary encoding and the lower bound

We replace each letter by a binary block of width logarithmic in the alphabet size. For insertion–deletion distance, the code below expands by at most its width and contracts by at most an absolute factor; hence transferring the preceding obstruction to binary words costs only the width times an absolute factor. The delimiter ensures that a code block whose bits all match consecutive positions must match one equal code block. We also prove the variable-length padding statement needed for the upper bound.

Lemma 4.1 (Binary delimiter code). Let $\mathcal{A}$ have size $A\ge2$, let $t=\lceil\log_2 A\rceil$, and put $w=2t+3$. Assign distinct labels $(a_1,\ldots,a_t)\in\{0,1\}^t$ to its letters. Let $c(a)$ be the prefix $110$ followed, in order, by the two-bit words $a_j0$ for $j=1,\ldots,t$. Extend $c$ by concatenation to all finite strings, with $c(\varepsilon)=\varepsilon$. Then

For an integer $D\ge0$ and $|x|\le D$, set $c_D(x)=c(x)0^{w(D-|x|)}\in\{0,1\}^{wD}$. Then

Proof. We prove both lower bounds at once for $U=c(x)0^r$ and $V=c(y)0^s$, where $r,s\ge0$ are arbitrary integers. The pattern $11$ occurs exactly at the start of a genuine letter block: zeros separate the label bits, every block ends in zero, and the added suffixes contain only zeros.

Fix an increasing bit matching. Let $a_U,a_V$ be its unmatched counts on the two sides and put $a=a_U+a_V$. Call a genuine block good if all of its bits are matched and their partners occupy consecutive positions. On either one side, at most $a$ genuine blocks are not good. For the $U$ side, a block containing an unmatched bit can be charged to one such bit, with distinct charges for distinct blocks; this accounts for at most $a_U$ blocks. Any other non-good block has all its bits matched, but some two consecutive block positions have partners separated by a nonempty open interval in $V$. Every bit in that interval is unmatched, since a partner would have to lie between consecutive positions in $U$. Charge one bit in the interval. The intervals for distinct blocks are disjoint by monotonicity, so this accounts for at most $a_V$ more blocks. The argument includes skipped intervals containing whole blocks or padding. Interchanging the two strings gives the same bound on the $V$ side.

A good block begins with matched bits $11$. Its consecutive partners therefore start at a genuine block boundary on the other side. There are exactly $w$ partners, so they form that entire block. The two blocks are equal and encode the same letter; the target block is itself good. The same argument in reverse shows that the good blocks on the two sides pair bijectively, in increasing order. They give a letter matching between $x$ and $y$ whose loss is the number of non-good genuine blocks, at most $2a$. Lemma 2.1 yields $\Delta(x,y) \le2a$. Minimizing the bit loss proves the lower bounds, including empty strings and independently chosen zero suffixes.

For the unpadded upper bound, implement each letter insertion or deletion by $w$ bit operations. For the padded bound, put $r = w(D - |x|)$ and $s = w(D - |y|)$. Transform the coded prefix while retaining its suffix, then adjust the suffix length:

The last inequality follows because one insertion or deletion changes length by one.

The quantitative obstruction

First bound the recurrence in Proposition 3.1. For sufficiently large $k$, we have $2P \le P^{3/2}$ and

For the last inequality, $P^{b/6} = b^{b/3} = b^{(100/3)k} \ge(b/10)^k = h^k$. Since $h \ge2$, solving (7) gives

The alphabet recurrence gives $A_s \le(2P+1)(2b)^s$: the base case is immediate and $1+(2b-1)A_{s-1} \le2bA_{s-1}$. Hence $\log A_k = O(k\log k)$. Fix a prime $p \in\mathcal{P}$ and apply Lemma 4.1 to the alphabet of $W_{k,p}$, without padding. Write $\operatorname{enc}$ for the resulting concatenated code. Its width is $w = O(k\log k)$, and all encoded words have the same length

for an absolute $C_{\mathrm{len}}$ and all sufficiently large $k$.

Proposition 4.2. For all sufficiently large $k$, every $\ell_1$ embedding of

has distortion at least

for an absolute constant $c_0 > 0$.

Proof. Let $f$ be an injective embedding of $\mathcal{W}_k$ with distortion $D$. Rescale it so that

and define $H(z)=f(\operatorname{enc}(W_{k,p}(z)))/(wn_k)$. For every listed step $(e,r)$, the code’s upper bound and (8) give, at each state,

Thus $H$ meets the averaged hypotheses of Proposition 3.1.

For $v=v_{k,p}$, the lower bounds give, again at every state,

In particular, these designated pairs represent distinct words, although other state pairs may coincide. Averaging and using (3.5) and (4.3), we obtain

Since $h=10k$ and $w=O(k\log k)$, the logarithm of the last expression is $k\log k-O(k)-O(\log k)$. It is at least $c_0k\log k$ for all sufficiently large $k$.

A witness for every sufficiently large cap

Set $t=\log d$ and fix $a>0$ small enough that $C_{\mathrm{len}}a^2\le1/2$. Choose

For sufficiently large $d$, this depth is available and $\log k\le\log t$. (4.4) gives

so $N_k\le d$. After increasing the threshold on $d$,

Proposition 4.2 therefore proves the lower bound in (1.1) for binary strings. This direct choice of $k$ uses no estimate on gaps between successive lengths $N_k$.

Finally, choose two letters in any finite alphabet $\Sigma$ of size at least two. Their strings form an isometric copy of binary edit distance. One inequality follows because every binary edit script is also a $\Sigma$-script. For the reverse inequality, project all other letters to one of the chosen letters; each operation in a $\Sigma$-script becomes at most one binary edit. Restricting an embedding to this subspace gives $E_\Sigma(d)\ge E_{\{0,1\}}(d)$ and completes the lower half of Theorem 1.1.

An upper bound uniform over finite alphabets

The upper proof uses one external embedding theorem. We state the normalized form needed here from Theorem 7, printed page 7, of the August 19, 2005 author manuscript of Ostrovsky and Rabani [8]. Their introduction also notes the larger-alphabet and varying-length extensions. The proof below supplies the complete uniform reduction from this fixed-length binary input.

Theorem 5.1 (Ostrovsky–Rabani, normalized form). There is an absolute constant $C_0$ such that, for every integer $m \ge3$, there is a map $g_m:\{0,1\}^m \to\ell_1$ satisfying

Here $\operatorname{ED}$ permits unit-cost substitutions as well as insertions and deletions.

On the finite domain, the minimum pairwise image-to-edit-distance ratio of an embedding is positive; division by that ratio makes the theorem noncontracting without changing distortion. Its asymptotic expression is written with natural logarithms, and increasing $C_0$ absorbs any finite set of small lengths $m \ge3$: mapping each binary string to a distinct coordinate vector has distortion at most $m$.

We reduce the alphabet to a number of labels depending only on $d$, then use Lemma 4.1 to encode and pad to one binary length. A final direct sum over all label maps will turn the pairwise probability estimate into one embedding of the whole domain.

Proposition 5.2 (Uniform alphabet bound). There is an absolute constant $C$ such that, for every finite alphabet $\Sigma$ with $|\Sigma| \ge2$,

Moreover, $E_{\Sigma}(1)=1$ and $1 \le E_{\Sigma}(2) \le2$.

Proof. Fix $d \ge1$ and put $q=4d^2$. Choose a map $h:\Sigma\to[q]$ by assigning independent uniform labels to the letters, and apply it letter by letter to strings. Equal original letters remain equal after relabeling, so every original increasing matching remains valid. Hence, for every outcome,

For a fixed pair $x,y \in\Sigma^{\le d}$, let $S$ be the set of letters appearing in either string. Since $|S| \le2d$, the union bound gives

When $h$ is injective on this pair’s letters, equality of symbols is preserved in both directions. The available increasing matchings are then exactly the same, so

For the alphabet $[q]$, use the delimiter code with $t=\lceil\log_2 q\rceil$, $w=2t+3$, and binary length $m=wd$. We have $m \ge7$, so Theorem 5.1 applies. For every $h$, the padded string $c_d(h(x))$ has length $m$. The metric comparisons, (4.2) and (5.3) give

On the event in (5.5), the reverse estimate is

Let $\mathcal{H}$ be the finite set of all $q^{|\Sigma|}$ label maps, with probabilities $p_h=q^{-|\Sigma|}$. Define

This finite direct sum is an $\ell_1$ vector, and the sum norm gives the exact identity

Taking expectations in (22) and (23), using (20), yields

Thus $F$ is injective and has distortion at most $32wD_m$. The empty string has image zero, since its padded code is $0^m$; its distance bounds are included in the same calculation.

For $d\geq3$, $w=O(\log d)$ and $m=O(d\log d)$ with absolute constants. Therefore

which proves (18), enlarging the absolute constant for finitely many initial values if necessary.

For $d=1$, all distinct strings in $\Sigma^{\leq1}$ have edit distance one, and $x\mapsto e_x/2$ is isometric. In general, every nonzero edit distance between strings of length at most $d$ lies between one and $d$: substitute the common-length part and then insert or delete the remaining symbols. The same coordinate-vector map has distortion at most $d$, giving $E_\Sigma(2)\leq2$. Distortion is always at least one.

Together with the binary witnesses of Section 4, this proves Theorem 1.1.