Algoritmo reduz limite de incerteza na resolução do teorema de Ramsey, maior avanço em 88 anos no estudo desse problema
Ilustração baseada no teorema de Ramsey
Vitória Couto / Revista Pesquisa FAPESP
Em 16 de março passado, três seminários foram ministrados de forma coordenada e quase simultânea sobre o mesmo problema matemático em três centros de estudo. Com doutorado obtido havia menos de uma semana no Instituto de Matemática Pura e Aplicada (Impa), no Rio de Janeiro, o paulista Marcelo Campos falou para uma plateia de cerca de 20 pessoas no Instituto de Matemática e Estatística da Universidade de São Paulo (IME-USP). O britânico Simon Griffiths, professor da Pontifícia Universidade Católica do Rio de Janeiro (PUC-RJ), fez uma apresentação no Impa e o canadense Julian Sahasrabudhe discorreu sobre o tema na Faculdade de Matemática da Universidade de Cambridge, no Reino Unido.
Ainda naquele dia, terminados os seminários, a trinca de matemáticos, mais o colega britânico Rob Morris, pesquisador do Impa, subiu um artigo científico a oito mãos no arXiv, um repositório de preprints, estudos ainda não revisados por pares. A essa altura, parte da comunidade de pesquisadores da área de combinatória, ramo da matemática que estuda as propriedades extremas, típicas e estruturais de objetos finitos, já tinha tomado contato com o trabalho. “Basicamente, todos os especialistas em combinatória se esforçaram muito para responder a essa pergunta – inclusive eu – e acho que é justo dizer que é um dos dois ou três principais problemas em aberto na combinatória extrema, ou talvez até mesmo o principal”, tuitou o britânico Timothy Gowers, ganhador da medalha Fields, um dos maiores prêmios da matemática, um dia depois de ter visto, maravilhado, o seminário em Cambridge.
Conforme seu título anunciava, o trabalho do quarteto trazia “um avanço exponencial” sobre o teorema de Ramsey, representado pela notação R(k). Trata-se de um problema de enunciado muito simples, mas que, desde 1935, não era alvo de nenhum progresso realmente significativo no caminho de sua elucidação. “Não resolvemos o teorema”, explica Campos. “O que fizemos foi criar um algoritmo que reduziu o valor do limite superior da resposta do teorema.”
Parece pouco para quem não é da área, mas o resultado foi saudado mundo afora como um feito e o artigo foi alvo de reportagens em meios de comunicação especializados em ciência e na imprensa em geral. “Fiquei chocado”, comentou o matemático Yuval Wigderson, da Universidade de Tel Aviv, em entrevista à Quanta Magazine, ao tomar conhecimento do trabalho. “Fiquei literalmente tremendo de meia a uma hora.” O pesquisador Guilherme Mota, do IME-USP, que organizou o seminário dado por Campos na universidade paulista, também se surpreendeu com a contribuição de seus colegas. “Todo mundo da área de combinatória já se debruçou em algum momento sobre esse teorema”, diz Mota, que atua nesse campo e tem trabalhos com dois dos quatro autores do novo artigo. “Depois de tanto tempo sem grandes avanços, ninguém esperava por essa notícia.”
Formulado em 1930 pelo matemático britânico Frank Plumpton Ramsey (1903-1930), o teorema que leva seu nome é tão simples de entender como difícil de resolver à medida que aumenta o valor do número inteiro envolvido em sua formulação. Uma popular adaptação de seu enunciado formal coloca a questão em termos do cotidiano. Qual é a quantidade mínima de convidados que uma festa deve ter para que sempre, inexoravelmente, exista um certo número de pessoas que se conheçam mutuamente ou que esse mesmo número de pessoas não se conheçam mutuamente? Não é necessário obedecer às duas condições, apenas uma delas basta. Esse misterioso número de convidados é representado genericamente pela letra k, aquela usada no enunciado do teorema de Ramsey, o tal R(k). Nesse exemplo, parte-se do pressuposto de que a relação de conhecimento ou desconhecimento é recíproca: se uma pessoa é amiga da outra, esta, por conseguinte, também é amiga daquela.
Rodrigo Cunha / Revista Pesquisa FAPESP
Enquanto k for um número baixo, o teorema é fácil de se resolver. Se k for 2, a resposta do problema também é 2. Numa festa com um par de participantes, os dois convidados são, forçosamente, amigos ou estranhos. Não há uma terceira possibilidade. Se k for 3, o teorema também pode ser equacionado. A resposta é 6. Dá um pouco mais de trabalho, mas até um leigo consegue entender e demonstrar que, com meia dúzia de participantes, sempre haverá três que se conhecem ou três que não se conhecem. Para k equivalente a 4, são necessárias 18 pessoas.
A partir de k igual a 5, os matemáticos não têm uma resposta fechada para o teorema. Conseguem dizer apenas que, nesse caso, o número mínimo de convidados se situa dentro de um intervalo entre 43 e 48 pessoas. Por isso, conforme aumenta o valor de k, tudo o que os especialistas em combinatória são capazes de afirmar é que a resposta do problema se encontra entre um limite inferior (no exemplo anterior, o número 43) e um superior (o 48).
Existem duas fórmulas para calcular cada limite da resposta parcial do teorema, o inferior e o superior. Ambas, no entanto, ainda estão longe de ser precisas e podem ser otimizadas. Em outras palavras, a equação do limite inferior dá um resultado muito menor e a do superior muito maior do que a desconhecida resposta exata do problema. O quarteto Campos, Morris, Griffiths e Sahasrabudhe criou um algoritmo que melhorou substancialmente a fórmula empregada para calcular o limite superior. Em vez de ser 4 elevado a k (4k), o novo trabalho mostrou que a equação pode ser reduzida a 3,995 elevado a k (3,995k). A mudança parece sutil, mas desde 1935, quando os matemáticos húngaros Paul Erdös (1913-1996) e George Szekeres (1911-2005) chegaram à fórmula 4k, nenhuma reforma significativa havia sido implementada na equação.
“Fizemos uma gambiarra matemática e tivemos sorte”, diz Griffiths, com bom humor, sobre a abordagem usada pelo quarteto para aprimorar a fórmula historicamente empregada para chegar no limite superior do teorema. “Nesse primeiro artigo, que devemos publicar em uma revista científica, não levamos nosso método à exaustão. Acreditamos que ainda é possível reduzir um pouco mais o valor de 3,995 que propusemos na nossa equação.”
A ideia de trabalhar como o teorema de Ramsey ganhou corpo em 2018, quando o canadense Sahasrabudhe, hoje professor na Universidade de Cambridge, estava no fim de seu pós-doutorado no Impa. “Estamos sempre em busca de problemas interessantes e difíceis”, conta Morris, do Impa. “Nossa estratégia habitual é passar alguns dias discutindo um novo problema em frente do quadro-negro, gerando ideias e tentando entender seus principais obstáculos. Depois, decidimos se temos uma abordagem que vale a pena perseguir mais adiante.” A maior parte dos encontros do grupo ocorreu no Rio, durante o verão, quando Sahasrabudhe podia deixar o Reino Unido e se juntar in loco aos colegas. Durante a pandemia, os encontros pessoais foram transferidos para o meio virtual.
Rodrigo Cunha / Revista Pesquisa FAPESP
Apesar de estarem há cinco anos estudando possíveis avanços na resolução do teorema, a contribuição que fez toda a diferença ocorreu apenas em janeiro de 2023, quando mudaram a estratégia para encarar a questão. Achado o caminho mais promissor, chegaram ao resultado em dias e logo escreveram o artigo com a descoberta. “Optamos por um método probabilístico, baseado nos trabalhos de Erdös, que tenta resolver problemas não aleatórios”, diz Campos, que se juntou ao grupo apenas em 2021.
O teorema de Ramsey não tem aplicabilidade na vida cotidiana, mas seu estudo teve, e tem, grande impacto na matemática e em áreas correlatas. Ele é visto como uma das questões centrais da combinatória, com implicações em disciplinas como computação, lógica e física estatística. A chamada teoria dos grafos, um dos componentes centrais da combinatória, está intimamente relacionada ao teorema.
Um grafo é uma representação abstrata de um conjunto de elementos e das relações entre cada subconjunto dessa estrutura formado por dois desses objetos. Os elementos são denominados vértices ou nós. As relações são associadas a arestas, que estabelecem uma conexão entre os pares de objetos. Na analogia social usada para explicar o teorema de Ramsey, o grafo da festa é formado por vértices (cada pessoa é um deles) e arestas (a relação entre cada par de convidados, se se conhecem ou se são completos estranhos). As arestas que ligam dois amigos são pintadas de uma cor, por convenção, geralmente azul. As que combinam dois estranhos costumam ser coloridas de vermelho. Assim é possível diferenciar o tipo ou qualidade da relação.
A ideia de fundo do teorema de Ramsey é mostrar que em qualquer estrutura formada por um conjunto de elementos, mesmo nas maiores e mais aleatórias, sempre há um subconjunto desses elementos, uma estrutura menor, que apresenta certo ordenamento. “Até dentro do caos, há uma parcela de organização”, explica Mota. No fundo, a resposta do problema indica qual é o tamanho mínimo que essa estrutura caótica deve ter para que sempre exista, dentro dela, uma subestrutura com algum tipo de padrão.
Vale a pena retomar mais uma vez o exemplo da festa para não deixar dúvidas sobre esse ponto central. Quantas pessoas, conhecidas ou não, devem constituir o conjunto de convidados da festa – uma estrutura, portanto, caótica – para que sempre exista um número k de indivíduos conhecidos entre si ou um número k de desconhecidos. Em ambos os casos, trata-se de uma subestrutura com ordenamento.
“A importância de estudar o teorema de Ramsey é que não sabemos o quanto de organização pode se ‘esconder’ dentro de uma estrutura, que, sob outros aspectos, parece ser aleatória”, diz Morris. “Essa é uma questão central no estudo dos objetos finitos grandes. A esperança é que, ao estudar o teorema de Ramsey, seremos levados a desenvolver ferramentas que possam ser aplicadas em muitos outros contextos.”
Um prodígio de Cambridge Matemático britânico formulou teorema com 26 anos, pouco antes de morrer
J. M. Keynes Papers Archive / Wikimedia CommonsFrank Plumpton RamseyJ. M. Keynes Papers Archive / Wikimedia Commons
O teorema de Ramsey é possivelmente a contribuição científica mais conhecida do britânico Frank Plumpton Ramsey (1903-1930), considerado um gênio por seus pares. Seus trabalhos se inserem nas áreas de matemática, filosofia e economia. Nascido em Cambridge, filho de uma sufragista e de um professor de matemática do Magdalene College, uma das faculdades da prestigiosa universidade local, iniciou seus estudos superiores aos 17 anos. Entrou em 1920 no Trinity College, outra faculdade de Cambridge, e se formou em 1923 como o melhor aluno de sua turma em matemática.
Fluente em alemão, ainda no segundo ano da faculdade, iniciou a tradução para o inglês do livro Tractatus logico-philosophicus, do filósofo austríaco Ludwig Wittgenstein (1889-1951), um dos membros do chamado Círculo de Viena. Esse grupo era formado por filósofos, matemáticos e pensadores que se reuniam regularmente na capital austríaca nos anos 1920 para discutir a linguagem e a metodologia científica. Ramsey esteve em Viena em 1923 e, no ano seguinte, passou ali seis meses, tendo se encontrado com Wittgenstein e outros membros do círculo.
As ideias que embasam seu teorema (e a teoria dos grafos) foram publicadas em 1930, ano em que o matemático morreu, pouco antes de completar 27 anos. Ramsey veio a óbito de causa misteriosa, após uma cirurgia de emergência, talvez em razão de possíveis problemas renais, icterícia ou leptospirose.
É permitida a republicação desta reportagem em meios digitais de acordo com a licença Creative Commons CC-BY-NC-ND. É obrigatório o cumprimento da Política de Republicação Digital de Conteúdo de Pesquisa FAPESP, aqui especificada. Em resumo, o texto não deve ser editado e a autoria deve ser atribuída, assim como a fonte (Pesquisa FAPESP). O uso do botão HTML permite o atendimento a essas normas. Em caso de reprodução apenas do texto, por favor, consulte a Política de Republicação Digital.
