Forma de celda de cuadrícula 3d más pequeña que es "fiel" en las isometrías de la cuadrícula

Question

Esta es una pregunta que se me ocurrió mientras jugaba tetris, y no de cualquier tarea. Traté de pensar acerca de mí mismo, pero me parece muy complicado, así que pensé que sería una buena idea publicar la pregunta aquí.

No tengo el lenguaje preciso para formular mi pregunta, así que voy a empezar a intentar explicar la pregunta mirando primero a la 2d caso.

Considerar el 2d de la cuadrícula, cuyos vértices son Z^2, considerando de plazas de unidad de longitud. Hay conectados formas en esta red, como las formas de conseguir que en el tetris. Algunas de esas formas, sin embargo, son especiales, en los que en virtud de cualquiera de los 2 diferentes isometrías de la cuadrícula, puede conseguir de 2 formas diferentes (no se puede traducir de una a coincidir con el otro). Mi pregunta se refiere a la más pequeña de tal forma. En 2d es muy fácil, ya que no hay una gran cantidad de posibilidades - es la forma de L con un lado más largo:

La siguiente forma, sin embargo, no es especial: ya que se puede reflejar a lo largo del eje vertical y obtener de la misma forma.

Y, entonces, mi pregunta es que si nos movemos en 3 dimensiones o más, ¿cuál es la mínima forma especial (que consta de por lo menos el número de bloques)? ¿Se sabe algo de la secuencia de el tamaño de la más pequeña de forma especial en n dimensiones?

Answer 1

Para $n\ge 6$, tarda $n+1$ bloques - véase la parte 2 para la construcción. Para $2\le n\le 5$, tarda $n+2$ bloques. El $n+2$-forma de bloque que funciona:

Parte 1

La etiqueta de los bloques basados en sus centros, situados en celosía puntos. La forma que lo hace tiene los bloques en $(-1,0,0,\dots)$, $(0,0,0,\dots)$, $(1,0,0,\dots)$, $(1,1,0,\dots)$, $(1,1,1,\dots)$, y así sucesivamente hasta que nos llene a todos de las coordenadas con.

¿Por qué funciona esto? Lo demostramos de manera inductiva, tomando la $2$-dimensiones en forma de L como el caso base y que demuestra que una isometría (de cualquier dimensión) que corrige la forma debe fijar cada bloque individual. Nuestra forma es un "gusano" con cada uno de los bloques conectados a dos los demás, excepto para los fines que sólo están conectados a una cuadra de cada uno. Los dos extremos también son distinguibles; sólo uno es parte de un tres cuadras de la línea recta. Llamada que termina con la "cabeza" y el final que no forma parte de un bloque de la cola.

Entonces, supongamos que una isometría mapas de la forma a sí mismo. Ya que los números de las conexiones de la misma estancia, los extremos se debe asignar a los extremos. Ya que los extremos son distinguibles, la cabeza debe asignar a la cabeza y la cola se debe asignar a la cola. Cortar la cola de bloque, reducción a la forma con uno de menor dimensión. Por la hipótesis inductiva, la isometría de las correcciones de cada uno de los bloques de la reducción de la forma. Agregar el fijo de la cola de la cuadra de nuevo, y la isometría de las correcciones de todos los bloques.

Finalmente, tomar la $n$-de la forma tridimensional y restringir nuestra isometría a una isometría de $\mathbb{R}^n$. El vector de diferencias entre los centros de los bloques span $\mathbb{R}^n$, por lo que una isometría que corrige cada bloque corrige un sistema generador, y debe corregir todos los de $\mathbb{R}^n$. Hecho.

Parte 2

Mientras que el anterior de forma que siempre funciona, no necesariamente es mínima. Para precisar el exacto mínimo, la primera nota que de cualquier forma con $n$ o menos de los bloques en los que se enmarca en $n-1$ o menos dimensiones; cada nuevo bloque está conectado a un bloque anterior, y los $\le n-1$ vectores no cubren la totalidad del espacio. Luego solo tenemos que dar una isometría que corrige todas las dimensiones, la forma, y se refleja en una de las otras dimensiones. Por lo tanto, el mínimo es siempre, al menos, $n+1$.

Para $n\ge 6$, el mínimo es igual a $n+1$. Las siete cuadras de la seis de la forma tridimensional: $(0,0,0,0,0,0)$, $(1,0,0,0,0,0)$, $(0,1,0,0,0,0)$, $(0,1,1,0,0,0)$, $(0,0,0,1,0,0)$, $(0,0,0,1,1,0)$, $(0,0,0,1,1,1)$. Tenemos un bloque de base con tres "colas" de diferentes longitudes que proceden de él, y que el bloque de base es el único bloque conectado a más de otros dos bloques. Desde las colas tienen diferentes longitudes, son distinguibles y cualquier isometría debe fijar cada cola. Como nuestro $n+2$ ejemplo, este utiliza todas las dimensiones, y por lo tanto, cualquier isometría que corrige todos los bloques soluciona todo.
Para $n>6$, ampliamos esta forma por la adición de más bloques para la cola más larga, de hasta $(0,0,0,1,1,1,\dots,1)$. Todas las propiedades de la clave, se quedan, y la forma no tiene no trivial de isometrías.

Parte 3

Que deja a $n\le 5$. Para obtener un poco mejor comprensión, voy a recurrir a la teoría de grafos aquí; si tomamos los bloques como vértices adyacentes conexiones como bordes, tenemos un gráfico. Una forma de $n+1$ bloques que utiliza todas las dimensiones que debe tener su gráfico de un árbol; el $n$ bordes son linealmente independientes, y que no hay ciclos

Ahora, cualquier gráfico automorphism de este árbol induce una isometría de la forma. Ahora vamos a demostrar que cualquier árbol en tres a seis vértices tiene trivial automorfismos, y por lo tanto, cualquier $n$-de la forma tridimensional de $n+1$ bloques tiene un trivial isometría para $2\le n\le 5$.

Tres vértices: sólo Hay un árbol de hasta automorphism. El intercambio de los dos extremos es una automorphism.

Cuatro vértices: Hay dos árboles de hasta automorphism:

Dos de ellos tienen trivial automorfismos; invertir el orden de la primera, mezclar las hojas de la segunda.

Cinco vértices: Hay tres árboles de hasta automorphism:

Todos tienen trivial automorfismos, que se puede visualizar fácilmente.

Seis vértices: Hay seis árboles de hasta automorphism:

Una vez más, todos tienen trivial automorfismos; el intercambio de colas de igual longitud que siempre funciona.