diff 7fbef52..a2bebc5 edit_distance_l1_matching_v2.txt
diff --git a/edit_distance_l1_matching_v2.txt b/edit_distance_l1_matching_v2.txt
index ffbd524..0ed019f 100644
--- a/edit_distance_l1_matching_v2.txt
+++ b/edit_distance_l1_matching_v2.txt
@@ -1,28 +1,13 @@
-EDIT DISTANCE IN l1: MATCHING BOUNDS UP TO CONSTANTS IN THE EXPONENT
+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.
-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
+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.
-
-Delta(x,y) is the insertion-deletion distance: the least number of
-single-letter insertions and deletions 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
+Write l1 for the real vector space of absolutely summable sequences, with norm
||v||_1 = sum_n |v_n|.
@@ -32,49 +17,68 @@ For a finite set X and an injective map f:X -> l1, the distortion of f is
*
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
+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.
+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,
+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.
+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
-Logarithms are natural unless a base is written.
+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.
-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.
+https://web.math.princeton.edu/~naor/homepage%20files/nonembed-final.pdf
-===============================================================================
-2. ALIGNMENTS, CUTS, AND FOURIER
-===============================================================================
+https://doi.org/10.1137/060660126
-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.
+https://www.cs.columbia.edu/~andoni/papers/k2n2.pdf
-LEMMA 1 (Alignments). For all finite strings x,y, including the empty
-string,
+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),
@@ -88,20 +92,19 @@ If |x| = |y| = n, define the one-sided deficit
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.
+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
@@ -110,26 +113,28 @@ displacement
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
+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,
+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.
+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 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,
+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}
@@ -141,7 +146,7 @@ Moreover,
where the right sum is over unordered pairs.
-PROOF. If |X| <= 1 every sum is empty. Otherwise fix a coordinate n of H.
+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},
@@ -153,22 +158,22 @@ The gaps telescope:
= 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
+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 above.
-Summing the coordinate identities and grouping nonnegative terms gives
-the displayed cut identity. QED.
+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 4 (Finite Fourier displacement identity). Let
+Lemma. Let
T = (Z/p_1Z) x ... x (Z/p_bZ),
@@ -183,10 +188,10 @@ For every F:T -> C and every l in T,
= 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.
+The squared sine does not depend on the integer representatives chosen for
+lambda_j and l_j.
-PROOF. The identity
+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
@@ -196,20 +201,20 @@ 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
+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
+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
+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.
@@ -236,10 +241,10 @@ It remains to prove
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.
+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
@@ -280,27 +285,15 @@ 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.
+over G. Summing the nonnegative cut weights proves the proposition 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
+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
@@ -309,11 +302,11 @@ Fix a large integer k and set
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.
+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:
@@ -332,14 +325,14 @@ Define
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
+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 the following three assertions hold for every p in Pool.
+so that assertions (1), (2), (3) hold for every p in Pool.
(1) Every listed step is cheap at every state:
@@ -363,10 +356,10 @@ 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.
+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
+Base case s=0. Take
G_{0,p} = Z/pZ,
v_{0,p} = 1,
@@ -386,7 +379,7 @@ 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.
+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
@@ -427,7 +420,7 @@ The full length and alphabet bounds are
These match the formulas in the proposition.
-CHEAP STEPS. There are two kinds of cheap steps.
+There are two kinds of cheap steps.
First include the simultaneous step
@@ -456,7 +449,7 @@ 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
+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
@@ -464,15 +457,12 @@ separately costs at most
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.
+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 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
+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,
@@ -484,25 +474,24 @@ If d >= 0 and r_p(U_a,V_b) >= d for every a,b, then
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.
+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.
+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
+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.
@@ -518,39 +507,40 @@ 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
+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
+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.
+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.
+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.
+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
+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.
@@ -565,12 +555,11 @@ Dividing by the row length n_s = 2BL,
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.
+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
@@ -582,24 +571,24 @@ and define
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
+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
+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 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
+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)
@@ -611,7 +600,7 @@ give
= 2(2P)^{2h}/L + Q_{s-1}/h
= Q_s.
-This proves (3) and completes the simultaneous induction in Proposition 5.
+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
@@ -620,8 +609,8 @@ 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
+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,
@@ -629,29 +618,22 @@ 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
-===============================================================================
+It remains to estimate this quotient and retain it when the growing alphabet
+is replaced by binary symbols.
-4.1 A binary code with a fresh pattern
+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.
-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
+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
+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 .
@@ -671,42 +653,40 @@ Then
whenever |x|,|y| <= D.
-PROOF. We prove both lower bounds at once for
+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.
-Lemma 1 yields
+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.
@@ -717,23 +697,21 @@ But a is exactly the insertion-deletion distance between U and V. Hence
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:
+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
+The last inequality follows because one insertion or deletion changes length
+by one. QED.
-We first bound the recurrence for Q_s. For sufficiently large k, we have
-2P <= P^{3/2}. Put
+The recurrence for Q_s is bounded first. For sufficiently large k, 2P <=
+P^{3/2}. Put
eta = 2(2P)^{2h}/L.
@@ -771,9 +749,9 @@ 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
+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).
@@ -788,7 +766,7 @@ and
for an absolute constant C_len and all sufficiently large k.
-PROPOSITION 8. For all sufficiently large k, every l1 embedding of
+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}
@@ -800,8 +778,8 @@ has distortion at least
for an absolute constant c_0 > 0.
-PROOF. Let f be an injective embedding of W_k with distortion D. Rescale
-it so that
+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)
@@ -817,7 +795,7 @@ property give, at each state,
<= w Delta(W(z+e), W(z)) / (w n_k)
<= r.
-Thus H meets the averaged hypotheses of Proposition 5.
+Thus H meets the averaged hypotheses of the recursive proposition.
For v=v_{k,p}, the lower bounds give, again at every state,
@@ -828,8 +806,8 @@ For v=v_{k,p}, the lower bounds give, again at every state,
>= 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
+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}.
@@ -843,9 +821,8 @@ Since h=10k and w=O(k log k), the logarithm of the last expression is
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
+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.
@@ -853,8 +830,8 @@ 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
+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
@@ -867,36 +844,29 @@ so N_k <= d. After increasing the threshold on d,
log k >= (1/3) log t,
k log k >= (a/6) sqrt( t log t ).
-Proposition 8 therefore proves the lower bound
+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.
+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
+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
-===============================================================================
+Thus the lower bound holds for every finite alphabet of size at least two.
-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.
+The upper bound uses one published embedding theorem. The normalized form
+needed is the fixed-length binary result of Ostrovsky and Rabani.
-THEOREM 9 (Ostrovsky-Rabani, normalized form). There is an absolute
-constant C_0 such that, for every integer m >= 3, there is a map
+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
@@ -908,17 +878,18 @@ where
D_m = exp( C_0 sqrt( log m * log log m ) ).
-Here ED permits unit-cost substitutions as well as insertions and
-deletions.
+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.
+https://web.cs.ucla.edu/~rafail/PUBLIC/68.pdf
-PROPOSITION 10 (Uniform alphabet bound). There is an absolute constant C
-such that, for every finite alphabet Sigma with |Sigma| >= 2,
+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 ) )
@@ -927,7 +898,7 @@ 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
+Proof. Fix d >= 1 and put q=4d^2. Choose a map
h : Sigma -> [q]
@@ -939,17 +910,17 @@ 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
+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
+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).
@@ -959,9 +930,9 @@ For the alphabet [q], use the delimiter code with
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
+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)))
@@ -993,89 +964,32 @@ 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
+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.
+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
+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.
+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:
+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.
+The lower and upper bounds coincide up to absolute constants in the exponent.