Squeezed into less?

The claim, in plain words

Take n points and the distances between them, and look for n new points in a space of much lower dimension whose distances are the same up to a factor D, the distortion. In Euclidean space the Johnson–Lindenstrauss lemma does this with a constant times log n dimensions for any fixed D above 1; a random Gaussian map works. In our test, 2,000 random points in 1,000 dimensions, mapped to 400, had largest stretch over smallest stretch about 1.46.

In an L_p space the distance is the p-th root of the sum, or integral, of p-th powers of coordinate differences, and the new points must lie in ℓ_p^d, the same kind of space in d dimensions. For p other than 2 the known bounds were far larger. Ball showed that n(n−1)/2 coordinates always suffice for an exact copy, and that order n² are needed for p below 2. With distortion, Schechtman reached order n for p below 2. Linear maps can need order n dimensions for every p ≠ 2; at p = 1 Brinkman and Charikar showed that even nonlinear maps need a power of n; and for p above 2 Naor and Ren recently showed that order log n is not enough. OpenAI’s catalog presents the new result as answering Naor’s question whether a sublinear dimension is possible.

Result 094 is one OpenAI preprint dated September 23, 2026 (19 pages). It claims that for every fixed p between 1 and ∞ other than 2 and every D above 1, every n-point subset of an L_p space embeds into ℓ_p^d with distortion at most D and d ≤ exp(C (log n)^γ(p)), which is n^o(1): smaller than any fixed power of n. Here γ(p) = 2 − p for p below 2 and 1 − 2/p for p above 2. A packing argument shows that at least log n / log(1 + 2D) coordinates are needed. For exact embeddings the answer is instead of order n²: between ⌊(n − 1)/4⌋² and n(n−1)/2 for n ≥ 9.

What it doesn’t claim

The constant C depends on p and D, with no uniformity claimed near p = 1, near p = 2, or as D approaches 1. The result is existential: no efficient algorithm is claimed, and the maps need not be linear. Neither the exponent γ(p) nor the log n lower bound is claimed optimal, so the optimal dimension with distortion remains open, and p = 1 is not covered.

Where it stands

Posted as a preprint

OpenAI, dated September 23, 2026, released October 6

Peer reviewed

Not yet

Checked in Lean

OpenAI published a Lean proof of the dimension bounds; we have not run the check

Last checked October 19, 2026. The preprint has not been revised. OpenAI published a Lean formalization of the dimension bounds, 45 files and 7,918 lines including the electrical-flow localization from the paper’s appendix, matched against a separate statement, with no unproved steps that we could find. We have not run the check. The paper is not among those OSVerify reviewed, and we have seen no expert review.

How the proof goes

1. Moments to coordinates. Give each point a random real label; across a pair, the difference of labels divided by the pair’s distance is a random increment. If one bounded distribution, with bound K, makes the p-th moments of all increments nearly equal, independent samples give the coordinates by Maurey’s empirical method, about K^2p log n of them. A convexity and separation argument shows it is enough to handle each weighted average over pairs separately, with the same moment and bound K for every weighting.
2. A projection with small rows. To keep increments consistent with labels on the points, the paper projects onto the space of such increments. A localization estimate for electrical flows, due to Gurel-Gurevich, Nachmias and Sachdeva, with a fixed-point reweighting of the pairs, keeps every row of the projection of total size at most 4 log(2n).
3. Heavy tails, both sides of 2. Below 2 the paper builds increments with symmetric p-stable marginals, clips their heavy tails and projects back. Above 2 it uses overlapping truncations, signed Poisson sampling and a moment inequality of Rosenthal type. Either way log K is at most a constant times (log n)^γ(p), which gives the dimension.
4. Exact embeddings need n². For p ≠ 2 the parallelogram defect ‖u+v‖^p + ‖u−v‖^p − 2‖u‖^p − 2‖v‖^p is zero exactly when u and v have disjoint supports. In a k × k grid, rows must stay disjoint from rows and columns from columns, while each row meets each column (their defect is 2^p − 4), so at least k² coordinates are needed.

The numbers in the video

• Johnson–Lindenstrauss: 2,000 Gaussian points in 1,000 dimensions, random Gaussian map to d dimensions; largest stretch over smallest about 2.03, 1.64 and 1.46 at d = 100, 200 and 400.
• Blind coordinate sampling at p = 3/2: for 40 spread-out points in 4,000 dimensions, 400 random coordinates give distortion about 1.25; for points with 5 nonzero coordinates each, it stays infinite up to 1,600 coordinates and above 10 at 3,200. That sparse set uses only 195 coordinates, so a map that adapts to it does fine.
• The parallelogram defect in a 3 × 3 grid: 0 for two rows, and 2^p − 4 for a row and a column, exactly 4 at p = 3 and −1.17 at p = 3/2.

Read the source

• Subpolynomial dimension reduction in Lp (PDF), 19 pages.
• The Lean scope note.
• The collection’s catalog, where this is result 094.

The paper

OpenAI groups related papers into one result; this one has a single paper.

• Subpolynomial dimension reduction in Lp

Transcript

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.