Suppose that $(X,\rho)$ is a compact doubling metric space. Does there necessarily exist an $\epsilon>0$ and a maximal $\epsilon$-net $\{x_i\}_{i=1}^n\subseteq X$ such that the map $$ \begin{aligned} \Phi:(X,\rho) & \rightarrow (\mathbb{R}^n,|\cdot|_2) \\ x&\mapsto \big(\rho(x,x_i)\big)_{i=1}^n \end{aligned} $$ is bi-Lipschitz? (A trivial upper-Lipschitz bound of $\sqrt{n}$ is clear but the lower-Lipschitz bound is far from obvious for me).

My question is rooted in the following observations.

Motivation/Intuition: The motivation for my question is rooted in the following two observations.

  1. The Assouad embedding theorem, see e.g. this paper for a recent formulation, shows that every doubling metric space admits a bi-Hölder embedding into a Euclidean space. Moreover, it is known that bi-Hölder is necessary, due to the global non-embeddability of the Heisenberg group, since the distortion of any closed ball diverges as the radius grows; this paper.

  2. As remarked in this old MO post, in this paper of Katz and Katz (with un unpublished quantitative version found here) shows we know that there is a bi-Lipschitz embedding of any closed and connected Riemannian manifold $(M,g)$ into some Euclidean space $(\mathbb{R}^n,|\cdot|_2)$ given by $$ \varphi:\,M\ni x\mapsto \big(\rho_g(x,x_i)\big)_{i=1}^n \in \mathbb{R}^n $$ where $\{x_i\}_{i=1}^n$ is any maximal $\epsilon$-net for some sufficiently small $\epsilon>0$ and $\rho_g$ is the geodesic distance on $(M,g)$. Clearly, compactness is needed here, since it is well-known that the hyperbolic plane cannot be bi-Lipschitz embedded into any Euclidean space.

  3. I comment that smoothness is not needed in (1) since the existence of $\Phi$ is obvious for any finite metric space.


Claim: Suppose that there exists some $0<\epsilon\le 1$ and a finite set $Y\subseteq X$ (depending on $\epsilon>0$) with the property that for every $x,z\in X$ there is some (possibly not unique) $y_{x,z}\in Y$ satisfying $$ \epsilon \rho(x,z)\le |\rho(x,y_{x,z})-\rho(z,y_{x,z})|. $$ Then, the map $\Phi(x)\mapsto (\rho(x,y))_{y\in Y}$ is a bi-Lipschitz embedding into the $|Y|$-dimensional Euclidean space.


If this case, the finiteness of $Y$ implies that $$ \epsilon \rho(x,z)\le |\rho(x,y_{x,z})-\rho(z,y_{x,z})| \le \max_{y\in Y}\, |\rho(x,y)-\rho(z,y)| \le \|\Phi(x)-\Phi(y)\|_2 \le |Y|^{1/2}\,\max_{y\in Y}\, |\rho(x,y)-\rho(z,y)| \le |Y|^{1/2}\rho(x,y) $$ where I used the fact that $|Y|<\infty$ and $x\mapsto \rho(x,y)$ is $1$-Lipschitz for every $y\in Y$.

Updated Question: So doesn't every $\epsilon$-packing do the trick and shouldn't any packing exist since packing numbers are upper-bounded by covering numbers, and in a doubling space all covering numbers are $O((\operatorname{diam}(X,\rho)\epsilon)^{-d})$ where $d$ is the doubling dimension of $(X,\rho)$ and $\operatorname{diam}(X,\rho)$ is its diameter?

In which case, why not take $\epsilon=1$? (Besides the fact that the distortion may be sub-optimal).

Thoughts: I guess the main challenge is to control the distortion and to show that one can get it to converge to $1$ as $\epsilon\downarrow 0$ (and this $n\uparrow \infty$ in general).

  • $\begingroup$ Maybe I misunderstand something, but wouldn't a tree be a counterexample: with edge lengths for example like this . 1/2 -> {. 1/4 -> {...}, . 1/4 -> {...}} (sorry for the notation, hope it is clear) $\endgroup$ Aug 13 at 23:14
  • $\begingroup$ @LorenoHeer Is such an infinite (discrete I guess) tree doubling? Since for the finite things go through ofc. $\endgroup$
    – ABIM
    Aug 14 at 0:18
  • $\begingroup$ @LorenoHeer Moreover, this tree is not complete so it is not compact. Unless I'm overlooking something. $\endgroup$
    – ABIM
    Aug 14 at 5:01
  • 1
    $\begingroup$ I meant metric tree (not discrete) with edge lengths as indicated 1/2 then branching and subsequently smaller. The limit points could be added to make the space complete I think, unless I overlook something. It is doubling with doubling constant 4, as far as I can tell. But double check this :) $\endgroup$ Aug 14 at 9:50
  • $\begingroup$ Aha, interesting, so one really needs distances to sets; as in some proofs. $\endgroup$
    – ABIM
    Aug 14 at 13:30

1 Answer 1


No. There are many compact, doubling metric spaces with no bi-Lipschitz embedding in a Hilbert space. Some examples:

  • The closed unit ball in the (continuous) Heisenberg group with its Carnot-Carath'eodory metric. (See, e.g., Theorem 6.1 of "Differentiability of Lipschitz maps from metric spaces to Banach spaces" and observe that the differentiability argument is purely local.)
  • The example in Theorem 2.3 of "Bilipschitz embeddings of metric spaces into space forms" by Lang and Plaut.
  • The examples constructed by Laakso in "Ahlfors $Q$-regular spaces with arbitrary $Q>1$ admitting weak Poincar'e inequality" and (suitably compactified) "Plane with $A_\infty$-weighted metric not bilipschitz embeddable to $\mathbb{R}^n$". See Proposition 1.23 of "Doubling conformal densities" by Bonk, Heinonen, and Rohde.
  • $\begingroup$ Ah so even for compact spaces one does need a holder type exponent...interesting... $\endgroup$
    – ABIM
    Aug 15 at 12:02
  • $\begingroup$ So with the holder exponent, does it sufficie to consider the distance to finitwly many points $\endgroup$
    – ABIM
    Aug 15 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.