History and the embedding question

The single-symbol error model is classical in coding and sequence comparison. Levenshtein studied binary codes correcting insertions and deletions [11], and Wagner and Fischer formulated string correction through increasing partial alignments [17]. An embedding asks for one set of coordinates that represents every pair in a domain. It is a different task from estimating the distance of one given pair of words. For supplied pairs of binary words, [13] gives a randomized approximation scheme with almost-linear worst-case expected time for each fixed rational accuracy.

Ostrovsky and Rabani proved an \(\ell_1\) distortion bound \(\exp(O(\sqrt{\log n\,\log\log n}))\) for binary words of a fixed length \(n\) [15]. Their recursion compares overlapping substrings and represents their distributions in smaller metric spaces. They also noted extensions to larger alphabets and varying lengths. For the upper bound used at the end of this paper, the companion uniform upper embedding theorem [14] gives the full quantitative statement on \(\Sigma^{\leq d}\) with constants independent of the finite alphabet.

On the lower-bound side, Andoni, Deza, Gupta, Indyk and Raskhodnikova realized complete bipartite graph metrics in binary edit distance and obtained \(\ell_1\) distortion approaching \(3/2\) [1]. Their witness uses three adjacent word lengths. Khot and Naor developed Fourier methods for nonembeddability and obtained an edit-distance lower bound of \((\log n)^{1/2-o(1)}\) for binary words of a fixed length [8]. Their insertion–deletion metric and the ordinary metric used here differ by at most a factor of two. Krauthgamer and Rabani then proved an \(\Omega(\log n)\) lower bound for binary words of length \(n\) [10]. Khot and Naor used Boolean noise sensitivity, while Krauthgamer and Rabani sharpened the obstruction through an influence inequality for bit flips and cyclic shifts. These cut and shift arguments are methodological predecessors of the proofs here. A cut records which pairs a binary coordinate separates, and Fourier coefficients describe how that separation changes under translations. We prove the particular translation estimates needed for our trees.

Alphabet reduction also has a substantial history. Schulman and Zuckerman use separation between long intervals of distinct codewords in concatenated insertion–deletion codes [16], and synchronization strings protect positions against insertion and deletion errors [5]. More directly, Bhattacharya, Dey, Goldenberg and Koucký state a map on all finite words with an insertion–deletion guarantee normalized by the sum of the word lengths, for pairs of positive total length. The block substitution used to prove their stated theorem has logarithmic width and, for a fixed error parameter, a constant target alphabet [2]. For equal-length inputs, their stated normalized guarantee, combined with the elementary delimiter construction below, gives a binary reduction with logarithmic width and absolute distortion. Our lower proofs do not use that result. They use the short delimiter code, whose width-dependent loss is harmless at the tree scale; the appendix gives a separate constant-distortion code for one prescribed word length. For comparison, the isometric Hamming-to-edit embedding of Bhattacharya et al. [3] starts from a different input metric. The conversions proved here compare edit distance on the source words with edit distance on their binary encodings.

Two independent tree proofs

Both constructions use an ordered tree. A leaf has a state coordinate and produces a symbol carrying its leaf label. An internal node produces a long list of rows, each containing its child words in their fixed order. Advancing the row index deletes a few rows at one end and inserts a few at the other, so it is inexpensive. A distinguished second shift must instead separate the words even when an alignment crosses row boundaries.

The shared alignment lemma in Section 2 handles this difficulty. Leaf labels preserve child indices, not row indices. An unsplit source row loses symbols because its child words are separated from the corresponding target words. A split source row forces a long unmatched target interval between consecutive matches. The intervals charged by different source rows are disjoint. Thus separation in every comparison of two rows implies separation of the whole words, without assuming that row boundaries match.

The two constructions arrange the shifts differently. In the finite tree of Section 3, a child’s period is its parent’s period times a new prime. At an internal node, a vector \(u_v\) advances rows and a multiple \(w_v\) has the parent period. The distinct prime factors prevent a difference of row indices from cancelling the distinguished shift in too many children. This gives a deterministic separation proof on a finite group. For a Fourier character, activity at a node with few active children has a short period and is detected by an average of inexpensive row shifts. A character escaping every such test must be active on many leaves; individual leaf changes then bound its contribution. The section closes with binary witnesses for every large cap.

The circle tree in Sections 4 and 5 uses quantized phases instead of finite residues. Random prime lists and coefficients make the root half-turn separate every base phase. The probabilistic assertion is only for one fixed shift; the all-phase conclusion follows deterministically from the alignment lemma. In its Fourier argument, tiny rotations detect large integer frequency sums and rational row shifts detect failed prime congruences. When both tests fail, divisibility forces every nonzero sum to continue through many children. This supplies the second binary proof without using the finite tree.

Both routes use the same elementary delimiter code from Section 2. Its distortion loss grows with the block width, but that width is only \(O(k\log k)\) here and does not change the logarithmic lower-bound scale. Appendix 7 proves a stronger, separate alphabet-conversion theorem: for words of one prescribed length \(M\) over at most \(M\) letters, blocks of width \(M^2\) preserve edit distance up to scale and an absolute factor \(804\). Its proof is independent of both trees, and neither headline lower bound requires this stronger conversion.

Subsequence matchings

A common subsequence matching of words \(x=x_1\cdots x_a\) and \(y=y_1\cdots y_b\) is a list of pairs \((i_1,j_1),\ldots,(i_s,j_s)\) whose two index lists are strictly increasing and for which \(x_{i_t}=y_{j_t}\) for every \(t\). Its largest possible size is \(\operatorname{LCS}(x,y)\). The insertion–deletion distance is \[\Delta(x,y)=|x|+|y|-2\operatorname{LCS}(x,y).\] Indeed, symbols of \(x\) that survive an insertion–deletion script form a common subsequence; conversely, retaining a longest common subsequence and deleting and inserting the remaining symbols attains this value. Replacing each substitution by one deletion and one insertion gives \[ \operatorname{ED}(x,y)\leq\Delta(x,y)\leq2\operatorname{ED}(x,y). \tag{1}\] For words of equal length \(n\), put \(r_n(x,y)=n-\operatorname{LCS}(x,y)\). Thus \[ r_n(x,y)\leq\operatorname{ED}(x,y)\leq2r_n(x,y). \tag{2}\] A matching of size \(n-E\) between two length-\(n\) words leaves exactly \(E\) unmatched positions on each side.

The common alignment lemma

Suppose each row consists of one block from each of several pairwise disjoint alphabets, in the same order. An equal-symbol match must then join blocks with the same index, although their row indices can differ. Products of words in the next lemma mean concatenation in increasing index order.

The two inequalities in the proof bound the same number \(E\) using different words: nonsplit rows give source losses, and split rows give target losses. Equal total lengths make the unmatched counts equal. The fixed order, equal block lengths and disjoint tags supply the target gaps; no alignment of row boundaries is assumed. Figure 1 illustrates the gap created by a split row.

Cuts and prime counts

We record two background facts for both constructions. The first turns an \(\ell_1\) distance on a finite set into a nonnegative sum of binary separation tests. This standard cut description is stated, for example, in Section 4 of Linial, London and Rabinovich [12]; the proof below includes a summability bound for maps with infinitely many coordinates.

The second fact supplies all primes used below. We use the elementary binomial-coefficient argument, following the classical prime-product method found, for example, in Erdős [4]. Write \(\pi(x)\) for the number of primes at most \(x\).

A short binary code

The trees initially use leaf labels and hence a growing alphabet. The following code will suffice for both binary lower bounds. It preserves subsequence deficits from below, while its expansion is at most its block width. For the tree alphabets that width will be \(O(k\log k)\), small compared with their eventual distortion lower bounds.

By (2), the lower bound in (7) is at least \(\operatorname{ED}(x,y)/4\). Consequently, if a finite set of equal-length words has \(\ell_1\) distortion at least \(D_0\), its encoded image has distortion at least \(D_0/(4B)\): composing an embedding of the encoded image with \(\mathcal B\) incurs at most the factor \(4B\).

Periods and word construction

Fix a sufficiently large integer \(k\) and put \[ m=20k,\qquad T=k^{20k}. \tag{8}\] Use the full ordered \(m\)-ary tree of depth \(k\), with root \(o\) at depth zero and children \(v1,\ldots,vm\) at each internal node \(v\). By Lemma 4, choose primes \(p_{j,i}\in[k^4,k^5]\) distinct over all pairs \(0\leq j<k\), \(1\leq i\leq m\). Nodes at the same depth use the same list. Define their periods by \[Q_o=2,\qquad Q_{vi}=Q_vp_{j,i} \quad\text{when $v$ has depth $j$}.\] All these primes are odd for large \(k\).

On the finite abelian group \[A=\prod_{u\text{ leaf}}\mathbb Z/Q_u\mathbb Z\] define vectors supported on their respective subtrees: \[ \begin{aligned} w_u&=e_u &&(u\text{ leaf}),\\ u_v&=\sum_{i=1}^m w_{vi},\qquad R_v=\prod_{i=1}^m p_{j,i},\qquad w_v=R_vu_v &&(v\text{ internal at depth }j). \end{aligned} \tag{9}\] Here \(e_u\) increments the coordinate of leaf \(u\).

For \(x\in A\), the leaf word is the single symbol \(G_u(x)=(u,x_u)\). At an internal node, define \[ G_v(x)=\prod_{a=0}^{T-1} \bigl(G_{v1}(x+a u_v)\cdots G_{vm}(x+a u_v)\bigr), \tag{10}\] where the product concatenates the rows in increasing \(a\). Only leaf coordinates below \(v\) affect \(G_v\). At depth \(j\) and height \(h=k-j\), its length is \(L_v=(mT)^h\). Write \[M=(mT)^k,\qquad G=G_o.\] Every symbol retains its leaf label. Thus the alphabets occurring below different children of a node are disjoint, exactly as required by Lemma 2.

Cheap translations and uniform separation

We first bound the cost of advancing rows or changing one leaf. These bounds hold at every state and will later be averaged over \(A\).

We now prove separation for every nonzero residue along the order-\(Q_v\) vector \(w_v=R_vu_v\), uniformly in the initial state.

We have obtained the two geometric facts needed for the obstruction: the root shift \(w_o\) is far at every state, while the shifts in Lemma 7 are cheap. The remaining argument compares their average images under an arbitrary \(\ell_1\) embedding.

Fourier detection of sparse activity

For a finite abelian group \(A\), use uniform probability measure and write \(\widehat A\) for its character group. The following identity represents an averaged \(\ell_1\) displacement through cuts and Fourier coefficients. It is the elementary translation principle underlying the comparison with the cut methods of Khot–Naor and Krauthgamer–Rabani [8, 10].

For a character \(\chi\), call a node \(v\) active when \(\chi(w_v)\ne1\). Let \(\operatorname{wt}(\chi)\) be the number of active leaves. The period design has one useful consequence: activity at a node with few active children is detected by a short average of cheap shifts. Frequencies that escape all these tests must have large leaf support.

Binary witnesses for every sufficiently large cap

The finite tree alphabet contains one symbol for each leaf and each residue in its coordinate group. Since \(Q_u\leq2k^{5k}\) at every leaf, its size \(K\) satisfies \[K\leq 2m^k k^{5k}=2(20k)^k k^{5k}.\] Choose \[t_k=\left\lceil\log_2\bigl(2(20k)^k k^{5k}\bigr)\right\rceil, \qquad B_k=2t_k+3=O(k\log k).\] There are enough \(t_k\)-bit labels for all symbols, so Lemma 5 applies with width \(B_k\). Its distortion loss is at most \(4B_k\). Hence Proposition 10 supplies a finite binary witness of the single length \[ d_k=B_kM=B_k[20k\cdot k^{20k}]^k \tag{18}\] whose distortion is at least \[D_k:=\frac{(k/4)^k}{4C_1B_k}.\] The separated root pair and the lower bound in Lemma 5 ensure that the witness contains at least two words.

The explicit widths \(B_k\) and lengths \(M\) increase with \(k\), so \(d_k\) increases to infinity, independently of which admissible primes were chosen. Moreover, \[\begin{align*} \log d_k&=20k^2\log k+k\log(20k)+\log B_k\\ &=20k^2\log k+O(k\log k),\\ \log D_k&\geq c'k\log k \end{align*}\] for an absolute \(c'>0\) and all sufficiently large \(k\). Given a sufficiently large integer \(d\), choose \(k\) with \(d_k\leq d<d_{k+1}\). Then \(\log d\leq Ck^2\log k\) and \(\log\log d\leq C'\log k\) for absolute constants. Thus \[\log D_k\geq c\sqrt{\log d\,\log\log d}.\] The witness of length \(d_k\leq d\) proves Theorem 1 for every sufficiently large cap.

Prime groups and row increments

Fix a sufficiently large integer \(k\) and set \[ g=16k,\qquad m=gk^2=16k^3,\qquad R=k^{8k},\qquad T=k^{52k}. \tag{19}\] Let \(\mathbb T=\mathbb R/\mathbb Z\), with \(|t|_{\mathbb T}\) denoting the circle distance from \(t\) to zero. Use a full ordered \(m\)-ary tree of depth \(k\), and divide the children of each internal node into \(g\) groups of \(k^2\) children. Each leaf phase will be quantized into \(R\) intervals, and each internal word will contain \(T\) rows.

Let \(\mathcal P_k\) be the primes in \([k^2,k^3]\). Lemma 4 gives \(|\mathcal P_k|>100g\) for large \(k\). At each internal node \(v\), independently between nodes, choose an ordered list \(r_{v,1},\ldots,r_{v,g}\) of distinct members of \(\mathcal P_k\), uniformly without replacement. Put \[P_v=\prod_{j=1}^g r_{v,j}\leq k^{48k}.\] To specify the increment of a child \(vi\) in group \(j\), choose \(z_{vi}\) uniformly from \(\{0,\ldots,r_{v,j}-1\}\) and define \[ c_{vi}=1+z_{vi}\frac{P_v}{r_{v,j}}. \tag{20}\] Conditionally on all prime lists, all these residues are independent. The increment \(c_{vi}/P_v\) has the decomposition \[\frac{c_{vi}}{P_v}=\frac1{P_v}+\frac{z_{vi}}{r_{v,j}}.\] Thus every child has a common drift of \(1/P_v\), together with an independently chosen step on its group’s prime grid. The same formula isolates the groups arithmetically: if \(\ell\ne j\), then \(c_{vi}\equiv1\pmod{r_{v,\ell}}\). At each selected prime, only coefficients from its own group can differ from one.

Associate a phase \(w_u\in\mathbb T\) to each leaf \(u\), and write \(w\in\mathbb T^{m^k}\) for the full vector. For a subtree vector \(\omega\), the notation \(\omega+t\) means addition of \(t\) to every coordinate of that vector. At a leaf, put \[X_u(w_u)=\bigl(u,\lfloor Rw_u\rfloor\bigr),\] using the representative of \(w_u\) in \([0,1)\). At an internal node, define \[ X_v(\omega)=\prod_{a=0}^{T-1} \left( X_{v1}\!\left(\omega_{v1}+\frac{a c_{v1}}{P_v}\right) \cdots X_{vm}\!\left(\omega_{vm}+\frac{a c_{vm}}{P_v}\right) \right), \tag{21}\] where \(\omega_{vi}\) is the subvector on the leaves below \(vi\). The product concatenates rows in increasing \(a\). At height \(h\), the word length is \((mT)^h\). The root map \(X=X_o\) has length \[ N=(mT)^k \tag{22}\] over the alphabet \(\Gamma=\{(u,b):u\text{ a leaf},\ b\in\{0,\ldots,R-1\}\}\), of size \(m^kR\). For fixed construction data, every position in this word quantizes one leaf phase plus a fixed offset. Hence the range of \(X\) is finite and \(X\) is measurable.

Good shifts give separation at every phase

Consider \(X_v(\omega)\) and \(X_v(\omega+t)\), where the scalar \(t\) is added to every leaf phase below \(v\). In a comparison of source row \(a\) with target row \(a'\), child \(vi\) receives the relative shift \[t+(a'-a)\frac{c_{vi}}{P_v}.\] The tagged-row lemma will separate the two words if enough children are separated for every row pair. Since each \(c_{vi}\) is an integer, the displayed shift depends only on \(a'-a\) modulo \(P_v\). This leads to a recursive condition on \(t\) alone, independent of the base phase. Set \[\epsilon=R^{-1},\qquad \delta=1/64,\qquad \gamma=1/128=\delta/2.\] Call a shift \(t\) eligible if \(|t|_{\mathbb T}\geq\epsilon\).

The condition asks for at least \(\delta m\) children, interpreted as a real threshold on their integer count. Its deterministic consequence is the following separation estimate.

It remains to make the one root shift \(t=1/2\) good. We prove a statement for each fixed eligible shift that can be propagated from a child to its parent. The all-phase conclusion will then follow from the deterministic lemma.

The probability of a good fixed shift

Fix this realization for the rest of the torus argument. The prime lists and coefficients now have fixed values. Only their stated size and congruence properties will be used below.

Pointwise and averaged edit costs

For a node \(v\), let \(e_v\in\mathbb R^{m^k}\) have entry one on the leaves below \(v\) and zero elsewhere. At an internal node, define \[ h_v(a)=\frac a{P_v}\sum_i c_{vi}e_{vi}\pmod1 \qquad(a\in\mathbb Z/P_v\mathbb Z). \tag{25}\] This is well defined because each \(c_{vi}\) is an integer. Let \(q\) be the depth of \(v\).

The Fourier identity on the torus

The next identity expresses averaged \(\ell_1\) distances through nonnegative frequency weights. It is the continuous counterpart of Lemma 9; its averaging measure and its integer frequencies are different.

Two tests and forced branching

Apply the notation of Lemma 15 with \(n=m^k\). For a frequency \(\xi\in\mathbb Z^{m^k}\) and a node \(v\), define its integer summary \[s_v=\langle\xi,e_v\rangle =\sum_{u\text{ leaf below }v}\xi_u.\] Thus \(s_v=\sum_i s_{vi}\) at an internal node and \(s_u=\xi_u\) at a leaf. The multiplier of the root half-turn is \(1-\cos(\pi s_o)\), equal to two for odd \(s_o\) and zero for even \(s_o\). We bound it using tests that cover every frequency with \(s_o\ne0\).

The cutoff and congruence tests have different jobs. The divisibility argument forces branching only after all summaries are known to have absolute value less than \(Q\). It would not rule out a large nonzero integer divisible by many of the selected primes.

The binary obstruction and every length cap

Apply Lemma 5 to the torus alphabet of size \(A=m^kR\), choosing labels of length \(\lceil\log_2A\rceil\). Write \(\mathcal B\) for the resulting encoding. Its block width is \[ B=2\lceil\log_2(m^kR)\rceil+3=O(k\log k). \tag{32}\] The encoded image consists of binary words of one length \(BN\). It has at least two points, since the lower code bound preserves the positive root separation in (23). We apply the detection inequality directly to an embedding of this encoded image; the code’s width will enter only the upper cost estimates.

Take any embedding \(f\) of the encoded image with distortion \(D\) and rescale it to be noncontracting with expansion at most \(D\). Set \[F(w)=f(\mathcal B(X(w))),\qquad L(h)=L_F(h).\] The map \(F\) is measurable with finite range, so Lemma 16 applies. The pointwise separation, the three costs in Lemma 14, and the code bounds give \[\begin{align*} L(e_o/2)&\geq\gamma^kN/2,\tag{33}\\ L(h_v(a))&\leq2DBNm^{-q}P_v/T &&(v\text{ internal},\ a\in\mathbb Z/P_v\mathbb Z),\tag{34}\\ L(\eta e_v)&\leq DBNm^{-q}R/Q &&(v\text{ any node},\ 0\leq\eta\leq1/Q),\tag{35}\\ L(\eta e_u)&\leq DBNm^{-k} &&(u\text{ leaf},\ \eta\in\mathbb T). \tag{36}\end{align*}\] For the second line, use the representative \(0\leq a<P_v\) in the pointwise cost proof; the displacement itself depends only on the residue. The third line uses the Haar-average cost, with no pointwise claim about tiny rotations.

There are \(m^q\) nodes at depth \(q\). Thus the factors \(m^{-q}\) cancel when the upper bounds are summed over a depth in (30). We obtain \[\begin{align*} L(e_o/2) &\leq DBN\left( 4(k+1)\frac RQ+4k\frac{k^{48k}}T+2k^{-k}\right)\\ &\leq C'DBNk^{-k}, \end{align*}\] for an absolute \(C'\), because \(R/Q=k^{-4k}\) and \(k^{48k}/T=k^{-4k}\). Comparing this with (33) gives \[ D\geq\frac{(\gamma k)^k}{2C'B}, \qquad\gamma=1/128. \tag{37}\] The denominator retains the width \(B\) from the delimiter code. Since \(B=O(k\log k)\), the logarithm of the right side is at least \(c_{\mathrm{tor}}k\log k\) for an absolute \(c_{\mathrm{tor}}>0\) and all sufficiently large \(k\).

The binary word length satisfies \[ \log(BN)=52k^2\log k+O(k\log k). \tag{38}\] For every sufficiently large integer \(d\), put \(\tau=\log d\) and choose \(k=\lfloor a\sqrt{\tau/\log\tau}\rfloor\), where \(a>0\) is a sufficiently small absolute constant. There is an absolute \(C_2\) such that \(\log(BN)\leq C_2k^2\log k\) for all large \(k\). Since \(k\leq a\sqrt{\tau/\log\tau}\) and \(\log k\leq\log\tau\) eventually, choosing \(C_2a^2\leq1/2\) gives \(\log(BN)\leq\tau/2<\tau\). Also, for all large \(\tau\), \[k\geq\frac a2\sqrt{\frac \tau{\log\tau}}, \qquad \log k\geq\frac13\log\tau.\] It follows that \(k\log k\geq(a/6)\sqrt{\tau\log\tau}\). The finite set \(\{\mathcal B(X(w)):w\in\mathbb T^{m^k}\}\subseteq\{0,1\}^{BN}\) therefore has distortion at least \(\exp(c\sqrt{\log d\,\log\log d})\) and has \(BN\leq d\). This completes the torus proof of Theorem 1 for every sufficiently large cap.