Edit distance in L1: alignment obstructions and matching exponential scales

Source and verification

This article explains family 099 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Edit distance and a common L1 representation

Ordinary edit distance $\mathrm{ED}(x,y)$ counts the least number of single-symbol insertions, deletions, and substitutions converting one word into another; each operation costs one. An insertion changes the positions of an entire suffix, making alignments more important than coordinatewise comparison.

For a finite alphabet $\Sigma$, let ${\Sigma }^{\le d}$ contain all words of length at most $d$, including the empty word. Only the endpoints are length constrained; an edit script may pass through longer words.

An injective map $f$ into ${\ell }_1$ has distortion

$$\begin{array}{rl}& \left(\underset{x\ne y}{\max }\frac{\Vert f(x)-f(y){\Vert }_1}{\mathrm{ED}(x,y)}\right)\\ & \times \left(\underset{x\ne y}{\max }\frac{\mathrm{ED}(x,y)}{\Vert f(x)-f(y){\Vert }_1}\right).\end{array}$$

Write $E_{\Sigma }(d)$ for the infimum of this quantity. Target dimension and computation time are unrestricted. The problem asks for one representation of every pair, not an algorithm estimating one supplied distance.

🏷️ Matching logarithmic scales

Statements in the family

There are absolute $c,C>0$ such that, for all sufficiently large $d$ and every finite alphabet with at least two symbols,

$$\begin{array}{c}{s}_d=\sqrt{\log d\log \log d},\\ \exp (c{s}_d)\le E_{\Sigma }(d)\le \exp (C{s}_d).\end{array}$$

The lower bound already occurs on a subset of binary words of one common length at most $d$. Constants are independent of alphabet size. (OpenAI, 2026) (OpenAI, 2026b) (OpenAI, 2026c)

Equivalently, $\log E_{\Sigma }(d)$ has the stated order. This is not a constant-factor estimate of $E_{\Sigma }(d)$ itself, because the constants sit inside exponentials. The growth is faster than every fixed power of $\log d$ and slower than every fixed positive power of $d$.

The main manuscript uses a marked-row lower construction and an upper reduction to the established Ostrovsky–Rabani theorem. The circle companion provides two further lower constructions, binary codes, and a finite histogram upper construction. The tree companion gives two independent lower routes and invokes the circle companion for its upper-bound consequence.

🏷️ Alignments and the split-row obstruction

Let $\mathrm{LCS}(x,y)$ be the length of a longest common subsequence. Insertion–deletion distance satisfies

$$\begin{array}{c}\Delta (x,y)=|x|+|y|-2\mathrm{LCS}(x,y),\\ \mathrm{ED}\le \Delta \le 2\mathrm{ED}.\end{array}$$

The second inequality follows by replacing each substitution by one deletion and one insertion. Thus controlling every increasing matching of equal symbols gives an edit-distance lower bound up to a factor of two.

The constructions arrange lower-level words into rows. Tags ensure that different payload slots cannot match, and long markers separate rows. If a source row matches only one target row, it inherits the lower-level separation estimate. If it splits across target rows, the matching must skip a long target interval or marker.

The essential accounting fact is that skipped intervals charged to distinct source rows are disjoint. Otherwise the argument could count the same missing symbols many times. This split-row lemma is how the manuscripts control arbitrary alignments; row boundaries are never assumed to line up. (OpenAI, 2026a) (OpenAI, 2026b) (OpenAI, 2026c)

🏷️ Cuts, frequencies, and cheap shifts

Every finite $L_1$ metric is a nonnegative sum of cut distances $|1_S(x)-1_S(y)|$. Consequently an inequality proved for every cut passes to every $L_1$ embedding.

The word states carry periodic shifts. Advancing all row indices can be cheap: delete a short initial block and reinsert it at the end. A distinguished shift is arranged to remain expensive under every alignment.

Fourier expansion of a cut on the finite state space compares its average change under these shifts. Characters supported on only a few components are detected by simultaneous shifts because distinct prime periods prevent cancellation. Characters involving many components are instead detected by averages of individual component shifts. An image in $L_1$ must obey this analytic comparison, while the source words violate it by a large factor. (OpenAI, 2026a)

In the circle companion, states are quantized phases at tree leaves. One construction includes complete residue lists, allowing denominator losses in an inductive separation argument to reset. The other uses an excluded-coordinate prime pattern: two putatively cheap child phases would force a forbidden small nonzero difference. Both use an arithmetic branching estimate to force sufficiently large total leaf frequency. (OpenAI, 2026b)

The tree companion gives a finite-period hierarchy and a separate circle hierarchy. In both, characters escaping cheap-shift tests must propagate through many children. The alignment proof and the Fourier proof meet at the same distinguished displacement, but each controls a different side of the distortion inequality. (OpenAI, 2026c)

🏷️ The depth calculation and binary transfer

At depth $k$, the source estimates have the form

$$\begin{array}{rl}\log D_k& \gtrsim k\log k,\\ \log L_k& \lesssim k^2\log k,\end{array}$$

where $L_k$ is word length. Choosing $k\asymp \sqrt{\log d/\log \log d}$ makes $L_k\le d$ with suitable constants and gives

$$k\log k\asymp \sqrt{\log d\log \log d}.$$

Choosing $k$ directly from the cap supplies every sufficiently large $d$, rather than only a subsequence.

Tags initially require a larger alphabet. A binary code must resist shifted and cross-block matches, not merely have large Hamming distance between codewords. The circle manuscript provides logarithmic-width substitutions with absolute edit distortion on equal-length inputs. The shorter delimiter reductions used by other routes lose a factor polynomial in $k$, harmless beside $\exp (ck\log k)$.

These coding claims should retain their length conventions. A code proved for one prescribed length or for pairs of equal lengths does not automatically give a uniform statement on all finite words.

🏷️ The upper construction

The main manuscript transfers the known fixed-length binary upper theorem using alphabet hashing, padding, and averaging, with constants uniform over all finite alphabets and with the empty word included. (OpenAI, 2026a)

The circle companion develops the recursive construction directly: divide words into blocks, collect overlapping windows, apply shorter-word representations, and record histograms of cut memberships. Histograms absorb small alignment shifts, while a recursion balances window length against accumulated distortion. Averaging yields a deterministic finite-dimensional map because the domain and the set of relevant cuts are finite. (OpenAI, 2026b)

The lower result is therefore an obstruction to all embeddings, while the upper result supplies one common representation. Neither is merely a pairwise approximation guarantee.

🏷️ Key steps and proof outlines

Split rows force disjoint losses in every alignment

An increasing matching pairs equal symbols in order. Call a source row split if its matched symbols reach at least two target rows. For an unsplit row, tags confine matching to the corresponding payload slot, so the induction hypothesis supplies a lower bound for its unmatched symbols. For a split row, choose a target marker lying between two of its matched target pieces. The source payload cannot match that marker.

The crucial order argument is that markers charged to distinct split source rows are disjoint: the increasing matching places all matches of an earlier source row before those of a later row. Therefore one target interval cannot be charged repeatedly. If $s$ rows split among $T$ rows, the proof obtains one loss bound from the $T-s$ unsplit rows and another from the $s$ crossed markers. Balancing them gives a lower bound independent of how the alignment crosses row boundaries. This is the combinatorial induction used by all three lower constructions. (OpenAI, 2026a)

Fourier analysis imposes a universal inequality on cut images

For a cut indicator $f$ on a finite periodic state space, its mean squared change under translation $h$ has Fourier expansion

$$\mathbb{E}|f(x+h)-f(x){|}^2=\sum _{\chi }|\hat{f}(\chi ){|}^2|\chi (h)-1{|}^2.$$

Because $f$ takes values zero and one, the square equals the absolute cut difference. Hence a pointwise comparison between the character multipliers for several translations yields a comparison between expected cut separations. Integrating nonnegative cut weights transfers it to every $L_1$ metric.

The hierarchy chooses cheap translations whose multipliers detect most characters. A character supported on few components is caught by a simultaneous shift, with coprime periods preventing cancellation. A character spread across many components is caught by averages of individual shifts. Any character escaping both tests must propagate nontrivial frequency through many descendants, which is quantitatively expensive. The distinguished translation remains expensive in edit distance by the split-row argument but cannot remain proportionally expensive under this $L_1$ comparison.

The companion hierarchies solve different arithmetic problems

The finite-circle construction with denominator resets includes complete residue lists. After an inductive step creates a denominator loss, a complete list resets the phase separation scale. The excluded-coordinate construction instead arranges prime patterns so that two allegedly cheap child phases would imply a forbidden small nonzero difference. Both produce sufficient frequency growth down the tree, but their arithmetic mechanisms are different. (OpenAI, 2026b)

The tree companion gives a finite-period version with nested orders and a circle-phase version. In the finite version, disjoint coordinate supports and coprime new primes compute the order of a parent translation exactly. In the circle version, leaf quantization uses half-open intervals; a shift at least one interval width changes the symbol even at boundary points. The induction then compares every source row with every target row, retaining arbitrary alignment offsets. (OpenAI, 2026c)

Binary codes must survive shifted matching

Large Hamming distance only compares aligned positions. Edit alignments can shift a codeword or match parts of several codewords, so the source uses segment-LCS estimates and delimiters. For two fixed length-$a$ segments of independently random binary codewords, a prescribed increasing matching of size $s$ has probability $2^{-s}$. Union-bounding over its two position lists gives ${\left(\genfrac{}{}{0ex}{}{a}{s}\right)}^2{2}^{-s}$, exponentially small when $s$ is close to $a$.

A finite union bound produces codewords for which every relevant segment pair has this property. The matching analysis distinguishes intact blocks from blocks crossing boundaries and charges broken delimiters to unmatched symbols. This yields edit-distance control with the stated length convention. Polynomial losses in the tree depth remain negligible compared with the exponential lower bound.

Histograms absorb alignment shifts in the upper construction

The recursive upper map examines overlapping windows of shorter words and applies shorter-scale cut coordinates. It then records counts of memberships in each cut, rather than insisting that window positions align exactly. A short edit changes only a controlled boundary portion of these histograms; a large subsequence deficit forces a substantial discrepancy at some recursive scale. Balancing block size against recursive distortion gives the matching exponent.

For arbitrary alphabets, random hashing to $4d^2$ labels never increases insertion–deletion distance. For any fixed pair of words of length at most $d$, at most $2d$ original letters occur, so a collision union bound leaves a fixed positive chance that all those letters receive distinct labels. Averaging the hashed maps therefore preserves a lower bound uniformly in alphabet size. Padding and the empty-word convention are handled before applying the fixed-length theorem. This produces one common embedding after averaging, not a different favorable hash for each pair.

See Also

Graph embeddings in L1 introduces the cut representation from the constructive side. Dimension reduction separates existence of an embedding from bounds on target dimension and computation.

Pairwise edit-distance approximation estimates one supplied pair without constructing a common embedding of the whole string space.

🏷️ Manuscripts and verification scope

• Edit Distance in ${\ell }_1$: Matching Bounds up to Constants in the Exponent — pinned manuscript and companion source.
• Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance — pinned manuscript and companion source.
• Tree Constructions for the ${\ell }_1$ Distortion of Binary Edit Distance — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The scope distinguishes the main headline bounds, the circle manuscript’s lower constructions, coding and histogram upper bound, and the tree manuscript’s two binary lower constructions. The tree scope does not include its separate coding theorem or the upper theorem it imports. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. Edit Distance in ℓ₁: Matching Bounds up to Constants in the Exponent.

🐻  OpenAI 2026b. Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance.

🐻  OpenAI 2026c. Tree Constructions for the ℓ₁ Distortion of Binary Edit Distance.