a versão original de essa história apareceu em Revista Quanta.
Até agora este ano, quanta registrou três grandes avanços na teoria de Ramsey, o estudo de como evitar a criação de padrões matemáticos. O primeiro resultado coloque um novo limite em quão grande um conjunto de números inteiros pode ser sem conter três números espaçados uniformemente, como {2, 4, 6} ou {21, 31, 41}. O segundo e terceiro da mesma forma, coloque novos limites no tamanho das redes sem grupos de pontos que estão todos conectados ou todos isolados uns dos outros.
As provas abordam o que acontece quando os números envolvidos crescem infinitamente. Paradoxalmente, às vezes isso pode ser mais fácil do que lidar com quantidades incômodas do mundo real.
Por exemplo, considere duas questões sobre uma fração com um denominador muito grande. Você pode perguntar qual é a expansão decimal de, digamos, 1/42503312127361. Ou você pode perguntar se esse número vai se aproximar de zero à medida que o denominador cresce. A primeira pergunta é específica sobre uma quantidade do mundo real e é mais difícil de calcular do que a segunda, que pergunta como a quantidade 1/n mudará “assintoticamente” conforme n cresce. (Aproxima-se cada vez mais de 0.)
“Este é um problema que atormenta toda a teoria de Ramsey”, disse William Gasarch, um cientista da computação da Universidade de Maryland. “A teoria de Ramsey é conhecida por ter resultados assintoticamente muito bons.” Mas analisar números menores que o infinito requer uma caixa de ferramentas matemática totalmente diferente.
Gasarch estudou questões na teoria de Ramsey envolvendo números finitos que são grandes demais para o problema ser resolvido pela força bruta. Em um projeto, ele assumiu a versão finita do primeiro dos avanços deste ano – um artigo de fevereiro de Zander Kelleyum estudante de pós-graduação da Universidade de Illinois, Urbana-Champaign, e Raghu Meka da Universidade da Califórnia, Los Angeles. Kelley e Meka encontraram um novo limite superior para quantos inteiros entre 1 e N você pode colocar em um conjunto, evitando progressões de três termos ou padrões de números uniformemente espaçados.
Embora o resultado de Kelley e Meka se aplique mesmo se N é relativamente pequeno, não fornece um limite particularmente útil nesse caso. Para valores muito pequenos de N, é melhor seguir métodos muito simples. Se N é, digamos, 5, basta olhar para todos os possíveis conjuntos de números entre 1 e Ne escolha o maior sem progressão: {1, 2, 4, 5}.
Mas o número de diferentes respostas possíveis cresce muito rapidamente e torna muito difícil empregar uma estratégia tão simples. Existem mais de 1 milhão de conjuntos compostos por números entre 1 e 20. Existem mais de 1060 usando números entre 1 e 200. Encontrar o melhor conjunto livre de progressão para esses casos exige uma grande dose de poder de computação, mesmo com estratégias de melhoria de eficiência. “Você precisa ser capaz de espremer muito desempenho das coisas”, disse James Glenn, um cientista da computação da Universidade de Yale. Em 2008, Gasarch, Glenn e Clyde Kruskal da Universidade de Maryland escreveu um programa para encontrar as maiores séries livres de progressão até um N de 187. (Trabalhos anteriores obtiveram as respostas até 150, bem como para 157.) Apesar de uma lista de truques, seu programa levou meses para ser concluído, disse Glenn.
