Por décadas, uma simples pergunta tem assombrado Máté Matolcsi, professor da Universidade de Tecnologia e Economia de Budapeste. Quanto de um plano infinito você pode colorir, certificando-se de que dois pontos coloridos não estejam exatamente separados por uma unidade de distância?

A questão foi colocada pela primeira vez por Leo Moser, um matemático canadense, no início dos anos 1960. Em 1967, Hallard Croft, da Universidade de Cambridge, apresentou uma construção que parecia fazer um bom trabalho. Sua forma, agora chamada de “tartaruga de Croft”, parece um círculo que encontra um cortador de biscoitos em forma de hexágono. Cada ponto dentro de cada tartaruga está a menos de uma unidade de distância de qualquer outro ponto na mesma tartaruga e a mais de uma unidade de distância do ponto mais próximo da tartaruga vizinha.

No meio século desde então, ninguém conseguiu encontrar uma forma que melhorasse os 22.936% do plano que as tartarugas cobrem. Mas poderia existir um, mesmo em teoria? Em 1984, László Székely, um matemático húngaro, provou que é impossível encontrar uma forma que cubra mais de 27.91% do plano. No ano seguinte, Paul Erdős, o conjecturador prolífico (e colega húngaro), disse que achava que o limite superior era inferior a 25%. Tal como acontece com muitos conjecturas de Erdős, atraiu a atenção de numerosos matemáticos ambiciosos ao longo dos anos.

Matolcsi enfocou esse problema em sua tese de doutorado no início dos anos 2000. Ele estava trabalhando na análise de Fourier — somando funções seno extraídas da trigonometria para representar funções mais complicadas — e pensou que essas técnicas poderiam ser usadas para provar a conjectura de Erdős.

"Eu não poderia fazer isso", disse ele. “Chegamos muito perto de 25%, mas não abaixo. Eu estava um pouco desapontado; colocamos muito esforço nisso. Fiz uma defesa de doutorado na Academia Húngara de Ciências e disse ao comitê: 'Olha, nem tenho mais certeza se isso é verdade. Colocamos muito esforço nisso, e esse maldito número não vai abaixo de 25.'”

Levaria quase um quarto de século para ele provar que estava errado.

Outros matemáticos continuaram a desbastar o número. Em 2010, Frank Vallentin, agora na University of Cologne, e Fernando Oliveira, agora na Delft University of Technology, empurraram o limite para menos de 27%. Matolcsi também continuou, e em 2014, com colegas, ele passou 26%. Em 2018, junto com Gergely Ambrus, ele baixou o limite para 25.442% - tentadoramente próximo ao palpite de 25% de Erdős.

Então ele desistiu.

Após o artigo de 2018, Matolcsi lembrou: “Eu disse: 'Nunca mais vou tocar nesse problema. Porque simplesmente não está funcionando. Eu fiz o que pude fazer.”

Acontece que ele não tinha. Matolcsi concordou em tentar resolver o problema uma última vez depois que alguns pesquisadores o abordaram em uma festa de aniversário. Dániel Varga, Adrián Csiszárik e Pál Zsámboki, todos da Academia Húngara de Ciências, pensaram que modelos de aprendizado de máquina como AlphaGo e AlphaFold poderiam ajudar a identificar o complicado conjunto de pontos necessários para resolver o problema.

Desde o resultado de 1984, uma técnica que se mostrou frutífera foi observar a quantidade de sobreposição que um conjunto de pontos candidatos tem com uma cópia deslocada de si mesmo, usando algo chamado função de autocorrelação. Para um determinado deslocamento – digamos, uma unidade para cima e uma unidade para a direita – a função fornece um número que é uma medida do tamanho da sobreposição. Se um conjunto é “evitando a distância da unidade”, então sua função de autocorrelação será zero sempre que for deslocada — em qualquer direção — por uma unidade.

Matolcsi, Ambrus e seus novos colaboradores analisaram a transformada de Fourier da função, que a traduz em uma soma gigante de ondas senoidais. A exigência de que a função seja zero para todos os deslocamentos de comprimento unitário restringe os valores possíveis dos elementos da soma de Fourier. Eles descobriram como expressar esse requisito como um problema de otimização linear – algo que Varga, Csiszárik e Zsámboki estavam bem equipados para lidar.

“Temos que encontrar o conjunto de pontos com um conjunto de propriedades muito delicado, muito raro, e não sabemos como fazer isso. Então pedimos ao computador para procurar esses objetos”, disse Varga.

Esse processo foi mais direto do que eles esperavam. Enquanto Varga e Csiszárik experimentaram modelos de inteligência artificial mais complicados para tentar identificar os pontos – e lutaram mais do que esperavam – Zsámboki usou estratégias de busca mais antigas desenvolvidas na década de 1980.

“Era muito estranho que o material avançado não funcionasse tão bem. Decidi usar métodos mais antigos”, disse Zsámboki, “e isso simplesmente funcionou muito melhor”. (Zsámboki acrescentou que Varga sugeriu o uso de uma técnica específica chamada busca em árvore.)

Depois de definirem os algoritmos a serem usados, eles tinham um grande problema a resolver: 25,552 variáveis ​​com 6,099 restrições. Eles executaram a busca por uma semana em 128 CPUs. No final da semana, eles tiveram seu resultado.

Em outubro de 2022, a equipe postou um papel mostrando que não mais do que 24.7% do plano pode ser colorido sem pares de unidades de distância, finalmente quebrando o limite de Erdős.

“Realmente foi, devo dizer, um momento muito satisfatório”, disse Matolcsi. “É apenas um resultado muito limpo e agradável.”

“Estou muito feliz por eles terem feito isso agora, porque já pensei que ir abaixo de 25% não seria possível com a capacidade atual do computador”, disse Vallentin.

Ainda assim, ninguém apresentou uma coloração mais completa do que as tartarugas Croft de 1967, que cobrem pouco menos de 23% do avião. Mas, em vez de tentar continuar a diminuir o limite superior em direção às tartarugas, vários dos autores agora estão focados em um problema relacionado: descobrir quantas cores são necessárias para cobrir completamente o plano, garantindo que cada cor evite a unidade de distância.

Este número é chamado de número cromático do plano. Em 2018, o matemático amador (e evangelista da longevidade) Aubrey de Gray provou que deve ser pelo menos 5. Sabe-se que é menor ou igual a 7. O novo papel implica, usando métodos diferentes dos de Grey, que pelo menos cinco cores são necessárias. “Podemos provar que é pelo menos 6?” perguntou Ambrus. “Isso é algo que pode ter uma chance. Estamos trabalhando nisso agora e pode ter uma chance com o nosso método.”