Return to Answer

With the $\ell_\infty$-norm this is true. For example, it is a classic theorem of Fréchet that every $n$-point metric space embeds in $\ell_\infty^{n-1}$. However, for other $\ell_p$-norms this is false. Ball proved that for all $n \geq 3$, there are $n$-point $\ell_1$-spaces that require dimension at least $\binom{n-2}{2}$ to embed in $\ell_1$. Ball also proved that for all $1 < p < 2$ and $n \geq 3$, there are $n$-point $\ell_p$-spaces that require dimension at least $\binom{n-1}{2}$ to embed in $\ell_p$. Of course, it is also well-known that there are $n$-point metric spaces that are not embeddable in $\ell_2$ (no matter what the dimension). For the references (and other related results), see the introduction of my paper The excluded minors for isometric realizability in the plane with Samuel Fiorini, Gwenaël Joret, and Antonios Varvitsiotis.

With the $\ell_\infty$-norm this is true. For example, it is a classic theorem of Fréchet that every $n$-point metric space embeds in $\ell_\infty^{n-1}$. The required embedding $f$ is easy to define. Label the $n$ points as $x_0, x_1, \dots, x_{n-1}$ and let $d(i,j)$ denote the distance between $x_i$ and $x_j$. Let $f(x_0)$ be the zero vector in $\mathbb{R}^{n-1}$ and for all $i,j \in [n-1]$, let $f(x_i)_j=d(i,j)-d(0,j)$. It is easy to check that $\|f(x_i) - f(x_j)\|_\infty=d(i,j)$ for all $i,j \in \{0, \dots, n-1\}$.

However, for other $\ell_p$-norms this is false. Ball proved that for all $n \geq 3$, there are $n$-point $\ell_1$-spaces that require dimension at least $\binom{n-2}{2}$ to embed in $\ell_1$. Ball also proved that for all $1 < p < 2$ and $n \geq 3$, there are $n$-point $\ell_p$-spaces that require dimension at least $\binom{n-1}{2}$ to embed in $\ell_p$. Of course, it is also well-known that there are $n$-point metric spaces that are not embeddable in $\ell_2$ (no matter what the dimension). For the references (and other related results), see the introduction of my paper The excluded minors for isometric realizability in the plane with Samuel Fiorini, Gwenaël Joret, and Antonios Varvitsiotis.

With the $\ell_\infty$-norm this is true. For example, it is a classic theorem of Fréchet that every $n$-point metric space embeds in $\ell_\infty^{n-1}$. However, for other $\ell_p$-norms this is false. Ball proved that for all $n \geq 3$, there are $n$-point $\ell_1$-spaces that require dimension at least $\binom{n-2}{2}$ to embed in $\ell_1$. Ball also proved that for all $1 < p < 2$ and $n \geq 3$, there are $n$-point $\ell_p$-spaces that require dimension at least $\binom{n-1}{2}$ to embed in $\ell_p$. For the references (and other related results), see the introduction of my paper The excluded minors for isometric realizability in the plane with Samuel Fiorini, Gwenaël Joret, and Antonios Varvitsiotis.

With the $\ell_\infty$-norm this is true. For example, it is a classic theorem of Fréchet that every $n$-point metric space embeds in $\ell_\infty^{n-1}$. However, for other $\ell_p$-norms this is false. Ball proved that for all $n \geq 3$, there are $n$-point $\ell_1$-spaces that require dimension at least $\binom{n-2}{2}$ to embed in $\ell_1$. Ball also proved that for all $1 < p < 2$ and $n \geq 3$, there are $n$-point $\ell_p$-spaces that require dimension at least $\binom{n-1}{2}$ to embed in $\ell_p$. Of course, it is also well-known that there are $n$-point metric spaces that are not embeddable in $\ell_2$ (no matter what the dimension). For the references (and other related results), see the introduction of my paper The excluded minors for isometric realizability in the plane with Samuel Fiorini, Gwenaël Joret, and Antonios Varvitsiotis.

With the $\ell_\infty$-norm this is true. For example, it is a classic theorem of Fréchet that every $n$-point metric space embeds in $\ell_\infty^{n-1}$. However, for other $\ell_p$-norms this is false. Ball proved that for all $n \geq 3$, there are $n$-point metric spaces that require dimension at least $\binom{n-2}{2}$ to embed in $\ell_1$. Ball also proved that for all $1 < p < 2$ and $n \geq 3$, there are $n$-point metric spaces that require dimension at least $\binom{n-1}{2}$ to embed in $\ell_p$. For the references (and other related results), see the introduction of my paper The excluded minors for isometric realizability in the plane with Samuel Fiorini, Gwenaël Joret, and Antonios Varvitsiotis.

With the $\ell_\infty$-norm this is true. For example, it is a classic theorem of Fréchet that every $n$-point metric space embeds in $\ell_\infty^{n-1}$. However, for other $\ell_p$-norms this is false. Ball proved that for all $n \geq 3$, there are $n$-point $\ell_1$-spaces that require dimension at least $\binom{n-2}{2}$ to embed in $\ell_1$. Ball also proved that for all $1 < p < 2$ and $n \geq 3$, there are $n$-point $\ell_p$-spaces that require dimension at least $\binom{n-1}{2}$ to embed in $\ell_p$. For the references (and other related results), see the introduction of my paper The excluded minors for isometric realizability in the plane with Samuel Fiorini, Gwenaël Joret, and Antonios Varvitsiotis.