EDIT DISTANCE IN l1: MATCHING BOUNDS UP TO CONSTANTS IN THE EXPONENT
This is a complete proof of the main theorem below, up to one stated
external embedding theorem. It is written for a reader who knows sets,
functions, and finite sums. Every symbol is defined before it is used.
===============================================================================
1. WHAT IS BEING PROVED
===============================================================================
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.
Two distances are used.
ED(x,y) is the usual edit distance: the least number of
single-letter insertions, deletions, and substitutions that turn x into y.
Every operation costs one.
Delta(x,y) is 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.
MAIN 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 already 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 proof has two halves. The lower half builds a hard finite set of
strings and proves that every l1 embedding of it must distort distances a
lot. The upper half uses one published embedding theorem for fixed-length
binary strings and reduces every finite alphabet and every length cap to
that case.
===============================================================================
2. ALIGNMENTS, CUTS, AND FOURIER
===============================================================================
We first record the elementary description of insertion-deletion distance
by increasing matchings. 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 1 (Alignments). 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 2 (Prime-product displacement inequality). 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.
LEMMA 3 (Finite cut decomposition). 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 we may interchange the coordinate sum with
the finite sum over unordered pairs. We get
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 above.
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 4 (Finite Fourier displacement identity). 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 PROPOSITION 2. By Lemma 3, 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 Lemma 4. 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 Proposition 2 for H.
QED.
The two cases explain the role of distinct prime periods. A frequency
that uses few components is detected by the simultaneous shift, because
its phase cannot be an integer. A frequency that uses many components is
detected by the sum of the component averages.
===============================================================================
3. THE RECURSIVE CONSTRUCTION
===============================================================================
This section builds the hard set of strings. The construction is recursive.
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 cheating by sending one source payload into several target
rows.
3.1 Parameters and the recursive statement
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.
For all large k such primes exist. The prime number theorem gives
pi(2P)-pi(P) ~ P/log P > b. The explicit interval estimate of Rosser and
Schoenfeld also gives this consequence. The same pool and the same
parameters are used at every level.
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 5 (Recursive properties). 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 the following three assertions 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. We prove all three assertions by simultaneous induction on s. At
each level we construct the word maps and the cheap-step lists 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.
CHEAP STEPS. 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 preceding level's 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).
3.2 Separation across row boundaries
We first isolate the matching argument supplied by the fresh markers. It
converts a comparison of every pair of payloads into a comparison of the
full row lists.
LEMMA 6 (Marked payloads). 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.
We now 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.
Their 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.
We have d_s <= B. Lemma 6, 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).
3.3 The averaged analytic recurrence
Suppose H:G_{s,p} -> l1 meets the listed averaged budgets. We need the
preceding level's assertion 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 preceding
level's 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 Proposition 2 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 in Proposition 5.
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.
===============================================================================
4. BINARY ENCODING AND THE LOWER BOUND
===============================================================================
4.1 A binary code with a fresh pattern
We replace each letter by a binary block whose width is logarithmic in the
alphabet size. The code below 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 7 (Binary delimiter code). 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. We prove both lower bounds 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.
Lemma 1 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.
4.2 The quantitative obstruction
We first bound the recurrence for Q_s. For sufficiently large k, we have
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 Lemma 7 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 8. 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 Proposition 5.
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, we obtain
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.
4.3 A witness 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 ).
Proposition 8 therefore proves the lower bound
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 half of the main theorem holds for every finite alphabet
of size at least two.
===============================================================================
5. THE UPPER BOUND
===============================================================================
The upper proof uses one published embedding theorem. We state the
normalized form needed here. This is the only external input in the whole
argument.
THEOREM 9 (Ostrovsky-Rabani, normalized form). 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.
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 10 (Uniform alphabet bound). 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.
We have m >= 7, so Theorem 9 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.
Together with the binary witnesses of Section 4, this proves the main
theorem.
===============================================================================
6. WHERE EACH INGREDIENT IS USED
===============================================================================
For a second reading, here is the logical map.
Lemma 1 turns insertion-deletion distance into increasing matchings and
gives the factor-two comparison with edit distance.
Proposition 2 is the analytic heart. It compares a shift in one prime
component with the simultaneous shift and with the average component
shifts. Cuts reduce the problem to Boolean functions. Fourier analysis
then treats each frequency according to how many prime components it
uses.
Lemma 6 is the geometric heart. Fresh markers force any alignment that
sends one payload into several rows to leave whole markers unmatched.
Proposition 5 combines the geometry and the analysis. Cheap row shifts
are bounded directly. A separated shift in the distinguished component
is bounded below by the induction hypothesis and Lemma 6. The averaged
l1 control follows from Proposition 2 and a slice argument.
Lemma 7 transfers the growing alphabet to binary symbols. The marker 11
keeps letter blocks aligned and costs only the code width.
Proposition 8 turns the recurrence into a distortion lower bound. The
quotient alpha_k/Q_k is exp(Omega(k log k)), while the binary word length
is exp(O(k^2 log k)). Choosing k from the cap d gives a witness for every
sufficiently large d.
Proposition 10 is the upper bound. It hashes the alphabet to a small
label set, encodes to one binary length, applies the Ostrovsky-Rabani
theorem, and averages over all hash maps by a direct sum. This makes the
bound uniform over all finite alphabets and includes the empty string.
===============================================================================
7. CONCLUSION
===============================================================================
The main theorem is proved. The lower bound is witnessed by binary
strings of one common length at most d. The upper bound holds uniformly
for every finite alphabet of size at least two. The exponent is
sqrt( log d * log log d )
up to absolute constants. This determines the exponential scale of
E_Sigma(d) up to constants in the exponent.
ACKNOWLEDGEMENT OF THE EXTERNAL THEOREM. The upper bound relies on
Theorem 9, the normalized Ostrovsky-Rabani embedding theorem. No other
external result is used. The lower bound is proved here from first
principles, using only finite sums, cuts, Fourier characters, and
increasing matchings.