# Bi-Lipschitz embeddings of compact doubling spaces

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

• 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) Aug 13 at 23:14
• @LorenoHeer Is such an infinite (discrete I guess) tree doubling? Since for the finite things go through ofc.
– ABIM
Aug 14 at 0:18
• @LorenoHeer Moreover, this tree is not complete so it is not compact. Unless I'm overlooking something.
– ABIM
Aug 14 at 5:01
• 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 :) Aug 14 at 9:50
• Aha, interesting, so one really needs distances to sets; as in some proofs.
– ABIM
Aug 14 at 13:30

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