30
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ By the way, this isn't graph theory (as indicated in the tags). $\endgroup$ – Alexander Gruber Mar 3 '13 at 22:17
  • 2
    $\begingroup$ Uniquely up to reflection and translation is not very uniquely at all. Essentially the question is whether or not the equivalence relation "same multiset of distances" is the same equivalence relation as "same set up to a reflection and translation". $\endgroup$ – Asaf Karagila Mar 3 '13 at 23:07
  • 3
    $\begingroup$ @Asaf: yes. What's your point? $\endgroup$ – Qiaochu Yuan Mar 3 '13 at 23:08
  • $\begingroup$ @Qiaochu: And that's a much clearer way of phrasing the question. Saying "uniquely up to..." confused me for quite a few minutes, especially in light of Alexander's answer and the comments which follows it. $\endgroup$ – Asaf Karagila Mar 3 '13 at 23:09
  • 3
    $\begingroup$ @Asaf: the original phrasing of the question was worse. I think your phrasing is unnecessarily pedantic. Perhaps we could say "if two such collections of points have the same multiset of distances, are they necessarily related by reflection and translation?" $\endgroup$ – Qiaochu Yuan Mar 3 '13 at 23:11
31
+100
$\begingroup$

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$.".

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ Very good. I'm glad it's not true, since I couldn't prove it! I wonder if $n=6$ is the smallest counterexample. $\endgroup$ – Alexander Gruber Mar 3 '13 at 23:40
  • $\begingroup$ @AlexanderGruber: Thanks. Frankly speaking, I consider the answer awesome for $n=6$ and $n\leq 4$, but not for $n=5$. There are just too many unpleasant cases, and I didn't discuss them all in detail. Any idea on further reducing the complexity would be welcome. My hope is that with further simplifications, a discussion of the case $n=6$ would become feasible (resulting in a classification of the counterexamples). So yes, leave the bounty up and let's hope this gets some more attention. $\endgroup$ – azimut Mar 14 '13 at 16:23
  • $\begingroup$ Is it clear that there exist counter-examples for all $n>6$? I can't think of a simple way to extend this counter-example to larger values of $n$. Might it be possible that there are larger values of $n$ where $n$ points can be recovered from their multiset? $\endgroup$ – Jared Mar 18 '13 at 23:40
  • $\begingroup$ @Jared: Yes, they do exist for all n≥6. look Lemma 2.1 in the first article Steve Kass has linked. $\endgroup$ – azimut Mar 19 '13 at 0:07
28
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Here's a conceptual explanation for non-uniqueness for $n \geq 7$.

Steve's first link, Lemka--Skiena--Smith's "Reconstructing Sets From Interpoint Distances", relies on Rosenblatt--Seymour's earlier "The Structure of Homometric Sets". Rosenblatt--Seymour's main innovation is the following observation. First, if U and V are finite multisets in $\mathbb{R}^n$, then $U+V$ and $U-V$ have the same multiset of pairwise differences. Second, the "virtual converse" holds: if $A$ and $B$ have the same multiset of pairwise differences, then there are "virtual multisets" $U$ and $V$, i.e. multisets where we allow negative multiplicities, such that $A = U+V$ and $B = U-V$.

In terms of generating functions, let $A(x) := \sum_{a \in A} x^a$. $A$ and $B$ having the same multiset of pairwise differences means precisely that $A(x)A(x^{-1}) = B(x)B(x^{-1})$, and the Rosenblatt--Seymour criterion means exactly that there are $U(x), V(x)$ with integer coefficients such that $A(x) = U(x)V(x)$ and $B(x) = U(x)V(x^{-1})$. (Here the exponents are real numbers, and it's multivariate in the case of $\mathbb{R}^n$.) In any case, the insight is that we can factor $A(x)$ into irreducibles and toggle $x \mapsto x^{-1}$ in a subset of the factors to construct all possible multisets with the same distances. Here factorization is unique up to units $\pm x^\alpha$.

Uniqueness with at most 5 points up to translation and reflection is hence equivalent to the following claim. If $U(x)V(x)$, $U(x)V(x^{-1})$, and $U(x^{-1})V(x)$ all differ by more than just overall x-shifts and all have non-negative integer coefficients, then the common sum of their coefficients is at least 6. There's of course some minimum value for this common sum, though it's not at all obvious that it's exactly 6. You can let U and V be non-symmetric 0-1 polynomials to immediately get common sums of the form $nm$ for $n, m \geq 3$. In fact, you can use $U(x) = 1-x+x^3$ and let $V(x)$ be any non-symmetric 0-1 polynomial with integer exponents and non-zero coefficients occurring in clumps of at least 3 adjacent to get all numbers $\geq 7$. Getting $n=6$ in this way seems difficult. Some brute force gives for instance $$x^{32}+x^{22}+x^{20}+x^9+x^1+1 = \left(x^2+x+1\right) \left(x^9-x^8+x^6-x^5+x^3-x^2+1\right) \left(x^{21}-x^{10}+x^9+1\right)$$

Perhaps azimut's arguments can be recast into the generating function setup and made more intuitive?

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.