OctoInformBeta

OpenAI preprint, September 2026 · §7. The range 2 < p < ∞

§7.3-§7.4 (proof of Theorem 1.1): summing the jumps and discarding a bad vector: Bounded gradient laws and coordinate dimension for p>2p>2 and fixed distortion greater than one

Ramp sums give subpolynomial dimension 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 a real LpL_p space, the dimension problem asks for a realization in finitely many real coordinates with prescribed distortion. Here p>2p>2. The constructions concern coordinate moments of fixed sums of symmetric random vectors and a cutoff that discards a whole vector.

The coordinate distance dℓp(y,y′)d_{\ell_p}(y,y') between y,y′∈ℝdy,y'\in\mathbb R^d is the ℓp\ell_p distance defined in (1). dℓp(y,y′)=(∑a=1d|ya−ya′|p)1/p.d_{\ell_p}(y,y')= \left(\sum_{a=1}^d|y_a-y'_a|^p\right)^{1/p}.(1) For a family size nn and a distortion DD, an admissible dimension dd for p,n,Dp,n,D is a nonnegative integer such that every injective family x1,…,xnx_1,\ldots,x_n in Lp(Ω,μ)L_p(\Omega,\mu), over any measure space, admits y1,…,yn∈ℝdy_1,\ldots,y_n\in\mathbb R^d and a scale s>0s>0 satisfying (2) for every i,ji,j. s∥xi−xj∥≤dℓp(yi,yj)≤Ds∥xi−xj∥.s\|x_i-x_j\|\le d_{\ell_p}(y_i,y_j) \le Ds\|x_i-x_j\|.(2) The universal coordinate dimension dp(n,D)d_p(n,D) is the infimum in the nonnegative integers of the admissible dimensions, as in (3). dp(n,D)=inf⁡{d∈ℕ0:d is admissible for p,n,D},γ(p)=1−2p.d_p(n,D)=\inf\{d\in\mathbb N_0:d\text{ is admissible for }p,n,D\}, \qquad \gamma(p)=1-\frac2p.(3)✦

Gradient Laws and Ramp Parameters

Let XX and EE be finite vertex and edge sets, with endpoint maps a,c:E→Xa,c:E\to X and real edge scales δe\delta_e. The incidence matrix AA is the matrix with entries in (4); the normalized gradient ∇δ\nabla_\delta is its product with the indicated diagonal matrix, and its image V⊆ℝEV\subseteq\mathbb R^E is the normalized-gradient space. Aei=𝟏{a(e)=i}−𝟏{c(e)=i},∇δ=diag⁡(δe−1)A,V=im⁡∇δ.A_{ei}=\mathbf1_{\{a(e)=i\}}-\mathbf1_{\{c(e)=i\}}, \qquad \nabla_\delta=\operatorname{diag}(\delta_e^{-1})A, \qquad V=\operatorname{im}\nabla_\delta.(4)

A symmetric probability law ν\nu on ℝE\mathbb R^E is a probability measure invariant under z↦−zz\mapsto-z. For a measure ν\nu on ℝE\mathbb R^E and N∈ℕ0N\in\mathbb N_0, the fixed convolution power ν*N\nu^{*N} is the measure defined by (5), where δ0\delta_0 denotes unit mass at zero. ν*0=δ0,ν*(N+1)=ν*N*ν(N∈ℕ0).\nu^{*0}=\delta_0,\qquad \nu^{*(N+1)}=\nu^{*N}*\nu\quad(N\in\mathbb N_0).(5) For a measure μ\mu on ℝE\mathbb R^E, an exponent qq, coordinate weights w=(we)e∈Ew=(w_e)_{e\in E}, and a target bb, write Mq,e(μ)M_{q,e}(\mu) for its coordinate qqth moment and ℰq,w,b(μ)\mathcal E_{q,w,b}(\mu) for the weighted error from bb, as in (6). Mq,e(μ)=∫|ze|qdμ(z),ℰq,w,b(μ)=∑e∈Ewe|Mq,e(μ)−b|.M_{q,e}(\mu)=\int |z_e|^q\,d\mu(z),\qquad \mathcal E_{q,w,b}(\mu)=\sum_{e\in E}w_e|M_{q,e}(\mu)-b|.(6) The global cutoff at a real threshold TT is the map 𝒞T:ℝE→ℝE\mathcal C_T:\mathbb R^E\to\mathbb R^E defined in (7). 𝒞T(z)={z,|ze|≤T for every e∈E,0,otherwise.\mathcal C_T(z)= \begin{cases} z,& |z_e|\le T\text{ for every }e\in E,\\ 0,&\text{otherwise}. \end{cases}(7)✦

The power intensity ϑp\vartheta_p is the measure on the positive half-line with density pr−p−1pr^{-p-1}, and the Pareto measure πp\pi_p is its restriction to (1,∞)(1,\infty), as in (8). dϑp(r)=𝟏{r>0}pr−p−1dr,πp=ϑp|(1,∞).d\vartheta_p(r)=\mathbf1_{\{r>0\}}pr^{-p-1}\,dr, \qquad \pi_p=\vartheta_p\big|_{(1,\infty)}.(8) For real a,ba,b, the band truncation Ba,b:ℝ→ℝB_{a,b}:\mathbb R\to\mathbb R retains a scalar precisely when its magnitude belongs to (a,b](a,b].✦ The dyadic ramp sum ρℓ:ℝ→ℝ\rho_\ell:\mathbb R\to\mathbb R, for ℓ∈ℕ0\ell\in\mathbb N_0, is the sum of these truncations in (9). Ba,b(r)=r𝟏{a<|r|≤b},ρℓ(r)=∑k=0ℓ−1B2k,2k+ℓ(r).B_{a,b}(r)=r\mathbf1_{\{a<|r|\le b\}},\qquad \rho_\ell(r)=\sum_{k=0}^{\ell-1}B_{2^k,2^{k+\ell}}(r).(9) The ramp variance constant vpv_p, the target moment bℓb_\ell, and the scales Hn,Jn,ℓH_n,J_{n,\ell} for n≥2n\ge2 are defined by (10). vp=p/(p−2)(1−2(2−p)/2)2,bℓ=∫|ρℓ(r)|pdπp(r),Hn=4log⁡n,Jn,ℓ=(vp+1)Hn22ℓ.\begin{gathered} v_p=\frac{p/(p-2)}{(1-2^{(2-p)/2})^2},\qquad b_\ell=\int|\rho_\ell(r)|^p\,d\pi_p(r),\\ H_n=4\log n,\qquad J_{n,\ell}=(v_p+1)H_n2^{2\ell}. \end{gathered}(10)✦

The Claim

Theorem 1. Let ε,U,H>0\varepsilon,U,H>0, b≥0b\ge0, B,err∈ℝB,\mathrm{err}\in\mathbb R, and N∈ℕ0N\in\mathbb N_0. Suppose ν\nu is a symmetric probability law on ℝE\mathbb R^E, we≥0w_e\ge0, and ∑ewe=1\sum_e w_e=1. Assume |ze|≤B|z_e|\le B for every ee, almost surely, and the moment conditions in (11). ∑ewe|NMp,e(ν)−b|≤err,∑eweNM2,e(ν)≤4U,NM2,e(ν)≤H2U(e∈E).\sum_e w_e|NM_{p,e}(\nu)-b|\le\mathrm{err},\qquad \sum_e w_eNM_{2,e}(\nu)\le4U,\qquad NM_{2,e}(\nu)\le H^2U\quad(e\in E).(11) The weighted moment estimate (12) holds with a constant C≥0C\ge0 depending only on p,ε,Up,\varepsilon,U. ℰp,w,b(ν*N)≤(1+ε)2err+((1+ε)2−1)b+CHp−2.\mathcal E_{p,w,b}(\nu^{*N})\le (1+\varepsilon)^2\mathrm{err} +\bigl((1+\varepsilon)^2-1\bigr)b+CH^{p-2}.(12)✦

Let ν\nu be a symmetric probability law on ℝE\mathbb R^E, J>0J>0, and N∈ℕ0N\in\mathbb N_0. Suppose |ze|≤J|z_e|\le J for all ee, almost surely, and NM2,e(ν)≤J2NM_{2,e}(\nu)\le J^2 for each ee. For every e∈Ee\in E and s∈ℝs\in\mathbb R with |s|=1|s|=1, the exponential integrability and bound are (13). [z↦exp⁡(sze/J)]∈L1(ν*N),∫exp⁡(sze/J)dν*N(z)≤exp⁡(1).\bigl[z\mapsto\exp(sz_e/J)\bigr]\in L^1(\nu^{*N}),\qquad \int\exp(sz_e/J)\,d\nu^{*N}(z)\le\exp(1).(13)✦

Take q>0q>0, a probability law μ\mu on ℝE\mathbb R^E, J>0J>0 and T≥0T\ge0. Suppose every |ze|q|z_e|^q is integrable and the exponential integrability and bound in (13) hold for μ\mu in place of ν*N\nu^{*N}. With a constant Cq>0C_q>0 depending only on qq, the cutoff error satisfies (14) for every e∈Ee\in E. |∫|𝒞T(z)e|qdμ(z)−Mq,e(μ)|≤Cq(2J)qexp⁡(−T2J)|E|.\left|\int|\mathcal C_T(z)_e|^q\,d\mu(z)-M_{q,e}(\mu)\right| \le C_q(2J)^q\exp\!\left(-\frac{T}{2J}\right)|E|.(14)✦

Fix ε>0\varepsilon>0. Suppose EE is nonempty, |X|=n≥2|X|=n\ge2, every vertex meets an edge, and every two distinct vertices are endpoints of some edge. Take δe,we>0\delta_e,w_e>0 with ∑ewe=1\sum_e w_e=1, and a finite nonempty family (gi)i∈I(g_i)_{i\in I} in VV satisfying ∑i∈I|gi(e)|p=1\sum_{i\in I}|g_i(e)|^p=1 for every ee. For every ℓ∈ℕ0\ell\in\mathbb N_0 and T≥0T\ge0, there is a probability law μ\mu on ℝE\mathbb R^E satisfying (15), with C>0C>0 depending only on p,εp,\varepsilon. μ(V∩[−T,T]E)=1,ℰp,w,bℓ(μ)≤((1+ε)3−1)bℓ+CHnp−2(ℓ+1)+CJn,ℓpexp⁡(−T2Jn,ℓ)|E|.\begin{gathered} \mu\bigl(V\cap[-T,T]^E\bigr)=1,\\ \mathcal E_{p,w,b_\ell}(\mu)\le \bigl((1+\varepsilon)^3-1\bigr)b_\ell +CH_n^{p-2}(\ell+1) +CJ_{n,\ell}^p\exp\!\left(-\frac{T}{2J_{n,\ell}}\right)|E|. \end{gathered}(15)✦

Suppose R>3R>3, C>0C>0, and β≤1/(2R)\beta\le1/(2R). For each integer n≥2n\ge2, parameters ℓ∈ℕ0\ell\in\mathbb N_0 and T∈ℝT\in\mathbb R can be chosen to satisfy (16), with a constant A>0A>0 independent of nn. 0≤T≤Hn2exp⁡(A(Hnγ(p)+1)),1≤bℓ/R,βbℓ+CHnp−2(ℓ+1)+CJn,ℓpexp⁡(−T2Jn,ℓ)n2≤bℓ/R.\begin{gathered} 0\le T\le H_n^2\exp\!\bigl(A(H_n^{\gamma(p)}+1)\bigr), \qquad 1\le b_\ell/R,\\ \beta b_\ell+CH_n^{p-2}(\ell+1) +CJ_{n,\ell}^p\exp\!\left(-\frac{T}{2J_{n,\ell}}\right)n^2 \le b_\ell/R. \end{gathered}(16)✦

For every D>1D>1 there is a real constant C=C(p,D)C=C(p,D) such that the universal coordinate dimension satisfies (17) for every integer n≥2n\ge2. dp(n,D)≤exp⁡(C(log⁡n)γ(p)).d_p(n,D)\le\exp\!\bigl(C(\log n)^{\gamma(p)}\bigr).(17)✦

In the paper, the result reads: with Hpap=4log⁡(2n)H_{\mathrm{pap}}=4\log(2n), the signed compound Poisson sum WW of the ramp jump ZZ belongs to VV, its ppth moments weighted by λ=(λe)e∈E\lambda=(\lambda_e)_{e\in E} approach a target bb after averaging the nearly additive moment error, for constants Cp′,C0C'_p,C_0 the scale Jpap=Cp′Hpap22ℓJ_{\mathrm{pap}}=C'_pH_{\mathrm{pap}}2^{2\ell} gives, for a scalar uu, ℙ(|We|>Jpapu)≤2exp⁡(C0−u)\mathbb P(|W_e|>J_{\mathrm{pap}}u)\le2\exp(C_0-u), and, for each η>0\eta>0, discarding the whole vector whenever max⁡e|We|>Kpap\max_e|W_e|>K_{\mathrm{pap}}, where Kpap=8Jpaplog⁡(2n)K_{\mathrm{pap}}=8J_{\mathrm{pap}}\log(2n), gives a bounded gradient FF with λ\lambda-weighted error at most ηb\eta b for sufficiently large nn and log⁡Kpap=Op,η((log⁡n)1−2/p)\log K_{\mathrm{pap}}=O_{p,\eta}((\log n)^{1-2/p}).

What Is Checked

The dimension estimate concerns the universal realization property in (2) for p>2p>2 and D>1D>1, while the moment and cutoff estimates concern probability laws on finite real coordinate spaces and normalized gradients as in (4).