Optimal L1 Distortion for Edit Distance Grows as exp(Θ(√(log d log log d)))

Two strings can differ at every position and still be close in edit distance. For example, 0101 becomes 1010 by deleting the first zero and inserting a zero at the end: two edits, not four substitutions. Edit distance allows a string to realign, and that freedom makes it hard to represent all edit distances with ordinary coordinate distances.

The manuscript asks how much distortion is unavoidable when strings of length at most d—including the empty string—are mapped injectively into real L1. Insertions, deletions, and substitutions each cost one. A single common rescaling must work for every pair: for a map f, every image distance must lie between the original edit distance divided by D and the original distance. Neither the target dimension nor the computation time is bounded. The question is about the best possible distortion, not an efficient algorithm.

For every finite alphabet with at least two symbols, and all sufficiently large d, the manuscript bounds the optimal distortion between exp(c√(log d log log d)) and exp(C√(log d log log d)), for absolute positive constants c and C. The alphabet may grow with d. The lower bound already holds for binary strings of one common length at most d. These are matching scales up to constants in the exponent, not an exact formula.

The proof first replaces edit distance with insertion-and-deletion distance, delta, temporarily forbidding substitutions. Since one substitution can be replaced by a deletion and an insertion, edit distance is at most delta, which is at most twice edit distance.

An alignment matches equal symbols in increasing order. Keeping the matched symbols and deleting and inserting everything else gives an insertion-and-deletion script; conversely, symbols surviving any such script form an alignment. Thus delta(x, y) equals the lengths of x and y added together, minus twice the length of their longest common subsequence.

The lower-bound construction builds long strings from rows of smaller “payload” words followed by markers. Each payload slot has its own alphabet tag, so symbols from different slots cannot match. Markers use fresh symbols absent from the payloads. Components cycle with distinct prime periods: advancing all components together shifts the row list by one, which costs little because the shift can be handled by deleting the first row and inserting a final one. Advancing only a distinguished component, by contrast, creates separation.

The key point is that this separation does not depend on rows lining up neatly. Consider two strings with T payloads each, payload length P, and Q copies of a fresh marker after every payload. Suppose any source payload, when matched against any one target payload, loses at least A symbols. For an arbitrary increasing matching, let E be the number of unmatched positions on each side, and S the number of source payloads whose matches are split across target payloads.

The T−S payloads that are not split each lose at least A symbols, so E ≥ A(T−S). Each split payload must cross a target marker. That marker cannot match anything: between the two source matches lies payload material, which contains no marker symbol. Distinct split payloads have disjoint ordered matching spans, so they force distinct unmatched markers, giving E ≥ QS. Combining the inequalities yields E ≥ TAQ/(A+Q). The insertion-and-deletion distance is twice the minimum unmatched count. In particular, when A ≤ Q, delta ≥ TA. Every alignment must pay; the estimate does not assume corresponding rows match.

To turn the alignment argument into an embedding lower bound, the manuscript compares the construction’s separation with what L1 geometry permits. An L1 distance can be written as a nonnegative weighted sum of cuts—tests that separate points into two sides. Fourier analysis of those cuts gives a bound on average displacement under steps in the construction.

Distinct prime periods matter here. If only a few components are active, a simultaneous step detects them; if many are active, averaging over individual component steps detects them. The video omits the detailed Fourier and recursive arguments. Its stated consequence is that, after normalizing a candidate embedding—first rescaling it so it does not expand edit distance, then dividing by constructed-word length—the resulting map obeys the construction’s cheap-step budgets.

At each recursive level, normalized word separation is at least 24 to the power −k, while permitted average image displacement is at most 4 times (10k) to the power −k. The separation and displacement shrink at different rates. Iterating this gap forces distortion of at least (h/24)^k/(16w), where h = 10k and the binary encoding width w grows on the order of k log k.

The recursive construction initially uses a growing alphabet, so the manuscript encodes its symbols as binary blocks. The illustrated code assigns four letters the blocks 1100000, 1100010, 1101000, and 1101010: each begins with 110, with zeros separating the label bits. The block-start pattern lets an arbitrary bit alignment be charged back to an alignment of letters. The encoding loses a factor proportional to block width, rather than destroying the separation outright.

The constructed binary length satisfies log Nₖ ≤ C_len k² log k, while the forced distortion has logarithm at least a constant times k log k. Choosing k proportional to √(log d / log log d), with a sufficiently small constant, keeps the witness length below d and gives the stated lower-bound scale for every sufficiently large length cap—not only selected lengths.

For the matching upper scale, the manuscript uses an earlier fixed-length binary embedding theorem of Ostrovsky and Rabani. That result embeds binary strings of length m into L1 with distortion exp(C₀√(log m log log m)). The manuscript identifies this theorem as its external input; the paper is available here.

To extend this to an arbitrary finite alphabet, the proof first considers one pair of strings. At most 2d distinct letters occur in that pair. Assign letters labels from a set of size 4d²; the probability that any two of those letters collide is less than one-half by a union bound. If the labels do not collide, the pair’s insertion-and-deletion distance is preserved. The labeled strings can then be encoded and padded to a common binary length before applying the binary embedding.

The argument does not claim that one lucky random labeling preserves every pair. Instead, it takes a weighted direct sum over all label maps. Averaging yields a single embedding with bounds that hold for every pair, including pairs involving the empty string. That uniformity is what makes the upper bound apply across finite alphabets, while the recursive alignment construction supplies the matching lower scale. The constants in the exponent remain unspecified.