Subpolynomial dimension reduction in Lp

1 · The essentials

The result concerns how to describe a finite collection of points using fewer coordinates while nearly preserving the distances between them. The points must belong to one of the spaces called $L_{p}$ , with a fixed number $p$ strictly between 1 and infinity. You may choose any fixed allowance for changing distances, however close that allowance is to exact preservation. Every collection of $n$ points can then be represented using a number of coordinates that grows more slowly than any fixed positive power of $n$ . The new coordinates measure distance using the same choice of $p$ as the original space. Requiring distances to be preserved exactly changes the situation: when $p \neq = 2$ , the worst-case number of coordinates grows on the order of $n^{2}$ . The main dimension-reduction result has a Lean formalization.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine replacing a collection of detailed records with much shorter records while keeping the measured differences between every pair nearly unchanged. The result says that a fixed allowance for error can make those records dramatically shorter, but only for the particular kinds of distance described in the statement.

Why it matters

The repository describes this as answering Naor’s sublinear-dimension question for $p \neq = 2$ . The stated bound is stronger than merely growing more slowly than $n$ : it grows more slowly than every fixed positive power of $n$ . The contrast with exact preservation highlights how much the permission to change distances slightly can matter.

2 · Going further

The precise statement is that, for every fixed $1 1$ , every $n$ -point subset of a real $L_{p}$ space admits an embedding into $ℓ_{p}^{d}$ with distortion at most $D$ and $d = n^{o (1)}$ . Distortion at most $D$ means that, after allowing a common change of scale, pairwise distances change by factors bounded between $1$ and $D$ . The notation $n^{o (1)}$ means that the dimension grows more slowly than $n^{ε}$ for every fixed $ε > 0$ , with $p$ and $D$ held fixed.

Two structural features are explicit in the abstract: the target uses the same exponent $p$ , and the embedding need not be linear. The repository identifies the result as answering Naor’s sublinear-dimension question for $p \neq = 2$ and states, in contrast, that exact embeddings require worst-case dimension $Θ (n^{2})$ when $p \neq = 2$ . The supplied abstract does not describe the argument or its main construction, so no proof mechanism can be extracted from it. Only the main manuscript is supplied; no companion manuscripts or relationships between them are specified.

Useful notions

Pairwise distances
Coordinates and dimension
The spaces $L_{p}$ and $ℓ_{p}^{d}$
Approximate distance preservation
Asymptotic growth notation

What was known before / what is new

Before

The repository identifies Naor’s sublinear-dimension question for $p \neq = 2$ as the question being answered. It also states the contrasting worst-case requirement of $Θ (n^{2})$ dimensions for exact embeddings when $p \neq = 2$ . The supplied text does not give a chronology or further prior bounds.

New

The main result gives dimension $d = n^{o (1)}$ for every fixed $1 1$ . It applies to every $n$ -point subset of a real $L_{p}$ space and keeps the same exponent in the target $ℓ_{p}^{d}$ . The embedding is not required to be linear, and the main result has a Lean formalization.

Limits and assumptions

The statement requires real $L_{p}$ spaces, fixed $1 1$ ; it does not cover the endpoints or exact preservation. It gives no bound here for parameters $p$ or $D$ that vary with $n$ , and the abstract supplies no explicit dimension formula beyond $n^{o (1)}$ . The main result has a Lean formalization, but the supplied material does not specify its detailed scope or establish that the separate exact-embedding comparison is formalized. No remaining open questions are listed in the supplied text.

Mini glossary

$L_{p}$ space: A space of functions whose size is measured by integrating the $p$ th power of their absolute value and taking the $p$ th root.
$ℓ_{p}^{d}$: The space of $d$ real coordinates with distance measured by the $p$ th root of the sum of the $p$ th powers of coordinate differences.
Embedding: A map representing the original points as distinct points in a target space.
Distortion: A measure of the multiplicative change in pairwise distances after allowing a common rescaling.
Subpolynomial dimension: A dimension bound written $n^{o (1)}$ , growing more slowly than every fixed positive power of $n$ .
$Θ (n^{2})$: Growth bounded above and below by positive constant multiples of $n^{2}$ for sufficiently large $n$ .

Keywords : Dimension reduction · $L_p$ geometry · Distortion

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

For every fixed $1 1, every n-point subset of real L_p embeds into $ℓ_{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 $Θ (n^{2})$ when p ≠ 2.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/094.md

Manuscripts in this family

★

Subpolynomial dimension reduction in Lp

23/09/2026

Verified by Lean

For every fixed $1 1, every n-point subset of a real L_p space embeds into $ℓ_{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.

PDF GitHub folder Lean formalization