Negative Type and Bi-lipschitz Embeddings into Hilbert Space

The theory of embeddings of metric spaces has a long and rich history, with some of the most classical results in this area dating back to Cayley [2] in the nineteenth century. In this paper we will study isometric and bi-lipschitz embeddings of metric spaces through the theory of p-negative type. The concept of p-negative type was originally developed by Schoenberg [12] to study isometric embeddings of powers of metric spaces into Hilbert space. Recently p-negative type has been the topic of much research in areas such as mathematical analysis and theoretical computer science (see [3,4,5,6,7] for a list of some of the applications of p-negative type to the isometric theory of metric spaces). The definition of p-negative type is as follows (note that the definition of strict p-negative type is due to Li and Weston in [7]).

Note that here we use the term semi-metric space to mean a ‘metric’ space except that we drop the requirement that the triangle inequality holds. All results in this paper will hold for semi-metric spaces since they do not require the use of the triangle inequality anywhere in their proofs.

Definition 1.1

Let \((X,d_{X})\) be a semi-metric space and \(0\le p<\infty \). Then X is said to have p-negative type if

for all distinct \(x_{1},\dots ,x_{n}\in X\), \(\xi _{1},\dots ,\xi _{n}\in {{\mathbb {R}}}\) with \(\sum _{i=1}^{n}\xi _{i}=0\) and \(n\ge 2\). Furthermore, X is said to have strict p-negative type if equality holds only for \(\xi _{1}=\dots =\xi _{n}=0\).

Central to the theory of p-negative type and its applications are the two following classical results of Schoenberg [11, 12] (note that the first statement below provides an isometric characterisation of subsets of Hilbert space).

Theorem 1.2

Let \((X,d_{X})\) be a semi-metric space and \(0\le p<\infty \).

1. (1)

   X has p-negative type if and only if \((X,d_{X}^{p/2})\) isometrically embeds in some Hilbert space.

2. (2)

   If \(0\le q<p\) and X has p-negative type then X also has strict q-negative type.

Note that the second statement in the above theorem implies that all of the values of p-negative type that a semi-metric space \((X,d_{X})\) possesses are encoded in the largest value \(s\ge 0\) such that X has s-negative type. Thus one is led to consider the quantity

which is referred to as the supremal p-negative type of X. Note that since all the sums that appear in the definition of p-negative type are finite sums a simple limiting argument shows that if \(\wp _{X}<\infty \) then X also has \(\wp _{X}\)-negative type. Consequently the set of values \(s\ge 0\) such that a semi-metric space \((X,d_{X})\) has s-negative type is always of the form \([0,\wp _{X}]\) or \([0,\infty )\).

More recently, Linial, London and Rabinovich [9] have provided a similar characterisation of those finite metric spaces that admit a bi-lipschitz embedding into some Hilbert space with a given level of distortion. Bi-lipschitz embeddings of metric spaces, and finite metric spaces in particular, have been studied extensively over the last half-century or so. Originally such embeddings were studied from the perspective of geometric analysis and Banach space theory. However, more recently the theory of bi-lipschitz embeddings has been examined from the perspective of combinatorial optimisation and theoretical computer science. This is in part due to Linial, London and Rabinovich [9] who showed that many problems in optimisation could be solved efficiently by considering bi-lipschitz embeddings of certain metric spaces into larger host spaces, such as Hilbert or Banach spaces.

Let us now recall the definition of a bi-lipschitz embedding.

Definition 1.3

Let \((X,d_{X})\) and \((Y,d_{Y})\) be semi-metric spaces and \(1\le C<\infty \).

1. (1)

   A map \(f:X\rightarrow Y\) is said to have distortion at most C if there exists a (scaling constant) \(s>0\) such that

   $$\begin{aligned} sd_{X}(x,y)\le d_{Y}(f(x),f(y))\le sCd_{X}(x,y) \end{aligned}$$

   for all \(x,y\in X\). The smallest such C for which this holds is denoted by \({{\,\textrm{dist}\,}}(f)\) (and if no such C exists we set \({{\,\textrm{dist}\,}}(f)=\infty \)). If \({{\,\textrm{dist}\,}}(f)<\infty \) then we say that f is a bi-lipschitz embedding.

2. (2)

   We denote by \(c_{(Y,d_{Y})}(X,d_{X})\) (or simply by \(c_{Y}(X)\)) the infimum of all constants \(1\le C\le \infty \) such that there exists a map \(f:X\rightarrow Y\) with \({{\,\textrm{dist}\,}}(f)\le C\) (where again we allow the possibility that \(c_{(Y,d_{Y})}(X,d_{X})=\infty \)). When \(Y=\ell ^{2}\), we denote \(c_{Y}(X)\) simply by \(c_{2}(X)\).

Remark 1.4

For our purposes, it is useful to say that a map \(f:(X,d_{X})\rightarrow (Y,d_{Y})\) is an isometry if there exists some \(s>0\) such that \(d_{Y}(f(x),f(y))=sd_{X}(x,y)\) for all \(x,y\in X\). Note that this is slightly more general than the usual definition of isometries in the literature. However, one may note that the defintion of (strict) p-negative type is invariant under this more general definition of isometry too. Moreover, with this definition one has that \({{\,\textrm{dist}\,}}(f)=1\) if and only if f is an isometry. In this way we may think of bi-lipschitz embeddings as a generalisation of isometries.

One of the main problems that one faces when dealing with bi-lipschitz embeddings of semi-metric spaces is how one may embed the given space into the larger space with as little distortion as possible. The most classical result along these lines is perhaps a result of Bourgain [1], which states that any n point metric space admits a bi-lipschitz embedding into \({{\mathbb {R}}}^{n}\) with distortion at most \(O(\log n)\) (the use of the word ‘metric’ is necessary here, since the result fails to hold in general for n point semi-metric spaces.). In [9] Linial, London and Rabinovich provided an algorithmic proof of this result and were able to show that this bound is attained for constant degree expander graphs (and hence cannot be improved in general).

To state one of the main results of [9] we need to introduce a certain class of matrices that will frequently appear throughout this paper. We will use \(M_{n}({{\mathbb {R}}})\) to denote the space of all real-valued \(n\times n\) matrices. Using \(A^{T}\) to denote the usual matrix transpose of A and \(\langle \cdot ,\cdot \rangle \) to denote the standard inner product on \({{\mathbb {R}}}^{n}\), we then set

That is, \(M_{n}^{+}({{\mathbb {R}}})\) is simply the set of all positive semidefinite matrices in \(M_{n}({{\mathbb {R}}})\). We will also use \(\mathbbm {1}\) to denote the vector in \({{\mathbb {R}}}^{m}\) whose entries are all 1, where m may depend on the context. Finally, we put

The result we shall be using from [9] is the following one.

Theorem 1.5

Let \((X,d_{X})=(\{x_{1},\dots ,x_{n}\},d_{X})\) be a finite semi-metric space and \(C\ge 1\). Then X admits a bi-lipschitz embedding into \({{\mathbb {R}}}^{n}\) with distortion at most C if and only if

for all \(Q=(q_{ij})_{i,j=1}^{n}\in \mathcal {O}_{n}({{\mathbb {R}}})\).

Our starting point for constructing an analogue of p-negative type that is compatible with bi-lipschitz embeddings is Theorem 1.5. Indeed, we are now in a position to provide our definition of distorted p-negative type, which is the main object of study in this article.

Definition 1.6

Let \((X,d_{X})\) be a semi-metric space, \(0\le p<\infty \) and \(1\le C<\infty \). Then X is said to have p-negative type with distortion C if

for all distinct \(x_{1},\dots ,x_{n}\in X\), \(Q=(q_{ij})_{i,j=1}^{n}\in \mathcal {O}_{n}({{\mathbb {R}}})\) and \(n\ge 2\). Furthermore, X is said to have strict p-negative type with distortion C if equality holds only for \(Q=0\).

In Sect. 2 we prove that with the above definition of distorted p-negative type many of the basic properties of the usual p-negative type also hold in this setting. In Sect. 3 we are able to show that a finite semi-metric space X has strict p-negative type with distortion C if and only if \(p<\wp _{X}\) or \(C>c_{2}(X,d_{X}^{p/2})\). Finally, in Sect. 4 we provide explicit examples of optimal distortion Euclidean embeddings of powers of the bipartite graph \(K_{m,n}\). In doing so we are also able to provide explicit examples of distorted polygonal equalities for these spaces as well as determine for which values of p and C these spaces have (strict) p-negative type with distortion C.

Our first point of call is to show that when \(C=1\), the definition of (strict) p-negative type with distortion C coincides with usual definition of (strict) p-negative type (see Definition 1.1).

Proposition 2.1

Let \((X,d_{X})\) be a metric space and \(p\ge 0\). Then the following are true.

1. (1)

   X has p-negative type if and only if X has p-negative type with distortion 1.

2. (2)

   X has strict p-negative type if and only if X has strict p-negative type with distortion 1.

Proof

We will prove only the second statement, since the proof of the first statement is more or less identical. First suppose that X has strict p-negative type with distortion 1. By definition, this means that

for all distinct \(x_{1},\dots ,x_{n}\in X\), all nonzero \(Q=(q_{ij})_{i,j=1}^{n}\in \mathcal {O}_{n}({{\mathbb {R}}})\) and \(n\ge 2\). Now, suppose that \(n\ge 2\), \(x_{1},\dots ,x_{n}\in X\) are distinct and that \(\xi _{1},\dots ,\xi _{n}\in {{\mathbb {R}}}\) (not all zero) with \(\sum _{i=1}^{n}\xi _{i}=0\). Setting \(Q=(\xi _{i}\xi _{j})_{i,j=1}^{n}\) it is a simple matter to check that \(Q\ne 0\) and \(Q\in \mathcal {O}_{n}(R)\). Hence, applying the above inequality to this particular choice of Q gives that

which shows that X has strict p-negative type. Conversely, suppose that X has strict p-negative type. Take distinct \(x_{1},\dots ,x_{n}\in X\) and a nonzero \(Q=(q_{ij})_{i,j=1}^{n}\in \mathcal {O}_{n}({{\mathbb {R}}})\) with \({{\,\textrm{rank}\,}}(Q)=r\). Since Q is positive semi-definite with \(Q\mathbbm {1}=0\), we may write it as \(Q=\sum _{k=1}^{r}R_{k}\) where each \(R_{k}\) is positive semi-definite with \({{\,\textrm{rank}\,}}(R_{k})=1\) and \(R_{k}\mathbbm {1}=0\). By basic linear algebra, for each \(1\le k\le r\) we can find \(\xi _{1}^{(k)},\dots ,\xi _{n}^{(k)}\in {{\mathbb {R}}}\) (not all zero) with \(\sum _{i=1}^{n}\xi _{i}^{(k)}=0\) such that \(R_{k}=(\xi _{i}^{(k)}\xi _{j}^{(k)})_{i,j=1}^{n}\). Putting this all togther, we have that

for all \(1\le i,j\le n\). Hence

which shows that X has strict p-negative type with distortion 1. \(\square \)

Next we remark that the bi-lipschitz embedding theorem of Linial, London and Rabinovich [9] can easily be extended to deal with infinite metric spaces also. This is due to the following classical result which states that Hilbertian distortion is finitely determined. A proof of the following proposition can be found in [13], for example.

Proposition 2.2

Let \((X,d_{X})\) be a semi-metric space and \(1\le C<\infty \). Then \((X,d_{X})\) embeds in a Hilbert space with distortion at most C if and only if every finite subset \(Y\subseteq X\) embeds in \(\ell ^{2}\) with distortion at most C.

Combined with Theorem 1.5, this allows us to say the following.

Theorem 2.3

Let \((X,d_{X})\) be a semi-metric space, \(0<p<\infty \) and \(1\le C<\infty \). Then X has p-negative type with distortion C if and only if \((X,d_{X}^{p/2})\) embeds in a Hilbert space with distortion at most C.

It is worth noting that for finite semi-metric spaces the definition of distorted p-negative type simplifies somewhat, since there is no need to vary over all distinct \(x_{1},\dots ,x_{n}\in X\). This is a direct consequence of Theorems 1.5 and 2.3.

Theorem 2.4

Let \((X,d_{X})=(\{x_{1},\dots ,x_{n}\},d_{X})\) be a finite semi-metric space, \(0\le p<\infty \) and \(1\le C<\infty \). Then the following statements are equivalent in pairs.

1. (1)

   X has p-negative type with distortion C.

2. (2)

   \((X,d_{X}^{p/2})\) embeds in \({{\mathbb {R}}}^{n}\) with distortion at most C.

3. (3)

   The inequality

   $$\begin{aligned} \sum _{q_{ij}>0}d_{X}(x_{i},x_{j})^{p}q_{ij}+C^{2}\sum _{q_{ij}<0}d_{X}(x_{i},x_{j})^{p}q_{ij}\le 0 \end{aligned}$$

   holds for all \(Q=(q_{ij})_{i,j=1}^{n}\in \mathcal {O}_{n}({{\mathbb {R}}})\).

An extremely useful corollary of the above theorem is the following formula for the Euclidean distortion of a finite semi-metric space (this was first observed by Linial, London and Rabinovich in [8]).

Corollary 2.5

Let \((X,d_{X})=(\{x_{1},\dots ,x_{n}\},d_{X})\) be a semi-metric space and \(0<p<\infty \). Then

We now show that distorted p-negative type satisfies a simple nesting result.

Proposition 2.6

Let \((X,d_{X})\) be a semi-metric space, \(0<p<\infty \) and \(1\le C_{1}<C_{2}<\infty \). If X has p-negative type with distortion \(C_{1}\) then X has strict p-negative type with distortion \(C_{2}\).

Proof

Take \(n\ge 2\), distinct \(x_{1},\dots ,x_{n}\in X\) and \(Q=(q_{ij})_{i,j=1}^{n}\in \mathcal {O}_{n}({{\mathbb {R}}})\) with \(Q\ne 0\). Now, since \(Q\in M_{n}^{+}({{\mathbb {R}}})\), note that \(\langle Q\xi ,\xi \rangle =0\) if and only if \(Q\xi =0\). One direction is obvious. For the other, use the existence of the square root \(Q^{1/2}\). Then \(\langle Q\xi ,\xi \rangle =0\) implies that \(\Vert Q^{1/2}\xi \Vert _{2}^{2}=\langle Q\xi ,\xi \rangle =0\) and so \(Q^{1/2}\xi =0\), and thus \(Q\xi =Q^{1/2}(Q^{1/2}\xi )=0\). Also, by linearity, since \(Q\ne 0\) there exists some \(1\le k\le n\) such that \(Qe_{k}\ne 0\), and so \(\langle Qe_{k},e_{k}\rangle >0\). Since \(Q\mathbbm {1}=0\) this means there exists some \(i\ne j\) such that \(q_{ij}<0\) and since \(i\ne j\) we also have that \(q_{ij}d_{X}(x_{i},x_{j})^{p}<0\). Hence

But then

which shows that X has strict p-negative type with distortion \(C_{2}\). \(\square \)

We may also bootstrap the nesting property from Theorem 1.2 to obtain the following analogous nesting result for distorted p-negative type.

Theorem 2.7

Let \((X,d_{X})\) be a semi-metric space, \(0<q<p<\infty \) and \(1\le C<\infty \). If X has p-negative type with distortion C then X has strict q-negative type with distortion \(C^{q/p}\).

Proof

Since X has p-negative type with distortion C, Theorem 2.3 gives that \((X,d_{X}^{p/2})\) embeds into some Hilbert space \((H,\Vert \cdot \Vert _{2})\) with distortion at most C. That is, there exists a map \(\phi :X\rightarrow H\) such that

for all \(x,y\in X\). Take \(n\ge 2\), distinct \(x_{1},\dots ,x_{n}\in X\) and \(Q=(q_{ij})_{i,j=1}^{n}\in \mathcal {O}_{n}({{\mathbb {R}}})\), with \(Q\ne 0\). Since \(0<2q/p<2\), we have that H has strict 2q/p-negative type (see Theorem 1.2), and so

Putting this all together, we have that

and so we are done. \(\square \)

A very large part of the recent research effort into p-negative type has revolved around the notions of strict p-negative type and polygonal equalities (see for example results in [3,4,5,6,7, 10]). In this section, we derive some basic results pertaining to these concepts in the distorted setting, including proving the existence of certain non-trivial polygonal equalities.

Let us start by defining what we mean by a polygonal equality here. In the distorted setting, Theorem 2.3 prompts us to define our polygonal equalities slightly differently. When we talk about polygonal equalities from now on, we will use the following (new) definition.

Definition 3.1

Let \((X,d_{X})\) be a semi-metric space, \(0\le p<\infty \) and \(1\le C<\infty \). A p-polygonal equality with distortion C (or a C-distorted p-polygonal equality) in X is an equality of the form

for some distinct \(x_{1},\dots ,x_{n}\in X\), \(Q=(q_{ij})_{i,j=1}^{n}\in \mathcal {O}_{n}({{\mathbb {R}}})\) and \(n\ge 2\). Such an equality is said to be non-trivial if \(Q\ne 0\). Also, the rank of such a polygonal equality is defined to be the rank of the matrix Q.

It follows immediately from the above definition and the definition of strict p-negative type with distortion (Definition 1.6) that a semi-metric space X has strict p-negative type with distortion C if and only if it has p-negative type with distortion C and X admits no non-trivial p-polygonal equalities with distortion C.

At this point, we must stop and justify our use of the terminology ‘polygonal equality’. Indeed the above definition in its current form looks nothing like the usual definition of polygonal equalities as they have appeared in the literature at this point in time. We now show the connection between our definition and the usual one.

Let \((X,d_{X})\) be a semi-metric space, \(x_{1},\dots ,x_{n}\in X\) be distinct, \(p\ge 0\) and \(Q=(q_{ij})_{i,j=1}^{n}\in \mathcal {O}_{n}({{\mathbb {R}}})\). By our definition a p-polygonal equality with distortion 1 is an equality of the form

Now, as in the proof of Proposition 2.1, we have that that \({{\,\textrm{rank}\,}}(Q)\le 1\) if and only if there exist \(\xi _{1},\dots ,\xi _{n}\in {{\mathbb {R}}}\) with \(\sum _{i=1}^{n}\xi _{i}=0\) such that \(q_{ij}=\xi _{i}\xi _{j}\), for all \(1\le i,j\le n\). So, in this case we actually have that

Readers familiar with the theory of p-negative type will recognise this as one of the more standard definitions of a polygonal equality, from say [6]. To summarise, our definition of rank 1 polygonal equalities with distortion 1 is equivalent to the standard definition of a polygonal equality from the isometric theory of p-negative type.

An invaluable tool in the study of strict p-negative type and polygonal equalities in the isometric setting is the p-negative type gap function. This was originally defined by Doust and Weston in [3] and studied extensively in [3, 4, 7, 14, 15].

Here we introduce an analogue of the p-negative type gap in the distorted setting. For what follows, if \(n\ge 1\) and \(A=(a_{ij})_{i,j=1}^{n}\in M_{n}({{\mathbb {R}}})\), we will use the notation

Definition 3.2

Let \((X,d_{X})=(\{x_{1},\dots ,x_{n}\},d_{X})\) be a finite semi-metric space. The distorted type gap function for X is defined to be the function \(\Delta _{X}:[0,\infty )\times [1,\infty )\rightarrow {{\mathbb {R}}}\) given by

for all \(0\le p<\infty \) and \(1\le C<\infty \).

First we remark that \(\Delta _{X}(p,C)\) is always finite. To see this let \(\mathcal {Q}\) denote the set of all \(Q\in \mathcal {O}_{n}({{\mathbb {R}}})\) with \({{\,\textrm{pos}\,}}(Q)=1\) and topologize \(\mathcal {Q}\) with the pointwise topology (i.e. \(Q_{k}\rightarrow Q\) if and only if \(Q_{k}\) converges to Q entrywise). Note that since \(M_{n}({{\mathbb {R}}})\) is finite-dimensional this coincides with the restriction of the unique norm topology on \(M_{n}({{\mathbb {R}}})\) to \(\mathcal {Q}\). It is a simple matter to check that with this topology \(\mathcal {Q}\) is compact (it is a closed and bounded subset of \(M_{n}({{\mathbb {R}}})\)). Also, define \(f:[0,\infty )\times [1,\infty )\times \mathcal {Q}\rightarrow {{\mathbb {R}}}\) by

Then f is continuous and also

So, since f is continuous and \(\mathcal {Q}\) is compact it follows that \(\Delta _{X}(p,C)\) is always finite and that the above infimum is always attained for some \(Q\in \mathcal {Q}\).

The fact that \(\Delta _{X}(p,C)\) is the infimum over a compact set also implies that it must be continuous. Here we will use the following result from elementary analysis. The proof of this result is left as an exercise for the reader.

Proposition 3.3

Let \((Y,\tau _{Y})\) be a topological space and let \((Z,\tau _{Z})\) be a compact topological space. Suppose that \(f:Y\times Z\rightarrow {{\mathbb {R}}}\) is continuous (with respect to the product topology on \(Y\times Z\)) and define \(g:Y\rightarrow {{\mathbb {R}}}\) by

for all \(y\in Y\). Then g is continuous.

Corollary 3.4

Let \((X,d_{X})=(\{x_{1},\dots ,x_{n}\},d_{X})\) be a finite semi-metric space. Then \(\Delta _{X}:[0,\infty )\times [1,\infty )\rightarrow {{\mathbb {R}}}\) is continuous (with respect to the product topology on \([0,\infty )\times [1,\infty )\).

It follows immediately from the above definition (and the fact that one may rescale appropriately) that if \((X,d_{X})=(\{x_{1},\dots ,x_{n}\},d_{X})\) is a finite semi-metric space, \(0\le p<\infty \) and \(1\le C<\infty \) then X has p-negative type with distortion C if and only if \(\Delta _{X}(p,C)\ge 0\). More importantly however is the following refinement of this property when dealing with strict distorted p-negative type. That is, \(\Delta _{X}\) has the following property.

Theorem 3.5

Let \((X,d_{X})=(\{x_{1},\dots ,x_{n}\},d_{X})\) be a finite semi-metric space, \(0\le p<\infty \) and \(1\le C<\infty \). Then X has strict p-negative type with distortion C if and only if \(\Delta _{X}(p,C)>0\).

Proof

First suppose that \(\Delta _{X}(p,C)>0\). So, take \(Q=(q_{ij})_{i,j=1}^{n}\in \mathcal {O}_{n}({{\mathbb {R}}})\) with \(Q\ne 0\). Then, since \({{\,\textrm{pos}\,}}(Q)\ne 0\) one may define \(R=(r_{ij})_{i,j=1}^{n}\) by \(R={{\,\textrm{pos}\,}}(Q)^{-1}Q\). Of course, one then has that \(R\in \mathcal {O}_{n}({{\mathbb {R}}})\) with \({{\,\textrm{pos}\,}}(R)={{\,\textrm{pos}\,}}(Q){{\,\textrm{pos}\,}}(Q)^{-1}=1\). Hence

Hence, after dividing both sides by \(-{{\,\textrm{pos}\,}}(Q)^{-1}\) one finds that

which shows that X has strict p-negative type with distortion C. Conversely, suppose that X has strict p-negative type with distortion C. Let us keep the notation from below Definition 3.2 so that

Since f is continuous and \(\mathcal {Q}\) is compact this infimum must be attained. That is, there exists some \(Q_{0}\in \mathcal {Q}\) (that depends on both p and C) such that

But since X has strict p-negative type with distortion C one has that \(f(p,C,Q_{0})>0\) and hence by the above equation we conclude that \(\Delta _{X}(p,C)>0\) as required. \(\square \)

Combining this with Corollary 3.4 gives the following result pertaining to strict distorted p-negative type.

Corollary 3.6

Let \((X,d_{X})\) be a finite semi-metric space, \(0\le p<\infty \) and \(1\le C<\infty \). Suppose that X has strict p-negative type with distortion C. Then there exists some \(\zeta >0\) (that depends on both p and C) such that X has strict q-negative type with distortion K for all \(q\in [p,p+\zeta ]\) and \(K\in [\max (C-\zeta ,1),C]\).

Thus we are now able to obtain a generalisation of the fact that all finite semi-metric spaces admit a non-trivial non-distorted \(\wp _{X}\)-polygonal equality (recall that \(\wp _{X}\) is used to denote the supremal p-negative type of X).

Corollary 3.7

Let \((X,d_{X})\) be a finite semi-metric space and \(p\ge \wp _{X}\). Then there exists a non-trivial \(c_{2}(X,d_{X}^{p/2})\)-distorted p-polygonal equality in X.

Proof

For ease of notation, let us denote \(c_{2}(X,d_{X}^{p/2})\) simply by \(c_{2}(X^{p/2})\). By Theorem 2.3 note that X has p-negative type with distortion \(c_{2}(X^{p/2})\), for all \(p\ge 0\). In particular this means that \(\Delta _{X}(p,c_{2}(X^{p/2}))\ge 0\), for all \(p\ge 0\). So, take \(p\ge \wp _{X}\) and let us assume for a contradiction that \(\Delta _{X}(p,c_{2}(X^{p/2}))>0\). Then by Theorem 3.5 this means that X has strict p-negative type with distortion \(c_{2}(X^{p/2})\) and hence by Corollary 3.6 there exists some \(\zeta >0\) such that X also has strict \((p+\zeta )\)-negative type with distortion \(c_{2}(X^{p/2})\). By Theorem 2.3 this means that \((X,d_{X}^{(p+\zeta )/2})\) embeds in \(\ell ^{2}\) with distortion at most \(c_{2}(X^{p/2})\) and hence \(c_{2}(X^{(p+\zeta )/2})\le c_{2}(X^{p/2})\). But this is impossible since the function \(r\mapsto c_{2}(X^{r/2})\) is strictly increasing for \(r\ge \wp _{X}\) (see Theorem 2.7). Hence it must be the case that \(\Delta _{X}(p,c_{2}(X^{p/2}))=0\).

Now, arguing as in the proof of Theorem 3.5 (and keeping the notation from that proof) there must exist some \(Q_{0}\in \mathcal {Q}\) such that

But this is just another way of saying that \(Q_{0}\) is a \(c_{2}(X^{p/2})\)-distorted p-polygonal equality in X. Also, since \(Q_{0}\in \mathcal {Q}\) we have that \({{\,\textrm{pos}\,}}(Q_{0})=1\) and hence \(Q_{0}\ne 0\). Hence \(Q_{0}\) is a non-trivial \(c_{2}(X^{p/2})\)-distorted p-polygonal equality in X and so we are done. \(\square \)

The above corollary enables us to classify those p and C for which a finite semi-metric space X has strict p-negative type with distortion C.

Corollary 3.8

Let \((X,d_{X})\) be a finite semi-metric space, \(0\le p<\infty \) and \(C\ge 1\). Then X has strict p-negative type with distortion C if and only if \(p<\wp _{X}\) or \(C>c_{2}(X,d_{X}^{p/2})\).

Proof

First suppose that \(p<\wp _{X}\). By the definition of \(\wp _{X}\) we have that X has \(\wp _{X}\)-negative type with distortion 1 and hence by Theorem 2.7X also has strict p-negative type with distortion 1. But then by Proposition 2.6 we also have that X has strict p-negative type with distortion C. Now, suppose instead that \(C>c_{2}(X,d_{X}^{p/2})\). Then Theorem 2.3 gives that X has p-negative type with distortion \(c_{2}(X,d_{X}^{p/2})\) and so Proposition 2.6 again shows that X has strict p-negative type with distortion C.

Conversely, suppose that X has strict p-negative type with distortion C and that \(p\ge \wp _{X}\). Then Theorem 2.3 implies that \(C\ge c_{2}(X,d_{X}^{p/2})\). But by Corollary 3.7 we know that X has nonstrict p-negative type with distortion \(c_{2}(X,d_{X}^{p/2})\) and so it must be the case that \(C>c_{2}(X,d_{X}^{p/2})\). \(\square \)

In this section we provide examples of semi-metric spaces and their values of (strict) distorted p-negative type, as well as some of their non-trivial polygonal equalities.

Throughout this section we will use the following standard notation when computing the distortion of a given embedding.

Definition 4.1

Let \((X,d_{X})\) and \((Y,d_{Y})\) be semi-metric spaces, and suppose that \(f:X\rightarrow Y\).

1. (1)

   The contraction of f is defined to be

   $$\begin{aligned} {{\,\textrm{contraction}\,}}(f)=\sup _{\begin{array}{c} x,y\in X \\ x\ne y \end{array}}\frac{d_{X}(x,y)}{d_{Y}(f(x),f(y))}. \end{aligned}$$
2. (2)

   The expansion of f is defined to be

   $$\begin{aligned} {{\,\textrm{expansion}\,}}(f)=\sup _{\begin{array}{c} x,y\in X \\ x\ne y \end{array}}\frac{d_{Y}(f(x),f(y))}{d_{X}(x,y)}. \end{aligned}$$

It is a simple matter to check that using this notation one has that if \((X,d_{X})\) and \((Y,d_{Y})\) are semi-metric spaces and \(f:X\rightarrow Y\) is a bi-lipschitz embedding then the distortion of f is given by

The spaces that we will study here are the bipartite graphs \(K_{m,n}\). When we say let \((X,d_{X})\) be the bipartite graph \(K_{m,n}\) we mean that X is the space \(X=\{u_{1},\dots ,u_{m},v_{1},\dots ,v_{n}\}\) with metric \(d_{X}\) defined by \(d_{X}(u_{i},u_{j})=d_{X}(v_{k},v_{l})=2\), for all \(1\le i,j\le m\) and \(1\le k,l\le n\) with \(i\ne j\) and \(k\ne l\), and also \(d_{X}(u_{i},v_{j})=1\) for all \(1\le i\le m\) and \(1\le j\le n\).

To properly describe the optimal embeddings of powers of \(K_{m,n}\) into Hilbert space we first need to understand how the complete graph \(K_{n}\) can be isometrically embedded into Hilbert space. For what follows when we say let \((X,d_{X})\) be the complete graph \(K_{n}\) we mean that \(X=\{u_{1},\dots ,u_{n}\}\) with metric \(d_{X}\) such that \(d_{X}(u_{i},u_{j})=1\), for all \(1\le i,j\le n\) with \(i\ne j\).

It is a simple matter to construct an isometric embedding of \(K_{n}\) into \({{\mathbb {R}}}^{n}\). Indeed, one may simply take \(u_{i}\mapsto e_{i}/\sqrt{2}\) for all \(1\le i\le n\) where \(e_{1},\dots ,e_{n}\) are the standard basis vectors. However, since \(K_{n}\) is an n point metric space it must therefore be possible to isometrically embed \(K_{n}\) into \({{\mathbb {R}}}^{n-1}\). In fact, it can also be shown that \(K_{n}\) cannot be isometrically embedded into \({{\mathbb {R}}}^{r}\) for any \(r<n-1\). Indeed, since \(K_{n}\) is an ultrametric space it has strict 2-negative type and hence it must embed isometrically into \({{\mathbb {R}}}^{n-1}\) as an affinely independent set. For such results see [5].

While the problem of writing an explicit formula for an isometric embedding of \(K_{n}\) into \({{\mathbb {R}}}^{n-1}\) is not a conceptually challenging one it is rather tedious. Let

and

where here \(\mathbbm {1}\) denotes the vector in \({{\mathbb {R}}}^{n-1}\) all of whose entries are 1. Then define \(\phi :K_{n}\rightarrow {{\mathbb {R}}}^{n-1}\) by \(\phi (u_{i})=e_{i}/\sqrt{2}-C_{n}\) for all \(1\le i\le n-1\) and \(\phi (u_{n})=c_{n}\mathbbm {1}-C_{n}\). It is a simple yet tedious task to check that \(\phi \) is an isometric embedding of \(K_{n}\) into \({{\mathbb {R}}}^{n-1}\). It is also simple to check that \(\Vert \phi (u_{i})\Vert _{2}=(1-1/n)^{1/2}/2^{1/2}\) for all \(1\le i\le n\). We will refer to this particular embedding as the standard embedding of \(K_{n}\) into \({{\mathbb {R}}}^{n-1}\).

We now move on to the problem of desribing optimal embeddings of powers of \(K_{m,n}\). In proving the optimality of our embeddings we will require a matrix Q that will serve as a distorted polygonal equality for \(K_{m,n}\).

Lemma 4.2

Define \(Q=(q_{ij})_{i,j=1}^{m+n}\in M_{m+n}({{\mathbb {R}}})\) by

Then \(Q\in \mathcal {O}_{m+n}({{\mathbb {R}}})\).

Proof

Define \(\xi _{1},\dots ,\xi _{m+n}\in {{\mathbb {R}}}\) by

Then \(\sum _{i=1}^{m+n}\xi _{i}=0\) and \(Q=(\xi _{i}\xi _{j})_{i,j=1}^{m+n}\). As in the proof of Proposition 2.1, it now follows that \(Q\in \mathcal {O}_{m+n}({{\mathbb {R}}})\). \(\square \)

In what follows if \(r\ge 1\) then we shall use \(0_{r}\) to denote the zero vector in \({{\mathbb {R}}}^{r}\) (i.e. the vector in \({{\mathbb {R}}}^{r}\) all of whose coordinates are zero). Also, for ease of notation we shall set

Theorem 4.3

Let \((X,d_{X})\) be the bipartite graph \(K_{m,n}\), where \(m,n\ge 1\) (not both 1) and let \(\wp =\wp _{m,n}\). Also, let \(x_{1},\dots ,x_{m}\in {{\mathbb {R}}}^{m-1}\) be the image of the standard embedding of \(K_{m}\) into \({{\mathbb {R}}}^{m-1}\) and let \(y_{1},\dots ,y_{n}\in {{\mathbb {R}}}^{n-1}\) be the image of the standard embedding of \(K_{n}\) into \({{\mathbb {R}}}^{n-1}\) (see the comments above Lemma 4.2). Then for \(p\ge \wp \) the map \(\phi :(X,d_{X}^{p/2})\rightarrow {{\mathbb {R}}}^{m-1}\oplus {{\mathbb {R}}}^{n-1}={{\mathbb {R}}}^{m+n-2}\) defined by

has \({{\,\textrm{dist}\,}}(\phi )=c_{2}(X,d_{X}^{p/2})\). Consequently \(\wp _{X}=\wp \) and

Proof

It follows immediately from the definition of \(\phi \) that

for all \(1\le i\ne j\le m\), \(1\le k\ne l\le n\). Now take \(1\le i\le m\) and \(1\le j\le n\). By what was said above about the standard embeddings of \(K_{r}\) into \({{\mathbb {R}}}^{r-1}\) we have that \(\Vert \phi (u_{i})\Vert _{2}=(1-1/m)^{1/2}/2^{1/2}\) and \(\Vert \phi (v_{j})\Vert _{2}=(1-1/n)^{1/2}/2^{1/2}\). Also, since \(\phi (u_{i})\) and \(\phi (v_{j})\) are clearly orthogonal we have that

Hence, since we are we are thinking of \(\phi \) as a map \(\phi :(X,d_{X}^{p/2})\rightarrow {{\mathbb {R}}}^{m+n-2}\), one has that

Since \(p\ge \wp =\wp _{m,n}\) it is readily checked that

Similarly, since \(p\ge \wp =\wp _{m,n}\) the contraction of \(\phi \) is given by

Hence the distortion of \(\phi :(X,d_{X}^{p/2})\rightarrow {{\mathbb {R}}}^{m+n-2}\) is

For the lower bound, let \(Q=(q_{ij})_{i,j=1}^{m+n}\) be the matrix defined in Lemma 4.2, which we know is in \(\mathcal {O}_{m+n}({{\mathbb {R}}})\). Then taking \(z_{1}=u_{1},\dots ,z_{m}=u_{m},z_{m+1}=v_{1},\dots ,z_{m+n}=v_{n}\), Theorem 2.5 gives that

Thus for \(p\ge \wp \) one has that

Note in particular that \(c_{2}(X,d_{X}^{\wp /2})=1\). The fact that \(c_{2}(X,d_{X}^{p/2})=1\) for all \(0\le p<\wp \) now follows from Theorem 2.7. \(\square \)

Corollary 4.4

Let \((X,d_{X})\) be the bipartite graph \(K_{m,n}\), where \(m,n\ge 1\) (not both 1), \(\wp =\wp _{m,n}\), \(0\le p<\infty \) and \(1\le C<\infty \). Then X has p-negative type with distortion C if and only if \(0\le p\le \wp \), or \(p>\wp \) and

Proof

This is a direct consequence of the above theorem and Theorem 2.3. \(\square \)

Corollary 4.5

Let \((X,d_{X})\) be the bipartite graph \(K_{m,n}\), where \(m,n\ge 1\) (not both 1), \(\wp =\wp _{m,n}\), \(0\le p<\infty \) and \(1\le C<\infty \). Then X has strict p-negative type with distortion C if and only if \(0\le p<\wp \), or \(p\ge \wp \) and

Proof

This is a direct consequence of Theorem 4.3 and Corollary 3.8. \(\square \)