OctoInformBeta

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

§8.1 (proof of Theorem 1.1): assembling the upper bound: The least universal coordinate dimension is admissible for exponent p>1p>1, cardinality n≥2n\ge2 and distortion D≥1D\ge1

Sampling size and exact coordinate bounds.

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

For a finite subset of real LpL_p, the coordinate dimension measures how many real coordinates suffice to realize its distances within a prescribed distortion. Let p>0p>0, let nn be a natural number, and let DD be a real distortion bound. For a natural number dd, the coordinate distance ρp\rho_p on ℝd\mathbb R^d is the function defined by (1): ρ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)✦

An admissible dimension dd for p,n,Dp,n,D is a natural number such that every family x1,…,xnx_1,\ldots,x_n of distinct points in real Lp(Ω,μ)L_p(\Omega,\mu), on any measure space (Ω,μ)(\Omega,\mu), admits points y1,…,yn∈ℝdy_1,\ldots,y_n\in\mathbb R^d and a scale s>0s>0 satisfying (2): s‖xi−xj‖Lp≤ρp(yi,yj)≤Ds‖xi−xj‖Lp(1≤i,j≤n).s\lVert x_i-x_j\rVert_{L_p} \le \rho_p(y_i,y_j) \le Ds\lVert x_i-x_j\rVert_{L_p} \qquad (1\le i,j\le n).(2)✦ Write 𝒟p(n,D)⊆ℕ\mathcal D_p(n,D)\subseteq\mathbb N for the set of admissible dimensions. The universal dimension dp(n,D)d_p(n,D) is the infimum in the natural numbers of the set 𝒟p(n,D)\mathcal D_p(n,D) of admissible dimensions for p,n,Dp,n,D, as in (3): dp(n,D)=infℕ𝒟p(n,D).d_p(n,D)=\inf_{\mathbb N}\mathcal D_p(n,D).(3)✦

The Sampling Parameters

For n≥2n\ge2, r>0r>0 and A≥0A\ge0, the sampling dimension dsampd_{\mathrm{samp}} is the natural number defined with HH and KK by (4); the ceiling denotes the least integer at least its argument. H=4log⁡n,K=H2exp⁡(A(Hr+1)),dsamp=⌈(Kp)2(H+1)⌉+1.\begin{aligned} H&=4\log n,\\ K&=H^2\exp\bigl(A(H^r+1)\bigr),\\ d_{\mathrm{samp}}&=\left\lceil (K^p)^2(H+1)\right\rceil+1. \end{aligned}(4) For p>1p>1 with p≠2p\ne2, the exponent γ(p)\gamma(p) is defined by (5): γ(p)={2−p,1<p<2,1−2/p,p>2.\gamma(p)= \begin{cases} 2-p,&1<p<2,\\ 1-2/p,&p>2. \end{cases}(5)

The Claim

Theorem 1. Let p>0p>0, r>0r>0, A≥0A\ge0 and n≥2n\ge2. The sampling dimension in (4) satisfies (6): dsamp≤exp⁡((3+4p+1r+4pA)4r(logn)r).d_{\mathrm{samp}} \le \exp\!\left( \left(3+\frac{4p+1}{r}+4pA\right)4^r(\log n)^r \right).(6)✦ For p>1p>1, n≥2n\ge2 and D≥1D\ge1, the universal dimension satisfies (7) and (8): dp(n,D)∈𝒟p(n,D).d_p(n,D)\in\mathcal D_p(n,D).(7)✦ dp(n,D)≤(n2).d_p(n,D)\le\binom n2.(8)✦

In the paper, the result reads: for p>1p>1, p≠2p\ne2 and prescribed D>1D>1, inserting the moments and magnitude bounds from Sections 6 and 7 into Lemma 3.1 and choosing the parameter η\eta for this distortion gives, for a constant Cp,DC_{p,D}, log⁡d≤Cp,D(log⁡n)γ(p)\log d\le C_{p,D}(\log n)^{\gamma(p)} for sufficiently large nn, after which the constant is enlarged and exact discretization covers the remaining finitely many nn.

What Is Checked

The statements concern the sampling parameters in (4) and the natural infimum in (3), with admissibility quantified over every measure space and every family of distinct points in its real LpL_p space as in (2).