Can a collection of points be recovered from its multiset of distances?

Consider $n$ distinct points $x_1,\dots,x_n$ on $\mathbb{R}$. Associated to these points is the multiset of all distances $d(x_i,x_j)$ between two points. Suppose one is only handed this multiset (you do not know the corresponding indices). Does this allow one to uniquely recover the original points up to reflection and translation?

Solution 1:

This is a really nice question!

Counterexample for $n=6$

The sets $$\{0,1,4,5,11,13\}\\\{0,1,2,6,10,13\}$$ are affinely inequivalent, but the multiset of differences is in both cases $$1^2\cdot 2\cdot 3\cdot 4^2 \cdot 5 \cdot 6\cdot 7 \cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13.$$

Counterexamples for $n \geq 7$ According to Lemma 2.1 in the first linked article in the answer of Steve Kass, for all $n\geq 6$, a counterexample is given by $$X\cup \{n+1,n+3\}\quad\text{and}\quad X\cup\{2,n+1\}$$ where $X = \{5,6,7,\ldots,n-1,n-2\} \cup \{0,1,n,n+5\}$.

Uniqueness for $n\leq 5$

For $n\in\{1,2\}$, the uniqueness is clear.

Let $X = \{x_1,x_2,\ldots,x_n\}$ be a point set. We assume $x_1\leq x_2\leq\ldots \leq x_n$. Up to affine equivalence, we may assume $x_1 = 0$. We denote the distance of two points $x,y$ by $\delta(x,y) = \left|x-y\right|$ and furthermore define the abbreviation $\delta_{i,j} = \delta(x_i,x_j)$. In the multiset of distances, let $a \geq b\geq c\geq d$ be the largest elements. It is clear that $a = \delta_{1,n}$ and thus $x_n = a$. Up to affine equivalence, we may assume $b = \delta_{1,n-1}$ (the other possibility is $\delta_{2,n}$), so $x_{n-1} = b$. This shows the uniqueness for $n = 3$.

For $n=4$, $\{\delta_{1,2},\delta_{2,n}\} = \{c,x_4-c\}$. This distinguishes the last remaining distance $\delta_{2,3}$, which in turn fixes $x_2$.

It remains to consider the case $n=5$.

First we see that if one further point $x\in\{x_2,x_3\}$ is fixed, the set $X$ is completely determined: Let $y$ be the missing point. Among the four remaining distances $\delta(x_1,y)$, $\delta(x,y)$, $\delta(y,x_4)$, $\delta(y,x_5)$, the maximum $d_m$ is contained in the set $\{\delta(x_1,y),\delta(x_5,y)\} = \{d_m, x_5-d_m\}$. So we also know the set $\{\delta(x,y),\delta(y,x_4)\}$. Because of $x,y\in(x_0,x_4)$, $\delta(y,x_4)$ is the larger of those two distances, which fixes the point $y$.

By the choice of $c$, we have $c = \delta_{1,3}$ (Case A) or $c = \delta_{2,n}$ (Case B). If the multiset of distances admits only one of those two cases, then by the above reasoning, $X$ is uniquely determined. So we have to see that if both cases are possible, then the point sets are necessarily identical.

Case A) If $c = \delta_{1,3}$, then $x_3 = c$, and $d\in\{\delta_{1,2},\delta_{2,5}\}$.

Case A1) $d = \delta_{1,2}$. Now $X = \{0,d,c,b,a\}$, and the $10$ distances are $$\delta_{1,2} = d,\quad \delta_{1,3} = c,\quad \delta_{1,4}= b,\quad \delta_{1,5} = a,\\ \delta_{2,3} = c-d,\quad \delta_{2,4} = b-d,\quad \delta_{2,5} = a-d,\\ \delta_{3,4} = b-c,\quad \delta_{3,5} = a-c, \\\delta_{4,5} = a-b$$

Case A2) $d = \delta_{2,5}$. Now $X = \{0,a-d,c,b,a\}$, and the $10$ distances are $$\delta_{1,2} = a-d,\quad \delta_{1,3} = c,\quad \delta_{1,4}= b,\quad \delta_{1,5} = a,\\ \delta_{2,3} = -a+c+d,\quad \delta_{2,4} = -a+b+d,\quad \delta_{2,5} = d,\\ \delta_{3,4} = b-c,\quad \delta_{3,5} = a-c, \\\delta_{4,5} = a-b$$

Case B) If $c = \delta_{2,5}$, then $x_2 = a-c$, and $d\in\{\delta_{1,3},\delta_{3,5},\delta_{2,4}\}$.

Case B1) $d = \delta_{1,3}$. Now $X = \{0,a-c,d,b,a\}$, and the $10$ distances are $$\delta_{1,2} = a-c,\quad \delta_{1,3} = d,\quad \delta_{1,4}= b,\quad \delta_{1,5} = a,\\ \delta_{2,3} = -a+c+d,\quad \delta_{2,4} = -a+b+c,\quad \delta_{2,5} = c,\\ \delta_{3,4} = b-d,\quad \delta_{3,5} = a-d, \\\delta_{4,5} = a-b.$$

By the above consideration, B1) and A1) cannot appear both (since they have $4$ points in common).

Assume that both B1) and A2) are possible. Then by comparing the distances, the two sets $\{-a+b+d, b-c\}$ and $\{-a+b+c, b-d\}$ must be the same. In both possibilities to match the elements, we end up with $c = d$, which shows that the point set is the same in both cases.

Case B2) $d = \delta_{3,5}$. Now $X = \{0,a-c,a-d,b,a\}$, and the $10$ distances are $$\delta_{1,2} = a-c,\quad \delta_{1,3} = a-d,\quad \delta_{1,4}= b,\quad \delta_{1,5} = a,\\ \delta_{2,3} = c-d,\quad \delta_{2,4} = -a+b+c,\quad \delta_{2,5} = c,\\ \delta_{3,4} = -a+b+d,\quad \delta_{3,5} = d, \\\delta_{4,5} = a-b.$$ We go on similarly as in B1).

Case B3) $d = \delta_{2,4}$. Here necessarily $a+d = b+c$, and the point $x_3$ is not yet fixed. The point set is $X = \{0,a-c,x_3,b,a\}$. We go on similarly as in B1), B2) to see that if B3) occurs together with A1) or A2), then $X$ is uniquely determined.

EDIT: The uniqueness for $n\leq 5$ is also stated in Lemma 2.1. in the first linked article of Steve Kass. However, the proof doesn't give to many details, and I do not understand the part "since $a + b = c$, if $a + c = 1$ then $b$ uniquely determines $T$.".

Solution 2:

This problem is called the "turnpike problem" or the "partial digest problem." Sets like the two @azimut gave are called "homometric" or "homeometric," and there can be many for a given set of distances (but the number of them is always a power of two). Here are a couple of references:

Reconstructing Sets From Interpoint Distances

The Partial Digest Problem

On the Turnpike Problem