Negative Type and Bi-lipschitz Embeddings into Hilbert Space

The usual theory of negative type (and p-negative type) is heavily dependent on an embedding result of Schoenberg, which states that a metric space isometrically embeds in some Hilbert space if and only if it has 2-negative type. A generalisation of this embedding result to the setting of bi-lipschitz embeddings was given by Linial, London and Rabinovich. In this article we use this newer embedding result to define the concept of distorted p-negative type and extend much of the known theory of p-negative type to the setting of bi-lipschitz embeddings. In particular we show that a metric space \((X,d_{X})\) $(X,d_X)$ has p-negative type with distortion C ( \(0\le p<\infty \) $0\le p<\infty$ , \(1\le C<\infty \) $1\le C<\infty$ ) if and only if \((X,d_{X}^{p/2})\) $(X,d_X^{p/2})$ admits a bi-lipschitz embedding into some Hilbert space with distortion at most C. Analogues of strict p-negative type and polygonal equalities in this new setting are given and systematically studied. Finally, we provide explicit examples of these concepts in the bi-lipschitz setting for the bipartite graphs \(K_{m,n}\) $K_{m,n}$ .