Naor's sublinear-dimension question for finite subsets of Lp, 1 < p < infinity, p not 2

The Johnson-Lindenstrauss lemma embeds every $n$ -point subset of Hilbert space into $O(\log n)$ dimensions with distortion $1+\varepsilon$ , and Johnson and Lindenstrauss (1984, Problem 3) asked what analogues hold in other Banach spaces. In $L_1$ polynomial dimension is necessary (Brinkman-Charikar), and Ball's exact bound for $L_p$ is $\binom n2$ coordinates. Naor (ICM 2018) remarked that for no fixed $p\in[1,\infty)\setminus\{2\}$ was it even known whether every $n$ -point subset of $\ell_p$ embeds with bounded distortion into a normed space of dimension $o(n)$ . For fixed $p\ne2$ and distortion $D$ , can every $n$ -point subset of $L_p$ be embedded with distortion $D$ in dimension $o(n)$ ?

Result: Proved(see note)
Status: Candidate (review pending)
AI contribution: AI-discovered
Method: Argument
Field: Metric embeddings, Banach space geometry
Posed by: Assaf Naor (after William B. Johnson and Joram Lindenstrauss)
Year posed: 2018
Years open: 8y
Solved: 2026-09-23
Model: Unreleased internal OpenAI model
Vendor: OpenAI
Collaborators: —
Verification: Lean-checked, statement unaudited
Publication: Announced
Collection: OpenAI math release (October 2026), version adc7f12
Significance: 35 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Theorem 1.1: for fixed $1<p<\infty$ , $p\ne2$ , and $D>1$ , every $n$ -point subset of any $L_p$ embeds with distortion $D$ into $\ell_p^d$ (same exponent, coordinate target, nonlinear map) with $d\le\exp(C_{p,D}(\log n)^{\gamma(p)})=n^{o(1)}$ , where $\gamma(p)=2-p$ for $p<2$ and $1-2/p$ for $p>2$ ; exact embeddings need dimension of order $n^2$ . This answers the $o(n)$ question for every $p\in(1,\infty)\setminus\{2\}$ . Not shown: $p=1$ ; Naor's Question 13 itself ( $O(\log n)$ dimension in some normed space), which Naor-Ren's 2026 lower bound already excludes for $\ell_p^d$ targets when $p>2$ ; optimal exponents; an efficient algorithm.

What the AI did

The release README says the results were produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscripts are authored 'OpenAI' and name no human author. The single manuscript (September 23, 2026) is the whole family.

Verification

No independent mathematician has checked this yet. Checked here: the abstract, introduction and Theorem 1.1 were read against Naor's remark (read in the ICM text) and Johnson-Lindenstrauss Problem 3. The proof (weighted-moment distributions by convex separation, electrical-flow localization, stable and signed Poisson increments, Maurey sampling) was not refereed. lean/formalization.yaml lists comparator SubpolynomialLp, declaration OAI.SubpolynomialLp.source_main (file OAI/Analysis/LpDimension/Main.lean). Its statement was read here: with $d_p(n,D)$ the least $d$ such that every injective $n$ -point family in any $L_p(\mu)$ embeds into $\ell_p^d$ with distortion $D$ , for $1<p$ , $p\ne2$ and each $D>1$ there is $C$ with $\log n/\log(1+2D)\le d_p(n,D)\le\exp(C(\log n)^{\gamma(p)})$ ; at $D=1$ , $\lfloor(n-1)/4\rfloor^2\le d_p(n,1)\le\binom n2$ for $n\ge9$ ; and the log-ratio tends to 0 or 2. That states the headline. Not rebuilt here. Permitted axioms: propext, Quot.sound, Classical.choice.

Naor's sublinear-dimension question for finite subsets of Lp, 1 < p < infinity, p not 2

What was actually shown

What the AI did

Verification

Sources

Discussion