Dimension Reduction in Lp: How OpenAI’s Proof Escapes the Quadratic Trap

An exact copy of the distances among a set of points can need quadratically many coordinates, even when the points themselves number only in the dozens. Allow a fixed amount of distortion, however small, and OpenAI’s preprint proves that the worst-case dimension drops below every positive power of the point count. This is dimension reduction in Lp with the geometry kept intact up to a multiplicative factor. The map chooses new coordinates while keeping the same norm exponent. The proof works by matching the moments of random pairwise differences while keeping those differences consistent with a single set of point labels.

01. What Is Dimension Reduction in Lp, and Why Is It Difficult?

Take $n$ distinct points from a real $L_p$ space. In the function-space setting, the distance between two points is the $p$th root of the integral of their absolute difference raised to the $p$th power. The finite target $\ell_p^d$ uses the same rule with a sum over $d$ coordinates. The source can be infinite-dimensional. The embedding must preserve all $\binom{n}{2}$ pairwise distances within the same distortion allowance.

A single vector assignment must serve both short and long pairs. A small additive error can overwhelm the distance between two close points, so the guarantee controls relative error for every pair after one global rescaling. A separate question in metric geometry, covered in our Falconer distance explainer, asks what distances a set determines. Here the entire list of distances, with the pairs identified, is the input to preserve.

02. The Johnson–Lindenstrauss Lemma and the Problem Beyond Euclidean Geometry

For $p=2$, the Johnson–Lindenstrauss lemma gives $O_D(\log n)$ dimensions at any fixed distortion $D>1$. Euclidean distances come from an inner product, and random linear projections can concentrate the squared norm of each difference vector. Taking a union bound over pairs then gives a simultaneous guarantee.

Asking for a Johnson–Lindenstrauss lemma in Lp raises two choices. One concerns the target, which here must use the original exponent. The other concerns linearity. A linear map must respect relations among the source vectors. Nonlinear Lp embeddings can position the points independently of those relations, subject to the distances. For another kind of metric guarantee, see our coverage of edit distance approximation.

03. The Previous Limitation and What the Earlier Lp Bounds Left Open

Ball’s work established the pair-count upper bound for exact embeddings and showed that quadratic order is necessary when $1\le p<2$. Below two, Schechtman’s approximate finite-set estimates went from $O_D(n\log n)$ to $O_{p,D}(n)$. Linear subspace discretization addresses a different parameter, the dimension of a subspace whose entire norm structure must be preserved. The span of the translated data can have dimension $n-1$, so a bound in that parameter alone gives no subpolynomial guarantee in $n$.

Selected configurations already force dimension proportional to the number of points when the map must be linear and $p\ne2$. The new theorem answers the open question of whether free placement in same-exponent coordinates permits sublinear dimension at fixed distortion.

04. OpenAI’s Subpolynomial Dimension Reduction Theorem Explained

For Theorem 1.1 in the September 23, 2026 preprint, write $d_p(n,D)$ as the least dimension that works for every $n$-point subset of every real $L_p$ space. For a given set, the images $y_i$ of the source points $x_i$ must satisfy the following inequalities for every pair, with one scale $s>0$.

In this definition of Lp embedding distortion, the largest target-to-source distance ratio can be at most $D$ times the smallest. For fixed $1<p<\infty$, $p\ne2$, and $D>1$, the theorem gives

All unmarked logarithms are natural. The exponent $\gamma(p)$ is $2-p$ below two and $1-2/p$ above two. For $p=3/2$, subtracting $3/2$ from two gives $1/2$. For $p=4$, subtracting $2/4$ from one also gives $1/2$. Both upper bounds therefore have a square root of $\log n$ in the exponential. The constants can differ and may grow as distortion approaches one.

05. Why Exact Embeddings Face a Quadratic Obstruction

Each scalar coordinate contributes a vector of powered pairwise distances. Divide each nonzero contribution by the sum of its entries. These normalized vectors lie in an affine hyperplane of dimension at most $\binom{n}{2}-1$. The normalized total distance vector is a barycenter of this compact set, even when the original distances come from integration. Carathéodory’s theorem represents it with at most $\binom{n}{2}$ contributions. Rescaling their coordinate labels realizes the original distances exactly.

For the lower bound, take the positive and negative indicators of every row and column of a $k\times k$ grid, plus the origin. In any isometric image fixing the origin, strict convexity forces antipodal points to remain antipodal. This makes the norms of sums and differences recoverable from the distance list. For two real coordinate entries $a$ and $b$, the $p$-parallelogram defect is

For $p\ne2$, it vanishes exactly when $ab=0$ and otherwise has the sign of $p-2$. Across coordinates, nonzero defects cannot cancel. Distinct rows thus retain disjoint supports, as do distinct columns. Each row and column must still overlap, since their defect is $2^p-4$. Each target coordinate witnesses at most one row–column intersection, so $4k+1$ points require at least $k^2$ coordinates. In the $3\times3$ case, thirteen points force nine coordinates. For general $n\ge9$, take $k=\lfloor(n-1)/4\rfloor$ and pad the configuration with distinct points if needed. Any exact embedding of the padded set must still realize the original intersections. This is a dimension obstruction tied to exact distances, distinct from the covering-based notion in our Urysohn width explainer.

06. The First Proof Step and the Role of Normalized Gradients

View the points as vertices of a complete graph and orient each edge once. For an edge $e=ij$, let $\delta_e=\lVert x_i-x_j\rVert_p$. One output coordinate gives each vertex a scalar label $z_i$. Its normalized increment is $(z_i-z_j)/\delta_e$. The subspace $V$ consists of all edge vectors obtained in this way. Fixing one label at zero makes recovery of the remaining labels unique.

For example, on the real line take input positions zero, two, and five and candidate labels zero, one, and four. The normalized increments along edges $12$, $23$, and $13$ are $-1/2$, $-1$, and $-4/5$. Multiplying back by the input distances gives $-1$, $-3$, and $-4$, with the first two summing to the third. Changing only the last increment can break that consistency. Sampling vectors in $V$ gives coordinates that always fit together.

07. How Weighted Moments Control Every Pair

Lemma 3.1 asks for a random gradient $F$ whose largest absolute entry is at most $K$ almost surely. For every strictly positive probability weighting $\lambda$ of the edges, the proof can choose a distribution with weighted absolute moment error at most $\eta b$, where $b$ is the target $p$th moment and $\eta$ is a small tolerance. Both $b$ and $K$ must stay fixed across tests. The criterion is

where $E$ is the set of edges and $\mathbb{E}$ denotes expectation.

Mixing distributions gives a compact convex set of moment vectors. If it missed the box of vectors within $2\eta b$ of $b$ on every edge, a separating hyperplane would supply a failed weighted test. The proof uses the absolute values of the separating coefficients, with a uniform component to make every weight positive. One law thus meets all edge targets.

Independent draws now supply coordinates, with the recovered labels scaled by $d^{-1/p}$. The powered distance ratios are sample averages of values in $[0,K^p]$. A bounded-sum estimate and a union bound over the pairs give a sufficient dimension of order $\max\{1,K^{2p}/(\eta^2b^2)\}\log(2n)$. The resulting distortion is at most $((1+3\eta)/(1-3\eta))^{1/p}$.

08. Electrical-Flow Localization and the Logarithmic Projection Bound

Clipping edge values individually can break the consistency illustrated above. To restore it, the proof projects onto $V$ using a weighted least-squares norm. For each test $\lambda$, the paper chooses a probability weighting $\sigma$ with $\sigma_e\ge\lambda_e/2$. In the weighted quadratic norm, both the projection $P$ and its residual $I-P$ are contractions.

With conductances $\sigma_e/\delta_e^2$, the projection is equivalent by diagonal rescaling to an electrical-flow projection. The localization theorem of Gurel-Gurevich, Nachmias, and Sachdeva bounds the Euclidean operator norm of the entrywise absolute projection matrix. This controls a weighted quadratic average of the absolute row sums of $P$. A continuous reweighting allocates more mass to large rows. Brouwer’s fixed-point theorem supplies weights for which every row sum is at most $H=4\log(2n)$. The quadratic norm controls average error, while the row bound limits the largest entry after projection. The localization argument uses the graph heat kernel, a continuous-time random walk. Random walks serve a different purpose in the switch-chain mixing proof, where the question is how quickly a sampler approaches equilibrium.

09. Homogeneous Increments and Signed Poisson Sampling

The proof can start with finitely many input coordinates by exact discretization. It divides each coordinate difference by the original pairwise distance and multiplies the resulting gradient by a positive scale $r$. On each source coordinate the scale carries intensity $pr^{-p-1}\,dr$. Because the powered normalized differences sum to one for each edge, the resulting measure $\nu$ satisfies $\nu(|v_e|>a)=a^{-p}$ for every edge and every $a>0$. This is an intensity measure. Its total mass can be infinite.

On a finite-mass region, take a Poisson number of independent jumps with mean equal to that mass and attach independent random signs. Their sum has mean zero and, for bounded jumps, variance equal to the integrated squared jump size. The magnitude density $pu^{-p-1}$ makes that integral finite near zero below two and finite near infinity above two. This common law is marginal. Edges can be dependent because a single jump labels all vertices.

10. The Proof for 1 < p < 2 Using Stable Distributions and Clipping

Below two, the sum of small jumps converges in quadratic mean across dyadic bands. Adding the finite Poisson sum of large jumps gives a gradient $Y$ with common symmetric $p$-stable marginals. Their tails have order $a^{-p}$ for $a\ge1$, so the full $p$th moment diverges logarithmically. Capping the magnitude at $a$ gives a common finite moment $b$ that grows on the order of $\log a$.

The paper clips each entry of $Y$ at magnitude $T$, projects back to $V$, and compares the projected moments at the smaller level $a=T/H$. The row bound controls the expected clipping error after projection. Weighted quadratic contraction controls the part of the projected $p$th moments above the cap. At this choice of $a$, the combined weighted error is of order at most $H^{2-p}$. Taking $\log T$ to be a sufficiently large multiple of $H^{2-p}$ makes the error small relative to $b$. The resulting magnitude bound $K=HT$ has $\log K=O_{p,D}((\log n)^{2-p})$.

11. The Proof for p > 2 Using Overlapping Truncations

Above two, the construction sums $\ell$ overlapping dyadic bands. Band $k$ keeps magnitudes in $(2^k,2^{k+\ell}]$ for $0\le k<\ell$. The number of bands covering a magnitude rises from one to $\ell$ and then falls back to one. Each dyadic bin contributes $p\log 2$ times its multiplicity to the power $p$. The common integrated $p$th-power magnitude therefore has order $\ell^{p+1}$.

Projection repairs the truncated increments. The paper estimates the repair at each cutoff in two ways. The retained low-magnitude part bounds the maximum size of the repair. Since the original gradient already lies in $V$, the repair can also be written using only the discarded high-magnitude part, which has finite quadratic energy. Splitting at the appropriate cutoff gives a tail bound for the total repair. Its error, measured as a weighted integrated $p$th power, is at most of order $H^{p-2}(\ell+1)$. The ratio of the error norm to the input norm is thus at most a constant times $H^{1-2/p}/\ell$. Choosing $\ell$ to be a sufficiently large multiple of $H^{1-2/p}$ makes the relative error small.

Signed Poisson sampling then turns the projected jumps into random gradients. The paper’s nearly additive moment estimate bounds the sampled $p$th moment by the integrated $p$th power with leading coefficient as close to one as needed, plus a variance term. That leading coefficient matters when the allowed distortion is close to one. The proof discards an entire draw if any entry is too large, preserving consistency. This gives $\log K=O_{p,D}((\log n)^{1-2/p})$.

12. Completing OpenAI’s Proof and Identifying the Open Questions

The moment criterion turns either bound on $\log K$ into a bound of the same order on $\log d$. Since $0<\gamma(p)<1$, dividing by $\log n$ gives a quantity tending to zero. That is the meaning of $n^{o(1)}$ here. Exact discretization covers the finitely many small sizes outside the asymptotic estimates.

For the packing lower bound, start with the equilateral set of coordinate unit vectors. Translate and scale the images so that they are one-separated and lie in a ball of radius $D$. The open half-unit balls around them are disjoint and lie inside a ball of radius $D+1/2$. Volume scales as the $d$th power of radius, so $n\le(1+2D)^d$, giving the theorem’s logarithmic lower bound.

At $p=1$, Brinkman and Charikar give obstructions even for nonlinear maps. Above two, the stronger lower bound of Naor and Ren rules out a universal logarithmic guarantee at fixed distortion. Along arbitrarily large cardinalities it gives at least order $(\log n/(\log\log n)^2)^{p/2}$ coordinates. The preprint leaves the optimal growth rate and efficient construction open, so it gives no runtime guarantee for applications such as metric k-median.

OpenAI’s release announcement describes the broader collection. The Lean scope note for family 094 documents the approximate and exact bounds, attainment of the least dimension, and both asymptotic limits. The Lean theorem file is the formal counterpart to those claims. For another formalization in the release, see our weak and strong normalization explainer. Binary Verse AI’s coverage of OpenAI’s mathematical proofs puts this result in the context of the wider release.

Dimension reduction in Lp now has a sharp qualitative dividing line. At exact distortion, support intersections can force quadratic dimension. With any fixed tolerance above one, consistent random coordinates can preserve every pair in subpolynomial dimension. Follow Binary Verse AI for more paper-led explainers on the boundary between geometric constraints and approximation.