Conjetura de Keller

En este teselado del plano con cuadrados congruentes, los cuadrados verdes y violetas se encuentran de borde a borde al igual que los cuadrados azules y naranjas

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.

El 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) ofrecen 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.​

El teselado pitagórico muestra que los cuadrados desiguales pueden formar mosaicos en el plano sin encontrarse lado a lado

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₀ + a₁ + ..., 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₀ 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₀ −A₀ (el conjunto diferencia de A₀ 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

El grafo de Keller de dimensión dos, isomorfo al grafo de Clebsch

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ⁿ (m₁,...,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ⁿ, 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ⁿ 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.​

Plantilla:Harvs refutó la conjetura de Keller encontrando una camarilla de tamaño 2¹⁰ en el grafo de Keller de dimensión 10. Esta camarilla conduce a un teselado sin teselas 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⁸ 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⁷ = 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.​

Bibliografía

• Brakensiek, Joshua; Heule, Marijn; Mackey, John; Narváez, David (2020), «The resolution of Keller's conjecture», en Peltier, Nicolas; Sofronie-Stokkermans, Viorica, eds., Automated Reasoning: 10th International Joint Conference, IJCAR 2020, Paris, France, July 1–4, 2020, Proceedings, Part I, Lecture Notes in Computer Science 12166, Springer, pp. 48-65, S2CID 203951899, arXiv:1910.03740, doi:10.1007/978-3-030-51074-9_4 .
• Conway, John H.; Burgiel, Heidi; Goodman-Strauss, Chaim (2008), «Understanding the Irish Bubbles», The Symmetries of Things, Wellesley, Massachusetts: A K Peters, p. 351, ISBN 978-1-56881-220-5, MR 2410150  .
• Corrádi, K.; Szabó, S. (1990), «A combinatorial approach for Keller's conjecture», Periodica Mathematica Hungarica. Journal of the János Bolyai Mathematical Society 21 (2): 95-100, MR 1070948, S2CID 121453908, doi:10.1007/BF01946848 ..
• Debroni, Jennifer; Eblen, John D.; Langston, Michael A.; Shor, Peter; Myrvold, Wendy; Weerapurage, Dinesh (2011), «A complete resolution of the Keller maximum clique problem», Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms, pp. 129-135, S2CID 15797721, doi:10.1137/1.9781611973082.11, hdl:1721.1/81184 ..
• Dutour Sikirić, Mathieu; Itoh, Yoshiaki; Poyarkov, Alexei (2007), «Cube packings, second moment and holes», European Journal of Combinatorics 28 (3): 715-725, MR 2300752, S2CID 15876010, arXiv:math/0509100, doi:10.1016/j.ejc.2006.01.008 ..
• Grünbaum, Branko; Shephard, G. C. (1980), «Tilings with congruent tiles», Bulletin of the American Mathematical Society 3 (3): 951-973, MR 585178, doi:10.1090/S0273-0979-1980-14827-2 ..
• Hajós, G. (1949), «Sur la factorisation des groupes abéliens», Československá Akademie Věd. Časopis Pro Pěstování Matematiky 74: 157-162, MR 0045727 ..
• Hartnett, Kevin (August 19, 2020), «Computer Search Settles 90-Year-Old Math Problem», Quanta Magazine ..
• Iosevich, Alex; Pedersen, Steen (1998), «Spectral and tiling properties of the unit cube», International Mathematics Research Notices 1998 (16): 819-828, MR 1643694, S2CID 14232561, arXiv:math/0104093, doi:10.1155/S1073792898000506 ..
• Johnson, David S.; Trick, Michael A. (1996), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11–13, 1993, Boston, MA, USA: American Mathematical Society, ISBN 0-8218-6609-5 .. Véanse en particular las páginas 43, 114, 147, 156 y 161-163, que describen diferentes resultados computacionales en los grafos de Keller incluidos en este conjunto de desafíos.
• Keller, O. -H. (1930), «Über die lückenlose Erfüllung des Raumes mit Würfeln», Crelle (revista) (en german) 1930 (163): 231-248, JFM 56.1120.01, S2CID 199547028, doi:10.1515/crll.1930.163.231 ..
• Lagarias, Jeffrey C.; Reeds, James A.; Wang, Yang (2000), «Orthonormal bases of exponentials for the $n$-cube», Duke Mathematical Journal 103 (1): 25-37, MR 1758237, doi:10.1215/S0012-7094-00-10312-2, «citeseerx: 10.1.1.207.4194» ..
• Lagarias, Jeffrey C.; Shor, Peter W. (1992), «Keller's cube-tiling conjecture is false in high dimensions», Bulletin of the American Mathematical Society, New Series 27 (2): 279-283, Bibcode:1992math.....10222L, MR 1155280, S2CID 6390600, arXiv:math/9210222, doi:10.1090/S0273-0979-1992-00318-X ..
• Lagarias, J. C.; Shor, P. W. (1994), «Cube-tilings of $\mathbb {R} ^{n}$ and nonlinear codes», Discrete and Computational Geometry 11 (4): 359-391, MR 1273224, doi:10.1007/BF02574014 ..
• Łysakowska, Magdalena; Przesławski, Krzysztof (2011), «On the structure of cube tilings and unextendible systems of cubes in low dimensions», European Journal of Combinatorics 32 (8): 1417-1427, doi:10.1016/j.ejc.2011.07.003 ..
• Łysakowska, Magdalena; Przesławski, Krzysztof (2012), «Keller's conjecture on the existence of columns in cube tilings of $\mathbb {R} ^{n}$», Advances in Geometry 12 (2): 329-352, MR 2911153, S2CID 14016886, arXiv:0809.1960, doi:10.1515/advgeom.2011.055 .
• Mackey, John (2002), «A cube tiling of dimension eight with no facesharing», Discrete and Computational Geometry 28 (2): 275-279, MR 1920144, doi:10.1007/s00454-002-2801-9 ..
• Perron, Oskar (1940a), «Über lückenlose Ausfüllung des $n$-dimensionalen Raumes durch kongruente Würfel», Mathematische Zeitschrift 46: 1-26, MR 0003041, S2CID 186236462, doi:10.1007/BF01181421 ..
• Perron, Oskar (1940b), «Über lückenlose Ausfüllung des $n$-dimensionalen Raumes durch kongruente Würfel. II», Mathematische Zeitschrift 46: 161-180, MR 0006068, S2CID 123877436, doi:10.1007/BF01181436 ..
• Robinson, Raphael M. (1979), «Multiple tilings of $n$-dimensional space by unit cubes», Mathematische Zeitschrift 166 (3): 225-264, MR 526466, S2CID 123242152, doi:10.1007/BF01214145 ..
• Shor, Peter (2004), Minkowski's and Keller's cube-tiling conjectures, Lecture notes for IAP Mathematics Lecture Series ..
• Szabó, Sándor (1982), «Multiple tilings by cubes with no shared faces», Aequationes Mathematicae 25 (1): 83-89, MR 716380, S2CID 122364522, doi:10.1007/BF02189600 ..
• Szabó, Sándor (1986), «A reduction of Keller's conjecture», Periodica Mathematica Hungarica. Journal of the János Bolyai Mathematical Society 17 (4): 265-277, MR 866636, S2CID 120163301, doi:10.1007/BF01848388 ..
• Szabó, Sándor (1993), «Cube tilings as contributions of algebra to geometry», Beiträge zur Algebra und Geometrie 34 (1): 63-75, MR 1239279 ..
• Zong, Chuanming (2005), «What is known about unit cubes», Bulletin of the American Mathematical Society, New Series 42 (2): 181-211, MR 2133310, doi:10.1090/S0273-0979-05-01050-5 ..

• Datos: Q4802474