En geometría , el número de besos de un espacio matemático se define como el mayor número de esferas unitarias no superpuestas que se pueden organizar en ese espacio de modo que cada una toque una esfera unitaria común. Para un empaquetamiento de esferas dado (disposición de esferas) en un espacio dado, también se puede definir un número de besos para cada esfera individual como el número de esferas que toca. Para un empaque de celosía, el número de besos es el mismo para todas las esferas, pero para un empaque de esfera arbitrario, el número de besos puede variar de una esfera a otra.
Otros nombres para el número de besos que se han utilizado son el número de Newton (después del origen del problema) y el número de contacto .
En general, el problema del número de besar busca el número besos máxima posible para n esferas -dimensional en ( n + 1) -dimensional espacio euclidiano . Las esferas ordinarias corresponden a superficies cerradas bidimensionales en un espacio tridimensional.
Encontrar el número de besos cuando los centros de las esferas están confinados a una línea (el caso unidimensional) o un plano (el caso bidimensional) es trivial. Probar una solución al caso tridimensional, a pesar de ser fácil de conceptualizar y modelar en el mundo físico, eludió a los matemáticos hasta mediados del siglo XX. [1] [2] Las soluciones en dimensiones más altas son considerablemente más desafiantes, y solo un puñado de casos se han resuelto con exactitud. Para otros, las investigaciones han determinado límites superiores e inferiores, pero no soluciones exactas. [3]
Números de besos más grandes conocidos
En una dimensión, [4] el número de besos es 2:
En dos dimensiones, el número de besos es 6:
Prueba : Considere un círculo con centro C que está tocado por círculos con centros C 1 , C 2 , .... Considere los rayos C C i . Todos estos rayos emanan del mismo centro C , por lo que la suma de los ángulos entre los rayos adyacentes es 360 °.
Suponga por contradicción que hay más de seis círculos en contacto. Entonces, al menos dos rayos adyacentes, digamos C C 1 y C C 2 , están separados por un ángulo de menos de 60 °. Los segmentos CC i tienen la misma longitud - 2 r - para todo i . Por lo tanto, el triángulo C C 1 C 2 es isósceles y su tercer lado, C 1 C 2 , tiene una longitud de lado menor que 2 r . Por lo tanto, los círculos 1 y 2 se cruzan, una contradicción. [5]
En tres dimensiones, el número de besos es 12, pero el valor correcto fue mucho más difícil de establecer que en las dimensiones uno y dos. Es fácil organizar 12 esferas de modo que cada una toque una esfera central, pero queda mucho espacio y no es obvio que no haya forma de empacar en una 13ª esfera. (De hecho, hay tanto espacio extra que dos de las 12 esferas exteriores pueden intercambiar lugares a través de un movimiento continuo sin que ninguna de las esferas exteriores pierda contacto con la central). Este fue el tema de un famoso desacuerdo entre los matemáticos Isaac. Newton y David Gregory . Newton pensó correctamente que el límite era 12; Gregory pensó que podría caber un 13 °. Algunas pruebas incompletas de que Newton estaba en lo cierto se ofrecieron en el siglo XIX, la más notable fue la de Reinhold Hoppe , pero la primera prueba correcta (según Brass, Moser y Pach) no apareció hasta 1953. [1] [2] [6 ]
Los doce vecinos de la esfera central corresponden al número de coordinación de volumen máximo de un átomo en una red cristalina en la que todos los átomos tienen el mismo tamaño (como en un elemento químico). Un número de coordinación de 12 se encuentra en una estructura compacta cúbica compacta o hexagonal compacta .
En cuatro dimensiones, se sabía desde hace algún tiempo que la respuesta era 24 o 25. Es sencillo producir un empaque de 24 esferas alrededor de una esfera central (se pueden colocar las esferas en los vértices de una escala centrada de 24 celdas adecuada Al origen). Como en el caso tridimensional, queda mucho espacio, incluso más, de hecho, que para n = 3, por lo que la situación era aún menos clara. En 2003, Oleg Musin demostró que el número de besos para n = 4 era 24, utilizando un truco sutil. [7] [8]
El número de besos en n dimensiones se desconoce para n > 4, excepto para n = 8 (240) y n = 24 (196,560). [9] [10] Los resultados en estas dimensiones provienen de la existencia de celosías altamente simétricas: la celosía E 8 y la celosía Leech .
Si los arreglos se limitan a arreglos de celosía , en los que los centros de las esferas se encuentran todos en puntos en un celosía , entonces este número de besos restringido se conoce para n = 1 a 9 yn = 24 dimensiones. [11] Para las dimensiones 5, 6 y 7, el arreglo con el número de besos más alto conocido encontrado hasta ahora es el arreglo de celosía óptimo, pero no se ha excluido la existencia de un arreglo sin celosía con un número de besos más alto.
Algunos límites conocidos
La siguiente tabla enumera algunos límites conocidos en el número de besos en varias dimensiones. [12] Las dimensiones en las que se conoce el número de besos se enumeran en negrita.
Dimensión | Límite inferior | Límite superior |
---|---|---|
1 | 2 | |
2 | 6 | |
3 | 12 | |
4 | 24 [7] | |
5 | 40 | 44 |
6 | 72 | 78 |
7 | 126 | 134 |
8 | 240 | |
9 | 306 | 363 |
10 | 500 | 553 |
11 | 582 | 869 |
12 | 840 | 1.356 |
13 | 1,154 [13] | 2.066 |
14 | 1.606 [13] | 3,177 |
15 | 2.564 | 4.858 |
dieciséis | 4.320 | 7.332 |
17 | 5.346 | 11,014 |
18 | 7.398 | 16,469 |
19 | 10,668 | 24,575 |
20 | 17.400 | 36,402 |
21 | 27,720 | 53.878 |
22 | 49,896 | 81,376 |
23 | 93,150 | 123,328 |
24 | 196.560 |
Generalización
El problema del número de besos se puede generalizar al problema de encontrar el número máximo de copias congruentes no superpuestas de cualquier cuerpo convexo que toque una copia determinada del cuerpo. Hay diferentes versiones del problema dependiendo de si las copias solo deben ser congruentes con el cuerpo original, traducidas del cuerpo original o traducidas por una celosía. Para el tetraedro regular , por ejemplo, se sabe que tanto el número de besos de celosía como el número de besos traducido son iguales a 18, mientras que el número de besos congruentes es al menos 56. [14]
Algoritmos
Hay varios algoritmos de aproximación en gráficos de intersección donde la relación de aproximación depende del número de besos. [15] Por ejemplo, existe un algoritmo de aproximación de 10 en tiempo polinómico para encontrar un subconjunto máximo que no se interseca de un conjunto de cuadrados unitarios rotados.
Enunciado matemático
El problema del número de besos se puede plantear como la existencia de una solución a un conjunto de desigualdades . Dejarser un conjunto de vectores de posición N D- dimensionales de los centros de las esferas. La condición de que este conjunto de esferas pueda situarse alrededor de la esfera central sin superponerse es: [16]
Así, el problema de cada dimensión puede expresarse en la teoría existencial de los reales . Sin embargo, los métodos generales para resolver problemas de esta forma toman al menos un tiempo exponencial, por lo que este problema solo se ha resuelto hasta en cuatro dimensiones. Al agregar variables adicionales,esto se puede convertir en una única ecuación cuártica en variables N ( N -1) / 2 + DN : [17]
Por tanto, resolver el caso en D = 5 dimensiones y N = 40 + 1 vectores equivaldría a determinar la existencia de soluciones reales a un polinomio cuártico en 1025 variables. Para las dimensiones D = 24 y N = 196560 + 1, el cuártico tendría 19,322,732,544 variables. Un enunciado alternativo en términos de geometría de distancia viene dado por las distancias al cuadradoentre la m ésima y la n ésima esfera:
Esto debe complementarse con la condición de que el determinante de Cayley-Menger sea cero para cualquier conjunto de puntos que forme un simplex ( D + 1) en dimensiones D , ya que ese volumen debe ser cero. Configuraciónda un conjunto de ecuaciones polinomiales simultáneas en solo y que deben resolverse solo para valores reales. Los dos métodos, al ser completamente equivalentes, tienen varios usos diferentes. Por ejemplo, en el segundo caso, se pueden alterar aleatoriamente los valores de y en pequeñas cantidades para tratar de minimizar el polinomio en términos de y .
Ver también
- Dimensión equilátera
- Código esférico
- Hechizo de soddy
- Embalaje de esfera de cilindro
Notas
- ↑ a b Conway, John H .; Neil JA Sloane (1999). Empaquetaduras, celosías y grupos de esferas (3ª ed.). Nueva York: Springer-Verlag. pag. 21 . ISBN 0-387-98585-9.
- ^ a b Latón, Peter; Moser, WOJ; Pach, János (2005). Problemas de investigación en geometría discreta . Saltador. pag. 93 . ISBN 978-0-387-23815-9.
- ^ Mittelmann, Hans D .; Vallentin, Frank (2009). "Límites de programación semidefinidos de alta precisión para besar números". Matemáticas experimentales . 19 : 174-178. arXiv : 0902.1105 . Código bibliográfico : 2009arXiv0902.1105M .
- ^ Tenga en cuenta que en una dimensión, las "esferas" son solo pares de puntos separados por la unidad de distancia. (La dimensión vertical de la ilustración unidimensional es meramente evocadora). A diferencia de las dimensiones superiores, es necesario especificar que el interior de las esferas (los intervalos abiertos de longitud unitaria) no se superponen para que haya un empaquetamiento finito densidad.
- ^ Ver también Lema 3.1 en Marathe, MV; Breu, H .; Hunt, HB; Ravi, SS; Rosenkrantz, DJ (1995). "Heurística simple para gráficos de disco unitario". Redes . 25 (2): 59. arXiv : math / 9409226 . doi : 10.1002 / net.3230250205 .
- ^ Zong, Chuanming (2008), "El número de besos, el número de bloqueo y el número de cobertura de un cuerpo convexo", en Goodman, Jacob E .; Pach, J├ínos; Pollack, Richard (eds.), Surveys on Discrete and Computational Geometry: Twenty Years Later (AMS-IMS-SIAM Joint Summer Research Conference, 18 de junio de 2006, Snowbird, Utah) , Contemporary Mathematics, 453 , Providence, RI: American Mathematical Society, págs. 529–548, doi : 10.1090 / conm / 453/08812 , ISBN 9780821842393, MR 2405694.
- ^ a b OR Musin (2003). "El problema de las veinticinco esferas". Russ. Matemáticas. Surv . 58 (4): 794–795. Código Bibliográfico : 2003RuMaS..58..794M . doi : 10.1070 / RM2003v058n04ABEH000651 .
- ^ Pfender, Florian; Ziegler, Günter M. (septiembre de 2004). "Besos números, empaquetaduras de esferas y algunas pruebas inesperadas" (PDF) . Avisos de la Sociedad Matemática Estadounidense : 873–883..
- ^ Levenshtein, Vladimir I. (1979). "О границах для упаковок в n-мерном евклидовом пространстве" [Límites para los embalajes en el espacio euclidiano n- dimensional]. Doklady Akademii Nauk SSSR (en ruso). 245 (6): 1299–1303.
- ^ Odlyzko, AM , Sloane, NJA Nuevos límites en el número de esferas unitarias que pueden tocar una esfera unitaria en n dimensiones. J. Combin. Teoría Ser. A 26 (1979), núm. 2, 210-214
- ^ Weisstein, Eric W. "Número de besos" . MathWorld .
- ^ Machado, Fabrício C .; Oliveira, Fernando M. (2018). "Mejora de la programación semidefinita enlazada para el número de besos mediante la explotación de la simetría polinomial". Matemáticas experimentales . 27 : 362–369. arXiv : 1609.05167 . doi : 10.1080 / 10586458.2017.1286273 .
- ^ a b В. А. Зиновьев, Т. Эриксон (1999).Новые нижние оценки на контактное число для небольших размерностей. Пробл. Передачи Информ. (en ruso). 35 (4): 3–11. Traducción en inglés: VA Zinov'ev, T. Ericson (1999). "Nuevos límites inferiores para números de contacto en pequeñas dimensiones". Problemas de transmisión de información . 35 (4): 287-294. Señor 1737742 .
- ^ Lagarias, Jeffrey C .; Zong, Chuanming (diciembre de 2012). "Misterios en el embalaje de tetraedros regulares" (PDF) . Avisos de la American Mathematical Society : 1540-1549.
- ^ Kammer, Frank; Tholey, Torsten (julio de 2012). "Algoritmos de aproximación para gráficos de intersección". Algoritmica . 68 (2): 312–336. doi : 10.1007 / s00453-012-9671-1 .
- ^ Números m y n van de 1 a N .es la secuencia de los N vectores posicionales. Como condición detrás del segundo cuantificador universal () No cambia si m y n se intercambian, es suficiente para dejar que este Quantor se extienden un poco más de. Para simplificar, se supone que los radios de las esferas son 1/2.
- ^ Sobre la matrizsólo se necesitan las entradas que tengan m < n . O, equivalente, se puede suponer que la matriz es antisimétrica. De todos modos, la matriz tiene solo N ( N - 1) \ 2 variables escalares libres. Además, existen N D -vectores dimensionales x n , que corresponden a una matrizde N vectores de columna.
Referencias
- T. Aste y D. Weaire The Pursuit of Perfect Packing (Institute of Physics Publishing London 2000) ISBN 0-7503-0648-3
- Tabla de los números de besos más altos actualmente conocidos mantenida por Gabriele Nebe y Neil Sloane (límites inferiores)
- Bachoc, Christine ; Vallentin, Frank (2008), "Nuevos límites superiores para besar números de programación semidefinida", Journal of the American Mathematical Society , 21 (3): 909–924, arXiv : math.MG/0608426 , doi : 10.1090 / S0894-0347 -07-00589-9 , MR 2393433
enlaces externos
- Grime, James. "Kissing Numbers" (video) . youtube . Brady Haran . Consultado el 11 de octubre de 2018 .