An insertion or deletion shifts every later symbol of a word. Yet a
cyclic shift of a nonempty word by one position costs at most two
edits: delete the first letter, then insert it after the last. The gap
between word length and the cost of translating a word measures how
much structure sits outside a bounded number of edits, and underpins
every obstruction constructed below.
Let ED(x, y) denote the minimum number of single-symbol insertions,
deletions, and substitutions transforming x into y, each costing one
unit. For a finite alphabet Sigma with |Sigma| >= 2 and an integer cap
d >= 1, let Sigma^{<= d} be the set of all words of length at most d,
including the empty word. The cap constrains only endpoints:
intermediate words produced while editing may have arbitrary length.
Fix an injective map f from Sigma^{<= d} into l1, the real space of
absolutely summable sequences with summable-coordinate norm
||u - v||_1 = sum_i |u_i - v_i|. The distortion of f is
dist(f) = (max_{x != y} ||f(x) - f(y)||_1 / ED(x, y))
* (max_{x != y} ED(x, y) / ||f(x) - f(y)||_1).
The first factor measures the largest stretching, the second the
largest shrinking. Set E_Sigma(d) = inf_f dist(f), the infimum over
injective f. The question is how fast E_Sigma(d) grows with d.
Single-symbol error models enter coding theory through Levenshtein's
work on deletion and insertion correcting codes
https://www.mathnet.ru/eng/dan31411, and through Wagner and Fischer's
increasing traces
https://doi.org/10.1145/321796.321811, which represent an optimal
script on a grid of |x| by |y| entries. The theorem that follows fixes
the order of log E_Sigma(d).
THEOREM (main). There are absolute constants c, C > 0 and an integer
d_0 such that, for every integer d >= d_0 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 constants c and C do not depend on Sigma or on d. In fact neither
constant depends on |Sigma|, so the estimate holds even for alphabets
whose size grows with d, and the same bound applies to the supremum of
E_Sigma(d) over all finite alphabets with at least two letters. The two
exponents need not agree, since only the order of log E_Sigma(d) is
pinned down. All logarithms are natural unless a base is displayed.
The exponent sqrt(log d log log d) sits strictly between every fixed
power of log d and every positive power of d: as d -> infinity it
exceeds (log d)^{1/2 - eps} for every fixed eps > 0 and is dwarfed by
d^eps for every fixed eps > 0. Thus E_Sigma(d) is d^{o(1)} while still
growing faster than every fixed power of log d.
Earlier bounds. Ostrovsky and Rabani obtained a matching upper bound
for fixed-length binary words by recursively comparing multisets of
overlapping substrings
pdf/ostrovsky-rabani-2007.pdf. Their scheme, developed below into a
complete finite histogram embedding with alphabet-independent constants
and all shorter words included, produces one deterministic map that
attains the right-hand inequality of the theorem for every pair of
short words simultaneously.
For lower bounds, Andoni, Deza, Gupta, Indyk, and Raskhodnikova
exhibited binary sets whose l1 distortion approaches 3/2
pdf/andoni-deza-gupta-indyk-raskhodnikova-2003.pdf. Khot and Naor
obtained a (log d)^{1/2 - o(1)} lower bound from Fourier analysis of
cut metrics and noisy shifts
pdf/khot-naor-2006.pdf, and Krauthgamer and Rabani sharpened the exponent
to Omega(log d) on binary words of length d
https://doi.org/10.1137/060660126. The constructions below keep the
same cut-and-Fourier viewpoint but add translation constraints through
distinct prime periods. Those constraints force a large total leaf
frequency and push the lower bound past every fixed power of log d.
Alphabet reductions from larger alphabets to binary words appear in
the work of Bhattacharya, Dey, Goldenberg, and Koucky on the many
flavors of edit distance
pdf/bhattacharya-dey-goldenberg-koucky-2024.pdf, and in the
Hamming-to-edit construction of Bhattacharya, Dey, Goldenberg, Habib,
Haeupler, K. S., and Koucky
pdf/bhattacharya-et-al-2026.pdf. Long-interval separation as a local
matching condition already appears in the inner code of Schulman and
Zuckerman
https://doi.org/10.1109/18.796406, and self-matching control of shifted
overlaps is a defining feature of the synchronization strings of
Haeupler and Shahrasbi
pdf/haeupler-shahrasbi-2017.pdf.
Two constructions. The lower bound of the theorem splits into two
sources: a family of hard words whose l1 distortion grows like a large
power of the word-length parameter, with the constants of the theorem,
and a deterministic map that attains the upper bound for every pair of
short words.
For the lower side, both constructions start with a finite phase circle
G = (M^{-1} Z) / Z of M equally spaced points, containing 1/2 so that
the half-turn w = 1/2 is available. A state assigns one phase v_j in G
to every leaf j of a finite rooted tree. At each leaf the word records
a translated half-circle on G; at each internal node the word
concatenates rows of tagged child words, each row shifted by a phase
determined from a row index through distinct primes attached to the
children. The tags guarantee that a match between two characters on the
same child index is the only alignment the two words admit.
Three edit costs drive the argument. Translations in a specified
subgroup move the row lists at negligible cost. Moving a single leaf by
a phase theta changes only the fraction of the word occupied by that
leaf, at cost proportional to theta. A simultaneous half-turn at every
leaf must have large edit cost under any alignment. The last assertion
requires the tagged-rows lemma, which converts any per-row lower bound
into a global deficiency estimate.
To compare edit costs on G^r with an arbitrary l1 image, the finite
metric of G^r is decomposed as a nonnegative sum of cut distances and
then expanded in characters of G^r. Each character carries one integer
frequency per leaf. Averaging over the cheap subgroup controls the
total weight of characters nonconstant on it. Among the remaining
characters, one that detects the half-turn must have large total
absolute leaf frequency, and single-leaf translations then force large
distortion. Two arithmetic branching arguments, based first on complete
residue systems and second on omitted coordinates, supply the necessary
inequality in the two constructions.
For the upper side, the recursion of Ostrovsky and Rabani is developed
into a complete finite construction, first at power lengths and then at
actual window lengths. Either form, together with fresh-symbol padding
to the cap d, yields the required map.
Metrics. A common subsequence of x and y is a set of equal-symbol
pairs whose position indices increase strictly on both sides. Let
LCS(x, y) be the largest possible such set. The elementary identity,
proved by counting the survivors of an optimal script, is
Delta(x, y) = |x| + |y| - 2 LCS(x, y), where Delta(x, y) denotes the
minimum number of single-symbol insertions and deletions, with
substitutions forbidden, transforming x into y.
LEMMA (metric comparisons). For all finite words x, y,
q(x, y) <= ED(x, y) <= 2 q(x, y),
ED(x, y) <= |x| + |y| - 2 LCS(x, y) <= 2 ED(x, y),
where q(x, y) = max(|x|, |y|) - LCS(x, y). In particular, when
|x| = |y| = n and r_n(x, y) = n - LCS(x, y),
r_n(x, y) <= ED(x, y) <= 2 r_n(x, y).
Proof. In any script of k edits, at least |x| - k original letters of x
survive in their original order. Those survivors form a common
subsequence of x and y, so LCS(x, y) >= |x| - k, hence k >= q(x, y).
Applying the same observation to the reverse script yields the same
bound for y, so the inequality holds for every script of k edits.
Deleting from x every symbol outside a longest common subsequence and
then inserting the missing letters of y produces a script of length
|x| + |y| - 2 LCS(x, y), which is therefore at most 2 q(x, y).
Survivor counts show that no insertion-deletion script can be shorter,
so the displayed middle expression equals Delta(x, y). Replacing each
substitution by one deletion followed by one insertion gives
Delta <= 2 ED, and inserting one substitution in place of any
deletion-plus-insertion pair gives ED <= Delta. QED
The deficit r_n(x, y) counts the unmatched positions on either side of
a longest common subsequence. All lower bounds below are first stated
in terms of r_N and then converted to ED bounds with the factor two.
Tagged rows. Suppose two words of common length N = R t L are
constructed as R rows, each row containing, in a fixed child order,
one block of length L in each of t pairwise disjoint alphabets
Gamma_1, ..., Gamma_t. Every letter carries its child index. Any
increasing matching of the two words pairs a source position with a
target position of the same child tag.
A source row is called split if its matches enter at least two
distinct target rows. The next lemma charges every split row to a
target interval that is provably unmatched.
LEMMA (charging split tagged rows). Let R, L, t >= 2 be integers, with
pairwise disjoint alphabets for the t child indices. Take two words of
common length N = R t L, each consisting of R rows, each row
containing in order a block in Gamma_i^L for i = 1, ..., t. Fix an
increasing matching with E unmatched positions on each side. Suppose
every non-split source row loses at least a fraction A of its source
positions, with 0 <= A <= 1; rows with no matches are included in this
hypothesis. Then
E >= A (N - t E / (t - 1)), and E >= A N / (1 + t A / (t - 1)).
Proof. Take a split source row and choose consecutive matched positions
in the matching that enter distinct target rows, first at target row a
and then at target row a' > a. Because the two are consecutive in the
matching, every source position between them stays in the same source
row. Their child indices i <= j agree between source and target. The
open target interval between their partners contains at least
((a' - a) t + j - i - 1) L >= (t - 1) L
positions, all of which are unmatched. Distinct source rows select
disjoint target intervals by monotonicity, so the number of split
source rows is at most E / ((t - 1) L), and the total source length
charged to split rows is at most t E / (t - 1).
Every remaining source row loses at least a fraction A of its own
positions. These losses are disjoint even if several source rows feed
one target row. Summing gives E >= A (N - t E / (t - 1)), and
rearrangement produces the second displayed form. QED
The lemma has two consequences. A matching either separates rows and
pays the fraction A, or splits many source rows and pays (t - 1) L
unmatched target positions per split row. Both constructions below
supply the fraction A by induction on tree height: a non-split source
row inherits the separation of its child row at one level below,
weighted by the phase displacement applied to that row. At the bottom
of the recursion a child word is a shifted half-circle on the phase
circle, and two half-circles of the same child at phases v, v + theta
differ in exactly 2M ||theta|| positions when the circle has M points.
That is the base case of the induction. The circle constructions below
are therefore two different machines for producing the fraction A at
the top level.
The tags enter the lemma through the pairwise disjoint alphabets. In
each construction a letter is stamped with its child index, and
distinct child indices use disjoint alphabets, so a matched pair of the
two words inherits its child index. The same construction at one level
below ensures that a matched pair in the same child of two rows again
has matching child index, and so on down to the base case.
First construction. The parameter h ranges over all sufficiently large
integers. Choose h^2 distinct primes p_{lk} in the interval [h^3, 2h^3],
for 1 <= l <= h and 1 <= k <= h. The prime-counting estimate
pi(2x) - pi(x) > 3x / (5 log x) (x >= x_0)
of Rosser and Schoenfeld
https://doi.org/10.1215/ijm/1255631807
supplies at least h^2 such primes for every sufficiently large h. Set
P_l = prod_{k=1}^{h} p_{lk},
M = 2 prod_{l=1}^{h} P_l,
R = h^{2h},
G = (M^{-1} Z) / Z.
The factor two places the half-turn 1/2 in the finite grid G. Each P_l
is a product of h distinct primes each at most 2h^3, so
log P_l <= h log(2h^3) <= 4 h log h for h >= 2, and hence
log M <= log 2 + 4 h^2 log h <= 5 h^2 log h.
Bounds of this order recur below without further comment.
At level l the children are indexed by
J_l = { (k, b) : 1 <= k <= h, 0 <= b < p_{lk} },
with total cardinality t_l = sum_{k=1}^h p_{lk}. Since each p_{lk} lies
in [h^3, 2h^3], the inequality h^4 <= t_l <= 2 h^4 holds whenever
h >= 2. With a fixed order on J_l, define additive maps on the group of
residue vectors z = (z_1, ..., z_h) with z_k in Z / p_{lk} Z by
sigma_l(z) = sum_{k=1}^h z_k / p_{lk} in G,
gamma_{l,(k,b)}(z) = sigma_l(z) + b z_k / p_{lk} in G.
For an integer a, let z(a) be the residue vector (a mod p_{lk})_k. The
Chinese remainder theorem makes the map a |-> z(a) a bijection from
Z / P_l Z onto the product of the groups Z / p_{lk} Z.
Set r_0 = 1 and r_l = t_l r_{l-1}. The integer r_l counts the leaves at
level l of a tree whose internal nodes at level l possess t_l children.
A state at level l is a tuple v = (v_j)_{j in J_l} with each v_j lying
in G^{r_{l-1}}. When a vector has all coordinates equal to some phase
theta in G, that vector is written theta * 1.
The level-zero word S_0(v), for a phase v in G, is the length-M binary
word whose bit at position b in {0, 1, ..., M-1} is
1 if (b/M - v) mod 1 lies in [0, 1/2), 0 otherwise.
Thus S_0(v) lights up M/2 consecutive sites of the circle and, as v
advances, slides the two boundary points around the circle.
At level l >= 1, the level-l word S_l(v) is the concatenation, over
a = 0, 1, ..., R P_l - 1, of the rows
row(a) = concat_{j in J_l}
[j, S_{l-1}( v_j + gamma_{l,j}(z(a)) * 1 )],
where [j, U] denotes the child word U with tag j attached to every
letter. A row concatenates all t_l child words, each shifted by a phase
determined jointly by the row index and the child's own prime group.
The row list has period P_l and repeats R times, so every level-l word
has length
L_0 = M, L_l = R P_l t_l L_{l-1}.
At the top the alphabet has size A = 2 r_h, since every letter carries
one bit and one tag.
Adding a fixed phase theta to every leaf coordinate below a node
produces the same subword as replacing the level-zero phase v by
v + theta * 1. This follows inductively from the concatenation and is
used below without further comment.
The subgroup of cheap translations is defined recursively:
C_0 = {0},
C_l = C_{l-1}^{J_l}
+ { (gamma_{l,j}(z) * 1)_{j in J_l} : z in prod_k Z/p_{lk} Z }.
The first summand applies a translation of C_{l-1} inside each child
block independently. The second summand adds one uniform child phase
gamma_{l,j}(z) to child j of every row, with the residue vector z
prescribed by the Chinese remainder theorem.
LEMMA (cheap translations). For every 0 <= l <= h, every state v in
G^{r_l}, and every c in C_l,
ED( S_l(v), S_l(v + c) ) <= 2 l L_l / R.
At the top level, for every leaf coordinate i and every 1 <= a <= M/2,
ED( S_h(v), S_h(v + e_i(a/M)) ) <= 2 a L_h / (M r_h).
Both estimates hold at every base state v.
Proof. Fix a translation c coming from the second summand of C_l. The
Chinese remainder theorem provides a row shift q in {0, 1, ..., P_l - 1}
with z(q) = z. Additivity of gamma then gives
gamma_{l,j}(z(a)) + gamma_{l,j}(z) = gamma_{l,j}(z(a + q)) for every a,
so row a of S_l(v + c) coincides with row (a + q mod P_l) of S_l(v).
Since the row list is P_l-periodic, S_l(v + c) is the cyclic row shift
of S_l(v) by q positions. Delete q rows at the start and insert them at
the end, at cost 2 q (row length) with row length equal to
t_l L_{l-1}. Because q <= P_l - 1 and L_l = R P_l t_l L_{l-1}, this cost
is at most 2 L_l / R.
For a translation c in the first summand C_{l-1}^{J_l}, apply the
level-(l-1) bound inside each child block independently. Each child
block is a word of length L_{l-1}, so each block costs at most
2(l-1) L_{l-1} / R, and each row contains t_l such blocks. The full
word contains R P_l t_l blocks, so the total cost is at most
2(l-1) L_l / R.
Adding the two contributions gives 2 l L_l / R. Every bound holds at
every base state, so the triangle inequality combines them through a
chain of intermediate states and gives the first display.
The leaf bound follows by viewing a single leaf coordinate as a copy of
S_0 repeated L_h / (M r_h) times. Shifting that half-circle by a/M, for
1 <= a <= M/2, changes exactly 2a bits in each copy, at unit cost per
changed bit. Substituting the changed bits, with every tag preserved,
proves the second display. QED
Next comes the scalar phase cost, measuring how much of a uniform phase
survives the cheapest possible choice of row translations at each
level:
D_0(theta) = ||theta||_{R/Z},
D_l(theta) = min_z (1/t_l) sum_{j in J_l}
D_{l-1}(theta + gamma_{l,j}(z)) (1 <= l <= h).
The minimum exists because z ranges over a finite set. Each D_l is
symmetric, since negating a minimizing z reverses the phase sum; and
subadditive, since adding two minimizing vectors and using
subadditivity of D_{l-1} controls the sum of two phase sums. The zero
vector shows 0 <= D_l(theta) <= D_{l-1}(theta) <= D_0(theta) <= 1/2
for every level and every theta.
LEMMA (word separation). For every 0 <= l <= h, every v in G^{r_l},
and every theta in G,
r_{L_l}( S_l(v), S_l(v + theta * 1) )
>= 2^{-l} / 4 * L_l * D_l(theta).
Proof. Base case l = 0. Let E = r_M(S_0(v), S_0(v + theta)). In an
increasing matching of M - E pairs, the k-th selected position on
either side lies between k and k + E, so each matched pair has
displacement at most E. The Hamming distance of the two half-circle
words is 2 M ||theta||. A source position where the two bits disagree
is either unmatched in the source, of which there are at most E, or
matched to a target position near one of the at most two transitions
of the target half-circle. Since each matched pair has displacement at
most E, at most 2E target positions sit within distance E of a
transition, for at most 4E positions total. Hence
2 M ||theta|| <= E + 4E = 5 E,
so E >= 2 M D_0(theta) / 5 >= M D_0(theta) / 4.
Induction step. Assume the assertion at level l-1 and fix a longest
common subsequence matching between S_l(v) and S_l(v + theta * 1). Let
t = t_l and L = L_{l-1}. Suppose the matches of a source row all land
in a single target row, with source row parameter a and target row
parameter a'. Every letter carries its child tag, so child j of the
source can only match child j of the target. For that j, the two child
words differ by the phase displacement (theta + gamma_{l,j}(z(a' - a)))
times 1, so the induction hypothesis bounds the source loss in child j
by
2^{-(l-1)} / 4 * L * D_{l-1}( theta + gamma_{l,j}(z(a' - a)) ).
Summing over j and using the recursion for D_l, the source row loses at
least
2^{-(l-1)} / 4 * L * t * D_l(theta) = A (row length),
with A = 2^{-(l-1)} D_l(theta) / 4 <= 1/8. A row with no matches loses
every source position and satisfies the same bound. The tagged-rows
lemma applies with parameters t and A, giving a global deficit of at
least
A L_l / (1 + t A / (t - 1)) >= A L_l / 2,
using t >= 4 and A <= 1/8. This is the stated bound. QED
The remaining task is to estimate D_h(1/2), that is, how much of the
half-turn phase survives the cheapest sequence of row translations
during a descent from level h to level 0.
LEMMA (denominator resets). For all sufficiently large h,
D_h(1/2) >= 4^{-h} h^{-h/2 - O(sqrt h) - 4h/100}.
Proof. At level l choose a minimizing residue vector z for D_l(theta),
put s = |{k : z_k != 0}|, and set K = floor(h/100). If z_k != 0, then
multiplication by z_k permutes the p_{lk} grid points of the k-th prime
group, so the average child phase cost in that group is at least
D_{l-1}(1/p_{lk}) / 2 by symmetry and subadditivity. The weight of that
group in the row is p_{lk} / t_l >= 1/(2h), and there are s active
groups. This gives the reset option
D_l(theta) >= s / (4h) * min_{k : z_k != 0} D_{l-1}(1/p_{lk}).
If s < sqrt(h), the inactive groups carry total weight at least
(h - s)/(2h) >= 1/4 and all exhibit the common phase theta + sigma_l(z).
This gives the inactive option
D_l(theta) >= (1/4) * D_{l-1}( theta + sigma_l(z) ).
Begin at level h with phase 1/2, whose reduced denominator is two. At
entry to level l, maintain a nonzero phase whose reduced denominator is
a product of at most K distinct primes, all equal to two or drawn from
levels strictly above l. The initial phase satisfies this invariant.
Use the reset option whenever s >= sqrt(h), and also when s < sqrt(h)
but the current denominator count plus s exceeds K. Use the inactive
option otherwise. A large reset costs a factor at least 1/(4 sqrt h) and
leaves a nonzero phase with a single prime denominator. A small reset
costs at least 1/(4h) and leaves the same. An inactive step costs at
least 1/4 and increases the denominator count by at most s < sqrt(h).
The phase remains nonzero throughout. Suppose the phase is a/Q in
lowest terms with Q > 1 and a new summand b/P is added, where P is a
product of active current-level primes. The invariant gives
gcd(Q, P) = 1, and the reduction of aP + bQ modulo Q yields aP != 0
mod Q, so a/Q + b/P is not an integer. The reduced denominator of the
new phase is therefore a product of at most (old count + s) distinct
primes.
The number q of small resets satisfies q = O(sqrt h). For each small
reset, take the interval of steps since the preceding reset of either
kind, or since the start. Its initial count is one, and an overflow
forces the sum of its small supports, including the last, to exceed
K - 1. These intervals are disjoint, and their total support sum is at
most h sqrt(h), so q <= h sqrt(h) / (K - 1) = O(sqrt h).
Let n_g, n_i, n_s denote the numbers of large resets, inactive steps,
and small resets. Since the descent visits h levels, n_g + n_i + n_s = h,
and the accumulated cost is at least
(4 sqrt h)^{-n_g} * 4^{-n_i} * (4h)^{-n_s}
= 4^{-h} * h^{-n_g/2 - n_s}.
At level zero the surviving phase is again nonzero. Its reduced
denominator is a product of at most K distinct primes, each at most
2h^3 <= h^4, so its denominator is at most h^{4K}. Its distance on the
circle from zero is therefore at least h^{-4K}. Multiplying and using
n_g/2 + n_s = h/2 - n_i/2 + n_s/2 along with n_s = O(sqrt h) gives
the stated bound. QED
Combining word separation with denominator resets gives the pointwise
half-turn deficit
r_{L_h}( S_h(v), S_h(v + 1/2 * 1) )
>= 2^{-h}/4 * L_h * 4^{-h} h^{-h/2 - O(sqrt h) - 4h/100}
= L_h 8^{-h}/4 * h^{-h/2 - O(sqrt h) - 4h/100}
for every state v. Taking logarithms, dividing by h log h, and using
log L_h = O(h log h) shows that the normalized deficit is at least
h^{-(0.54 + o(1)) h}. This is the pointwise half-turn separation of the
construction, and it holds for every pair S_h(v), S_h(v + 1/2 * 1) with
v ranging over G^{r_h}.
Analytic comparison. Let V = G^r be a finite product of the circle
grid G, and let H <= V be a subgroup. Put w = (1/2) * 1 and fix a
positive number B, the branching threshold. The next lemma converts a
single displacement by w in an arbitrary l1 image into the average
subgroup displacement plus weighted leaf-scale displacements.
Finite cut representation. For a finite set X and any l1 distance d
on X, there exist nonnegative weights a_A indexed by subsets A of X
with d(x, y) = sum_A a_A |1_A(x) - 1_A(y)| for all x, y in X. The
identity |s - t| = int_0^{inf} |1(s > u) - 1(t > u)| du, applied to
each coordinate of an l1 distance, produces the representation with
total weight equal to the sum of pairwise distances. Infinite l1
targets are handled by allowing a sigma-finite measure over cuts; sums
and integrals commute with nonnegative integrands, so the arguments
below pass to that setting unchanged.
For an injective F: V -> l1 and a shift u in V, define
Delta_F(u) = (1/|V|) sum_v ||F(v + u) - F(v)||_1.
LEMMA (weighted finite-circle inequality). Let B > 0 satisfy the
branching premise: whenever chi_alpha is trivial on H but
chi_alpha(w) != 1, the total frequency weight T(alpha) = sum_i
|alpha_i| is at least B. Then for every F: V -> l1 there exist
nonnegative weights omega_alpha with
Delta_F(u) = sum_alpha omega_alpha |1 - chi_alpha(u)|^2 (u in V),
and these weights satisfy
sum_{alpha notin H^perp} omega_alpha
= (1/2) E_{u in H} Delta_F(u),
4 sum_alpha omega_alpha T(alpha)
<= sum_{i=1}^{r} sum_{a in D_M} (M/a)
Delta_F((a/M) e_i),
where H^perp = {alpha : chi_alpha|_H = 1} and D_M is the set of
positive powers of two at most M/2. Consequently
Delta_F(w) <= 2 E_{u in H} Delta_F(u)
+ (1/B) sum_{i=1}^{r} sum_{a in D_M} (M/a)
Delta_F((a/M) e_i).
Proof. Write d_F = ||F(v) - F(v')||_1 and apply the finite cut
representation. For a cut A and a shift u, put g_A(v) = 1_A(v). The
identity |1_A(v+u) - 1_A(v)| = |1_A(v+u) - 1_A(v)|^2, since a cut
distance is 0 or 1, converts the first power of the cut distance into
a square. Fourier expansion on the finite abelian group V then gives
E_v |1_A(v+u) - 1_A(v)|^2
= sum_alpha |g_A_hat(alpha)|^2 |1 - chi_alpha(u)|^2,
where g_A_hat(alpha) = (1/|V|) sum_v g_A(v) conj(chi_alpha(v)).
Summing over cuts with the weights a_A and defining
omega_alpha = sum_A a_A |g_A_hat(alpha)|^2 >= 0
produces the Fourier decomposition of Delta_F. Only the argument
|1_A(v+u) - 1_A(v)| = |1_A(v+u) - 1_A(v)|^2 depends on the cut
structure; the rest is linearity.
A nontrivial character of the finite group H has zero mean, so
E_{u in H} |1 - chi_alpha(u)|^2 equals two when alpha is not in H^perp
and zero otherwise. This gives the off-mass identity.
For the weighted-mass inequality, fix a coordinate i and a character
alpha. Since |alpha_i| <= M/2, some power of two a satisfies
M/(2|alpha_i|) >= a > M/(4|alpha_i|). Then the angle
2 pi a alpha_i / M lies in [pi/2, pi] mod sign, so
|1 - e^{2 pi i a alpha_i / M}|^2 >= 2, and the same estimate gives
M/a >= 2|alpha_i|. Hence
(M/a) Delta_F((a/M) e_i)
>= 4 |alpha_i| omega_alpha,
summing first over a and then over i yields the weighted-mass
inequality.
Combine the two inequalities. Squaring chi_alpha(w) = (-1)^T(alpha)
gives |1 - chi_alpha(w)|^2 = 4 when T(alpha) is odd and 0 otherwise. So
Delta_F(w) = 4 sum_{T(alpha) odd} omega_alpha
= 4 sum_{T(alpha) odd, alpha notin H^perp} omega_alpha
+ 4 sum_{T(alpha) odd, alpha in H^perp} omega_alpha.
The first sum is at most 4 sum_{alpha notin H^perp} omega_alpha, equal
to 2 E_{u in H} Delta_F(u) by the off-mass identity. For the second
sum, the branching premise bounds each T(alpha) from below by B, hence
4 sum_{T(alpha) odd, alpha in H^perp} omega_alpha
<= (4/B) sum_alpha omega_alpha T(alpha)
<= (1/B) sum_i sum_{a in D_M} (M/a) Delta_F((a/M) e_i).
Adding the two bounds completes the proof. QED
Frequency branching. The branching premise is verified for the mask
construction. Every level-l internal node a of the first construction has a subtree
sum t_a, defined as the sum of its leaf frequencies alpha_i. Every
level-l node has t_l children
indexed by J_l = {(k, b) : 1 <= k <= h, 0 <= b < p_{lk}}.
LEMMA (frequency branching). Let chi_alpha be any character of V = G^{r_h}.
If chi_alpha|_{C_h} = 1 and chi_alpha(w) != 1, then
sum_{i = 1}^{r_h} |alpha_i| >= (h/2)^h.
Proof. Write T = sum_i |alpha_i|. Because w = (1/2) * 1,
chi_alpha(w) = (-1)^{T}, so T is odd and in particular nonzero. Fix a
level-l node a and a level-l prime index k. The translation that adds
gamma_{l,j}(z) to child j of a, with z_k = 1 and all other residues
zero, and that leaves everything outside a fixed, belongs to C_h.
Evaluating chi_alpha on that translation gives
t_a + sum_{b=0}^{p_{lk}-1} b t_{a,(k,b)} = 0 (mod p_{lk}), (1)
where t_{a,(k,b)} is the subtree sum of child (k, b) of a.
Suppose T < (h/2)^h. Then |t_{a'}| < (h/2)^h for every node a'. Fix a
level-l node a with t_a nonzero, and let q be the number of
level-l primes p_{lk} dividing t_a. Those q primes are distinct, each
exceeds h^3, and their product divides t_a, so |t_a| >= h^{3 q}. The
bound |t_a| < (h/2)^h gives h^{3 q} < h^h / 2^h, hence 3 q < h and
therefore q < h/3. Enumerate the groups k for which p_{lk} does not
divide t_a. There are at least 2h/3 such groups. For each, if all
children t_{a,(k,b)} vanished, then (1) would force t_a = 0 mod p_{lk},
so p_{lk} would divide t_a, contradiction. Hence every such group
contains at least one nonzero child, and the node a has at least 2h/3
nonzero children.
Beginning at the root, which is nonzero because T is odd, iterating
this argument through the h levels of the tree produces at least
(2h/3)^h nonzero leaves. Each nonzero leaf contributes |alpha_i| >= 1,
so T >= (2h/3)^h > (h/2)^h. This contradicts T < (h/2)^h, so
T >= (h/2)^h. QED
The branching premise for the mask construction holds with threshold
B = (h/2)^h and H = C_h. In the weighted finite-circle inequality, the
leaf-scale sum has |D_M| = O(log M) powers of two, and M <= exp(5 h^2
log h) bounds log M by 5 h^2 log h. Consequently the second term in
the displacement bound is at most
(|D_M|/B) * sum_i max_{a in D_M} Delta_F((a/M) e_i)
<= (O(h^2 log h) / (h/2)^h) * (max leaf-scale displacement).
Alphabet reduction. The circle constructions produce words over
alphabets of size 2 r_h in the first case and 2 L m^h in the second,
both growing with the parameter. Binary words are the target. A fixed
substitution reduces every finite alphabet to {0, 1} at logarithmic
width while preserving edit-distance deficits.
Fix a finite alphabet A with |A| >= 2 and let m >= 1 be a block width.
A map C: A -> {0,1}^m extends to C: A^* -> {0,1}^* by concatenating
block images in order; the integer m is the block width of C, and
C(x_1 ... x_L) = C(x_1) ... C(x_L) has length mL.
Loss accounting. Let x, y be words in A^L of common length L, with
encoded words Cx, Cy of common length mL. Fix an optimal increasing
matching of Cx, Cy with deficit E. Number positions inside blocks 1
through m.
For a source block i, let U_i count unmatched positions in block i.
If block i has matches, let V_i count globally unmatched target
positions inside the smallest interval of Cy containing all its
partners; if block i has no matches, set V_i = 0. Distinct source
blocks have disjoint target spans by monotonicity, so
sum_{i=1}^{L} U_i = E, sum_{i=1}^{L} V_i <= E,
and the target span of block i, when nonempty, has length exactly
m - U_i + V_i.
For 0 < theta < 1, call a source block theta-good when U_i, V_i <=
theta m. At most 2E/(theta m) blocks fail this condition. A theta-good
block has target span at most m + theta m < 2m, hence meets at most
three target blocks; one of those three receives at least
(1 - theta) m/3 of its matches.
Two distinct m-substitutions are constructed below; each has width m =
O(log(2|A|)) and an absolute deficit factor a > 0.
Interval-separated substitution. Pick m and, independently for every
letter a in A, a uniform binary word C_a of length m. Set u =
floor(m/8). Fix 0 < alpha < 1/2 with gamma := 1 - alpha -
2 H_2(alpha) > 0, where H_2(t) = -t log_2 t - (1-t) log_2(1-t).
For fixed distinct letters a != b and two index lists of length l = u -
floor(alpha u) inside {1, ..., u}, the equalities C_a[p_j] = C_b[q_j]
for j = 1, ..., l involve l independent pairs of independent uniform
bits, so their probability is 2^{-l}. There are at most
binom(u, l)^2 pairs of index lists, and the binomial coefficient obeys
binom(u, l) <= 2^{H_2(l/u) u}, giving
Pr[two u-intervals from C_a, C_b share an l-common subsequence]
<= binom(u, l)^2 2^{-l}
<= 2^{(2 H_2(alpha) - 1 + alpha) u + o(u)}
= 2^{-gamma u + o(u)}.
The total number of length-u interval pairs over all ordered pairs of
distinct letters is at most |A|^2 m^2. Choosing m to be a sufficiently
large absolute multiple of log(2|A|) makes the union bound over all
pairs strictly less than one, so some fixed code satisfies: every pair
of length-u intervals from distinct codewords has LCS less than
(1 - delta) u, with delta = alpha/2. Fix such a code.
Local reconstruction. Let p be a matched position in a theta-good
source block i, with relative source index in the middle third
Mid := {ceil(m/3), ..., floor(2m/3)}. Both u-length intervals inside the
source block, one running forward from p and one backward from p, fit
inside the block because p is in the middle third. Let q in {1, ...,
m} be the relative index of p's target partner. At least one of the
two analogous u-length intervals inside the target block fits. Choose
the same direction on both sides. Trim the last V_i source positions
off the tail of the source interval (measured away from the anchor);
this removes at most V_i source positions.
For any remaining matched pair at source distance at most
u - 1 - V_i from the anchor, the number of unmatched target positions
in the target interval up to the pair's partner is at most V_i, so the
partner lies at target distance at most u - 1, inside the trimmed
target interval. At most U_i retained source positions are unmatched.
The two intervals therefore contain a common subsequence of length at
least
u - U_i - V_i >= u - 2 theta m.
Once 2 theta m < delta u, this common subsequence exceeds (1 - delta)
u, and the interval-separation property forces the two blocks to
carry the same letter.
Fix one offset p chosen uniformly from Mid, the same p in every source
block, and retain every theta-good source block whose offset-p
position is matched. Retained blocks carry equal letters and their
target block indices are nondecreasing. A theta-good block is omitted
when its offset-p position is unmatched, which occurs for at most E
pairs, so the expected number of omitted theta-good blocks is at most
E/|Mid| <= 4E/m. Together with the at most 2E/(theta m) blocks that are
not theta-good, the expected total omissions are at most
(2/theta + 4) E/m.
Duplicates. Distinct retained blocks that send matches to the same
target block are counted separately. Non-adjacent retained blocks can
only map to a repeated target block index if an omitted source block
sits between them, so these duplicates number at most the omission
count. Between adjacent retained blocks i and i+1 with the same target
index, the offsets where both positions are matched can only fail to
be distinguished for at most 3(U_i + U_{i+1}) choices of p; summing
over adjacent pairs gives total expected contribution at most
24 E/m.
Removing one position per duplicate leaves an increasing equal-letter
subsequence of x, y of length at least L minus (omissions + duplicates).
Therefore
E_p r_L(x, y) <= (4/theta + 32) E / m,
so r_L(x, y) <= (4/theta + 32) E/m, equivalently
r_{mL}(Cx, Cy) >= a_1 m r_L(x, y), a_1 = (4/theta + 32)^{-1},
uniformly over all x, y in A^L.
Anchor substitution. A second m-substitution achieves a sharper local
property. Pick m and, independently for every letter a in A, a
uniform binary word C_a of length m. Fix an absolute 0 < epsilon <
1/64 small enough that 2 H_2(epsilon) < 1/8.
The anchor event. Fix distinct letters a != b and integer lists
k_1 < k_2 < ... < k_q and l_1 < l_2 < ... < l_q in {1, ..., m} with
q >= m/4 and k_j != l_j for every j.
If a != b, the equalities C_a[k_j] = C_b[l_j] involve q independent
pairs of independent uniform bits, so their probability is
2^{-q} <= 2^{-m/4}. If a = b, then all equalities constrain one
codeword C_a. Form the graph G on {1, ..., m} with edge {k_j, l_j}
for each j. There are no loops (k_j != l_j) and every vertex has
degree at most two, because each index appears at most once in each
list. Repeated unordered edges are impossible: a repetition would
require reversed index pairs, which strict increase on both sides
forbids.
Every connected component with v vertices and e edges imposes at most
v - 1 independent binary equations on the bits of C_a, and in every
component v - 1 >= e/2 (equality for paths; e - 1 for cycles; both at
least e/2 since e <= v). Summing over components, the rank of the
equality system is at least q/2, so the probability that all q
equalities hold is at most 2^{-q/2} <= 2^{-m/8}.
The number of candidate configurations is at most
|A|^2 m^4 2^{2 H_2(epsilon) m}, obtained by choosing two letters and
two ordered index lists, then bounding the number of such lists by the
entropy of the fraction epsilon. Choosing m as a sufficiently large
absolute multiple of log(2|A|) makes the union bound at most
|A|^2 m^4 2^{(2 H_2(epsilon) - 1/8) m} < 1.
So some fixed code satisfies: for every epsilon-good source block i
and every target block j receiving at least m/4 of its matches, the
two blocks carry equal letters and some position k in {1, ..., m}
satisfies (i, k) matching (j, k).
Good-block reconstruction. Fix x, y in A^L, let E = r_{mL}(Cx, Cy),
fix an optimal matching, and call a source block epsilon-good as
before. At most 2E/(epsilon m) blocks are not epsilon-good.
Choose the target block j receiving at least (1 - epsilon) m / 3 >=
m/4 of the matches of an epsilon-good block i. By the anchor property,
x_i = y_j, and some k in {1, ..., m} is matched at equal relative
index. For any other matched pair (k', l') between blocks i and j,
strict increase of the matching gives
|l' - k'| = |(# unmatched target positions strictly between
(j, k) and (j, l'))
- (# unmatched source positions strictly between
(i, k) and (i, k'))|
<= V_j + U_i <= 2 epsilon m.
So restricting to source positions k' in the middle region
{2 epsilon m + 1, ..., m - 2 epsilon m}, every target partner l' lies
in block j. The middle region has m - 4 epsilon m positions, and at
most U_i <= epsilon m of them are unmatched. Block i therefore sends
at least m - 5 epsilon m > m/2 matched pairs to block j.
Two distinct epsilon-good blocks cannot map to the same target block
j: each sends > m/2 matches to j, and two such sets would exceed the
m positions of block j. So distinct good blocks map to distinct
target blocks, and the corresponding pairs (x_i, y_{j(i)}) form an
increasing equal-letter subsequence of x, y with at least
L - 2E/(epsilon m) positions. Therefore
r_L(x, y) <= 2E/(epsilon m),
which gives
r_{mL}(Cx, Cy) >= a_2 m r_L(x, y), a_2 = epsilon/2,
uniformly over x, y in A^L.
Upper bound. Every edit of x, y at the letter level simulates at most
m block operations on Cx, Cy: an insertion or deletion touches a
single block, and a substitution deletes a source block and inserts a
target block. Hence
ED(Cx, Cy) <= m ED(x, y)
for all finite words x, y over A.
Combined statement. Let a = min(a_1, a_2) > 0 be absolute. For every
finite alphabet A with |A| >= 2 and every m >= C log(2|A|) with C an
absolute constant, there exists an m-substitution C: A -> {0,1}^m for
which
a m r_L(x, y) <= r_{mL}(Cx, Cy) for every L >= 1 and x, y in A^L,
ED(Cx, Cy) <= m ED(x, y) for every x, y in A^*.
The two variants above yield this conclusion with potentially
different absolute values of a; each one is valid.
First lower bound. Return to the mask construction, with grid G of M
points, row repetition R = h^{2h}, depth h, and words S_h(v) in
A^{L_h} for A = 2 r_h, one state v per leaf. The alphabet size obeys
log A = O(h log h), so the anchor substitution from the previous
paragraph, taken with block width
m = C_0 log(2 |A|) = O(h log h),
produces, for a fixed absolute constant C_0, a binary code C: A ->
{0,1}^m satisfying
a m r_{L_h}(x, y) <= r_{m L_h}(Cx, Cy) (x, y in A^{L_h}),
ED(Cx, Cy) <= m ED(x, y) (x, y in A^*),
for an absolute a > 0. Write X_h(v) = C(S_h(v)) and n_h = m L_h.
The mask separation lemma and the code lower bound combine to give the
far bound
ED(X_h(v), X_h(v + w)) >= a m r_{L_h}(S_h(v), S_h(v + w))
>= a m L_h h^{-(0.54 + o(1)) h}
= a n_h h^{-(0.54 + o(1)) h}.
The cheap-translation lemma and the code upper bound combine to give,
for u in C_h and any leaf index i,
ED(X_h(v), X_h(v + u)) <= m * 2 h L_h / R = 2 h n_h / R,
ED(X_h(v), X_h(v + e_i(a/M)))
<= m * 2 a L_h / (M r_h) = 2 a n_h / (M r_h) (1 <= a <= M/2).
Both bounds hold at every base state v.
Fix an arbitrary injective f: image(X_h) -> l1 whose distortion is D,
and scale f so that
ED(x, y)/D <= ||f(x) - f(y)||_1 <= ED(x, y)
for all x, y in image(X_h). Let F = f o X_h, and let Delta_F be the
averaged displacement from the previous paragraph. The far bound gives
Delta_F(w) >= a n_h h^{-(0.54 + o(1)) h} / D,
and the cheap bounds give, for every u in C_h and every a in {1, ...,
M/2},
Delta_F(u) <= 2 h n_h / R,
Delta_F((a/M) e_i) <= 2 a n_h / (M r_h).
Substitute the last two displays into the weighted finite-circle
inequality with H = C_h and B = (h/2)^h. Each coordinate-scale term,
after multiplication by M/a and averaging, contributes
(1/n_h) * sum_i sum_{a in D_M} (M/a) * Delta_F((a/M) e_i)
<= sum_i sum_{a in D_M} (M/a) * (2 a / (M r_h))
= 2 |D_M|.
The displacement form of the lemma then reads
h^{-(0.54 + o(1)) h} / D <= 4h / R + 2 |D_M| / B.
Now R = h^{2h}, B = (h/2)^h, and |D_M| = O(log M) = O(h^2 log h).
The right side is at most C 2^h h^{-h} h^2 log h for a suitable
constant C and all sufficiently large h. Therefore
D >= h^{(0.46 - o(1)) h} / (C 2^h h^2 log h)
>= h^{0.1 h}
for all sufficiently large h.
The length. The level-l word has length L_l = R P_l t_l L_{l-1} with
L_0 = M, so
log L_h = sum_{l=1}^{h} (log R + log P_l + log t_l)
<= O(h^2 log h),
using t_l <= 2 h^4, log P_l <= 4 h log h, and log R = 2 h log h.
Combining with log m = O(h log h) gives
log n_h = O(h^2 log h).
So for every sufficiently large integer h, the code applied to the
mask construction supplies a binary subset of {0,1}^{n_h}, with
log_2 n_h <= C_len h^2 log h for an absolute C_len, whose least l1
distortion is at least h^{0.1 h}.
Second lower bound. The second construction hardens the frequency
branching: it attaches a distinct prime to each child coordinate, and
at level l makes the translation associated with prime p_{l,i} act on
every child except the i-th. Under any cheap alignment, this omission
forces all but a few coordinates of the chosen shift to be zero.
Primes. Fix a large integer m and set h = m. The construction uses m^2
distinct primes p_{l,i}, one for each pair (l, i) with 1 <= l <= h and
1 <= i <= m, all distinct across all pairs, satisfying
m^3 < p_{l,i} <= m^5.
Existence. For an integer n >= 1, the central binomial coefficient
satisfies binom(2n, n) >= 4^n / (2n+1), because the central term is the
largest among the 2n+1 coefficients that sum to 4^n. In Legendre's
valuation formula for binom(2n, n), each difference
floor(2n/p^j) - 2 floor(n/p^j) is zero or one, so the exponent of a
prime p is at most floor(log_p(2n)), and binom(2n, n) <= (2n)^{pi(2n)}.
Taking logarithms with n = floor(m^5/2) gives pi(m^5) >= c m^5 / log m
for an absolute c > 0 and all sufficiently large m. Since pi(m^3) <=
m^3, the interval (m^3, m^5] contains at least m^2 primes once m is
large enough. The structure of the argument follows Erdos's proof of
Bertrand's postulate and Chebyshev's estimate, which Erdos attributes
to ideas of Landau
https://acta.bibl.u-szeged.hu/13396/
Fix such a choice of primes. Set
P_l = prod_{i=1}^{m} p_{l,i},
L = 2 prod_{l=1}^{h} P_l,
R = m^{2h},
T = R/Z.
The factor two in L makes 1/2 a grid point of (1/L)Z/Z. The circle T
carries all phase arguments below.
Alphabet, states, and the tree. Let Lambda = [m]^h = {1, ..., m}^h.
Its elements index the leaves of the m-ary tree of height h; a node at
height l is a prefix a of length h - l, and ai denotes its child
obtained by appending i.
The alphabet is
A = Lambda x {0, 1, ..., L-1} x {0, 1},
so |A| = 2 L m^h. The first coordinate is a leaf tag, the second a
position tag, and the third a bit.
A state is any v in G := ( (1/L)Z/Z )^Lambda, i.e. a collection of
phases v_a indexed by leaves. The half-turn w_* has every coordinate
equal to 1/2.
Leaf words. At a leaf a in Lambda and phases v in G, theta in
(1/L)Z/Z, the leaf word W_a(v, theta) is the length-L word whose b-th
letter is
(a, b, 1) if (b/L - v_a - theta) mod 1 lies in [0, 1/2),
(a, b, 0) otherwise.
The word W_a therefore records a half-circle of the phase circle
(1/L)Z/Z translated by v_a + theta.
Internal words. At a node a at height l >= 1 with children ai for i in
{1, ..., m}, define
W_a(v, theta) = concat_{s=0}^{R P_l - 1} concat_{i=1}^{m}
W_{ai}( v, theta + c_{l,i}(s) ),
where
u_{l,i}(s) = s / p_{l,i} mod 1,
c_{l,i}(s) = sum_{j != i} u_{l,j}(s) mod 1.
The parameter s in {0, ..., P_l - 1} is the level-l row index.
Define W(v) = W_empty(v, 0).
Length. Every height-l word has the same length N_l:
N_0 = L, N_l = m R P_l N_{l-1}.
When a node a is a summand inside a higher-level word, only its own
concatenation structure contributes to the total length.
Phase identity. Below a node, every leaf inherits the same phase
addition. Adding z in G to every coordinate of v produces the same
subword as replacing theta by theta + z:
W_a(v + z, theta) = W_a(v, theta + z) (z in G).
This is a leaf identity, propagated through the concatenation.
Scalar costs. Define
rho_0(z) = ||z||_T,
rho_l(z) = min_{0 <= s < P_l} (1/m) sum_{i=1}^{m}
rho_{l-1}( z + c_{l,i}(s) ) (1 <= l <= h).
Each minimum is over a finite set. Negating a minimizing s reverses the
phase, so rho_l is symmetric. Adding minimizing phases for two inputs
and using subadditivity of rho_{l-1} proves subadditivity. The zero
parameter shows 0 <= rho_l(z) <= rho_{l-1}(z) <= ||z||_T <= 1/2 for
every 1 <= l <= h and every z in T.
LEMMA (word separation). For every 0 <= l <= h, every node a at
height l, every state v in G, and every theta, z in (1/L)Z/Z,
r_{N_l}( W_a(v, theta), W_a(v, theta + z) ) >= N_l 3^{-l} rho_l(z).
Proof. Base case l = 0. The two half-circle words disagree in the bit
coordinate at exactly 2L ||z||_T positions (a half-circle of
circumference 2L moves by ||z||_T, losing 2L||z||_T bit positions on
each boundary). Their subsequence deficit is half that number, so it
equals L ||z||_T = N_0 rho_0(z) = N_0 3^0 rho_0(z).
Inductive step. Fix a longest common subsequence matching of
W_a(v, theta) and W_a(v, theta + z), with a at height l. Write t = m
and L' = N_{l-1}. A row of W_a contains m child words each of length
L', concatenated in the fixed order 1, ..., m. Every letter carries
its leaf tag, so a matched pair of the two words inherits its child
index.
Consider a non-split source row with parameter s and target row with
parameter s'. Child i of the source can only match child i of the
target, and the two child words differ by phase
z + c_{l,i}(s) - c_{l,i}(s') = z + c_{l,i}(s - s').
The induction hypothesis bounds source loss in child i from below by
N_{l-1} 3^{-(l-1)} rho_{l-1}( z + c_{l,i}(s - s') ).
Summing over i and using the recursion for rho_l gives
sum_{i=1}^{m} rho_{l-1}( z + c_{l,i}(s - s') ) >= m rho_l(z).
So the source row loses at least a fraction
A := 3^{-(l-1)} rho_l(z)
of its length m N_{l-1}. A row with no matches loses every source
position and satisfies the same bound. The tagged-rows lemma with
t = m and child length N_{l-1} applies, giving
E >= A N_l / (1 + m A / (m - 1)) >= A N_l / 3,
using m/(m-1) <= 2 and A <= 1. Therefore
E >= 3^{-(l-1)} rho_l(z) N_l / 3 = N_l 3^{-l} rho_l(z). QED
Cheap subgroup and translations. For a node a at height l and
parameter s, define a vector tau_{a,s} in G by
tau_{a,s}(a') = c_{l,i}(s) if a' lies below child ai of a,
tau_{a,s}(a') = 0 otherwise.
Let H be the subgroup of G generated by all such tau_{a,s}.
For a fixed node a at height l and parameter s, adding tau_{a,s} to v
replaces the row parameter of a by its translate by s, at that node
only. The row list of length P_l is repeated R times, so shifting by s
is the same as deleting s rows at one end of each period and
reinserting them at the other. Cost per occurrence of a: at most
2 s m N_{l-1} <= 2 N_l / R. Node occurrences at a fixed height
partition the root word into subwords of length N_l each, so combined
cost over all nodes at that height is at most 2 N_h / R, where N_h is
the total word length. Every element of H decomposes as a sum of at
most h single-height translations, because sums at one node combine
into a single parameter and nodes at the same height contribute
independently. Following intermediate states and adding by the
triangle inequality therefore gives
ED( W(v), W(v + u) ) <= 2 h N_h / R
for every v in G and every u in H.
Leaf translations. For a leaf a in Lambda and a shift z in
(1/L)Z/Z, the vector z e_a in G has value z at a and zero elsewhere.
Shifting the half-circle of the leaf word by z changes exactly
2 L ||z||_T bits per occurrence, and the occurrences of a fixed leaf
occupy the fraction m^{-h} of the root word. Substituting the changed
bits, with every tag preserved, gives
ED( W(v), W(v + z e_a) ) <= (2 N_h / m^h) ||z||_T.
Half-turn far bound. All primes p_{l,i} are odd (each exceeds m^3 >=
8), so the half-turn z = 1/2 in T has order two. Combined with the
code from the previous paragraph, the separation lemma and the cheap
bounds produce, for X(v) = C(W(v)) and n_* = w N_h,
ED( X(v), X(v + w_*) ) / n_* >= eta 3^{-h} F_h,
ED( X(v), X(v + u) ) / n_* <= 2 h / R (u in H),
ED( X(v), X(v + z e_a) ) / n_* <= (2 / m^h) ||z||_T,
for every v in G, every u in H, every leaf a, and every z in
(1/L)Z/Z, where eta > 0 is the coding constant and F_h is the lower
bound on rho_h(1/2) furnished by the small-cost lemma below.
Small-cost descent. The bound F_h on rho_h(1/2) arises from a descent
in the recursion for rho_l. The descent shows that small phases admit
rigid representations in which most coordinates vanish.
LEMMA (small-cost). Let 0 <= l <= h, and let z in T be nonzero with
order q. Suppose q <= m^{10} and gcd(q, prod_{a=1}^{l} P_a) = 1. Then
rho_l(z) >= F_l := m^{-l/4 - 100 m^{3/4}}.
Proof. Induct on l.
For l = 0, rho_0(z) = ||z||_T >= 1/(2q) >= 1/(2 m^{10}), which exceeds
m^{-100 m^{3/4}} = F_0 for all sufficiently large m.
Inductive step. Assume the bound at heights 0, ..., l - 1 and fix z
nonzero with q <= m^{10}, gcd(q, prod_{a=1}^{l} P_a) = 1. Suppose for
contradiction that rho_l(z) < F_l.
Put a := m^{-1/4} and b_t := 4 a^{t+1} for t >= 0. For m >= 32^4, all
b_t < 1 and
log prod_{t >= 0} (1 - b_t)^{-1}
<= sum_{t >= 0} b_t / (1 - b_t)
<= 4a / ((1 - a)(1 - 4a)) < log 2,
m sum_{t >= 0} b_t = 4 m^{3/4} / (1 - m^{-1/4}) <= 5 m^{3/4}.
Choose phases z_0 = z, z_1, ..., z_l recursively so that at time t
rho_{l-t}(z_t) < F_l prod_{j < t} (1 - b_j)^{-1} < 2 F_l. (1)
The left inequality holds at t = 0 by assumption.
Suppose 0 <= t < l and write r = l - t. Choose s minimizing rho_r(z_t),
put u_i = u_{r,i}(s) and U = sum_{i=1}^{m} u_i. Call an index i small
when
rho_{r-1}(z_t + U - u_i) < F_{r-1}/2.
The average of these m costs is rho_r(z_t) < 2 F_l by (1). Every
non-small index contributes at least F_{r-1}/2, so the number of
non-small indices is at most 4 m F_l / F_{r-1}. Since
F_l / F_{r-1} = m^{-l/4 + (r-1)/4} = m^{-(t+1)/4},
this count is at most 4 m^{1 - (t+1)/4} = m b_t < m. So there are at
least two small indices.
Alignment. If two small indices i, j had u_i != u_j, symmetry and
subadditivity would give
rho_{r-1}(u_i - u_j)
<= rho_{r-1}(z_t + U - u_i) + rho_{r-1}(z_t + U - u_j)
< F_{r-1}.
The difference u_i - u_j is nonzero and has order dividing
p_{r,i} p_{r,j} <= m^{10}. Its order is coprime to prod_{a=1}^{r-1}
P_a because p_{r,i}, p_{r,j} are level-r primes. The small-cost lemma
at height r - 1, which belongs to the induction hypothesis, gives
rho_{r-1}(u_i - u_j) >= F_{r-1}, contradicting the displayed
inequality.
So all small indices have the same value u_i = u_*. Two distinct
prime-order subgroups of T intersect only at zero, and u_* lies in the
intersection of Z/p_{r,i}Z and Z/p_{r,j}Z for distinct small i, j.
Therefore u_* = 0, and every small index has u_i = 0.
Let k_t = #{i : u_i != 0}, so k_t <= m b_t < m. Every index with
u_i = 0 (in particular every small index) contributes the child phase
z_t + U; set z_{t+1} = z_t + U. Every other contribution is
nonnegative, so
rho_{r-1}(z_{t+1})
<= rho_r(z_t) / (1 - k_t/m) <= rho_r(z_t) / (1 - b_t).
Combined with (1), this extends the invariant to time t + 1.
Terminal. Let Q be the product of the distinct level primes that arose
in the descent. Because the descent selects parameters at most 5
m^{3/4} distinct primes in all, each <= m^5,
Q <= m^{5 * 5 m^{3/4}} = m^{25 m^{3/4}}.
The phase z_l - z has order dividing Q by construction. If z_l
vanished, then z = -(z_l - z) would also have order dividing Q, which
would place q | Q and contradict gcd(q, prod_a P_a) = 1. So z_l is
nonzero. Its order divides q Q, and
rho_0(z_l) = ||z_l||_T >= 1/(2 q Q)
>= 1/(2 m^{10 + 25 m^{3/4}}).
But the terminal invariant (1) at t = l gives
rho_0(z_l) < 2 F_l = 2 m^{-l/4 - 100 m^{3/4}}.
The two bounds are incompatible once m is large enough that
l/4 + 75 m^{3/4} - log_m 4 > 10. So rho_l(z) >= F_l. QED
Half-turn application. Take l = h and z = 1/2 in T. Every prime
p_{l,i} exceeds m^3 >= 8, so gcd(2, prod_{a=1}^{h} P_a) = 1. The
small-cost lemma with q = 2 gives
rho_h(1/2) >= F_h = m^{-h/4 - 100 m^{3/4}}.
The phase identity in the excluded construction equates W(v, 1/2) with
W(v + w_*), and the separation lemma at l = h yields
r_N(W(v), W(v + w_*)) = r_N(W(v, 0), W(v, 1/2))
>= N_h 3^{-h} rho_h(1/2)
>= N_h 3^{-h} F_h.
This is the half-turn far bound quoted in the previous display. QED
Frequency branching for the second construction. Let chi_xi be a
character of V = G, with centered integer representatives xi_a and
total weight T(xi) = sum_a |xi_a|.
LEMMA (frequency branching). Suppose chi_xi|_H = 1 and
chi_xi(w_*) != 1. Then T(xi) >= K := m^{3 h / 4}.
Proof. Since w_* has every coordinate equal to 1/2,
chi_xi(w_*) = (-1)^{t_root} where t_root = sum_a xi_a. So t_root is
odd, hence nonzero.
Suppose T(xi) < K. Every internal node a of the tree has children ai
for i = 1, ..., m, with node sum t_a = sum_i t_{ai} and child sums
t_{ai}. The translations in H act on child ai by adding c_{l,i}(s) to
every leaf below it. Evaluating chi_xi on that translation and
requiring invariance for every choice of s gives the congruences
t_a = t_{ai} (mod p_{l,i}), i = 1, ..., m, (2)
by the same Chinese remainder theorem argument as in the first
construction.
At a level-l node a with t_a != 0, let q count the level-l primes
p_{l,i} dividing t_a. Every such prime divides t_a, is at least m^3,
and the primes are distinct, so their product m^{3q} divides t_a. Then
|t_a| >= m^{3q}. Combined with |t_a| <= T(xi) < m^{3h/4}, this forces
3q < 3h/4, so q < h/4 = m/4.
For every i with p_{l,i} not dividing t_a, the congruence (2) would,
if t_{ai} = 0, force p_{l,i} | t_a, contrary to the choice of i. So
t_{ai} != 0. Therefore at least m - m/4 = 3m/4 children of a are
nonzero.
Starting at the root, which is nonzero because t_root is odd, and
iterating the argument through the h levels gives at least (3m/4)^h
nonzero leaves. Each contributes |xi_a| >= 1, so
T(xi) >= (3m/4)^h >= m^{3 h / 4} = K
for m >= 4. This contradicts T(xi) < K. QED
Second lower bound. The code from the coding paragraph applies with
width w = C_0 log(2|A|) = O(h^2 log m), and produces C: A -> {0,1}^w
with absolute deficit factor eta > 0. Set X(v) = C(W(v)) and
n_* = w N_h. The far and cheap bounds hold:
ED(X(v), X(v + w_*)) / n_* >= eta 3^{-h} F_h,
ED(X(v), X(v + u)) / n_* <= 2 h / R (u in H),
ED(X(v), X(v + z e_a)) / n_* <= (2/m^h) ||z||_T (a in Lambda).
Fix an arbitrary injective f: image(X) -> l1 with distortion D, and
scale f so that ED(x, y)/D <= ||f(x) - f(y)||_1 <= ED(x, y). Let
F = f o X. Substituting the three bounds into the weighted
finite-circle inequality with H and K:
Delta_F(w_*) >= eta 3^{-h} F_h n_* / D,
Delta_F(u) <= 2 h n_* / R (u in H),
Delta_F((d/L) e_a) <= (2/m^h) n_* (d/L) (a in Lambda, d | L).
Then
Delta_F(w_*) <= 2 E_{u in H} Delta_F(u)
+ (1/K) sum_{a in Lambda} sum_{d in D_L}
(L/d) Delta_F((d/L) e_a).
The first term is at most 4 h n_* / R. The leaf-scale sum is at most
sum_{a in Lambda} sum_{d in D_L} (L/d) (2 n_* d / (L m^h))
= (2 n_* / m^h) * m^h * |D_L| = 2 |D_L| n_*,
so the second term is at most 2 |D_L| n_* / K. Dividing by n_* and
combining with the far bound:
eta 3^{-h} F_h / D <= 4h / R + 2 |D_L| / K.
Now R = m^{2h}, K = m^{3h/4}, |D_L| = O(log L) = O(h^2 log m). The
right side is at most O(h^2 log m * m^{-3h/4}) for large m, so
D >= eta 3^{-h} m^{-h/4 - 100 m^{3/4}}
/ (O(h^2 log m * m^{-3h/4})).
With h = m, the exponent h/2 - 100 m^{3/4} in the numerator is at
least m/4 for all sufficiently large m. Hence
log D >= (m/4) log m - m log 3 - O(log m * polylog)
and therefore D >= m^{m/4} for all sufficiently large m.
The length. The total word length obeys
log N_h = sum_{l=1}^{h} (log m + log R + log P_l)
<= O(h^2 log m) = O(m^2 log m).
The code width log w = O(log(h^2 log m)) = O(log m), so
log_2 n_* = O(m^2 log m).
So every sufficiently large m supplies a binary same-length family of
words of length n_* with log_2 n_* <= C m^2 log m and least l1
distortion at least m^{m/4}.
All-length caps. Each construction has produced, for every
sufficiently large parameter k, a binary subset of one common length
n_k with
log_2 n_k <= C_0 k^2 log k, (length bound)
distortion >= exp(c_0 k log k). (distortion bound)
For the first construction k = h and c_0 = 0.1; for the second k = m
and c_0 = 1/4 (after dropping constants into a smaller positive c_0).
LEMMA (all-length inversion). Let c_0, C_0 > 0 be absolute. Suppose
that, for every sufficiently large integer k, there is an integer
n_k >= 1 and a finite subset W_k of {0,1}^{n_k} whose least l1
distortion is at least exp(c_0 k log k), with log n_k <= C_0 k^2 log k.
Then there are absolute constants c > 0 and d_0 such that, for every
integer d >= d_0, some binary subset of one length at most d has
distortion at least exp(c sqrt(log d * log log d)).
Proof. Put t = log d and fix a positive a with C_0 a^2 <= 1/2. Set
k = floor(a sqrt(t / log t)).
For all sufficiently large t this sits above the construction
threshold, so W_k exists, and
k >= (a/2) sqrt(t / log t), log k >= (1/3) log t, k <= t.
Then
log n_k <= C_0 k^2 log k <= C_0 a^2 t (log k / log t)
<= C_0 a^2 t <= t/2 < t,
using log k <= log t. So n_k < d and the witness fits under the cap.
The distortion obeys
exp(c_0 k log k) >= exp((a c_0 / 6) sqrt(t log t)).
Setting c = a c_0 / 6 completes the proof. QED
Both constructions feed the inversion. The first yields c_0 = 1/10
and C_0 = C_len, the second yields c_0 = 1/4 and C_0 = C. In each
case the inversion converts the parameter-indexed family into a
witness for every length cap d.
The main lower bound. Fix a finite alphabet Sigma with |Sigma| >= 2
and a cap d >= d_0. Choose any two symbols 0' and 1' in Sigma and let
{0', 1'}^{<= d} denote the subalphabet of words using only these two
symbols. This subalphabet is isometric for edit distance inside
Sigma^{<= d}: any script on binary words is itself a script on Sigma-
words, and the projection Sigma -> {0', 1'} sending every other symbol
to 0' maps a script of k edits on Sigma-words to a script of at most k
edits on {0', 1'}-words (an insertion of a symbol other than 0' or 1'
becomes an insertion of 0'; a deletion of such a symbol becomes a
deletion; and a substitution becomes an identity or a substitution).
For any injective f: Sigma^{<= d} -> l1, its restriction f' to
{0', 1'}^{<= d} is a valid map on the binary subalphabet, with
dist(f) >= dist(f'). The all-length inversion supplies a binary f'
with dist(f') >= exp(c sqrt(log d * log log d)). So every injective
f on Sigma^{<= d} has distortion at least exp(c sqrt(log d *
log log d)). This is the asserted lower bound of the main theorem.
Upper bound. The matching upper bound in the main theorem comes from a
different source: a recursive block construction that compares
overlapping sliding windows of shorter words. The recursion develops
ideas of Ostrovsky and Rabani
pdf/ostrovsky-rabani-2007.pdf,
which the present construction extends to alphabet-independent
constants and to all shorter words.
Restate the target. Fix a finite alphabet Sigma with |Sigma| >= 2 and
an integer cap d >= 2. The goal is a deterministic map
F: Sigma^{<= d} -> l1^M with
ED(x, y) <= ||F(x) - F(y)||_1
and
||F(x) - F(y)||_1 <= exp(C sqrt(log d * log log d)) ED(x, y)
for absolute constants C and d_0 independent of Sigma. All logarithms
in this part are natural.
Metric comparisons. For finite words x, y define
q(x, y) = max(|x|,|y|) - LCS(x, y),
r_n(x, y) = n - LCS(x, y) (only when |x| = |y| = n).
The metric comparisons from the second paragraph apply throughout:
q <= ED <= 2 q, and r_n <= ED <= 2 r_n at equal length.
Fresh symbol. Let star be a symbol not in Sigma. If star does not
occur in x or y, and N >= max(|x|, |y|), let x-hat = x star^{N - |x|}
and y-hat = y star^{N - |y|}. Then
LCS( x-hat, y-hat ) = LCS(x, y) + N - max(|x|, |y|),
because matched original symbols form a common subsequence of x, y,
while matched star symbols can occupy a final suffix of length at most
N - max(|x|, |y|), and both bounds are attained by appending star-pairs
to an optimal matching. Subtracting yields
r_N( x-hat, y-hat ) = q(x, y),
so that at equal padded length the deficit of the padded words equals
the unequal-length deficit q of the original words.
Common suffix. When two words u, v of equal length m-s+1 are extended
by a common suffix z in Gamma^{s-1}, the deficit comparison
r_m(uz, vz) >= r_{m-s+1}(u, v) holds: a match of the extended words
restricts to a match of the short prefixes with at most r_m deficit at
the level of the prefixes. The opposite inequality fails in general,
which is why the construction uses a fixed suffix only for the
expansion estimate.
Cut representation. Fix a finite set X. An l1 distance on X can be
written as
d(x, y) = sum_{A subset X} a_A |1_A(x) - 1_A(y)|
with a_A >= 0 and sum_A a_A < = sum_{x != y} d(x, y)/2. This is the
finite cut representation of Linial, London, and Rabinovich
https://doi.org/10.1007/BF01200757,
whose treatment includes the identity |s - t| = int |1(s > u) - 1(t >
u)| du applied coordwise.
Random partition. Fix a finite space (X, rho) with nonnegative
weights a_A on cuts A subset X. For a rate alpha > 0 select each cut A
independently with probability 1 - exp(-alpha a_A), and define
pi(u) = pi(v) when every selected cut contains u and v together. Then
Pr[pi(u) = pi(v)] = exp(-alpha rho(u, v)),
because the separating cuts of u, v are the same and the selected-cut
probability factorizes.
Let H_L^pi be the vector of block counts, one coordinate per part of
pi, applied to a list L of size s. The following two histogram
estimates control how far apart two lists become.
LEMMA (histogram estimates). Let s >= 1 and let L, L' be two lists of
size s in the finite space above. Set T = E ||H_L^pi - H_{L'}^pi||_1.
If every cross-pair (u, v) with u in L, v in L' has rho-distance at
least a, then
T >= 2 s ( 1 - s^2 exp(-alpha a) ).
If a pairing of list occurrences leaves t occurrences unpaired on each
side, then
T <= 2 t + 2 sum over paired (u, v) of ( 1 - exp(-alpha rho(u, v)) ).
Writing P_L = H_L^pi / s and TV(P, Q) = (1/2) ||P - Q||_1 yields the
normalization
||H_L^pi - H_{L'}^pi||_1 = s ||P_L - P_{L'}||_1.
Proof. The probability that any particular cross-pair (u, v) collides
is exp(-alpha rho(u, v)), which is at most exp(-alpha a). A union
bound over all s^2 cross-pairs gives the lower estimate. For the upper
bound, unpaired occurrences contribute one to the symmetric difference
of supports in each coordinate. Paired pairs contribute one if their
parts differ and zero otherwise; the probability of a difference is
1 - exp(-alpha rho(u, v)). Summing gives the displayed bound, and
1 - e^{-z} <= z for z >= 0 turns the exponential into a linear ratio.
QED
Power lengths. Fix integers b >= 2 and H >= 1, and set n = b^H. Fix
a nonempty finite alphabet Gamma. Inductively construct maps F_k at
length b^k, 0 <= k <= H, with
r_{b^k}(x, y) <= ||F_k(x) - F_k(y)||_1 <= Lambda_k r_{b^k}(x, y).
At length one, the map a -> (1/2) e_a has distance exactly r_1, so
Lambda_0 = 1.
Upgrade F_{k-1} to F_k. Write m = b^{k-1} and N = bm. Split each
length-N word into b consecutive blocks of length m. At each dyadic
scale s <= m, block j supplies the list
W_{j,s}(x) = ( x_{[ jm + r, jm + r + m - s + 1 ]} )_{r=0}^{s-1},
of its s overlapping windows of length m - s + 1, counted with
multiplicity. Fix one common suffix z_s in Gamma^{s-1} and embed a
window u via F_{k-1}(u z_s). By the common-suffix comparison, the
resulting distance rho_s satisfies
r_{m-s+1}(u, v) <= rho_s(u, v) <= Lambda_{k-1} r_{m-s+1}(u, v).
Applying the histogram lemma on the full domain Gamma^{m-s+1} at rate
alpha_s = 4 log(s + 1) / s
produces one map per block and scale. Define F_k as four times the
direct sum of these maps over j and s.
Separation. Suppose corresponding blocks have deficit q > 0. The
largest dyadic integer s <= (q + 1)/2 is available and satisfies
(q + 1)/4 < s <= (q + 1)/2, s >= q/4.
Every cross-pair (u, v) of their length-(m - s + 1) windows has
r_{m-s+1}(u, v)
>= (m - s + 1) - LCS( u, v )
>= (m - s + 1) - LCS(x, y) restricted to those blocks
>= q - s + 1 >= s,
by subtracting the s - 1 overlapping suffix. The union bound in the
histogram lower estimate is at most s^2 / 4(s+1)^4 (since alpha s = 4
log(s+1) gives exp(-alpha s) = (s+1)^{-4}), hence at most 1/2. The
component is at least s >= q/4. Common subsequences of the blocks
concatenate, so summing over blocks gives noncontracting:
||F_k(x) - F_k(y)||_1 >= r_N(x, y).
Expansion along a move. Suppose x, y in Gamma^N differ by one
single-letter operation (an insertion, deletion, or substitution of
one letter in one block). In a non-exceptional block, the lists
W_{j,s}(x) and W_{j,s}(y) share at least s - 1 identical occurrences:
pair window starts shifted by one, or pair equal starts. The histogram
upper estimate bounds the contribution of a non-exceptional block by
2. In an exceptional block (at most two such, since a single move
affects at most two adjacent blocks), pair the windows at the same
starts. Their deficits differ by at most one, even after the common
suffix z_s is appended, so one such block costs
2 s alpha_s Lambda_{k-1} = 8 log(s + 1) Lambda_{k-1}.
Summing over blocks at fixed scale and multiplying by four:
T_{k,s}(x, y) <= 2b + 16 log(s + 1) Lambda_{k-1} (3)
for one single-letter move.
Power-length recursion. There are at most 1 + floor(log_2 m) <= 1 +
floor(log_2 n) scales. Therefore one move costs at most
C_1 log^2(n + 2) (b + Lambda_{k-1})
for an absolute constant C_1. Any script from x to y of length
ED(x, y) is a sequence of at most ED(x, y) single-letter moves, so the
triangle inequality in the F_k image gives
||F_k(x) - F_k(y)||_1
<= C_1 log^2(n + 2) (b + Lambda_{k-1}) ED(x, y).
Since ED(x, y) <= 2 r_n(x, y),
Lambda_k <= C_1' log^2(n + 2) (b + Lambda_{k-1}),
with Lambda_0 = 1 and C_1' = 2 C_1 an absolute constant. Iterating
from k = 0 to k = H yields
Lambda_H <= b (2 C_1' log^2(n + 2))^H.
Parameters. For all sufficiently large d take
H = floor( sqrt( log d / log log d ) ),
b = ceil( d^{1/H} ),
n = b^H.
Then d <= n, b <= 2 d^{1/H}, and log n <= log d + H log 2 = O(log d).
Also H has order sqrt(log d / log log d), so
log Lambda_H
<= log b + H log(2 C_1' log^2(n + 2))
= O( sqrt(log d log log d) ).
Fresh-symbol padding. Work over the extension alphabet Gamma = Sigma
union {star} with star not in Sigma, and pad every input to length n
by appending star. Define F(x) = 2 F_H(x-hat). By the fresh-symbol
comparison and the metric comparisons,
ED(x, y) <= ED(x-hat, y-hat) <= 2 r_n(x-hat, y-hat)
= 2 q(x, y) <= 2 ED(x, y).
Since ||F_H(x-hat) - F_H(y-hat)||_1 >= r_n(x-hat, y-hat) = q(x, y) and
q(x, y) >= ED(x, y)/2, the map F is noncontracting:
ED(x, y) <= ||F(x) - F(y)||_1.
For the expansion,
||F(x) - F(y)||_1 <= 2 Lambda_H q(x, y) <= 2 Lambda_H ED(x, y),
and log Lambda_H = O(sqrt(log d log log d)). Absorbing the factor two
into the constant C produces the theorem.
Two equivalent formulations. The power-length recursion above compares
each block at every dyadic scale to the maps at the preceding power
length. A variant uses maps Phi_t at the actual shorter lengths
1 <= t <= d instead. For n > 1, partition n positions into b_n =
min(B, n) blocks of nearly equal length, with each block length at
most ceil(n/B), and place on each block the list of overlapping
windows of each dyadic length s <= block length. Embedding each window
at its actual length with the map Phi_{blocklen - s + 1} and using the
count histograms at rate alpha_s = 4 log(2d)/s gives a recursion
ED(x, y) <= ||Phi_n(x) - Phi_n(y)||_1
<= C_6 log^2(d + 1) (B + D') ED(x, y),
where D' = max_{t <= ceil(n/B)} of the expansion at shorter lengths
and D' is bounded by B (C_7 log^2(2d))^{floor(log_B d)}. Taking
B = ceil(exp(sqrt(log d log log d))) gives
log(D') <= O( sqrt(log d log log d) ).
The expansion estimate admits two independent proofs. One uses an
arbitrary longest common subsequence matching of x, y, and shows that
corresponding aligned segments have at least n - 3 e_j positions in
common, where e_j counts the unmatched positions in the j-th pair of
aligned segments. The other uses the move analysis: a single-letter
edit changes at most two adjacent blocks, and either the block pair
is non-exceptional (contribution at most 2) or exceptional
(contribution at most 6 e_j with e_j <= 1, i.e. at most 6). Either
argument produces the same recursion, and the fresh-symbol padding
then reaches every shorter word.
A third formulation uses total variation of probability histograms.
The same counting and move arguments give the recurrence
D_i <= C_5 log(2 n_i) (b + log(2 n_i) D_{i-1}),
which unfolds to the same exponent under the parameter choice above.
Each formulation is a complete independent proof of the upper bound.
Closing. The two directions of the argument now meet. The main
theorem, for every d >= d_0 and every finite alphabet Sigma with
|Sigma| >= 2, states
exp( c sqrt(log d log log d) ) <= E_Sigma(d)
<= exp( C sqrt(log d log log d) ).
The lower bound comes from the construction with omitted-coordinate
translations, its binary substitution, and the all-length inversion;
the upper bound comes from the overlapping-window histogram recursion
and its power-length analysis with fresh-symbol padding. The two
absolute constants are independent of Sigma and d.
The constructions and estimates extend the histogram upper bound of
Ostrovsky and Rabani
pdf/ostrovsky-rabani-2007.pdf,
the cut-based l1 representation of Linial, London, and Rabinovich
https://doi.org/10.1007/BF01200757,
the deletion and insertion coding framework of Levenshtein
https://www.mathnet.ru/eng/dan31411
and of Wagner and Fischer
https://doi.org/10.1145/321796.321811,
the Fourier and cut lower bounds of Khot and Naor
pdf/khot-naor-2006.pdf
and of Krauthgamer and Rabani
https://doi.org/10.1137/060660126,
the binary codes of Schulman and Zuckerman
https://doi.org/10.1109/18.796406
and of Haeupler and Shahrasbi
pdf/haeupler-shahrasbi-2017.pdf,
the l1 lower bound of Andoni, Deza, Gupta, Indyk, and Raskhodnikova
pdf/andoni-deza-gupta-indyk-raskhodnikova-2003.pdf,
the prime-counting of Erdos
https://acta.bibl.u-szeged.hu/13396/
and of Rosser and Schoenfeld
https://doi.org/10.1215/ijm/1255631807,
and the logarithmic-width alphabet reductions of Bhattacharya, Dey,
Goldenberg, and Koucky
pdf/bhattacharya-dey-goldenberg-koucky-2024.pdf
and of Bhattacharya, Dey, Goldenberg, Habib, Haeupler, Karthik, and
Koucky
pdf/bhattacharya-et-al-2026.pdf.