Dimension reduction in Lp: approximate compression and exact rigidity

Source and verification

This article explains family 094 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.

🏷️ Finite subsets and target dimension

For $1<p<\infty$, the space ${\ell }_p$ consists of sequences with norm $\Vert x{\Vert }_p=({\sum }_j|x_j{|}^p{)}^{1/p}$. Given $n\ge 2$ and $D\ge 1$, let $d_p(n,D)$ be the least integer $d$ such that every $n$-point subset of ${\ell }_p$ admits a map into ${\ell }_p^d$ of distortion at most $D$.

Distortion permits a common rescaling:

$$\begin{array}{rl}s\Vert x-y{\Vert }_p& \le \Vert f(x)-f(y){\Vert }_p,\\ \Vert f(x)-f(y){\Vert }_p& \le Ds\Vert x-y{\Vert }_p\end{array}$$

for some $s>0$ and all distinct points. The map is defined only on the finite set. It need not be the restriction of a linear operator on the ambient space.

The question asks for a dimension bound uniform over all $n$-point configurations. It places no computational efficiency requirement on the resulting map.

🏷️ The claimed dimension bounds

Statement in the manuscript

Fix $1<p<\infty$, $p\ne 2$, and $D>1$. There is a constant $C_{p,D}$ such that

$$\begin{array}{c}{d}_p(n,D)\ge \frac{\log n}{\log (1+2D)},\\ d_p(n,D)\le \\ \exp \left(C_{p,D}(\log n{)}^{{\gamma }_p}\right),\end{array}$$

where

$${\gamma }_p=\{\begin{array}{ll}2-p,& 1<p<2,\\ 1-2/p,& 2<p<\infty .\end{array}$$

For exact embeddings and $n\ge 9$, the same manuscript claims

$${\lfloor \frac{n-1}{4}\rfloor }^2\le d_p(n,1)\le \left(\genfrac{}{}{0ex}{}{n}{2}\right).$$

(OpenAI, 2026)

For each fixed eligible $p$, the exponent ${\gamma }_p$ lies strictly between zero and one. Thus any fixed distortion allowance $D>1$ gives subpolynomial dimension:

$$\frac{\log d_p(n,D)}{\log n}⟶0.$$

Exact preservation instead gives $\log d_p(n,1)/\log n\to 2$. The constant $C_{p,D}$ may deteriorate as $D\downarrow 1$ or as $p$ approaches an endpoint. There is no contradiction between those two limits.

The Hilbert case $p=2$ belongs to the classical Johnson–Lindenstrauss regime and is excluded from this statement. Neither $p=1$ nor $p=\infty$ is covered.

🏷️ The packing lower bound

The vectors $e_1,\dots ,e_n$ in ${\ell }_p^n$ are equidistant. After rescaling a proposed image in ${\ell }_p^d$, suppose its minimum pairwise distance is one and maximum distance is at most $D$.

Open balls of radius $1/2$ about the image points are disjoint. All lie in the ball of radius $D+1/2$ about the first point. Lebesgue volume in any $d$-dimensional normed space scales as the $d$th power of radius, so

$$n(1/2{)}^d\le (D+1/2{)}^d.$$

Rearranging gives $n\le (1+2D{)}^d$, which proves the displayed logarithmic lower bound. This calculation does not use a linear embedding hypothesis.

🏷️ Pairwise moments and a common map

An embedding must preserve all pairwise distances simultaneously. Finding a favorable scalar function separately for every pair would not produce one set of coordinates.

The source instead proves inequalities against arbitrary nonnegative weights on pairs. These weighted inequalities are suitable for convex separation: if no common distribution of scalar maps realized the required distance moments, a separating functional would supply pair weights contradicting the inequalities.

Once a suitable distribution of scalar maps is available, independent samples become coordinates of an ${\ell }_p^d$ map. The pairwise moment estimates and sampling bounds control all pairs together. This is the transition from analytic inequalities to target dimension. (OpenAI, 2026)

Consistency is a serious issue. An arbitrary number assigned to every pair need not equal differences of vertex values. Around a cycle, genuine increments must sum to zero. The manuscript uses an electrical-flow projection to replace approximate increments by consistent ones. It is contractive in an $L_2$ sense and has an $L_{\infty }$ bound of order $\log n$.

🏷️ Two regimes of the construction

When $1<p<2$, the argument uses stable-law ingredients, clipping, and the consistency projection. Clipping controls rare large increments, while the projection restores a common vertex potential. The errors must be balanced without losing the near-isometric moment comparison required when $D$ is close to one.

For $p>2$, the source uses overlapping truncations and a signed Poisson construction. Overlap allows contributions near a truncation boundary to be shared rather than creating an abrupt moment error. The resulting moment estimate again has a constant that can be brought close enough to one for a prescribed fixed $D>1$.

The two balances lead to the exponents $2-p$ and $1-2/p$. Their role is in $\log d$, not as powers of $n$. For example, at $p=4$ the claimed upper bound is $\exp (C_D\sqrt{\log n})$, which grows more slowly than $n^{\epsilon }$ for every fixed $\epsilon >0$.

The exact-embedding statement uses a different rigidity problem. There is no sampling error budget at $D=1$, and the manuscript’s quadratic lower bound shows that the approximate construction cannot be passed to that endpoint with a uniform constant.

🏷️ Key steps and proof outlines

Exact discretization turns all distances into one finite moment vector

Index the unordered pairs by $E$, with $|E|=N=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. For representatives $x_i(t)$ in an $L_p$ space, define

$$q(t)=(|x_i(t)-x_j(t){|}^p{)}_{ij\in E}.$$

The target distance-power vector is $\int q(t)d\mu (t)$. Normalize by the sum of its coordinates, so these vectors lie in a finite-dimensional simplex. A convexity argument and Carathéodory’s theorem express the integral using at most $N$ scalar-coordinate patterns. Rescaling those scalar values by the corresponding weights gives an exact embedding into ${\ell }_p^N$.

This reduction allows the approximate argument to work with finite coordinates without changing the metric. It also illustrates why pair moments must come from one vector of vertex values: the coordinates of $q(t)$ are constrained by their common origin. Arbitrary independently prescribed pair numbers do not lie in this distance cone. (OpenAI, 2026)

Electrical projection restores consistent increments

Let $V$ be the subspace of normalized edge increments arising from vertex potentials. The source chooses pair weights and an orthogonal projection $P$ onto $V$ that is contractive in the corresponding weighted ${\ell }_2$ norm and has absolute row sums bounded by $H=O(\log n)$.

Electrical-flow localization controls the row sums after a fixed-point reweighting. The weighted orthogonal property pays for quadratic errors, while the row-sum bound gives $\Vert Pv{\Vert }_{\infty }\le H\Vert v{\Vert }_{\infty }$. Both are needed: clipping a consistent increment vector usually destroys cycle consistency, and projecting it back can enlarge individual coordinates. The two norm bounds quantify that enlargement in complementary ways.

Below two, a logarithmic main term dominates clipping errors

For $1<p<2$, construct a random consistent vector $Y$ whose normalized coordinates share a symmetric $p$-stable marginal, with tail comparable to $t^{-p}$. Clip at height $T$ and set $F=P[Y{]}_T$. Since $PY=Y$, tail integration gives

$$\mathbb{E}|Y_e-F_e|{\lesssim }_{p}H{T}^{1-p},\sum _e{\sigma }_e\mathbb{E}|F_e{|}^2{\lesssim }_p{T}^{2-p}.$$

Compare $p$th moments below a second level $a=T/H$. The function $\min (|t|,a{)}^p$ is $p{a}^{p-1}$-Lipschitz, so the first error is $O_p(H^{2-p})$. The remaining upper tail is bounded by $a^{p-2}|F_e{|}^2$, giving the same order in weighted average. Meanwhile the common capped moment satisfies

$$b=p{\int }_0^a{t}^{p-1}P(|Y_e|>t)dt{\gtrsim }_p\log a.$$

Choose $\log a$ sufficiently larger than $H^{2-p}$ to make the relative moment error as small as the desired distortion requires. This balance produces the exponent $2-p$ in the logarithm of the final dimension.

Above two, overlapping truncations increase signal relative to error

For $p>2$, stable marginals no longer provide the same mechanism. The source uses overlapping magnitude intervals $(2^k,2^{k+\ell }]$. An increment in the central range contributes to several intervals, creating a ramp of multiplicities instead of a single abrupt cutoff. The main moment grows with this overlap, while the projection error can be estimated using its smoother distribution across levels.

Signed Poisson sampling combines the truncated increments. A refined Rosenthal-type inequality has leading coefficient $1+ϵ$ on the principal $p$th-moment contribution, with the quadratic contribution separated. An unspecified fixed coefficient would not permit distortion arbitrarily close to one. Balancing overlap, projection, and Poisson errors yields the exponent $1-2/p$.

Convex separation and sampling produce one embedding

The analytic estimates are established against every nonnegative system of pair weights. If no common distribution of bounded scalar maps had the required pair moments, a separating hyperplane would give such weights contradicting those estimates. Thus a suitable common distribution exists. Independent samples become coordinates, scaled by the inverse $p$th root of the sample count. Concentration and a union bound over $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs give simultaneous distance control.

The boundedness parameter and the moment lower bound determine the sample count; inserting the two balances above gives the stated subpolynomial dimension. At exact distortion, the separate antipodal row-and-column construction uses equality in the scalar $p$-parallelogram defect to force disjoint supports. Counting those supports yields a quadratic lower bound. Sampling with a positive error allowance cannot be passed to this endpoint with uniform constants.

See Also

Doubling subsets of Hilbert space concerns one infinite space and a fixed target dimension, a different quantifier order. Graph embeddings in L1 imposes graph structure and changes the target geometry.

🏷️ Manuscripts and verification scope

• Subpolynomial dimension reduction in $L_p$ — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The scope describes the approximate dimension bounds and the exact-embedding bounds, with their stated parameter restrictions. 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 2026. Subpolynomial dimension reduction in Lₛ.