15
$\begingroup$

I am looking for a reference to the bipartite version of the Schoenberg's criterion of embeddability into a Hilbert space. The Schoenberg criterion is formulated as Proposition 8.5(ii) of the book "Geometric Nonlinear Functional Analysis" by Benyamini and Lindenstrauss:

Theorem (Schoenberg). A metric space $(X,d)$ admits an isometric embedding into a Hilbert space if and only if the function $d^2$ is negative definite in the sense that $\sum d^2(x_i,x_j)c_i\bar c_j\le 0$ for all $x_1,\dots,x_n\in X$ and all complex scalars $c_1,\dots,c_n$ satisfying $\sum c_j=0$.

This characterization has a bipartite version:

Theorem (??). A metric space $(X,d)$ admits an isometric embedding into a Hilbert space if and only if $$\sum_{i<j} d^2(x^+_i,x^+_j)+\sum_{i<j} d^2(x^-_i,x^-_j)\le \sum_{i,j=1}^n d^2(x^+_i,x_j^-)$$ for any points $x^+_1,\dots,x^+_n$ and $x^-_1,\dots,x^-_n$ in $X$.

Question. I hope Theorem (??) is known. If yes, could you provide me with a suitable reference?

The reduction of Theorem (??) to Schoenberg's Theorem can be done in six steps:

Lemma. For a pseudometric $d$ on a set $X$ the following conditions are equivalent:

(1) $\sum d^2(x_i,x_j)c_i c_j\le 0$ for any $x_1,\dots,x_n\in X$ and any complex numbers $c_1,\dots,c_n$ with $\sum c_j=0$.

(2) $\sum d^2(x_i,x_j)c_i c_j\le 0$ for any $x_1,\dots,x_n\in X$ and any real numbers $c_1,\dots,c_n$ with $\sum c_j=0$.

(3) $\sum d^2(x_i,x_j)c_i c_j\le 0$ for any $x_1,\dots,x_n\in X$ and any rational numbers $c_1,\dots,c_n$ with $\sum c_j=0$.

(4) $\sum d^2(x_i,x_j)c_i c_j\le 0$ for any $x_1,\dots,x_n\in X$ and any integer numbers $c_1,\dots,c_n$ with $\sum c_j=0$.

(5) $\sum d^2(x_i,x_j)c_i c_j\le 0$ for any $x_1,\dots,x_n\in X$ and any integer numbers $c_1,\dots,c_n\in\{-1,1\}$ with $\sum c_j=0$.

(6) $\sum_{i,j=1}^m d^2(x^+_i,x^+_j)+\sum_{i,j=1}^m d^2(x^-_i,x^-_j)\le \sum_{i,j=1}^m (d^2(x^+_i,x_j^-)+d^2(x^-_i,x^+_j))$ for any points $x^+_1,\dots,x^+_m$ and $x^-_1,\dots,x^-_m$ in $X$.

Proof. The implications $(1)\Rightarrow(2)\Rightarrow(3)\Rightarrow(4)\Rightarrow(5)$ are trivial.

$(2)\Rightarrow(1)$ Take any complex numbers $c_1,\dots,c_n$ with $\sum c_k=0$. Write each complex number $c_k$ as $c_k=a_k+ b_ki$. The equality $\sum c_k=0$ implies $\sum a_k=0=\sum b_k$. Consider the number $s=\sum d^2(x_i,x_j)c_i\bar c_j$ and observe that it is real: $\bar s=\sum d^2(x_i,x_j)\bar c_ic_j=\sum d^2(x_j,x_i)c_j\bar c_i=s$. Then $$s=\sum d^2(x_i,x_j)c_i\bar c_j=\sum d^2(x_ix_j)(a_ia_j+b_ib_j)=\sum d^2(x_ix_j)a_ia_j+\sum d^2(x_i,x_j)b_ib_j\le 0$$by (2).

$(3)\Rightarrow(2)$ can be proved by a standard continuity argument.

$(4)\Rightarrow(3)$ can be proved by multiplying the rational numbers $c_1,\dots,c_n$ by their common denominator.

$(5)\Rightarrow(4)$ can be proved by repeating each point $x_i$ $|c_i|$ times.

$(5)\Leftrightarrow(6)$ The condition (6) is a rewritten condition (5) with $m=n/2$ and points $x^+_1,\dots,x^+_m$ corresponding to $c_i=1$ and $x^-_1,\dots,x^-_m$ to $c_i=-1$.

$\endgroup$
13
  • $\begingroup$ Your first sentence has a double possible meaning. After checking in the book, "Which can be found" refers to Schoenberg's theorem, not to what you call its geometric version. (Is it more geometric?? for me it rather sounds like a bipartite version.) $\endgroup$
    – YCor
    Apr 12, 2018 at 7:56
  • $\begingroup$ @YCor Thank you for the comment. I have made an edit, including the change of terminology to "bipartite". Writing "geometric" I had in mind that the Schoenberg criterion is "analytic". $\endgroup$ Apr 12, 2018 at 8:05
  • $\begingroup$ Possibly there have been people looking at a description of the cone of conditionally negative (semi)definite kernels (i.e., the conditions satisfied by $d^2$ in Schoenberg's criterion). What are its facets? your characterization shows that it's a polyhedral cone and that the facets are among the hyperplanes occurring in it. $\endgroup$
    – YCor
    Apr 12, 2018 at 8:19
  • $\begingroup$ @YCor For infinite $X$ the cone is infinite-dimensional. So your comment about faces concerns only finite $X$? $\endgroup$ Apr 12, 2018 at 8:43
  • $\begingroup$ I remember that Hilbert had something to do with this topic in a basic way. (Sorry, I . don't have my books from the past). $\endgroup$
    – Wlod AA
    Apr 12, 2018 at 8:52

2 Answers 2

6
$\begingroup$

In "Geometry of cuts and metrics" by Deza and Laurent, your inequality is called pure inequality of negative type.

In Section 6.1.1, it is stated that pure inequalities of negative type imply all inequalities of negative type.

In Theorem 6.2.2 they formulate Schoenberg's criterion: a metric space admits an isometric embedding into a Hilbert space if and only it the square of the metric satisfies all the inequalities of negative type.

$\endgroup$
4
$\begingroup$

This nice observation is new to me. In particular, I do not know a reference. Thus this is not an answer, rather a comment which I want to highlight. My comment is that you can supplement your observation with the following one, which could be proven similarly, based on an analogous reduction of positive definite kernels.

Claim: A $[0,\pi]$-valued metric space $(X,d)$ admits an isometric embedding into a round sphere (possibly infinite dimensional) iff for every naturals $m,n$ and elements $x^+_1,\ldots x^+_n,x^-_1,\ldots x^-_m \in X$ we have $$ \frac{1}{2}(n+m)+ \sum_{i<j\leq n} \cos(d(x^+_i,x^+_j)) + \sum_{i<j\leq m} \cos(d(x^-_i,x^-_j)) \geq \sum_{i\leq n,j\leq m} \cos(d(x^+_i,x^-_j)).$$

I suppose also that upon replacing $\cos$ with $\cosh$ you can have a similar iff criterion for embedablility in hyperbolic spaces, but I didn't check the details here.

$\endgroup$
4
  • $\begingroup$ Great development! In fact, I was interested in all this embedding staff because I am looking for nice (isometric, bi-Lipschitz or equi-Holder) embeddings of fractals (those are attractors of IFS on complete metric spaces) into Hilbert spaces. Unfortunately, at the moment I have only conjectures, but not results. $\endgroup$ Apr 13, 2018 at 7:54
  • $\begingroup$ @Uri do you have a reference for this fact? $\endgroup$
    – ABIM
    Jun 2, 2023 at 1:04
  • $\begingroup$ @ABIM No, sorry. The comment above is five years old and I do not remember the details. It was made by my old self, a person I tend to trust, but I might be biased. He says that this "could be proven similarly, based on an analogous reduction of positive definite kernels". Did you check this claim? $\endgroup$
    – Uri Bader
    Jun 2, 2023 at 8:25
  • 1
    $\begingroup$ @UriBader Yes lat night, before going to the land of sleep, I did and it is indeed a simple check (after using an old results from circa 1940s of Sheonberg). So I would say thanks do your old and new selfs :p :) $\endgroup$
    – ABIM
    Jun 2, 2023 at 11:27

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.