OctoInformBeta

A doubling Hilbert subset with no finite-dimensional bi-Lipschitz embedding

A metric space (X,d)(X,d) is doubling with constant at most λ\lambda if every open ball of radius rr centered in XX is covered by at most λ\lambda open balls of radius r/2r/2 centered in XX. A map f:X→ℝkf\colon X\to\mathbb{R}^k is a bi-Lipschitz embedding with distortion at most D≥1D\ge1 if there is a scale a>0a>0 such that ad(x,y)≤∥f(x)−f(y)∥≤Dad(x,y)a\,d(x,y)\le\|f(x)-f(y)\|\le Da\,d(x,y) for all x,y∈Xx,y\in X. Every subset of a finite-dimensional Euclidean space is doubling. Lang and Plaut asked whether every doubling subset of Hilbert space admits a bi-Lipschitz embedding into some finite-dimensional Euclidean space. Gupta, Krauthgamer and Lee independently formulated the question in the context of algorithmic dimension reduction.

For 0<α<10<\alpha<1, write dαd^\alpha for the distance (x,y)↦d(x,y)α(x,y)\mapsto d(x,y)^\alpha on XX. Assouad proved that if (X,d)(X,d) is doubling with constant at most λ\lambda, then (X,dα)(X,d^\alpha) admits a bi-Lipschitz embedding into some ℝk\mathbb{R}^k. Naor and Neiman proved that, for α\alpha close to 11, the dimension kk can be bounded in terms of λ\lambda alone, independently of α\alpha. Their bound on the distortion still depends on α\alpha. For finite subsets of Hilbert space, Gottlieb and Krauthgamer obtained embeddings of (X,dα)(X,d^\alpha) with distortion arbitrarily close to one, in a dimension depending on λ\lambda, on α\alpha and on the distortion allowed. The question of Lang and Plaut concerns the distance dd itself, with any finite dimension and any finite distortion allowed. For every p>2p>2, Lafforgue and Naor constructed doubling subsets of LpL_p that admit no bi-Lipschitz embedding into any finite-dimensional Euclidean space. Independently, Bartal, Gottlieb and Neiman obtained obstructions to dimension reduction for doubling subsets of ℓp\ell_p. Schioppa announced a negative answer in 2017. Schioppa withdrew the announcement after reporting a possible issue with its argument.

The preprint answers the question of Lang and Plaut in the negative: there is a single subset SS of real ℓ2\ell_2, with its induced distance, which is doubling with constant at most 7680076800 and admits no bi-Lipschitz embedding into ℝk\mathbb{R}^k for any positive integer kk, at any finite distortion. The preprint also proves that there is a constant Λ\Lambda such that every infinite-dimensional real Banach space BB contains a compact subset KBK_B, doubling with constant at most Λ\Lambda, that admits no bi-Lipschitz embedding into any finite-dimensional real normed space, at any finite distortion. It further derives that SS is isometric to a subset of real Lp([0,1])L_p([0,1]) for every 1≤p<∞1\le p<\infty, a consequence the Lean library does not contain.

The Lean library DoublingHilbert proves the theorem on SS. It also proves the theorem on the compact subsets KBK_B. Lean has checked every result of the Lean library, so the Lean library is the reference. The results on these pages are the Lean library’s, each stated as the Lean library states it and linked to the Lean declaration behind it. Where the preprint states a result differently, the page gives the Lean library’s statement, with the preprint’s beside it. The preprint is a guide only: it gives the results their order and their names. The theorem on SS in the Lean library carries no hypothesis.

The Lean library: DoublingHilbert

DoublingHilbert is a Lean library: 15 items, in six groups. Each has a page written by OctoInform, listed below.

§1. Introduction and the main theorem 2 items
  1. Doubling and bi-Lipschitz embeddings Doubling and bi-Lipschitz embeddable subsets of Hilbert space.
  2. Theorem 1 A doubling subset of ℓ2\ell^2 with no bi-Lipschitz embedding in ℝk\mathbb{R}^k.
§2. The subset and its doubling bound 2 items
  1. Scales, colored strips and the set S A Hilbert subset built over colored strips of the plane.
  2. Proposition 2 The constructed subset of Hilbert space is doubling.
§3. Sheets and extremal derivatives 3 items
  1. Sheets, good points, the compact set K and the pair (A, B) Sheets of a Lipschitz map and the extremal derivative pair.
  2. Lemma 3 Second coordinates of a compact set near its lexicographic maximum.
  3. The variance identity The variance identity and an energy bound on segments.
§4. Near-extremal rectangles and two energy estimates 2 items
  1. Near-extremal rectangles, added sheets and selected derivative fields Near-extremal grid rectangles and sheets added at an unused level.
  2. Proposition 4 Energy bounds for added sheets on near-extremal grids.
§5. Crossings force a packing contradiction (proof of Theorem 1) 1 item
  1. One period block, selected lines and separated vectors No bi-Lipschitz embedding of the constructed set into Euclidean space.
§7. Compact obstructions in infinite-dimensional Banach spaces 5 items
  1. Corollary 6 Compact doubling sets with no finite-dimensional bi-Lipschitz embedding.
  2. Finite witnesses Finite subsets of SS forcing large distortion in ℝk\mathbb{R}^k.
  3. Placement and cluster doubling Finite subsets of SS placed in infinite-dimensional normed spaces.
  4. Compact assembly and its covering bound Doubling clusters at dyadic scales assemble into a compact doubling set.
  5. Finite-dimensional targets A Euclidean target suffices for finite-dimensional bi-Lipschitz embeddings.

No item matches.