OctoInformBeta

OpenAI preprint, September 2026 · §8. Dimension bounds and exact embeddings

§8.2 (proof of Theorem 1.1): packing lower bound: Equilateral LpL_p sets constrain universal coordinate dimensions for p>1p>1 and D≥1D\ge1

Packing forces a dimension lower bound.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

The packing question asks how many mutually separated points fit in a bounded ball of a finite-dimensional normed space. For finite subsets of real LpL_p, the dimension question asks which coordinate dimensions permit a prescribed distortion for every set of a fixed size.

For a real exponent pp, a natural number dd, and vectors u,v∈ℝdu,v\in\mathbb R^d, the coordinate distance ρp(u,v)\rho_p(u,v) is ρp(u,v)=(∑a=1d|ua−va|p)1/p.\rho_p(u,v)=\left(\sum_{a=1}^{d}|u_a-v_a|^p\right)^{1/p}.(1) For real p,Dp,D and n∈ℕn\in\mathbb N, an admissible dimension dd is a natural number such that, for every measure space (Ω,μ)(\Omega,\mu) and every injective family x:{1,…,n}→Lp(Ω,μ)x:\{1,\ldots,n\}\to L_p(\Omega,\mu), there are a family y:{1,…,n}→ℝdy:\{1,\ldots,n\}\to\mathbb R^d and a scale s>0s>0 satisfying, with the distance from (1), s∥xi−xj∥≤ρp(yi,yj)≤Ds∥xi−xj∥(1≤i,j≤n).s\|x_i-x_j\| \le \rho_p(y_i,y_j) \le Ds\|x_i-x_j\| \qquad (1\le i,j\le n).(2)✦ The universal coordinate dimension dp(n,D)d_p(n,D) is the infimum in the natural numbers of the dimensions satisfying (2): dp(n,D)=infℕ{d∈ℕ:d is admissible for p,n,D}.d_p(n,D)=\inf_{\mathbb N}\{d\in\mathbb N:d\text{ is admissible for }p,n,D\}.(3)✦

The Claim

Theorem 1. Let EE be a real finite-dimensional normed space of dimension mm. Let R≥0R\ge0 and let S⊂ES\subset E be finite, with ∥c∥≤R\|c\|\le R for every c∈Sc\in S and ∥c−d∥≥1\|c-d\|\ge1 for distinct c,d∈Sc,d\in S. Then |S|≤(1+2R)m.|S|\le(1+2R)^m.(4)✦

For p>0p>0 and n∈ℕn\in\mathbb N, let In={1,…,n}I_n=\{1,\ldots,n\} carry counting measure. There is an injective family x:In→Lp(In)x:I_n\to L_p(I_n) such that ∥xi−xj∥=21/p(i,j∈In,i≠j).\|x_i-x_j\|=2^{1/p} \qquad (i,j\in I_n,\ i\ne j).(5)✦

Let p>1p>1, n≥2n\ge2 and D≥1D\ge1. Every admissible dimension dd satisfies log⁡nlog⁡(1+2D)≤d.\frac{\log n}{\log(1+2D)}\le d.(6)✦ The universal coordinate dimension satisfies log⁡nlog⁡(1+2D)≤dp(n,D).\frac{\log n}{\log(1+2D)}\le d_p(n,D).(7)✦

What Is Checked

The packing estimate (4) is stated for finite subsets of real finite-dimensional normed spaces, and the equilateral and dimension statements (5), (6) and (7) concern counting measure on InI_n and the admissibility property (2) over arbitrary measure spaces with its natural infimum (3), respectively.