Episode 099, October 2026

Sharp at last?

How much edit distance must be distorted to fit into ℓ₁: the claimed answer is exp(Θ(√(log d · log log d)))

Covers result 099 in OpenAI’s catalog: all 3 papers. See its connections to other results and the work it cites.

Play Episode 099: Sharp at last? Rows of tagged slots followed by long markers, and a binary word with its cyclic shift aligned at a cost of two edits.

6:09. English captions available. The video loads from YouTube when you press play.

Chapters

The claims, in plain words

The edit distance between two strings is the least number of single-symbol insertions, deletions and substitutions that turn one into the other. Because an insertion or deletion shifts everything after it, the distance depends on the best alignment: cutting the first symbol of a word and pasting it at the end costs at most two edits, though it can change most positions. Many algorithms would be simpler with an ℓ₁ distance, a sum of absolute differences of coordinates, instead. The question is the least distortion D such that some map into ℓ₁ keeps every edit distance within a factor D, after rescaling, for all strings of length at most d.

Ostrovsky and Rabani embedded the binary strings of length d with distortion exp(O(√(log d · log log d))), and noted extensions to other alphabets and lengths. Lower bounds grew from close to 3/2 (Andoni, Deza, Gupta, Indyk and Raskhodnikova) to order √(log d / log log d) (Khot and Naor) and order log d (Krauthgamer and Rabani), leaving a large gap.

Result 099 is three OpenAI preprints dated September 27, 2026: the main paper (15 pages) and two companions, on finite circles, binary codes and histogram embeddings (33 pages) and on tree constructions (23 pages). The main paper claims that for absolute constants c and C, every large d and every finite alphabet with at least two symbols, the least ℓ₁ distortion lies between exp(c √(log d · log log d)) and exp(C √(log d · log log d)). So the Ostrovsky–Rabani exponent is sharp up to constant factors, and binary strings of one common length already force the lower bound. The companions give four further lower-bound constructions, from circles and from trees, and a complete histogram embedding for the upper bound.

What it doesn’t claim

Only the exponent is determined: the paper does not specify the constants c and C, and the distortion itself could still improve by a factor that grows with d, as long as the exponent keeps its order. Nothing is claimed about computing the embedding quickly. The main paper takes Ostrovsky and Rabani’s fixed-length theorem as an input and extends it to all alphabets and lengths.

Where it stands

Posted as preprints: OpenAI, three preprints dated September 27, 2026, released October 6
Peer reviewed: Not yet
Checked in Lean: OpenAI published Lean proofs of the two-sided bound and the four further lower-bound constructions; we have not run the checks

Last checked October 19, 2026. The preprints have not been revised. OpenAI published Lean formalizations matched against four separate statements. The main two-sided bound, matched against its comparator statement, takes 45 files and 6,275 lines and proves its own histogram upper embedding instead of citing Ostrovsky and Rabani; it fixes the constants at c = 1/1200 and C = 32, beyond a threshold it does not compute. The circle paper’s full statement and the two tree constructions take about 150 more files. We found no unproved steps. We have not run the checks. The papers are not among those OSVerify reviewed, and we have seen no expert review.

How the lower bound goes

Rows, payloads and markers. Words are built level by level. A word is a long list of rows; each row holds a payload of lower-level words in fixed slots, each slot with its own tag so that different slots cannot match, followed by a marker of a fresh symbol as long as the payload. The lower-level words depend on states in many components; in each, a distinguished step cycles the state with a prime period, with different primes for different components. Advancing every component at once shifts the row list by one, which costs only the deletion and insertion of one row.
The distinguished step costs. Advancing only the distinguished component changes it in many separately tagged slots. Pairing row i with row i leaves those slots apart; any other pairing, by a row shift shorter than the word, leaves many of the other prime-period components apart. An alignment that spreads one source payload across several target rows skips a whole marker in between, and the skipped markers are disjoint. So every alignment pays, and relative to the word length the guaranteed separation shrinks by a factor of 24 per level.
The ℓ₁ side. A finite ℓ₁ metric is a nonnegative sum of cut metrics, and each cut is expanded in Fourier characters on the product of the cycles. A character involving few components is caught by the simultaneous step: with distinct prime denominators its phase change is never a whole number, and with few denominators it stays well away from one. A character involving many components is caught by the average of the single-component steps. After k levels, any ℓ₁ map must distort the words by at least (h/24)^k/(16w) = exp(Ω(k log k)), with h = 10k, while the logarithm of the word length is O(k² log k). A delimiter code makes the words binary, and choosing k of order √(log d / log log d) gives the exponent √(log d · log log d).

The numbers in the video

Kitten to sitting takes 3 edits. A cyclic shift of a random 1,000-bit word changes 508 positions, at an edit cost of 2.
The exact least ℓ₁ distortion of tiny sets, by linear programming over cut metrics: 8/7 for the 8 binary words of length 3 (127 cuts), 5/4 for the 16 words of length 4 (32,767 cuts), and 4/3 for the 15 words of length at most 3 (16,383 cuts).
For the primes 2, 3, 5, 7 and 11, none of the 2,309 nonzero characters has a whole-number phase change; for example 1/2 + 2/3 + 4/5 = 59/30.
The bar chart compares log log d with √(log d · log log d), constants set to 1: 2.6 and 6.0 at d = 10⁶, 4.0 and 14.9 at d = 10²⁴, 5.4 and 35.4 at d = 10¹⁰⁰.

Read the source

Edit Distance in ℓ1: Matching Bounds up to Constants in the Exponent (PDF), 15 pages.
Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit Distance (PDF), 33 pages.
Tree Constructions for the ℓ1 Distortion of Binary Edit Distance (PDF), 23 pages.
The Lean scope note.
The collection’s catalog, where this is result 099.

The 3 papers in this result

OpenAI groups related papers, such as alternative proofs, supporting results and consequences, into one result; we label the first paper it lists the main paper and the others companions.

Transcript

Read the full script

0:00Edit distance and ℓ₁

The edit distance between two strings is the least number of single-symbol insertions, deletions and substitutions that turn one into the other. Kitten becomes sitting in 3 edits. Inserting or deleting a symbol shifts everything after it, so the distance depends on the best alignment of the two strings. Cut the first symbol of a word and paste it at the end: nearly every position may change, yet the cost is at most 2 edits. For a random 1,000-bit word, that shift changes 508 positions, at a cost of 2. Algorithms would like to replace edit distance by a simpler one, such as the ℓ₁ distance, a sum of absolute differences of coordinates. The question is the cost: the least distortion D such that some map into ℓ₁ keeps every distance within a factor D, after rescaling, for all strings of length at most d. Ostrovsky and Rabani embedded the binary strings of length d with distortion exp(C √(log d · log log d)), and noted extensions to other alphabets and lengths. On the other side, Andoni, Deza, Gupta, Indyk and Raskhodnikova found sets needing distortion close to 3/2, Khot and Naor proved a lower bound growing like √(log d / log log d), and Krauthgamer and Rabani one of order log d. A large gap remained. For tiny sets, the least distortion can be computed exactly. Every finite ℓ₁ metric is a nonnegative combination of cut metrics, so the best map comes from a linear program over cuts. All 8 binary words of length 3 need distortion 8/7. All 16 of length 4 need 5/4, a program with over 32,000 cuts. All 15 words of length at most 3 need 4/3. Small cases like these cannot show the growth rate; that takes the constructions below.

1:58The claims

Result 099 is three OpenAI preprints, all dated September 27. The main one, 15 pages, claims that for every large d and every finite alphabet with at least two symbols, the least ℓ₁ distortion of edit distance on strings of length at most d lies between exp(c √(log d · log log d)) and exp(C √(log d · log log d)), for absolute constants c and C. So the Ostrovsky–Rabani exponent is sharp up to constant factors. The lower bound already holds for binary strings of one common length. Two companions, of 33 and 23 pages, give four further lower-bound constructions, from circles and from trees, and a complete histogram embedding for the upper bound. The paper does not specify the constants, and nothing is claimed about computing the embedding quickly. The main paper takes Ostrovsky and Rabani’s fixed-length theorem as an input, and extends it to all alphabets and lengths. OpenAI published Lean formalizations matched against four separate statements: the main two-sided bound, in 45 files and about 6,300 lines, which proves its own upper embedding instead of citing Ostrovsky and Rabani, and the circle paper’s full statement, with its own histogram embedding, and the two tree constructions, in about 150 more files. The Lean proof of the main bound does fix the constants, at 1/1200 and 32, beyond a threshold it does not compute. We have not run the checks.

3:33How the lower bound goes

The lower bound builds words level by level. A word is a long list of rows. Each row holds a payload of lower-level words in fixed slots, each slot with its own tag so that different slots cannot match, followed by a long marker made of a fresh symbol. The lower-level words depend on states. In each component, a distinguished step cycles the state with a prime period, and different components use different primes. Advancing every component at once shifts the row list by one, which costs only the deletion and insertion of one row. Advancing only the distinguished component is different. It is repeated in many separately tagged slots, so any pairing of rows either keeps those slots apart, or leaves many other components apart. An alignment could spread one payload across several target rows, but then it skips a whole marker, and the skipped markers are disjoint. So every alignment pays, and relative to word length, the guaranteed separation shrinks only by a fixed factor at each level. On the ℓ₁ side, a finite ℓ₁ metric is a sum of cut metrics, and each cut can be expanded in Fourier characters on the product of the cycles. A character involving few components is caught by the simultaneous step: with distinct prime denominators, its phase change is never a whole number, and with only a few denominators it stays well away from one. In our check with the primes 2, 3, 5, 7 and 11, none of the 2,309 nonzero characters failed. A character involving many components is caught by the average of the single-component steps. After k levels, any ℓ₁ map must distort these words by at least exp(c·k log k), while the logarithm of the word length is only of order k² log k. A delimiter code makes the words binary, and solving for k gives the exponent, √(log d · log log d).

5:32Where it stands

The three preprints are not peer reviewed and have not been revised. Lean covers the two-sided bound and the four further lower-bound constructions; we have not run it. They are not among the papers OSVerify reviewed, and we have seen no expert review. If it holds, no embedding of edit distance into ℓ₁ can beat Ostrovsky and Rabani’s exponent by more than a constant factor: √(log d · log log d) is the right exponent. The best constants in that exponent remain open.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.