Binary Edit Distance Requires L1 Distortion of exp(Θ(√(log d · log log d)))

Two binary strings can disagree at every position and still be close under edit distance. In the example, alternating strings have eight positional mismatches. Delete the first zero and append a zero, however, and one becomes the other in two edits. Insertions, deletions, and substitutions each cost one. A shift can move many symbols while costing little.

The question is whether one map into an L1 space can preserve the edit distances between every pair in a family of words. L1 distance is the sum of absolute coordinate differences. After rescaling, distortion D means that every pair x, y satisfies edit distance at most the L1 distance between their images, and that distance is at most D times the edit distance.

The manuscript proves a worst-case lower bound: for every sufficiently large length cap d, some finite family of at least two binary words, each of length at most d, requires distortion at least exp(c√(log d · log log d)), where c is a positive absolute constant and the logarithms are natural. The family can depend on d. This is an obstruction to embedding all pairwise distances in one family with one map, not a claim about the difficulty of computing the edit distance for a single pair.^†

Both constructions arrange words on ordered trees. A leaf contributes a symbol containing its leaf label and a changing state. At an internal node, child words form blocks in a row, and many rows are concatenated into a word. Shifting the row parameter can delete a few rows at the beginning and insert a few at the end—a cheap change relative to the full word.

The challenge is to find another shift that remains far apart under every alignment. Leaf labels identify child indices, not row indices, so a matching can cross row boundaries. The shared alignment lemma accounts for that freedom.

Suppose each word has T rows, each containing m blocks of length B, with m at least two. Different block indices use disjoint alphabets. For a pair of corresponding blocks, define its deficit as B minus the length of their longest common subsequence. Assume that, for every source-row and target-row pair, the deficits across their blocks sum to at least δ.

Fix any increasing common-subsequence matching of the full words. Since the words have equal length, the number of unmatched symbols on each side is the same; call it E. A source row is split if its matches land in more than one target row. If S rows are split, then each of the other T − S rows loses at least δ source symbols. This includes a row with no matches, so E ≥ δ(T − S).

Splitting also costs unmatched target symbols. In a split row, choose consecutive matches in the overall matching that cross a target-row boundary. Their block indices and order are preserved. Between them, at least m − 1 complete blocks must be skipped, costing at least G = (m − 1)B unmatched target symbols. The target intervals charged to different source rows are disjoint, so E ≥ SG. Combining the inequalities gives E ≥ TδG/(δ + G). When δ ≤ G, at least half the row-wise deficit survives.

For equal-length words, the longest common subsequence leaves E unmatched symbols on either side. Any edit sequence must use at least E operations: one edit can increase the length of a common subsequence by at most one. Thus the edit distance is at least E. Applying the argument to a longest matching makes the bound hold for edit distance, without assuming that row boundaries align.

In the first construction, each child’s period is its parent’s period multiplied by a fresh prime. The distinct primes prevent row-index differences from canceling the distinguished shift in too many children. Repeated applications of the alignment lemma keep the root shift separated.

The proof then represents L1 distances as nonnegative weighted sums of cuts and tracks how those cuts respond to shifts using Fourier frequencies. A frequency that responds at a node but at fewer than K children can be exposed by a cheap row shift. If it responds at the root and escapes those tests, it must branch to at least K children at each of K levels, producing at least K^K active leaves. Cheap changes at individual leaves constrain the frequency’s weight; together with the root separation, those constraints force large distortion.

The independent second construction uses phases on circles rather than finite residues. Randomly chosen primes and increments produce a fixed half-turn that is good at the root. Once chosen, the construction gives separation for every base phase; it does not claim that one random choice works for every shift. Tiny rotations detect large frequency sums, while rational row shifts detect failed prime congruences. A frequency that responds to the root half-turn and escapes both tests must again branch through at least K^K nonzero leaf frequencies.

The tree symbols include leaf labels, so they are not yet binary words. The manuscript assigns each symbol a distinct T-bit label, prefixes it with 110, and inserts a zero after every label bit. Two consecutive ones then occur only at block starts. The resulting block width is 2T + 3.

The encoding makes the binary edit distance at least one quarter of the original and at most the block width times the original. The distortion obstruction therefore loses at most a factor of four times that width. In these trees the width grows like K log K, which does not erase the exponential scale.

At depth K, the logarithm of word length grows like K² log K, while the logarithm of the distortion lower bound grows like K log K. Balancing those scales yields an exponent on the order of √(log d · log log d). The construction chooses a depth that fits every sufficiently large length cap, rather than applying only at a sparse sequence of lengths.

The manuscript combines its lower construction with a companion upper-embedding theorem. Together they give the same exponential order for the least distortion needed to embed all words of length at most d, over every finite alphabet of size at least two, including alphabets that grow with d. The constants inside the exponent are not matched.^†