Tree Constructions for the l1 Distortion of Binary Edit Distance

1 Introduction

An insertion or deletion changes the positions of every later symbol in a word. A long interval can therefore move at small edit cost even when many positions change. This tension between order and inexpensive shifts is central to the question studied here: how faithfully can one represent the edit distances of an entire set of words by distances in \ellone?

We use ordinary edit distance \ED(x,y): the minimum number of single-symbol insertions, deletions and substitutions taking x to y, each with cost one. For a finite alphabet \Sigma with at least two symbols and an integer d\geq1, let \Sigma^{\leq d} be the set of words of length at most d, including the empty word. The cap constrains the words in the domain; an edit script computing their distance may pass through words of any finite length.

For a finite metric space (X,\rho) with at least two points and an injective map f:X\to\ellone, where \ellone is the space of absolutely summable real sequences, define

Let c_1(X,\rho) be the infimum of \dist(f) over such maps, and put E_\Sigma(d)=c_1(\Sigma^{\leq d},\ED). No restriction is imposed on the dimension of the image or on the computation of the map. Throughout the paper, logarithms in asymptotic estimates are natural unless a base is written explicitly.

We prove the following lower bound in two independent ways. Each proof uses a tree to combine inexpensive shifts with a displacement that no alignment can hide.

The words in a witness all have the same length, although that length may depend on the cap d. At tree depth k, each construction produces logarithmic distortion of order at least k\log k and logarithmic word length of order k^2\log k. Balancing these two scales gives Theorem 1.1 for every sufficiently large cap, not just for a subsequence of caps.

The lower bound is proved here without a companion input. The uniform upper embedding theorem of the finite-circle companion, stated precisely in Section 6, then gives

with constants independent of the finite alphabet \Sigma. This is a matching exponential scale, not a constant-factor estimate for E_\Sigma(d) itself.

1.1 History and the embedding question

The single-symbol error model is classical in coding and sequence comparison. Levenshtein studied binary codes correcting insertions and deletions [11], and Wagner and Fischer formulated string correction through increasing partial alignments [17, Sections 3 and 5]. An embedding asks for one set of coordinates that represents every pair in a domain. It is a different task from estimating the distance of one given pair of words. For supplied pairs of binary words, [13, Theorem 1.1] gives a randomized approximation scheme with almost-linear worst-case expected time for each fixed rational accuracy.

Ostrovsky and Rabani proved an \ellone distortion bound \exp(O(\sqrt{\log n\,\log\log n})) for binary words of a fixed length n [15]. Their recursion compares overlapping substrings and represents their distributions in smaller metric spaces. They also noted extensions to larger alphabets and varying lengths. For the upper bound used at the end of this paper, the companion uniform upper embedding theorem [14, Uniform upper embedding theorem] gives the full quantitative statement on \Sigma^{\leq d} with constants independent of the finite alphabet.

On the lower-bound side, Andoni, Deza, Gupta, Indyk and Raskhodnikova realized complete bipartite graph metrics in binary edit distance and obtained \ellone distortion approaching 3/2 [1, Section 2 and Theorem 3.1]. Their witness uses three adjacent word lengths. Khot and Naor developed Fourier methods for nonembeddability and obtained an edit-distance lower bound of (\log n)^{1/2-o(1)} for binary words of a fixed length [8]. Their insertion–deletion metric and the ordinary metric used here differ by at most a factor of two. Krauthgamer and Rabani then proved an \Omega(\log n) lower bound for binary words of length n [10, Theorem 1.3]. Khot and Naor used Boolean noise sensitivity, while Krauthgamer and Rabani sharpened the obstruction through an influence inequality for bit flips and cyclic shifts. These cut and shift arguments are methodological predecessors of the proofs here. A cut records which pairs a binary coordinate separates, and Fourier coefficients describe how that separation changes under translations. We prove the particular translation estimates needed for our trees.

Alphabet reduction also has a substantial history. Schulman and Zuckerman use separation between long intervals of distinct codewords in concatenated insertion–deletion codes [16], and synchronization strings protect positions against insertion and deletion errors [5]. More directly, Bhattacharya, Dey, Goldenberg and Koucký state a map on all finite words with an insertion–deletion guarantee normalized by the sum of the word lengths, for pairs of positive total length. The block substitution used to prove their stated theorem has logarithmic width and, for a fixed error parameter, a constant target alphabet [2, Theorem 3; full version, Section 3.2.1 and Lemma 3.3]. For equal-length inputs, their stated normalized guarantee, combined with the elementary delimiter construction below, gives a binary reduction with logarithmic width and absolute distortion. Our lower proofs do not use that result. They use the short delimiter code, whose width-dependent loss is harmless at the tree scale; the appendix gives a separate constant-distortion code for one prescribed word length. For comparison, the isometric Hamming-to-edit embedding of Bhattacharya et al. [3, Theorem 7] starts from a different input metric. The conversions proved here compare edit distance on the source words with edit distance on their binary encodings.

1.2 Two independent tree proofs

Both constructions use an ordered tree. A leaf has a state coordinate and produces a symbol carrying its leaf label. An internal node produces a long list of rows, each containing its child words in their fixed order. Advancing the row index deletes a few rows at one end and inserts a few at the other, so it is inexpensive. A distinguished second shift must instead separate the words even when an alignment crosses row boundaries.

The shared alignment lemma in Section 2 handles this difficulty. Leaf labels preserve child indices, not row indices. An unsplit source row loses symbols because its child words are separated from the corresponding target words. A split source row forces a long unmatched target interval between consecutive matches. The intervals charged by different source rows are disjoint. Thus separation in every comparison of two rows implies separation of the whole words, without assuming that row boundaries match.

The two constructions arrange the shifts differently. In the finite tree of Section 3, a child’s period is its parent’s period times a new prime. At an internal node, a vector u_v advances rows and a multiple w_v has the parent period. The distinct prime factors prevent a difference of row indices from cancelling the distinguished shift in too many children. This gives a deterministic separation proof on a finite group. For a Fourier character, activity at a node with few active children has a short period and is detected by an average of inexpensive row shifts. A character escaping every such test must be active on many leaves; individual leaf changes then bound its contribution. The section closes with binary witnesses for every large cap.

The circle tree in Sections 4 and 5 uses quantized phases instead of finite residues. Random prime lists and coefficients make the root half-turn separate every base phase. The probabilistic assertion is only for one fixed shift; the all-phase conclusion follows deterministically from the alignment lemma. In its Fourier argument, tiny rotations detect large integer frequency sums and rational row shifts detect failed prime congruences. When both tests fail, divisibility forces every nonzero sum to continue through many children. This supplies the second binary proof without using the finite tree.

Both routes use the same elementary delimiter code from Section 2. Its distortion loss grows with the block width, but that width is only O(k\log k) here and does not change the logarithmic lower-bound scale. Appendix A 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. Its proof is independent of both trees, and neither headline lower bound requires this stronger conversion.

2 Edit deficits, ordered rows and binary transfer

Both trees need four elementary tools. Subsequence deficits and an alignment lemma turn separation of child blocks into separation of whole words, even when matches cross row boundaries. A cut representation permits the later Fourier estimates, and a prime count supplies the periods. Finally, a short binary code transfers either tree’s obstruction to binary words with a controlled width loss.

2.1 Subsequence matchings

A common subsequence matching of words x=x_1\cdots x_a and y=y_1\cdots y_b is a list of pairs (i_1,j_1),\ldots,(i_s,j_s) whose two index lists are strictly increasing and for which x_{i_t}=y_{j_t} for every t. Its largest possible size is \LCS(x,y). The insertion–deletion distance is

Indeed, symbols of x that survive an insertion–deletion script form a common subsequence; conversely, retaining a longest common subsequence and deleting and inserting the remaining symbols attains this value. Replacing each substitution by one deletion and one insertion gives

For words of equal length n, put r_n(x,y)=n-\LCS(x,y). Thus

A matching of size n-E between two length-n words leaves exactly E unmatched positions on each side.

2.2 The common alignment lemma

Suppose each row consists of one block from each of several pairwise disjoint alphabets, in the same order. An equal-symbol match must then join blocks with the same index, although their row indices can differ. Products of words in the next lemma mean concatenation in increasing index order.

The two inequalities in the proof bound the same number E using different words: nonsplit rows give source losses, and split rows give target losses. Equal total lengths make the unmatched counts equal. The fixed order, equal block lengths and disjoint tags supply the target gaps; no alignment of row boundaries is assumed. Figure 1 illustrates the gap created by a split row.

2.3 Cuts and prime counts

We record two background facts for both constructions. The first turns an \ellone distance on a finite set into a nonnegative sum of binary separation tests. This standard cut description is stated, for example, in Section 4 of Linial, London and Rabinovich [12]; the proof below includes a summability bound for maps with infinitely many coordinates.

The second fact supplies all primes used below. We use the elementary binomial-coefficient argument, following the classical prime-product method found, for example, in Erdős [4]. Write \pi(x) for the number of primes at most x.

2.4 A short binary code

The trees initially use leaf labels and hence a growing alphabet. The following code will suffice for both binary lower bounds. It preserves subsequence deficits from below, while its expansion is at most its block width. For the tree alphabets that width will be O(k\log k), small compared with their eventual distortion lower bounds.

By (2), the lower bound in (7) is at least \ED(x,y)/4. Consequently, if a finite set of equal-length words has \ellone distortion at least D_0, its encoded image has distortion at least D_0/(4B): composing an embedding of the encoded image with \mathcal B incurs at most the factor 4B.

3 A finite tree with nested periods

We first construct words over a finite alphabet that grows with the tree. At every internal node, one vector advances the rows cheaply and a multiple of it has a prescribed smaller period. The latter vector separates words for every state. We then use Fourier analysis to show that an \ellone map cannot preserve both kinds of displacement with small distortion. The short binary code from Lemma 2.4 will then complete the first proof of Theorem 1.1.

3.1 Periods and word construction

Fix a sufficiently large integer k and put

Use the full ordered m-ary tree of depth k, with root o at depth zero and children v1,\ldots,vm at each internal node v. By Lemma 2.3, choose primes p_{j,i}\in[k^4,k^5] distinct over all pairs 0\leq j<k, 1\leq i\leq m. Nodes at the same depth use the same list. Define their periods by

All these primes are odd for large k.

On the finite abelian group

define vectors supported on their respective subtrees:

Here e_u increments the coordinate of leaf u.

For x\in A, the leaf word is the single symbol G_u(x)=(u,x_u). At an internal node, define

where the product concatenates the rows in increasing a. Only leaf coordinates below v affect G_v. At depth j and height h=k-j, its length is L_v=(mT)^h. Write

Every symbol retains its leaf label. Thus the alphabets occurring below different children of a node are disjoint, exactly as required by Lemma 2.1.

3.2 Cheap translations and uniform separation

We first bound the cost of advancing rows or changing one leaf. These bounds hold at every state and will later be averaged over A.

We now prove separation for every nonzero residue along the order-Q_v vector w_v=R_vu_v, uniformly in the initial state.

We have obtained the two geometric facts needed for the obstruction: the root shift w_o is far at every state, while the shifts in Lemma 3.2 are cheap. The remaining argument compares their average images under an arbitrary \ellone embedding.

3.3 Fourier detection of sparse activity

For a finite abelian group A, use uniform probability measure and write \widehat A for its character group. The following identity represents an averaged \ellone displacement through cuts and Fourier coefficients. It is the elementary translation principle underlying the comparison with the cut methods of Khot–Naor and Krauthgamer–Rabani [8, 10].

For a character \chi, call a node v active when \chi(w_v)\ne1. Let \wt(\chi) be the number of active leaves. The period design has one useful consequence: activity at a node with few active children is detected by a short average of cheap shifts. Frequencies that escape all these tests must have large leaf support.

3.4 Binary witnesses for every sufficiently large cap

The finite tree alphabet contains one symbol for each leaf and each residue in its coordinate group. Since Q_u\leq2k^{5k} at every leaf, its size K satisfies

Choose

There are enough t_k-bit labels for all symbols, so Lemma 2.4 applies with width B_k. Its distortion loss is at most 4B_k. Hence Proposition 3.5 supplies a finite binary witness of the single length

whose distortion is at least

The separated root pair and the lower bound in Lemma 2.4 ensure that the witness contains at least two words.

The explicit widths B_k and lengths M increase with k, so d_k increases to infinity, independently of which admissible primes were chosen. Moreover,

for an absolute c'>0 and all sufficiently large k. Given a sufficiently large integer d, choose k with d_k\leq d<d_{k+1}. Then \log d\leq Ck^2\log k and \log\log d\leq C'\log k for absolute constants. Thus

The witness of length d_k\leq d proves Theorem 1.1 for every sufficiently large cap.

4 A tree of circle phases

The second construction again concatenates ordered child words into rows, but a leaf now records a quantized circle phase. We will choose the increments between rows so that a half-turn of all leaf phases separates the resulting words. The choice is random; its output is one fixed word map with separation at every base phase.

4.1 Prime groups and row increments

Fix a sufficiently large integer k and set

Let \T=\R/\Z, with |t|_{\T} denoting the circle distance from t to zero. Use a full ordered m-ary tree of depth k, and divide the children of each internal node into g groups of k^2 children. Each leaf phase will be quantized into R intervals, and each internal word will contain T rows.

Let \mathcal P_k be the primes in [k^2,k^3]. Lemma 2.3 gives |\mathcal P_k|>100g for large k. At each internal node v, independently between nodes, choose an ordered list r_{v,1},\ldots,r_{v,g} of distinct members of \mathcal P_k, uniformly without replacement. Put

To specify the increment of a child vi in group j, choose z_{vi} uniformly from \{0,\ldots,r_{v,j}-1\} and define

Conditionally on all prime lists, all these residues are independent. The increment c_{vi}/P_v has the decomposition

Thus every child has a common drift of 1/P_v, together with an independently chosen step on its group’s prime grid. The same formula isolates the groups arithmetically: if \ell\ne j, then c_{vi}\equiv1\pmod{r_{v,\ell}}. At each selected prime, only coefficients from its own group can differ from one.

Associate a phase w_u\in\T to each leaf u, and write w\in\T^{m^k} for the full vector. For a subtree vector \omega, the notation \omega+t means addition of t to every coordinate of that vector. At a leaf, put

using the representative of w_u in [0,1). At an internal node, define

where \omega_{vi} is the subvector on the leaves below vi. The product concatenates rows in increasing a. At height h, the word length is (mT)^h. The root map X=X_o has length

over the alphabet \Gamma=\{(u,b):u\text{ a leaf},\ b\in\{0,\ldots,R-1\}\}, of size m^kR. For fixed construction data, every position in this word quantizes one leaf phase plus a fixed offset. Hence the range of X is finite and X is measurable.

4.2 Good shifts give separation at every phase

Consider X_v(\omega) and X_v(\omega+t), where the scalar t is added to every leaf phase below v. In a comparison of source row a with target row a', child vi receives the relative shift

The tagged-row lemma will separate the two words if enough children are separated for every row pair. Since each c_{vi} is an integer, the displayed shift depends only on a'-a modulo P_v. This leads to a recursive condition on t alone, independent of the base phase. Set

Call a shift t eligible if |t|_{\T}\geq\epsilon.

The condition asks for at least \delta m children, interpreted as a real threshold on their integer count. Its deterministic consequence is the following separation estimate.

It remains to make the one root shift t=1/2 good. We prove a statement for each fixed eligible shift that can be propagated from a child to its parent. The all-phase conclusion will then follow from the deterministic lemma.

4.3 The probability of a good fixed shift

Fix this realization for the rest of the torus argument. The prime lists and coefficients now have fixed values. Only their stated size and congruence properties will be used below.

5 Torus displacements, Fourier detection and binary transfer

The fixed construction separates every phase vector from its half-turn translate. We now compare this displacement with whole-row shifts, tiny rotations, and changes of a single leaf. The Fourier argument will use the cutoff

The ratio P_v/T\leq k^{-4k} controls the cost of whole-row shifts, and R/Q=k^{-4k} controls the cost of tiny rotations. After proving the comparison for an arbitrary finite-range map on the torus, we apply the shared binary code.

5.1 Pointwise and averaged edit costs

For a node v, let e_v\in\R^{m^k} have entry one on the leaves below v and zero elsewhere. At an internal node, define

This is well defined because each c_{vi} is an integer. Let q be the depth of v.

5.2 The Fourier identity on the torus

The next identity expresses averaged \ellone distances through nonnegative frequency weights. It is the continuous counterpart of Lemma 3.4; its averaging measure and its integer frequencies are different.

5.3 Two tests and forced branching

Apply the notation of Lemma 5.2 with n=m^k. For a frequency \xi\in\Z^{m^k} and a node v, define its integer summary

Thus s_v=\sum_i s_{vi} at an internal node and s_u=\xi_u at a leaf. The multiplier of the root half-turn is 1-\cos(\pi s_o), equal to two for odd s_o and zero for even s_o. We bound it using tests that cover every frequency with s_o\ne0.

The cutoff and congruence tests have different jobs. The divisibility argument forces branching only after all summaries are known to have absolute value less than Q. It would not rule out a large nonzero integer divisible by many of the selected primes.

5.4 The binary obstruction and every length cap

Apply Lemma 2.4 to the torus alphabet of size A=m^kR, choosing labels of length \lceil\log_2A\rceil. Write \mathcal B for the resulting encoding. Its block width is

The encoded image consists of binary words of one length BN. It has at least two points, since the lower code bound preserves the positive root separation in (23). We apply the detection inequality directly to an embedding of this encoded image; the code’s width will enter only the upper cost estimates.

Take any embedding f of the encoded image with distortion D and rescale it to be noncontracting with expansion at most D. Set

The map F is measurable with finite range, so Lemma 5.3 applies. The pointwise separation, the three costs in Lemma 5.1, and the code bounds give

For the second line, use the representative 0\leq a<P_v in the pointwise cost proof; the displacement itself depends only on the residue. The third line uses the Haar-average cost, with no pointwise claim about tiny rotations.

There are m^q nodes at depth q. Thus the factors m^{-q} cancel when the upper bounds are summed over a depth in (30). We obtain

for an absolute C', because R/Q=k^{-4k} and k^{48k}/T=k^{-4k}. Comparing this with (33) gives

The denominator retains the width B from the delimiter code. Since B=O(k\log k), the logarithm of the right side is at least c_{\mathrm{tor}}k\log k for an absolute c_{\mathrm{tor}}>0 and all sufficiently large k.

The binary word length satisfies

For every sufficiently large integer d, put \tau=\log d and choose k=\lfloor a\sqrt{\tau/\log\tau}\rfloor, where a>0 is a sufficiently small absolute constant. There is an absolute C_2 such that \log(BN)\leq C_2k^2\log k for all large k. Since k\leq a\sqrt{\tau/\log\tau} and \log k\leq\log\tau eventually, choosing C_2a^2\leq1/2 gives \log(BN)\leq\tau/2<\tau. Also, for all large \tau,

It follows that k\log k\geq(a/6)\sqrt{\tau\log\tau}. The finite set \{\mathcal B(X(w)):w\in\T^{m^k}\}\subseteq\{0,1\}^{BN} therefore has distortion at least \exp(c\sqrt{\log d\,\log\log d}) and has BN\leq d. This completes the torus proof of Theorem 1.1 for every sufficiently large cap.

6 The uniform two-sided bound

The two lower constructions use no result from a companion manuscript. For the matching upper estimate we use the following full statement of the companion uniform upper embedding theorem [14, Theorem 8.1].

The lower inequality makes the map injective. We use only the resulting distortion bound.

The alphabet may grow with d. The estimate determines the order of \log E_\Sigma(d) uniformly; it leaves the constants within the exponent unspecified.

A A constant-distortion code for one prescribed length

The short code in Lemma 2.4 is sufficient for both tree lower bounds. Here we prove a stronger transfer result: a binary block code with absolute distortion for every pair of words of one prescribed length M, over an alphabet of size at most M. Its width M^2 increases the word length polynomially. The proof combines separation between segments of unequal codewords with an extraction of original common subsequences from matches between equal codewords.

We first choose blocks whose long segments are separated whenever the underlying letters differ. Separation of long intervals of distinct binary codewords also appears in the inner code of Schulman and Zuckerman [16, Section II-C, Condition 2 and Lemma 2]. We prove the precise property needed here directly. The later argument will handle matches between equal letters without a condition on self-overlaps of a codeword.

The segment property is a property of the chosen codebook, so the theorem holds simultaneously for every pair in \Gamma^M. The choice is tied to M: its guarantee is for one prescribed input length and does not assert a logarithmic block width.

For the finite tree, K\leq2m^k k^{5k}\leq M for all large k. This theorem therefore also gives binary witnesses of length M^3 with distortion at least (k/4)^k/(804C_1). The scale P cancels when an embedding is composed with the code. This alternative retains an absolute distortion loss, at the cost of longer words than the delimiter conversion used in Section 3.