Novo recorde de empacotamento de esferas surgiu de uma fonte inesperada

• Boaz Klartag introduziu ferramentas de geometria convexa no problema de empacotamento de esferas em dimensões ultraltas, em contraste com as abordagens anteriores
• O novo método aleatório de Klartag gera elipsoides de volume maior, atualizando de forma expressiva o recorde anterior
• Essa abordagem permite empacotar dramaticamente mais esferas em espaços de alta dimensão
• O resultado reacende o debate sobre a importância de ordem e simetria no empacotamento
• A pesquisa vem chamando atenção por suas possíveis aplicações em áreas como criptografia e comunicações

---

Limites e pesquisas anteriores sobre empacotamento de esferas

• No passado, a vantagem do método de Rogers era que a rede inicial não precisava necessariamente ser eficiente, desde que se escolhesse um elipsoide adequado
• Porém, como os eixos do elipsoide podem ser deformados de muitas maneiras em altas dimensões, havia opções demais sobre como fazê-lo crescer
• Depois disso, os matemáticos voltaram à abordagem de Minkowski e passaram a focar na própria rede, especializando-se em teoria das redes e se afastando da abordagem mais geométrica de Rogers
• Essa estratégia mostrou melhorias graduais no empacotamento de esferas em alta dimensão, mas trouxe apenas ganhos modestos de eficiência em relação ao método de Rogers
• Durante décadas, não houve grandes saltos, e a área permaneceu estagnada

Uma inovação iniciada por um olhar externo

• Boaz Klartag, do Weizmann Institute of Science, é originalmente um pesquisador de geometria convexa, não de teoria das redes
• Ele tinha interesse no problema de empacotamento de esferas havia muito tempo, mas não tinha tido oportunidade de pesquisá-lo
• Em 2023, com mais tempo disponível, abriu um seminário com Barak Weiss, da Tel Aviv University, para explorar intensamente a literatura clássica (Minkowski, Rogers)
• Klartag concluiu que o método dos elipsoides de Rogers era ineficiente por falta de know-how na manipulação de corpos convexos
• Ele passou a acreditar que, com elipsoides mais eficientes, seria possível reescrever o recorde no empacotamento de esferas

Introdução de um algoritmo de crescimento aleatório

• Klartag aplicou um método próprio em que expande ou contrai aleatoriamente a fronteira do elipsoide em cada direção dos eixos
• Quando a fronteira toca um ponto da rede, o crescimento naquela direção para, enquanto continua nas demais
• Nesse processo, o elipsoide explora o espaço com forma irregular e vai crescendo gradualmente
• Como, por causa do caráter aleatório, cada elipsoide gerado tem um volume diferente, ele repetiu o experimento muitas vezes para avaliar a possibilidade de obter elipsoides de volume maior
• Em poucas semanas, provou que era possível obter elipsoides maiores do que os de Rogers

Quebra de recorde e impacto

• O novo método com elipsoides alcançou a maior melhora já obtida na eficiência do empacotamento de esferas desde Rogers (1947)
• Quando a dimensão é d, ele permite empacotar d vezes mais esferas do que a abordagem anterior
  • 100 dimensões → cerca de 100 vezes mais; 1.000.000 de dimensões → cerca de 1 milhão de vezes mais
• Com insights vindos da geometria convexa, Klartag superou em poucos meses alguns dos antigos problemas centrais sobre redes e empacotamento de esferas
• Seu resultado voltou a destacar a visão de que empacotamentos baseados em ordem e simetria podem alcançar as configurações mais densas
• Por outro lado, pesquisas mais recentes também defendem que é preciso explorar a desordem, sem redes regulares

Avaliação e perspectivas futuras

• Ainda há debate na comunidade acadêmica sobre se o método de empacotamento de Klartag está realmente perto do ótimo ou se ainda há espaço para melhorias
• A resposta para essa questão é muito importante também em aplicações práticas, como criptografia e engenharia de comunicações
• Ainda não está em fase de uso prático, mas já vem sendo observado como uma nova tecnologia promissora em áreas de engenharia
• Klartag espera que este trabalho fortaleça a conexão entre geometria convexa e teoria das redes
• Ele também espera que essa integração supere a separação entre os dois campos e se estenda à solução de outros problemas com redes além do empacotamento

[GN⁺]

Comentários do Hacker News

• Confissão de que sempre é difícil explicar aos pais que sua profissão realmente existe; imaginar a situação ficando ainda mais embaraçosa ao dizer: “eu estudo formas, mas só aquelas que não têm partes côncavas”
  • Pela minha experiência, a melhor conclusão é explicar a profissão usando termos técnicos difíceis; no fim, as opções se resumem a três: se você der uma explicação relativamente simples que seus pais consigam entender, o trabalho parece fácil demais e a reação é “você realmente ganha dinheiro com isso?”; se você explicar direito por que isso é importante, a explicação fica longa demais, seus pais se cansam e se arrependem de ter perguntado; ou então você fala de forma breve usando jargão complicado, ninguém entende nada, mas parece impressionante sem motivo — e essa acaba sendo a melhor opção
  • Tenho um micro negócio que fabrica componentes para equipamentos de física de altas energias e, quando tento explicar meu trabalho para outras pessoas, ainda não encontrei uma forma de fazê-las entender, porque é um tema extremamente estranho, nichado e várias etapas distante de qualquer experiência do cotidiano que o público já tenha tido
  • Eu simplesmente digo: "trabalho com computadores" e aí vem a resposta “ah, legal, é um bom trabalho”, e a conversa termina — o que é bem conveniente
  • Para mim, o problema quase nunca é a pergunta “o que você faz?”, mas sim a que vem depois: “e isso serve para quê/onde isso é usado?”; é sempre difícil explicar de forma curta e eficaz a longa cadeia que liga pesquisa fundamental a aplicações reais
  • Pelo menos o empacotamento de esferas (sphere packing) está intimamente ligado a problemas centrais da teoria da informação e, nesse sentido, dá para encontrar contexto histórico e importância no fato de isso estar conectado ao aumento da confiabilidade do sistema Bell de telefonia (sobre corpos convexos, não sei dizer)
• Relato de experiência tentando pensar em algoritmos de compressão de dados vetoriais usando sphere packing; a abordagem teórica só funcionava quando os dados eram muito uniformes, e era difícil aplicá-la a dados do mundo real
  • Para transformar dados não estruturados (não uniformes) em algo mais uniforme, o truque habitual é usar conhecimento de domínio para reduzir a assimetria; por exemplo, mesmo que os dados tenham uma estrutura de alta dimensão, localmente eles muitas vezes acabam bem uniformes por causa do ruído; se você calcular e armazenar centróides, eles ficam mais uniformes, e cada vetor pode ser armazenado separando o índice do centróide e o deslocamento do vetor; o índice serve para compressão entrópica eficiente, e o deslocamento, agora quase uniforme, fica mais adequado para aplicar a estratégia tradicional de empacotamento de esferas
  • Talvez já tenham tentado isso, mas dá para investigar se uma pré-compressão (precompression) reduziria a esparsidade dos vetores e aumentaria a uniformidade
  • Observação em tom de piada de que, ao lidar com vetores reais, é preciso tomar cuidado ao “apalpá-los” (grope é “apalpar”, um erro de digitação de group)
  • Chamada de atenção para a necessidade de expandir o alcance da teoria até problemas práticos — isto é, dados heterogêneos; se as aplicações do mundo real forem diversas demais, talvez uma abordagem geral seja difícil, mas ainda assim vale ampliar essa linha de pesquisa
  • Observação de que, em áreas antigas e comercialmente importantes, a maior parte dos resultados fáceis de obter (os “frutos mais baixos”) já foi colhida
• Concordância com a afirmação de Klartag de que “corpos convexos são muito poderosos e têm grande utilidade”; embora não seja matemático, a pessoa comenta que já viu algoritmos de Convex Hull aparecerem em lugares inesperados, especialmente em vários problemas como decomposição automática de paleta em imagens, e fornece um link de referência: Convex Hull and automatic palette decomposition
• Dúvida sobre a nova forma de empacotamento de esferas de Klartag, que aparentemente permite empacotar d vezes mais esferas do que antes numa dimensão d; em 100 dimensões, isso seria 100 vezes mais, e em um milhão de dimensões, um milhão de vezes mais — um número enorme; fica a curiosidade se, em vários sistemas de comunicação, isso significaria na prática dezenas ou centenas de vezes mais largura de banda, ou um grande corte no consumo de energia
  • Na prática, à medida que a dimensão aumenta, a densidade piora exponencialmente como n^2/2^n, então essa melhora linear teórica não aparece integralmente no desempenho real; ou seja, isso é útil para dados que têm naturalmente estrutura de alta dimensão, mas, para dados digitais (em que você pode escolher só o comprimento), dá para optar por dimensões pequenas; para mais detalhes sobre sphere packing, veja wikipedia link
• Ideia de que matemáticos deveriam poder fazer um segundo doutorado, alguns anos depois do primeiro, em uma área adjacente em vez de exatamente no mesmo campo
  • Como o objetivo fundamental do doutorado é provar a capacidade de fazer pesquisa de forma independente, na prática muitos pesquisadores mudam de área ou trocam de tema de interesse depois de concluir o doutorado; a partir daí, o foco passa a ser a própria “pesquisa”
  • Como exemplo real de que isso é possível, o famoso matemático Bela Bollobas tem dois doutorados, um em geometria discreta e outro em análise funcional; dito isso, tentar repetir isso no meio acadêmico atual provavelmente seria muito difícil
  • Se houvesse essa flexibilidade institucional em toda a ciência, técnicas e ideias de áreas diferentes poderiam circular mais rapidamente, acelerando o avanço científico; a expectativa é de benefício ainda maior em campos como a matemática, onde as conexões entre subáreas são especialmente importantes
• Pergunta de iniciante: o empacotamento ótimo de esferas (sphere packing) está sempre ligado a reticulados regulares? Em 2D e 3D parece que sim, mas a dúvida é se isso se estende para N dimensões
  • Além de 2 e 3 dimensões, há casos em que o melhor empacotamento foi provado como sendo um reticulado regular em 8 dimensões (reticulado E₈) e 24 dimensões (reticulado de Leech); isso foi demonstrado em 2017 por Maryna Viazovska e colaboradores, com links para os materiais relacionados: artigo 1, artigo 2, explicação em pdf; porém, em outras dimensões podem existir contraexemplos em que o empacotamento ótimo não seja um reticulado regular, e em algumas dimensões formas irregulares podem até ser mais densas
  • Não necessariamente; mesmo em 3 dimensões, além do empacotamento em lattice (reticulado regular), também é possível criar infinitas configurações não reticulares variando o deslocamento horizontal de cada camada; nesses casos, a densidade continua igual à do reticulado FCC; em dimensões altas, há até a conjectura de que o empacotamento ótimo seja sempre não reticular por falta de simetria suficiente
• Curiosidade sobre a menor dimensão a partir da qual essa nova estrutura de empacotamento de esferas supera os casos em que a melhor densidade anterior já era comprovada
• Sugestão de direção futura: se os resultados deste estudo poderiam ser aplicados, nas áreas de criptografia e comunicações, ao desenvolvimento de sistemas de comunicação de fato mais seguros, mais confiáveis e mais eficientes em energia; um campo de pesquisa muito interessante
• Uma analogia espirituosa mencionando Cow Packing na física real — como estudos teóricos sobre preencher vacas com densidade ótima — e a possibilidade de aplicações práticas
• O empacotamento de esferas é interessante porque aparece em uma diversidade enorme de problemas aplicados; expectativa de ler o artigo com atenção