OctoInformBeta

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

Doubling and bi-Lipschitz embeddings: Subsets of real ℓ2\ell^2 doubling with constant at most λ\lambda, and bi-Lipschitz embeddings into ℝk\mathbb{R}^k with scale aa and distortion DD

Doubling and bi-Lipschitz embeddable subsets of Hilbert space.

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

Take a subset SS of the real Hilbert space ℓ2\ell^2, with the distance it inherits. Two conditions on SS make precise that it is finite-dimensional as a metric space: that SS is doubling, a condition on the distances between its points alone, and that SS admits a bi-Lipschitz embedding into some Euclidean space ℝk\mathbb{R}^k.

A subset of ℓ2\ell^2 with a bi-Lipschitz embedding into some ℝk\mathbb{R}^k is doubling. The question is the converse: does every doubling subset of ℓ2\ell^2 admit a bi-Lipschitz embedding into some ℝk\mathbb{R}^k? The library’s source answers it in the negative, with a doubling subset of ℓ2\ell^2 that admits no bi-Lipschitz embedding into any ℝk\mathbb{R}^k.

The Definition

Definition 1. The real Hilbert space ℓ2\ell^2 is the space of real sequences x=(xn)n≥0x = (x_n)_{n \ge 0} with ∑n≥0xn2<∞\sum_{n \ge 0} x_n^2 < \infty, with the norm and the distance ∥x∥=(∑n≥0xn2)1/2,d(x,y)=∥x−y∥.\|x\| = \Big(\sum_{n \ge 0} x_n^2\Big)^{1/2}, \qquad d(x, y) = \|x - y\|.(1)✦

For a natural number λ\lambda, a subset SS of ℓ2\ell^2 is doubling with constant at most λ\lambda if for every point xx of SS and every r>0r > 0 there is a set CC of at most λ\lambda points of SS with S∩B(x,r)⊆⋃c∈CB(c,r/2),S \cap B(x, r) \subseteq \bigcup_{c \in C} B(c, r/2),(2)✦ where B(z,s)B(z, s) is the open ball of radius ss about zz in ℓ2\ell^2.

For a natural number kk, a subset SS of ℓ2\ell^2 admits a bi-Lipschitz embedding into the Euclidean space ℝk\mathbb{R}^k, with its norm ∥⋅∥\|\cdot\|, 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 with ad(x,y)≤∥f(x)−f(y)∥≤Dad(x,y)for all x,y∈S.a\, d(x, y) \le \|f(x) - f(y)\| \le D\, a\, d(x, y) \qquad \text{for all } x, y \in S.(3)✦

What Is Checked

The definitions of doubling and of bi-Lipschitz embeddability are stated over subsets SS of the real Hilbert space ℓ2\ell^2 of square-summable real sequences (1), with a natural number λ\lambda bounding the size of the set CC in (2) and a natural number kk, the dimension of the Euclidean space ℝk\mathbb{R}^k in (3).