Un nuevo récord de empaquetamiento de esferas surgido de un lugar inesperado
(quantamagazine.org)- En el problema de empaquetamiento de esferas en altas dimensiones, Boaz Klartag publicó en línea en abril un breve manuscrito con la mayor mejora de eficiencia desde Claude Ambrose Rogers en 1947
- El nuevo método parte de una retícula arbitraria, construye un elipsoide más grande y luego usa el procedimiento de Rogers para construir un empaquetamiento denso de esferas, reviviendo un enfoque geométrico que había quedado relegado durante un tiempo
- La construcción de Klartag permite empaquetar, en dimensión d, aproximadamente d veces más esferas que muchos resultados anteriores; eso equivale a unas 100 veces en 100 dimensiones y a cerca de un millón de veces en un millón de dimensiones
- A diferencia del debate sobre la posibilidad de empaquetamientos desordenados, que creció tras el récord no reticular de 2023, este resultado muestra que el orden y la simetría aún podrían ser candidatos fuertes en los empaquetamientos óptimos de altas dimensiones
- Aunque el problema de empaquetamiento de esferas es importante para aplicaciones en criptografía y comunicaciones, este resultado no tiene una aplicación inmediata y podría servir para volver a conectar la geometría convexa y la teoría de retículas
Un gran avance en el empaquetamiento de esferas de altas dimensiones
- El problema de empaquetamiento de esferas consiste en encontrar la manera de llenar un espacio de alta dimensión con bolas de la forma más eficiente posible
- Este problema ha atraído a matemáticos durante siglos y tiene posibles aplicaciones importantes en criptografía y comunicaciones de larga distancia
- A comienzos del siglo XVII, Johannes Kepler mostró que, si se apilan esferas tridimensionales como naranjas en una tienda de comestibles, pueden ocupar alrededor del 74% del espacio, y conjeturó que eso era óptimo
- Esta conjetura recién se demostró casi 400 años después
- En dimensiones más altas, salvo en las dimensiones 8 y 24, todavía no se conoce la respuesta óptima
- Durante mucho tiempo, los matemáticos han buscado mejores empaquetamientos, pero las mejoras han sido pequeñas y poco frecuentes
- Boaz Klartag, en un breve manuscrito publicado en abril, superó ampliamente el récord anterior, y algunos investigadores consideran que este resultado podría estar cerca de ser óptimo
Una vieja idea que va de las retículas a los elipsoides
- En 1905, Hermann Minkowski estableció una forma de pensar el empaquetamiento de esferas mediante retículas (lattices)
- Consiste en crear un arreglo de puntos que se repite en el espacio y dibujar una esfera alrededor de cada punto
- El problema de encontrar el empaquetamiento óptimo de esferas en una dimensión determinada se convierte en el problema de encontrar la retícula cuyos puntos estén dispuestos de la forma más eficiente
- En dos dimensiones, la retícula hexagonal es óptima
- En 1947, Claude Ambrose Rogers propuso otra perspectiva
- Se puede empezar incluso con una retícula arbitraria que no sea óptima
- En lugar de dibujar una esfera en cada punto, se dibuja un elipsoide alrededor de un punto, de modo que su superficie toque otros puntos de la retícula sin sobrepasarlos
- A partir de ese elipsoide, presentó un algoritmo para construir un empaquetamiento denso de esferas
- La ventaja del método de Rogers es que la retícula inicial no necesita ser especialmente eficiente
- Si se elige el elipsoide correcto, se puede construir un empaquetamiento eficiente de esferas
- Pero los elipsoides son más difíciles de manejar que las esferas
- Una esfera queda determinada por un solo radio, mientras que un elipsoide se define por varios ejes de distintas longitudes
- A medida que aumenta la dimensión, crecen rápidamente las direcciones en las que puede estirarse y las formas posibles
- Con el tiempo, los matemáticos volvieron al enfoque reticular de Minkowski y se concentraron más en la teoría de retículas, alejándose del enfoque geométrico de Rogers
- Esa estrategia también mejoró el empaquetamiento de esferas en altas dimensiones, pero la mayoría de las mejoras fueron menores que la del empaquetamiento de Rogers
Un investigador de geometría convexa revive el enfoque de Rogers
- Klartag es matemático del Weizmann Institute of Science y se dedica principalmente a la geometría convexa (convex geometry)
- Una figura convexa es una figura que no tiene hendiduras hacia adentro
- En altas dimensiones incluye diversas simetrías, y Klartag ve estas figuras como herramientas matemáticas poderosas
- Tenía interés en las retículas y el empaquetamiento de esferas, pero no había tenido tiempo de estudiar a fondo ese campo
- En noviembre del año pasado, después de terminar un proyecto importante, su agenda se liberó y le pidió a Barak Weiss, de Tel Aviv University, mentoría para aprender una nueva área
- Weiss inició un pequeño seminario en el que Klartag y algunas otras personas leían la bibliografía
- Klartag leyó en detalle los métodos de empaquetamiento de esferas de Minkowski y Rogers
- Después de leer cómo Rogers convertía un elipsoide en un empaquetamiento de esferas, Klartag se preguntó por qué los matemáticos habían abandonado ese método
- Como los elipsoides son figuras convexas, Klartag contaba con métodos sofisticados para manipularlos
- Consideró que el elipsoide inicial usado por Rogers era intuitivo, pero ineficiente
- Si podía construir un elipsoide de mayor volumen, podía establecer un nuevo récord de empaquetamiento usando el procedimiento original de Rogers
Crear un elipsoide más grande mediante crecimiento aleatorio
- Klartag partió de un método que le resultaba familiar: hacer crecer y contraer la frontera del elipsoide a lo largo de cada eje mediante un proceso aleatorio
- Cuando la frontera se expandía lo suficiente como para tocar un nuevo punto de la retícula, detenía el crecimiento en esa dirección
- Ese punto no entraba en el interior del elipsoide
- En otras direcciones, el elipsoide seguía inflándose hasta tocar otro punto
- En este proceso, el elipsoide avanzaba por el espacio circundante de forma gradual, deteniéndose y moviéndose como a tirones
- Con el tiempo, en promedio, el volumen del elipsoide aumentaba
- La pregunta clave de Klartag era si ese aumento de volumen bastaría para superar el elipsoide intuitivo de Rogers
- Como el proceso aleatorio producía un elipsoide distinto en cada ejecución, Klartag evaluó el rango de volúmenes posibles
- Al principio no logró encontrar un único elipsoide lo suficientemente grande como para superar el de Rogers
- Después de ajustar los detalles del proceso de crecimiento aleatorio, en una o dos semanas demostró que a veces surgía un elipsoide lo bastante grande como para imponer un nuevo récord
El significado matemático de una mejora de aproximadamente d veces
- La demostración de Klartag fue verificada, y al convertir el nuevo elipsoide inicial en un empaquetamiento de esferas se obtiene la mayor mejora de eficiencia desde el artículo de Rogers de 1947
- En una dimensión dada d, el método de Klartag permite empaquetar aproximadamente d veces más esferas que muchos resultados anteriores
- En un espacio de 100 dimensiones, empaqueta aproximadamente 100 veces más esferas
- En un espacio de un millón de dimensiones, empaqueta aproximadamente un millón de veces más esferas
- Klartag estudió el área del empaquetamiento de esferas durante unos meses y, tras escribir la demostración en unas semanas, logró un avance importante en uno de sus problemas centrales
- Su experiencia en geometría convexa fue decisiva para aplicar al problema de empaquetamiento de esferas técnicas que normalmente se trataban como pertenecientes a otra área
- Gil Kalai calificó el resultado como “un avance realmente sorprendente” y lo vio como un logro relacionado con un problema que ha entusiasmado a los matemáticos durante casi 100 años
El debate entre orden y desorden
- El resultado de Klartag reaviva el debate sobre la naturaleza de los empaquetamientos óptimos en altas dimensiones
- Durante un tiempo, los matemáticos consideraron que los empaquetamientos basados en retículas, con alto grado de simetría, eran la mejor manera de disponer esferas de forma más densa
- En 2023 se descubrió un empaquetamiento que no dependía limpiamente de una retícula repetitiva y que se convirtió en el récord previo a Klartag
- Algunos matemáticos lo vieron como evidencia de que se necesitaba más desorden en la búsqueda del empaquetamiento óptimo de esferas
- El trabajo de Klartag vuelve a respaldar la idea de que el orden y la simetría podrían ser candidatos fuertes
- Qué tan denso puede llegar a ser el empaquetamiento de esferas sigue en discusión
- Algunos matemáticos creen que el empaquetamiento de Klartag está muy cerca del óptimo
- Otros consideran que todavía hay margen de mejora
- Marcus Michelen, de University of Illinois, Chicago, dice que en este momento no sabe qué creer y que todas las posibilidades siguen abiertas
Más que una aplicación inmediata, una gran conexión entre campos
- La respuesta al problema de empaquetamiento de esferas es importante por sus posibles aplicaciones en criptografía y comunicaciones
- Or Ordentlich, teórico de la información de Hebrew University, dice que el problema es grande para los ingenieros, pero ha tenido pocos avances, por lo que este resultado genera entusiasmo
- Sin embargo, el resultado de Klartag no es inmediatamente útil para esas aplicaciones
- Klartag espera que su trabajo sirva para volver a una forma, como en la época de Rogers, en la que la geometría convexa y la teoría de retículas estaban más conectadas
- Considera que la comprensión actual de los cuerpos convexos podría ser útil no solo para el empaquetamiento de esferas, sino también para problemas de retículas
- El objetivo de Klartag es que ambos campos estén menos desconectados que ahora
1 comentarios
Comentarios de Hacker News
Ya es difícil explicarles a mis padres que mi trabajo es un trabajo de verdad; imaginar explicarles que “solo estudio figuras que no tienen partes que sobresalgan ni se metan hacia adentro” suena todavía más difícil
En realidad solo hay tres opciones. Si lo explicas brevemente con palabras que la otra persona entiende, el trabajo parece fácil y terminan pensando: “¿Cómo le pagan por esto?”
Si explicas con palabras que la otra persona entiende qué haces y por qué es importante, se vuelve demasiado largo, se aburren y se arrepienten de haber preguntado
O puedes explicarlo brevemente con jerga que la otra persona no conoce, lo cual los aburre pero los impresiona; entre las malas opciones, esa es la mejor
Todavía no he encontrado una forma de explicar a la gente común, aunque sea un poco, de qué trata mi negocio. Todo es demasiado abstruso y está a varios pasos de la vida cotidiana
No es que sea necesariamente complejo; más bien hay demasiados detalles con los que una persona promedio nunca ha tenido contacto familiar, y casi no hay analogías cotidianas
Sobre los cuerpos convexos, no sé mucho
Una forma de hablar que suena demasiado detallada puede volverse tóxica y alejar a la gente
Se puede explicar desde una perspectiva como: “Quiero hacer XYZ, pero es tan difícil que resulta frustrante, así que hago una conjetura sencilla. Pensar este problema de forma tan aproximada lo vuelve más manejable, y como conozco ABC, construyo ABC. Y al usarlo me emociona porque se acerca más a funcionar mejor que todo lo que he probado hasta ahora”
Para personas no técnicas, una explicación cargada de emoción también funciona perfectamente. Es posible que estén más acostumbradas a pensar emocionalmente, mientras que nosotros estamos profundamente inmersos en la lógica del trabajo y, a veces, en las matemáticas. Por eso hay que volver a incorporar emoción en la explicación
Se lo expliqué así a mi familia, y me siguieron el hilo y de verdad lo entendieron
En el artículo decían que “en un espacio de 100 dimensiones, su método llena aproximadamente 100 veces más esferas, y en un espacio de un millón de dimensiones, aproximadamente un millón de veces más”; es un buen ejemplo de lo raro que puede ser un espacio de alta dimensión.
Parece significar que, cuando gente muy inteligente intentó meter la mayor cantidad posible de naranjas de 100 dimensiones en una caja de 100 dimensiones, hasta ahora no habían logrado llenar ni el 1% del espacio, y durante décadas no encontraron lugar para meter ni una más.
Si pensamos en una n-esfera unitaria encerrada en un hipercubo unitario, la proporción que ocupa la esfera desaparece a medida que n crece. Además, curiosamente, esta relación no es monótona y alcanza su máximo en n=6.
En n=100, el volumen de una 100-esfera unitaria es aproximadamente 10^-40, y por supuesto no se puede meter una segunda esfera dentro de ese hipercubo. Así que no sorprende tanto que la ganancia obtenida al mejorar el empaquetamiento pueda ser tan grande.
Mucha gente dice que puede visualizar 4 dimensiones, pero todavía no he visto a nadie que realmente pueda hacerlo. Esto incluye a muchos matemáticos, aunque quienes hacen esa afirmación normalmente no son matemáticos.
Me gusta la animación[0] de este post de Math Overflow, porque tiene mucha complejidad oculta que la mayoría no considera. Esa animación en realidad es una ilusión óptica y estamos viendo una “alucinación”. ¿La figura de arriba proyecta un cubo sobre un plano? En realidad eso no es un cubo. Ya es un cubo proyectado a 2 dimensiones. Técnicamente es 3D, pero la tercera dimensión no es una dimensión espacial, sino temporal. Esto en sí mismo es una buena lección para aprender la abstracción de las dimensiones.
Así que alucinamos un cubo que gira y, después de ver su proyección sobre un plano, volvemos a alucinar que tiene profundidad en lugar de ser un cuadrado no distorsionado. Eso por sí solo ya es bastante extraño.
De hecho, también nos cuesta imaginar 2 dimensiones. La mayoría afirma que puede visualizar 2D, y esa afirmación casi nunca se refuta.
Si no han leído Flatland[1], se lo recomiendo a todos. Mucha gente lo lee mal. Normalmente lo leen como una analogía reducida en una dimensión: nosotros, seres tridimensionales, corresponderíamos a seres bidimensionales, y los seres de 4 dimensiones nos resultarían tan desconcertantes como un ser de 3 dimensiones para un Flatlander. Eso es correcto, pero ahí hay una trampa. Creemos que entender 2 dimensiones es muy fácil. Pero les aseguro que lo que están dibujando ahora en su cabeza está mal. Para ser honesto, el libro tampoco es perfectamente preciso.
Hay que ponerse realmente en el lugar de un Flatlander. No dentro del libro, sino en la posición de un Flatlander real. Si imaginan que son un Flatlander cuadrado y ven un triángulo, ¿qué verían? Probablemente piensen en una línea, pero eso está mal. Le dieron grosor y metieron una tercera dimensión. Si lo intentan de nuevo y se desafían a imaginar Flatland real, agregando más profundidad, descubrirán que no pueden hacerlo.
En cambio, sí podemos visualizar y razonar sobre un espacio bidimensional incrustado dentro de 3 dimensiones. Se podría decir que esto es ponerse quisquilloso, pero si no fuera así, también debería estar perfectamente bien decir que esto[2,3] es un hipercubo de 4 dimensiones, y no una representación de un hipercubo de 4 dimensiones.
Creo que entender esto ayuda mucho a comprender dimensiones muy altas. Cuando uno enfrenta la enorme dificultad de visualizar con precisión lo que pasa al sumar o restar una dimensión, es menos probable que se engañe al razonar sobre dimensiones mucho más altas.
Como dijo Feynman, el primer principio es no engañarse a uno mismo, y la persona más fácil de engañar es uno mismo.
[0] https://math.stackexchange.com/a/2286226
[1] http://www.geom.uiuc.edu/~banchoff/Flatland/
[2] [https://en.wikipedia.org/wiki/Tesseract#/media/File:8-cell-s...](https://en.wikipedia.org/wiki/Tesseract#/media/File:8-cell-simple.gif)
[3] Es un buen video de Carl Sagan explicando con una proyección tridimensional de un hipercubo, es decir, su sombra. Muestre lo que muestre, no puede sino estar incrustado en 2 dimensiones. Lo levanta a partir del minuto 6:20 https://www.youtube.com/watch?v=UnURElCzGc0
Interesante. Durante un mes probé un enfoque de empaquetamiento de esferas para crear un mejor algoritmo de compresión.
Tenía muchos vectores agrupados mediante clustering, pero llegué a la conclusión de que el enfoque teórico solo funciona bien con datos uniformes y no se ajusta bien a datos del mundo real.
Por ejemplo, supongamos que los datos tienen una estructura de alta dimensión, pero localmente son uniformes. Esto es común y ocurre por procesos que generan ruido. Si calculas y guardas los centroides, los datos quedan más uniformes que los originales y no son tantos, así que de todos modos no es un gran problema.
Cada vector se guarda como índice de centroide y offset del vector. En este caso es SoA, no AoS. Los índices se pueden comprimir con el método entero basado en entropía que prefieras, y si no necesitas conservar el orden, incluso puedes hacerlo mejor.
Como, por hipótesis, los offsets ahora son aproximadamente uniformes, puedes usar la estrategia de esferas de la literatura que prefieras.
Claro que, si los casos de uso reales son demasiado heterogéneos como para que una técnica general sea efectiva, quizá no.
Los matemáticos sienten que, unos años después de su primer doctorado, deberían poder hacer un segundo título de nivel doctoral en un campo adyacente, aunque no sea el mismo que el suyo
Muchos investigadores se vuelven a formar o suman intereses de investigación en campos adyacentes durante el posdoctorado o después. A partir de ese momento, simplemente es investigación
Dicho eso, en el entorno académico moderno no sería fácil intentarlo
En particular, conectar distintas áreas de las matemáticas puede ser muy potente
Al menos en Alemania, se parece bastante a lo descrito
Klartag dice que, para una dimensión dada d, puede empaquetar d veces más esferas que la mayoría de los resultados anteriores.
Es decir, en 100 dimensiones serían aproximadamente 100 veces más esferas, y en un millón de dimensiones aproximadamente un millón de veces más; los números suenan enormes. ¿Significa eso que en varios sistemas de comunicación el ancho de banda aumentaría varios órdenes de magnitud o el consumo de energía bajaría?
Por eso solo ayuda a objetos que son naturalmente de alta dimensión. Los objetos digitales no tienen una dimensión natural, es decir, una longitud en bytes, así que se puede elegir una dimensión pequeña.
https://en.m.wikipedia.org/wiki/Sphere_packing
Aunque Klartag, por su formación, no es especialista en empaquetamiento de esferas, es uno de los solucionadores de problemas más destacados que hay.
A principios de este año resolvió la Conjetura del Hiperplano, y ha contribuido a avances en problemas relacionados con la teoría de la convexidad, como la Conjetura KLS, la Conjetura de Mahler y el teorema central del límite para cuerpos convexos.
El trabajo de su estudiante Eldan sobre localización estocástica (Stochastic Localization) también resultó ser clave en algoritmos de muestreo log-cóncavo, lo cual está relacionado con la Conjetura KLS, y además dio una charla en el ICM.
Además, las herramientas usadas en geometría convexa, especialmente algunas de análisis armónico, también son bastante útiles para estudiar el empaquetamiento de esferas.
Así que difícilmente se puede decir que sea “inesperado”
Estoy de acuerdo con Klartag en que las figuras convexas son una herramienta matemática subestimada. No soy matemático, pero he visto algoritmos de envolvente convexa resolver problemas en lugares totalmente inesperados.
Por ejemplo, uno no se imaginaría que se usarían algoritmos de envolvente convexa en un artículo sobre descomposición automática de paletas de imágenes.
https://www.rose-hulman.edu/class/cs/csse451/Papers/DILvGRB....
Pregunta de principiante: ¿el empaquetamiento de esferas óptimo está correlacionado con retículas regulares? ¿No es así en 2 y 3 dimensiones? Si es así, ¿se extendería a n dimensiones?
Maryna Viazovska lo demostró en 2017, y en el segundo artículo participaron coautores. https://doi.org/10.4007/annals.2017.185.3.7 https://doi.org/10.4007/annals.2017.185.3.8
Esto también vale la pena verlo: https://www.ams.org/journals/notices/201702/rnoti-p102.pdf
En otras dimensiones es un problema abierto y, en general, parece poco probable que sea cierto. En algunas dimensiones, el empaquetamiento no regular más denso conocido es más denso que el empaquetamiento regular más denso conocido
Sin embargo, todos tienen la misma densidad que la retícula FCC. Estos empaquetamientos pueden construirse desplazando horizontalmente, unas respecto de otras, las capas horizontales de la FCC.
En dimensiones altas existe la conjetura de que el empaquetamiento más denso siempre será no reticular, porque esos espacios no tienen suficiente simetría
Hoy más temprano hubo una publicación sobre neandertales que renderizaban grasa.
Se dijo que los antropólogos no sabían que hervir era posible incluso antes de la invención de la cerámica, y también que los profesores de ciencias sí conocían esa posibilidad porque lo hacen en clase.
Por último, la conversación iba por la línea de que, así como alguien que estudiaba la glucosa redescubrió la regla del trapecio de la integración, a veces se redescubre lo mismo en campos distintos.
Esto también es otro ejemplo de cómo la experiencia en otra área puede ayudar.
Basta con ver un video de YouTube que muestre un método usado en situaciones de supervivencia. Seguramente hay muchos similares: https://www.youtube.com/shorts/0zun_UxO2vU
Es cierto que no conozco el contexto, pero si una afirmación tan sorprendente no tiene fuente, no tiene sentido. Ni siquiera pasa la “prueba de la risa”.