🤖 AI

Improved lower bounds for the Shannon capacity of odd cycles

Este artigo apresenta limites inferiores melhorados para a capacidade de Shannon dos ciclos ímpares $C_7$ , $C_{11}$ , $C_{13}$ e $C_{15}$ através da construção de conjuntos independentes maiores em seus produtos fortes por meio de colaboração iterativa com um Modelo de Linguagem de Grande Escala.

Autores originais: Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman

Publicado 2026-07-31

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você esteja tentando enviar uma mensagem secreta através de um canal de walkie-talkie com ruído. Cada vez que você fala, a estática pode embaralhar suas palavras, transformando um "sim" em um "não". No mundo da teoria da informação, os cientistas fazem uma pergunta muito específica: Qual é a velocidade máxima com que podemos enviar mensagens para que o receptor as entenda perfeitamente, com zero erros, não importa quanta estática haja no ar? Esse limite é chamado de capacidade de Shannon.

Para descobrir isso, matemáticos usam uma ferramenta chamada "grafo", que é apenas uma palavra chique para um mapa de pontos conectados por linhas. Pense nos pontos como diferentes mensagens que você pode enviar, e as linhas como as semelhanças confusas entre elas. Se dois pontos estão conectados, significa que essas duas mensagens podem se misturar devido ao ruído. O objetivo é escolher um grupo de pontos (mensagens) que não estejam conectados entre si, para que todos sejam distintos e seguros contra confusões. Quanto maior esse grupo, mais informação você pode enviar.

A parte complicada é que podemos combinar esses mapas para criar mapas ainda maiores e mais complexos. Ao empilhar esses mapas, podemos às vezes encontrar grupos enormes de mensagens seguras que não conseguiríamos ver antes. Para certas formas, como anéis de números pares, sabemos a resposta perfeitamente. Mas para anéis de números ímpares (como uma forma de 7 ou 11 lados), a resposta tem sido um mistério persistente por décadas. É como tentar encontrar o maior número de pontos que não se tocam em uma pulseira torcida e com nós, e ninguém conseguiu encontrar a melhor disposição absoluta ainda.

Este artigo trata de uma equipe de pesquisadores que decidiu enfrentar esses anéis ímpares persistentes usando um novo tipo de ajudante: um Grande Modelo de Linguagem (LLM), que é o mesmo tipo de IA que alimenta chatbots inteligentes. Em vez de apenas escrever código para buscar a resposta, eles trataram a IA como uma parceira criativa. Eles pediram à IA que olhasse para as melhores disposições conhecidas de mensagens seguras para esses anéis ímpares e depois tentasse ajustar essas disposições apenas um pouquinho para torná-las ainda maiores.

Os resultados foram surpreendentemente bem-sucedidos. A equipe, trabalhando com a IA, descobriu novos e maiores grupos de mensagens seguras para anéis com 7, 11, 13 e 15 lados. Para o anel de 7 lados, eles encontraram um grupo de 134.753 mensagens seguras, o que é maior que o recorde anterior de 367. Para o anel de 11 lados, encontraram 21.909 mensagens seguras. Para o de 13 lados, encontraram 62.530, e para o de 15 lados, um massivo 8.076.974.

Esses números podem parecer apenas uma lista de dígitos, mas eles representam uma melhoria real em nossa compreensão de quanta informação pode ser enviada sem erros. Ao encontrar esses grupos maiores, os pesquisadores provaram que o limite de velocidade para o envio de mensagens perfeitas através desses canais ruidosos específicos é ligeiramente maior do que pensávamos antes. Por exemplo, para o anel de 7 lados, a velocidade limite agora é conhecida por ser maior que 3,258020, enquanto antes era conhecida apenas por ser maior que 3,257865.

O que torna esta história particularmente emocionante não são apenas os números, mas como eles foram encontrados. Os pesquisadores tentaram usar métodos tradicionais de busca computacional, como o recozimento simulado (simulated annealing — que é como sacudir uma caixa de peças de quebra-cabeça até que elas se encaixem), mas esses métodos falharam em encontrar esses novos e maiores grupos. Até algoritmos de busca local construídos com IA não conseguiram alcançar novas alturas. Foi apenas através de uma conversa de ida e volta com a IA, onde os pesquisadores davam dicas e a IA sugeria modificações criativas aos padrões existentes, que esses novos recordes foram quebrados.

O artigo não afirma ter resolvido todo o mistério da capacidade de Shannon para todos os anéis ímpares; esse problema permanece em aberto. No entanto, ele mostra que, ao combinar a intuição matemática humana com o poder de reconhecimento de padrões da IA moderna, podemos expandir os limites do que sabemos. Os pesquisadores verificaram cada um de seus novos grupos de mensagens para garantir que fossem matematicamente corretos, provando que a IA não apenas adivinhou, mas realmente encontrou soluções válidas e maiores que especialistas humanos haviam perdido. Isso sugere que o futuro da resolução de quebra-cabeças matemáticos complexos pode envolver uma equipe de humanos e IA trabalhando juntos, com a IA atuando como uma centelha criativa que nos ajuda a ver o próximo passo na dança dos números.

Resumo Técnico: Limites Inferiores Melhorados para a Capacidade de Shannon de Ciclos Ímpares

Enunciado do Problema
A capacidade de Shannon $\Theta(G)$ de um grafo $G$ quantifica a taxa máxima de comunicação sem erro em um canal ruidoso definido por $G$ . Ela é definida como $\Theta(G) = \sup_{d \in \mathbb{N}} \alpha(G^d)^{1/d}$ , onde $\alpha(G^d)$ é o número de independência do $d$ -ésimo produto forte de $G$ . Enquanto $\Theta(C_p) = p/2$ para ciclos pares e $\Theta(C_5) = \sqrt{5}$ , os valores para ciclos ímpares $C_{2r+1}$ com $r > 2$ permanecem desconhecidos. Determinar $\Theta(C_7)$ é um problema aberto notoriamente difícil. A abordagem padrão para estabelecer limites inferiores envolve a construção de grandes conjuntos independentes em produtos fortes $C_k^d$ para maximizar a quantidade $\alpha(C_k^d)^{1/d}$ .

Metodologia
Os autores empregam uma interação iterativa com um Modelo de Linguagem Grande (LLM), especificamente o ChatGPT-5.6 Sol Pro, para descobrir construções combinatórias explícitas de conjuntos independentes. A metodologia difere das buscas heurísticas tradicionais (como o simulated annealing ou algoritmos de busca local), que os autores observam terem falhado em atingir os limites relatados, apesar de extensas tentativas.

O processo envolveu:

Prompting: Os autores forneceram ao LLM parâmetros específicos: o comprimento do ciclo ( $k$ ), a dimensão do produto ( $d$ ), a melhor construção existente conhecida e uma cardinalidade alvo para melhoria.
Geração e Execução: O modelo gerou programas de busca, executou-os em seu ambiente e retornou candidatos a conjuntos independentes.
Refinamento Iterativo: Os autores realizaram prompts de acompanhamento para elevar a cardinalidade além dos resultados iniciais encontrados pelo modelo.
Verificação: Todos os conjuntos construídos foram rigorosamente verificados pelos autores para garantir que constituem conjuntos independentes válidos (ou seja, nenhum par de vetores difere por no máximo 1 em cada coordenada módulo $k$ ).

Contribuições Principais e Resultados
O artigo apresenta limites inferiores melhorados para a capacidade de Shannon de quatro ciclos ímpares específicos, construindo maiores conjuntos independentes em seus produtos fortes:

$C_7$ (Ciclo de 7): Os autores construíram um conjunto independente de tamanho 134.753 no 10º produto forte $C_7^{10}$ . Isso melhora o limite anterior de $367^{1/5}$ (proveniente de um conjunto independente de tamanho 367 em $C_7^5$ ).
- Novo Limite Inferior: $\Theta(C_7) \geq 134753^{1/10} > 3.258020$ (anteriormente $> 3.257865$ ).
- Estratégia de Construção: O conjunto foi derivado da modificação do conjunto conhecido de tamanho 367 $R$ de Polak e Schrijver. Os autores deletaram vetores específicos de $R$ para formar um subconjunto $B$ , e então construíram o conjunto final $I$ usando o produto cartesiano $B \times B$ aumentado com vetores adicionais derivados de $R$ e transformações específicas.
$C_{11}$ (Ciclo de 11): Um conjunto independente de tamanho 21.909 foi encontrado em $C_{11}^6$ .
- Novo Limite Inferior: $\Theta(C_{11}) \geq 21909^{1/6} > 5.289773$ (anteriormente $148^{1/3} > 5.289572$ ).
- Estratégia de Construção: Partindo do conjunto de tamanho 148 em $C_{11}^3$ , os autores definiram subconjuntos específicos ($DL, DR, BL, BR$) e conjuntos de vetores auxiliares ( $F_A, F_B, \dots$ ) para construir o conjunto no 6º produto.
$C_{13}$ (Ciclo de 13): Um conjunto independente de tamanho 62.530 foi encontrado em $C_{13}^6$ .
- Novo Limite Inferior: $\Theta(C_{13}) \geq 62530^{1/6} > 6.300109$ (anteriormente $247^{1/3} > 6.274305$ ).
- Estratégia de Construção: O LLM implementou uma busca local aleatória em um grafo auxiliar $G_A$ (com 134 vértices) para encontrar um grande conjunto independente $S$ de 370 vetores em $\mathbb{Z}_{13}^4$ . O conjunto final $I$ foi definido como $\{x \in \mathbb{Z}_{13}^6 : Ax \in S\}$ .
$C_{15}$ (Ciclo de 15): Um conjunto independente de tamanho 8.076.974 foi encontrado em $C_{15}^8$ .
- Novo Limite Inferior: $\Theta(C_{15}) \geq 8076974^{1/8} > 7.301399$ (anteriormente $2842^{1/4} > 7.301397$ ).
- Estratégia de Construção: Partindo do conjunto de tamanho 2842 em $C_{15}^4$ , os autores deletaram vetores específicos e adicionaram outros para formar um conjunto base $R$ . O conjunto final foi formado por $B \times B$ (onde $B \subset R$ ) aumentado com vetores determinados por tabelas de consulta ( $W_0, W_1$ ) baseadas em condições de adjacência.

Adicionalmente, o artigo reporta limites inferiores melhorados para os números de independência de vários produtos fortes individuais que não melhoram diretamente os limites da capacidade de Shannon (por exemplo, $\alpha(C_{11}^4) \geq 766$ , $\alpha(C_{15}^3) \geq 383$ ).

Significância e Alegações
O artigo alega que estes resultados representam melhorias modestas nos limites inferiores conhecidos para $\Theta(C_7)$ , $\Theta(C_{11})$ e $\Theta(C_{15})$ , e uma melhoria mais significativa para $\Theta(C_{13})$ .

A principal significância do trabalho reside na metodologia:

Eficácia do LLM: As construções foram descobertas através da interação iterativa com um LLM, que produziu conjuntos independentes que as heurísticas de busca manual (incluindo simulated annealing e algoritmos de busca local construídos por IA) não conseguiram encontrar, apesar de meses de esforço.
Papel do Conhecimento: Os autores sugerem que o sucesso do LLM pode advir de sua capacidade de alavancar o conhecimento matemático existente e modificar conjuntos independentes conhecidos usando mudanças "pequenas", destacando o potencial dos LLMs para encontrar construções combinatórias explícitas.
Direção Futura: O artigo propõe que estudar os mecanismos que permitem aos LLMs superar as heurísticas de busca tradicionais na descoberta de conjuntos independentes é uma valiosa direção de pesquisa futura.

Os autores mantêm-se modestos quanto à magnitude das melhorias numéricas (por exemplo, o aumento em $\Theta(C_{15})$ é na sexta casa decimal), mas enfatizam a novidade do processo de descoberta. Todas as construções e códigos são disponibilizados em um repositório público.

Mais como este