OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Theorem 1.1: For p>1p>1, p≠2p\ne2, fixed distortion above one and exact embeddings have different logarithmic limits

Dimension bounds for finite LpL_p sets.

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

Fix a real exponent p>1p>1 with p≠2p\ne2. The dimension reduction problem asks how few real coordinates suffice to represent finite subsets of real LpL_p spaces at a prescribed distortion. All logarithms are natural, and the maps need not be linear.

For a nonnegative integer dd, the coordinate distance ρp\rho_p on ℝd\mathbb R^d is given, for u,v∈ℝdu,v\in\mathbb R^d, 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)✦

For a nonnegative integer nn and a real number DD, a nonnegative integer dd is an admissible dimension for (p,n,D)(p,n,D) if every set of nn distinct points x1,…,xnx_1,\ldots,x_n in a real Lp(μ)L_p(\mu) space, over any measure space, 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\|x_i-x_j\|_{L_p(\mu)} \le \rho_p(y_i,y_j) \le Ds\|x_i-x_j\|_{L_p(\mu)} \qquad (1\le i,j\le n).(2)✦

The universal coordinate dimension dp(n,D)d_p(n,D) is the infimum, in the nonnegative integers, of the admissible dimensions in (3). dp(n,D)=infℕ{d∈ℕ:d is an admissible dimension for (p,n,D)}.d_p(n,D)=\inf_{\mathbb N} \{d\in\mathbb N: d\text{ is an admissible dimension for }(p,n,D)\}.(3)✦

The growth exponent γ(p)\gamma(p) is the real number defined by (4). γ(p)={2−p,1<p<2,1−2p,p>2.\gamma(p)= \begin{cases} 2-p, & 1<p<2,\\ 1-\dfrac{2}{p}, & p>2. \end{cases}(4)✦

The Claim

Theorem 1. Let p>1p>1 with p≠2p\ne2. For D>1D>1 and n≥2n\ge2, the dimension dp(n,D)d_p(n,D) is admissible, and for n≥9n\ge9, the dimension dp(n,1)d_p(n,1) is admissible.✦ The following bounds and limits hold, with a real constant C=C(p,D)C=C(p,D) for each fixed D>1D>1 in the first line of (5): log⁡nlog⁡(1+2D)≤dp(n,D)≤exp⁡(C(logn)γ(p))(D>1,n≥2),⌊n−14⌋2≤dp(n,1)≤(n2)(n≥9),limn→∞log⁡dp(n,D)log⁡n={0,D>1,2,D=1(D≥1).\begin{aligned} \frac{\log n}{\log(1+2D)} &\le d_p(n,D) \le \exp\!\left(C(\log n)^{\gamma(p)}\right) && (D>1,\ n\ge2),\\[0.8ex] \left\lfloor\frac{n-1}{4}\right\rfloor^{\!2} &\le d_p(n,1)\le\binom{n}{2} && (n\ge9),\\[0.8ex] \lim_{n\to\infty}\frac{\log d_p(n,D)}{\log n} &=\begin{cases} 0, & D>1,\\ 2, & D=1 \end{cases} && (D\ge1). \end{aligned}(5)✦

What Is Checked

The claim is stated over arbitrary measure spaces and injective nn-point configurations in real LpL_p, with p>1p>1 and p≠2p\ne2, using admissible coordinate dimensions, their universal infimum dp(n,D)d_p(n,D), and the exponent γ(p)\gamma(p).