Número de beso

Concepto geométrico

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 disponer en ese espacio de manera que cada una de ellas 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 empaquetamiento reticular , el número de besos es el mismo para cada esfera, pero para un empaquetamiento de esferas arbitrario, el número de besos puede variar de una esfera a otra.

Otros nombres que se han utilizado para el número del beso son número de Newton (en honor al creador del problema) y número de contacto .

En general, el problema del número de besos busca el número de besos máximo posible para esferas n -dimensionales en el espacio euclidiano ( n + 1)-dimensional . Las esferas ordinarias corresponden a superficies cerradas bidimensionales en el espacio tridimensional.

Encontrar el número de beso cuando los centros de las esferas están confinados a una línea (caso unidimensional) o a un plano (caso bidimensional) es trivial. Demostrar una solución para el 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 superiores son considerablemente más desafiantes, y solo un puñado de casos se han resuelto de manera exacta. Para otros, las investigaciones han determinado límites superiores e inferiores, pero no soluciones exactas. ^[3]

Los números de besos más grandes conocidos

Una dimensión

En una dimensión, ^[4] el número de besos es 2:

Dos dimensiones

En dos dimensiones, el número de besos es 6:

Demostración : Considérese un círculo con centro C que es tocado por círculos con centros C ₁ , C ₂ , .... Considérense los rayos C C _i . Estos rayos emanan todos del mismo centro C , por lo que la suma de los ángulos entre rayos adyacentes es 360°.

Supongamos por contradicción que hay más de seis círculos que se tocan. Entonces, al menos dos semirrectas adyacentes, digamos C C ₁ y C C ₂ , están separadas 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 ₁ C ₂ es isósceles y su tercer lado – C ₁ C ₂ – tiene una longitud de lado de menos de 2 r . Por lo tanto, los círculos 1 y 2 se intersecan – una contradicción. ^[5]

Una realización altamente simétrica del número 12 en tres dimensiones es alineando los centros de las esferas externas con los vértices de un icosaedro regular . Esto deja un poco más de 0,1 del radio entre dos esferas cercanas.

Tres dimensiones

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, con mucho espacio sobrante, y no es obvio que no haya forma de empaquetar una esfera número 13. (De hecho, hay tanto espacio adicional 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 una esfera número 13. Algunas pruebas incompletas de que Newton estaba en lo cierto se ofrecieron en el siglo XIX, la más notable fue una 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 máximo de coordinación de un átomo en una red cristalina en la que todos los átomos tienen el mismo tamaño (como en un elemento químico). El número de coordinación 12 se encuentra en una estructura compacta cúbica o hexagonal .

Dimensiones más grandes

En cuatro dimensiones, el número de besos es 24. Esto fue demostrado en 2003 por Oleg Musin. ^{[7] [8]} Anteriormente, se pensaba que la respuesta era 24 o 25: es sencillo producir un empaquetamiento de 24 esferas alrededor de una esfera central (uno puede colocar las esferas en los vértices de una celda de 24 a escala adecuada centrada en el origen), pero, como en el caso tridimensional, queda mucho espacio libre —incluso más, de hecho, que para n = 3— por lo que la situación era aún menos clara.

La existencia de la red E 8 altamente simétrica y la red Leech ha permitido obtener resultados conocidos para n = 8 (donde el número de besos es 240) y n = 24 (donde es 196.560). ^{[9] [10]} El número de besos en n dimensiones es desconocido para otras dimensiones.

Si los arreglos se restringen a arreglos reticulares , en los que los centros de las esferas se encuentran todos en puntos de un entramado , entonces este número de besos restringido se conoce para n = 1 a 9 y n = 24 dimensiones. ^[11] Para 5, 6 y 7 dimensiones, el arreglo con el número de besos más alto conocido encontrado hasta ahora es el arreglo reticular óptimo, pero no se ha excluido la existencia de un arreglo no reticular con un número de besos más alto.

Algunos límites conocidos

La siguiente tabla enumera algunos límites conocidos del número de besos en varias dimensiones. ^[12] Las dimensiones en las que se conoce el número de besos se enumeran en negrita.

Las estimaciones aproximadas del volumen muestran que el número de besos en n dimensiones crece exponencialmente en n . La base del crecimiento exponencial no se conoce. El área gris en el gráfico anterior representa los valores posibles entre los límites superior e inferior conocidos. Los círculos representan valores que se conocen con exactitud.

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 tocan una copia dada del cuerpo. Hay diferentes versiones del problema dependiendo de si solo se requiere que las copias sean congruentes con el cuerpo original, trasladadas del cuerpo original o trasladadas por una red. Para el tetraedro regular , por ejemplo, se sabe que tanto el número de besos de la red como el número de besos traslativo son iguales a 18, mientras que el número de besos congruentes es al menos 56. ^[13]

Algoritmos

Existen varios algoritmos de aproximación en gráficos de intersección donde la relación de aproximación depende del número de besos. ^[14] Por ejemplo, existe un algoritmo de aproximación de tiempo polinomial 10 para encontrar un subconjunto máximo que no se intersecte de un conjunto de cuadrados unitarios rotados.

Enunciado matemático

El problema del número de besos puede enunciarse como la existencia de una solución para un conjunto de desigualdades . Sea 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 estar alrededor de la esfera central sin superponerse es: ^[15] ${\displaystyle x_{n}}$ $${\displaystyle \exists x\ \left\{\forall _{n}\{x_{n}^{\textsf {T}}x_{n}=1\}\land \forall _{m,n:m\neq n}\{(x_{n}-x_{m})^{\textsf {T}}(x_{n}-x_{m})\geq 1\}\right\}}$$

Así, el problema para cada dimensión puede expresarse en la teoría existencial de los reales . Sin embargo, los métodos generales de resolución de problemas en esta forma requieren 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 N ( N  − 1)/2 + DN variables: ^[16] ${\displaystyle y_{nm}}$ $${\displaystyle \exists xy\ \left\{\sum _{n}\left(x_{n}^{\textsf {T}}x_{n}-1\right)^{2}+\sum _{m,n:m<n}{\Big (}(x_{n}-x_{m})^{\textsf {T}}(x_{n}-x_{m})-1-(y_{nm})^{2}{\Big )}^{2}=0\right\}}$$

Por lo tanto, resolver el caso en D  = 5 dimensiones y N  =  40  + 1 vectores equivaldría a determinar la existencia de soluciones reales para un polinomio de cuarto grado en 1025 variables. Para las D = 24 dimensiones y N  =  196560  + 1, el polinomio de cuarto grado tendría 19.322.732.544 variables. Una afirmación alternativa en términos de geometría de distancias viene dada por las distancias al cuadrado entre la esfera m ^-ésima y la n ^-ésima : ${\displaystyle R_{mn}}$ $${\displaystyle \exists R\ \{\forall _{n}\{R_{0n}=1\}\land \forall _{m,n:m<n}\{R_{mn}\geq 1\}\}}$$

Esto debe complementarse con la condición de que el determinante de Cayley-Menger sea cero para cualquier conjunto de puntos que forme un  símplex ( D + 1) en D dimensiones, ya que ese volumen debe ser cero. El establecimiento da un conjunto de ecuaciones polinómicas simultáneas en 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 . ${\displaystyle R_{mn}=1+{y_{mn}}^{2}}$

Véase también

• Dimensión equilátera
• Código esférico
• El hexlet de Soddy
• Empaque de esferas cilíndricas

Notas

1. Conway, John H. ; Neil JA Sloane (1999). Empaquetamientos de esferas, redes y grupos (3.ª ed.). Nueva York: Springer-Verlag. p. 21. ISBN 0-387-98585-9.
2. Brass, Peter; Moser, WOJ; Pach, János (2005). Problemas de investigación en geometría discreta . Springer. p. 93. ISBN 978-0-387-23815-9.
3. Mittelmann, Hans D.; Vallentin, Frank (2010). "Límites de programación semidefinida de alta precisión para números besándose". Experimental Mathematics . 19 (2): 174–178. arXiv : 0902.1105 . Bibcode :2009arXiv0902.1105M. doi :10.1080/10586458.2010.10129070. S2CID  218279.
4. Nótese que en una dimensión, las "esferas" son simplemente pares de puntos separados por la unidad de distancia. (La dimensión vertical de la ilustración unidimensional es meramente evocativa). A diferencia de lo que ocurre en dimensiones superiores, es necesario especificar que el interior de las esferas (los intervalos abiertos de longitud unitaria) no se superponen para que haya una densidad de empaquetamiento finita.
5. Véase también el Lema 3.1 en Marathe, MV; Breu, H.; Hunt, HB; Ravi, SS; Rosenkrantz, DJ (1995). "Heurísticas simples para grafos de discos unitarios". Redes . 25 (2): 59. arXiv : math/9409226 . doi :10.1002/net.3230250205.
6. Zong, Chuanming (2008). "El número de beso, 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.). Encuestas sobre geometría discreta y computacional: veinte años después (Conferencia de investigación de verano conjunta AMS-IMS-SIAM, 18-22 de junio de 2006, Snowbird, Utah) . Matemáticas contemporáneas. Vol. 453. Providence, RI: American Mathematical Society. págs. 529-548. doi :10.1090/conm/453/08812. ISBN . 9780821842393.Sr. 2405694  ..
7. OR Musin (2003). "El problema de las veinticinco esferas". Russ. Math. Surv . 58 (4): 794–795. Bibcode :2003RuMaS..58..794M. doi :10.1070/RM2003v058n04ABEH000651. S2CID  250839515.
8. Pfender, Florian; Ziegler, Günter M. (septiembre de 2004). "Números de besos, empaquetamientos de esferas y algunas pruebas inesperadas" (PDF) . Avisos de la American Mathematical Society : 873–883..
9. Levenshtein, Vladimir I. (1979). "О границах для упаковок в n -мерном евклидовом пространстве" [Sobre los límites de los embalajes en el espacio euclidiano de n dimensiones]. Doklady Akademii Nauk SSSR (en ruso). 245 (6): 1299-1303.
10. Odlyzko, AM ; Sloane, NJA (1979). "Nuevos límites en el número de esferas unitarias que pueden tocar una esfera unitaria en n dimensiones". Journal of Combinatorial Theory . Serie A. 26 (2): 210–214. doi : 10.1016/0097-3165(79)90074-8 .
11. Weisstein, Eric W. "Número de beso". MathWorld .
12. Machado, Fabrício C.; Oliveira, Fernando M. (2018). "Mejora de la cota de programación semidefinida para el número de besos explotando la simetría polinomial". Experimental Mathematics . 27 (3): 362–369. arXiv : 1609.05167 . doi :10.1080/10586458.2017.1286273. S2CID  52903026.
13. Lagarias, Jeffrey C.; Zong, Chuanming (diciembre de 2012). "Misterios en el empaquetamiento de tetraedros regulares" (PDF) . Avisos de la American Mathematical Society : 1540–1549.
14. Kammer, Frank; Tholey, Torsten (julio de 2012). "Algoritmos de aproximación para gráficos de intersección". Algorithmica . 68 (2): 312–336. doi :10.1007/s00453-012-9671-1. S2CID  3065780.
15. Los números m y n van de 1 a N. es la secuencia de los N vectores posicionales . Como la condición detrás del segundo cuantificador universal ( ) no cambia si se intercambian m y n , es suficiente dejar que este cuantificador se extienda justo sobre . Para simplificar, se supone que los radios de las esferas son 1/2. ${\displaystyle x=(x_{n})_{N}}$ ${\displaystyle \forall }$ ${\displaystyle m,n:m<n}$
16. En cuanto a la matriz, sólo se necesitan las entradas que tengan m  <  n . O, equivalentemente, se puede suponer que la matriz es antisimétrica. De todos modos, la matriz tiene sólo N ( N  − 1)/2 variables escalares libres. Además, hay N vectores D -dimensionales x _n , que corresponden a una matriz de N vectores columna. ${\displaystyle y=(y_{mn})_{N\times {N}}}$ ${\displaystyle x=(x_{nd})_{N\times D}}$

Referencias

• T. Aste y D. Weaire La búsqueda del empaquetamiento perfecto (Institute Of Physics Publishing London 2000) ISBN 0-7503-0648-3 
• Tabla de los números de besos más altos conocidos en la actualidad, mantenida por Gabriele Nebe y Neil Sloane (límites inferiores)
• Bachoc, Christine ; Vallentin, Frank (2008). "Nuevos límites superiores para números de beso a partir de programación semidefinida". Journal of the American Mathematical Society . 21 (3): 909–924. arXiv : math.MG/0608426 . Bibcode :2008JAMS...21..909B. doi :10.1090/S0894-0347-07-00589-9. MR  2393433. S2CID  204096.

Enlaces externos

• Grime, James. "Kissing Numbers" (video) . youtube . Brady Haran . Archivado desde el original el 2021-12-12 . Consultado el 11 de octubre de 2018 .