Let Sigma be a finite alphabet. A string is a finite sequence of letters from
Sigma. The length of x is written |x|. The empty string is eps.
For strings x,y, let ED(x,y) be the usual edit distance: the least number of
single-letter insertions, deletions, and substitutions that turn x into y.
Every operation costs one. Let Delta(x,y) be the insertion-deletion distance:
the least number of single-letter insertions and deletions that turn x into y.
Substitutions are not allowed.
Write l1 for the real vector space of absolutely summable sequences, with norm
||v||_1 = sum_n |v_n|.
For a finite set X and an injective map f:X -> l1, the distortion of f is
max_{x != y} ( ||f(x)-f(y)||_1 / ED(x,y) )
*
max_{x != y} ( ED(x,y) / ||f(x)-f(y)||_1 ).
The two factors measure expansion and contraction. A map has distortion at
most D exactly when it can be rescaled so that
ED(x,y)/D <= ||f(x)-f(y)||_1 <= ED(x,y)
for all distinct x,y.
For d >= 1, let Sigma^{<=d} be the set of all strings of length at most d,
including eps. Define E_Sigma(d) to be the infimum of the distortion over all
injective maps from Sigma^{<=d} into l1. The target dimension is not restricted,
and the map need not be computable.
Theorem. There are absolute constants c,C > 0 and an integer d0 such that, for
every d >= d0 and every finite alphabet Sigma with |Sigma| >= 2,
exp( c * sqrt( log d * log log d ) )
<= E_Sigma(d) <=
exp( C * sqrt( log d * log log d ) ).
The lower bound is witnessed by a set of binary strings, all of one common
length at most d. The constants do not depend on Sigma, even if |Sigma| grows
with d. Logarithms are natural unless a base is written.
The single-symbol error model is classical. Levenshtein studied codes
correcting insertions, deletions and substitutions. Wagner and Fischer
described edit scripts through increasing traces. The alignment language is
essential: every lower bound must control every increasing matching of equal
symbols, including matchings that cross the boundaries used to construct the
strings.
https://www.mathnet.ru/eng/dan31411
https://doi.org/10.1145/321796.321811
Ostrovsky and Rabani proved the upper scale for fixed-length binary strings by
recursively comparing collections of overlapping substrings. The normalized
form needed is their Theorem 7.
"Theorem 7. There exists a universal constant c > 0 such that for every d in N
there exists an embedding phi: {0,1}^d -> l1 with distortion at most
2^{c sqrt(log d log log d)}."
https://web.cs.ucla.edu/~rafail/PUBLIC/68.pdf
Khot and Naor obtained an Omega(sqrt(log d / log log d)) lower bound by
studying cuts and Fourier analysis of noisy shifts. Krauthgamer and Rabani
proved an Omega(log d) lower bound for binary strings of length d. Andoni,
Deza, Gupta, Indyk and Raskhodnikova constructed binary subsets whose L1
distortion approaches 3/2. The recursive construction reaches the scale of the
Ostrovsky-Rabani exponent.
https://web.math.princeton.edu/~naor/homepage%20files/nonembed-final.pdf
https://doi.org/10.1137/060660126
https://www.cs.columbia.edu/~andoni/papers/k2n2.pdf
An increasing matching between x and y is a list of pairs (i,j) such that
x_i = y_j, and both i and j strictly increase from one pair to the next. Let
LCS(x,y) be the largest size of such a matching.
Lemma. For all finite strings x,y, including the empty string,
ED(x,y) <= Delta(x,y) <= 2 ED(x,y),
and
Delta(x,y) = |x| + |y| - 2 LCS(x,y).
If |x| = |y| = n, define the one-sided deficit
r_n(x,y) = n - LCS(x,y) = Delta(x,y)/2.
A matching of size n - E leaves exactly E unmatched positions on each side.
Proof. An insertion-deletion script is an edit script, so ED <= Delta.
Replace each substitution by one deletion and one insertion. This turns any
edit script into an insertion-deletion script of at most twice the cost, so
Delta <= 2 ED.
For the identity, take an increasing matching of size m. Delete the |x|-m
unmatched positions of x and insert the |y|-m unmatched positions of y. This
costs |x|+|y|-2m and transforms x into y. Hence Delta(x,y) <= |x|+|y|-2m for
every matching. Conversely, take an optimal insertion-deletion script. The
positions of x that survive and the positions of y that receive them form an
increasing matching of size m. The script has cost at least |x|+|y|-2m.
Minimizing over scripts gives Delta = |x|+|y|-2 LCS. The equal-length
statement follows by putting |x|=|y|=n and m=LCS. QED.
For a finite abelian group G and a map H:G -> l1, define the average
displacement
V_H(g) = E_{z in G} ||H(z+g) - H(z)||_1,
where the expectation is uniform over G.
Proposition. Let b,h >= 1, P >= 1, and let G_1,...,G_b be finite abelian
groups. Suppose v_j in G_j has order p_j, where p_1,...,p_b are distinct
primes in [P,2P]. Put
G = G_1 x ... x G_b,
tau = v_1 + ... + v_b,
where v_j is also used for the element that acts only in coordinate j. Then
for every H:G -> l1 and every integer u,
V_H(u v_1)
<= (2P)^{2h} V_H(tau)
+ (2/h) sum_{j=1}^b E_{a in Z/p_jZ} V_H(a v_j).
The proof uses two standard tools. The first writes a finite l1 metric as a
nonnegative sum of cut metrics. This cut representation is standard from
Linial, London and Rabinovich.
https://doi.org/10.1007/BF01200757
Lemma. Let X be finite and H:X -> l1. There are finite numbers c_A >= 0,
indexed by nonempty proper subsets A of X, such that for all x,y in X,
||H(x)-H(y)||_1
= sum_{empty != A proper subset of X}
c_A |1_A(x) - 1_A(y)|.
Moreover,
sum_A c_A <= sum_{{x,y} subset X, x != y} ||H(x)-H(y)||_1,
where the right sum is over unordered pairs.
Proof. If |X| <= 1 every sum is empty. Otherwise fix a coordinate n of H.
List the distinct values of H_n on X as t_1 < ... < t_k. Put
A_r = {x : H_n(x) > t_r},
a_r = t_{r+1} - t_r, for 1 <= r < k.
The gaps telescope:
|H_n(x)-H_n(y)|
= sum_{r=1}^{k-1} a_r |1_{A_r}(x)-1_{A_r}(y)|.
Group all terms with the same set A and set c_A equal to the sum of the
corresponding a_r over all coordinates. At first c_A may be +infinity. All
terms are nonnegative, so the coordinate sum may be interchanged with the
finite sum over unordered pairs. This gives
sum_A c_A |A| |X\A|
= sum_{{x,y}} sum_n |H_n(x)-H_n(y)|
= sum_{{x,y}} ||H(x)-H(y)||_1 < infinity.
Every indexed cut separates at least one pair, so |A||X\A| >= 1. Hence all
c_A are finite and their total is at most the right side. Summing the
coordinate identities and grouping nonnegative terms gives the displayed cut
identity. QED.
The second tool is the Fourier expansion on a product of cyclic groups.
Lemma. Let
T = (Z/p_1Z) x ... x (Z/p_bZ),
where each p_j >= 2. For lambda in T define
chi_lambda(t) = exp( 2 pi i sum_j lambda_j t_j / p_j ),
hat F(lambda) = E_{t in T} F(t) conjugate(chi_lambda(t)).
For every F:T -> C and every l in T,
E_{t in T} |F(t+l)-F(t)|^2
= sum_{lambda in T} |hat F(lambda)|^2
* 4 sin^2( pi sum_j l_j lambda_j / p_j ).
The squared sine does not depend on the integer representatives chosen for
lambda_j and l_j.
Proof. The identity
(1/p) sum_{a=0}^{p-1} exp(2 pi i q a / p)
= 1 if p divides q, and 0 otherwise
shows coordinate by coordinate that the characters chi_lambda are
orthonormal for the inner product
<F_1,F_2> = E_t F_1(t) conjugate(F_2(t)).
There are |T| characters and the function space has dimension |T|, so they
form a basis. Thus
F(t) = sum_lambda hat F(lambda) chi_lambda(t),
and the squared norm is the sum of squared Fourier coefficients. Apply this
to
F(t+l)-F(t)
= sum_lambda hat F(lambda) (chi_lambda(l)-1) chi_lambda(t),
and use |exp(2 pi i theta)-1|^2 = 4 sin^2(pi theta). QED.
Proof of the proposition. By the cut lemma, each displacement of H is a
nonnegative linear combination of displacements of Boolean cut maps. Both
sides of the desired inequality are linear in the cut weights, so it is
enough to prove the inequality for H = 1_A for a subset A of G.
Let K = <v_1> x ... x <v_b>, a subgroup of G. Every shift in the desired
inequality preserves every coset of K. On a fixed coset choose a
representative c and identify T = prod_j Z/p_jZ with the coset by
t -> c + sum_j t_j v_j.
The cut becomes F(t) = 1_A(c + sum_j t_j v_j). For Boolean values,
|F(t+l)-F(t)| = |F(t+l)-F(t)|^2.
Write
D_F(l) = E_t |F(t+l)-F(t)|^2.
It remains to prove
D_F(u e_1)
<= (2P)^{2h} D_F(1,...,1)
+ (2/h) sum_{j=1}^b E_{a in Z/p_jZ} D_F(a e_j),
where e_j is the jth coordinate vector.
Use the Fourier lemma. Compare the multipliers frequency by frequency. Fix
lambda in T, put S = {j : lambda_j != 0}, and r = |S|. If lambda_1 = 0,
the left multiplier is zero. Assume lambda_1 != 0. The left multiplier is
at most 4.
Case 1: r < h. Choose integer representatives 0 <= lambda_j < p_j and put
q = prod_{j in S} p_j,
theta = sum_{j in S} lambda_j / p_j.
For any i in S, the primes are distinct, so
q theta = lambda_i (q/p_i) mod p_i,
and this is not 0 mod p_i because lambda_i != 0 mod p_i and p_i does not
divide q/p_i. Hence theta is not an integer. Its denominator divides q,
so its distance delta from the nearest integer satisfies
1/2 >= delta >= 1/q >= (2P)^{-r} >= (2P)^{-h}.
On [0,pi/2], sine is concave, so sin(pi delta) >= 2 delta. Therefore the
simultaneous-shift multiplier is at least
(2P)^{2h} * 4 sin^2(pi theta)
= (2P)^{2h} * 4 sin^2(pi delta)
>= (2P)^{2h} * 16 delta^2
>= 16.
This bounds the left multiplier.
Case 2: r >= h. For each coordinate j, the geometric-series identity gives
E_{a in Z/p_jZ} 4 sin^2(pi a lambda_j / p_j)
= 2 - 2 Re E_a exp(2 pi i a lambda_j / p_j)
= 2 if j is in S, and 0 otherwise.
The component terms on the right therefore have combined multiplier
(2/h) * 2r >= 4,
again bounding the left multiplier.
Multiplying by |hat F(lambda)|^2 and summing over lambda proves the coset
inequality. Averaging over the equal-size cosets gives the uniform average
over G. Summing the nonnegative cut weights proves the proposition for H.
QED.
The construction builds the hard set of strings. At each level, a word is a
long list of rows. Moving all components by one step shifts the row list by
one, which is cheap. Moving only the distinguished component does not shift
the row list, and the lower-level words inside the rows stay far apart. The
marker symbol prevents a global alignment from sending one source payload
into several target rows.
Fix a large integer k and set
b = 100k,
P = b^2,
h = b/10 = 10k,
L = P^(b/2).
Choose b distinct primes in the interval [P,2P], and call this set Pool. The
interval estimate of Rosser and Schoenfeld supplies such primes for all
large k. The same pool and the same parameters are used at every level.
https://doi.org/10.1215/ijm/1255631807
For every 0 <= s <= k and every p in Pool, the construction supplies:
a finite abelian group G_{s,p},
a distinguished element v_{s,p} of order p,
a word map W_{s,p}: G_{s,p} -> A_{s,p}^{n_s},
a finite list S_{s,p} of pairs (e,r), where e is a step in G_{s,p}
and r > 0 is its displacement budget.
Here A_{s,p} is a finite alphabet and A_{s,p}^{n_s} is the set of strings
of length n_s over that alphabet. The word map need not be injective.
Define
alpha_s = 24^{-s},
Q_0 = 2,
Q_s = 2(2P)^{2h}/L + Q_{s-1}/h for s >= 1.
Proposition. The families can be chosen with
n_s = (2(2b-1)L)^s,
|A_{s,p}| <= A_s,
A_0 = 2P,
A_s = 1 + (2b-1) A_{s-1},
so that assertions (1), (2), (3) hold for every p in Pool.
(1) Every listed step is cheap at every state:
Delta(W_{s,p}(z), W_{s,p}(z+e)) <= n_s r
for every (e,r) in S_{s,p} and every z in G_{s,p}.
(2) Every nonzero distinguished shift is separated at every state:
Delta(W_{s,p}(z), W_{s,p}(z+u v_{s,p})) >= n_s alpha_s
for every z in G_{s,p} and every 1 <= u < p.
(3) If H:G_{s,p} -> l1 satisfies the averaged budgets
V_H(e) <= r for every (e,r) in S_{s,p},
then
V_H(u v_{s,p}) <= Q_s for every 1 <= u < p.
Assertions (1) and (2) describe the geometry of the words. Assertion (3)
says that any l1 map respecting the cheap-step budgets has small average
displacement in the separated direction.
Proof. All three assertions are proved by simultaneous induction on s. At
each level the word maps and the cheap-step lists are constructed together.
Base case s=0. Take
G_{0,p} = Z/pZ,
v_{0,p} = 1,
W_{0,p}(z) = (z),
S_{0,p} = {(e,2) : e != 0}.
The word (z) is a single symbol. Distinct symbols have insertion-deletion
distance two. Therefore for e != 0,
Delta(W_{0,p}(z), W_{0,p}(z+e)) = 2 = n_0 * 2,
so (1) holds with n_0=1. Also for 1 <= u < p, z+u != z, so
Delta(W_{0,p}(z), W_{0,p}(z+u)) = 2 >= n_0 alpha_0 = 1,
and (2) holds. For (3), if V_H(e) <= 2 for every e != 0, then in
particular V_H(u) <= 2 = Q_0 for every 1 <= u < p. The alphabet has
p <= 2P = A_0 symbols.
Induction step. Suppose the families at level s-1 have been constructed.
To build the family indexed by p, enumerate the pool as p_1,...,p_b with
p_1=p. Abbreviate
G_j = G_{s-1,p_j},
v_j = v_{s-1,p_j},
W_j = W_{s-1,p_j},
m = n_{s-1}.
Set
G_{s,p} = G_1 x ... x G_b,
v_{s,p} = (v_1,0,...,0).
Since v_1 has order p_1=p, the element v_{s,p} has order p.
For z=(z_1,...,z_b), the new word is a concatenation of L rows, indexed
by i=0,...,L-1. Row i begins with a payload of 2b-1 slots.
The first b slots contain separately tagged copies of W_1(z_1+i v_1).
The remaining b-1 slots contain tagged copies of W_j(z_j+i v_j) for
j=2,...,b, in that order. Each slot has its own tag. Tags are fixed
across all rows and different from every other slot tag.
The payload length is
B = (2b-1)m.
Append a marker #^B, where # is a fresh symbol absent from all payloads.
More formally, the new alphabet is the disjoint union of {#} and one set
{r} x A_{s-1,p_j} for each slot r carrying component j. This also tags
every lower-level marker, so none of them becomes the new symbol #.
The full length and alphabet bounds are
n_s = 2BL = 2(2b-1)L n_{s-1},
|A_{s,p}| <= 1 + (2b-1) A_{s-1}.
These match the formulas in the proposition.
There are two kinds of cheap steps.
First include the simultaneous step
tau = (v_1,...,v_b)
with budget 2/L. Row i of the word at z+tau is row i+1 of the word at z
for 0 <= i < L-1. To transform one word into the other, delete the first
row and insert one final row. The cost is at most
2 * (2B) = 4B = 2 n_s / L.
Thus the simultaneous step is cheap with budget 2/L.
For the other steps, put c_1=b and c_j=1 for j >= 2. Define
omega_j = c_j m / (2B).
Then
sum_{j=1}^b omega_j
= (bm + (b-1)m)/(2B)
= (2b-1)m/(2B)
= 1/2.
The number omega_j is the fraction of the full word occupied by component
j. The markers occupy the other half.
For each old cheap step (e,r) in S_{s-1,p_j}, include its lift e~ to
coordinate j with budget omega_j r. The level s-1 bound holds at
every translated state z_j+i v_j. Editing the L c_j affected slots
separately costs at most
L c_j m r = n_s omega_j r.
This proves (1).
The fresh markers supply a matching argument that separates rows. It
converts a comparison of every pair of payloads into
a comparison of the full row lists.
Lemma. Let T,p,q >= 1 be integers, let Gamma be an alphabet, and let # be a
symbol not in Gamma. For strings U_a,V_b in Gamma^p with 1 <= a,b <= T, put
X = U_1 #^q U_2 #^q ... U_T #^q,
Y = V_1 #^q V_2 #^q ... V_T #^q,
N = T(p+q).
If d >= 0 and r_p(U_a,V_b) >= d for every a,b, then
r_N(X,Y) >= T d q / (d+q) >= (T/2) min(d,q).
In particular, if d <= q, then Delta(X,Y) >= T d.
Proof. Fix an increasing matching, and let E be the number of unmatched
positions on each side. No source payload symbol can match a target marker.
Let s be the number of source payloads whose matches reach at least two
target payloads.
A source payload whose matches lie in one target payload loses at least d
source positions. A payload with no matches loses p >= d positions.
Summing over these T-s payloads gives
E >= d(T-s).
For each of the other s payloads, choose a target marker between two of its
matches. The entire marker is unmatched: a matched target position between
the two chosen matches would have its source partner between their source
partners, inside this source payload, where # does not occur. The target
matched spans of different source payloads are ordered and disjoint, so the
chosen markers are distinct. Thus
E >= s q.
Combining the two estimates gives
E >= d(T-E/q),
hence
E >= T d q / (d+q).
The latter is at least (T/2) min(d,q). This holds for every matching,
including when d=0, and proves the displayed inequality. Finally,
Delta(X,Y)=2 r_N(X,Y). QED.
Apply the lemma to the words at z and at z+u v_{s,p}, where 1 <= u < p_1.
Compare source payload i with target payload i', and write
delta = i' - i.
The relative shifts are
(delta+u) v_1 in component 1,
delta v_j in component j >= 2.
At least b/3 slots have a nonzero shift. To see this, first suppose that p_1
does not divide delta+u. Then all b copies of component 1 have a nonzero
shift. Otherwise p_1 divides delta+u. Since 1 <= u < p_1, this implies
delta != 0 mod p_1, so delta != 0.
Now 0 < |delta| < L = P^(b/2). The product of b/2 distinct primes from the
pool is at least P^(b/2) = L. Therefore fewer than b/2 pool primes can
divide delta. Among the components 2,...,b, at least b/3 have a nonzero
shift.
In each such slot, the induction hypothesis gives insertion-deletion
distance at least m alpha_{s-1}. A matching of the two complete length-m
slot words therefore leaves at least m alpha_{s-1}/2 source positions
unmatched. Since the slot tags are disjoint, every matching between the two
payloads restricts to a matching of the corresponding complete slot words.
Its size is bounded by their LCS even if other source payloads use some
positions of the same target slot.
Thus every pair of payloads has one-sided deficit at least
d_s = alpha_{s-1} b m / 6.
Since d_s <= B, the marked-payload lemma, with T=L and marker length B,
gives
Delta(W_{s,p}(z), W_{s,p}(z+u v_{s,p})) >= L d_s.
Dividing by the row length n_s = 2BL,
Delta(...) / n_s
>= d_s / (2B)
= (alpha_{s-1} b m / 6) / (2(2b-1)m)
= alpha_{s-1} b / (12(2b-1))
>= alpha_{s-1} / 24
= alpha_s.
This proves the pointwise separation (2).
Suppose H:G_{s,p} -> l1 meets the listed
averaged budgets. The level s-1 assertion is needed for one
component, but its hypotheses concern averages over that component's entire
state group. The right map is a direct sum over all settings of the other
components.
For fixed j, let
Y_j = product_{ell != j} G_ell
and define
T_j(x) = (1/(omega_j |Y_j|)) direct_sum_{y in Y_j} H(x,y),
x in G_j.
Here H(x,y) means that x occupies coordinate j, and the finite direct sum
of sequence spaces is identified with l1. For every e in G_j, additivity of
the sum norm gives
V_{T_j}(e)
= (1/omega_j) E_{x in G_j, y in Y_j}
||H(x+e,y)-H(x,y)||_1
= V_H(e~)/omega_j.
The lifted step budgets therefore make T_j satisfy all the level s-1
hypotheses at once. The induction assertion yields
V_H(a v_j) <= omega_j Q_{s-1} for 0 <= a < p_j.
The case a=0 is immediate.
Apply the displacement proposition to the factors G_j and their
distinguished elements. The simultaneous budget, the component control, and
sum_j omega_j=1/2 give
V_H(u v_{s,p})
<= (2P)^{2h} V_H(tau)
+ (2/h) sum_{j=1}^b E_{a in Z/p_jZ} V_H(a v_j)
<= (2P)^{2h} (2/L)
+ (2/h) sum_{j=1}^b omega_j Q_{s-1}
= 2(2P)^{2h}/L
+ (2/h)(1/2) Q_{s-1}
= 2(2P)^{2h}/L + Q_{s-1}/h
= Q_s.
This proves (3) and completes the simultaneous induction.
The quotient alpha_s/Q_s measures the obstruction to embedding the word
image. Indeed, let f: W_{s,p}(G_{s,p}) -> l1 have distortion D, normalized
so that
ED(x,y)/D <= ||f(x)-f(y)||_1 <= ED(x,y).
Define H = f o W_{s,p} / n_s. Then H satisfies the listed budgets by
ED <= Delta and the cheap-step property. On the other hand, the far property
and ED >= Delta/2 give
alpha_s/(2D) <= V_H(v_{s,p}) <= Q_s,
so
D >= alpha_s/(2Q_s).
It remains to estimate this quotient and retain it when the growing alphabet
is replaced by binary symbols.
The binary encoding replaces each letter by a binary block whose width is
logarithmic in the alphabet size. The code expands insertion-deletion
distance by at most its width and contracts it by at most a factor two. The
pattern 11 marks the start of a genuine letter block. This prevents a bit
matching from matching parts of different letter blocks.
Lemma. Let A be an alphabet with A >= 2 letters. Put
t = ceil(log_2 A),
w = 2t + 3.
Assign distinct labels (a_1,...,a_t) in {0,1}^t to the letters of A. For a
letter a, let c(a) be the binary word
110 a_1 0 a_2 0 ... a_t 0 .
Extend c by concatenation to all finite strings, with c(eps)=eps. Then
(1/2) Delta(x,y) <= Delta(c(x),c(y)) <= w Delta(x,y)
for all x,y.
For an integer D >= 0 and |x| <= D, set
c_D(x) = c(x) 0^{w(D-|x|)} in {0,1}^{wD}.
Then
(1/2) Delta(x,y) <= Delta(c_D(x),c_D(y)) <= 2w Delta(x,y)
whenever |x|,|y| <= D.
Proof. Both lower bounds are proved at once for
U = c(x) 0^r,
V = c(y) 0^s,
where r,s >= 0 are arbitrary integers.
The pattern 11 occurs exactly at the start of a genuine letter block. Zeros
separate the label bits, every block ends in zero, and the added suffixes
contain only zeros. Thus 11 is a reliable block marker.
Fix an increasing bit matching. Let a_U and a_V be the numbers of unmatched
positions on the two sides, and put a=a_U+a_V. Call a genuine block good if
all of its bits are matched and their partners occupy consecutive positions.
On either one side, at most a genuine blocks are not good. For the U side, a
block containing an unmatched bit can be charged to one such bit. Distinct
blocks receive distinct charges, so this accounts for at most a_U blocks.
Any other non-good block has all its bits matched, but some two consecutive
block positions have partners separated by a nonempty open interval in V.
Every bit in that interval is unmatched, since a partner would have to lie
between consecutive positions in U. Charge one bit in the interval. The
intervals for distinct blocks are disjoint by monotonicity, so this accounts
for at most a_V more blocks. The argument includes skipped intervals
containing whole blocks or padding. Interchanging the two strings gives the
same bound on the V side.
A good block begins with matched bits 11. Its consecutive partners therefore
start at a genuine block boundary on the other side. There are exactly w
partners, so they form that entire block. The two blocks are equal and encode
the same letter. The target block is itself good. The same argument in
reverse shows that the good blocks on the two sides pair bijectively, in
increasing order. They give a letter matching between x and y whose loss is
the number of non-good genuine blocks, at most 2a. The alignment lemma yields
Delta(x,y) <= 2a.
But a is exactly the insertion-deletion distance between U and V. Hence
(1/2) Delta(x,y) <= Delta(U,V).
This proves both lower bounds, including empty strings and independently
chosen zero suffixes.
For the unpadded upper bound, implement each letter insertion or deletion by
w bit operations. For the padded bound, put r=w(D-|x|) and s=w(D-|y|).
Transform the coded prefix while retaining its suffix, then adjust the suffix
length:
Delta(c(x)0^r, c(y)0^s)
<= Delta(c(x),c(y)) + |r-s|
<= w Delta(x,y) + w ||x|-|y||
<= 2w Delta(x,y).
The last inequality follows because one insertion or deletion changes length
by one. QED.
The recurrence for Q_s is bounded first. For sufficiently large k, 2P <=
P^{3/2}. Put
eta = 2(2P)^{2h}/L.
Then
eta
<= 2 P^{3h} / P^{b/2}
= 2 P^{3h-b/2}
= 2 P^{-b/5}
<= P^{-b/6}
<= h^{-k}.
For the last inequality, P=b^2, so
P^{b/6} = b^{b/3} = b^{(100/3)k} >= (b/10)^k = h^k.
Since h >= 2, solving the recurrence gives
Q_k
= 2h^{-k} + eta sum_{j=0}^{k-1} h^{-j}
<= 2h^{-k} + 2 eta
<= 4h^{-k}.
The alphabet recurrence gives
A_s <= (2P+1)(2b)^s.
Indeed, the base case is immediate, and
1 + (2b-1)A_{s-1}
<= 1 + (2b-1)(2P+1)(2b)^{s-1}
<= (2P+1)(2b)^s.
Hence
log A_k = O(k log k).
Fix a prime p in Pool and apply the binary delimiter lemma to the alphabet
of W_{k,p}, without padding. Write enc for the resulting concatenated code.
Its width is
w = O(k log k).
All encoded words have the same length
N_k = w n_k
= w (2(2b-1) P^{b/2})^k,
and
log N_k <= C_len k^2 log k
for an absolute constant C_len and all sufficiently large k.
Proposition. For all sufficiently large k, every l1 embedding of
W_k = { enc(W_{k,p}(z)) : z in G_{k,p} }
subset {0,1}^{N_k}
has distortion at least
(h/24)^k / (16w)
>= exp(c_0 k log k)
for an absolute constant c_0 > 0.
Proof. Let f be an injective embedding of W_k with distortion D. Rescale it
so that
ED(x,y)/D <= ||f(x)-f(y)||_1 <= ED(x,y)
for all x,y in W_k. Define
H(z) = f(enc(W_{k,p}(z))) / (w n_k).
For every listed step (e,r), the code's upper bound and the cheap-step
property give, at each state,
||H(z+e)-H(z)||_1
<= ED(enc(W(z+e)), enc(W(z))) / (w n_k)
<= w Delta(W(z+e), W(z)) / (w n_k)
<= r.
Thus H meets the averaged hypotheses of the recursive proposition.
For v=v_{k,p}, the lower bounds give, again at every state,
||H(z+v)-H(z)||_1
>= ED(enc(W(z+v)), enc(W(z))) / (D w n_k)
>= Delta(enc(W(z+v)), enc(W(z))) / (2 D w n_k)
>= Delta(W(z+v), W(z)) / (4 D w n_k)
>= 24^{-k} / (4 D w).
In particular, these designated pairs represent distinct words, although
other state pairs may coincide. Averaging and using the l1 control and the
bound on Q_k gives
24^{-k}/(4Dw) <= V_H(v) <= 4h^{-k}.
Therefore
D >= (h/24)^k / (16w).
Since h=10k and w=O(k log k), the logarithm of the last expression is
k log k - O(k) - O(log k).
It is at least c_0 k log k for all sufficiently large k. QED.
A witness is now chosen for every sufficiently large cap. Set t=log d and
fix a>0 small enough that
C_len a^2 <= 1/2.
Choose
k = floor( a sqrt( t / log t ) ).
For sufficiently large d, this depth is available and log k <= log t. The
bound on log N_k gives
log N_k
<= C_len k^2 log k
<= C_len a^2 t
<= t,
so N_k <= d. After increasing the threshold on d,
k >= (a/2) sqrt( t / log t ),
log k >= (1/3) log t,
k log k >= (a/6) sqrt( t log t ).
The binary lower bound therefore gives
exp( c sqrt( log d * log log d ) )
for binary strings, with c=c_0 a/6. This direct choice of k uses no estimate
on gaps between successive lengths N_k.
Finally, choose two letters in any finite alphabet Sigma of size at least
two. The strings over those two letters form an isometric copy of binary edit
distance. One inequality follows because every binary edit script is also a
Sigma-script. For the reverse inequality, project all other letters to one of
the chosen letters; each operation in a Sigma-script becomes at most one
binary edit. Restricting an embedding to this subspace gives
E_Sigma(d) >= E_{0,1}(d).
Thus the lower bound holds for every finite alphabet of size at least two.
The upper bound uses one published embedding theorem. The normalized form
needed is the fixed-length binary result of Ostrovsky and Rabani.
Theorem. There is an absolute constant C_0 such that, for every integer
m >= 3, there is a map
g_m : {0,1}^m -> l1
satisfying
ED(u,v) <= ||g_m(u)-g_m(v)||_1 <= D_m ED(u,v),
where
D_m = exp( C_0 sqrt( log m * log log m ) ).
Here ED permits unit-cost substitutions as well as insertions and deletions.
https://web.cs.ucla.edu/~rafail/PUBLIC/68.pdf
On the finite domain {0,1}^m, the minimum pairwise ratio of image distance to
edit distance is positive. Dividing by that ratio makes the theorem
noncontracting without changing distortion. The expression for D_m is
written with natural logarithms. Increasing C_0 absorbs any finite set of
small lengths m >= 3.
Proposition. There is an absolute constant C such that, for every finite
alphabet Sigma with |Sigma| >= 2,
E_Sigma(d) <= exp( C sqrt( log d * log log d ) )
for d >= 3. Moreover,
E_Sigma(1) = 1,
1 <= E_Sigma(2) <= 2.
Proof. Fix d >= 1 and put q=4d^2. Choose a map
h : Sigma -> [q]
by assigning independent uniform labels to the letters. Apply h letter by
letter to strings.
Equal original letters remain equal after relabeling. Therefore every
original increasing matching remains valid, and for every outcome,
Delta(h(x),h(y)) <= Delta(x,y).
Now fix a pair x,y in Sigma^{<=d}. Let S be the set of letters appearing in
either string. Since |S| <= 2d, the union bound gives
Pr(h is not injective on S)
<= binomial(|S|,2)/q
<= (2d)(2d-1)/(8d^2)
< 1/2.
When h is injective on this pair's letters, equality of symbols is preserved
in both directions. The available increasing matchings are then exactly the
same, so
Delta(h(x),h(y)) = Delta(x,y).
For the alphabet [q], use the delimiter code with
t = ceil(log_2 q),
w = 2t + 3,
m = wd.
Since m >= 7, the Ostrovsky-Rabani theorem applies. For every h, the
padded string c_d(h(x)) has length m. The metric comparisons and the hash
contraction give
||g_m(c_d(h(x))) - g_m(c_d(h(y)))||_1
<= D_m Delta(c_d(h(x)), c_d(h(y)))
<= 2w D_m Delta(h(x),h(y))
<= 2w D_m Delta(x,y)
<= 4w D_m ED(x,y).
On the event where h is injective on S, the reverse estimate is
||g_m(c_d(h(x))) - g_m(c_d(h(y)))||_1
>= ED(c_d(h(x)), c_d(h(y)))
>= (1/2) Delta(c_d(h(x)), c_d(h(y)))
>= (1/4) Delta(h(x),h(y))
= (1/4) Delta(x,y)
>= (1/4) ED(x,y).
Let H be the finite set of all q^{|Sigma|} label maps, with probabilities
p_h = q^{-|Sigma|}.
Define
F(x) = direct_sum_{h in H} p_h
( g_m(c_d(h(x))) - g_m(0^m) ).
This finite direct sum is an l1 vector, and the sum norm gives the exact
identity
||F(x)-F(y)||_1
= E_h ||g_m(c_d(h(x))) - g_m(c_d(h(y)))||_1.
Taking expectations in the upper and lower estimates, and using that the good
event has probability greater than 1/2, yields
(1/8) ED(x,y)
<= ||F(x)-F(y)||_1
<= 4w D_m ED(x,y).
Thus F is injective and has distortion at most 32wD_m. The empty string has
image zero, since its padded code is 0^m. Its distance bounds are included in
the same calculation.
For d >= 3, w=O(log d) and m=O(d log d) with absolute constants. Therefore
log(32wD_m)
= O(log log d)
+ O( sqrt( log m * log log m ) )
= O( sqrt( log d * log log d ) ).
This proves the displayed upper bound, enlarging the absolute constant for
finitely many initial values if necessary.
For d=1, all distinct strings in Sigma^{<=1} have edit distance one, and
x -> e_x/2 is isometric. Hence E_Sigma(1)=1. In general, every nonzero edit
distance between strings of length at most d lies between one and d:
substitute the common-length part and then insert or delete the remaining
symbols. The same coordinate-vector map has distortion at most d, giving
E_Sigma(2) <= 2. Distortion is always at least one. QED.
The lower and upper bounds coincide up to absolute constants in the exponent.