Un nuevo récord de empaquetamiento de esferas surgido de un origen inesperado

• Boaz Klartag introdujo herramientas de geometría convexa en el problema del empaquetamiento de esferas en dimensiones ultraltas, a diferencia de los enfoques previos
• El nuevo método aleatorio de Klartag genera elipsoides de mayor volumen y actualiza ampliamente los récords anteriores
• Este enfoque permite empaquetar dramáticamente más esferas en espacios de alta dimensión
• El resultado reaviva el debate sobre la importancia del orden y la simetría en el empaquetamiento
• La investigación está atrayendo atención por sus posibles aplicaciones en criptografía y comunicaciones

---

Límites de las investigaciones previas sobre empaquetamiento de esferas

• En el pasado, la ventaja del método de Rogers era que la red inicial no necesitaba ser necesariamente eficiente: bastaba con elegir un elipsoide adecuado
• Pero los ejes del elipsoide pueden deformarse de muchas maneras en alta dimensión, así que había demasiadas opciones sobre cómo hacerlo crecer
• Después, los matemáticos volvieron al enfoque de Minkowski y se concentraron en la propia red, especializándose en teoría de redes y alejándose del enfoque geométrico centrado en Rogers
• Esta estrategia mostró mejoras graduales en el empaquetamiento de esferas en alta dimensión, pero solo logró una ligera mejora de eficiencia frente al método de Rogers
• Durante décadas no hubo grandes saltos y el campo permaneció estancado

Una innovación iniciada desde una mirada externa

• Boaz Klartag, del Weizmann Institute of Science, era originalmente especialista en geometría convexa, no en teoría de redes
• Durante mucho tiempo le interesó el problema del empaquetamiento de esferas, pero no había tenido la oportunidad de investigarlo
• En 2023 consiguió nuevo tiempo para ello y abrió un seminario con Barak Weiss, de Tel Aviv University, para explorar intensivamente la literatura clásica (Minkowski, Rogers)
• Klartag juzgó que el método de elipsoides de Rogers era ineficiente por la falta de experiencia en la manipulación de cuerpos convexos
• Ganó confianza en que, si se construían elipsoides más eficientes, sería posible reescribir el récord del empaquetamiento de esferas

Introducción de un algoritmo de crecimiento aleatorio

• Klartag aplicó su propio método, que expande o contrae aleatoriamente el borde del elipsoide en cada dirección de sus ejes
• Cuando el borde toca un punto de la red, el crecimiento se detiene en esa dirección y continúa en las demás
• En este proceso, el elipsoide explora el espacio con una forma irregular y va creciendo gradualmente
• Como por su naturaleza aleatoria cada elipsoide generado tiene un volumen distinto, realizó muchos ensayos para evaluar la posibilidad de obtener elipsoides de mayor volumen
• En pocas semanas demostró que podían obtenerse elipsoides más grandes que los de Rogers

Nuevo récord e impacto

• El nuevo método basado en elipsoides logró la mayor mejora en eficiencia del empaquetamiento de esferas desde Rogers (1947)
• Cuando la dimensión es d, permite empaquetar d veces más esferas que el método anterior
  • 100 dimensiones → unas 100 veces más; 1,000,000 de dimensiones → unas 1,000,000 de veces más esferas
• Con intuiciones provenientes de la geometría convexa, Klartag rompió en pocos meses varios de los problemas centrales de larga data sobre redes y empaquetamiento de esferas
• Su logro vuelve a poner en primer plano la idea de que los empaquetamientos basados en orden y simetría pueden alcanzar la máxima densidad
• Por otro lado, también compite una línea reciente de investigación que sostiene que hay que aprovechar el desorden, sin redes regulares

Evaluación y perspectivas futuras

• Dentro de la comunidad académica hay debate sobre si el método de empaquetamiento de Klartag está realmente cerca del óptimo o si todavía hay margen para mejorarlo
• La respuesta a este problema es muy importante también en aplicaciones reales como criptografía e ingeniería de comunicaciones
• Aún no está en etapa de aplicación práctica, pero está siendo observado como una nueva tecnología en ámbitos como la ingeniería
• Klartag espera que este avance fortalezca la conexión entre geometría convexa y teoría de redes
• También desea superar la separación entre ambos campos y que esta convergencia se extienda a la solución de problemas de redes más allá del empaquetamiento

[GN⁺]

Comentarios en Hacker News

• Confesión de que siempre es difícil explicarles a los padres que tu profesión realmente existe; imaginar lo incómodo que se vuelve cuando uno dice: “estudio figuras, pero solo las que no tienen partes hundidas hacia adentro”
  • Según mi experiencia, la mejor conclusión es explicar el trabajo usando terminología difícil. Las opciones se reducen a tres: si das una explicación relativamente sencilla que tus padres puedan entender, el trabajo parece demasiado fácil y reaccionan con un “¿de verdad te pagan por eso?”; si explicas bien por qué es importante, la explicación se vuelve demasiado larga, tus padres se cansan y terminan arrepintiéndose de haber preguntado; o si lo cuentas brevemente con jerga técnica compleja, no entienden nada pero de algún modo suena impresionante. Esa es la mejor opción.
  • Tengo un microemprendimiento que fabrica piezas para equipos de física de altas energías, y cuando intento explicar a qué me dedico sigo sin encontrar una forma de hacer entender un tema que la gente nunca ha visto, que está a varias capas de distancia de la vida cotidiana y que es extremadamente extraño y de nicho.
  • Yo simplemente digo: “trabajo con computadoras”, y entonces responden “ah, claro, buen trabajo”, y la conversación termina. Muy conveniente.
  • Para mí, más que la pregunta “¿a qué te dedicas?”, lo difícil siempre es responder después “¿y eso para qué sirve / en qué se usa?”. Cómo explicar de forma breve y efectiva la larga cadena que conecta la investigación fundamental con una aplicación real.
  • Al menos el empaquetamiento de esferas (sphere packing) está muy relacionado con un problema central de la teoría de la información, y en ese sentido se puede encontrar contexto histórico e importancia en su vínculo con la mejora de la confiabilidad de Bell Telephone Systems. (Sobre cuerpos convexos no sé mucho.)
• Experiencia de haber pensado en algoritmos de compresión de datos vectoriales usando métodos de empaquetamiento de esferas (sphere packing); el enfoque teórico solo funcionaba cuando los datos eran muy uniformes, y era difícil aplicarlo a datos reales.
  • Para transformar datos irregulares (no uniformes) en algo uniforme, el truco habitual es usar conocimiento del dominio para reducir la asimetría. Por ejemplo, aunque los datos tengan estructura de alta dimensión, localmente suelen volverse bastante uniformes por el ruido. Si calculas y guardas centroides, los centroides se vuelven más uniformes, y cada vector puede almacenarse separado en un índice de centroide y un desplazamiento del vector. El índice sirve para una compresión por entropía eficiente, y el desplazamiento, al haberse vuelto casi uniforme, facilita aplicar la estrategia clásica de empaquetamiento de esferas.
  • Seguro ya lo intentaste, pero quizá valga la pena probar si una precompresión (precompression) que reduzca la dispersión del vector mejora la uniformidad.
  • Comentario en tono de broma: cuando manipules vectores reales, hay que tener cuidado (grope significa “manosear”, error tipográfico de group).
  • Se destaca la necesidad de extender el alcance de la teoría a problemas prácticos, es decir, datos no homogéneos. Si los casos de uso reales son demasiado variados, puede que un enfoque general sea difícil, pero aun así vale la pena prestar atención a esa expansión de la investigación.
  • Observación de que, en áreas antiguas y comercialmente importantes, la mayoría de los logros fáciles de obtener ya fueron cosechados.
• Coinciden con la afirmación de Klartag de que “los cuerpos convexos son muy poderosos y muy útiles”; aunque no es matemático, comparte que ha visto aparecer algoritmos de Convex Hull en lugares inesperados, especialmente en problemas como la descomposición automática de paletas de imagen, y aporta un artículo de referencia: Convex Hull and automatic palette decomposition
• El nuevo método de empaquetamiento de esferas de Klartag supuestamente permite apilar, para una dimensión d, d veces más esferas que antes; eso significaría 100 veces más en 100 dimensiones y un millón de veces más en un millón de dimensiones, una cifra enorme. Surge la duda de si esto implica en la práctica decenas o cientos de veces más ancho de banda, o una gran reducción del consumo energético, en varios sistemas de comunicación.
  • En la práctica, a medida que aumenta la dimensión, la densidad empeora exponencialmente como n^2/2^n, así que la mejora lineal teórica no se refleja completa en el rendimiento real. Es decir, puede servir para datos que naturalmente tienen estructura de alta dimensión, pero en datos digitales, donde uno puede elegir la longitud, se pueden tomar dimensiones pequeñas. Más sobre sphere packing: wikipedia link
• Idea de que un matemático debería poder obtener, algunos años después de su primer doctorado, un segundo doctorado en un área vecina y no en exactamente el mismo campo.
  • El propósito fundamental del doctorado es demostrar la capacidad de investigar de manera independiente; en la práctica, muchos investigadores cambian de área o de tema de interés después de graduarse, y a partir de ahí lo central pasa a ser la “investigación” en sí.
  • Como ejemplo real de que esto es posible, el famoso matemático Bela Bollobas tiene dos doctorados, uno en geometría discreta y otro en análisis funcional. Aun así, intentar algo así de nuevo en la academia moderna sería muy difícil.
  • Si existiera esa flexibilidad institucional en toda la ciencia, las técnicas e ideas entre campos distintos podrían intercambiarse más rápido y eso podría acelerar el progreso científico; se espera que sea especialmente útil en áreas como las matemáticas, donde las conexiones entre subdisciplinas son importantes.
• Pregunta de principiante: si el empaquetamiento óptimo de esferas (sphere packing) siempre está relacionado con una retícula regular. En 2D y 3D parece ser así, pero queda la duda de si eso se extiende a N dimensiones.
  • Además de 2 y 3 dimensiones, también hay casos en 8 dimensiones (retícula E₈) y 24 dimensiones (retícula de Leech) donde se demostró que el mejor empaquetamiento tiene forma de retícula regular. Esto fue probado en 2017 por Maryna Viazovska y colaboradores; se comparten materiales relacionados: paper 1, paper 2, explicación pdf. Pero en otras dimensiones puede haber contraejemplos donde el empaquetamiento óptimo no sea una retícula regular, y en algunas dimensiones formas irregulares pueden tener mayor densidad.
  • No necesariamente. Incluso en 3 dimensiones, además de apilar en una lattice (retícula regular), hay infinitas formas no reticulares cambiando el desplazamiento horizontal de cada capa; aun así, la densidad es la misma que la de la retícula FCC. En dimensiones altas, por la falta de simetría, incluso se conjetura que el empaquetamiento óptimo podría ser siempre no reticular.
• Curiosidad por la dimensión mínima a partir de la cual esta nueva estructura de empaquetamiento de esferas supera a las mejores densidades previamente demostradas.
• Se plantea como posible línea de desarrollo si los resultados de esta investigación podrían aplicarse en criptografía y comunicaciones para crear sistemas de comunicación más seguros, más confiables y más eficientes energéticamente; es un campo de investigación muy interesante.
• Ingeniosa analogía mencionando el “Cow Packing” en física real, como si hubiera aplicaciones prácticas para investigar cómo llenar teóricamente un espacio con vacas a densidad óptima.
• Resulta interesante que el empaquetamiento de esferas aparezca en tantos problemas distintos dentro de campos aplicados; dan ganas de leer el artículo completo.