Edit Distance Requires Exponential Distortion in L₁ Embeddings

A one-position shift can make two binary strings look maximally different when compared bit by bit, yet nearly identical under edit distance. For example, 01010101 and 10101010 differ at all eight fixed positions. But deleting the first zero and inserting it at the end transforms one into the other in two edits. Insertions, deletions, and substitutions each cost one.

That gap makes edit distance difficult to represent as ordinary numerical vectors. The manuscript’s central claim is that the difficulty has matching upper and lower scales: any embedding of short words into L₁The space whose distance is the sum of absolute coordinate differences. must incur substantial distortion, but an embedding with distortion on that same asymptotic scale exists.

The map must be a single injective representation of every word up to a length cap D, including the empty word. After rescaling, its L₁ distance for every pair must be at least their edit distance and at most D times that distance. The manuscript defines the best possible distortion as the infimum over such maps. For sufficiently large D, it places this quantity between exp(c√(log D · log log D)) and exp(C√(log D · log log D)), for positive absolute constants c and C. The constants remain absolute even as the finite alphabet grows with D; the alphabet must contain at least two symbols. For the lower bound, binary words of one common length already suffice.^†

The lower-bound construction begins with phases arranged around finite circles. In a twelve-site example, half the sites are ones and half zeros. Shifting the marked half by one site changes only two bits; turning it halfway around changes all twelve. The construction places phases at the leaves of a tree, then builds longer words by joining child words into rows with distinct tags and repeating translated rows.

Some translations are cheap in edit distance because they shift the long row lists. Changing one leaf affects only its share of the whole word. The difficulty is proving that turning every leaf halfway around still costs many edits under any alignment, not just the obvious position-by-position comparison.

To count the cost, let E be the total number of unmatched positions on either side of an alignment, and let N be the common word length. An alignment matches equal symbols in increasing order on both strings. Suppose a source row matches into two different target rows. Select consecutive matches around the point where the alignment crosses between target rows. Because tags must match, the tag index cannot go backward. Advancing to the next target row therefore leaves a gap of at least t−1 blocks, each of length L. Every position in that gap is unmatched: a match inside it would fall between the selected consecutive matches.

With three tags and two positions per block, the gap contains at least four unmatched positions. More generally, each split row forces an unmatched interval. The intervals charged to different source rows cannot overlap, because the alignment is increasing. Thus at most E/((t−1)L) rows can split, and their source positions account for at most tE/(t−1) positions.

The remaining, nonsplit rows occupy at least N−tE/(t−1) positions. If each loses at least a fraction A of its positions—including rows with no matches—their losses contribute at least A(N−tE/(t−1)) unmatched positions. Those losses are included in E, so rearranging gives E ≥ AN/(1 + tA/(t−1)). This tagged-row argument lets local separation survive alignments that cross row boundaries.

The manuscript describes two circle constructions that arrange prime periods differently. One uses complete residue groups and resets phase denominators during a descent; the other lets each prime translation move every child except its own. Both combine cheap shifts with costly half-turns. To constrain any L₁ map, the paper decomposes distances into nonnegative weighted yes-or-no cuts, then uses Fourier analysis to turn translation rules into constraints on integer frequencies at the leaves. The prime constraints force enough nonzero frequency through the tree. Comparing those constraints with weighted single-leaf shifts means a map cannot keep half-turns far apart and all cheap shifts cheap unless its distortion grows. The denominator and Fourier estimates are not developed in the circle illustration.

The circle construction uses a larger alphabet, so the manuscript gives two ways to replace each tagged letter with a binary block of logarithmic width. A single code is chosen for a given input length. For equal-length inputs, the encoded subsequence deficit—the length minus the longest common subsequence—lies between a constant times the block width times the original deficit and the block width times that deficit.

This yields edit-distance preservation up to an absolute distortion factor for equal-length inputs. The two arguments recover letter matches differently: one uses separated intervals and a common offset; the other uses equal-index anchors. The lower guarantee is for equal-length inputs. No explicit codewords are displayed, and the stated lower guarantee does not extend to unequal lengths.

For the upper bound, the manuscript develops an overlapping-substring method associated with Ostrovsky and Rabani. Words are split into blocks, and overlapping windows are listed at several scales. Shorter windows are embedded recursively; at each scale, the construction counts how many windows fall into each part of a partition, preserving repeated occurrences.

The shift example shows why overlap helps. Of three windows in a block, two remain identical after the shift, leaving only one occurrence on each side to account for. More generally, blocks away from the endpoints of a deletion and insertion can be paired almost perfectly. For sufficiently separated blocks, some scale makes cross-window pairs far apart, so their histograms are often disjoint.

The resulting vector includes every partition outcome, weighted by its probability. It is a deterministic, finite-dimensional map fixed over the full finite domain—not a fresh randomized map for each pair of words.

The lower construction yields logarithmic distortion at least a constant times H log H, while its word length has logarithm at most a constant times H² log H. Choosing H to fit the length cap produces the square-root logarithmic exponent. The upper recursion balances branching against depth and reaches the same scale, potentially with a different constant. Fresh-symbol padding brings every shorter word, including the empty word, into the domain.

The result is matching exponential scales, not exact distance preservation or an exact leading constant. A full Lean reproduction has not been run in the stated environment.