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.

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

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

4more comments