Quatro matemáticos quebraram um recorde de 75 anos ao encontrar uma maneira mais densa de empacotar esferas de alta dimensão.
Os matemáticos gostam de generalizar conceitos em dimensões superiores.
Às vezes isso é fácil.
Se você deseja embalar quadrados em duas dimensões com eficiência, organize-os como um tabuleiro de xadrez.
Para comprimir cubos tridimensionais, você os empilha como caixas móveis.
Os matemáticos podem facilmente estender esses arranjos, empacotando cubos em espaços de dimensões superiores para preenchê-los perfeitamente.
Embalar esferas é muito mais difícil.
Os matemáticos sabem como agrupar círculos ou bolas de futebol de uma forma que minimize o espaço vazio entre eles.
Mas em quatro ou mais dimensões, o esquema de empacotamento mais eficiente é um completo mistério.
(Com exceção das dimensões 8 e 24, que foram resolvidas em 2016.) “Parece tão simples”, disse Julian Sahasrabudhe, matemático da Universidade de Cambridge.
“Pode haver 20 maneiras diferentes de abordar isso.
E parece que foi isso que aconteceu – há muitas ideias diferentes.” Os empacotamentos esféricos ótimos conhecidos em 2, 3, 8 e 24 dimensões parecem redes, cheias de padrões e simetria.
Mas em todas as outras dimensões, as melhores embalagens podem ser totalmente caóticas.
“Isso, eu acho, é um aspecto muito tentador.
É realmente muito aberto”, disse Akshay Venkatesh, matemático do Instituto de Estudos Avançados.
“Nós simplesmente não sabemos.” Em dezembro passado, Sahasrabudhe, junto com seu colega de Cambridge Marcelo Campos, Matthew Jenssen do King’s College London e Marcus Michelen da Universidade de Illinois, Chicago, forneceram uma nova receita de como compactar esferas densamente em todas as dimensões arbitrariamente altas.
É o primeiro avanço significativo no problema geral do empacotamento de esferas em 75 anos.
“É uma bela peça matemática”, disse Yufei Zhao, matemático do Instituto de Tecnologia de Massachusetts.
“Existem ideias novas e inovadoras.” Melhorando a Linha de Base: A maneira mais precisa de organizar círculos em um plano bidimensional é em um padrão hexagonal, com círculos colocados nos cantos e no centro de cada hexágono.
Essa grade preenche um pouco mais de 90% do plano.
Em 1611, o físico Johannes Kepler pensou na melhor forma de empacotar esferas tridimensionais.
Para a camada base, ele empacotou as esferas em um arranjo hexagonal, como os círculos.
Ele então colocou uma segunda camada de esferas sobre a primeira, preenchendo as lacunas.
Mas então há uma escolha fazendo.
A terceira camada pode ficar diretamente acima da primeira camada:
Ou pode ser compensado
Em ambos os casos, o padrão se repete.
E em ambos os casos, as esferas preenchem exatamente a mesma quantidade de espaço: cerca de 74%.
Em 1831, Carl Friedrich Gauss, um dos matemáticos mais proeminentes do século XIX, mostrou que as configurações de Kepler são as melhores redes possíveis – repetindo configurações semelhantes a uma grade – mas não foi capaz de descartar a possibilidade de que algum arranjo irregular pudesse funcionar melhor.
(Essa possibilidade foi finalmente descartada por volta da virada do milênio.) Em dimensões superiores, os matemáticos estavam perdidos.
Então, em 2016, Maryna Viazovska usou a existência de simetrias específicas do espaço de oito dimensões para provar que redes específicas são ótimas.
Ela também trabalhou com colaboradores para estender a prova para 24 dimensões.
Ela ganhou a Medalha Fields 2022, o maior prêmio em matemática, por este trabalho.
“O que adoro no [empacotamento esférico] é o modo como ele é um fio que conecta muitas áreas diferentes da matemática, da ciência da computação e da física”, disse Henry Cohn, matemático da Microsoft Research que trabalhou com Viazovska na prova de 24 dimensões.
Esses empacotamentos ótimos conhecidos – em uma, duas, três, oito e 24 dimensões – não parecem generalizar para dimensões superiores.
Em dimensões superiores, os matemáticos não sabem que percentagem de espaço um arranjo ideal preencheria.
Em vez disso, eles tentam aproximar isso.
Em qualquer dimensão, se você começar com uma caixa muito grande e preenchê-la sucessivamente com bolas – colando uma em qualquer lugar onde encontrar uma abertura grande o suficiente – então as esferas ocuparão pelo menos 1 2 d da caixa, onde d é a dimensão da caixa.
Assim, em duas dimensões, preencherão pelo menos 1/4 do espaço, e em três dimensões, preencherão pelo menos 1/8 do espaço, e assim por diante.
Em dimensões relativamente pequenas, os matemáticos geralmente conhecem empacotamentos específicos que funcionam muito melhor do que esse limite geral.
(Por exemplo, o empacotamento tridimensional do Kepler preenche 74% do espaço – significativamente mais do que os 12,5% mínimos%.) Mas o
“Esta é uma espécie de linha de base”, disse Zhao.
O progresso no estabelecimento de uma base melhor que generalize para dimensões arbitrárias tem sido lento.
Em 1905, o matemático Hermann Minkowski provou que, em qualquer número arbitrário de dimensões, existe uma rede que pode conter o dobro de bolas que a linha de base, através da colocação de uma esfera em cada ponto da rede.
A próxima melhoria substancial ocorreu em 1947, quando Claude Ambrose Rogers, um matemático inglês, apresentou uma rede ainda melhor.
Enquanto a melhoria de Minkowski em relação à linha de base foi por um fator constante, o esquema de Rogers foi uma melhoria “assintótica? em relação à linha de base, o que significa que à medida que o número de dimensões aumenta, também aumenta a diferença na eficiência do empacotamento.
Em 50 dimensões, Rogers poderia empacotar cerca de 50 vezes mais esferas que a linha de base, mas em 1.000 dimensões, seu empacotamento era aproximadamente 1.000 vezes melhor.
Nos últimos 75 anos, alguns resultados aqui e ali melhoraram o empacotamento de Rogers por um múltiplo constante, mas ninguém foi capaz de encontrar outra melhoria assintótica que funcionasse em todas as dimensões até agora.
Conectando os Pontos Campos, Jenssen, Michelen e Sahasrabudhe começaram trabalhando juntos no início da pandemia, reunindo-se no Zoom durante horas todos os dias – embora não, no início, sobre este problema.
Eles foram coautores de três artigos antes de se conhecerem pessoalmente no outono passado, quando Jenssen e Michelen vieram a Cambridge para uma visita de um mês.
Foi então que eles se voltaram para o problema do empacotamento de esferas.
“Foi durante esse período que começamos e essencialmente concluímos o problema do empacotamento de esferas”, disse Michelen.
“Foi definitivamente muito rápido e, de certa forma, foi uma surpresa.”
Os matemáticos abordaram o problema por meio de gráficos, que são coleções de vértices (pontos) conectados por arestas (linhas).
Os gráficos são frequentemente usados em combinatória e teoria das probabilidades, os principais campos de pesquisa dos autores.
Quase todos os limites inferiores de quão densamente as esferas podem ser compactadas vieram do estudo de estruturas semelhantes a treliças.
Mas o artigo recente usa a teoria dos grafos para criar empacotamentos altamente desordenados – uma abordagem muito diferente.
“Quando começamos a falar sobre isso, parecia um pouco intimidante”, disse Sahasrabudhe.
“Percebemos que poderíamos modelá-lo como um gráfico.
Aí começamos a nos sentir mais em casa.” Para criar sua embalagem, eles começaram espalhando pontos aleatoriamente no espaço.
Esses pontos acabariam por ser os centros das esferas no empacotamento.
Eles então desenharam uma linha conectando quaisquer dois pontos que estivessem muito próximos um do outro – as esferas centradas nesses dois pontos se sobreporiam.
Deste gráfico, eles queriam extrair um conjunto independente, que é uma coleção de vértices onde não há dois vértices conectados por uma aresta, como os mostrados em vermelho abaixo.
Se desenhassem esferas em todos os pontos de um conjunto independente, as bolas não se sobreporiam.
Eles formariam um empacotamento esférico.
É fácil criar um conjunto independente esparso – basta pegar alguns vértices de regiões distantes em um gráfico.
Mas para fazer um empacotamento esférico denso – com tantas bolas quanto possível – eles precisavam de um conjunto independente muito grande.
O desafio deles era extrair um conjunto independente usando uma grande porção de vértices no gráfico original.
Para fazer isso, eles usaram uma técnica chamada nibble de Rödl, em que se remove iterativamente (ou “mordisca”) pedaços do gráfico.
“É uma técnica super influente”, disse Sahasrabudhe.
“Isso remonta aos anos 80, mas nos últimos 10 a 15 anos, as pessoas têm realmente insistido nisso.” Eles começaram passando por todos os vértices do gráfico.
Em cada um deles, eles (metaforicamente) jogaram uma moeda com forte peso na direção da coroa.
Se o flip desse coroa, eles não faziam nada.
Se atingisse cara, eles removiam o vértice e o adicionavam a um novo gráfico.
Este processo de mordiscar criou um conjunto independente usando uma porção relativamente pequena do gráfico original.
Mas este conjunto independente não era suficientemente grande.
Então eles repetiram o processo, cortando mais pedaços do gráfico original e adicionando-os ao novo gráfico.
No final, eles obtiveram um grande conjunto independente do gráfico original, que era exatamente o que procuravam.
Esse avanço foi o ingrediente final da prova.
Com seu grande conjunto independente, eles criaram o empacotamento esférico mais denso conhecido em dimensões superiores e a primeira melhoria assintótica no limite de Rogers.
“O que me surpreende no novo artigo é a ideia simples e agradável que ele é”, disse Will Perkins, cientista da computação teórico do Instituto de Tecnologia da Geórgia.
Embora o novo resultado seja uma melhoria significativa, não é a resposta final.
Ninguém sabe quão próximo o novo empacotamento esférico está do ideal.
Em 2010, os físicos Francesco Zamponi e Giorgio Parisi teorizaram que o melhor empacotamento “amorfo? ou desordenado possível de esferas seria exatamente duas vezes mais denso que o recente avanço.
Portanto, os matemáticos podem estar se aproximando do limite de quão compactadas as esferas podem ser compactadas de maneira desordenada.
Mas é possível que uma esfera compactada em um padrão regular seja significativamente mais densa.
Na batalha perene entre a ordem e o caos, o novo empacotamento de esferas marca um ponto pela desordem.
Mas os matemáticos ainda estão indecisos sobre se a ordem ou a desordem vencerão.
“Neste caso, acho que é um verdadeiro mistério”, disse Perkins.
Publicado em 14/05/2024 02h31
Artigo original:
- https://www.quantamagazine.org/to-pack-spheres-tightly-mathematicians-throw-them-at-random-20240430/