A metric space is doubling with constant at most if every open ball of radius centered in is covered by at most open balls of radius centered in . A map is a bi-Lipschitz embedding with distortion at most if there is a scale such that for all . 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 , write for the distance on . Assouad proved that if is doubling with constant at most , then admits a bi-Lipschitz embedding into some . Naor and Neiman proved that, for close to , the dimension can be bounded in terms of alone, independently of . Their bound on the distortion still depends on . For finite subsets of Hilbert space, Gottlieb and Krauthgamer obtained embeddings of with distortion arbitrarily close to one, in a dimension depending on , on and on the distortion allowed. The question of Lang and Plaut concerns the distance itself, with any finite dimension and any finite distortion allowed. For every , Lafforgue and Naor constructed doubling subsets of 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 . 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 of real , with its induced distance, which is doubling with constant at most and admits no bi-Lipschitz embedding into for any positive integer , at any finite distortion. The preprint also proves that there is a constant such that every infinite-dimensional real Banach space contains a compact subset , doubling with constant at most , that admits no bi-Lipschitz embedding into any finite-dimensional real normed space, at any finite distortion. It further derives that is isometric to a subset of real for every , a consequence the Lean library does not contain.
The Lean library DoublingHilbert proves the theorem on . It also proves the theorem on the compact subsets . 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 in the Lean library carries no hypothesis.
DoublingHilbert is a Lean library: 15 items, in six groups. Each has a page written by OctoInform, listed below.
No item matches.