Matemáticos concluem a missão para construir 'cubos esféricos'

No século IV, o matemático grego Pappus de Alexandria elogiou as abelhas por sua “previsão geométrica”. A estrutura hexagonal de seu favo de mel parecia a maneira ideal de dividir o espaço bidimensional em células de área igual e perímetro mínimo - permitindo que os insetos reduzissem a quantidade de cera que precisavam produzir e gastassem menos tempo e energia construindo seus colmeia.

Ou então Pappus e outros hipotetizaram. Por milênios, ninguém conseguiu provar que os hexágonos eram ótimos – até que finalmente, em 1999, o matemático Thomas Hales mostrou que nenhuma outra forma poderia ser melhor. Hoje, os matemáticos ainda não sabem quais formas podem ladrilhar três ou mais dimensões com a menor área de superfície possível.

Esse problema da “espuma” acabou tendo uma ampla gama de aplicações – para físicos que estudam o comportamento de bolhas de sabão (ou espumas) e químicos que analisam a estrutura de cristais, para matemáticos que exploram arranjos de empacotamento de esferas e estatísticos que desenvolvem técnicas eficazes de processamento de dados .

Em meados dos anos 2000, uma formulação particular do problema da espuma também chamou a atenção de cientistas teóricos da computação, que descobriram, para sua surpresa, que ela estava profundamente ligada a um importante problema em aberto em seu campo. Eles foram capazes de usar essa conexão para encontrar uma nova forma de alta dimensão com área de superfície mínima.

“Adoro esse vai e vem”, disse Assaf Naor da Universidade de Princeton. “Algumas matemáticas antigas tornam-se relevantes para a ciência da computação; a ciência da computação retribui e resolve a questão da matemática. É muito bom quando isso acontece.”

Mas aquela forma, embora ótima, faltava algo importante: uma base geométrica. Como sua existência foi comprovada usando técnicas da ciência da computação, sua geometria real era difícil de entender. É o que Naor, junto com Oded Regev, um cientista da computação do Instituto Courant da Universidade de Nova York, decidiu corrigir em uma prova postada online no mês passado.

“É um final muito bom para a história”, disse Regev.

Espumas cúbicas

Os matemáticos consideraram outras versões do problema da espuma – incluindo o que acontece se você só puder particionar o espaço de acordo com o que é chamado de rede inteira. Nessa versão do problema, você pega uma matriz quadrada de pontos igualmente espaçados (cada um com 1 unidade de distância) e transforma cada um desses pontos no centro de uma forma. O problema da espuma “cúbica” pergunta qual será a área de superfície mínima quando for necessário ladrilhar o espaço dessa maneira.

Inicialmente, os pesquisadores estavam interessados ​​em impor essa restrição para entender propriedades de espaços topológicos chamados variedades. Mas a questão ganhou vida própria, tornando-se relevante na análise de dados e outras aplicações.

Também é geometricamente interessante, porque muda o significado de “ideal”. Em duas dimensões, por exemplo, os hexágonos regulares não podem mais ladrilhar o plano se puderem ser deslocados apenas por quantidades inteiras nas direções horizontal e vertical. (Você tem que movê-los por quantidades irracionais em uma das duas direções.)

Os quadrados podem. Mas isso é o melhor que pode ser feito? Como o matemático Jaigyoung Choe descoberto em 1989, a resposta é não. A forma ideal é um hexágono que foi comprimido em uma direção e alongado em outra. (O perímetro desse hexágono é de aproximadamente 3.86 quando sua área é 1 — superando o perímetro do quadrado de 4.)

Essas diferenças podem parecer triviais, mas ficam muito maiores em dimensões mais altas.

Dentre todas as formas de um dado volume, a que minimiza a área de superfície é a esfera. Como n, o número de dimensões cresce, a área da superfície da esfera aumenta proporcionalmente à raiz quadrada de n.

Mas as esferas não podem ladrilhar um espaço sem deixar lacunas. Por outro lado, um ncubo tridimensional de volume 1 lata. O problema é que sua área de superfície é 2n, crescendo na proporção direta de sua dimensão. Um cubo de 10,000 dimensões de volume 1 tem uma área de superfície de 20,000 - muito maior que 400, a área de superfície aproximada de uma esfera de 10,000 dimensões.

E assim os pesquisadores se perguntaram se poderiam encontrar um “cubo esférico” – uma forma que se encaixa nespaço tridimensional, como um cubo, mas cuja superfície cresce lentamente, como a de uma esfera.

Parecia improvável. “Se você deseja que sua bolha preencha exatamente o espaço e seja centralizada nessa grade cúbica, é difícil pensar sobre o que você usaria, exceto uma bolha cúbica”, disse Ryan O'Donnell, um cientista da computação teórico da Carnegie Mellon University. “Realmente parece que o cubo deve ser o melhor.”

Agora sabemos que não é.

A dureza dos problemas difíceis

Durante décadas, o problema da espuma cúbica permaneceu relativamente inexplorado em dimensões superiores. Os primeiros pesquisadores a fazer progressos não vieram do reino da geometria, mas da ciência da computação teórica. Eles o encontraram por acaso, enquanto procuravam uma maneira de provar uma afirmação central em seu campo conhecida como conjectura de jogos únicos. “A conjectura dos jogos únicos”, disse Regev, “é o que vejo atualmente como a maior questão em aberto na ciência da computação teórica”.

Proposto em 2002 por Subhash Khot, um estudante de pós-graduação na época, a conjectura postula que, se um determinado problema — aquele que envolve a atribuição de cores aos nós de uma rede — não puder ser resolvido exatamente, será muito difícil encontrar uma solução aproximada. Se verdadeira, a conjectura permitiria aos pesquisadores entender a complexidade de uma vasta variedade de outras tarefas computacionais de uma só vez.

Os cientistas da computação geralmente classificam as tarefas com base em se elas podem ser resolvidas com um algoritmo eficiente ou se são "NP-difíceis" (o que significa que não podem ser resolvidas com eficiência à medida que o tamanho do problema aumenta, desde que uma crença amplamente aceita mas a conjectura não comprovada sobre a complexidade computacional é verdadeira). Por exemplo, o problema do caixeiro viajante, que pede o caminho mais curto necessário para visitar todas as cidades em uma rede apenas uma vez, é NP-difícil. Assim como determinar se um grafo — uma coleção de vértices conectados por arestas — pode ser rotulado com no máximo três cores, de modo que quaisquer dois vértices conectados tenham cores diferentes.

Acontece que é NP-difícil encontrar até mesmo uma solução aproximada para muitas dessas tarefas. Digamos que você queira rotular os vértices de um grafo com cores diferentes de uma forma que satisfaça alguma lista de restrições. Se é NP-difícil satisfazer todas essas restrições, que tal tentar cumprir apenas 90% delas, ou 75%, ou 50%? Abaixo de algum limite, pode ser possível criar um algoritmo eficiente, mas acima desse limite, o problema torna-se NP-difícil.

Durante décadas, os cientistas da computação trabalharam para estabelecer limites para diferentes problemas de otimização de interesse. Mas algumas perguntas escapam a esse tipo de descrição. Embora um algoritmo possa garantir 80% da melhor solução, pode ser NP-difícil alcançar 95% da melhor solução, deixando incerta a questão de onde exatamente entre 80% e 95% o problema cai no território NP-difícil.

A conjectura de jogos exclusivos, ou UGC, oferece uma maneira de identificar imediatamente a resposta. Ele faz uma afirmação que a princípio parece mais limitada: que é NP-difícil dizer a diferença entre um gráfico para o qual você pode satisfazer quase todo um certo conjunto de restrições de coloração (digamos, mais de 99%) e um gráfico para que você pode satisfazer quase nenhum (digamos, menos de 1%).

Mas logo após o UGC ter sido proposto em 2002, os pesquisadores mostraram que, se a conjectura for verdadeira, você pode calcular facilmente o limite de dureza para qualquer problema de satisfação de restrição. (Isso ocorre porque o UGC também implica que um algoritmo conhecido alcança a melhor aproximação possível para todos esses problemas.) “Foi precisamente o eixo para todos esses problemas de otimização”, disse O'Donnell.

E assim os cientistas da computação teóricos começaram a provar o UGC - uma tarefa que acabou levando alguns deles a descobrir cubos esféricos.

Tornando Problemas Difíceis Mais Difíceis

Em 2005, O'Donnell trabalhava na Microsoft Research. Ele e dois colegas - Uriel Feige, agora no Weizmann Institute of Science, e Cara Kindler, agora na Universidade Hebraica de Jerusalém - se uniram para enfrentar o UGC.

Eles tinham uma vaga ideia de como queriam proceder. Eles começariam com uma pergunta sobre gráficos — muito semelhante ao UGC. O chamado problema de corte máximo (“max-cut”) pergunta, quando dado um grafo, como particionar seus vértices em dois conjuntos (ou cores) de modo que o número de arestas conectando esses conjuntos seja o maior possível. (Você pode pensar no corte máximo como uma questão sobre a melhor maneira de colorir um gráfico com duas cores, de modo que o menor número possível de arestas conecte os vértices da mesma cor.)

Se o UGC for verdadeiro, isso implicaria que, dado algum gráfico aleatório, um algoritmo de aproximação eficiente só pode chegar a cerca de 87% do corte máximo verdadeiro desse gráfico. Fazer melhor seria NP-difícil.

Em vez disso, Feige, Kindler e O'Donnell queriam ir na direção oposta: eles esperavam mostrar que o corte máximo é difícil de estimar e, em seguida, usar isso para provar o UGC. O plano deles baseava-se na força de uma técnica chamada repetição paralela – uma estratégia inteligente que torna os problemas difíceis ainda mais difíceis.

Digamos que você saiba que é NP-difícil distinguir entre um problema que você pode resolver e um que você pode resolver principalmente. A repetição paralela permite que você desenvolva isso para mostrar um resultado de dureza muito mais forte: que também é NP-difícil distinguir entre um problema que você pode resolver e um que você mal consegue resolver. “Esse fenômeno profundo e não intuitivo… está no âmago de grande parte da ciência da computação hoje”, disse Naor.

Mas há um porém. A repetição paralela nem sempre amplifica a dificuldade de um problema tanto quanto os cientistas da computação desejam. Em particular, há aspectos do problema do corte máximo que “criam uma grande dor de cabeça para a repetição paralela”, disse Regev.

Feige, Kindler e O'Donnell se concentraram em mostrar que a repetição paralela poderia funcionar apesar das dores de cabeça. “Isso é uma coisa realmente complicada de analisar”, disse Dana Moshkovitz, um cientista da computação teórico da Universidade do Texas, Austin. “Mas isso parecia tentadoramente próximo. A repetição paralela parecia que [ajudaria a fazer] essa conexão do corte máximo para jogos únicos.”

Como aquecimento, os pesquisadores tentaram entender a repetição paralela para um caso simples de corte máximo, o que Moshkovitz chamou de “o corte máximo mais estúpido”. Considere um número ímpar de vértices conectados por arestas para formar um círculo ou “ciclo ímpar”. Você deseja rotular cada vértice com uma das duas cores para que nenhum par de vértices adjacentes tenha a mesma cor. Nesse caso, isso é impossível: uma aresta sempre conectará vértices da mesma cor. Você tem que deletar essa aresta, “quebrando” o ciclo ímpar, para que seu gráfico satisfaça a restrição do problema. Por fim, você deseja minimizar a fração total de arestas que precisa excluir para colorir adequadamente seu gráfico.

A repetição paralela permite que você considere uma versão de alta dimensão desse problema — na qual você precisa quebrar todos os ciclos ímpares que aparecem. Feige, Kindler e O'Donnell precisavam mostrar que, à medida que o número de dimensões aumenta, é preciso excluir uma fração muito grande de arestas para quebrar todos os ciclos ímpares. Se isso fosse verdade, significaria que a repetição paralela poderia efetivamente amplificar a dificuldade desse problema de “corte máximo estúpido”.

Foi quando a equipe descobriu uma curiosa coincidência: havia uma maneira geométrica de interpretar se a repetição paralela funcionaria da maneira que eles esperavam. O segredo está na área da superfície das espumas cúbicas.

Dos limões à limonada

O problema deles, reescrito na linguagem das espumas, resumia-se a mostrar que os cubos esféricos não podem existir – que é impossível dividir o espaço de alta dimensão ao longo da rede inteira em células com área de superfície muito menor que a do cubo. (Uma área de superfície maior corresponde à necessidade de excluir mais arestas “ruins” no gráfico de ciclos ímpares, como os cientistas da computação esperavam mostrar.)

“Nós pensamos, oh, que problema estranho de geometria, mas provavelmente é verdade, certo?” disse O'Donnell. “Nós realmente precisávamos que fosse a verdadeira resposta.” Mas ele, Feige e Kindler não puderam provar. Assim, em 2007, eles publicou um artigo descrevendo como eles planejavam usar esse problema para ajudar a atacar o UGC.

Logo, suas esperanças foram frustradas.

Correu Raz, um cientista da computação teórico em Princeton que já havia provado vários resultados importantes sobre a repetição paralela, ficou intrigado com o artigo. Ele decidiu analisar a repetição paralela para o problema do ciclo ímpar, em parte por causa da conexão com a geometria que Feige, Kindler e O'Donnell haviam descoberto.

Raz não começou com o problema da espuma, mas atacou de frente a versão da ciência da computação da questão. Ele mostrou que você pode deletar muito menos arestas para quebrar todos os ciclos ímpares em um gráfico. Em outras palavras, a repetição paralela não pode amplificar suficientemente a dificuldade desse problema de corte máximo. “Os parâmetros que se obtém exatamente da repetição paralela ficam aquém de fornecer isso”, disse Moshkovitz.

“Nosso plano de usar a repetição paralela para mostrar a dificuldade de jogos únicos nem funcionou no caso mais simples”, disse O'Donnell. “Isso meio que quebrou todo o plano.”

Embora decepcionante, o resultado de Raz também sugeriu a existência de cubos esféricos: formas capazes de n-espaço dimensional com uma área de superfície dimensionada em proporção à raiz quadrada de n. “Pensamos, bem, vamos fazer dos limões uma limonada e pegar esse resultado técnico decepcionante sobre repetição paralela e gráficos discretos e transformá-lo em um resultado legal e interessante em geometria”, disse O'Donnell.

Ele e Kindler, em colaboração com os cientistas da computação Anup Rao e Avi Wigderson, se debruçaram sobre a prova de Raz até aprenderem suas técnicas bem o suficiente para traduzi-las para o problema da espuma. Em 2008, eles mostraram que cubos esféricos são realmente possíveis.

“É uma boa maneira de raciocinar sobre o problema”, disse Mark Braverman de Princeton. "É lindo."

E levantou questões sobre o lado da geometria da história. Como eles usaram o trabalho de Raz sobre repetição paralela para construir sua forma de ladrilhos, Kindler, O'Donnell, Rao e Wigderson acabaram com algo feio e parecido com Frankenstein. O ladrilho estava bagunçado e cheio de reentrâncias. Em termos matemáticos, não era convexo. Embora isso funcionasse para seus propósitos, o cubo esférico carecia das propriedades preferidas dos matemáticos – propriedades que tornam uma forma mais concreta, mais fácil de definir e estudar e mais adequada para possíveis aplicações.

“Há algo muito insatisfatório na construção deles”, disse Regev. “Parece uma ameba. Não se parece com o que você esperaria, um belo corpo de ladrilhos.

Foi isso que ele e Naor decidiram descobrir.

Libertando-se da Jaula

Desde o início, Naor e Regev perceberam que teriam que começar do zero. “Em parte porque os corpos convexos são tão restritivos, nenhuma das técnicas anteriores teve qualquer chance de funcionar”, disse Dor Minzer, um cientista da computação teórico do Instituto de Tecnologia de Massachusetts.

Na verdade, era totalmente plausível que a convexidade fosse muito restritiva – que um cubo esférico convexo simplesmente não existe.

Mas no mês passado, Naor e Regev provaram que você pode particionar nespaço tridimensional ao longo de coordenadas inteiras com uma forma convexa cuja área de superfície é bem próxima à da esfera. E eles fizeram isso inteiramente de forma geométrica – devolvendo o problema às suas raízes matemáticas.

Eles primeiro tiveram que contornar um grande obstáculo. O problema da espuma cúbica requer que cada ladrilho seja centrado em coordenadas inteiras. Mas na rede inteira, existem distâncias muito curtas entre alguns pontos – e essas distâncias curtas causam problemas.

Considere um ponto na grade bidimensional. Ele está localizado a 1 unidade de distância de seus pontos mais próximos nas direções horizontal e vertical. Mas na direção diagonal, o ponto mais próximo está $latex sqrt{2}$ unidades de distância — uma discrepância que piora em espaços maiores. No n-dimensional integer lattice, os pontos mais próximos ainda estão a 1 unidade de distância, mas esses pontos “diagonais” estão agora $latex sqrt{n}$ unidades de distância. Em, digamos, 10,000 dimensões, isso significa que o vizinho “diagonal” mais próximo de qualquer ponto está a 100 unidades de distância, embora existam 10,000 outros pontos (um em cada direção) que estão a apenas 1 unidade de distância.

Em outras redes, esses dois tipos de distância crescem proporcionalmente um ao outro. Os matemáticos sabem há décadas como ladrilhar essas redes com formas convexas de área de superfície mínima.

Mas na rede inteira, as distâncias mais curtas sempre serão fixadas em 1. Isso atrapalha a construção de um ladrilho de boa aparência com a área de superfície ideal. “Eles meio que colocam você nesta jaula”, disse Regev. “Eles deixam tudo muito apertado ao seu redor.”

Então, Naor e Regev, em vez disso, consideraram uma fatia de todo o n- espaço dimensional. Eles escolheram cuidadosamente esse subespaço para que ainda fosse rico em pontos inteiros, mas nenhum desses pontos estaria muito próximo.

Em outras palavras, o subespaço com o qual eles acabaram era exatamente o tipo que os matemáticos já sabiam como ladrilhar de maneira ideal.

Mas isso foi apenas metade do trabalho. Naor e Regev precisavam dividir todo o espaço, não apenas uma parte dele. Para obter um ncubo esférico multidimensional, eles tiveram que multiplicar seu ladrilho eficiente com um ladrilho do espaço restante (semelhante a como você pode multiplicar um quadrado bidimensional com um segmento de linha unidimensional para obter um cubo tridimensional). Fazer isso elevaria sua construção de volta ao espaço original, mas também aumentaria sua área de superfície.

A dupla teve que mostrar que o ladrilho do espaço restante, que não era tão ideal, não aumentava muito a área da superfície. Uma vez que eles fizeram isso, sua construção foi concluída. (A área de superfície de sua forma final acabou sendo um pouco maior do que a do cubo esférico não convexo, mas eles acreditam que pode ser possível encontrar um ladrilho convexo que seja tão eficiente quanto seu equivalente não convexo.)

“A prova deles é completamente diferente” do trabalho anterior sobre cubos esféricos, disse o matemático Noga Alon. “E, em retrospecto, talvez seja uma prova mais natural. Isso é o que alguém deveria ter tentado para começar.

“Quando as coisas são feitas de maneira diferente”, acrescentou Raz, “às vezes você encontra implicações adicionais interessantes”.

Esperança reacendeu

Ainda não está claro quais podem ser essas implicações - embora o trabalho explore o uso potencial de redes inteiras em criptografia e outras aplicações. Dado o quanto esse problema está conectado a outros campos, “é provável que leve a outras coisas”, disse Alon.

No momento, os cientistas da computação não veem uma maneira de interpretar o resultado convexo na linguagem da repetição paralela e do UGC. Mas eles não desistiram totalmente do plano original de usar o problema da espuma para provar a conjectura. “Existem várias maneiras de tentar subverter as barreiras óbvias que encontramos”, disse Kindler.

Braverman e Minzer tentaram uma dessas maneiras quando espumas revisitadas em 2020. Em vez de exigir que a forma ladrilhada seja convexa, eles pediram que obedecesse a certas simetrias, de modo que parecesse a mesma, não importando como você invertesse suas coordenadas. (Em 2D, um quadrado funcionaria, mas um retângulo não; nem os cubos esféricos de alta dimensão descritos até o momento.) Sob essa nova restrição, a dupla foi capaz de mostrar o que Kindler e outros esperavam 15 anos antes: que você não pode fazer muito melhor do que a área da superfície do cubo, afinal.

Isso correspondia a um tipo diferente de repetição paralela - uma que tornaria o caso mais simples de corte máximo tão difícil quanto necessário. Embora o resultado ofereça alguma esperança para esta linha de pesquisa, não está claro se esta versão da repetição paralela funcionará para todos os problemas de corte máximo. “Isso não significa que você acabou”, disse Braverman. “Significa apenas que você está de volta aos negócios.”

“Há muito potencial na geometria”, disse Minzer. “É só que não entendemos bem o suficiente.”