The metric and the question.

For finite words \(x,y\), let \(\operatorname{ED}(x,y)\) be the least number of single-symbol insertions, deletions, and substitutions taking \(x\) to \(y\), with each operation costing one. If \(\Sigma\) is a finite alphabet with at least two symbols and \(d\geq1\) is an integer, let \(\Sigma^{\leq d}\) contain all words of length at most \(d\), including the empty word. This cap restricts only the endpoints of a comparison; intermediate words in an edit script are unrestricted. For an injective map \(f:\Sigma^{\leq d}\to\ell_1\), its distortion is \[\operatorname{dist}(f)= \left(\max_{x\ne y}\frac{\|f(x)-f(y)\|_1}{\operatorname{ED}(x,y)}\right) \left(\max_{x\ne y}\frac{\operatorname{ED}(x,y)}{\|f(x)-f(y)\|_1}\right), \qquad E_\Sigma(d)=\inf_f\operatorname{dist}(f).\] Here \(\ell_1\) is the real space of absolutely summable sequences. There is no restriction on target dimension or on how the map is computed. The question asks for one map that represents every pair in the domain.

All logarithms are natural unless a base is displayed. The constants are independent of the finite alphabet, including alphabets whose size grows with \(d\). Thus the same estimates hold for \(\sup_{2\leq|\Sigma|<\infty}E_\Sigma(d)\). Equation (1) determines the order of \(\log E_\Sigma(d)\); the constants in its two exponents need not agree.

Earlier bounds and the role of alignment.

The single-symbol error model has its roots in Levenshtein’s work on insertion and deletion codes [8]. Wagner and Fischer’s increasing traces describe the alignments available to two words [15]. In particular, if \(\operatorname{LCS}(x,y)\) denotes the longest common subsequence length, the insertion–deletion distance is \[\Delta(x,y)=|x|+|y|-2\operatorname{LCS}(x,y),\qquad \operatorname{ED}(x,y)\leq\Delta(x,y)\leq2\operatorname{ED}(x,y).\] A lower bound must therefore control arbitrary increasing matchings, even when they cross many of the boundaries used to construct the words.

Ostrovsky and Rabani obtained the upper scale in Theorem 1 for fixed-length binary edit distance by recursively comparing multisets of overlapping substrings [12]. They also noted extensions to larger alphabets and varying lengths. Section 8 gives a complete finite histogram construction with alphabet-independent constants and all shorter words included. It can be read on its own.

For lower bounds, Andoni, Deza, Gupta, Indyk, and Raskhodnikova found binary sets whose \(L_1\) distortion approaches \(3/2\) [1]. Their construction uses several nearby word lengths. Khot and Naor obtained a \((\log d)^{1/2-o(1)}\) bound using Fourier analysis of cuts and noisy shifts [6]; their insertion–deletion convention transfers to ours within a factor of two. Krauthgamer and Rabani strengthened the bound to \(\Omega(\log d)\) on binary words of length \(d\) [7]. Our constructions use the same broad cut and Fourier viewpoint, but impose translation constraints through distinct prime periods. Those constraints force large total leaf frequency and yield the exponent in (1). The resulting lower bound grows faster than every fixed power of \(\log d\), while remaining \(d^{o(1)}\). Thus it reaches the scale of the Ostrovsky–Rabani upper bound after taking logarithms.

The lower constructions.

A phase is a point of the circle \(\mathbb R/\mathbb Z\). We work on a finite equally spaced grid containing the half-turn \(1/2\). A state assigns one grid phase to each leaf of a finite rooted tree. At a leaf, a binary pattern records a translated half-circle on that grid. At an internal node, a row lists the child words, each with its own tag; a long word repeats rows at translated phases.

Both constructions compare three kinds of phase change. Translations in a specified subgroup move the row lists at low edit cost. Moving just one leaf changes only the fraction of the word occupied by that leaf, with edit cost at most twice the occupied length times the phase displacement. A simultaneous half-turn at every leaf must have a large edit cost. This last assertion requires control of arbitrary alignments: a matching may cross many of the rows used to define the words.

The row tags provide that control. A source row whose matches stay in one target row inherits the child separation. If its matches enter several target rows, they leave a long unmatched target interval. The intervals charged by distinct source rows are disjoint. Lemma 3 turns this observation into the separation estimate used by both constructions.

To compare these edit costs with an arbitrary \(\ell_1\) image, we express its distances on the finite phase space as nonnegative sums of cut distances and then use finite Fourier expansion. A character has one integer frequency at each leaf. Averaging over the cheap subgroup controls the total Fourier weight of characters nonconstant on it. Among the remaining characters, one that detects the half-turn must have large total absolute leaf frequency: if that total were small, the prime constraints would force nonzero frequency sums to branch through too many leaves. Weighted single-leaf shifts control the Fourier mass carried by these large frequencies. The common analytic step is Lemma 8; each construction proves its own arithmetic branching bound.

The two prime patterns also give different proofs of half-turn separation. The first construction groups children by primes and includes every residue of each prime. Its separation proof follows a nonzero phase down the tree while keeping track of the loss at each level. The complete residue lists allow the descent to restart at the reciprocal of a single prime; these resets keep the denominator factors acquired at other steps from accumulating without control. The accumulated losses and the final phase’s distance from zero give a quantitative lower bound for the half-turn. Section 3 constructs the words and carries out this descent.

The second construction uses one child per prime, with that prime’s translation acting on every child except its own. Two child phases of small cost would have a small difference involving at most two fresh prime denominators. The induction rules out every nonzero such difference, forcing most translation coordinates to vanish. Section [sec:excluded] develops this separate argument.

Binary transfer and the upper construction.

The tags initially require a larger alphabet. Section 4 gives two direct binary substitutions of width \(O(\log(2A))\) for an alphabet of size \(A\). Each has absolute distortion on all equal-length words, simultaneously for every common length. One proof separates intervals of differently labelled codewords and uses a common offset to recover a letter matching. The other controls shifted self-overlaps and finds anchors at equal relative indices. The lower constructions use these bounds only at equal lengths.

The same existence order follows from the alphabet reduction of Bhattacharya, Dey, Goldenberg, and Koucký [2]. Their stated theorem approximately preserves normalized insertion–deletion distance, with each distance divided by the sum of the lengths of its two arguments. The block substitution in its proof has logarithmic width for a fixed target alphabet. Composing that substitution with a fixed-width binary delimiter gives the claimed binary width and distortion, as we explain in Section 4. Our direct proofs expose two different local matching conditions. Long-interval separation is already present in Schulman and Zuckerman’s inner code [14], and self-matching control is a central feature of synchronization strings [5].

For either lower route, depth \(h\) gives logarithmic distortion of order \(h\log h\) at lengths whose logarithms are \(O(h^2\log h)\). The direct parameter choice in Section 7 supplies every sufficiently large cap. Finally, Section 8 develops the independent upper construction: divide words into blocks, list overlapping windows, partition their shorter-word images using cuts, and record the resulting histograms. After the power-length proof, a map at actual window lengths admits two expansion estimates, one from an arbitrary longest common subsequence and one from moves. A final variant uses total variation.

Theorem [thm:uniform-upper] supplies the upper embedding stated as Theorem 6.1 of the companion tree constructions [11], which is combined with their lower bounds in Corollary 6.2. Their lower proofs are independent of the present constructions. A shorter companion proof [10] uses marked rows and a prime-product displacement inequality, with no lower-proof dependence on the circle constructions.

Subsequence deficit and tagged rows

A common subsequence is a collection of equal-symbol pairs whose position indices increase strictly on both sides. Write \(\operatorname{LCS}(x,y)\) for its maximum size. For equal-length words of length \(n\), put \[r_n(x,y)=n-\operatorname{LCS}(x,y).\] This is the number of unmatched positions on either side of a longest common subsequence. For arbitrary lengths put \(q(x,y)=\max(|x|,|y|)-\operatorname{LCS}(x,y)\).

Here is the alignment fact used by both constructions. A row consists of \(t\) child blocks of equal length, in the same fixed child order in both words. Every letter carries its child tag, so a matched pair must preserve the child index. A source row is split if its matched positions enter at least two target rows.

Translated rows on a finite circle

Fix a sufficiently large integer \(h\). Choose \(h^2\) distinct primes \(p_{\ell k}\in[h^3,2h^3]\), for \(1\leq\ell,k\leq h\). Here \(\pi(x)\) denotes the number of primes at most \(x\). The estimate \(\pi(2x)-\pi(x)>3x/(5\log x)\) for sufficiently large \(x\) [13] supplies this many primes for every sufficiently large \(h\). Put \[ P_\ell=\prod_{k=1}^h p_{\ell k},\qquad M=2\prod_{\ell=1}^hP_\ell,\qquad R=h^{2h},\qquad G=(M^{-1}\mathbb Z)/\mathbb Z. \tag{3}\] The factor two puts the half-turn in the finite grid \(G\).

At level \(\ell\) the child set is \[J_\ell=\{(k,b):1\leq k\leq h,\ 0\leq b<p_{\ell k}\}, \qquad t_\ell=\sum_kp_{\ell k},\] with a fixed order. For a residue vector \(z\in\prod_k\mathbb Z/p_{\ell k}\mathbb Z\), define the additive maps \[ \sigma_\ell(z)=\sum_k\frac{z_k}{p_{\ell k}},\qquad \gamma_{\ell,(k,b)}(z)=\sigma_\ell(z)+\frac{bz_k}{p_{\ell k}} \quad\text{in }G. \tag{4}\] For an integer \(a\), write \(z(a)\) for its vector of residues at this level. By the Chinese remainder theorem, \(a\bmod P_\ell\) runs through every \(z\).

Set \(r_0=1\) and \(r_\ell=t_\ell r_{\ell-1}\). A state \(v\in G^{r_\ell}\) is a tuple \((v_j)_{j\in J_\ell}\) with \(v_j\in G^{r_{\ell-1}}\). For \(\theta\in G\), write \(\theta\mathbf1\) for the vector whose every coordinate is \(\theta\). At level zero, \(S_0(v)\) is the length-\(M\) binary word with bit at position \(b\in\{0,\ldots,M-1\}\) equal to \[\mathbf1_{[0,1/2)}(b/M-v),\] where the interval is read modulo one. Thus \(S_0(v)\) records \(M/2\) consecutive sites of the circle.

For \(\ell\geq1\), define \(S_\ell(v)\) by concatenating, for \(a=0,\ldots,RP_\ell-1\), the row \[ \mathop{\Vert}_{j\in J_\ell} [j,S_{\ell-1}(v_j+\gamma_{\ell,j}(z(a))\mathbf1)]. \tag{5}\] Here \(\Vert\) means concatenation in the fixed order, and \([j,U]\) attaches the tag \(j\) to every letter of \(U\). The tags are part of the alphabet, so a match must preserve the child index. All level-\(\ell\) words have length \[ L_0=M,\qquad L_\ell=RP_\ell t_\ell L_{\ell-1}. \tag{6}\] At level \(h\) the alphabet has size \(A=2r_h\). Injectivity of the map from states to words is not required.

The following subgroup records the translations that move row indices: \[ C_0=\{0\},\qquad C_\ell=C_{\ell-1}^{J_\ell}+ \{(\gamma_{\ell,j}(z)\mathbf1)_{j\in J_\ell}: z\in\textstyle\prod_k\mathbb Z/p_{\ell k}\mathbb Z\}. \tag{7}\] For a leaf coordinate \(i\), let \(e_i(\theta)\) have value \(\theta\) there and zero in the other coordinates.

A scalar cost and separation under arbitrary alignments

The subgroup can choose different row translations at successive levels. To measure how much of a uniform phase survives those choices, define \[ D_0(\theta)=\|\theta\|_{\mathbb R/\mathbb Z},\qquad D_\ell(\theta)=\min_z\frac1{t_\ell}\sum_{j\in J_\ell} D_{\ell-1}(\theta+\gamma_{\ell,j}(z)). \tag{10}\] The minimum exists because its set is finite. These functions are symmetric and subadditive: negate a minimizing residue vector for symmetry, and add two minimizing vectors before using the preceding subadditivity inequality. The zero vector also shows \(0\leq D_\ell\leq1/2\).

The remaining geometric question is now one-dimensional: how small can \(D_h(1/2)\) be? The next descent gives the quantitative answer. It is here that the prime groups and their complete residue lists enter the proof.

Keeping a nonzero phase through the descent

Lemmas 5 and 6 give a pointwise half-turn deficit at least \(L_hh^{-(0.54+o(1))h}\). The exponential factors \(8^{-h}\) are absorbed by the \(o(1)h\) term on this logarithmic scale. We next check that the cheap subgroup forces the large frequency size needed to compare this separation with an \(\ell_1\) image.

A common analytic comparison for circle shifts

The word construction has supplied cheap translations and an expensive half-turn. We now derive the inequality that compares those costs in an arbitrary \(\ell_1\) image. The proof is stated for any finite circle product; the next subsection will verify its arithmetic hypothesis for the translation subgroup \(C_h\).

For a finite set \(X\) and \(A\subset X\), write \(\delta_A(x,y)=|\mathbf1_A(x)-\mathbf1_A(y)|\). The finite cut representation of \(\ell_1\) distances is standard [9]. We include the summability argument because an \(\ell_1\) target may have infinitely many coordinates.

For this common lemma, let \(M\geq2\) be any even integer, \(G=(M^{-1}\mathbb Z)/\mathbb Z\), and \(V=G^r\) for \(r\geq1\). For a map \(F:V\to\ell_1\) define its averaged displacement by \[\Delta_F(a)=\mathbb E_{v\in V}\|F(v+a)-F(v)\|_1.\] All averages on finite groups in this paper are uniform. Represent a character of \(V\) as \(\chi_\alpha(v)=\exp(2\pi\mathrm i\sum_i\alpha_i v_i)\), choosing each integer \(\alpha_i\) with \(|\alpha_i|\leq M/2\). Either representative at an endpoint gives the same absolute value. Put \(T(\alpha)=\sum_i|\alpha_i|\) and \(\mathcal D_M=\{1,2,4,\ldots\}\cap[1,M/2]\). For \(\theta\in G\), write \(\theta e_i\) for the vector in \(V\) with value \(\theta\) in coordinate \(i\) and zero elsewhere.

The hypothesis (15) is the only arithmetic input to this lemma. We shall prove it from the prime translations of each construction. The inequalities themselves concern averages over all base states; they impose no pointwise condition on individual Fourier weights.

Prime groups force leaf frequency

Return to the value of \(M\) and the grid \(G\) in (3). Put \(r=r_h\), \(V=G^r\), \(w=\tfrac12\mathbf1\), and \(B=(h/2)^h\). For a character \(\chi_\alpha\) choose the centered integer representatives used in Lemma 8.

The lemma verifies (15) with \(H=C_h\) and \(B=(h/2)^h\). Thus every \(F:V\to\ell_1\) satisfies \[ \Delta_F(w)\leq2\mathbb E_{c\in C_h}\Delta_F(c)+ \frac1B\sum_{i=1}^r\sum_{a\in\mathcal D_M}\frac Ma \Delta_F(e_i(a/M)). \tag{22}\] We now have all three ingredients: the pointwise half-turn separation, the pointwise cheap translations, and the averaged \(\ell_1\) comparison. The tags still use \(2r_h\) letters. The next section supplies the binary substitution, after which Section 5 completes the numerical distortion estimate.

What an arbitrary bit matching tells us

Both proofs use the same elementary loss accounting. Fix an increasing matching between two encoded words of common length \(wL\), numbering positions inside each block from \(1\) to \(w\), and let \(E\) be its number of unmatched positions on either side. In source block \(i\), let \(U_i\) count unmatched positions. If the block has any matches, its target span is the closed interval from its first partner to its last partner; let \(V_i\) count the globally unmatched target positions in that interval. For a block without matches put \(V_i=0\).

The target spans of different source blocks are disjoint, since their matches occur in strict order. Also, a matched target position inside one span has its partner in that source block, by monotonicity. Consequently \[ \sum_iU_i=E,\qquad \sum_iV_i\leq E, \qquad |\text{target span of }i|=w-U_i+V_i \tag{25}\] when the span is nonempty. For a threshold \(0<\theta<1\), call block \(i\) good if \(U_i,V_i\leq\theta w\). At most \(2E/(\theta w)\) blocks fail this condition. A good block has a nonempty target span of length at most \((1+\theta)w<2w\), so its matches meet at most three target blocks.

For the probabilistic choices below, write \(H_2(t)=-t\log_2t-(1-t)\log_2(1-t)\) for binary entropy. We use \[ \sum_{j\leq t m}\binom mj\leq2^{H_2(t)m}\qquad(0<t<1/2). \tag{26}\] Indeed, with \(z=t/(1-t)<1\), \((1+z)^m\geq z^{tm}\sum_{j\leq tm}\binom mj\), which rearranges to the display. The indices in the sum are integers.

Different-label intervals and a common offset

The first code separates sufficiently long intervals of differently labelled codewords. This kind of interval separation already appears in the inner code of Schulman and Zuckerman [14]. We prove the particular binary property needed here, then use one common offset in every source block to recover a matching of letters.

Choose an integer \(m\) and independent uniform binary words of length \(m\), one for each letter, and put \(u=\lfloor m/8\rfloor\). We seek an absolute \(\delta>0\) such that every pair of length-\(u\) intervals from differently labelled codewords has longest common subsequence at most \((1-\delta)u\).

Choose an absolute \(0<\alpha<1/2\) with \(\gamma=1-\alpha-2H_2(\alpha)>0\). For a fixed pair of intervals with different labels, the probability of a common subsequence of length \(u-\lfloor\alpha u\rfloor\) is at most \[\binom{u}{\lfloor\alpha u\rfloor}^{\!2} 2^{-u+\lfloor\alpha u\rfloor}\leq2^{-\gamma u}.\] For fixed index lists the involved bits are independent, giving the probability factor; (26) bounds their number. There are at most \(A^2m^2\) interval pairs. Taking \(m\) to be a sufficiently large absolute multiple of \(\log(2A)\) makes the total failure probability less than one. For sufficiently large \(u\), \(u-\lfloor\alpha u\rfloor\leq(1-\alpha/2)u\); absence of a subsequence of the former length therefore permits \(\delta=\alpha/2\). Fix a code with this property. It makes no assertion about two intervals of the same codeword.

Choose a positive absolute \(\eta<1\) small enough that, for every permitted width, \[ 2\eta m<\delta\lfloor m/8\rfloor. \tag{27}\] For instance choose \(\eta<\delta/100\) first and then increase the minimum width. Fix \(x,y\in\mathcal A^L\), \(L\geq1\), and an optimal encoded matching with deficit \(E\). Apply (25) with \(w=m\) and call a source block good at threshold \(\eta\). At most \(2E/(\eta m)\) blocks are not good.

Let \(I=\{\lceil m/3\rceil,\ldots,\lfloor2m/3\rfloor\}\) be the integer middle-third positions. We claim that a matched position in a good block whose relative index lies in \(I\) lands in a target block with the same letter label. Let \(p\) be its relative source index and \(q\) the relative index of its target partner. A length-\(u\) interval from \(p\) fits in either direction inside the source block. At least one of those directions fits from \(q\) inside its target block. Choose that direction on both sides. Put \(U=U_i\) and \(V=V_i\) for this good source block, and trim the last \(V\) source positions from the interval, measured away from the anchor. For any remaining matched position at source distance \(k\leq u-1-V\) from the anchor, its partner is at target distance at most \(k+V\leq u-1\). The difference of the two distances is the number of intervening unmatched target positions minus the corresponding source number, and the former is at most \(V\). Monotonicity puts the partner on the chosen side. At most \(U\) retained source positions are unmatched. Hence the two intervals share a subsequence of length at least \[u-U-V\geq u-2\eta m>(1-\delta)u.\] The interval property forces equal labels. This argument also applies when \(q\) is at an endpoint of the target block.

Choose one offset \(p\) uniformly from \(I\), using this same \(p\) in every source block. The minimum width ensures \(|I|\geq m/4\). Retain each good source block whose position at offset \(p\) is matched, and assign it the index of the target block containing that partner. If \(B(p)\) blocks are omitted, then \[ \mathbb E_pB(p)\leq\frac{2E}{\eta m}+\frac E{|I|} \leq\left(\frac2\eta+4\right)\frac Em. \tag{28}\] All retained assignments identify equal labels, and their target indices are nondecreasing. We must count the duplicates before turning them into a strictly increasing letter matching.

For two consecutive retained blocks that were not originally adjacent, charge a duplicate target index to an omitted source block strictly between them. The open source-index gaps of consecutive retained pairs are disjoint, so these duplicates number at most \(B(p)\).

For originally adjacent blocks \(i,i+1\), put \(d_i=U_i+U_{i+1}\). Their two positions at a common offset are exactly \(m\) apart. If both are matched, their target partners are at least \(m-d_i\) apart. If those partners lie in one target block, the first is therefore in its first \(d_i\) positions. A good block \(i\) meets at most three target blocks, and its distinct source positions have distinct partners. This duplicate event can thus occur for at most \(3d_i\) offsets; it is impossible when \(d_i=0\). Since \(\sum_{i=1}^{L-1}d_i\leq2E\), the number \(D_{\rm adj}(p)\) of these adjacent duplicates satisfies \[ \mathbb E_pD_{\rm adj}(p)\leq\frac{6E}{|I|}\leq\frac{24E}{m}. \tag{29}\] Only linearity of expectation is used; duplicate events need not be independent.

In a nondecreasing list, removing one item for each consecutive equality leaves one item for every distinct index. The retained assignments therefore give an increasing equal-letter subsequence after at most \(B(p)+D_{\rm adj}(p)\) further deletions. Thus \(r_L(x,y)\leq2B(p)+D_{\rm adj}(p)\). Taking expectations gives \[r_L(x,y)\leq\left(\frac4\eta+32\right)\frac Em.\] This proves the first construction in Theorem 10 with \(w=m\) and \(a=(4/\eta+32)^{-1}\). All constants were chosen before \(L\), and the estimate has no additive error depending on \(L\).

Self-overlaps and an anchor at equal relative indices

The second code controls a different local event. It rules out a long, nearly complete matching between two codeword intervals unless their labels agree and one matched pair has the same index relative to its two block starts. That anchor will put a strict majority of one source block into a single target block, making the recovered letter assignments distinct.

Choose an absolute \(\epsilon>0\) with \[ 2H_2(\epsilon)<\tfrac18,\qquad \epsilon<\tfrac1{10}. \tag{30}\] We seek binary codewords of width \(M\) with this precise property: every increasing matching of at least \(M/4\) pairs between two codewords, omitting at most \(\epsilon M\) positions in each of its two spanned intervals, has equal labels and contains a pair at equal relative indices. The two codewords may have the same label, so this condition controls shifted self-overlaps as well.

Self-matching is central to synchronization strings [5]; related local conditions occur in the Hamming-to-edit construction of Bhattacharya et al. [3]. The property just stated is the particular one we need, and the following argument proves it directly.

Choose all code bits independently and uniformly. For a fixed pair of labels, there are at most \[M^4\left(\sum_{j\leq\epsilon M}\binom Mj\right)^2 \leq M^4 2^{2H_2(\epsilon)M}\] candidate index-list pairs: choose four span endpoints and the omitted positions; the remaining increasing lists determine the matching. Counting choices of different list lengths only enlarges the bound.

For different labels, a fixed matching of \(q\geq M/4\) pairs has equality probability \(2^{-q}\). For the same label and no equal-index pair, form a graph on the \(M\) independent code bits with one edge for each required equality. It has no loops. Every index occurs at most once in either list, so the degree, counting incidences, is at most two. A repeated unordered edge would require reversed index pairs and violate strict increase; even if double edges were allowed, a nontrivial connected component with \(v\) vertices and \(e\) edges has \(v\geq2\), \(e\leq v\), and \(v-1\geq e/2\). Equality of all bits in that component imposes \(v-1\) independent binary constraints. The full equality system therefore has rank at least \(q/2\), so its probability is at most \(2^{-q/2}\leq2^{-M/8}\).

The probability of any violation of the local property is at most \[A^2M^4 2^{(2H_2(\epsilon)-1/8)M}.\] By (30), this is less than one for \(M\) a sufficiently large absolute multiple of \(\log(A+1)\). Fix such codewords.

Now take an optimal matching of \(c(x),c(y)\) with deficit \(E\), and use (25) with \(w=M\) and threshold \(\epsilon\). At most \(2E/(\epsilon M)\) source blocks are not good. A good block has at least \((1-\epsilon)M\) matches in a span meeting at most three target blocks. One target block receives at least \((1-\epsilon)M/3\geq M/4\) of them. Restrict to matches between this source and target block. A position between the first and last restricted matches on either side, if globally matched, is still in the restricted matching: monotonicity places its partner between the opposite endpoints. Hence the omissions in the two restricted spans are bounded by \(U_i,V_i\). The local property gives equal labels and an anchor at equal relative indices.

Put \(b=\lfloor\epsilon M\rfloor\). Both losses of the good block are at most \(b\). Measure target indices relative to the fixed start of the chosen target block, even for matches outside it. Relative to the anchor, the displacement of any match from equal relative indices is the difference between the intervening unmatched counts. Its absolute value is at most \(2b\). Every matched source index in \(\{2b+1,\ldots,M-2b\}\) therefore still lands in the chosen target block. At most \(b\) of these \(M-4b\) positions are unmatched. The chosen block receives at least \[M-5b\geq(1-5\epsilon)M>M/2\] matches. Two good source blocks cannot choose the same target block, since their matched target positions are disjoint. Their chosen target indices are increasing by monotonicity. The good blocks thus give an equal-letter subsequence, proving \[r_L(x,y)\leq\frac{2E}{\epsilon M}.\] This is the second construction with \(w=M\) and \(a=\epsilon/2\), completing Theorem 10.

Relation to the earlier alphabet reduction

The existence order in Theorem 10 has a close predecessor. Theorem 1.1 of the full version of Bhattacharya, Dey, Goldenberg, and Koucký [2] states an alphabet reduction for normalized insertion–deletion distance, with each distance divided by the sum of the lengths of its two arguments. The construction used to prove that theorem is a fixed block substitution \(C:\mathcal A\to Q^k\) in Section 3.2.1 and Lemma 3.3. With approximation parameter \(1/8\), the target alphabet \(Q\) has absolute size \(q\geq2\), and \(k=O(\log(2A))\). Their stated normalized bounds, applied to that construction, give \[ \tfrac78 k\Delta(x,y)\leq\Delta(C(x),C(y))\leq k\Delta(x,y). \tag{31}\] Indeed, the total encoded length is \(k(|x|+|y|)\), so the normalizing factor cancels. When both words are empty, the unnormalized inequalities are immediate.

For clarity, here is the elementary binary step in this comparison. Give the \(q\) target letters distinct \(t=\lceil\log_2q\rceil\) bit labels and encode a letter \(a\) by \(j(a)=11\,0\,a_1\,0\cdots a_t\,0\), of fixed width \(v=2t+3\). The string \(11\) occurs exactly at a block start. In any increasing bit matching, let \(e\) count unmatched positions in the two words together. Then at most \(e\) source blocks fail to be fully matched to consecutive target positions: charge a block either to one of its unmatched source bits or, if all its bits are matched, to an unmatched target position skipped between consecutive partners. The charged gaps of different source blocks are disjoint. The same bound holds on the target side. A fully and consecutively matched block begins at a genuine target block start, by the unique \(11\), so it matches an entire equal block that is itself good on the target side. Conversely, every good target block is paired this way. The good blocks therefore give a letter matching with total loss at most \(2e\). Minimizing over bit matchings proves \[\tfrac12\Delta(u,z)\leq\Delta(j(u),j(z))\leq v\Delta(u,z)\] for arbitrary finite words; the upper bound simulates letter edits.

The composite \(j\circ C\) is a single binary substitution of width \(w=vk\). Combining this inequality with (31) gives \(\Delta(jC(x),jC(y))\geq(7/(16v))w\Delta(x,y)\). At equal lengths this is the deficit lower factor \(7/(16v)\), and for ordinary edit distance it gives the lower factor \(7/(32v)\); bitwise simulation gives the upper factor one. This deduction uses the earlier stated theorem and its block construction. The two proofs above establish the stated binary bounds directly and exhibit distinct ways to recover a letter matching.

The translation pattern and its phase cost

Write \(\mathbb T=\mathbb R/\mathbb Z\) for the circle of circumference one, and let \(\|z\|_{\mathbb T}\) denote the distance of \(z\) from zero. Set \(h=m\). We need \(hm=m^2\) primes, all distinct across all levels, satisfying \[ m^3<p_{\ell,i}\le m^5, \qquad 1\le\ell\le h,\quad 1\le i\le m. \tag{38}\] The following count uses the central binomial coefficient and Legendre’s factorial valuation formula in the manner of Erdős [4], who attributes the underlying ideas to Landau. The central term is the largest of the \(2n+1\) binomial coefficients summing to \(4^n\), so \[\binom{2n}{n}\ge\frac{4^n}{2n+1}.\] In the valuation formula for \(\binom{2n}{n}\), each term \(\lfloor2n/p^j\rfloor-2\lfloor n/p^j\rfloor\) is zero or one. Thus the exponent of \(p\) is at most \(\lfloor\log_p(2n)\rfloor\), and each prime contributes a factor at most \(2n\). Writing \(\pi(x)\) for the number of primes at most \(x\), we obtain \[\binom{2n}{n}\le (2n)^{\pi(2n)}.\] Taking logarithms and then \(n=\lfloor m^5/2\rfloor\) gives \(\pi(m^5)\ge c m^5/\log m\) for an absolute \(c>0\) and all sufficiently large \(m\). Since \(\pi(m^3)\le m^3\), the interval \((m^3,m^5]\) contains at least \(m^2\) primes once \(m\) is large enough. Fix such a choice.

For each level put \[ P_\ell=\prod_{i=1}^m p_{\ell,i},\qquad u_{\ell,i}(s)=\frac{s}{p_{\ell,i}}\pmod1,\qquad c_{\ell,i}(s)=\sum_{j\ne i}u_{\ell,j}(s). \tag{39}\] The parameter \(s\) is taken modulo \(P_\ell\). By the Chinese remainder theorem, \((u_{\ell,i}(s))_{i=1}^m\) runs through the full product of the prime-order subgroups. In particular, one coordinate can be prescribed while all the others are set to zero. Each \(c_{\ell,i}\) is a homomorphism. If only \(u_{\ell,i}\) is nonzero, its value is added to all children except child \(i\).

The scalar cost of a phase after \(\ell\) levels is \[ \rho_0(z)=\|z\|_{\mathbb T},\qquad \rho_\ell(z)=\min_{s\bmod P_\ell} \frac1m\sum_{i=1}^m \rho_{\ell-1}\bigl(z+c_{\ell,i}(s)\bigr) \quad(1\le\ell\le h). \tag{40}\] These functions are defined on all of \(\mathbb T\). Each minimum is over a finite set. They are symmetric and subadditive: negate a minimizing parameter for symmetry, and add minimizing parameters for two inputs and use the preceding subadditivity term by term. The zero parameter shows inductively that, for \(1\le\ell\le h\), \[\rho_\ell(0)=0,\qquad 0\le \rho_\ell(z)\le \rho_{\ell-1}(z) \le\|z\|_{\mathbb T}\le\frac12.\]

The next lemma quantifies what the omitted coordinate prevents. Its input phase has a small order relatively prime to the primes still available in the recurrence. The phases followed during the proof can have much larger orders.

Words whose tags preserve the child index

We now turn the scalar cost into edit separation. Put \[ L=2\prod_{\ell=1}^hP_\ell,\qquad R=m^{2h},\qquad \Lambda=[m]^h,\qquad G=(L^{-1}\mathbb Z/\mathbb Z)^\Lambda . \tag{48}\] The set \(\Lambda\) indexes the leaves of an \(m\)-ary tree of height \(h\): a node at height \(\ell\) is a prefix \(a\in[m]^{h-\ell}\), and \(ai\) denotes its child obtained by appending \(i\). The alphabet is \[\mathcal A=\Lambda\times\{0,\ldots,L-1\}\times\{0,1\}, \qquad J=|\mathcal A|=2Lm^h.\] The first two coordinates are symbol tags. The factor two in \(L\) places the half-turn in the phase group, and every translation \(c_{\ell,i}(s)\) also belongs to this group.

For a state \(v\in G\) and an auxiliary phase \(\theta\in L^{-1}\mathbb Z/\mathbb Z\), define \(W_a(v,\theta)\) recursively. At a leaf \(a\), it is the length-\(L\) word \[ W_a(v,\theta)= \bigl(a,b,\mathbf1_{[0,1/2)}(b/L-v_a-\theta)\bigr)_{b=0}^{L-1}, \tag{49}\] where the half-open interval is interpreted on \(\mathbb T\). At height \(\ell\ge1\), concatenate the following rows, each consisting of \(m\) child words: \[ W_a(v,\theta)= \mathop{\Vert}_{s=0}^{RP_\ell-1} \mathop{\Vert}_{i=1}^{m} W_{ai}\bigl(v,\theta+c_{\ell,i}(s)\bigr). \tag{50}\] The symbol \(\Vert\) denotes concatenation in the displayed order. All height-\(\ell\) words have the same length \[ N_0=L,\qquad N_\ell=mRP_\ell N_{\ell-1}. \tag{51}\] Write \(N=N_h\) and \(W(v)=W_{\varnothing}(v,0)\). Adding a phase \(z\) to every state coordinate below a node has the same effect on its word as replacing \(\theta\) by \(\theta+z\): this follows at a leaf from (49), and then at every height from the concatenation.

Let \(w_*\in G\) have every coordinate equal to \(1/2\). All primes in (38) are odd. The phase \(1/2\) has order two, so Lemmas 11 and 12, together with the phase identity for node words, give the pointwise bound \[ r_N\bigl(W(v),W(v+w_*)\bigr)\ge N3^{-h}F_h \qquad(v\in G). \tag{53}\]

Cheap translations and the binary transfer

For a node \(a\) at height \(\ell\ge1\) and \(s\bmod P_\ell\), define \(\tau_{a,s}\in G\) by \[(\tau_{a,s})_b= \begin{cases} c_{\ell,i}(s),&\text{if the leaf $b$ has prefix $ai$},\\ 0,&\text{if $b$ is outside the subtree below $a$}. \end{cases}\] Let \(H\le G\) be the subgroup generated by these vectors over all internal nodes. At each fixed node, \(s\mapsto\tau_{a,s}\) is a homomorphism.

Fix one height \(\ell\) and choose one translation at each node of that height. In an occurrence of \(W_a(v,\theta)\), adding \(\tau_{a,s}\) replaces row parameter \(t\) by \(t+s\) in (50). The row list has period \(P_\ell\) and repeats it \(R\) times. Choose \(0\le s<P_\ell\). Deleting the first \(s\) rows from the unshifted list and the last \(s\) rows from the shifted list leaves identical words. The edit cost in this occurrence is at most \[2s\,mN_{\ell-1}\le \frac{2N_\ell}{R}.\] At a fixed height the node occurrences partition the root word. The combined cost for all nodes at that height is therefore at most \(2N/R\). Every element of \(H\) is a sum of at most \(h\) such single-height translations: \(G\) is abelian, sums at one node combine to one parameter, and the nodes can then be grouped by height. The edit estimate holds for every state and every ancestor phase. Applying it at each intermediate state and using the triangle inequality gives \[ \operatorname{ED}\bigl(W(v),W(v+u)\bigr) \le\frac{2hN}{R} \qquad(v\in G,\ u\in H). \tag{54}\]

For a leaf \(a\in\Lambda\), write \(ze_a\) for the state vector with value \(z\) at \(a\) and zero elsewhere. This shift changes exactly \(2L\|z\|_{\mathbb T}\) symbols in every occurrence of that leaf word. Each branching has \(m\) equally long children, so the occurrences of a fixed leaf occupy the fraction \(m^{-h}\) of the root word. Substituting only the changed symbols yields \[ \operatorname{ED}\bigl(W(v),W(v+ze_a)\bigr) \le\frac{2N}{m^h}\|z\|_{\mathbb T}. \tag{55}\] This holds for every \(v\in G\), \(z\in L^{-1}\mathbb Z/\mathbb Z\), and \(a\in\Lambda\).

Apply the second construction of Theorem 10, proved using anchors at equal relative indices in Section 4.3, to \(\mathcal A\). It gives one code \(\mathcal C:\mathcal A\to\{0,1\}^{w}\) with \(w\le C_{\rm code}\log(2J)\) and an absolute \(\eta>0\). Its exact estimates are \[ \begin{aligned} r_{wq}(\mathcal Cx,\mathcal Cy)&\ge\eta w r_q(x,y) &&(x,y\in\mathcal A^q),\\ \operatorname{ED}(\mathcal Cx,\mathcal Cy) &\le w\operatorname{ED}(x,y). \end{aligned} \tag{56}\] The lower estimate holds simultaneously at every common length \(q\ge0\), with the code fixed before \(q\) is chosen; the upper estimate holds for arbitrary finite words. Here we use the lower estimate at the common length \(N\).

Set \(X(v)=\mathcal C W(v)\) and \(n_*=wN\). The metric comparison \(r_{n_*}\le\operatorname{ED}\) from Lemma 2, the code estimates, and (53)–(55) give \[\begin{align*} \frac{\operatorname{ED}(X(v),X(v+w_*))}{n_*} &\ge\eta3^{-h}F_h, \tag{57}\\ \frac{\operatorname{ED}(X(v),X(v+u))}{n_*} &\le\frac{2h}{R}, \tag{58}\\ \frac{\operatorname{ED}(X(v),X(v+ze_a))}{n_*} &\le\frac{2}{m^h}\|z\|_{\mathbb T}. \tag{59}\end{align*}\] All three inequalities hold for every \(v\in G\). The second holds for every \(u\in H\), and the third for every \(z\in L^{-1}\mathbb Z/\mathbb Z\) and \(a\in\Lambda\). In particular, each half-turn pair consists of distinct words; other repetitions among the state images are allowed.

Large total leaf frequency

It remains to show that the cheap translations prevent an \(\ell_1\) map from preserving the half-turn distance. Write characters of \(G\) as \[\chi_\xi(v)=\exp\!\left(2\pi\mathrm i\sum_{a\in\Lambda}\xi_a v_a\right), \qquad \xi\in(\mathbb Z/L\mathbb Z)^\Lambda .\] For each coordinate choose an integer representative of minimum absolute value, with either sign allowed in a tie, and put \[ T(\xi)=\sum_{a\in\Lambda}|\xi_a|. \tag{60}\] Thus \(T\) records the total magnitude of the leaf frequencies. Let \(H^\perp=\{\xi:\chi_\xi(u)=1\text{ for every }u\in H\}\).

The distortion and length estimates

Let \(f\) be any injection of the finite set \(X(G)\) into \(\ell_1\), with distortion \(D\). Rescale it by its contraction factor so that \[ \operatorname{ED}(x,y)\le\|f(x)-f(y)\|_1 \le D\operatorname{ED}(x,y) \qquad(x,y\in X(G)). \tag{63}\] This applies to each injection individually. Put \(g(v)=f(X(v))/n_*\) and, using uniform measure on \(G\), define \[\mathcal E(u)=\mathbb E_{v\in G}\|g(v+u)-g(v)\|_1 .\] The cut–Fourier representation in Lemma 8 provides nonnegative weights \(\omega_\xi\) such that \[ \mathcal E(u)=\sum_\xi\omega_\xi|1-\chi_\xi(u)|^2 . \tag{64}\] The lemma applies with period \(L\), \(m^h\) coordinates, subgroup \(H\), and threshold \(K\) by Lemma 13. Its representation and intermediate weight estimates use normalized counting measure and also apply when the target \(\ell_1\) has infinitely many coordinates.

We spell out the two resulting bounds on frequency mass. Let \(\mathcal D_L=\{1,2,4,\ldots\}\cap[1,L/2]\). For every \(s\in\mathcal D_L\), (63) and (59) imply \[\frac Ls\sum_{a\in\Lambda}\mathcal E((s/L)e_a) \le \frac Ls\,m^h\frac{2D}{m^h}\frac{s}{L}=2D.\] The weighted estimate in Lemma 8 therefore gives \[ \begin{aligned} 4\sum_\xi\omega_\xi T(\xi) &\le\sum_{s\in\mathcal D_L}\frac Ls \sum_{a\in\Lambda}\mathcal E((s/L)e_a)\\ &\le 2D|\mathcal D_L| \le C D\log(L+1). \end{aligned} \tag{65}\] In particular \(\sum_\xi\omega_\xi T(\xi)\le C D\log(L+1)\) after adjusting the absolute constant. The subgroup identity in that lemma, together with (58), gives \[ \sum_{\xi\notin H^\perp}\omega_\xi =\frac12\mathbb E_{u\in H}\mathcal E(u) \le \frac{Dh}{R}. \tag{66}\] This is the uniform average on the finite subgroup \(H\) itself.

The half-turn multiplier in (64) equals four when \(t_{\varnothing}\) is odd and zero otherwise. A detecting frequency inside \(H^\perp\) has \(T(\xi)\ge K\), whereas (66) controls all frequencies outside \(H^\perp\). Using also the noncontracting half-turn bound from (57), we obtain \[\begin{align*} \eta3^{-h}F_h &\le \mathcal E(w_*) \\ &\le 4\sum_{\xi\notin H^\perp}\omega_\xi +\frac4K\sum_\xi\omega_\xi T(\xi) \\ &\le C D\left(\frac hR+\frac{\log(L+1)}K\right). \tag{67}\end{align*}\] Thus the separation in the word metric and the branching of frequencies have now been compared using the same finite subgroup.

The prime bounds give \[ \log L\le\log2+5hm\log m. \tag{68}\] With \(h=m\), \(R=m^{2h}\), and \(K=m^{3h/4}\), the term \(h/R\) in (67) is bounded by \(\log(L+1)/K\) for all large \(m\). Since \(F_h=m^{-h/4-100m^{3/4}}\), it follows that \[ D\ge c\eta\, \frac{3^{-m}m^{m/2-100m^{3/4}}}{\log(L+1)} \tag{69}\] for an absolute \(c>0\). The logarithm of the right side, divided by \(m\log m\), tends to \(1/2\): the losses contribute \(100m^{-1/4}\), \(\log3/\log m\), and a term tending to zero by (68). Therefore, after increasing an absolute threshold, \[ D\ge m^{m/4}\qquad(m\ge m_0). \tag{70}\] Because \(f\) was arbitrary, this is a distortion lower bound for the finite set \(X(G)\).

Finally, (48) and (51) give the exact root length \[N=L\prod_{\ell=1}^h(mRP_\ell) =\frac{L^2}{2}(mR)^h.\] Consequently \[\log N\le12m^2\log m+m\log m+\log2.\] Also \(J=2Lm^h\) and \(w\le C_{\rm code}\log(2J)\), so \(\log w=O(\log m)\). Hence, for an absolute \(C_0\), \[ \log n_*=\log(wN)\le C_0m^2\log m \qquad(m\ge m_0). \tag{71}\] We have obtained these binary same-length witnesses for every sufficiently large integer \(m\). Section 7 applies its direct all-length inversion to (70) and (71), yielding a witness of one length at most each sufficiently large cap.

Subsequence deficits and local moves

A common subsequence is an increasing matching of equal symbols; its maximum size is \(\operatorname{LCS}(x,y)\). For arbitrary words put \[q(x,y)=\max(|x|,|y|)-\operatorname{LCS}(x,y),\] and for words of the same length \(n\) put \(r_n(x,y)=n-\operatorname{LCS}(x,y)\). Thus \(r_n\) counts the unmatched positions on either one side of a longest common subsequence.

The recursion at equal lengths will use a common suffix with arbitrary symbols. The final passage to varying lengths will use the fresh symbol in (75).

A finite histogram component

The next construction turns a distance between shorter words into a distance between lists of such words. We use the standard cut representation of finite \(\ell_1\) metrics [9]. The proof below includes the summability needed when the original target has infinitely many coordinates.

Thus a lower estimate for one component follows from separation of all cross-pairs, while an upper estimate follows from a pairing of occurrences. Both estimates concern the same map (77), whose partition distribution is fixed on the full finite domain before any pair of input words is considered.

Power lengths and count histograms

Actual window lengths and two expansion estimates

The power-length construction padded each window to the preceding power. We now use maps at the actual window lengths. This gives one recursion whose expansion can be proved in two ways: directly from an arbitrary longest common subsequence, or from the move estimate already used above. Both arguments analyze the same deterministic histogram map.

Fix an integer cap \(d\ge2\), an integer \(B\ge2\), and a nonempty finite alphabet \(\Gamma\). Construct maps \(\Phi_n\) on \(\Gamma^n\), \(1\le n\le d\), whose distances lie between \(\operatorname{ED}\) and \(E_n\operatorname{ED}\), starting with \(\Phi_1(a)=\tfrac12e_a\) and \(E_1=1\). For \(n>1\), partition the positions into \(b_n=\min(B,n)\) nonempty blocks of nearly equal lengths, with boundaries \[0=p_0<p_1<\cdots<p_{b_n}=n,\qquad \ell_j=p_{j+1}-p_j\le\lceil n/B\rceil.\] For each dyadic \(s\le\ell_j\), use the list of \(s\) windows \(x_{[p_j+r,\,p_j+r+\ell_j-s+1)}\), \(0\le r<s\). Embed each window by the map at its actual length. Writing \[D'=\max_{1\le t\le\lceil n/B\rceil}E_t,\] its embedded distance satisfies \(\operatorname{ED}\le\rho\le D'\operatorname{ED}\). Every child length is strictly less than \(n\). Use count histograms at rate \[ \alpha_s=\lambda/s,\qquad \lambda=4\log(2d), \tag{87}\] and define \(\Phi_n\) as six times their direct sum. Write \(T_{j,s}\) for the expected count distance. Equivalently, each component before the factor six is \(s\) times the expected \(\ell_1\) distance of probability histograms, by (80).

Total-variation normalization

A final variant retains the power lengths \(n_i=b^i\) and the common-suffix window embeddings of Section 8.3. Construct \(V_i\) with distances between \(r_{n_i}\) and \(D_i r_{n_i}\), starting with \(V_0(a)=\tfrac12e_a\) and \(D_0=1\). At scale \(s\), use rate \[ \alpha_s=\frac{\log(2s^2)}s \tag{96}\] and \(s\) times expected total variation of probability histograms. This component is half the count distance. For block deficit \(q>0\), choose \(s\) as in (83). Every cross-window deficit is at least \(s\), so the probability of any cross-collision is at most \(s^2e^{-\log(2s^2)}=1/2\). The component is at least \(s/2>q/8\); eight times the summed map is therefore noncontracting for \(r_{n_i}\).

Along a move, a nonexceptional block costs at most one, while an exceptional block costs at most \(s\alpha_sD_{i-1}\). Consequently the unscaled cost at each scale is at most \[ b+2\log(2s^2)D_{i-1}, \tag{97}\] and the move path gives \[ D_i\le C_5\log(2n_i)\bigl(b+\log(2n_i)D_{i-1}\bigr). \tag{98}\] Choose \(b,H,n\) as in (86). Bounding the logarithmic factors by those at \(n=b^H\) and using (85) yields \(D_H\le b(C\log^2(2n))^H\) for an absolute \(C\). The parameter calculation in the power-length proof gives the required exponent. Its fresh-symbol padding and final multiplication by two apply to \(V_H\), proving the same theorem on all shorter words.