13
$\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$
  • $\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 '18 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$ – Taras Banakh Apr 12 '18 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 '18 at 8:19
  • $\begingroup$ @YCor For infinite $X$ the cone is infinite-dimensional. So your comment about faces concerns only finite $X$? $\endgroup$ – Taras Banakh Apr 12 '18 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 '18 at 8:52
3
$\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$
  • $\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$ – Taras Banakh Apr 13 '18 at 7:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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