Um modelo da OpenAI refutou uma conjectura central da geometria discreta

Por quase 80 anos, matemáticos estudaram uma questão enganosamente simples: se você coloca $n$ pontos no plano, quantos pares de pontos podem estar exatamente à distância $1$ um do outro?

Este é o problema das distâncias unitárias no plano, proposto pela primeira vez por Paul Erdős em 1946. É uma das questões mais conhecidas da geometria combinatória, fácil de enunciar e notavelmente difícil de resolver. O livro de 2005 Research Problems in Discrete Geometry, de Brass, Moser e Pach, o descreve como “possivelmente o problema mais conhecido (e mais simples de explicar) da geometria combinatória”. Noga Alon, importante combinatorialista de Princeton, descreve o problema como “um dos problemas favoritos de Erdős”. Erdős chegou até a oferecer um prêmio em dinheiro para quem resolvesse esse problema.

Hoje, compartilhamos um avanço no problema da distância unitária. Desde o trabalho original de Erdős, a crença predominante era a de que as construções de “grade quadrada” mostradas mais abaixo eram essencialmente ótimas para maximizar o número de pares a distância unitária. Um modelo interno da OpenAI refutou essa conjectura de longa data, fornecendo uma família infinita de exemplos que produz uma melhoria polinomial. A prova foi verificada por um grupo de matemáticos externos. Eles também escreveram um artigo complementar explicando o argumento e fornecendo mais contexto e informações de base sobre a importância do resultado.

O resultado também é notável pela forma como foi encontrado. A prova veio de um novo modelo de raciocínio de propósito geral, e não de um sistema treinado especificamente para matemática, estruturado para buscar estratégias de prova ou voltado especificamente para o problema da distância unitária. Como parte de um esforço mais amplo para testar se modelos avançados podem contribuir para pesquisa de fronteira, nós o avaliamos em uma coleção de problemas de Erdős. Neste caso, ele produziu uma prova que resolve o problema em aberto.

Essa prova é um marco importante para as comunidades de matemática e IA. Ela marca a primeira vez em que um problema em aberto de destaque, central para um subcampo da matemática, foi resolvido autonomamente por IA. Ela também demonstra a profundidade de raciocínio que esses sistemas agora oferecem. A matemática oferece um campo de teste particularmente claro para o raciocínio: os problemas são precisos, provas potenciais podem ser verificadas, e um argumento longo só funciona se o raciocínio se sustentar do começo ao fim. O método pelo qual o problema foi resolvido também é notável. A prova mobiliza ideias inesperadas e sofisticadas da teoria algébrica dos números para tratar de uma questão geométrica elementar.

O medalhista Fields Tim Gowers, escrevendo no artigo complementar, chama o resultado de “um marco na matemática com IA”. Segundo o importante teórico dos números Arul Shankar, “Na minha opinião, este artigo demonstra que os modelos atuais de IA vão além de meros auxiliares de matemáticos humanos – eles são capazes de ter ideias originais e engenhosas, e então levá-las à concretização”.

A prova está disponível aqui⁠(abre em uma nova janela). O artigo complementar de importantes matemáticos externos está disponível aqui⁠(abre em uma nova janela). Você pode encontrar uma versão resumida da cadeia de pensamento do modelo aqui⁠(abre em uma nova janela).

Seja $u(n)$ o maior número possível de pares a distância unitária entre $n$ pontos no plano. Exemplos que atingem taxa de crescimento linear são fáceis de construir: colocar $n$ pontos em uma linha gera $n-1$ pares, enquanto uma grade quadrada gera cerca de $2n$ pares. A melhor construção conhecida anteriormente, vinda de uma grade quadrada reescalonada, na verdade produz ainda mais: $n^{1 + C / \log \log(n)}$ para uma constante $C$. Como $\log \log(n)$ tende ao infinito com $n$, o termo adicional no expoente tende a $0$, o que significa que essas construções atingem crescimento apenas ligeiramente mais rápido que linear. Durante décadas, acreditou-se amplamente que essa taxa era essencialmente a melhor possível e que nenhuma construção poderia melhorar significativamente a grade quadrada. Em termos técnicos, Erdős conjecturou uma cota superior de $n^{1+o(1)}$, em que o $o(1)$ adicional indica um termo que tende a $0$ com $n$.

Nosso novo resultado refuta essa conjectura. Mais precisamente, para infinitos valores de $n$, a prova constrói configurações de $n$ pontos com pelo menos $n^{1+\delta}$ pares a distância unitária, para algum expoente fixo $\delta > 0$. (A prova original da IA não fornece um $\delta$ explícito, mas um refinamento futuro do professor de matemática de Princeton Will Sawin mostrou que é possível tomar $\delta=0.014$.)

A história do problema ajuda a entender por que o resultado é surpreendente. A melhor cota inferior conhecida permanecia essencialmente inalterada desde a construção original de Erdős, de 1946. A melhor cota superior, $O(n^{4/3})$, remonta ao trabalho de Spencer, Szemerédi e Trotter em 1984 e, apesar de refinamentos posteriores e trabalhos estruturais relacionados de Székely, Katz e Silier, Pach, Raz e Solymosi, entre outros, a cota superior permaneceu essencialmente inalterada. Como evidência a favor da conjectura, Matoušek e Alon-Bucić-Sauermann estudaram o problema com distâncias não euclidianas no plano e provaram que a “maioria” dessas distâncias não euclidianas obedece à conjectura em certo sentido.

Surpreendentemente, os principais ingredientes da construção vêm de uma parte muito diferente da matemática, conhecida como teoria algébrica dos números, que estuda conceitos como fatoração em extensões dos inteiros conhecidas como corpos de números algébricos.

Em alto nível, a prova começa com uma ideia geométrica familiar e a leva em uma direção inesperada.

O limite inferior original de Erdős pode ser entendido por meio dos inteiros gaussianos: números da forma $a+bi$, em que $a$ e $b$ são inteiros e $i$ é a raiz quadrada de $-1$. Os inteiros gaussianos estendem os inteiros ordinários e, como eles, desfrutam de propriedades como a fatoração única em primos. Tais extensões dos inteiros ordinários ou dos racionais são conhecidas como corpos algébricos de números. O novo argumento substitui os inteiros gaussianos por generalizações mais complicadas da teoria algébrica dos números, com simetrias mais ricas que podem criar muito mais diferenças de comprimento unitário.

O argumento preciso usa ferramentas como torres infinitas de corpos de classes e a teoria de Golod–Shafarevich para mostrar que os corpos numéricos exigidos pelo argumento de fato existem. Essas ideias eram bem conhecidas pelos teóricos algébricos dos números, mas foi uma grande surpresa que esses conceitos tenham implicações para questões geométricas no plano euclidiano.

Este resultado marca um momento importante na interação entre IA e matemática: um sistema de IA resolveu autonomamente um problema em aberto de longa data no centro de um campo ativo. Ele também oferece um vislumbre inicial de um novo tipo de colaboração entre IA e matemáticos humanos. Neste caso, o trabalho complementar de matemáticos externos traça um quadro substancialmente mais rico do que a solução original sozinha.

Como Thomas Bloom escreve na nota complementar:

“Ao avaliar a importância e a influência de uma prova gerada por IA, uma pergunta que faço a mim mesmo é: isso nos ensinou algo novo sobre o problema? Entendemos melhor a geometria discreta agora? Acho que a resposta é um sim moderado: isso mostra que construções da teoria dos números têm muito mais a dizer sobre esse tipo de questão do que suspeitávamos; além disso, que a teoria dos números necessária pode ser muito profunda. Sem dúvida, muitos teóricos algébricos dos números examinarão de perto outros problemas em aberto da geometria discreta nos próximos meses.”

A conexão inesperada entre teoria algébrica dos números e geometria discreta revelada pela solução é parte do que torna o resultado notável. Ela não apenas resolve uma conjectura específica, mas pode fornecer aos matemáticos uma ponte para começar a explorar outros problemas relacionados.

Bloom também aponta para uma possibilidade mais ampla:

“As fronteiras do conhecimento são muito irregulares, e sem dúvida os próximos meses e anos verão sucessos semelhantes em muitas outras áreas da matemática, em que problemas em aberto de longa data são resolvidos por uma IA ao revelar conexões inesperadas e levar o maquinário técnico existente ao seu limite. A IA está nos ajudando a explorar mais plenamente a catedral da matemática que construímos ao longo dos séculos; que outras maravilhas ainda não vistas estão à espera nos bastidores?”

Este resultado oferece um exemplo promissor: a IA contribuindo não apenas com uma solução, mas com uma descoberta matemática cujo significado se torna mais claro e mais rico por meio da compreensão humana subsequente.

A principal conclusão é maior do que este resultado específico. Um raciocínio matemático melhor pode tornar a IA uma parceira de pesquisa mais forte: algo que consegue sustentar linhas de pensamento difíceis, conectar ideias entre áreas distantes do conhecimento, revelar caminhos promissores que especialistas talvez não tenham priorizado e ajudar pesquisadores a avançar em problemas que, de outra forma, seriam complexos demais ou exigiriam tempo demais para enfrentar.

Essas capacidades importam para além da matemática. Se um modelo consegue manter coerente um argumento complicado, conectar ideias entre áreas distantes do conhecimento e produzir trabalho que resiste ao escrutínio de especialistas, então essas também são habilidades úteis em biologia, física, ciência dos materiais, engenharia e medicina, e fazem parte do nosso caminho de longo prazo rumo a uma pesquisa mais automatizada: sistemas que podem ajudar cientistas e engenheiros a explorar mais ideias e perseguir questões técnicas mais difíceis.

A IA está prestes a começar a assumir um papel muito sério nas partes criativas da pesquisa e, mais importante, da própria pesquisa em IA. Embora esse progresso não seja inesperado, ele reforça a urgência que sentimos em compreender essa próxima fase do desenvolvimento da IA, os desafios de alinhar sistemas muito inteligentes e o futuro da colaboração entre humanos e IA.

Esse futuro ainda depende do julgamento humano. A expertise se torna mais valiosa, não menos. A IA pode ajudar a buscar, sugerir e verificar. As pessoas escolhem os problemas que importam, interpretam os resultados e decidem quais questões perseguir em seguida.