30 votos

¿Se puede recuperar una colección de puntos de su conjunto múltiple de distancias?

Considerar $n$ distintos puntos $x_1, \dots, x_n$ en $\mathbb{R}$. Asociados a estos puntos es el conjunto múltiple de todas las distancias $ $d(x_i,x_j) entre dos puntos. Supongamos que uno solo se entrega este multiset (no sabes los índices correspondientes). ¿Esto permite a recuperar únicamente los puntos originales hasta a la reflexión y la traducción?

31voto

azimut Puntos 13457

Esto es realmente una buena pregunta!

Contraejemplo para $n=6$

Los conjuntos $$\{0,1,4,5,11,13\}\\\{0,1,2,6,10,13\}$$ son affinely no equivalentes, pero el conjunto múltiple de las diferencias es que en ambos casos $$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.$$

Contraejemplos para $n \geq 7$ Según el Lema 2.1 en el primer artículo relacionado en la respuesta de Steve Kass, para todo $n\geq 6$, un contraejemplo es dada por $$X\cup \{n+1,n+3\}\quad\text{y}\quad X\cup\{2,n+1\}$$ donde $X = \{5,6,7,\ldots,n-1,n-2\} \cup \{0,1,n,n+5\}$.

La singularidad de $n\leq 5$

Para $n\in\{1,2\}$, la unicidad es clara.

Deje que $X = \{x_1,x_2,\ldots,x_n\}$ ser un punto establecido. Asumimos $x_1\leq x_2\leq\ldots \leq x_n$. Hasta afín de equivalencia, podemos suponer que $x_1 = 0$. Se denota la distancia de dos puntos $x,$ y $\delta(x,y) = \left|x-y\right|$ y además definir la abreviatura $\delta_{i,j} = \delta(x_i,x_j)$. En el conjunto múltiple de distancias, deje que $a \geq b\geq c\geq d$ a ser el más grande de elementos. Es claro que $a = \delta_{1,n}$ y por tanto $x_n =$. Hasta afín de equivalencia, podemos suponer que $b = \delta_{n-1,n}$ (la otra posibilidad es $\delta_{1,2}$), por lo que $x_{n-1} = b$. Esto muestra la singularidad para $n = 3$.

Para $n=4$, $\{\delta_{1,2},\delta_{2,n}\} = \{c,x_4-c\}$. Este distinquishes la última distancia restante $\delta_{2,3}$, que a su vez corrige $x_2$.

Queda por considerar el caso $n=5$.

En primer lugar observamos que si un punto más de $x\in\{x_2,x_3\}$ es fijo, el conjunto $X$ es completamente determinado: Deja $$ y ser el punto que falta. Entre los restantes cuatro distancias de $\delta(x_1,y)$, $\delta(x,y)$, $\delta(y,x_4)$, $\delta(y,x_5)$, el máximo de $d_m$ está contenida en el conjunto $\{\delta(x_1,y),\delta(x_5,y)\} = \{d_m, x_5-d_m\}$. Así también sabemos que el conjunto $\{\delta(x,y),\delta(y,x_4)\}$. Porque de $x,y\in(x_0,x_4)$, $\delta(y,x_4)$ es el más grande de los dos distancias, que fija el punto $y$.

Por la elección de los $c$ tenemos $c = \delta_{1,3}$ (Caso a) o $c = \delta_{2,n}$ (Caso B). Si el conjunto múltiple de distancias admite sólo uno de los dos casos, entonces, por las razones arriba mencionadas, $X$ es determinada únicamente. Lo que tenemos que ver que si en ambos casos son posibles, entonces el punto de conjuntos son necesariamente idénticos.

El caso a) Si $c = \delta_{1,3}$, entonces $x_3 = c$ y $d\in\{\delta_{1,2},\delta_{2,5}\}$.

Caso A1) $d = \delta_{1,2}$. Ahora $X = \{0,d,c,b,a\}$ y el $10$ distancias son $$\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$$

A2) $d = \delta_{2,5}$. Ahora $X = \{0,a-d,c,b,a\}$ y el $10$ distancias son $$\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$$

Caso B) Si $c = \delta_{2,5}$, entonces $x_2 = a-c$ y $d\in\{\delta_{1,3},\delta_{3,5},\delta_{2,4}\}$.

Caso B1) $d = \delta_{1,3}$. Ahora $X = \{0,a-c,d,b,a\}$ y el $10$ distancias son $$\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.$$

Por la anterior consideración, B1) y A1) no puede aparecer tanto (ya que ellos tienen $4$ puntos en común).

Se supone que ambas B1) y A2) son posibles. A continuación, mediante la comparación de las distancias, los dos conjuntos $\{-a+b+d, b-c\}$ y $\{-a+b+c, b-d\}$ debe ser el mismo. En ambas posibilidades para que coincida con los elementos, nos encontramos con $c = d$, lo que muestra que el punto de ajuste es el mismo en ambos casos.

Caso B2) $d = \delta_{3,5}$. Ahora $X = \{0,a-c,a-d,b,a\}$ y el $10$ distancias son $$\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.$$ Seguimos igual que en B1).

Caso B3) $d = \delta_{2,4}$. Aquí necesariamente $a+d = b+c$, y el punto de $x_3$ aún no es fijo. El punto de ajuste es de $X = \{0,a-c,x_3,b,a\}$. Seguimos igual que en B1), B2) a ver que si B3) se produce junto con A1) A2), entonces $X$ es determinada únicamente.

EDITAR: La singularidad de $n\leq 5$ se declaró también en el Lema 2.1. en el primer artículo relacionado de Steve Kass. Sin embargo, la prueba no da muchos detalles, y no entiendo la parte de "ya $a + b = c$, si $a + c = 1$ entonces $b$ únicamente determina $T$.".

28voto

Steve Kass Puntos 5967

Este problema se denomina la "autopista de peaje problema" o "parcial digerir problema". Conjuntos como los dos @azimut dio se llama "homometric" o "homeometric," y puede haber muchos para un conjunto dado de distancias (pero el número de ellos es siempre una potencia de dos). Aquí hay un par de referencias:

La Reconstrucción De Conjuntos De Interpoint Distancias

El Parcial De Digerir Problema

En la autopista Problema

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by: