Novo recorde de empacotamento de esferas vem de uma fonte inesperada
(quantamagazine.org)- No problema de empacotamento de esferas em alta dimensão, Boaz Klartag publicou online em abril um manuscrito curto com a maior melhoria de eficiência desde Claude Ambrose Rogers, em 1947
- O novo método parte de uma rede arbitrária, cria um elipsoide maior e então usa o procedimento de Rogers para construir um empacotamento denso de esferas, reavivando uma abordagem geométrica que havia ficado em segundo plano por algum tempo
- A construção de Klartag consegue empacotar cerca de d vezes mais esferas na dimensão d do que muitos resultados anteriores, o que corresponde a cerca de 100 vezes em 100 dimensões e a cerca de 1 milhão de vezes em 1 milhão de dimensões
- Em contraste com as discussões sobre a possibilidade de empacotamentos desordenados, que ganharam força após o recorde não reticular de 2023, este resultado mostra que ordem e simetria ainda podem ser candidatas fortes nos empacotamentos ótimos em alta dimensão
- Embora o problema do empacotamento de esferas seja importante para aplicações em criptografia e comunicação, este resultado não tem aplicação imediata e pode servir para reconectar a geometria convexa e a teoria das redes
Grande avanço no empacotamento de esferas em alta dimensão
- O problema do empacotamento de esferas consiste em encontrar uma forma de preencher um espaço de alta dimensão com bolas da maneira mais eficiente possível
- Esse problema atrai matemáticos há séculos e também tem aplicações potenciais importantes em criptografia e comunicações de longa distância
- No início do século XVII, Johannes Kepler mostrou que, ao empilhar esferas tridimensionais como laranjas em um supermercado, é possível preencher cerca de 74% do espaço, e conjecturou que isso era ótimo
- Essa conjectura só foi provada quase 400 anos depois
- Em dimensões mais altas, exceto nas dimensões 8 e 24, a resposta ótima ainda é desconhecida
- Matemáticos vêm buscando empacotamentos melhores há muito tempo, mas as melhorias foram pequenas e raras
- Em um manuscrito curto publicado em abril, Boaz Klartag superou o recorde anterior por uma grande margem, e alguns pesquisadores veem o resultado como possivelmente próximo do ótimo
Uma ideia antiga que vai de redes a elipsoides
- Em 1905, Hermann Minkowski estabeleceu uma forma de pensar o empacotamento de esferas por meio de redes (lattices)
- O método consiste em criar uma disposição de pontos que se repete no espaço e desenhar uma esfera em torno de cada ponto
- Em uma dimensão específica, o problema de encontrar o empacotamento ótimo de esferas se transforma no problema de encontrar a rede em que os pontos estão dispostos da forma mais eficiente
- Em duas dimensões, a rede hexagonal é ótima
- Em 1947, Claude Ambrose Rogers apresentou outra perspectiva
- É possível começar até mesmo com uma rede arbitrária que não seja ótima
- Em vez de desenhar uma esfera em cada ponto, desenha-se um elipsoide em torno de um ponto, de modo que sua superfície toque outros pontos da rede sem ultrapassá-los
- A partir desse elipsoide, ele apresentou um algoritmo para construir um empacotamento denso de esferas
- A vantagem do método de Rogers é que a rede inicial não precisa ser particularmente eficiente
- Basta escolher o elipsoide correto para produzir um empacotamento eficiente de esferas
- Mas elipsoides são mais difíceis de manejar do que esferas
- Uma esfera é determinada por um único raio, enquanto um elipsoide é determinado por vários eixos de comprimentos diferentes
- À medida que a dimensão aumenta, as direções em que ele pode ser alongado e as formas possíveis crescem rapidamente
- No fim, os matemáticos voltaram à abordagem reticular de Minkowski e se afastaram da abordagem geométrica de Rogers, concentrando-se mais na teoria das redes
- Essa estratégia também melhorou o empacotamento de esferas em alta dimensão, mas na maior parte dos casos as melhorias foram menores do que a do empacotamento de Rogers
Um pesquisador de geometria convexa reaviva a abordagem de Rogers
- Klartag é matemático do Weizmann Institute of Science e pesquisa principalmente geometria convexa (convex geometry)
- Uma figura convexa é uma figura que não tem reentrâncias para dentro
- Em alta dimensão, essas figuras incluem várias simetrias, e Klartag as vê como ferramentas matemáticas poderosas
- Ele tinha interesse em redes e empacotamento de esferas, mas não tinha tido tempo para estudar a área em profundidade
- Em novembro do ano passado, depois de concluir um grande projeto, com a agenda cheia de vistos, pediu a Barak Weiss, da Tel Aviv University, mentoria para aprender uma nova área
- Weiss iniciou um pequeno seminário em que Klartag e algumas outras pessoas liam a literatura juntos
- Klartag leu em detalhe os métodos de Minkowski e Rogers para empacotamento de esferas
- Depois de ler como Rogers transformava um elipsoide em um empacotamento de esferas, Klartag se perguntou por que os matemáticos haviam abandonado esse método
- Como elipsoides são figuras convexas, Klartag dispunha de métodos sofisticados para manipulá-los
- Ele avaliou que o elipsoide inicial usado por Rogers era intuitivo, mas ineficiente
- Se fosse possível construir um elipsoide de volume maior, o procedimento original de Rogers poderia estabelecer um novo recorde de empacotamento
Criando elipsoides maiores por crescimento aleatório
- Klartag partiu de um método familiar para ele, no qual a fronteira de um elipsoide cresce e encolhe ao longo de cada eixo por meio de um processo aleatório
- Quando a fronteira se expandia o suficiente para tocar um novo ponto da rede, o crescimento naquela direção era interrompido
- Isso impedia que esse ponto entrasse no interior do elipsoide
- Em outras direções, o elipsoide continuava a inflar até tocar outro ponto
- Nesse processo, o elipsoide avançava e parava aos trancos, explorando gradualmente o espaço ao redor
- Com o tempo, em média, o volume do elipsoide aumentava
- A pergunta central de Klartag era se esse aumento de volume seria suficiente para superar o elipsoide intuitivo de Rogers
- Como o processo aleatório produzia um elipsoide diferente a cada execução, Klartag avaliou a faixa de volumes possíveis dos elipsoides
- No início, ele não encontrou um único elipsoide grande o bastante para superar o de Rogers
- Depois de ajustar os detalhes do processo de crescimento aleatório, em uma ou duas semanas ele provou que, às vezes, surgia um elipsoide grande o suficiente para estabelecer um novo recorde
O significado matemático de uma melhoria de cerca de d vezes
- A prova de Klartag foi verificada, e a conversão do novo elipsoide inicial em um empacotamento de esferas produz a maior melhoria de eficiência desde o artigo de Rogers de 1947
- Em uma dimensão d dada, o método de Klartag consegue empacotar cerca de d vezes mais esferas do que muitos resultados anteriores
- Em um espaço de 100 dimensões, empacota aproximadamente 100 vezes mais esferas
- Em um espaço de 1 milhão de dimensões, empacota aproximadamente 1 milhão de vezes mais esferas
- Klartag estudou a área de empacotamento de esferas por alguns meses, escreveu a prova em algumas semanas e fez avançar significativamente um de seus problemas centrais
- Sua experiência em geometria convexa foi diretamente importante para aplicar ao problema do empacotamento de esferas técnicas que normalmente eram tratadas como pertencentes a uma área separada
- Gil Kalai chamou o resultado de “um avanço realmente surpreendente” e o considerou uma conquista ligada a um problema que entusiasma matemáticos há quase 100 anos
O debate entre ordem e desordem
- O resultado de Klartag reaviva o debate sobre a natureza dos empacotamentos ótimos em alta dimensão
- Por algum tempo, matemáticos consideraram que os empacotamentos baseados em redes, altamente simétricos, eram a melhor forma de organizar esferas da maneira mais densa
- Em 2023, foi descoberto um empacotamento que não dependia de forma clara de uma rede repetitiva, tornando-se o recorde anterior a Klartag
- Alguns matemáticos viram isso como evidência de que seria necessária mais desordem na busca pelo empacotamento ótimo de esferas
- O trabalho de Klartag volta a sustentar a ideia de que ordem e simetria podem ser candidatas fortes
- Ainda há debate sobre quão denso o empacotamento de esferas pode se tornar
- Alguns matemáticos veem o empacotamento de Klartag como muito próximo do ótimo
- Outros matemáticos acreditam que ainda há espaço para melhorias
- Marcus Michelen, da University of Illinois, Chicago, disse que no momento não sabe em que acreditar e que todas as possibilidades estão abertas
Mais uma conexão entre áreas do que uma aplicação imediata
- As respostas ao problema do empacotamento de esferas são importantes por suas possíveis aplicações em criptografia e comunicação
- Or Ordentlich, teórico da informação da Hebrew University, diz que esse problema é importante para engenheiros, mas teve pouco avanço, por isso este resultado desperta entusiasmo
- Ainda assim, o resultado de Klartag não é imediatamente útil para essas aplicações
- Klartag espera que seu trabalho sirva como um impulso para retornar a uma forma de pesquisa, como na época de Rogers, em que geometria convexa e teoria das redes estavam mais conectadas
- Ele acredita que o entendimento atual sobre corpos convexos pode ser útil também para problemas de redes, além do empacotamento de esferas
- O objetivo de Klartag é fazer com que as duas áreas sejam menos separadas do que são hoje
1 comentários
Comentários do Hacker News
Já é difícil explicar para os meus pais que o meu trabalho é um emprego de verdade; explicar que eu “só estudo formas sem partes que saltam para fora e entram para dentro” é ainda mais difícil só de imaginar
Na prática, só existem três opções. Se você explica de forma curta, com palavras que a outra pessoa entende, o trabalho parece fácil e ela pensa: “como alguém recebe dinheiro por isso?”
Se você explica com palavras que a outra pessoa entende o que faz e por que isso importa, fica longo demais, entediante, e ela acaba se arrependendo de ter perguntado
Ou você pode explicar de forma curta com jargão que a outra pessoa não conhece e causar tédio, mas também admiração; entre as opções ruins, essa é a melhor
Ainda não encontrei um jeito de explicar o que a minha empresa faz de um modo que uma pessoa comum consiga entender minimamente. Tudo é complicado demais e está várias camadas distante da vida cotidiana
Não é necessariamente por ser complexo, mas porque há detalhes demais com os quais a pessoa média nunca teve familiaridade, e quase não existem analogias do dia a dia
Já a parte de corpos convexos eu realmente não conheço
Um jeito de falar que parece excessivamente detalhista pode acabar tendo um efeito tóxico de afastar as pessoas
Dá para explicar a partir de uma perspectiva como: “quero fazer XYZ, mas é difícil demais e frustrante, então tento uma conjectura simples. Pensar nesse problema de forma mais grosseira facilita lidar com ele, e como sabemos ABC, construímos ABC. E quando usamos isso, ficamos animados porque chegamos mais perto de algo que funciona melhor do que tudo o que tentamos até agora”
Para quem não é técnico, uma explicação carregada de emoção também funciona muito bem. Essas pessoas podem estar mais acostumadas a pensar emocionalmente, enquanto nós estamos profundamente imersos na lógica do trabalho e, às vezes, na matemática. Por isso, precisamos recolocar emoção na explicação
Expliquei assim para a minha família, e eles conseguiram acompanhar e realmente entenderam
No artigo diziam que, “em um espaço de 100 dimensões, o método dele empacota cerca de 100 vezes mais esferas, e em um espaço de um milhão de dimensões, cerca de 1 milhão de vezes mais”, o que é um bom exemplo de quão estranho o espaço de alta dimensão é
Parece querer dizer que, quando pessoas muito inteligentes tentaram colocar o máximo possível de laranjas de 100 dimensões em uma caixa de 100 dimensões, até agora não conseguiram preencher nem 1% do espaço e, mesmo procurando por décadas, não encontraram lugar para colocar nem mais uma
Se pensarmos em uma n-esfera unitária circunscrita por um hipercubo unitário, a fração ocupada pela esfera desaparece à medida que n aumenta. Além disso, curiosamente, essa relação não é monotônica e atinge o máximo em n=6
Em n=100, o volume da 100-esfera unitária é aproximadamente 10^-40, e obviamente não dá para colocar uma segunda esfera dentro desse hipercubo. Por isso, não é tão surpreendente que o ganho obtido com uma melhoria no empacotamento possa ser tão grande
Muita gente diz que consegue visualizar 4 dimensões, mas ainda não vi ninguém que realmente consiga. Isso inclui muitos matemáticos, mas curiosamente quem faz esse tipo de afirmação geralmente não são matemáticos
Gosto da animação neste post do Math Overflow[0], porque ela tem muita complexidade escondida em que a maioria das pessoas não pensa. Aquela animação na verdade é uma ilusão de ótica, e estamos vendo uma “alucinação”. A figura de cima projeta um cubo em um plano? Na verdade, aquilo não é um cubo. Já é uma projeção do cubo em 2D. Tecnicamente é 3D, mas a terceira dimensão não é espacial, e sim temporal. Isso por si só já é uma boa lição para aprender a abstração de dimensão
Então nós alucinamos um cubo girando, vemos uma projeção no plano e depois alucinamos novamente aquilo como se tivesse profundidade, em vez de ser apenas um quadrado sem torção. Isso por si só já é bem estranho
Na verdade, também temos dificuldade para imaginar 2 dimensões. A maioria afirma que consegue visualizar 2D, e essa afirmação em geral não é contestada
Se você nunca leu Flatland[1], eu recomendaria a todos. Muita gente lê errado. Normalmente como uma analogia de uma dimensão a menos, entendendo que nós, seres 3D, correspondemos aos seres 2D, e que um ser 4D seria para nós tão desconcertante quanto um ser 3D é para um habitante de Flatland. Isso está certo, mas há um truque aí. Achamos que entender 2D é muito fácil. Mas aposto que o que você está imaginando agora está errado. Para ser sincero, o livro também não é perfeitamente preciso
É preciso realmente tentar se colocar na posição de um habitante de Flatland. Não a posição dentro do livro, mas a de um Flatlander real. Se você imaginar ser um habitante quadrado de Flatland olhando para um triângulo, o que veria? Provavelmente vai imaginar uma linha, mas isso está errado. Você deu espessura a ela e introduziu uma terceira dimensão. Tente de novo, desafie a si mesmo a imaginar a Flatland real adicionando cada vez mais profundidade, e vai perceber que não consegue
Em vez disso, conseguimos visualizar e raciocinar sobre um espaço 2D embutido em 3D. Isso pode parecer picuinha, mas se não for, então também deveria ser totalmente aceitável chamar isto[2,3] de um hipercubo 4D, e não de uma representação de um hipercubo 4D
Acho que entender isso ajuda muito a entender dimensões muito altas. Quando você encara a enorme dificuldade de visualizar com precisão uma dimensão a mais ou a menos, fica menos propenso a se enganar ao raciocinar sobre dimensões muito maiores
Como disse Feynman, o primeiro princípio é não enganar a si mesmo — e a pessoa mais fácil de enganar é você mesmo
[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] É um bom vídeo do Carl Sagan explicando com uma projeção 3D de um hipercubo, isto é, uma sombra. Seja o que for que se mostre, inevitavelmente está embutido em 2D. Ele pega nisso a partir de 6:20 https://www.youtube.com/watch?v=UnURElCzGc0
Interessante. Passei um mês tentando usar uma abordagem de empacotamento de esferas para criar um algoritmo de compressão melhor
Eu tinha muitos vetores agrupados por clustering, mas cheguei à conclusão de que a abordagem teórica só funciona direito com dados uniformes e não se encaixa bem em dados do mundo real
Por exemplo, suponha que os dados tenham estrutura de alta dimensão, mas sejam localmente uniformes. Isso é comum e surge por causa de processos que introduzem ruído. Se você calcular e armazenar centróides, eles ficam mais uniformes que os dados originais e não são tão numerosos, então de qualquer forma não viram um grande problema
Cada vetor é armazenado como um índice de centróide e um deslocamento de vetor. Aqui é SoA, não AoS. Os índices podem ser comprimidos com o método inteiro baseado em entropia de sua preferência e, se não for necessário preservar a ordem, talvez dê para fazer ainda melhor
Como os deslocamentos agora são aproximadamente uniformes, pela hipótese, dá para usar a estratégia de esfera de sua preferência da literatura
Claro, talvez não, se os casos de uso reais forem heterogêneos demais para que uma técnica geral funcione
Matemáticos acham que, alguns anos após o primeiro doutorado, deveriam poder obter um segundo título de nível doutoral em uma área adjacente, ainda que não seja exatamente a mesma da sua área
Muitos pesquisadores se reciclam para áreas adjacentes ou acrescentam novos interesses de pesquisa durante o pós-doutorado ou depois disso. A partir desse ponto, é simplesmente pesquisa
Mas, no ambiente acadêmico atual, tentar fazer isso não seria fácil
Em especial, conectar diferentes áreas da matemática pode ser extremamente poderoso
Pelo menos na Alemanha, é bastante parecido com o que foi descrito
Para uma dimensão d dada, Klartag diz que é possível empacotar d vezes mais esferas do que na maior parte dos resultados anteriores
Ou seja, em 100 dimensões seriam cerca de 100 vezes mais esferas, e em um milhão de dimensões cerca de um milhão de vezes mais, o que soa gigantesco. Isso significaria, em vários sistemas de comunicação, um aumento de várias ordens de grandeza na largura de banda ou uma redução no consumo de energia?
Portanto, isso só ajuda em objetos que são naturalmente de alta dimensão. Objetos digitais não têm uma dimensão natural, isto é, comprimento em bytes, então é possível escolher uma dimensão pequena
https://en.m.wikipedia.org/wiki/Sphere_packing
Embora Klartag não seja, por formação, um especialista em empacotamento de esferas, ele é um dos grandes solucionadores de problemas por aí
No começo deste ano, resolveu a Hyperplane Conjecture e também vem contribuindo para avanços em problemas de teoria da convexidade, como a KLS Conjecture, a Mahler Conjecture e o teorema central do limite para corpos convexos
O trabalho de localização estocástica (Stochastic Localization) de seu aluno Eldan também já se mostrou central em algoritmos de amostragem log-côncava, o que se relaciona com a KLS Conjecture, e ele também palestrou no ICM
Além disso, as ferramentas usadas em geometria convexa, especialmente algumas de análise harmônica, também são bastante úteis no estudo de empacotamento de esferas
Então é difícil chamar isso de “inesperado”
Concordo com a visão de Klartag de que formas convexas são uma ferramenta matemática subestimada. Não sou matemático, mas já vi algoritmos de envoltória convexa resolverem problemas em lugares totalmente inesperados
Por exemplo, eu nunca imaginaria usar algoritmos de envoltória convexa em algo como um artigo sobre decomposição automática de paleta em imagens
https://www.rose-hulman.edu/class/cs/csse451/Papers/DILvGRB....
Pergunta de iniciante: o empacotamento de esferas ótimo tem correlação com reticulados regulares? Em 2 e 3 dimensões não é assim? Se for, isso se estenderia para n dimensões?
Isso foi provado em 2017 por Maryna Viazovska, e no segundo artigo houve coautores. https://doi.org/10.4007/annals.2017.185.3.7 https://doi.org/10.4007/annals.2017.185.3.8
Isto também vale a leitura: https://www.ams.org/journals/notices/201702/rnoti-p102.pdf
Nas outras dimensões, é uma questão em aberto, e no geral parece improvável que seja verdade. Em algumas dimensões, o empacotamento não regular mais denso conhecido é mais denso do que o empacotamento regular mais denso conhecido
Só que todos têm a mesma densidade do reticulado FCC. Esses empacotamentos podem ser construídos deslocando horizontalmente, umas em relação às outras, as camadas horizontais do FCC
Em dimensões mais altas, há a conjectura de que o empacotamento mais denso será sempre não reticulado. O motivo é que esses espaços não têm simetria suficiente
Hoje, mais cedo, houve um post dizendo que os neandertais derretiam gordura
Surgiu a observação de que os antropólogos não sabiam que era possível ferver coisas mesmo antes da invenção da cerâmica, e também que professores de ciências já conheciam essa possibilidade porque fazem isso em aula
Por fim, a linha da discussão era que, assim como alguém pesquisando glicose redescobriu a fórmula do trapézio da integração, às vezes a mesma coisa é redescoberta em áreas diferentes
Este também é mais um exemplo de como a especialização de outra área pode ajudar
Basta ver um vídeo no YouTube mostrando um método usado em situação de sobrevivência. Deve haver vários parecidos: https://www.youtube.com/shorts/0zun_UxO2vU
É verdade que não conheço o contexto, mas, sem uma fonte para uma afirmação tão surpreendente, isso não faz sentido. Nem passa no “teste da risada”