# Conjetura de Keller

En geometría, la conjetura de Keller postula que en cualquier teselado del espacio euclídeo de n dimensiones mediante hipercubos idénticos, existen parejas de hipercubos contiguos que comparten entre sí una cara completa de dimensión (n − 1). Por ejemplo, en cualquier mosaico del plano con cuadrados idénticos, existen series de cuadrados contiguos que deben compartir un borde completo, como ocurre en la ilustración.
Esta conjetura fue introducida por Keller (1930), de quien lleva el nombre. Un avance de Lagarias y Shor (1992) demostró que es falso en diez o más dimensiones, y después de refinamientos posteriores, ahora se sabe que es verdadero en espacios de dimensión siete como máximo y falso en todas las dimensiones superiores. Las pruebas de estos resultados utilizan una reformulación del problema en términos del clique de ciertos grafos ahora conocidos como grafos de Keller.
La conjetura del teselado cúbico reticulado de Minkowski, una cuestión relacionada, establece que siempre que un teselado del espacio con cubos idénticos tiene la propiedad adicional de que los centros de los cubos forman un retículo, algunos cubos deben encontrarse cara a cara. Fue probado por György Hajós en 1942.
Szabó (1993), Shor (2004) y Zong (2005) han publicado reseñas de sus trabajos sobre la conjetura de Keller y problemas relacionados con el mismo.

## Enunciado

Un teselado o mosaico de un espacio euclídeo es, intuitivamente, una familia de subconjuntos que cubren todo el espacio sin superponerse. Más formalmente, una familia de conjuntos cerrados, llamadas teselas, forma un teselado si su unión es el espacio completo y cada dos conjuntos distintos de la familia tienen interiores separados. Se dice que un teselado es monoédrico si todas las teselas tienen la misma forma (son congruentes entre sí). La conjetura de Keller se refiere a teselados monoédricos en los que todas las teselas son hipercubos de la misma dimensión que el espacio. Como Szabó (1986) formuló el problema, un teselado cúbico es un teselado formado por hipercubos congruentes, en el que además se requiere que cualquier par de teselas puedan hacerse corresponder entre sí únicamente mediante traslaciones, sin necesidad de rotación alguna, o equivalentemente, que tengan todos sus lados paralelos a los ejes del sistema de coordenadas del espacio. No todos los mosaicos formados por cubos congruentes tienen esta propiedad; por ejemplo, el espacio tridimensional puede estar revestido por láminas bidimensionales de cubos que están girados en ángulos arbitrarios entre sí. Al formular el mismo problema, Shor (2004) consideró todas las teselas del espacio mediante hipercubos congruentes, y afirmó sin demostrarlo que la suposición de que los cubos son paralelos a los ejes coordenados se puede sumar sin pérdida de generalidad.
Un hipercubo de dimensión n tiene 2n caras de dimensión n − 1 que son, en sí mismas, hipercubos. Por ejemplo, un cuadrado tiene cuatro aristas y un cubo tridimensional tiene seis caras cuadradas. Dos teselas en un teselado cúbico (definido de cualquiera de las formas anteriores) se encuentran "cara a cara" si hay un hipercubo de dimensión (n − 1) que es una cara de ambos. La conjetura de Keller es la afirmación de que cada teselado cúbico tiene al menos un par de teselas que se encuentran cara a cara de esta manera.
La versión original de la conjetura expuesta por Keller abordaba una afirmación más contundente: cada teselado cúbico tiene una columna de cubos que se encuentran cara a cara. Esta versión del problema es verdadera o falsa para las mismas dimensiones que su formulación más comúnmente estudiada. Es una parte necesaria de la conjetura que todos los cubos del teselado sean congruentes entre sí, ya que si se permiten cubos de tamaños desiguales, entonces el teselado pitagórico sería un contraejemplo en dos dimensiones.
La conjetura mencionada no requiere que todos los cubos de un teselado se encuentren cara a cara con otros cubos. Aunque los teselados formados por cuadrados congruentes en el plano tienen la propiedad más fuerte de que cada cuadrado se encuentra borde a borde con otro cuadrado, es posible que algunas de las teselas en teselados con hipercubos de dimensiones superiores no se encuentren cara a cara con ninguna otra tesela. Por ejemplo, en tres dimensiones, la estructura denominada tetrastix formada por tres conjuntos perpendiculares de prismas cuadrados se puede utilizar para construir un teselado de cubos, combinatoriamente equivalente a la estructura de Weaire-Phelan, en el que una cuarta parte de los cubos (los que no forman parte de ningún prisma) son rodeados por otros doce cubos sin encontrarse con ninguno de ellos cara a cara.

## Reformulación de la teoría de grupos

Oskar Perron demostró que la conjetura de Keller era cierta en como máximo seis dimensiones. La refutación de la conjetura de Keller, para dimensiones suficientemente altas, ha progresado a través de una secuencia de reducciones que la transforman de un problema de geometría de teselados a un problema en teoría de grupos y, de ahí, a un problema en teoría de grafos.
Hajós (1949) reformuló por primera vez la conjetura de Keller en términos de factorizaciones de grupos abelianos. Demuestra que si hay un contraejemplo para la conjetura, entonces se puede suponer que es un teselado de cubos con una longitud de lado entera y posiciones de vértice enteras; y por lo tanto, al estudiar la conjetura, basta considerar cuestiones de esta forma especial. En este caso, el grupo de traslaciones de números enteros, módulo de las traslaciones que conservan el teselado, forma un grupo abeliano, y ciertos elementos de este grupo corresponden a las posiciones de las teselas. Hajós definió una familia de subconjuntos A$_i$ de un grupo abeliano como una factorización si cada elemento del grupo tiene una expresión única como suma a$_0$ + a$_1$ + ..., donde cada a$_i$ pertenece a A$_i$. Con esta definición, la conjetura reformulada de Hajós es que siempre que un grupo abeliano tiene una factorización en la que el primer conjunto A$_0$ puede ser arbitrario pero cada conjunto posterior A$_i$ toma la forma especial {0, g$_i$, 2g$_i$, 3g$_i$, ..., (|A$_i$| − 1)g$_i$} para algún elemento g$_i$ de A$_i$, entonces al menos un elemento |A$_i$|g$_i$ debe pertenecer a A$_0$ −A$_0$ (el conjunto diferencia de A$_0$ consigo mismo).
Szabó (1986) demostró que se puede suponer que cualquier teselado que forme un contraejemplo de la conjetura tiene una forma aún más especial: los cubos tienen una longitud de lado que debe ser una potencia de dos y coordenadas de vértice enteras, y el teselado es periódico, con un período dos veces la longitud del lado de los cubos en cada dirección de coordenadas. Con base en esta simplificación geométrica, también simplificó la formulación de la teoría de grupos de Hajós, mostrando que es suficiente considerar grupos abelianos que son sumas directas de grupos cíclicos de orden cuatro, con cada q$_i$ = 2.

## Grafo de Keller

Corrádi y Szabó (1990) reformuló el resultado de Szabó como una condición sobre la existencia de una camarilla grande en una determinada familia de grafos, que posteriormente se conocieron como los grafos de Keller. Más precisamente, los vértices del grafo de Keller de dimensión n son los elementos 4$^n$ (m$_1$,...,m$_n$) donde cada m es 0, 1, 2 o 3. Dos vértices están unidos por una arista si difieren en al menos dos coordenadas y difieren exactamente en dos en al menos una coordenada. Corrádi y Szabó demostraron que la camarilla en este grafo tiene un tamaño como máximo de 2$^n$, y si hay una camarilla de este tamaño, entonces la conjetura de Keller es falsa. Dada una camarilla de este tipo, se puede formar una cobertura del espacio mediante cubos de lado dos, cuyos centros tengan coordenadas que, tomadas en módulo cuatro, son vértices de la camarilla. La condición de que dos vértices cualesquiera de la camarilla tengan una coordenada que difiera en dos implica que los cubos correspondientes a estos vértices no se superponen. La condición de que los vértices difieran en dos coordenadas implica que estos cubos no pueden encontrarse cara a cara. La condición de que la camarilla tenga un tamaño 2$^n$ implica que los cubos dentro de cualquier período del teselado tienen el mismo volumen total que el período mismo. Esto, unido al hecho de que no se superponen, implica que los cubos colocados de esta forma teselan el espacio sin encontrarse cara a cara.
Lagarias y Shor (1992) refutaron la conjetura de Keller encontrando una camarilla de tamaño 2$^{10}$ en el grafo de Keller de dimensión 10. Esta camarilla conduce a un teselado sin piezas cara a cara en la dimensión 10, y sus copias se pueden apilar (desplazadas en media unidad en cada dirección coordenada) para producir teselados sin piezas cara a cara en cualquier dimensión superior. De manera similar, Mackey (2002) encontró una camarilla de tamaño 2$^8$ en el grafo de Keller de dimensión ocho, lo que lleva de la misma manera a un teselado sin piezas cara a cara en la dimensión 8 y (por apilamiento) en la dimensión 9.
Posteriormente, Debroni et al. (2011) demostró que el grafo de Keller de dimensión siete tiene una camarilla máxima de tamaño 124. Debido a que esto es menor que 2$^7$ = 128, la versión teórica de grafos de la conjetura de Keller es cierta en siete dimensiones. Sin embargo, la traslación de los teselados cúbicos a la teoría de grafos puede cambiar la dimensión del problema, por lo que este resultado no resuelve la versión geométrica de la conjetura en siete dimensiones. Finalmente, un prueba asistida por ordenador de 200 gigabytes realizada en 2019 utilizó grafos de Keller para establecer que la conjetura es cierta en siete dimensiones. Por tanto, la cuestión planteada por Keller puede considerarse resuelta: la conjetura es verdadera en siete dimensiones o menos, pero es falsa cuando hay más de siete dimensiones.
Los tamaños de las camarillas máximas en los grafos de Keller de dimensiones 2, 3, 4, 5 y 6 son, respectivamente, 2, 5, 12, 28 y 60. Los grafos de Keller de dimensiones 4, 5 y 6 han sido incluidos en el conjunto de grafos de desafío DIMACS que se utilizan con frecuencia como prueba de evaluación para algoritmos de obtención de camarillas.

## Problemas relacionados

Como describe Szabó (1993), Hermann Minkowski llegó a un caso especial de la conjetura del teselado cúbico a partir de un problema de aproximación diofántica. Una consecuencia del teorema de Minkowski es que cualquier retículo (normalizado para que su determinante sea uno) debe contener un punto distinto de cero cuya distancia de Chebyshov hasta el origen sea como máximo uno. Las redes que no contienen un punto distinto de cero con una distancia de Chebyshov estrictamente menor que uno se denominan críticas, y los puntos de una red crítica forman los centros de los cubos en un teselado cúbico. Minkowski conjeturó en 1900 que siempre que un teselado cúbico tenga sus cubos centrados en puntos de la red de esta manera, debe contener dos cubos que se encuentren cara a cara. Si esto es cierto, entonces (debido a las simetrías de la red) cada cubo en el teselado debe ser parte de una columna de cubos, y las secciones transversales de estas columnas forman un teselado de cubos de una dimensión más pequeña. Razonando de esta manera, Minkowski demostró que (asumiendo la verdad de su conjetura) cada red crítica tiene una base que puede expresarse como una matriz triangular, con unos en su diagonal principal y números a menos de uno de la diagonal. György Hajós demostró la conjetura de Minkowski en 1942 utilizando el teorema de Hajós sobre factorizaciones de grupos abelianos, un método de teoría de grupos similar al que más adelante se aplicaría a la conjetura más general de Keller.
La conjetura de Keller es una variante de la conjetura de Minkowski en la que se relaja la condición de que los centros de los cubos formen una red. Una segunda conjetura relacionada, planteada por Furtwängler en 1936, relaja la condición de que los cubos formen un teselado. Furtwängler preguntó si un sistema de cubos centrados en puntos de la red que forman un recubrimiento del k espacio (es decir, todos los subconjuntos de puntos en el espacio excepto un subconjunto de medida cero deben ser interiores exactamente a cubos de dimensión k) debe necesariamente tener dos cubos que se encuentren cara a cara. La conjetura de Furtwängler es cierta para el espacio bidimensional y tridimensional, pero Hajós encontró un contraejemplo de cuatro dimensiones en 1938. Robinson (1979) caracterizó las combinaciones de k y de la dimensión n que permiten un contraejemplo. Además, combinando las conjeturas de Furtwängler y Keller, Robinson demostró que los recubrimientos cuadrados de k lóbulos del plano euclídeo deben incluir dos cuadrados que se encuentren borde a borde. Sin embargo, para cada k > 1 y cada n > 2, existe un teselado de k lóbulos del espacio n dimensional mediante cubos sin caras compartidas.
Una vez que se conocieron los contraejemplos de la conjetura de Keller, resultó interesante preguntar por la dimensión máxima de una cara compartida que se puede garantizar que existe en un teselado cúbico. Cuando la dimensión n es como máximo siete, esta dimensión máxima es solo n − 1, según las pruebas de la conjetura de Keller para estas dimensiones pequeñas, y cuando n es al menos ocho, entonces esta dimensión máxima es como máximo de n − 2. Lagarias y Shor (1994) demostró que es como máximo n − √n/3, más fuerte en diez o más dimensiones.
Iosevich y Pedersen (1998) y Lagarias, Reeds y Wang (2000) encontraron conexiones estrechas entre los teselados cúbicos y la teoría espectral de funciones de cuadrado integrable en el cubo.
Dutour Sikirić, Itoh y Poyarkov (2007) usa camarillas en los grafos de Keller que son máximas, pero que no son máximas para estudiar empaquetamientos de cubos en el espacio que no se pueden ampliar agregando cubos adicionales.
En 1975, Ludwig Danzer e independientemente Branko Grünbaum y G. C. Shephard encontraron un teselado del espacio tridimensional mediante paralelepípedos con ángulos de cara de 60° y 120°, en los que no hay dos paralelepípedos que compartan una cara.