OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction and the main theorem

Theorem 1: One set SS, chosen before the dimension k≥1k \ge 1 and the distortion, with doubling constant at most 7680076800

A doubling subset of ℓ2\ell^2 with no bi-Lipschitz embedding in ℝk\mathbb{R}^k..

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

Every subset of a Euclidean space ℝk\mathbb{R}^k is doubling, and a bi-Lipschitz image of a doubling space is again doubling. Being doubling is therefore necessary for a subset of the Hilbert space ℓ2\ell^2 to admit a bi-Lipschitz embedding into some ℝk\mathbb{R}^k, and the question is whether it is also sufficient.

The library settles the question with one theorem about a single subset SS of ℓ2\ell^2, built on two definitions: a doubling subset and a bi-Lipschitz embedding.

Doubling Subsets and Bi-Lipschitz Embeddings

The Hilbert space ℓ2\ell^2 is the real vector space of square-summable real sequences z=(zn)n≥0z = (z_n)_{n \ge 0}, with the distance d(z,z′)=∥z−z′∥=(∑n≥0(zn−zn′)2)1/2.d(z, z') = \|z - z'\| = \Big(\sum_{n \ge 0} (z_n - z'_n)^2\Big)^{1/2}.(1)✦

Let NN be a natural number. A subset SS of ℓ2\ell^2 is doubling with constant at most NN if for every point z∈Sz \in S and every radius r>0r > 0 there is a set CC of at most NN points of SS such that z′∈S,d(z′,z)<r⇒d(z′,c)<r/2 for some c∈C.z' \in S,\ d(z', z) < r \quad\Longrightarrow\quad d(z', c) < r/2 \ \text{ for some } c \in C.(2)✦

Let kk be a natural number, and give ℝk\mathbb{R}^k its Euclidean norm. A subset SS of ℓ2\ell^2 admits a bi-Lipschitz embedding into ℝk\mathbb{R}^k if there are a map f:S→ℝkf\colon S \to \mathbb{R}^k, a scale a>0a > 0 and a distortion D≥1D \ge 1 such that ad(z,z′)≤∥f(z)−f(z′)∥≤Dad(z,z′)for all z,z′∈S.a\, d(z, z') \le \|f(z) - f(z')\| \le D\, a\, d(z, z') \qquad \text{for all } z, z' \in S.(3)✦

The Claim

Theorem 1. There is a subset SS of ℓ2\ell^2, doubling with constant at most 7680076800 in the sense of (2), such that for every positive integer kk, every map f:S→ℝkf\colon S \to \mathbb{R}^k, every scale a>0a > 0 and every distortion D≥1D \ge 1, there are points z,z′∈Sz, z' \in S with ∥f(z)−f(z′)∥<ad(z,z′)or∥f(z)−f(z′)∥>Dad(z,z′).\|f(z) - f(z')\| < a\, d(z, z') \quad\text{or}\quad \|f(z) - f(z')\| > D\, a\, d(z, z').(4)✦

What Is Checked

The claim is stated over the Hilbert space ℓ2\ell^2 with the distance (1), the doubling condition (2) with N=76800N = 76800, and bi-Lipschitz embeddings into ℝk\mathbb{R}^k in the sense of (3).