En geometría , la conjetura de Keller es la conjetura de que en cualquier mosaico del espacio euclidiano n- dimensional por hipercubos idénticos , hay dos hipercubos que comparten una cara completa ( n - 1) dimensional entre sí. Por ejemplo, en cualquier mosaico del plano por cuadrados idénticos, unos dos cuadrados deben compartir un borde completo, como lo hacen en la ilustración.
Esta conjetura fue introducida por Ott-Heinrich Keller ( 1930 ), de quien toma su nombre. Un avance de Lagarias y Shor ( 1992 ) mostró que es falso en diez o más dimensiones, y después de posteriores refinamientos, 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 número de clique de ciertos gráficos que ahora se conocen como gráficos de Keller .
La conjetura relacionada de Minkowski enrejado de cubos establece que siempre que un mosaico de espacio por cubos idénticos tiene la propiedad adicional de que los centros de los cubos forman un enrejado , algunos cubos deben encontrarse cara a cara. György Hajós lo probó en 1942.
Szabó (1993) , Shor (2004) y Zong (2005) ofrecen encuestas sobre el trabajo sobre la conjetura de Keller y problemas relacionados.
Declaración
Un mosaico o mosaico de un espacio euclidiano es, intuitivamente, una familia de subconjuntos que cubren todo el espacio sin superponerse. Más formalmente, una familia de conjuntos cerrados , llamados mosaicos , forma un mosaico si su unión es el espacio completo y cada dos conjuntos distintos de la familia tienen interiores separados. Se dice que un mosaico es monoédrico si todos los mosaicos tienen la misma forma (son congruentes entre sí). La conjetura de Keller se refiere a los mosaicos monoédricos en los que todos los mosaicos son hipercubos de la misma dimensión que el espacio. Como Szabó (1986) formula el problema, un mosaico de cubos es un mosaico por hipercubos congruentes en el que se requiere que los mosaicos sean traslaciones entre sí sin ninguna rotación, o lo que es lo mismo, que tengan todos sus lados paralelos a los ejes de coordenadas. del espacio. No todos los mosaicos por cubos congruentes tienen esta propiedad; por ejemplo, el espacio tridimensional puede estar embaldosado por láminas bidimensionales de cubos que se retuercen en ángulos arbitrarios entre sí. Al formular el mismo problema, Shor (2004), en cambio, considera todas las teselaciones del espacio mediante hipercubos congruentes y afirma, sin pruebas, que la suposición de que los cubos son ejes paralelos se puede sumar sin pérdida de generalidad.
Un hipercubo n- dimensional tiene 2 n 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 de cubo (definido en cualquiera de las formas anteriores) se encuentran cara a cara si hay un hipercubo ( n - 1 ) dimensional que es una cara de ambos. La conjetura de Keller es la afirmación de que cada mosaico de cubos tiene al menos un par de mosaicos que se encuentran cara a cara de esta manera. [1]
La versión original de la conjetura de Keller era una afirmación más fuerte: cada mosaico de cubos 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. [2] Es una parte necesaria de la conjetura que los cubos en el mosaico sean todos congruentes entre sí, porque si se permiten cubos de tamaños desiguales, entonces el mosaico pitagórico formaría un contraejemplo en dos dimensiones.
La conjetura, tal como se dijo, no requiere que todos los cubos en un mosaico se encuentren cara a cara con otros cubos. Aunque los mosaicos de cuadrados congruentes en el plano tienen la propiedad más fuerte de que cada cuadrado se encuentra de borde a borde con otro cuadrado, algunos mosaicos en mosaicos de hipercubo de dimensiones superiores pueden no encontrarse cara a cara con ningún otro mosaico. Por ejemplo, en tres dimensiones, la estructura tetrastix formada por tres conjuntos perpendiculares de prismas cuadrados se puede utilizar para construir un mosaico de cubos, combinatoriamente equivalente a la estructura Weaire-Phelan , en la que una cuarta parte de los cubos (los que no forman parte de ningún prisma) están rodeados por otros doce cubos sin encontrarse con ninguno de ellos cara a cara. [3]
Reformulación de la teoría de grupos
Perron ( 1940a , 1940b ) demostró que la conjetura de Keller es cierta en dimensiones como máximo seis . 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 en la geometría de los mosaicos en un problema en la teoría de grupos y, de ahí, en un problema en la teoría de grafos . [1]
Hajós (1949) reformuló por primera vez la conjetura de Keller en términos de factorizaciones de grupos abelianos . Muestra que si hay un contraejemplo de la conjetura, entonces se puede suponer que es un mosaico periódico de cubos con una longitud de lado entera y posiciones de vértice enteras; así, al estudiar la conjetura, es suficiente considerar teselaciones de esta forma especial. En este caso, el grupo de traslaciones enteras, módulo las traslaciones que preservan el mosaico, forma un grupo abeliano, y ciertos elementos de este grupo corresponden a las posiciones de los mosaicos. Hajós define 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 una 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 , 2 g i , 3 g 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 de diferencias de A 0 consigo mismo). [1]
Szabó (1986) mostró que se puede suponer que cualquier mosaico que forme un contraejemplo de la conjetura tiene una forma aún más especial: los cubos tienen una longitud de lado de una potencia de dos y coordenadas de vértice enteras, y el mosaico es periódico con un punto dos veces el lado longitud de los cubos en cada dirección de coordenadas. Basado 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 las sumas directas de grupos cíclicos de orden cuatro, con cada q i = 2 .
Gráficos de Keller
Corrádi y Szabó (1990) reformularon el resultado de Szabó como una condición sobre la existencia de una gran camarilla en una determinada familia de grafos, que posteriormente se conocieron como grafos de Keller . Más precisamente, los vértices de la gráfica de Keller de dimensión n son los 4 n elementos ( 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 máxima en este gráfico tiene un tamaño como máximo de 2 ny si hay una camarilla de este tamaño, entonces la conjetura de Keller es falsa. Dada tal camarilla, se puede formar una cubierta de espacio por cubos del lado dos cuyos centros tienen coordenadas que, cuando se toman 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 mosaico tienen el mismo volumen total que el período en sí. Junto con el hecho de que no se superponen, esto implica que los cubos colocados de esta manera embaldosan el espacio sin encontrarse cara a cara. [4]
Lagarias y Shor ( 1992 ) refutaron la conjetura de Keller al encontrar una camarilla de tamaño 2 10 en el gráfico de Keller de dimensión 10. Esta camarilla conduce a un mosaico no cara a cara en la dimensión 10, y se pueden apilar copias de él ( compensado por media unidad en cada dirección de coordenadas) para producir mosaicos no cara a cara en cualquier dimensión superior. De manera similar, Mackey (2002) encontró una camarilla de tamaño 28 en el gráfico de Keller de dimensión ocho, conduciendo de la misma manera a un mosaico no cara a cara en la dimensión 8 y (por apilamiento) en la dimensión 9.
Posteriormente, Debroni et al. (2011) mostraron que la gráfica Keller de dimensión siete tiene una camarilla máximo de tamaño 124 <2 7 . Debido a que este es menor que 2 7 , la versión gráfica de teoría de la conjetura de Keller es cierto en siete dimensiones. Sin embargo, la traslación de los mosaicos de cubos a la teoría de grafos puede cambiar la dimensión del problema, por lo que este resultado no establece la versión geométrica de la conjetura en siete dimensiones. Finalmente, una prueba asistida por computadora de 200 gigabytes en 2019 utilizó gráficos de Keller para establecer que la conjetura es cierta en siete dimensiones. [5] Por lo tanto, la pregunta que planteó Keller puede considerarse resuelta: la conjetura es verdadera en siete dimensiones o menos, pero es falsa cuando hay más de siete dimensiones. [6]
Los tamaños de las camarillas máximas en los gráficos de Keller de las dimensiones 2, 3, 4, 5 y 6 son, respectivamente, 2, 5, 12, 28 y 60. Los gráficos de Keller de las dimensiones 4, 5 y 6 han sido incluido en el conjunto de "gráficos de desafío DIMACS" que se utilizan con frecuencia como punto de referencia para los algoritmos de búsqueda de camarillas . [7]
Problemas relacionados
Como describe Szabó (1993) , Hermann Minkowski fue llevado a un caso especial de la conjetura del mosaico de cubos a partir de un problema de aproximación diofántica . Una consecuencia del teorema de Minkowski es que cualquier retícula (normalizada para tener un determinante uno) debe contener un punto distinto de cero cuya distancia de Chebyshev al origen sea como máximo uno. Las celosías que no contienen un punto distinto de cero con una distancia de Chebyshev estrictamente menor que uno se denominan críticas , y los puntos de una celosía crítica forman los centros de los cubos en un mosaico de cubos. Minkowski conjeturó en 1900 que siempre que un mosaico de cubos tiene sus cubos centrados en puntos de celosía 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 celosía) cada cubo en el mosaico debe ser parte de una columna de cubos, y las secciones transversales de estas columnas forman un mosaico de cubos de una dimensión más pequeña. Razonando de esta manera, Minkowski demostró que (asumiendo la verdad de su conjetura) cada retícula 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 teórico de grupos similar al que luego aplicaría a la conjetura más general de Keller. [8]
La conjetura de Keller es una variante de la conjetura de Minkowski en la que se relaja la condición de que los centros del cubo formen una red. Una segunda conjetura relacionada, hecha por Furtwängler en 1936, en cambio relaja la condición de que los cubos formen un mosaico. Furtwängler preguntó si un sistema de cubos centrados en puntos de celosía que forman un k- pliegue que cubre el espacio (es decir, todos los puntos del espacio, excepto un subconjunto de medida cero, deben ser interiores a exactamente k cubos) necesariamente debe 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 la dimensión n que permiten un contraejemplo. Además, combinando las conjeturas de Furtwängler y Keller, Robinson mostró que las cubiertas cuadradas k -fold del plano euclidiano deben incluir dos cuadrados que se encuentran de borde a borde. Sin embargo, para cada k > 1 y cada n > 2 , hay un mosaico de k- pliegues del espacio n -dimensional por cubos sin caras compartidas. [9]
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 exista en un mosaico de cubos. Cuando la dimensión n es como máximo siete, esta dimensión máxima es simplemente n - 1 , según las pruebas de la conjetura de Keller para esas dimensiones pequeñas, y cuando n es al menos ocho, entonces esta dimensión máxima es como máximo n - 2 . Lagarias y Shor (1994) demostraron que es como máximo n - √ n / 3 , más fuerte para diez o más dimensiones.
Iosevich y Pedersen (1998) y Lagarias, Reeds y Wang (2000) encontraron estrechas conexiones entre las teselaciones del cubo y la teoría espectral de funciones cuadradas integrables en el cubo.
Dutour Sikirić, Itoh y Poyarkov (2007) usan camarillas en los gráficos de Keller que son máximas pero no máximas para estudiar empaquetaduras de cubos en el espacio que no se puede extender agregando cubos adicionales.
En 1975, Ludwig Danzer e independientemente Branko Grünbaum y GC Shephard encontraron un mosaico de espacio tridimensional por paralelepípedos con ángulos de cara de 60 ° y 120 ° en el que no hay dos paralelepípedos que compartan una cara. [10]
Notas
- ↑ a b c Szabó (1993) ; Shor (2004) ; Zong (2005)
- ^ Łysakowska y Przesławski ( 2011 , 2012 ).
- ^ Conway, Burgiel y Goodman-Strauss (2008) .
- ^ Corrádi y Szabó (1990) .
- ^ Brakensiek y col. (2020) .
- ^ Hartnett (2020) .
- ^ Johnson y truco (1996) ; Debroni y col. (2011) , "Los gráficos de Keller se encuentran en el conjunto de referencia de problemas de camarillas del desafío de camarillas de DIMACS, y parecen ser especialmente difíciles para los algoritmos de camarillas".
- ^ Szabó (1993) .
- ^ Szabó (1982) .
- ^ Grünbaum y Shephard (1980) .
Referencias
- Brakensiek, Joshua; Heule, Marijn ; Mackey, John; Narváez, David (2020), "La resolución de la conjetura de Keller", en Peltier, Nicolas; Sofronie-Stokkermans, Viorica (eds.), Automated Reasoning: 10th International Joint Conference, IJCAR 2020, París, Francia, 1 al 4 de julio de 2020, Actas, Parte I , Lecture Notes in Computer Science, 12166 , Springer, págs. 48 –65, arXiv : 1910.03740 , doi : 10.1007 / 978-3-030-51074-9_4 , S2CID 203951899
- Conway, John H .; Burgiel, Heidi; Goodman-Strauss, Chaim (2008), "Comprensión de las burbujas irlandesas", Las simetrías de las cosas , Wellesley, Massachusetts: AK Peters, p. 351, ISBN 978-1-56881-220-5, MR 2410150
- Corrádi, K .; Szabó, S. (1990), "Un enfoque combinatorio para la conjetura de Keller", Periodica Mathematica Hungarica. Revista de la Sociedad Matemática János Bolyai , 21 (2): 95–100, doi : 10.1007 / BF01946848 , MR 1070948 , S2CID 121453908.
- Debroni, Jennifer; Eblen, John D .; Langston, Michael A .; Shor, Peter ; Myrvold, Wendy ; Weerapurage, Dinesh (2011), "Una resolución completa del problema de la camarilla máxima de Keller" (PDF) , Actas del 22 ° Simposio ACM-SIAM sobre algoritmos discretos , págs. 129-135, doi : 10.1137 / 1.9781611973082.11 , hdl : 1721.1 / 81184 , S2CID 15797721.
- Dutour Sikirić, Mathieu; Itoh, Yoshiaki; Poyarkov, Alexei (2007), "Empaquetaduras de cubo, segundo momento y agujeros", European Journal of Combinatorics , 28 (3): 715–725, arXiv : math / 0509100 , doi : 10.1016 / j.ejc.2006.01.008 , MR 2300752 , S2CID 15876010.
- Grünbaum, Branko ; Shephard, GC (1980), "Tilings with congruent tiles", Bulletin of the American Mathematical Society , 3 (3): 951–973, doi : 10.1090 / S0273-0979-1980-14827-2 , MR 0585178.
- 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 (19 de agosto de 2020), "La búsqueda informática resuelve un problema matemático de 90 años" , Revista Quanta.
- Iosevich, Alex; Pedersen, Steen (1998), "Spectral and Tiling properties of the unit cube", International Mathematics Research Notices , 1998 (16): 819–828, arXiv : math / 0104093 , doi : 10.1155 / S1073792898000506 , MR 1643694 , S2CID 14232561.
- Johnson, David S .; Trick, Michael A. (1996), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, 11-13 de octubre de 1993 , Boston, MA, EE. UU .: 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 gráficos de Keller incluidos en este conjunto de desafíos.
- Keller, O. -H. (1930), "Über die lückenlose Erfüllung des Raumes mit Würfeln", Journal für die reine und angewandte Mathematik (en alemán), 1930 (163): 231–248, doi : 10.1515 / crll.1930.163.231 , JFM 56.1120.01 , S2CID 199547028.
- Lagarias, Jeffrey C .; Reeds, James A .; Wang, Yang (2000), "Bases ortonormales de exponenciales para la-cube ", Duke Mathematical Journal , 103 (1): 25–37, CiteSeerX 10.1.1.207.4194 , doi : 10.1215 / S0012-7094-00-10312-2 , MR 1758237.
- Lagarias, Jeffrey C .; Shor, Peter W. (1992), "La conjetura del mosaico de cubos de Keller es falsa en dimensiones elevadas", Boletín de la American Mathematical Society , New Series, 27 (2): 279-283, arXiv : math / 9210222 , Bibcode : 1992math ..... 10222L , doi : 10.1090 / S0273-0979-1992-00318-X , MR 1155280 , S2CID 6390600.
- Lagarias, JC ; Shor, PW (1994), "Cubo-mosaicos dey códigos no lineales ", Geometría discreta y computacional , 11 (4): 359–391, doi : 10.1007 / BF02574014 , MR 1273224.
- Łysakowska, Magdalena; Przesławski, Krzysztof (2011), "Sobre la estructura de los mosaicos de cubos y los sistemas no extensibles de cubos en dimensiones bajas", European Journal of Combinatorics , 32 (8): 1417–1427, doi : 10.1016 / j.ejc.2011.07.003.
- Łysakowska, Magdalena; Przesławski, Krzysztof (2012), "la conjetura de Keller sobre la existencia de columnas en mosaicos de cubos", Avances en geometría , 12 (2): 329–352, arXiv : 0809.1960 , doi : 10.1515 / advgeom.2011.055 , MR 2911153
- Mackey, John (2002), "Un mosaico de cubos de dimensión ocho sin caras compartidas", Geometría discreta y computacional , 28 (2): 275-279, doi : 10.1007 / s00454-002-2801-9 , MR 1920144.
- Perron, Oskar (1940a), "Über lückenlose Ausfüllung des-dimensionalen Raumes durch kongruente Würfel ", Mathematische Zeitschrift , 46 : 1–26, doi : 10.1007 / BF01181421 , MR 0003041 , S2CID 186236462.
- Perron, Oskar (1940b), "Über lückenlose Ausfüllung des-dimensionalen Raumes durch kongruente Würfel. II ", Mathematische Zeitschrift , 46 : 161–180, doi : 10.1007 / BF01181436 , MR 0006068 , S2CID 123877436.
- Robinson, Raphael M. (1979), "Múltiples teselaciones de-espacio dimensional por unidad de cubos ", Mathematische Zeitschrift , 166 (3): 225–264, doi : 10.1007 / BF01214145 , MR 0526466 , S2CID 123242152.
- Shor, Peter (2004), las conjeturas del mosaico de cubos de Minkowski y Keller , notas de la conferencia para la serie de conferencias de matemáticas de la IAP.
- Szabó, Sándor (1982), "Mosaicos múltiples por cubos sin caras compartidas" (PDF) , Aequationes Mathematicae , 25 (1): 83–89, doi : 10.1007 / BF02189600 , MR 0716380 , S2CID 122364522.
- Szabó, Sándor (1986), "Una reducción de la conjetura de Keller", Periodica Mathematica Hungarica. Revista de la Sociedad Matemática János Bolyai , 17 (4): 265-277, doi : 10.1007 / BF01848388 , MR 0866636 , S2CID 120163301.
- Szabó, Sándor (1993), "Los mosaicos de cubos como contribuciones del álgebra a la geometría" , Beiträge zur Algebra und Geometrie , 34 (1): 63–75, MR 1239279.
- Zong, Chuanming (2005), "What is know about unit cubes", Bulletin of the American Mathematical Society , New Series, 42 (2): 181–211, doi : 10.1090 / S0273-0979-05-01050-5 , MR 2133310.