Theorem (??) derived in this MO-post from Schoenberg's theorem yeilds a "bipartite" characterization of metric spaces that admit an isometric embedding into a Hilbert space. This Theorem (??) implies the following necessary condition of bi-Lipschitz embeddability into a Hilbert space.

Theorem. If a metric space $X$ admits a bi-Lipschitz embedding to a Hilbert space, then there exists a positive real constant $L$ such that the inequality $$\sum_{i<j}d^2(x_i^+,x_j^+)+\sum_{i<j}d^2(x_i^-,x_j^-)\le L\cdot \sum_{i,j}d^2(x_i^+,x_j^-)\quad\quad\quad(*)$$holds for any points $x_1^+,\dots,x_n^+,x_1^-,\dots,x_n^-\in X$.

Remark. The inequality $(*)$ in Theorem is not sufficient for the existence of a bi-Lipschitz embeding of $X$ to a Hilbert space. Indeed, the triangle inequality implies that for every metric $d$ on set $X$ the metric $\sqrt{d}$ satisfies the inequality $(*)$ with $L=2$. It is known that the unit ball $(B,d)$ of the Banach space $c_0$ does not admit a uniform embedding into a Hilbert space. Then the metric space $(B,\sqrt{d})$ satisfies the inequality $(*)$ (with $L=2$ but admits no bi-Lipschitz embedding to a Hilbert space.

Problem 1. Is there any nice geometric condition (or inequality) which is necessary and sufficient for the existence of a bi-Lipschitz embedding of a given metric space to a Hilbert space?

Problem 2. Is there a positive $\varepsilon$ such that each metric space $X$ satifying the inequality $(*)$ for $L=1+\varepsilon$ admits a bi-Lipschitz embedding to a Hilbert space?

  • $\begingroup$ So, as in your previous post, if (*) holds with L=1 then it is also a sufficient condition? In other words, is $\epsilon = 0$ a trivial answer to problem 2? $\endgroup$ Commented Apr 17, 2018 at 20:36
  • $\begingroup$ @BehnamEsmayli Yes, so I am asking about positive $\varepsilon$. $\endgroup$ Commented Apr 18, 2018 at 4:05

2 Answers 2


Schoenberg's criterion can be extended to bi-Lipschtiz embeddings. This is Corollary 3.5 in:

N. Linial, E. London, Y. Rabinovich, The geometry of graphs and some of its algorithmic applications. Combinatorica 15 (1995), no. 2, 215–245. (Also available here.) (MathSciNet review.)

  • $\begingroup$ "can be extended"... is a vague statement, and in any case this is just one possible extension. This is a criterion for existence of a embedding with some bound on the distortion. $\endgroup$
    – YCor
    Commented Apr 13, 2018 at 14:56
  • $\begingroup$ @YCor Existence of an embedding with distortion $c\geq 1$ means existence of a bi-Lipschitz embedding $d(x,y)\geq |f(x)-f(y)|\geq c^{-1}d(x,y)$ into a Euclidean space. Corollary 3.5 provides a characterization in the case of finite metric spaces so it is a very good answer. $\endgroup$ Commented Apr 13, 2018 at 15:12
  • $\begingroup$ @PiotrHajlasz I didn't say it's not a good answer, but (1) it would be a much better answer if it did more than quickly quoting a corollary (2) I'm suggesting that it's not "the" extension but "an" extension of Schoenberg's result. $\endgroup$
    – YCor
    Commented Apr 13, 2018 at 15:40
  • 1
    $\begingroup$ @Manor-Mendel Thank your for your answer. I looked at Corollary 3.5 and see some resemblance with the inequality $(*)$. But Corollary 3.5 is more complicated comparing to Schoenberg characterization as instead of complex numbers $c_1,\dots,c_n$ it involves positive semidefinite matrices. Can this Corollary 3.5 reformulated in language of numbers $c_1,\dots,c_n$ (not matrices)? $\endgroup$ Commented Apr 13, 2018 at 16:24
  • 2
    $\begingroup$ @TarasBanakh. You are of course totally right, I was carried away. I deleted the additional incorrect characterization (which is equivalent to () above, as you mentioned). Incidentally, I think () is called "Enflo's generalized roundness", and it holds for any metric space with $L=2$ $\endgroup$ Commented Apr 16, 2018 at 1:28

One such characterization follows from Theorem 3.3 in my paper

Chávez-Domínguez, Javier Alejandro. Lipschitz factorization through subsets of Hilbert space. J. Math. Anal. Appl. 418 (2014), no. 1, 344–356. https://doi.org/10.1016/j.jmaa.2014.04.001 (Also available here).

which more generally characterizes maps between metric spaces which admit a Lipschitz factorization through a subset of a Hilbert space. For the particular case of interest here, the statement is as follows:

For a metric space $X$ and a constant $C \ge 1$, the following are equivalent:

  1. $X$ admits a bi-Lipschitz embedding into a Hilbert space with distortion $C$.
  2. Whenever $x_1,\dotsc,x_m, x'_1,\dotsc,x'_m$ and $y_1,\dotsc,y_n, y'_1,\dotsc,y'_n$ are points in $X$ and $\mu_1,\dotsc,\mu_m, \lambda_1,\dotsc,\lambda_n$ are real numbers satisfying the condition that for all Lipschitz functions $f:X \to \mathbb{R}$ one has $$\sum_{i=1}^n \lambda_i^2|f(y_i)-f(y'_i)|^2 \le \sum_{j=1}^m \mu_j^2|f(x_j)-f(x'_j)|^2,$$ it follows that $$\sum_{i=1}^n \lambda_i^2d(y_i,y'_i)^2 \le C^2 \sum_{j=1}^m \mu_j^2d(x_j,x'_j)^2.$$
  • $\begingroup$ Thank you for you answer. Replacing the real numbers $\lambda_i$, $\mu_j$ by rational numbers, then integer numbers and finally units, one can simplify your condition to the case $\lambda_i=\mu_j=1$ for all $i,j$. $\endgroup$ Commented May 3, 2018 at 3:43
  • $\begingroup$ How to check your condition 2 even on simlpest examples of 4-element metric spaces? $\endgroup$ Commented May 3, 2018 at 4:01
  • $\begingroup$ Lemma 3.2 in the paper gives an alternative characterization of the assumption in condition 2, although it involves matrices which is something you did not want. And even using that characterization, I must say that checking the condition on particular examples seems hard. $\endgroup$ Commented May 7, 2018 at 12:58

Your Answer

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

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