Suppose that $(X,\rho)$ is a compact [doubling metric space](https://en.wikipedia.org/wiki/Doubling_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](https://web.math.princeton.edu/%7Enaor/homepage%20files/assouad-N(K).pdf), 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](https://web.math.princeton.edu/%7Enaor/homepage%20files/UCHeis9.pdf).
2. As remarked in this [old MO post](https://mathoverflow.net/questions/417185/finite-approximations-to-the-kuratowski-fr%C3%A9chet-embedding), in [this paper of Katz and Katz](https://link.springer.com/article/10.1007/s10711-010-9497-4) (with un unpublished quantitative version [found here](https://arxiv.org/pdf/1305.1529.pdf)) 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).



Bi-Lipschitz embeddings of compact doubling spaces
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.


