Um grande avanço na solução da hipótese de 60 anos de idade lança luz sobre como a ordem começa a aparecer neles com o crescimento de sistemas aleatórios
Uma equipe de matemáticos e cientistas da computação finalmente demonstrou progresso na solução, à primeira vista, de uma tarefa simples que atormentou os pesquisadores por quase seis décadas.
Essa tarefa, definida pelos matemáticos Pal Erdös e Richard Rado em 1960, diz respeito à frequência com que se pode esperar o aparecimento de padrões semelhantes a um girassol em grandes conjuntos de objetos - por exemplo, em um grande número de pontos espalhados em um plano. Embora o
novo resultado não resolva completamente a hipótese de Erdös e Rado, promove o entendimento dos matemáticos na aparência de estruturas surpreendentemente complexas em grupos aleatórios. Para esse fim, a tarefa foi reformulada em termos de uma função computacional, aproveitando a crescente relação entre ciência da computação teórica e matemática pura.
“Neste trabalho, uma ideia matemática se manifesta de uma maneira nova, que se tornará a idéia principal do nosso tempo. O resultado em si é incrível ”, disse
Gil Kalai, da Universidade Hebraica de Jerusalém.
A hipótese do girassol refere-se a conjuntos ou conjuntos de objetos. É mais fácil imaginar usando o exemplo de um conjunto de pontos no plano xy. Primeiro, selecione um número fixo de pontos que serão incluídos em cada conjunto. Em seguida, desenhe loops aleatórios para que cada loop, ou conjunto, inclua um número selecionado de pontos. Os loops podem se cruzar e alguns pontos podem cair em vários conjuntos, parecendo um diagrama de Venn.
Se você desenhar muitos loops contendo um grande número de pontos, a maioria deles se cruzará e se parecerá com os meandros das trepadeiras. Mas Erdös e Rado previram que uma estrutura refinada também resultaria: três ou mais conjuntos se cruzariam, deixando o mesmo subconjunto de pontos na interseção, enquanto nenhum desses conjuntos se cruzaria com outros conjuntos.
Se você remover esse subconjunto comum de pontos, os três conjuntos serão localizados ao redor do vazio e serão completamente separados um do outro - como pétalas em torno do meio escuro do girassol. O girassol mais simples é considerado como tendo três conjuntos que não se cruzam com nenhum outro; essas ilhas são chamadas de conjuntos disjuntos.
Erdös e Rado sugeriram que, à medida que o número de voltas aumenta, esses girassóis aparecerão inevitavelmente, na forma de conjuntos disjuntos ou na forma de conjuntos sobrepostos da maneira indicada. Essa hipótese do girassol faz parte de uma área mais geral da matemática chamada
teoria de Ramsey, que estuda como a ordem começa a aparecer nelas com o aumento do tamanho dos sistemas aleatórios.
"Se você tem um objeto matemático suficientemente grande, uma certa estrutura deve estar oculta", disse
Shachar Lovet, da Universidade da Califórnia em San Diego, co-autor de um novo trabalho no qual
Ryan Alweis, da Universidade de Princeton, também trabalhou, Keven Wu, da Universidade de Pequim. e
Jiapeng Zhang, da Universidade de Harvard.
Erdös e Rado queriam saber exatamente quantos conjuntos e qual o tamanho necessário para garantir um girassol. Eles deram o primeiro passo modesto para resolver o problema, definindo o parâmetro w, denotando o número de pontos em cada um dos conjuntos. Em seguida, eles provaram que são necessários cerca de w
w de conjuntos de tamanho w para garantir que um girassol composto por três conjuntos seja garantido para aparecer neles. Portanto, se você quiser usar conjuntos de 100 pontos, precisará de 100 a
100 conjuntos para garantir a aparência de um girassol.
Ao mesmo tempo, Erdös e Rado sugeriram que, na verdade, o número de conjuntos que garantem um girassol é muito menor que w
w - e mais como uma constante em grau w (por exemplo, 3
w ou 80
w ou 5 000 000
w ). No entanto, eles não conseguiram encontrar uma maneira de provar seu palpite.
"Eles disseram que a tarefa parecia extremamente simples e ficaram surpresos por não conseguirem progredir nela", disse Alveys.
E eles não estavam sozinhos. No período entre o primeiro resultado e esse novo trabalho, que apareceu 60 anos depois, apenas dois matemáticos fizeram pelo menos algum progresso nessa questão - e depois foram gradualmente, dando um passo em 1997 e o
segundo neste ano .
"Todo mundo já tentou todas as idéias com as quais as pessoas se sentem confortáveis", disse
Anup Rao, da Universidade de Washington, que publicou
trabalho adicional simplificando os métodos obtidos no novo resultado. "E ninguém foi capaz de melhorar a linha de base estabelecida por Erds e Rado."
Mas as novas evidências fizeram um grande avanço.
Quatro pesquisadores, incluindo matemáticos e cientistas da computação, conseguiram fazer isso dividindo a tarefa em dois cenários diferentes. No primeiro, mais fácil, eles examinaram o que aconteceria quando os conjuntos se cruzassem significativamente entre si, facilitando muito a compreensão de quando um girassol deveria aparecer ali.
"Quando você tem um conjunto de elementos que pertencem a um conjunto maior de conjuntos, pode usar essa estrutura", para procurar um girassol, disse Lovet.
A princípio, os pesquisadores se perguntaram se existe um conjunto de pontos pertencentes a uma parte suficientemente grande de todos os conjuntos no sistema. Tendo encontrado tais pontos, em sua busca por um girassol, eles se limitaram apenas à parte dos conjuntos que contêm esse conjunto de pontos. Então eles continuaram a agir da mesma maneira, refinando a pesquisa, incluindo nela cada vez menos conjuntos de sistemas, que têm cada vez mais pontos em comum. Esta poda continuou até encontrar o girassol.
Em um segundo cenário mais complexo, eles analisam o que acontecerá se os conjuntos não se cruzarem fortemente. Nesse caso, a maneira mais provável de obter um girassol é fazer três séries separadas. No entanto, provar que três conjuntos separados estão escondidos em conjuntos com um ligeiro cruzamento não é fácil.
É aqui que a ciência da computação entra em cena. Dois co-autores, Lovet e Zhang, tentam há vários anos analisar o problema do girassol usando as mesmas ferramentas que os cientistas da computação usam para estudar as funções booleanas. Essas funções executam operações em uma sequência de bits - uns e zeros - e produzem um único bit no final, correspondendo a uma declaração computacional ser verdadeira ou falsa. Por exemplo, uma função booleana pode ser programada para retornar 1 se pelo menos um dos bits de entrada for 1 e 0 se nenhum dos bits de entrada for 1.
Há três anos, Lovet e Zhang perceberam que poderia ser feita a mesma pergunta sobre se existem três conjuntos disjuntos entre um conjunto de conjuntos que não se cruzam fortemente. Primeiro, atribua um rótulo a cada ponto do conjunto: 1 se estiver contido apenas nesse conjunto e 0 em outro caso. Uma função booleana retorna 1 (verdadeiro) se cada ponto na entrada for 1 - ou seja, cada ponto do conjunto existe exclusivamente nesse conjunto, o que torna esse conjunto separado. O verdadeiro resultado sugere que existem condições adequadas para encontrar um girassol.
Comprovando rigorosamente essa correspondência, os pesquisadores usaram amplo conhecimento sobre as funções booleanas para atacar o problema do girassol, que anteriormente carecia de recursos. Eles provaram que os conjuntos (log w)
w são suficientes para obter um girassol. Tal resultado não é suficiente para provar a hipótese de que uma certa constante em grau w é suficiente para obter um girassol. Mas esse é um resultado de ordem de magnitude melhor do que o obtido por Erdös e Rado, e coincide aproximadamente com o número de conjuntos que eles previram.
Após meio século de falhas, o novo trabalho sugere que em breve veremos uma solução completa. Também melhora a compreensão de como formas especiais surgem inevitavelmente na natureza matemática do acaso.