Bi-Lipschitz embeddings of compact doubling spaces

Question

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.

---

Update:

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.

Proof:

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).

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.