DESTAQUE
Uma equipe de matemáticos e cientistas da computação finalmente avançou em um problema aparentemente simples que atormentou os pesquisadores por quase seis décadas.
Colocado pelos matemáticos Paul Erd?s e Richard Rado em 1960, o problema diz respeito à frequência com que você esperaria encontrar padrões semelhantes aos girassóis em grandes coleções de objetos, como uma grande dispersão de pontos no avião. Embora o novo resultado não resolva completamente a conjectura de girassol de Erd?s e Rado, ele avança na compreensão matemática de como estruturas surpreendentemente intrincadas emergem da aleatoriedade. Para isso, reinventou o problema em termos de função de computador – aproveitando a interação cada vez mais rica entre ciência da computação teórica e matemática pura.
“O artigo é uma nova manifestação de uma ideia matemática que será uma ideia central do nosso tempo. O resultado em si é espetacular ?, disse Gil Kalai, da Universidade Hebraica de Jerusalém.
A conjectura de girassol é sobre conjuntos, que são coleções de objetos. A conjectura é mais fácil de visualizar se você pensar em conjuntos de pontos no plano xy plano. Primeiro, decida um número fixo de pontos que você deseja incluir em cada conjunto. Em seguida, desenhe loops aleatoriamente para que cada loop, ou conjunto, abranja esse número de pontos. Tudo bem se os loops se sobrepuserem, então alguns pontos podem acabar em mais de um conjunto, como as interseções em um diagrama de Venn.
Se você desenhar muitos loops que contenham um grande número de pontos, a maioria dos loops se sobreporá e se enredará como um emaranhado de sarças. Mas Erd?s e Rado previram que uma estrutura delicada invariavelmente surgiria: três ou mais conjuntos se sobreporiam em parte exatamente no mesmo subconjunto de pontos, e nenhum deles se sobreporia a outros conjuntos.
Se você excluir esse subconjunto comum de pontos, os três conjuntos serão dispostos em torno de um vazio, completamente separados um do outro – como pétalas em torno do centro escuro de um girassol. Para os propósitos do problema, o tipo mais simples de girassol é considerado um com três conjuntos que não se sobrepõem nem a nenhum outro conjunto; essas ilhas são chamadas de conjuntos “disjuntos”.
Erd?s e Rado conjeturaram que, à medida que você desenha mais laços, um girassol emerge inevitavelmente, como conjuntos disjuntos ou conjuntos que se sobrepõem da maneira certa. Sua conjectura de girassol é parte de uma área mais ampla da matemática chamada teoria de Ramsey, que estuda como a ordem começa a aparecer à medida que os sistemas aleatórios aumentam.
“Se você tem um objeto matemático grande o suficiente de alguma natureza, deve haver alguma estrutura oculta dentro dele”, disse Shachar Lovett, da Universidade da Califórnia, em San Diego, co-autor do novo trabalho, juntamente com Ryan Alweiss, de Princeton. Universidade, Kewen Wu, da Universidade de Pequim, e Jiapeng Zhang, da Universidade de Harvard.
Erd?s e Rado queriam saber exatamente quantos conjuntos – exatamente de qual tamanho – você precisa para garantir um girassol. Eles deram um primeiro passo modesto para resolver o problema, estabelecendo um parâmetro, w, que representava o número de pontos em cada conjunto. O par então provou que você precisava de dois conjuntos de tamanho w para encontrar um girassol feito de três conjuntos. Portanto, se você deseja que cada conjunto contenha 100 pontos, eles provaram que você precisa da ordem de 100100 conjuntos para garantir um girassol.
Ao mesmo tempo, Erd?s e Rado conjeturaram que o número real de conjuntos necessários para garantir um girassol é muito menor que ww – é mais como um número constante da potência w (portanto, 3w ou 80w ou 5.000.000w). No entanto, eles não conseguiram encontrar uma maneira de provar que sua intuição estava correta.
“Eles disseram que esse problema parece extremamente simples e estavam se perguntando por que não conseguiram avançar nele”, disse Alweiss.
Eles não eram os únicos. Entre o primeiro resultado de Erd?s e Rado e essa nova prova, 60 anos depois, apenas dois matemáticos fizeram algum progresso na questão – e eles apenas fizeram avanços incrementais, um em 1997 e outro no início deste ano.
“Todo mundo tentou todas as idéias com as quais as pessoas se sentiam confortáveis”, disse Anup Rao, da Universidade de Washington, que publicou um documento de acompanhamento que simplificou os métodos por trás desse novo resultado. “Nenhum deles parecia capaz de melhorar o limite básico que Erd?s e Rado provaram.”
Por outro lado, a nova prova é um grande avanço.
Os quatro pesquisadores – uma mistura de matemáticos e cientistas da computação – conseguiram o feito dividindo o problema em dois cenários distintos. No primeiro e mais fácil cenário, eles consideraram o que acontece quando os conjuntos têm sobreposição substancial, o que torna relativamente fácil entender quando um girassol deve aparecer.
“Quando você tem uma coleção de elementos que pertencem a uma grande coleção de conjuntos, existe uma estrutura que você pode explorar” para encontrar um girassol, disse Lovett.
Os pesquisadores primeiro perguntam se existe um conjunto de pontos que é comum a uma grande fração do total de conjuntos no sistema. Depois de identificar esse conjunto de pontos, eles restringem sua busca por um girassol à fração do total de conjuntos que contém esse conjunto de pontos. Eles procedem dessa maneira, refinando sua pesquisa para incluir uma fração cada vez menor do total de conjuntos no sistema que tem cada vez mais pontos em comum. Esta poda continua até encontrar um girassol.
No segundo e mais difícil cenário, eles analisam o que acontece quando os conjuntos não se sobrepõem muito. Nesse caso, a maneira mais provável de produzir um girassol é ter três conjuntos separados. Mas não é fácil provar que três conjuntos completamente separados se ocultam entre um grande número de itens ligeiramente sobrepostos.
É aí que entra a conexão com a ciência da computação. Por vários anos, dois dos co-autores – Lovett e Zhang – tentaram analisar o problema do girassol usando as mesmas ferramentas que os cientistas da computação usam para estudar um tipo de programa chamado booleano. função. Essas funções executam operações em uma série de bits – 1s e 0s – e emitem um único bit no final, correspondendo se a declaração computacional é verdadeira (1) ou falsa (0). Por exemplo, uma função booleana pode ser programada para gerar 1 se pelo menos um de seus bits de entrada for 1 e gerar 0 se nenhuma das entradas for 1.
Três anos atrás, Lovett e Zhang perceberam que a questão de saber se três conjuntos disjuntos estão ou não presentes em uma coleção de conjuntos ligeiramente sobrepostos poderia ser considerada da mesma maneira. Primeiro, você atribui a cada ponto de um conjunto específico um rótulo: 1 se estiver contido apenas nesse conjunto e 0 se não estiver. A função booleana emitirá um 1 (verdadeiro) se cada ponto de entrada for 1 – significando que cada ponto do conjunto está exclusivamente nesse conjunto, tornando o conjunto separado. Um resultado “verdadeiro” indica, portanto, que as condições certas estão presentes para você encontrar um girassol.
Ao provar rigorosamente essa correspondência, os pesquisadores trouxeram amplo conhecimento sobre as funções booleanas para o problema do girassol com poucos recursos. Eles provaram que os conjuntos (log w) w são suficientes para produzir um girassol. O novo resultado não chega a provar que o número conjecturado de conjuntos (um número constante à potência w) é suficiente para garantir um girassol. Mas é uma ordem de magnitude melhor do que o resultado da ww de Erd?s e Rado, e é em torno do número de sets que os dois previstos devem ser necessários para produzir um girassol.
Após meio século de falha, o novo trabalho sugere que uma solução completa está à vista. Também explica a inevitabilidade com que formas especiais se enraízam na natureza matemática aleatória.
Publicado em 21/02/2020 21h16
Artigo original:
Estudo original:
Achou importante? Compartilhe!
Assine nossa newsletter e fique informado sobre Astrofísica, Biofísica, Geofísica e outras áreas. Preencha seu e-mail no espaço abaixo e clique em “OK”: