Un subconjunto más grande de una red cúbica con la única a la que las distancias entre sus puntos

Question

Deje $n$ ser un entero positivo. Considere un conjunto $S_n=([1,n]\cap\mathbb N)^3$ tener $n^3$ puntos en el espacio Euclidiano $\mathbb R^3$ dispuestos en una red cúbica. Deje $a_n$ ser del tamaño de un subconjunto más grande de $S_n$ tal que para cada par de puntos en el subconjunto no hay otro par de puntos en el subconjunto que tiene la misma distancia entre ellos (es decir, todas las distancias entre los puntos en el subconjunto son únicos). Puedes sugerir una manera eficiente para calcular $a_n$, o encontrar una fórmula general para esta secuencia? O, al menos, encontrar $a_n$ para un par de pequeños enteros positivos?

---

Actualización: Inferior o superior de los límites, o comportamiento asintótico son bienvenidos. Es la secuencia de las $\{a_n\}$ estrictamente creciente?

Answer 1

Para cada una de las $r \in [1, \ldots, 3 n^2]$ deje $E_r$ el conjunto de pares no ordenados $(p,q)$ de los puntos en $S_n$ tal que $\|p-q\|^2 = r$. Queremos una mayor subconjunto $X$ $S_n$ tal que $X$ contiene al menos uno de cada $E_r$. Puede ser considerado como un cuadráticamente limitada entero de un problema de programación:

maximizar $\sum_{p \in S_n} x_p$

sujeto a $\sum_{(p,q) \in S_r} x_p x_q \le 1$ por cada $r$

todos los $x_p \in \{0,1\}$

No se de que existen métodos eficientes para resolver esto, pero CPLEX debe ser capaz de hacer esto por pequeño $n$.

EDIT: parece que una cuidadosa programación lineal entera (modelo con variables binarias para ambos bordes y vértices) funciona mejor. Los resultados para las pequeñas $n$

$$ \matriz{n + a_n\cr 1 & 1\cr 2 & 3\cr 3 & 4\cr 4 & 6\cr}$$ Tengo unas tenues esperanzas de conseguir $a_5$ (hasta ahora CPLEX ha encontrado una solución con $7$ vértices y un límite superior de $19.51$)

EDIT: CPLEX se estrelló antes de la obtención de una solución óptima para $n=5$. Un ejemplo para mostrar a $a_5 \ge 7$ es $$\pmatrix{ 3 & 4 & 2\cr 1 & 2 & 2\cr 4 & 4 & 2\cr 5 & 5 & 2\cr 5 & 1 & 4\cr 5 & 5 & 4\cr 2 & 1 & 5\cr}$$

EDITAR:

Para $n=6$, Jyrki la estimación de la muestra $a_6 \le 9$, y (usando búsqueda tabú) que fue capaz de encontrar un ejemplo para mostrar a $a_6 = 9$:

$$ \pmatrix{ 4 & 3 & 1\cr 1 & 5 & 4\cr 1 & 2 & 6\cr 6 & 1 & 1\cr 1 & 6 & 4\cr 2 & 5 & 3\cr 2 & 2 & 2\cr 6 & 2 & 6\cr 1 & 6 & 6\cr}$$

EDIT: yo era capaz de encontrar un ejemplo para mostrar a $a_7 \ge 10$: $$\pmatrix{ 1 & 7 & 7\cr 5 & 7 & 1\cr 7 & 2 & 2\cr 7 & 5 & 5\cr 1 & 2 & 2\cr 1 & 4 & 7\cr 2 & 7 & 7\cr 7 & 6 & 4\cr 1 & 7 & 5\cr 6 & 3 & 1\cr}$$

Todavía tratando de $11$.

Answer 2

La promoción de los comentarios a una respuesta, como el límite superior parece ser sorprendentemente bien temprano.

Queremos evitar repeticiones de los cuadrados de las distancias. El cuadrado de la distancia $d$ entre dos puntos en $S_n$ es de la forma $$ d=a^2+b^2+c^2, $$ donde $a,b,c$ son enteros en el rango de $[0,n-1]$. Nos deja denotar por $D_n$ el conjunto de tales sumas $>0$. El tamaño exacto de la set $D_n$ es difícil de escribir, pero obviamente es $<3(n-1)^2$, y hace crecer más o menos como una ecuación cuadrática función polinómica de $n$.

Llamar a un subconjunto $S\subseteq S_n$ 3 dimensiones de la regla de Golomb, 3DGR para el corto, si no hay repeticiones entre los cuadrados de las distancias entre sus puntos. Si $S$ es un 3DGR con $m$ elementos, entonces los cuadrados de las distancias entre sus puntos forman un subconjunto de a $\binom m2$ enteros del conjunto $D_n$. Por lo tanto, tenemos la desigualdad $$ \binom m2\le |D_n|.\qquad(*) $$ Así que si $a_n$ es el tamaño máximo de un 3DGR $S\subseteq S_n$, luego tenemos un límite superior $a_n\le m$ donde $m$ es el entero más grande de satisfacciones $(*)$.

---

Ejemplo. Considere el caso en $n=3$. Podemos ver fácilmente que el conjunto $D_3$ se compone de los números enteros $$ D_3=\{1,2,3,4,5,6,8,9,12\}, $$ un total de nueve elementos. Debido a $\binom 42<9<\binom 52$ podemos deducir que una 3DGR $\subseteq S_3$ puede tener en la mayoría de los cuatro elementos. Es fácil comprobar que $$ S=\{(1,1,1),(1,1,3),(2,3,3),(3,3,3)\} $$ es un 3DGR (rendimiento de los cuadrados de las distancias $1,4,5,8,9,12$). Por lo tanto, el obligado es difícil en este caso, y podemos concluir que $a_3=4$.

---

He aquí una pequeña tabla (gracias, Mathematica) de los límites superiores a $a_n$: $$ \begin{array}{c|c|ccc|c|c} n&|D_n|&a_n\le&&n&|D_n|&a_n\le\\ \hline 1&0&1&&11&178&19\\ 2&3&3&&12&211&21\\ 3&9&4&&13&259&23\\ 4&18&6&&14&299&24\\ 5&31&8&&15&346&26\\ 6&44&9&&16&401&28\\ 7&66&12&&17&463&30\\ 8&87&13&&18&516&32\\ 9&115&15&&19&591&34\\ 10&144&17&&20&648&36 \end{array} $$

Así que podemos ver que el límite superior crece linealmente en función de $n$ (se sigue inmediatamente de las estimaciones sobre el tamaño de $D_n$). No me atrevo a adivinar, ¿los verdaderos valores de $a_n$ se comportan. El caso de 1-dimensional Golomb gobernantes es bastante difícil, y enormes cantidades de recursos informáticos se han puesto hacia la mejora de su construcción.