La conjetura de Keller es la hipótesis propuesta por Ott-Heinrich Keller [1] de que en cualquier teselación en el espacio euclidiano que consta de hipercubos idénticos , hay dos cubos que se tocan cara a cara. Por ejemplo, como se muestra en la figura, en cualquier mosaico en un plano de cuadrados idénticos, algunos dos cuadrados deben tocar borde con borde. Perron demostró que esto es cierto en dimensiones de hasta 6 [2] [3] ; Brackenzik y sus coautores demostraron la corrección de la conjetura para la dimensión 7 [4] . Sin embargo, esto no es cierto para dimensiones superiores, como demostraron Lagarias y Shor para dimensiones 10 y superiores [5] , Mackay para dimensiones 8 y superiores [6] , para lo cual utilizaron una reformulación del problema en términos del número clique de algunos gráficos, ahora conocidos como gráficos de Keller .
Una conjetura de Minkowski relacionada sobre la red de mosaico cúbico establece que cuando el espacio se llena con cubos idénticos con la propiedad adicional de que los centros de los cubos forman una red , algunos cubos deben tocarse cara a cara. La hipótesis fue probada por Hayosh en 1942.
Una familia de conjuntos cerrados , llamados mosaicos , forma un parquet o mosaico en el espacio euclidiano si su unión llena completamente el espacio y dos conjuntos distintos cualesquiera de la familia tienen interiores disjuntos. Se dice que una teselación es monoédrica si todas sus teselas son congruentes. La conjetura de Keller se refiere a mosaicos monoédricos en los que todos los mosaicos son hipercubos . Como dijo Szabo [7] , un mosaico cúbico es un mosaico de hipercubos congruentes que requiere que todos los mosaicos sean traslaciones paralelas entre sí sin rotación, o de manera equivalente, todos los bordes de los mosaicos deben ser paralelos a los ejes de coordenadas. No todas las teselas de cubos congruentes tienen esta propiedad. Por ejemplo, el espacio tridimensional se puede teselar con capas de cubos que se giran entre sí en un ángulo arbitrario. Shor [8] , por otro lado, define un teselado cúbico como un teselado arbitrario del espacio por hipercubos y afirma sin prueba que se pueden requerir lados paralelos a los ejes sin pérdida de generalidad.
Un hipercubo en un espacio n -dimensional 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 mosaicos en un mosaico cúbico (definido por cualquiera de los métodos anteriores) se tocan cara a cara si existe un hipercubo de ( n - 1) dimensión que es una cara de ambos mosaicos. La conjetura de Keller establece que cualquier mosaico cúbico contiene al menos un par de mosaicos que se tocan cara a cara de esta manera.
La versión original de la conjetura de Keller contenía la afirmación más fuerte de que cualquier mosaico cúbico tiene una columna de cubos tangentes cara a cara. Es cierto en las mismas dimensiones que la afirmación más débil, que suele ser considerada por los investigadores [9] [10] .
Un requisito esencial de la hipótesis es el requisito de que las fichas sean congruentes entre sí. Para cubos similares pero no congruentes , es posible un mosaico pitagórico , que sirve como un contraejemplo trivial en el espacio bidimensional.
La refutación de la conjetura de Keller para dimensiones suficientemente altas pasó por una secuencia de reducciones que transforman el problema de geometría mosaico en un problema de teoría de grupos , y de éste en un problema de teoría de grafos .
Hayosh [11] fue el primero en formular la conjetura de Keller en términos de factorización de grupos abelianos . Demostró que si hay un contraejemplo a la conjetura, entonces puede considerarse un mosaico periódico de cubos con longitudes de lado enteras y coordenadas de vértice enteras. Así, cuando se estudia una hipótesis, basta considerar teselaciones de una forma especial. En este caso, el grupo de traslaciones paralelas enteras que conserva el mosaico forma un grupo abeliano, y los elementos del grupo corresponden a las posiciones de los mosaicos. Hayosh 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 . De acuerdo con esta definición, Hayosh reformuló la conjetura: si un grupo abeliano tiene una factorización en la que el primer conjunto A 0 puede ser arbitrario, y cada conjunto posterior A i tiene una forma especial {0, g i , 2 g i , 3 g i , ..., ( q i − 1) g i }, entonces al menos uno de los elementos q i g i debe pertenecer a A 0 − A 0 ( la diferencia de Minkowski de A 0 consigo mismo).
Szabo [7] demostró que cualquier mosaico que forme un contraejemplo a la conjetura debe tener una forma aún más específica: la longitud de un lado de un cubo es una potencia de dos, los vértices tienen coordenadas enteras y el mosaico es periódico con un período igual al doble de la longitud del lado del cubo en cada coordenada. Basado en esta simplificación geométrica, simplificó la formulación de la teoría de grupos de Hajos al mostrar que es suficiente considerar grupos abelianos que son sumas directas de grupos cíclicos de orden cuatro con q i = 2.
Corradi y Szabo [12] reformularon el resultado de Szabo en forma de una condición sobre la existencia de una gran camarilla en cierta familia de grafos, que más tarde se conoció como grafos de Keller . Más precisamente, los vértices de un gráfico de Keller de dimensión n son 4 n elementos ( m 1 ,..., m n ), donde cada número m es 0, 1, 2 o 3. Dos vértices están conectados por una arista si difieren en al menos dos coordenadas y difieren en dos en al menos una coordenada. Corradi y Szabo demostraron que la camarilla más grande en este gráfico tiene un tamaño máximo de 2 n , y si hay una camarilla de este tamaño, entonces la conjetura de Keller no es cierta. Dada tal camarilla, se puede formar un espacio de cubos de lado dos cuyos centros tengan coordenadas que, módulo cuatro, sean los vértices de la camarilla. De la condición de que dos vértices cualesquiera de una camarilla tengan coordenadas que difieren en dos, se sigue que los cubos correspondientes a estos vértices no se superponen. De la condición de que la camarilla tenga un tamaño de 2 n , se sigue que los cubos dentro de cualquier período del mosaico tienen el mismo volumen que el período mismo. Junto con el hecho de que las teselas no se superponen, esto implica que los cubos teselan el espacio. Sin embargo, de la condición de que los vértices de dos camarillas cualesquiera difieran en al menos dos coordenadas, se sigue que no hay dos cubos que tengan caras comunes.
Lagarias y Shor en 1992 [5] refutaron la conjetura de Keller al encontrar una camarilla de tamaño 2 10 en el gráfico de Keller de dimensión 10. Estas camarillas conducen a un mosaico de dimensión 10 sin caras comunes (contacto cara a cara), y las copias de los mosaicos se pueden colocar en el espacio (compensadas por media unidad en cada dirección de coordenadas), creando un mosaico sin contacto cara a cara en cualquier dimensión superior. De manera similar, Makei [6] redujo las dimensiones en las que se encontraron los contraejemplos al encontrar una camarilla de tamaño 2 8 en un gráfico de Keller de dimensión ocho.
Debrony, Eblen, Langston y Shore [13] demostraron que el gráfico de Keller de siete dimensiones tiene la camarilla más grande de tamaño 124 < 2 7 . Así, en esta dimensión no fue posible encontrar un contraejemplo a la conjetura de Keller de la misma forma que en las dimensiones 10 y 8 anteriores. Más tarde se demostró que si no hay una camarilla de tamaño 2 7 en cierto gráfico relacionado con la gráfica de Keller, entonces la conjetura es verdadera en la dimensión 7. La ausencia de tal camarilla en esta gráfica fue mostrada por Brackenzik et al. en arXiv.org en 2019 y en actas de conferencias en 2020. La condición para la ausencia de una camarilla se escribió como una fórmula proposicional , se simplificó usando un programa especial, su imposibilidad se demostró usando un solucionador automático SAT , luego de lo cual la prueba se verificó formalmente adicionalmente por el programa [4] [14] .
Los tamaños de las camarillas más grandes de los gráficos de Keller en dimensiones bajas 2, 3, 4, 5 y 6 son 2, 5, 12, 28 y 60, respectivamente, utilizados como pruebas de rendimiento para los algoritmos de búsqueda de clics [15] .
Como escribe Szabo [16] , Herman Minkowski llegó a un caso especial de la conjetura de mosaico cúbico del problema de aproximación diofántica . Una de las consecuencias del teorema de Minkowski es que cualquier red (normalizada para tener un determinante igual a uno) debe contener un punto distinto de cero, la distancia de Chebyshev , desde el cual al origen no excede de uno. Las redes que no contienen puntos distintos de cero con una distancia de Chebyshev estrictamente menor que uno se denominan críticas, y los puntos de la red crítica forman los centros de los cubos del mosaico cúbico. Minkowski sugirió en 1900 que si una red cúbica tuviera tal disposición de centros, debería contener dos cubos que se toquen cara a cara. Si esto es cierto, entonces (debido a la simetría de la red) cada cubo en este mosaico debe ser parte de una columna de cubos, y las intersecciones de estos cubos deben formar un mosaico cúbico de menor dimensión. Al razonar de esta manera, Minkowski demostró que (suponiendo que la hipótesis sea cierta) cualquier red crítica tiene una base que se puede expresar como una matriz triangular con unos en la diagonal principal y números menores que uno fuera de la diagonal. György Hajos demostró la conjetura de Minkowski en 1942 utilizando el teorema de factorización de Hajos para grupos abelianos, un enfoque de teoría de grupos que luego aplicó a la conjetura de Keller más general.
La hipótesis de Keller es una variante de la hipótesis de Minkowski, en la que se debilita la condición de que los centros de los cubos formen una red. Otra conjetura relacionada, presentada por Furtwangler en 1936, relaja la condición de que los cubos formen una red. Furtwangler preguntó si un sistema de cubos con centro de celosía que forman una cubierta de espacio de k pliegues (es decir, cualquier punto en el espacio, excepto los puntos de un subconjunto de medida cero, debe pertenecer al interior de exactamente k cubos) debe contener dos cubos que se tocan cara a arista. La conjetura de Furtwangler es cierta para las dimensiones dos y tres, pero para un espacio de cuatro dimensiones, Shayosh encontró un contraejemplo en 1938. Robinson [17] describió combinaciones del número de cubos k y la dimensión n para las que son posibles contraejemplos. Además, al combinar las hipótesis de Furtwangler y Keller, Robinson demostró que una cubierta de cuadrados con pliegues en k del plano euclidiano debe contener dos cuadrados de borde a borde. Sin embargo, para cualquier k > 1 y n > 2, hay un mosaico de k veces del espacio n -dimensional por cubos que no tienen caras comunes [18] .
Tan pronto como se conocieron los contraejemplos a la conjetura de Keller, surgió la cuestión de la dimensión máxima de las caras cuya existencia está garantizada para los cubos en un mosaico cúbico. Si la dimensión de n no excede de seis, entonces la dimensión máxima es igual a n − 1 según la prueba de Perron de la conjetura de Keller para dimensiones pequeñas, y para n no menor a ocho, la dimensión máxima no excede de n − 2. Lagarias y Shor [19] dieron un límite superior más estricto, n − √n / 3.
Iosevich y Pedersen [20] , así como el grupo formado por Lagarias, Reed y Wang [21] , encontraron una estrecha conexión entre las teselaciones cúbicas y la teoría espectral de funciones integrables al cuadrado en el cubo.
Dutour-Sikirich, Ito y Poyarkov [22] utilizaron camarillas de gráficos de Keller que son máximos pero no máximos para estudiar el empaquetamiento de cubos en el espacio al que no se puede agregar ningún cubo adicional.
En 1975, Ludwig Danzer e, independientemente, Branko Grünbaum y Shepard encontraron una teselación paralelepipédica tridimensional con caras inclinadas de 60° y 120°, en la que dos paralelepípedos no comparten una cara [23] .
| mosaicos geometricos | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Periódico |
| ||||||||
| aperiódico |
| ||||||||
| Otro |
| ||||||||
| Por configuración de vértice |
| ||||||||