QUANTAS CORES PARA PINTAR O ESPAÇO? PARA UMA RÉGUA TÍPICA, NO MÁXIMO 2d

Pegue cada ponto de um plano e dê a cada um uma cor. Uma regra: dois pontos a exatamente uma unidade de distância nunca podem ter a mesma cor. Qual é o menor número de cores que funciona?

Este é o problema de Hadwiger–Nelson, que remonta a 1950 e é, nas palavras dos autores, um dos problemas em aberto mais famosos da geometria discreta. Durante muito tempo, sabia-se que a resposta estava entre 4 e 7. Um avanço recente elevou o limite inferior para 5. A resposta exata continua desconhecida.

Trocando a régua

A distância não precisa ser medida com uma régua comum. Os matemáticos definem muitas outras normas — maneiras de medir comprimentos —, cada uma descrita por sua “bola unitária”, o conjunto dos pontos a uma distância de no máximo 1 do centro. Para a distância usual, é uma bola redonda; para outras normas, pode ser qualquer forma convexa simétrica em relação ao centro.

Para qualquer norma no plano, a resposta ao quebra-cabeça de coloração fica entre 4 e 7. Em d dimensões, ela é no máximo exponencial em d para qualquer norma e, para muitas normas naturais — incluindo a euclidiana usual —, também é no mínimo exponencial: o número de cores explode à medida que a dimensão cresce.

Essa explosão é a regra? Noga Alon (Universidade de Princeton e Universidade de Tel Aviv), Matija Bucić (Universidade de Viena) e James Davies (Universidade de Leipzig) estudaram uma norma típica. Não há maneira natural de escolher uma norma “ao acaso”, então eles usam uma noção topológica: uma propriedade vale para uma norma típica se as exceções formam um conjunto desprezível (“magro”). Um trabalho anterior de Alon, Bucić e Lisa Sauermann havia mostrado que uma norma típica precisa de no máximo 2ᵈ cores, e perguntava quão perto isso estava da verdade.

Linear, não exponencial

A resposta: bem longe. O novo artigo prova que

• para uma norma típica no espaço de dimensão d, 2d cores sempre bastam;
• isso é o melhor possível: um conjunto aberto de normas exige pelo menos 2d cores. Logo, algumas normas precisam de exatamente 2d.

Em dez dimensões, uma norma típica precisa de no máximo vinte cores, enquanto a distância usual precisa de um número que cresce exponencialmente. Segundo os autores, é também a primeira vez que o número de coloração é determinado exatamente para uma norma “estritamente convexa” em qualquer dimensão d.

O limite inferior usa uma armadilha engenhosa. Encontre 2d pontos que estejam todos a exatamente uma unidade uns dos outros, exceto dois, a e b, que estão a meia unidade. Acrescente a imagem espelhada de toda a configuração em relação a a. Com menos de 2d cores, tanto b quanto sua imagem espelhada seriam forçados a ter a cor de a — mas eles estão a exatamente uma unidade de distância. Contradição. Um lema de estabilidade mostra que essa configuração sobrevive a qualquer pequena alteração da norma.

Um corredor solitário em altas dimensões

O limite superior colore cada ponto conforme o lugar onde cai uma projeção bem escolhida dele, em fatias de largura 1/(2d). Fazê-lo funcionar exige um ingrediente-chave que os autores descrevem como uma versão matricial, em altas dimensões, da famosa conjectura do corredor solitário (lonely runner conjecture):

sup over x of minᵢ ‖aᵢ · x − bᵢ‖ ≥ k / (2n)

onde ‖t‖ é a distância de t ao inteiro mais próximo, para quaisquer n vetores aᵢ em k dimensões dos quais quaisquer k são independentes. Esse enunciado também resolve uma conjectura de I. J. Schoenberg de 1978 sobre “obstrução da visão” (view obstruction) — uma questão sobre quão espessas devem ser placas periódicas para bloquear toda vista até o infinito —, que os autores consideram um dos problemas em aberto mais clássicos da área, bem como uma conjectura relacionada de Henze e Malikiosis.

A máquina nos agradecimentos

Os autores são explícitos: “O ChatGPT 6 Pro nos forneceu a prova do último ingrediente de que precisávamos na prova do Teorema 1, a saber, a do Lema 7, após uma discussão prolongada”, na qual eles haviam compartilhado suas próprias observações — incluindo a ideia da indução e a estratégia geral. “O argumento do limite inferior também foi encontrado com a ajuda do ChatGPT 6 Pro.”

Restam questões. O valor exato 2d está provado em um conjunto aberto de normas, não para todas as normas típicas. E, para a distância euclidiana comum, os autores esperam estritamente mais de 2d cores em todas as dimensões — algo já conhecido nas dimensões 2, 4, 7, 8 e de 9 em diante, mas ainda em aberto nas dimensões 3, 5 e 6.