Ads-728

Ads-728

Psicología

Astrofísica

Genética

Neurociencia

» » Nueva herramienta para ayudar a los matemáticos con el problema del empaquetado

por Natalie Wolchover, 20 de diciembre 2013

En el período previo al lanzamiento de la nave espacial gemela Voyager en 1977, los ingenieros de la NASA se enfrentaron a una difícil pregunta: Cuando las sondas lleguen a Júpiter y Saturno, ¿cómo iban a transmitir fotos a color a la Tierra usando aproximadamente la potencia de una bombilla?

Una fotografía a color de Saturno y sus lunas tomadas por la nave espacial Voyager 1 el 3 de noviembre de 1980, y transmitida a la Tierra utilizando un código binario de 24 bits. crédito NASA/JPL
Era una tarea que requería extrema parsimonia: Cada imagen tendría que ser convertida en una serie de secuencias binarias de 24 bits, llamadas "palabras código", y transmitidas al espacio a través de ondas de radio que significaban cada 1 ó 0 por la posición de su picos y valles. Pero la transmisión de datos es ruidosa. A medida que estas palabras codificadas viajaban hacia la Tierra, los ingenieros sabían algunos 1 se distorsionarían en 0 y algunos 0 en 1. Para reconstruir las icónicas fotos de la Voyager, que debían ser capaces de corregir el código.

Las sondas Voyager tendrían que usar las palabras código cuyas secuencias fueran lo suficientemente distintas para ser reconocibles, incluso con unos pocos bits dañados. Usar las menos palabras código posibles proporcionaría mayores posibilidades dentro del límite de los 24 bits, lo que permitiría la transmisión de datos más rápida. Estas necesidades se traducen en un problema de geometría donde los bits se corresponden a unas coordenadas espaciales, con cada palabra código en el punto central de una esfera de un espacio 24-dimensional. Si las esferas se superponían, las palabras código asociadas ya no serían reconocibles de forma única. Para optimizar la cantidad de datos que puede ser transmitida y luego corregida, la cuestión se convirtió en, ¿qué densidad debían tener las esferas empaquetadas en un espacio 24-dimensional?

"El problema de la corrección de errores de los canales de comunicación ruidosos, es exactamente el problema del empaquetamiento de esferas", señaló Henry Cohn, un matemático de Microsoft Research de Nueva Inglaterra en Cambridge, Mass.

El problema del empaquetamiento de esferas subyace a casi todas las comunicaciones y almacenamientos digitales, desde teléfonos celulares y CDs hasta Internet. Pero los códigos óptimos para estas formas de transmisión se corresponden con un empaquetamiento más denso de esferas en dimensiones que están más allá de las tres clásicas de la experiencia cotidiana, y los problemas relativos a dimensiones superiores han demostrado ser formidables. Aún más difíciles de resolver son los de empaquetamiento más denso de esferas de diferentes tamaños o formas más vanguardistas, los problemas de dos y tres dimensiones ya son relevantes para la ciencia de materiales y la fabricación industrial. Los matemáticos han lidiado con estos problemas de empaquetado durante siglos, atraídos por la dificultad problemática así como por sus aplicaciones en el mundo real, pero cada caso ha inducido su propio tipo especial de dolor de cabeza. "Es ridículo", dijo Cohn. "Nosotros no sabemos siquiera la mejor manera de hacer las maletas para el avión."

Frank Vallentin, profesor de matemáticas
aplicadas y ciencias de la computación
en la Universidad de Colonia en Alemania.
Cortesía de Frank Vallentin.
Ahora, una nueva técnica computacional ha permitido avances en un número importante de casos que habían resistido el progreso durante décadas. Los matemáticos Christine Bachoc de la Universidad de Burdeos en Francia, y Frank Vallentin de la Universidad de Colonia en Alemania, desarrollaron una herramienta en 2008, llamada "límites de programación semidefinidos",  esbozado en un documento anterior por Alexander Schrijver, de la Universidad de Amsterdam en los Países Bajos. Esta técnica proporciona estimaciones generales sobre el empaquetamiento más denso de los objetos, a través de la identificación de un límite superior que se puede bajar gradualmente hasta la solución exacta, de forma que el cálculo del límite se vuelve cada vez más detallado. La herramienta está produciendo nuevos conocimientos sobre la geometría subyacente a los problemas de empaquetado, ayudando a abordar si la simetría es la característica central del más denso empaquetado.


Thomas Hales, en la foto en 1998,
proveyó de una famosa conjetura sobre
la forma más densa de empacar esferas.
Fotografía Michigan
Vallentin, que es profesor de matemáticas aplicadas y ciencias de la computación, y sus colegas, utilizaron recientemente la programación semidefinida para bajar el techo del empaquetamiento más denso de pentágonos en dos dimensiones espaciales y de esferas en cuatro, cinco, seis, siete y nueve dimensiones. "Este fue un verdadero avance que nos dejaba ir más allá de las técnicas analíticas que teníamos anteriormente", subrayó Cohn, quien co- descubrió los mejores límites anteriores en esas dimensiones.
Los problemas de empaquetamiento son de los más antiguos de la geometría. En siglos de esfuerzo se ha conseguido demostrar que a pesar de que estos problemas son fáciles de entender y fáciles de adivinar, son casi imposibles de resolver con rigor mediante las leyes de las matemáticas. Johannes Kepler conjeturó en 1611 que la disposición más densa de esferas en tres dimensiones es la forma en que se apilan naranjas en una caja, conocido como el empaquetado cúbico centrado en las caras. Esta disposición, que llena ligeramente más de un 74 por ciento de espacio, es obviamente correcta, pero con un número infinito de posibles disposiciones de esferas el problema empuja el poder de la lógica matemática hasta sus límites: Sólo en 1998 el matemático Thomas Hales demostró rigurosamente la conjetura de Kepler y su prueba involucró 50.000 líneas de código informático.

La programación semidefinida mejora una técnica llamada de programación lineal, que procuraba descubrir el límite superior por elección. Con la programación lineal, los investigadores enumeraban las restricciones sobre las posibles correlaciones entre pares de objetos, la regla era que ambas esferas no podía ser inferior al doble de su radio de distancia. Un algoritmo buscaba entonces la mayor densidad que satisficiera la lista de restricciones, produciendo un límite superior al descartar una gama de densidades. En la programación semidefinida, la lista también puede incluir limitaciones a triples, cuádruples o más grandes colecciones de objetos, proporcionando una descripción más rica de la geometría que produce mejores límites.

"La gran disyuntiva está entre la complejidad de los límites y lo cerca que esperamos que vengan a ser verdaderos", explicó Cohn .

La nueva herramienta ya ha permitido a los investigadores mejorar la optimización de los códigos binarios similares al utilizado por la nave espacial Voyager. En un par de artículos publicados en Mayo de 2012 y noviembre de 2013 en IEEE Transactions on Information Theory, dos grupos han mejorado los límites de los códigos con un rango de longitud de 18 a 28 bits.

Pero aparte de la comunicación en el espacio profundo, los códigos de esas longitudes tienen sólo unas pocas aplicaciones. La mayoría de transmisión digital moderna implica paquetes de datos mucho mayores, y la eficiencia de la transmisión corresponde al empaquetado de esferas en cientos o miles de dimensiones espaciales. En esos casos, el saber sobre el empaquetado más denso conocido —según conjeturaron en 2006 los profesores Salvatore Torquato y Frank Stillinger, de la Universidad de Princeton—, es escaso, con esferas que rellenan sólo unas milésimas de un porcentaje del espacio. "No hay pruebas en dimensiones más altas donde el empaquetado sea más denso", dijo Torquato. "Existe la posibilidad de que a medida que aumenta la dimensionalidad del espacio, vaya terminando el desorden, y el empaquetamiento más denso vaya venciendo a la disposición azarosa."

Una disposición de pentágonos que se cree,
aunque no está probado, que es el más
denso posible. crédito Toby Hudson.
Las disposiciones desordenadas son difíciles de definir matemáticamente y usar los códigos de corrección de errores. Los investigadores se han esforzado por encontrar una densa retícula simétrica de las esferas en las altas dimensiones una vez que, el matemático estadounidense Claude Shannon descubrió la relevancia del problema de la transmisión de datos en su ya clásico estudio de 1948 que fundó la teoría de la información. Los límites de programación semidefinida podría ser un enfoque útil para determinar las densidades aproximadas que podrían ser alcanzables, señalaron Vallentin y otros investigadores.

La herramienta también está ayudando a desgranar los problemas de empaquetamiento más generales. Vallentin y sus colegas aplicaron su algoritmo recientemente a fin de encontrar algunos de los primeros límites superiores sobre el empaque más denso de esferas en dos diferentes tamaños, un problema de interés para el estudio de los cristales y de códigos en los que algunos mensajes son más importantes que otros. También demostraron que los pentágonos que no pueden llenar más del 98 por ciento de un espacio de dos dimensiones.

"La obtención de límites superiores para este tipo de problemas ha sido extraordinariamente difícil", resaltó Yoav Kallus, físico en Princeton. Hace tres años, Kallus y sus colaboradores probaron que los objetos piramidales llamados tetraedros no pueden llenar más del 99,99999999999999999999999974 por ciento del espacio. "Obviamente, no esperamos que el empaquetamiento llegue tan alto", dijo. "Es tan difícil de conseguir como cualquier límite superior."

Vallentin está perfeccionando su algoritmo con la esperanza de reducir finalmente el límite de tetraedros que más se acerque a la densidad óptima. (Hasta ahora, la disposición más densa conocida, +descubierta en 2010++ por Sharon Glotzer, y sus colegas de la Universidad de Michigan, llena el 85,63 por ciento de espacio). Este algoritmo, a su vez, se aplicaría a una variedad de otras formas. "El objetivo final es que usted da al ordenador su forma, y el equipo le devuelve un límite superior con una densidad de empaquetamiento que resulte razonable", dijo Vallentin .

Teniendo en cuenta la complejidad de los problemas de empaquetamiento en dos y tres dimensiones, ¿cómo fueron las sondas Voyager capaces de transmitir fotos utilizando las palabras código de 24-dimensiones? Por suerte para la NASA, entre el puñado de problemas de empaquetado que se han resuelto está el caso especial de los entramados de esferas en 24 dimensiones. "En la dimensión-24, hay un entramado sorprendentemente simétrico y denso llamado el 'entramado Leech’, dijo Torquato. Descubierto en 1960 por el matemático británico John Leech, esta cómodo disposición de esferas dio a la sonda Voyager una rica paleta de 4.096 palabras código para usar durante la transmisión de datos. Pero el entramado Leech hace mucho más que representar el empaquetado más denso de esferas en 24 dimensiones, pertenece a una nueva clase de estructuras geométricas que son disposiciones preferidas de objetos que interactúan en una variedad de formas, no solamente como esferas que no pueden superponerse. Estos "optimos universales" son "las más interesantes y las más bellas e importantes estructuras", señaló Cohn, que los estudia con su colaborador Abhinav Kumar, profesor asociado de matemáticas en el Instituto de Tecnología de Massachusetts.

La óptima universal exhibe ciertas propiedades milagrosas, como llama Cohn al fenómeno de no quedarse estancado. Consideremos la posibilidad de encontrar el empacaje más denso de círculos en un plano. Podríamos empezar por dibujar un círculo en el centro de una hoja de papel e encajando tantos círculos adicionales alrededor de ella como sea posible. Pronto descubriremos que seis círculos forman un hexágono apretado alrededor del central. No hay razón alguna para pensar que este patrón continúe así (si estuvieras dibujando pentágonos, por ejemplo, sólo podrías dibujar un anillo de vecinos antes de que aparecían torpes vacíos), pero resulta que usted puede seguir añadiendo círculos de acuerdo con el patrón hexagonal sin meterse en problemas. "Esto es algo funciona", dijo Cohn.

Esta rara característica de la red hexagonal de dos dimensiones, ejemplificada por planos continuos de nidos de abeja, es compartida por el entramado de Leech en 24 dimensiones, y una estructura llamada el entramado E8, en ocho dimensiones. Aunque es imposible de visualizar, estos entramados son, matemáticamente, tanto o más fáciles de construir. "Todo acaba en su sitio", explicaba Cohn. "El patrón solamente sigue su camino como cabría desear. Nunca quedas atascado."

Henry Cohn, investigador principal y miembro
fundador de Microsoft Research de Nueva
Inglaterra, en Cambridge, Massachusetts,
estudia una nueva clase de estructuras
geométricas llamada "optima universal".
crédito Renate Schmid.
Esta característica está ligada a la propiedad de optimalidad universal. En los Anales de Matemáticas en 2009, Cohn y Kumar demostraron los límites superiores en ocho y 24 dimensiones, que vienen dentro de una fracción de un porcentaje de densidad de los entramados E8 y de Leech, lo que indica que son casi con toda seguridad los empaquetados más densos de esferas en sus respectivas dimensiones. Sin embargo, estos entramados también parecen ser las configuraciones óptimas en general, no sólo para las esferas, sino también para las partículas que ejercen fuerzas entre sí, como dos átomos empujándose a distancia uno a otro. Para "toda fuerza repulsiva razonable entre partículas", decía Cohn, las partículas se auto-ensamblan en un entramado hexagonal en 2-D, una entramado E8 en 8-D y un entramado Leech en 24-D. Estas disposiciones no sólo son más densas, sino "universalmente" óptimas.

Tal vez por esta razón, dichas estructuras aparecen globalmente en toda las matemáticas y en la física. "Desde la combinatoria y la teoría de grafos hasta la geometría y la geometría algebraica, y así sucesivamente, aparecen en todo lugar", dijo Kumar.

El rol que juega E8 en la teoría de cuerdas, una hipotética "teoría del todo" que dice que el espacio-tiempo es de 10 dimensiones, y que las partículas como electrones y quarks son como diminutas cuerdas unidimensionales que oscilan en diferentes frecuencias. En la década de 1980, los teóricos de cuerdas mostraron que una variante, llamada la teoría de cuerdas heterótica, podía formularse utilizando las simetrías de dos copias de E8. "Podemos producir exactamente el mundo real que conocemos a partir de la teoría de cuerdas heterótica E8", dijo Burt Ovrut, un teórico de cuerdas de la Universidad de Pennsylvania. Cuando la teoría E8 se reduce de una manera que hace que el mundo parezca tridimensional, contiene "quarks, leptones, el bosón de Higgs y todas las otras partículas que observamos."

La optimalidad universal es una idea joven, y los investigadores todavía están explorando su significado y consecuencias. Recientemente, Cohn y su ex-estudiante, Jeechul Woo, han usado los límites de programación semidefinida para descubrir una nueva optima universal, que incluye algunas disposiciones bastante menos simétricas de lo que se esperaba.

"La simetría, definitivamente, juega un papel importante", dijo Kallus, "pero creo que una de las cosas más interesantes que Henry Cohn ha demostrado es que, hay configuraciones que son óptima universal que no tienen nada de esta simetría."

Los matemáticos se han acercado a mucho problemas de empaquetamiento bajo el supuesto de que, como sabe cualquier viajero, el orden suele prevalecer sobre el desorden cuando se trata del empaquetado. El hecho es que la simetría no es toda la historia, no al menos en altas dimensiones, donde reina la aleatoriedad, ni en algunos casos de pocas dimensiones recientemente estudiados, y esto significa que los científicos pueden necesitar algún que otro principio para entender la geometría que subyace al empaquetado y su gran extensión, la optimalidad universal.

"Por el momento, creo que no hay un principio unificador fundamental", concluyó Kumar. "Creo que hay todo tipo de cosas interesantes por ahí. Estamos buscando algún sustituto de la simetría."


- Imágenes, créditos asignados en cada una de las imágenes, recogidas en la web de Quanta Magazine.
.

«
Next
Entrada más reciente
»
Previous
Entrada antigua
Editor del blog Pedro Donaire

Filosofía

Educación

Deporte

Tecnología

Materiales