MatemáticaPré-publicaçãoTeoria4 min de leitura

A PROVA DE UMA IA, REDESENHADA PARA HUMANOS

Desenhe alguns pontos e ligue alguns deles com linhas. Os matemáticos chamam isso de grafo; os pontos são vértices, as linhas são arestas, e o número de linhas que tocam um ponto é o seu grau. Uma árvore é um grafo sem ciclos que se mantém inteiro numa só peça, como um galho ramificado; uma árvore com t pontos tem sempre t − 1 linhas.

No início dos anos 1960, Paul Erdős e Vera T. Sós fizeram uma pergunta simples: quantas linhas obrigam um grafo a conter todas as árvores de um dado tamanho? A resposta deles, a conjectura de Erdős–Sós, é a seguinte:

Se um grafo tem grau médio maior que t − 2, ele contém todas as árvores com t vértices.

O limiar é exato. Pegue cópias separadas de um grafo completo com t − 1 pontos, em que cada par está ligado: cada ponto tem exatamente t − 2 vizinhos, mas nenhuma peça é grande o bastante para conter uma árvore de t pontos. A dificuldade está na palavra média. Se cada ponto tivesse pelo menos t − 1 vizinhos, seria possível encaixar uma árvore ramo por ramo sem problema. Mas uma média não diz nada sobre nenhum ponto individual: alguns podem ter centenas de vizinhos, outros quase nenhum.

Sessenta anos de respostas parciais

Segundo o histórico relatado no artigo, o problema data de 1962–1964 e tornou-se central no ramo da matemática que estuda quantas arestas obrigam o aparecimento de um dado padrão. Casos particulares foram caindo: estrelas, caminhos, estrelas duplas, árvores com poucos ramos. No início dos anos 1990, quatro matemáticos — Ajtai, Komlós, Simonovits e Szemerédi — anunciaram uma prova para árvores muito grandes, mas artigos recentes observam que nenhum manuscrito completo foi jamais publicado. Outros resultados parciais chegaram em 2021, 2024 e 2026. Em 4 de setembro de 2026, Reed e Stein publicaram uma prova para grafos grandes e densos, que afirmam ter sido desenvolvida sem IA.

Depois veio um relatório. Em setembro de 2026, Tom Adamczewski e Thomas Bloom, num documento chamado FrontierMath Erdős, atribuíram uma prova da conjectura completa a uma versão pré-lançamento de um modelo de IA, o GPT-6 Astra. O argumento de contagem original é público, e um repositório que o acompanha registra a busca autônoma da IA pela prova e uma verificação formal na linguagem de verificação de provas Lean. Os autores do relatório também convocaram especialistas humanos a escrever relatos mais completos e tradicionais.

Revelar um grafo um ponto de cada vez

Jay Cummings, da California State University, Sacramento, responde a esse apelo. Seu artigo de 27 páginas mantém o argumento de contagem central da IA, mas muda a forma de contá-lo:

  1. Revelar o grafo aos poucos. Liste os vértices em alguma ordem e descubra-os um a um, junto com as arestas entre os que já foram mostrados.
  2. Pedir mais. Em vez de qualquer cópia da árvore, procure uma cuja “raiz” escolhida fique exatamente no primeiro vértice. Pedir mais torna a prova mais fácil.
  3. Contar os vizinhos precoces. São os vizinhos do primeiro vértice que aparecem antes de surgir uma tal cópia. Some-os sobre todas as ordens possíveis.
  4. Limitar o total. Trocando vértices ou blocos inteiros da ordem — movimentos que sempre podem ser desfeitos —, Cummings mostra que, em média sobre todas as ordens, há no máximo t − 2 vizinhos precoces.

O passo final é curto. Se o grafo não contivesse nenhuma cópia da árvore, todo vizinho do primeiro vértice seria precoce, em todas as ordens. Em média sobre todas as ordens, isso é exatamente o grau médio — que, por hipótese, ultrapassa t − 2. Contradição: a árvore tem de estar lá.

A prova usa apenas o total dos graus, não a forma como estão distribuídos. Cummings dá também uma versão probabilística e trabalha exemplos com árvores de quatro e cinco vértices em grafos concretos.

Uma prova em livro ilustrado

O artigo contém 32 figuras. Termina com uma consequência clássica: pinte todas as linhas de um grafo completo com q cores, e uma das cores conterá sempre uma dada árvore assim que o grafo tiver q(t − 2) + 2 vértices. Numa declaração final, Cummings explica que desenvolveu o texto num longo diálogo com o ChatGPT, que as novas ideias de apresentação — os vizinhos precoces, as partições explícitas, os desenhos — são dele, e que verificou tudo e assume total responsabilidade.

Ele compara o seu relato com outros recentes, de Riordan e Scott, de Wood e de Frederickson, e observa que o método já foi estendido a redes com direções e a “hipergrafos”, sendo algumas dessas extensões também atribuídas ao GPT-6 Astra. A contribuição dele, escreve, é “uma exposição visual do argumento centrada no leitor, não uma nova resolução da conjectura”.