Let $d:[n]^2\to \mathbb R$ be a metric, and $k$ a non-negative integer. Consider the space of functions $$F:=\{f:[n]\to\mathbb R^k \text{ such that } d(x, x') = \|f(x)-f(x')\|\}$$
- Given $n$, what is the minimal $k$ such that $F$ is always nonempty?
Clearly $k \le n(n-1)/2$ by symmetry and the condition $d(x,x)=0$. However, I can't figure out how the triangle inequality affects dimensionality here.
- By definition, $F$ is clearly invariant under the action of the orthogonal group of dimension $k$ with translations. Does there exist $n, d$ such that this is not the only invariant action?
For $n=3$, triangle similarity (three equivalent sides) shows there cannot exist such a $d$ since here, $k=2$. However, I cannot think of how to generalize this approach.
For $n=2$ and $3$, the minimal $k$ is $1$ and $2$, respectively.
However, assuming that $\|\cdot\|$ is the standard norm on $\Bbb R^k$, $F$ can be empty for each $n > 3$. Indeed, put $$d(i,j)=\begin{cases}0, &\mbox{ if } i=j, \\ 2, &\mbox{ if } (i,j)=(1,2)\mbox{ or }(i,j)=(2,1), \\ 1 & \mbox{ otherwise}.\end{cases}$$ Since for each $i,j,k\in [n]$ we have $d(i,i)=0$ and $d(i,j)=d(j,i)\le 2\le d(i,k)+d(k,j)$, the function $d$ is a metric on the set $[n]$. Suppose to the contrary that $f : [n] \to \Bbb R^k$ is an isometric embedding. Then both $f(3)$ and $f(4)$ are midpoints of a segment $[f(1),f(2)]$, so $d(f(3), f(4)) = 0$, a contradiction. Hence, the set $F$ corresponding to the metric $d$ is empty.
For $n=2$, the only invariant action is $\Bbb R$ acting as translations, for $n=3$, the only invariant action is $\Bbb R^2 \times O(2)$ being translations and rotations, and all actions are trivially invariant for $n=1, n>3$.