Subpolynomial dimension reduction in L_{p}

For every fixed 1\lt p\lt \infty and distortion D > 1, every n-point subset of real L_p embeds into \ell_p^d with distortion at most D and dimension d=n^{o(1)}, answering Naor's sublinear-dimension question for p ≠ 2. In contrast, exact embeddings require worst-case dimension \Theta(n^2) when p ≠ 2. (Lean)

Manuscript

Subpolynomial dimension reduction in Lp

September 23, 2026 · source · Lean formalization available · cite as \cite{OAI:Subpolynomial-dimension-reduction-in-Lp-September-23-2026}

For every fixed 1\lt p\lt \infty and D > 1, every n-point subset of a real L_p space embeds into \ell_p^d with distortion at most D and subpolynomial dimension d=n^{o(1)}. The target has the same exponent p, and the embedding need not be linear.

Result 094 · Convex and metric geometry. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.