Tree Constructions for the l1 Distortion of Binary Edit Distance

We give two independent constructions of binary words of one length at most d whose ordinary edit-distance metrics require ℓ${}_1$ distortion $\exp (\Omega (\sqrt{\log d\log \log d}))$ for every sufficiently large d. We also prove a constant-distortion binary conversion for one prescribed input length. Together with the companion upper embedding theorem, these lower bounds determine the order of logarithmic distortion uniformly over finite alphabets with at least two symbols.