Vtyjkyuk

Let $d(cdot, cdot)$ be a distance metric on some space (not necessarily Euclidean) $mathcalX$. Is it true that
$$
K(x, y) := exp(-d(x, y))
$$
always defines a positive definite kernel? If not, are there certain conditions on $d(cdot, cdot)$ under which the result is true?

Remark: in this subject, "positive definite" typically means "positive semidefinite" (Wikipedia) and I treat it as such. One does not expect the matrix $exp(-d(x_i, x_j))$ to be strictly positive definite since some $x_i$ could be repeated.

Counterexample

Consider the 3-dimensional space $ell_infty^3$, i.e., the norm is $|(x, y, z)| = max(|x|, |y|, |z|)$. Let $mathcal X$ be the five-point subset of $ell_infty^3$, the coordinates of each point being a row of the matrix
$$
A = frac110 beginpmatrix
0 & 0 & 1 \ 0 & 0 & -1 \ 1 & 1 & 0 \ 1 & -1 & 0 \ -1 & 1 & 0
endpmatrix
$$
The distance matrix of this space is
$$
D = frac110 beginpmatrix 0 & 2 & 1 & 1 & 1 \ 2 & 0 & 1 & 1 & 1 \ 1 & 1 & 0 & 2 & 2 \ 1 & 1 & 2 & 0 & 2 \ 1 & 1 & 2 & 2 & 0 endpmatrix
$$
Applying the function $tmapsto exp(-t)$ to each element of $D$, we get a matrix $B$ which is not positive semidefinite. Specifically, the vector $v = (3, 3, -2, -2, -2)$ satisfies
$$
vBv^T = 30 + 42e^-1/5 - 72e^-1/10 < 0
$$

Sufficient condition

The kernel $exp(-lambda d)$ is positive semidefinite for all $lambda>0$ if and only if $d$ is a a kernel of conditionally negative type, see Transforming a distance function to a kernel. In the article linked there, Schoenberg proved that a metric space admits an isometric embedding into a Hilbert space if and only if $d^2$ is a kernel of conditionally negative type.

Conclusion: if $(X, d)$ is a metric space such that its "snowflake" $(X, d^1/2)$ admits an isometric embedding into a Hilbert space, then $exp(-d)$ is a positive semidefinite kernel. Examples of such spaces are: Hilbert space itself, $L^1$, and of course any subsets of those.

This motivated my counterexample above: $ell_infty^3$ is one of the simplest spaces that do not embed into $L^1$.

A contemporary source on this subject is Naor's ICM talk on $L^1$ embeddings (its main subject is the Heisenberg group, but the introduction gives an overview of the situation).