A Fixed Distortion Gap Cuts Lp Embedding Dimension Below Every Polynomial

For fixed p strictly between 1 and infinity, with p not equal to 2, and any fixed distortion D greater than 1, the paper claims that every set of n points in a real Lp space can be represented in finite-dimensional ℓp using a subpolynomial number of coordinates. The exponent p stays the same. The guarantee concerns distances among a finite set, not a map of the entire space.

One common rescaling is allowed: after rescaling, every pairwise distance must be at least its original value and at most D times that value. The map need not be linear. The result is not uniform as D approaches 1.

The stated bound is dₚ(n,D) ≤ exp(Cₚ,ᴅ (log n)^γ), where γ = 2 − p for 1 < p < 2, and γ = 1 − 2/p for p > 2. Both exponents lie strictly between 0 and 1, so the bound is eventually smaller than n^ε for every fixed ε > 0. The constant may depend on p and D, but not on n, the underlying measure, or the point set. At p = 2, the paper notes a classical logarithmic bound.^†

The proof first establishes an exact, potentially expensive representation: any finite set of n points in real Lp can be represented isometrically in a finite coordinate space. To seek a smaller approximate representation, it builds coordinates from scalar labelings of the points.

For labels zᵢ, define the normalized increment for a pair i,j as Fᵢⱼ = (zⱼ − zᵢ)/δᵢⱼ, where δᵢⱼ is the original distance between the points. The magnitude |Fᵢⱼ| is that coordinate’s contribution to the pair’s distance ratio. But increments cannot be chosen independently: around a triangle, the signed differences along two edges must add to the difference along the third.

Choose d such labelings as coordinates and scale each coordinate vector by d to the power −1/p. The p-th power of the new distance, divided by the original distance to the p-th power, is the average of |Fᵢⱼ|ᵖ across the coordinates. The goal is to find random, consistent labelings whose increments are bounded in magnitude and whose expected p-th powers are nearly the same for every pair. Independent samples can turn those expectations into coordinate averages.

If every pair’s average lies between (1 − 3η)b and (1 + 3η)b, taking p-th roots gives distortion at most ((1 + 3η)/(1 − 3η)) to the power 1/p. Choosing η small enough meets the desired D.

The challenge is satisfying all pairs at once. For any positive weighting of the pairs, a labeling distribution may depend on those weights, but the target moment b and increment bound K must be common across weightings. A convex-separation argument yields one distribution that works for every pair. Concentration and a union bound then supply finitely many coordinates; the displayed dimension bound is proportional to max(1, K²ᵖ/(η²b²)) log(2n).

The difficult construction is to make increments both bounded and consistent. Simply cutting off large increments can break the cycle constraints: values around a triangle that previously added correctly may no longer do so. The paper repairs this by projecting back onto the space of valid increments.

After reweighting the pairs, the projection contracts a weighted square norm. Its maximum-norm amplification is at most H = 4 log(2n). The stated ingredients are an electrical-flow estimate and a fixed-point reweighting argument.

The construction differs on either side of p = 2. For 1 < p < 2, it clips heavy-tailed stable random increments and projects them. For p > 2, it uses overlapping truncations, followed by projection and signed Poisson sampling. In both branches, the magnitude intensity is proportional to p u⁻ᵖ⁻¹ du; this is an intensity measure, not a probability distribution.

In the p > 2 illustration, four intervals overlap across magnitude scales, with counts 1, 2, 3, 4, 3, 2, 1. A bin with overlap count m contributes p log 2 times mᵖ: the factor mᵖ comes from the truncated increment, while uᵖ cancels u⁻ᵖ⁻¹ in the intensity, leaving p du/u. Thus the contribution is the same at each doubling scale. At p = 4, summing the seven bins gives b = 1808 log 2. Four intervals illustrate the calculation; the proof uses a variable number, ℓ.

For the p > 2 branch, useful energy grows like ℓᵖ⁺¹, while the p-th power of the projection error is bounded by a constant times Hᵖ⁻²(ℓ + 1). Comparing the two gives a relative error controlled by H¹⁻²/ᵖ divided by ℓ. Choosing ℓ large enough makes that error small.

Signed Poisson sampling produces candidate increments. If any increment in a sampled vector is too large, the whole vector is discarded; discarding the whole vector preserves consistency. The paper controls the additional errors from sampling and discarding. The resulting log K grows on the scale of (log n)^γ. Substituting this into the coordinate-sampling bound gives d ≤ exp(Cₚ,ᴅ (log n)^γ), the claimed subpolynomial dimension. The source presents this as a proof roadmap, not a replacement for its estimates.

The paper contrasts approximate preservation with exact preservation using row and column indicator vectors on a k by k grid, their negatives, and zero: a set of 4k + 1 points. Under an exact isometry, strict convexity forces opposite pairs to remain opposite. For p not equal to 2, a distance identity detects whether two vectors’ coordinate supports intersect.

Distinct rows must have disjoint supports, as must distinct columns. Yet every row must intersect every column. Each of the k² row-column intersections therefore requires a coordinate, giving a lower bound of k² coordinates for exact embedding. The displayed exact-dimension result is dₚ(n,1) = Θ(n²).

This lower bound does not conflict with the approximate result: it applies at distortion exactly 1, while the subpolynomial upper bound allows any fixed D greater than 1. The paper does not claim that this approximate bound is optimal or provide an efficient algorithm.