Almost Homogeneity Characterizes Almost Bi-Lipschitz Euclidean Embeddability

Abstract

A metric space admits an almost bi-Lipschitz embedding into a Euclidean space if and only if it is almost homogeneous. We prove the sufficient direction, complementing the known necessary condition. More quantitatively, we bound the target dimension and the embedding constants for every logarithmic exponent $γ>1$. The bounds depend only on the covering parameters in the almost homogeneity condition. In particular every doubling metric space admits such an embedding. This answers a question of Margaris and Robinson and the almost bi-Lipschitz part of a question of Olson and Robinson. As a consequence, the difference set of the image is doubling, which answers the difference-set questions of Olson and Robinson and of Margaris.