Browse › Convex and metric geometry › 094 Subpolynomial dimension reduction in Lp
Subpolynomial dimension reduction in Lp
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
For every fixed $1\lt p\lt \infty$ and D > 1, every n-point subset of a real Lp 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.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI, Subpolynomial dimension reduction in Lp: Lean formalization scope (OpenAI Math Release, lean/docs/094.md, 6 October 2026). The scope note describes formalization of both bounds of Theorem 1.1 for fixed distortion D>1, the quadratic exact-distortion bounds for D=1 (n≥9), attainment of the least dimension, and the limit of log d_p(n,D)/log n, for p > 1 with p ≠ 2. [family-level]
- OpenAI, OAI/Analysis/LpDimension/Main.lean (github.com/openai/math, commit adc7f12). The Lean file contains the theorem
SubpolynomialLp.source_main, stated for real p>1 with p≠2, whose three parts are the D>1 bounds, the D=1 quadratic bounds, and the exponent limit.
Possibly relevant literature (found by the agent, not checked)
- W. B. Johnson and A. Naor, The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite (arXiv:0807.1919, 2008). Studies which normed spaces satisfy a linear JL-type lemma, bearing on the introduction's discussion of Johnson–Lindenstrauss Problem 3 (JL analogues in other Banach spaces).
- O. Regev, Entropy-based Bounds on Dimension Reduction in L₁ (arXiv:1108.1283, 2011). Gives another proof of the polynomial lower bounds at p=1, including the near-linear bound of Andoni–Charikar–Neiman–Nguyen for distortion 1+ε; this concerns the endpoint obstruction the paper cites via Brinkman–Charikar and Lee–Naor.
- Y. Bartal and L.-A. Gottlieb, Dimension reduction techniques for ℓp, 1 ≤ p ≤ 2, with applications (arXiv:1408.1789, 2014). Builds nonlinear dimension-reduction embeddings for finite subsets of ℓp with 1≤p≤2, with bounds in terms of intrinsic dimension; compare the paper's survey of earlier finite-set bounds below p=2 (Schechtman).
Digests and expositions
- Open Mathematics Courses / Claude Opus 5.5, Dimension reduction in L_p (Open Mathematics Courses, undated). Five lessons present the paper's dimension bounds through weighted moments, electrical-flow projections and signed Poisson sums, with proofs and exercises; the source states that independent review is incomplete. [AI-generated per source]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 094
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Subpolynomial-dimension-reduction-in-Lp-September-23-2026,
author = {{OpenAI}},
title = {{Subpolynomial dimension reduction in $L_p$}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Subpolynomial-dimension-reduction-in-Lp-September-23-2026/paper.pdf}{OAI:Subpolynomial-dimension-reduction-in-Lp-September-23-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/094.md. The Lean statements have not been checked by people against the paper's claims.
Family 094: Subpolynomial dimension reduction in Lp
For every fixed $1\lt p\lt \infty$ and distortion D > 1, every n-point subset of real Lp 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.
This is the only paper in this family.