CAI A CONJECTURA DO GIRASSOL

Pegue nos números de 1 a n e olhe para todas as maneiras de escolher alguns deles: há 2ⁿ desses subconjuntos. Agora escolha alguns subconjuntos que partilhem exatamente a mesma parte comum, e nada mais. Os matemáticos chamam a isto um girassol (sunflower): a parte partilhada é o núcleo, e o que resta de cada conjunto é uma pétala que não toca em nenhuma outra pétala.

Os girassóis são uma ferramenta básica da combinatória. O artigo enumera ligações aos limites de certos circuitos lógicos, ao problema dos “cap sets”, à multiplicação rápida de matrizes e à teoria da informação.

Uma pergunta de 1970

A pergunta mais natural sobre eles remonta, segundo os autores, a um artigo de Paul Erdős de 1970. Que tamanho pode ter uma coleção de subconjuntos de {1, …, n} se nenhuns k dos seus conjuntos formarem um girassol?

Nos anos 1970, Erdős e Endre Szemerédi conjeturaram que tal coleção tem de ser exponencialmente menor do que os 2ⁿ subconjuntos possíveis: no máximo cⁿ, para algum número c estritamente abaixo de 2.

Durante décadas, os melhores limites só tiravam um pouco, nunca o suficiente para baixar a base abaixo de 2. Só o caso de três pétalas (k = 3) foi resolvido, em 2016, graças ao avanço no problema dos cap sets e a uma redução devida a Alon, Shpilka e Umans.

O limite

Matija Bucić e Fankang He (Universidade de Viena) e Hyunwoo Lee (KAIST e Institute for Basic Science, Coreia do Sul) demonstram a conjetura para todo k ≥ 3. O seu teorema principal: uma coleção sem girassol de k pétalas tem no máximo

3 · (2 − 1/(16k³))ⁿ

elementos. A base fica mesmo abaixo de 2, mas é um número fixo abaixo de 2, e é exatamente isso que Erdős e Szemerédi pediam. Uma construção de 1997 mostra que, para k grande, o valor verdadeiro não pode ser muito mais baixo.

Dos conjuntos aos vetores

A demonstração passa por uma versão do problema com vetores. Divida os números em n blocos de D elementos e escolha um elemento por bloco: cada escolha é um vetor. Vários vetores formam um girassol quando, em cada posição, as suas entradas são todas iguais ou todas diferentes.

Os autores constroem então um “testador de girassóis”: uma função que, numa coleção sem girassóis, só é não nula quando todas as suas entradas são o mesmo vetor. O ingrediente novo é escrever esta função, passo a passo, com polinómios de interpolação de grau baixo. Contar esses polinómios limita o tamanho da coleção (o seu Teorema 2). Um argumento probabilístico, blocos aleatórios com média sobre todos os tamanhos de conjunto, leva o limite de volta aos conjuntos comuns.

Encontrado por uma máquina, verificado por outra

A declaração do artigo sobre a IA é invulgarmente direta. A demonstração do Teorema 2 foi encontrada pelo ChatGPT 6 Astra Pro, após uma breve discussão que começou por lhe pedir para generalizar o argumento conhecido para três pétalas. Os autores precisavam desse passo para outro objetivo: uma versão induzida de um problema de grafos colocado por Szemerédi, que anunciam para uma nota posterior.

O modelo escreveu a sua demonstração na linguagem do “slice rank”. Os autores reescreveram-na na linguagem do método polinomial, que consideram mais acessível para os leitores. Afirmam ter verificado todos os resultados e assumem total responsabilidade, e que a demonstração foi verificada em Lean 4.35, um software de verificação de demonstrações, devendo a verificação ser publicada no repositório Palomar.

O que fica por resolver

Os autores não tentaram otimizar a base. Para três pétalas, ela não bate o limite de 2017 de Naslund e Sawin, cerca de 1,89. E o problema irmão mais forte, a conjetura do girassol de Erdős–Rado, continua em aberto: os seus limites ainda dependem fortemente do tamanho de bloco D, que é precisamente o que esse problema proíbe.