Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance

1 Introduction

An insertion or deletion changes the positions of every later symbol. Yet cyclically shifting a nonempty word by one position costs at most two edits: delete its first symbol and insert it at the end. We use the difference between the length of a word and the cost of translating it to study how faithfully edit distance can be represented in \ell_1.

The metric and the question. For finite words x,y, let \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

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 \LCS(x,y) denotes the longest common subsequence length, the insertion–deletion distance is

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.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, Theorem 1.3]. 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 2.2 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 3.5; 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 6 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, Theorem 1.1 and Section 3.2.1 of the full version]. 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, Section II-C], 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 8.1 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.

2 Alignments and tagged rows

We first relate edit distance to increasing subsequence matchings, then transfer a separation estimate for tagged child words to an estimate for rows under arbitrary alignments. This is the only general tool needed before constructing the circle words.

2.1 Subsequence deficit and tagged rows

A common subsequence is a collection of equal-symbol pairs whose position indices increase strictly on both sides. Write \LCS(x,y) for its maximum size. For equal-length words of length n, put

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|)-\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.

3 A circle construction with denominator resets

We now construct the first family of words. A translation subgroup will move long lists of rows at low edit cost, while a simultaneous half-turn will remain separated under every alignment. After proving separation, we derive a common analytic comparison and verify its arithmetic hypothesis for these translations. The tags will then be replaced by binary blocks in the next section.

3.1 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, Corollary 3] supplies this many primes for every sufficiently large h. Put

The factor two puts the half-turn in the finite grid G.

At level \ell the child set is

with a fixed order. For a residue vector z\in\prod_k\mathbb Z/p_{\ell k}\mathbb Z, define the additive maps

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

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

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

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:

For a leaf coordinate i, let e_i(\theta) have value \theta there and zero in the other coordinates.

3.2 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

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.

3.3 Keeping a nonzero phase through the descent

Lemmas 3.2 and 3.3 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.

3.4 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, Section 4]. 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

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.

3.5 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 3.5.

The lemma verifies (15) with H=C_h and B=(h/2)^h. Thus every F:V\to\ell_1 satisfies

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.

4 Two logarithmic-width binary substitutions

The circle words use tags to prevent matches between different children. We now replace each tagged letter by a binary block. The needed property is a lower bound for the deficit of every pair of equal-length words, with the same block-width factor as the elementary upper bound. This makes the loss in distortion absolute, even as the alphabet grows.

The two constructions need not give the same code, width, or constant. Either substitution may be used in either circle construction. Their lower bounds imply (a/2)w\ED(x,y)\leq\ED(c(x),c(y)) at equal length, by Lemma 2.1. The lower assertion is made only at equal input lengths; the upper assertion holds for arbitrary lengths. The case L=0 is immediate. For the upper deficit bound, concatenate the code blocks of a common subsequence. For (24), simulate each letter insertion, deletion, or substitution by at most w bit edits. It remains to prove the lower deficit bound twice.

4.1 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

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

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.

4.2 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, Section II-C, Condition 2 and Lemma 2]. 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

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,

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

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

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

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

This proves the first construction in Theorem 4.1 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.

4.3 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

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, Sections 6.1–6.2 of the full version]; related local conditions occur in the Hamming-to-edit construction of Bhattacharya et al. [3, Section 2.2]. 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

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

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

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

This is the second construction with w=M and a=\epsilon/2, completing Theorem 4.1.

4.4 Relation to the earlier alphabet reduction

The existence order in Theorem 4.1 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

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

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.

5 The first binary obstruction

We return to the words S_h and parameters M,R,C_h from Section 3; here w=\tfrac12\mathbf1 again denotes the half-turn in G^{r_h}. The words use an alphabet of size A=2r_h. Apply the first construction of Theorem 4.1, with width b_h\leq C\log(2A) and lower deficit factor a_{\rm off}b_h, where a_{\rm off}>0 is absolute. Let X_h(v)=c(S_h(v)) and n_h=b_hL_h. The code is fixed for this alphabet and applies at the common length L_h.

The code lower bound, word separation, and denominator reset estimate give, for all sufficiently large h and every state v,

Indeed, the normalized deficit before coding is at least h^{-(0.54+o(1))h}, and the fixed factor a_{\rm off} is absorbed by the slack to 0.75. Simulating each letter edit with at most b_h bit edits in Lemma 3.1 also gives

These bounds hold at every base state. The state map need not be injective; (32) guarantees precisely the distinct pairs needed.

Let f be any embedding of the finite image of X_h into \ell_1, with distortion D. Scale it so that

This uses the maximum expansion on the finite image and does not assume that the infimum of distortions is attained. Apply (22) to F=f\circ X_h. Each coordinate-scale term, after multiplication by M/a, is at most 2n_h/r_h. The pointwise edit bounds therefore imply

Here |\mathcal D_M|=O(\log M) and \log M=O(h^2\log h). Since R=h^{2h} and B=(h/2)^h, the right side is at most C2^h h^{-h}h^2\log h for large h. Hence

Finally t_\ell\leq2h^4 gives \log r_h=O(h\log h) and b_h=O(h\log h). The exact recurrence (6) yields

with an absolute constant C_{\rm len}. Thus every sufficiently large integer h supplies a binary same-length obstruction with distortion at least h^{0.1h} and logarithmic length at most C_{\rm len}h^2\log h. After the second construction, Section 7 will convert each such family into witnesses for every sufficiently large cap.

6 Excluded-coordinate translations on a finite circle

We now construct a second family of hard binary words. The parameter is a sufficiently large integer m; the eventual distortion is at least m^{m/4}, while the logarithm of the word length is O(m^2\log m). At each level there is one prime for each of the m child indices. The translation associated with that prime acts on every child except its own. This omission has two uses. A small phase cost will force most translation coordinates to vanish, whereas a frequency annihilating all the translations and detecting the half-turn must have large total absolute leaf frequency. The proof of this frequency bound assumes the total is small and forces branching through too many children. We first prove the phase assertion, then realize it by words and compare it with the frequency assertion.

6.1 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

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

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

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

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

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,

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.

6.2 Words whose tags preserve the child index

We now turn the scalar cost into edit separation. Put

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

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

where the half-open interval is interpreted on \mathbb T. At height \ell\ge1, concatenate the following rows, each consisting of m child words:

The symbol \Vert denotes concatenation in the displayed order. All height-\ell words have the same length

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 6.1 and 6.2, together with the phase identity for node words, give the pointwise bound

6.3 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

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

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

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

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 4.1, 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

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.1, the code estimates, and (53)–(55) give

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.

6.4 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

For each coordinate choose an integer representative of minimum absolute value, with either sign allowed in a tie, and put

Thus T records the total magnitude of the leaf frequencies. Let H^\perp=\{\xi:\chi_\xi(u)=1\text{ for every }u\in H\}.

6.5 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

This applies to each injection individually. Put g(v)=f(X(v))/n_* and, using uniform measure on G, define

The cut–Fourier representation in Lemma 3.5 provides nonnegative weights \omega_\xi such that

The lemma applies with period L, m^h coordinates, subgroup H, and threshold K by Lemma 6.3. 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

The weighted estimate in Lemma 3.5 therefore gives

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

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

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

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

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,

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

Consequently

Also J=2Lm^h and w\le C_{\rm code}\log(2J), so \log w=O(\log m). Hence, for an absolute C_0,

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.

7 Every length cap and every finite alphabet

Each lower construction supplies binary words of one common length for every sufficiently large integer value of its parameter. We now choose that parameter directly from an arbitrary length cap. This avoids any need to compare successive witness lengths.

For the reset construction, use (36) and (37) with k=h. For the excluded-coordinate construction, use (70) and (71) with k=m. Each separately satisfies the lemma. Restricting a map on \{0,1\}^{\leq d} to either hard subset proves the binary lower bound for every sufficiently large d.

A binary subalphabet is isometric for ordinary edit distance inside any larger alphabet. One inequality follows by using a binary edit script. For the reverse one, project all extra alphabet symbols to either binary symbol and apply this projection to an ambient edit script. Each edit projects to one edit or no change, while the binary endpoints remain fixed. Thus the same lower bound holds for every finite alphabet with at least two letters, with constants independent of its size.

Theorem 8.1 in the next section supplies the upper bound on the whole length-capped space, completing Theorem 1.1. Its fresh-symbol padding serves a different purpose from the binary code transfers: the latter are applied only at equal lengths, while the upper map must compare every pair of shorter words simultaneously.

8 An alphabet-uniform embedding by substring histograms

We now construct an embedding on the whole set of words of bounded length. For a finite alphabet \Sigma, let \Sigma^{\le d} include all words of length at most d, including the empty word. Write \operatorname{ED}(x,y) for the minimum number of single-symbol insertions, deletions, and substitutions taking x to y, each at unit cost. Intermediate words may have arbitrary length. All logarithms in this section are natural.

The construction develops the block-and-shift recursion of Ostrovsky and Rabani [12]. They compare multisets of overlapping shifted substrings using embeddings of shorter strings, and their introduction also identifies extensions to larger alphabets and varying lengths. We give the estimates for these extensions explicitly.

The recursive step represents a block by lists of overlapping windows. After embedding the shorter windows, we record how many of them fall in each part of a random partition. Averaging over every partition outcome gives one deterministic \ell_1 map. A pair of distant blocks has a scale at which every cross-pair of windows is distant, so their histograms are often disjoint. For expansion, a deletion followed by an insertion shifts most blocks by one position, allowing most windows to be paired identically. These observations prove the theorem first at power lengths. We then construct a map using the actual window lengths and analyze its expansion both through an arbitrary longest common subsequence and through moves. A final variant uses total variation in the power-length recursion.

8.1 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

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).

8.2 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, Section 4]. 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.

8.3 Power lengths and count histograms

8.4 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

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

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

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).

Separation. If corresponding blocks have edit distance k_j>0, then k_j\le\ell_j by substitution. The largest dyadic s\le(k_j+2)/3 is available and satisfies s\ge k_j/6 and k_j-2(s-1)\ge s. Deleting the positions omitted from the two windows shows that every cross-window edit distance is at least k_j-2(s-1). The probability of any cross-collision is at most d^2e^{-\lambda}\le1/2, so T_{j,s}\ge s\ge k_j/6. Blockwise edit scripts concatenate; hence the sum of the block distances dominates the whole-word distance. The factor six makes \Phi_n noncontracting.

Corresponding segments in an arbitrary alignment. Fix an arbitrary longest common subsequence matching of x,y, of size n-k, where k=r_n(x,y). Let t_j be the number of matched source positions strictly before p_j. Choose target boundaries

so that exactly t_j matched target positions precede q_j. For an internal boundary, take q_j to be the position of target match number t_j+1 if it exists, and take q_j=n otherwise. This gives nondecreasing boundaries and permits repeated boundaries and empty target segments. The matching pairs exactly the matched positions of [p_j,p_{j+1}) with those of [q_j,q_{j+1}).

Let A_j,B_j be the numbers of unmatched source and target positions in the prefixes ending at these boundaries. Since p_j=t_j+A_j, q_j=t_j+B_j, and 0\le A_j,B_j\le k,

Let a_j,b_j count unmatched positions in the source block and its aligned target segment, and put e_j=a_j+b_j. These segments partition the two words, so

In a matched pair belonging to these segments, the relative indices measured from p_j,q_j differ by at most e_j: their numbers of preceding matched positions agree, and their preceding unmatched counts are bounded by a_j,b_j.

Pairing the original window lists. Put L=\ell_j-s+1. Pair the source window starting at p_j+r with the target window starting at q_j+r precisely when both belong to the original fixed-block lists. Thus

The two intervals of allowed starts overlap in \max(0,s-|q_j-p_j|) positions. Exactly \min(s,|q_j-p_j|) windows on each side remain unpaired.

Consider a paired window. At most a_j\le e_j of its source positions are unmatched. For any other source position, its partner’s relative index differs by at most e_j. Therefore only matched source positions within e_j positions of an endpoint can have partners outside the target window; there are at most 2e_j of them. The windows have a common subsequence of length at least \max(0,L-3e_j), and (73) gives

This reasoning also covers a target window extending outside its aligned segment. Every partner of a matched source-block position lies in that segment, and the argument counts precisely those partners that remain inside the target window. It requires no condition on the other target positions.

Using the partial pairing in (79), the shorter-map expansion, and (87), we obtain

Each block has at most L_d=1+\lfloor\log_2d\rfloor scales. Summing (91), using (88) and (89), and applying the factor six gives

The last inequality uses k=r_n(x,y)\le\operatorname{ED}(x,y). The chosen alignment serves only to analyze two images; every partition and coordinate of \Phi_n was fixed on the entire domain beforehand.

An alternative expansion estimate from moves. For a single move, a nonexceptional block has s-1 identical windows and therefore contributes at most two. In either of the at most two exceptional blocks, windows at equal starts have edit distance at most two. Their embedded distance is at most 2D', so (79) gives a block cost at most 4s\alpha_sD'=4\lambda D'. Thus, at each scale,

Summing scales, multiplying by six, and following the r_n(x,y)\le\operatorname{ED}(x,y) moves gives the alternative expansion estimate

The arbitrary-alignment argument established this order of expansion without decomposing the comparison into moves.

Depth and varying lengths. Both estimates have the form E_n\le A(B+D') with A=C\log^2(2d) for an absolute C. The identity

follows because both sides are the least integer t with n\le B^2t. It bounds the recursion depth by h=\lceil\log_Bd\rceil. The induction used in (85) gives expansion at most

For sufficiently large d, take B=\lceil\exp(\sqrt{\log d\,\log\log d})\rceil. The logarithm of this bound is then O(\sqrt{\log d\,\log\log d}).

Finally, work over \Gamma=\Sigma\cup\{\ast\} and append the fresh symbol to length d. Erasing \ast from a padded edit script projects each operation to at most one edit, and (73) and (75) give

Thus \Phi_d(\widehat x) proves Theorem 8.1 on all shorter words, including the empty word, with an additional expansion factor two.

8.5 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

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

and the move path gives

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.