537 NÚMEROS, SEIS CORES, NENHUMA SOMA

Eis um quebra-cabeça que uma criança consegue entender. Pegue os números 1, 2, 3 e assim por diante. Dê uma cor a cada um. A única regra: dentro de uma mesma cor, nunca se podem encontrar dois números junto com sua soma. Os dois números podem até ser o mesmo, então, se o 2 for vermelho, o 4 não pode ser vermelho, porque 2 + 2 = 4.

Um conjunto sem nenhum trio desse tipo é chamado de livre de somas. Até onde se pode ir antes que a regra obrigue a parar? Esse limite, para k cores, é o número de Schur S(k). O problema remonta a um artigo de 1916 de I. Schur, o primeiro item da lista de referências.

Uma sequência famosa pela teimosia

Com uma cor, você trava imediatamente: 1 + 1 = 2, então a cor só pode conter o número 1. Os valores conhecidos são:

• S(1) = 1
• S(2) = 4
• S(3) = 13
• S(4) = 44
• S(5) = 160, determinado por M. J. H. Heule (num artigo publicado em 2018).

Para seis cores, ninguém sabe a resposta. Desde 2000, a melhor construção conhecida, encontrada por H. Fredricksen e M. M. Sweet por meio de uma busca entre colorações simétricas, chegava a 536. Esse número vem sendo citado desde então como o melhor limite inferior — um piso: S(6) é pelo menos desse tamanho, e seu valor verdadeiro, ainda desconhecido, pode ser maior.

Um número a mais

Zhiyang Chen e Fan Long, da Universidade de Toronto, e Ligeng Zhu, da NVIDIA Research, levam-no agora a 537. A prova deles é do tipo que os matemáticos adoram pela franqueza: eles imprimem a resposta. Seis listas de números — com 76, 76, 88, 70, 76 e 151 números — que juntas contêm cada inteiro de 1 a 537 exatamente uma vez, sem que nenhuma cor contenha x, y e x + y. Verificá-la significa testar cada soma dentro de cada lista, um trabalho rápido para um computador.

A solução tem uma forma marcante. Ela é simétrica: cada número x tem a mesma cor que 538 − x. As quatro primeiras cores começam em 1, 2, 3 e 4; a quinta só aparece a partir de 38, a sexta só a partir de 151, e a sexta cor preenche todo o trecho central de 237 a 301. Até a primeira cor pode ser reconstruída a partir de uma semente de apenas 14 números pequenos, por meio de uma reflexão espelhada, um deslocamento e um número a mais.

Ondas que sobem

Os números de Schur se alimentam uns aos outros. Receitas conhecidas transformam uma boa coloração com k cores numa com k + 2 ou k + 5 cores: S(k + 2) é pelo menos 10 S(k) + 2, e S(k + 5) pelo menos 380 S(k) + 148. Assim, o novo 537 eleva outros recordes:

• oito cores: de 5.362 para 5.372 — e a equipe também construiu explicitamente essa coloração;
• onze cores: de 203.828 para 204.208;
• treze cores: de 2.038.282 para 2.042.082.

Ele também melhora um número de Ramsey, R₆(3): o menor número de pontos, todos ligados dois a dois, para o qual qualquer coloração das ligações com seis cores contém obrigatoriamente um triângulo de uma só cor. Numere 538 pontos de 0 a 537 e pinte a ligação entre i e j com a cor de sua diferença |i − j|: a coloração livre de somas não deixa nenhum triângulo de uma só cor. Assim, R₆(3) é pelo menos 539, contra 538 antes.

131 maneiras de fazer

A busca não encontrou uma solução, mas 131 genuinamente diferentes, que os autores classificam em cinco famílias e publicam por inteiro. A maioria fica muito próxima da primeira: as das famílias F1 a F4 coincidem com ela em pelo menos 462 das 537 posições. Uma família quebra a simetria de espelho; outra é construída misturando três cópias embaralhadas da original.

O artigo não explica como a busca em si foi feita. Os autores ressaltam que suas 131 colorações não são um catálogo completo das soluções com seis cores, apenas novos pontos de partida para quem quiser tentar chegar a 538.