View source for Dimension reduction in Lp spaces

'''Dimension reduction in L<sub>p</sub> spaces''' asks how many coordinates are needed to place every ''n''-point subset of an ''L''<sub>''p''</sub> space in ℓ<sub>''p''</sub><sup>''d''</sup>, with the same exponent ''p'', at distortion at most ''D''. For ''p'' = 2 the Johnson–Lindenstrauss lemma gives ''O''<sub>''D''</sub>(log ''n'') coordinates. A manuscript in OpenAI's public mathematics collection ([https://github.com/openai/math github.com/openai/math]), dated 23 September 2026, claims that for every fixed 1 < ''p'' < ∞ and ''D'' > 1, ''n''<sup>''o''(1)</sup> coordinates suffice; the collection presents this as answering Naor's question whether sublinear dimension is possible for ''p'' ≠ 2. This page summarizes the published claim and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper or a formal proof is not presented here as independent verification.

== Background ==
* As recounted in the introduction of the manuscript:
** Johnson and Lindenstrauss asked which analogues of their lemma hold in other Banach spaces. The manuscript studies the coordinate-target version: points may be moved freely, but their images must lie in ℓ<sub>''p''</sub><sup>''d''</sup>.
** Ball proved that exact embeddings need at most ''n''<sup>2</sup> coordinates and that this order is sharp for 1 ≤ ''p'' < 2. Below 2, Schechtman's finite-set bounds improved from ''O''<sub>''D''</sub>(''n'' log ''n'') to ''O''<sub>''p'',''D''</sub>(''n'') coordinates; the subspace theorems of Bourgain–Lindenstrauss–Milman and Talagrand give linear maps whose dimension depends on the dimension of a subspace, not on the number of points.
** Linear maps with fixed distortion can need dimension proportional to ''n'' when ''p'' ≠ 2. At ''p'' = 1 the lower bound of Brinkman and Charikar, also proved by Lee and Naor, applies to nonlinear maps as well. For ''p'' > 2, a recent lower bound of Naor and Ren rules out ''O''<sub>''p'',''D''</sub>(log ''n'') coordinates.

== The original result ==
* '''Claim.''' Theorem 1.1 of ''Subpolynomial dimension reduction in Lp'' states that for fixed 1 < ''p'' < ∞, ''p'' ≠ 2, and every ''D'' > 1 there is a constant ''C''<sub>''p'',''D''</sub> such that the least dimension ''d''<sub>''p''</sub>(''n'', ''D'') satisfies log ''n''/log(1 + 2''D'') ≤ ''d''<sub>''p''</sub>(''n'', ''D'') ≤ e<sup>''C''<sub>''p'',''D''</sub> (log ''n'')<sup>γ(''p'')</sup></sup>, with γ(''p'') = 2 − ''p'' for ''p'' < 2 and γ(''p'') = 1 − 2/''p'' for ''p'' > 2. For exact embeddings it states ⌊(''n'' − 1)/4⌋<sup>2</sup> ≤ ''d''<sub>''p''</sub>(''n'', 1) ≤ ''n''(''n'' − 1)/2 for ''n'' ≥ 9, so that log ''d''<sub>''p''</sub>(''n'', ''D'')/log ''n'' tends to 0 for ''D'' > 1 and to 2 for ''D'' = 1.
* '''Stated limits.''' The constants depend on ''p'' and ''D'', with no uniformity near the endpoints or as ''D'' approaches 1. The theorem is existential, asserts no efficient algorithm, and does not require the embedding to be linear; neither the upper exponent nor the logarithmic lower bound is asserted to be optimal.
* ''Method, as described:'' a convex-separation argument produces one bounded distribution of scalar images with nearly equal normalized ''p''-th moments for all pairs, and independent sampling in the manner of Maurey's empirical method gives the coordinates. The geometric input is a projection with logarithmic ''L''<sub>∞</sub> norm, obtained by reweighting the electrical-flow localization estimate of Gurel-Gurevich, Nachmias and Sachdeva. Clipped ''p''-stable marginals handle ''p'' < 2, and overlapping magnitude truncations with signed Poisson sampling handle ''p'' > 2.
* '''Source''' (openai/math repository, commit <code>7ef5c0c</code>): [https://github.com/openai/math/tree/7ef5c0cc5ca4b0e072b7a050fca09ab24bc6fa3a/preprints/Subpolynomial-dimension-reduction-in-Lp-September-23-2026 Subpolynomial dimension reduction in Lp], dated 23 September 2026, 19 pages.
* '''Formalization, as described by the repository.''' The scope note [https://github.com/openai/math/blob/7ef5c0cc5ca4b0e072b7a050fca09ab24bc6fa3a/lean/docs/094.md lean/docs/094.md] states that the formalization proves both bounds for fixed ''D'' > 1, the quadratic bounds at distortion 1 for ''n'' ≥ 9, attainment of the least dimension, and the limits of log ''d''<sub>''p''</sub>(''n'', ''D'')/log ''n'', for ''p'' > 1 with ''p'' ≠ 2.

== Public follow-up work ==
{| class="wikitable"
! Date !! Work !! Relation !! Public claim !! Public status (checked 29 October 2026)
|-
| 2026-10-06 || [https://lowrank.github.io/latent-seminar/OpenAI-Math/094-lp-dimension-reduction ''Dimension reduction in Lp: approximate compression and exact rigidity''], an article of the Latent Seminar blog at lowrank.github.io || Reading (exposition) || Explains finite subsets and the target dimension, the claimed bounds, the packing lower bound, pairwise moments and a common map, and the two regimes of the construction, with outlines of the key steps. || Blog article; it states that its review covers statements, introductions and selected proof mechanisms and is not an independent verification of the complete proofs.
|-
| 2026-10-09 || [https://kokunoyumeto.github.io/open-math-courses-public/courses/dimension-reduction-in-lp/ ''Dimension reduction in L_p''], a course on Open Mathematics Courses ([https://github.com/kokunoyumeto/open-math-courses-public kokunoyumeto/open-math-courses-public]) || Reading (exposition) || Five lessons on the manuscript's theorem: finite subsets of ''L''<sub>''p''</sub>, weighted moments and sampling, electrical flows and a weighted projection, signed Poisson sums for exponents below two, and truncation ramps for exponents above two. || The lessons state that they were written by Claude Opus 5.5 (Anthropic) in October 2026 and self-checked by the writing AI; the course lists its status as author self-checked.
|-
| 2026-10-15 || ''AI Proved What?'', episode 094 [https://aiprovedwhat.com/episodes/094-subpolynomial-dimension-reduction-lp/ Squeezed into less?], remade version of 26 October 2026 || Reading (exposition) || Video explainer of the claim that for every fixed ''p'' between 1 and ∞ other than 2 and every distortion ''D'' above 1, every ''n''-point subset of an ''L''<sub>''p''</sub> space embeds into ℓ<sub>''p''</sub><sup>''d''</sup> with distortion at most ''D'' and a number of coordinates smaller than any fixed power of ''n'', while exact embeddings need a number of order ''n''<sup>2</sup>. The episode states that the constant depends on ''p'' and ''D'', that the result is existential, gives no efficient algorithm and uses maps that need not be linear, that neither the exponent nor the logarithmic lower bound is claimed optimal, and that ''p'' = 1 is not covered. || Web page and video; the site states that its scripts and animations are produced with AI assistance and that the narration is an AI-generated voice. Status record last checked 27 October 2026: posted as a preprint: OpenAI, dated September 23, 2026, released October 6; under expert review: not yet; peer reviewed: not yet; checked in Lean: OpenAI published a Lean proof of the dimension bounds, the site has not run the check. The page also states that the Lean formalization of the dimension bounds has 45 files and 7,918 lines, including the electrical-flow localization from the paper's appendix, that it found no unproved steps, and that it has seen no expert review.
|}

== Notes ==
* The background summarizes the manuscript's own account of earlier work.
* The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.

[[Category:OpenAI results]]