New lower bounds for constant-weight codes via seeded bit-swap tabu search

Imagine que você está tentando arrumar uma mala para uma viagem, mas com uma regra muito estranha: cada item que você embalar deve ter exatamente o mesmo tamanho, e nenhum item pode ser muito parecido com outro. Se forem muito parecidos, eles podem se misturar no escuro, causando o caos. No mundo da comunicação digital, esta "mala" é uma mensagem, os "itens" são padrões de zeros e uns (bits), e o "tamanho" é quantos uns existem no padrão. Este é o enigma dos códigos de peso constante. Cientistas usam esses códigos para enviar dados de forma confiável através de canais ruidosos, como Wi-Fi ou rádio de espaço profundo, garantindo que, mesmo que alguns bits sejam embaralhados, o receptor ainda consiga entender o que foi enviado. O objetivo é simples, mas incrivelmente difícil: encaixar o máximo de itens únicos e distintos na mala sem que eles colidam uns com os outros. Quanto maior a mala (mais códigos você consegue encaixar), mais informação podemos enviar de uma só vez.

Entra em cena William Echols, que decidiu enfrentar este problema de empacotamento com um toque inteligente. Em vez de começar com uma mala vazia e jogar itens aleatoriamente, esperando que caibam, ele usou uma abordagem "com semente" (seeded). Pense nisso como se fosse assim: se você quer construir um castelo de Lego melhor, você não começa do zero; você pega um castelo excelente já existente, remove algumas peças e as troca para ver se consegue torná-lo ainda maior ou mais robusto. Echols usou um método de computador chamado busca tabu (tabu search), que é como um explorador muito teimoso que se recusa a retratar seus passos (para evitar ficar preso em loops) e continua tentando novos camos. Ao "semear" este explorador com designs de códigos existentes e de alta qualidade, ele o guiou para encontrar 124 novos arranjos de empacotamento maiores que nunca haviam sido descobertos. Esses novos arranjos melhoram os limites inferiores de quantos códigos podemos enviar e até nos ajudam a entender quantos esferas podem tocar uma esfera central em um espaço de alta dimensão — um conceito conhecido como "números de beijo" (kissing numbers).

O Enigma do Empacotamento e a Semente Mágica

No mundo digital, os dados são apenas uma longa sequência de zeros e uns. Às vezes, para torná-los robustos, permitimos apenas sequências que tenham um número específico de uns. Por exemplo, se dissermos que o "peso" é 5, cada sequência deve ter exatamente cinco uns e o restante zeros. Agora, imagine que você tem uma coleção dessas sequências. Para evitar erros, cada sequência em sua coleção deve ser suficientemente diferente de todas as outras. Se duas sequências forem muito parecidas, um pouco de ruído pode transformá-las uma na outra, e o receptor ficaria confuso. A "distância" entre elas é medida por quantos pontos são diferentes.

A grande questão neste campo é: Qual é o número máximo de sequências que você pode encaixar em sua coleção? Esse número máximo é chamado de $A(n, d, w)$, onde $n$ é o comprimento da sequência, $d$ é a distância mínima necessária e $w$ é o número de uns. Durante décadas, matemáticos e cientistas da computação tentaram encontrar as maiores coleções possíveis para vários cenários. Eles encontraram ótimas coleções, mas muitas vezes não sabem se encontraram a maior de todas. Eles apenas sabem que não conseguem fazer melhor do que um certo número.

A Estratégia "Semeada"

Tentativas anteriores de encontrar esses números máximos usando buscas computacionais muitas vezes pareciam caminhar em uma floresta escura. Os computadores começavam com palpites aleatórios e, embora às vezes encontrassem bons caminhos, frequentemente ficavam presos em clareiras locais que pareciam o topo de uma montanha, mas não eram. Eles paravam ali, pensando que haviam encontrado o melhor código possível, quando um muito maior estava logo após a próxima colina.

Echols percebeu que a chave era parar de começar do zero. Ele usou uma técnica de inicialização semeada (seeded initialization). Em vez de gerar um ponto de partida aleatório, ele pegou um código conhecido e de alta qualidade (uma "semente") e o usou para lançar a busca.

Ele fez isso de duas maneiras lúdicas:

1. Semeadura Direta: Ele pegou um código existente e adicionou uma palavra extra a ele, escolhida cuidadosamente para causar o mínimo de "problemas" (déficits de distância). Isso criou um ponto de partida ligeiramente maior e ligeiramente bagunçado.
2. Semeadura de Vizinhos: Ele olhou para códigos de problemas ligeiramente diferentes. Por exemplo, se ele quisesse um código de comprimento 30, poderia pegar um ótimo código de comprimento 29, adicionar um zero a cada palavra para torná-las de comprimento 30 e, então, usá-lo como ponto de partida. Ou, ele poderia pegar um código de comprimento 31, remover um zero e usá-lo.

Uma vez que ele teve esses pontos de partida "semeados", ele executou sua busca tabu de troca de bits (bit-swap tabu search). Imagine esta busca como um jogo de dança das cadeiras onde as cadeiras são as posições dos uns nas sequências. O algoritmo troca os bits de lugar, tentando tornar as sequências mais distintas. A parte "tabu" significa que o algoritmo mantém uma memória das jogadas que acabou de fazer e se recusa a desfazer imediatamente essas jogadas, forçando-o a explorar novos territórios em vez de girar em círculos.

Os Resultados: 124 Novas Descobertas

Ao usar esta estratégia inteligente de semeadura, Echols encontrou 124 novas construções que superaram os recordes conhecidos anteriormente. Estas não são apenas pequenas melhorias; algumas são saltos massivos.

Por exemplo:

• Para um código de comprimento 39 com restrições específicas, o recorde anterior era de 1.014 palavras. O novo método encontrou 1.118 palavras. Isso é um ganho de 104!
• Para o comprimento 40, o recorde saltou de 1.170 para 1.230.
• Para o comprimento 56, o número passou de 2.414 para 2.477.

Esses números representam o número máximo de mensagens únicas que agora podemos garantir enviar sem confusão para esses cenários específicos. O artigo não afirma que estes são os limites máximos absolutos (o verdadeiro limite matemático), mas prova que certamente podemos fazer melhor do que pensávamos. Ele eleva o "limite inferior", o que significa que sabemos com certeza que podemos encaixar pelo menos este número de itens na mala.

Números de Beijo: Um Efeito Colateral Surpreendente

É aqui que a história fica ainda mais interessante. O artigo também toca em um conceito chamado números de beijo (kissing numbers). Imagine que você tem uma bola gigante no meio de uma sala. Quantas outras bolas do mesmo tamanho você pode empacotar ao redor dela de modo que todas toquem a bola central sem se sobreporem? No espaço 3D, a resposta é 12. Mas em dimensões superiores (como 32 ou 33 dimensões), a resposta é muito mais difícil de encontrar.

A matemática desses números de beijo está profundamente conectada aos códigos de peso constante que Echols encontrou. Como ele melhorou os códigos para parâmetros específicos (especificamente $A(n, 8, 8)$), ele automaticamente melhorou os limites inferiores para os números de beijo nas dimensões 32, 33, 34 e 37.

Por exemplo, para a dimensão 32 ($\tau_{32}$), a estimativa anterior era que pelo menos 345.408 bolas poderiam tocar a bola central. Com os novos códigos, esse número salta para 346.432. É um aumento percentual pequeno, mas no mundo da geometria de alta dimensão, encontrar até mesmo uma bola a mais que caiba é uma vitória significativa.

A Conclusão

William Echols não encontrou apenas alguns códigos melhores; ele mostrou que, ao ser inteligente sobre como iniciar sua busca — usando "sementes" de conhecimentos existentes em vez de começar às cegas — você pode encontrar soluções muito melhores. O artigo prova que 124 melhorias específicas são possíveis e nos dá um novo patamar mais alto para o quanto de dados podemos confiar em empacotar nessas sequências digitais. É um lembrete de que, às vezes, a melhor maneira de seguir em frente é apoiar-se no que já sabemos, em vez de tentar construir tudo do zero.