Subpolynomial dimension reduction in L_p

Points in Lp space can be squeezed into far fewer coordinates if distances may stretch slightly.

1 paper September 23, 2026 Explained by AI

Some ways of measuring distance use a power p other than 2. For such rulers, copying n points exactly can need about n squared coordinates. This paper proves (Lean proof listed) that a small allowed stretch changes the picture. Then the count grows slower than any fixed power of n. The map that does this need not be a straight-line one.

First step

1984

Johnson and Lindenstrauss, who asked about other spaces

Significance

Major

If it holds, it moves the known counts for p other than 2 from polynomial to subpolynomial.

Trust

Formal proof listed

Field

Convex and metric geometry

1 paper

The explanation

Take two points on a grid, (0, 0) and (3, 4). Their straight-line distance is 5. There are other fair ways to measure the gap. Add the two gaps, 3 plus 4, and you get 7. Or cube the gaps, add them to get 91, and take the cube root. That gives about 4.50. Each power p gives its own ruler. A space of long lists of numbers, measured with power p, is called an L_p space. The straight-line ruler is the case p = 2.

Now take a million points, each a very long list of numbers. Can each point be described by far fewer numbers, with every distance kept? Each number in the short list is called a coordinate. The usual price is a little stretching. Allowing distortion D means this. After one common rescaling, each new distance lies between the old one and D times it. Distortion 1 means an exact copy.

For the straight-line ruler, the answer has been known since 1984. The Johnson–Lindenstrauss lemma fits any n points into a number of coordinates that grows like log n. That holds for any fixed distortion above 1. Johnson and Lindenstrauss also asked what happens for other rulers.

Exact copies are costly. Keith Ball showed in 1990 that n points always fit exactly into n(n−1)/2 coordinates. For a million points that is 499,999,500,000. The paper shows this cannot be cut much when p is not 2. It builds point sets from the rows and columns of a square gridSource 1. Take n of at least 9. An exact copy then needs at least the square of the whole-number part of (n−1)/4Source 2. For a million points, that whole-number part is 249,999, so the minimum is 62,499,500,001 coordinates.

Allowing a little stretch had helped only partly. For p below 2, Gideon Schechtman cut the count from about n log n to about n coordinates. Those counts still grow in step with the number of points. Lee, Mendel and Naor showed that straight-line maps can need that many when p is not 2. At p = 1, Brinkman and Charikar found an obstacle that holds even for bent maps. For p above 2, Naor and Ren recently ruled out counts that grow like log n.

This paper proves a much smaller count for every p between 1 and infinity except 2Source 3. Fix any distortion above 1. Then n points fit into n^o(1) coordinatesSource 4. That notation means the count eventually drops below every fixed power of n, even n^0.01. More exactly, the logarithm of the count grows like a power of log n below 1. For p = 3 that power is one third. For a million points, log n is about 13.8, and its cube root is about 2.40. So exact copies need about n² coordinates, but any stretch above 1 needs far fewer.

The single obstacle is that the map must bendSource 5. Straight-line maps can need a count in proportion to n, so they cannot workSource 6. The paper instead builds one random rule that gives each point a single bounded numberSource 7. Raise each pair's gap to the power p and average it. For every pair, the rule makes this nearly match the original, up to one common factor. Many independent copies of that rule then serve as the coordinates. The hard part is making one rule serve every pair at once.

Some limits come with the result. A constant in the bound depends on p and the distortion, and its size is not givenSource 8. So the theorem gives no actual count for a million points. It promises that an embedding exists, not a fast way to compute itSource 9. A simple packing argument shows some sets need at least log n divided by log(1 + 2D) coordinatesSource 10. For a million points at distortion 2, that ratio is about 8.6, so at least 9 coordinates are needed. The paper does not claim either bound is the best possibleSource 11.

How sure is this? A computer proof checker called Lean has checked a formal version of the main theorem. It covers the upper and lower bounds with stretch, the exact-copy bounds and the two limits. The statement is matched against a fixed reference statement by a tool called Comparator. No specialist review of the paper has been published.

What it doesn't show. This does not give a fast way to build the embedding, or an explicit count for given n.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

The main theorem has a Lean proof listed with a Comparator statement. The constants are not explicit, the bounds are not claimed optimal, and no specialist review is published.

Words used

L_p space: A space of lists or functions where distance is measured by adding gaps raised to the power p, then taking the p-th root.
Coordinate: One number in the list that describes a point; the dimension is how many there are.
Distortion: The largest factor by which a copy stretches distances, after one common rescaling.
Embedding: A way to place points in a new space while keeping distances close to the originals.
Subpolynomial: Growing more slowly than every fixed power of n, such as n^0.01.
Johnson–Lindenstrauss lemma: The 1984 result that n points with straight-line distances fit into about log n coordinates with small stretch.
Comparator: A tool that checks a Lean proof proves exactly a fixed reference statement.

The original paper

Subpolynomial dimension reduction in Lp (PDF, opens in a new tab)
September 23, 2026 Formal proof listed

Lean notes

All quoted lines (11)

Lemma … recalls the distance-cone and Carath\'eodory argument for that upper bound. The lower bound in (…) uses an antipodal row-and-column configuration.
Subpolynomial dimension reduction in Lp Back to text
For $n\ge9$ , take $k=\lfloor(n-1)/4\rfloor$ and add distinct points if necessary to obtain an $n$ -point set. Any exact embedding of that set restricts to one of $\mathcal X_k$ , proving the lower bound in (…).
Subpolynomial dimension reduction in Lp Back to text
Fix $1<p<\infty$ , $p\ne2$ , and put $\gamma(p)= \begin{cases} 2-p,&1<p<2,\\ 1-2/p,&2<p<\infty. \end{cases}$ For every $D>1$ there is a constant $C_{p,D}<\infty$ such that, for every integer $n\ge2$ , $\frac{\log n}{\log(1+2D)} \le d_p(n,D) \le \exp\!\bigl(C_{p,D}(\log n)^{\gamma(p)}\bigr).$
Subpolynomial dimension reduction in Lp Back to text
Consequently, $\lim_{n\to\infty}\frac{\log d_p(n,D)}{\log n} =\begin{cases}0,&D>1,\\2,&D=1.\end{cases}$
Subpolynomial dimension reduction in Lp Back to text
The absence of a linearity requirement is essential: fixed-distortion linear maps on selected $L_p$ configurations can require dimension proportional to their cardinality when $p\ne2$ .
Subpolynomial dimension reduction in Lp Back to text
The absence of a linearity requirement is essential: fixed-distortion linear maps on selected $L_p$ configurations can require dimension proportional to their cardinality when $p\ne2$ .
Subpolynomial dimension reduction in Lp Back to text
Convex separation produces one distribution working for all pairs; independent sampling then supplies the coordinates of a finite embedding.
Subpolynomial dimension reduction in Lp Back to text
The constants in the upper bound depend on the fixed parameters $p,D$ ; no uniformity as $p$ approaches an endpoint or $D$ approaches $1$ is asserted.
Subpolynomial dimension reduction in Lp Back to text
The theorem is existential and does not assert an efficient embedding algorithm.
Subpolynomial dimension reduction in Lp Back to text
Their open balls of radius $1/2$ are disjoint and lie in the ball of radius $D+1/2$ about that point. Comparing $d$ -dimensional Lebesgue volumes gives $n(1/2)^d\le(D+1/2)^d, \qquad\text{hence}\qquad n\le(1+2D)^d.$
Subpolynomial dimension reduction in Lp Back to text
This is compatible with (…); neither its upper exponent nor its elementary logarithmic lower bound is asserted to be optimal.
Subpolynomial dimension reduction in Lp Back to text

Subpolynomial dimension reduction in Lp