Resumo Técnico: Uma Forma Fraca de Equivalência Comutativa em Códigos Finitos

Autores: Dean Kraizberg
Data: 31 de março de 2026
Áreas: Teoria da Codificação, Teoria de Grafos, Monoides Livres.

1. Problema e Contexto

O artigo investiga a relação estrutural entre códigos prefixos (prefix-free codes) sobre o alfabeto binário $\{a, b\}$ e uma classe específica de árvores enraizadas não rotuladas, denominadas árvores simétricas.

O problema central situa-se no âmbito da Conjectura de Equivalência Comutativa, proposta por Perrin e Schützenberger. A conjectura original afirmava que todo código finito é comutativamente equivalente a um código prefixo. Dois códigos são comutativamente equivalentes se existe uma bijeção entre eles que preserva o número de ocorrências de cada símbolo (neste caso, 'a' e 'b') em cada palavra.

No entanto, Peter Shor refutou essa conjectura geral, apresentando um contraexemplo ($C_{Shor}$) que não é comutativamente equivalente a nenhum código prefixo. Isso levou à restrição da conjectura apenas para códigos maximais.

O objetivo deste trabalho não é provar a equivalência comutativa total (que falha), mas estabelecer uma forma fraca de equivalência estrutural. O autor busca demonstrar que, para qualquer código $C$, existe um código prefixo $C'$ que preserva certas quantidades combinatórias específicas relacionadas às ocorrências do símbolo 'a', mesmo que o número total de palavras (cardinalidade) dos códigos difira.

2. Metodologia e Estrutura Teórica

A abordagem do artigo baseia-se na construção de uma correspondência biunívoca entre códigos prefixos e árvores simétricas, utilizando ferramentas de teoria de grafos e teoria de grupos.

2.1 Definições Fundamentais

• Árvores Simétricas (Definição 1.7): Uma árvore enraizada finita (subárvore da árvore 3-ária completa) é simétrica se, para todo vértice com pelo menos dois filhos, existem dois filhos distintos cujas subárvores enraizadas são idênticas.
• Correspondência Canônica (Teorema 1.8): O autor estabelece uma bijeção entre códigos prefixos e árvores simétricas. Sob esta correspondência, o número de folhas na árvore $T$ na profundidade $k$, denotado por $|L_k(T)|, é igual à soma ponderada das palavras do código$C$ de comprimento $k$:
  $$|L_k(T)| = \sum_{w \in C, |w|=k} 2^{[w]_a}$$
  onde $[w]_a$ é o número de ocorrências do símbolo 'a' na palavra $w$.

2.2 Construção via Grupos Livres

A prova da correspondência utiliza o Grupo Livre $F(a, b)$ e seu Grafo de Cayley.

1. Um código prefixo $C$ é mapeado para uma árvore rotulada $T_b$ no grafo de Cayley.
2. Utiliza-se uma projeção $\pi$ do grafo de Cayley para o monoide livre $\{a, b\}^*$.
3. A estrutura simétrica emerge da restrição da árvore levantada a coordenadas pares, onde a simetria das subárvores é garantida pela presença de pares de extensões inversas (ex: $a$ e $a^{-1}$) no grupo livre, que se projetam no mesmo símbolo 'a' no alfabeto original.

2.3 Prova do Resultado Principal

Para provar o Teorema 1.9, o autor utiliza indução no tamanho do código $|C|$:

1. Assume-se a existência de uma árvore simétrica para um subconjunto do código.
2. Estende-se essa árvore para a profundidade máxima $M$ do código original.
3. Analisa-se o "complemento" da árvore estendida dentro de uma árvore 3-ária completa.
4. Utiliza-se o Lema 2.6 (um lema de soma de potências de 2) para demonstrar que é possível selecionar um subconjunto de folhas do complemento que satisfaça exatamente a soma de potências de 2 requerida pela palavra de maior comprimento que falta no código.
5. Caso a seleção direta não seja possível, o autor emprega um processo de "ajuste" (swap) iterativo: remove-se palavras de certas camadas da árvore e insere-se palavras "faltantes" em outras, preservando a contagem total de folhas ponderada, até que a configuração desejada seja alcançada.

3. Contribuições e Resultados Chave

Teorema 1.8 (Correspondência)

Estabelece a bijeção fundamental entre códigos prefixos e árvores simétricas, preservando não apenas os comprimentos das palavras, mas também a estrutura de contagem baseada nas ocorrências do símbolo 'a' (ponderada por $2^{[w]_a}$).

Teorema 1.9 (Resultado Principal)

Para todo código $C$ (não necessariamente maximal ou prefixo), existe um código prefixo $C'$ tal que, para todo comprimento fixo $k$:
$$\sum_{w \in C, |w|=k} 2^{[w]_a} = \sum_{w' \in C', |w'|=k} 2^{[w']_a}$$
Este resultado é uma "forma fraca" de equivalência comutativa. Diferente da equivalência comutativa forte (que exigiria $|C| = |C'|$ e preservação exata de $[w]_a$ e $[w]_b$ para cada palavra individual), este teorema garante a preservação da soma das potências de dois das ocorrências de 'a' para cada comprimento.

Generalização (Seção 3)

O autor observa que o resultado se estende para alfabetos finitos arbitrários de tamanho $A$. Para um código $C$ sobre um alfabeto de tamanho $A$, existe um código prefixo $C'$ tal que:
$$\sum_{w \in C, |w|=k} A^{k-[w]_a} = \sum_{w' \in C', |w'|=k} A^{k-[w']_a}$$
(Nota: A fórmula exata na generalização envolve uma ponderação similar adaptada ao tamanho do alfabeto).

4. Significado e Implicações

1. Resolução Parcial da Conjectura: O trabalho oferece uma perspectiva nova sobre a Conjectura de Equivalência Comutativa. Embora não prove que todo código é comutativamente equivalente a um prefixo (o que é falso), prova que existe sempre um código prefixo que preserva uma "assinatura" combinatória robusta (a soma das potências de 2 das ocorrências de um símbolo).
2. Conexão Estrutural: A descoberta de que códigos prefixos podem ser mapeados bijectivamente para árvores simétricas fornece uma nova ferramenta para analisar propriedades de códigos através da teoria de árvores e grupos, permitindo o uso de indução estrutural em árvores.
3. Limitações e Cardinalidade: O artigo destaca explicitamente (Remarque 1.10) que o código prefixo $C'$ resultante não precisa ter a mesma cardinalidade que o código original $C$. No contraexemplo de Shor, a cardinalidade deve mudar para satisfazer a condição de soma de potências, o que explica por que a equivalência comutativa forte falha.
4. Questões Abertas: O trabalho levanta a questão de quão próximo em cardinalidade um código pode estar de seu equivalente prefixo fraco, questionando se a diferença $||C| - |C'||$ pode ser limitada por uma constante ou por $O(|C|)$.

Em suma, o artigo avança a teoria de códigos finitos ao substituir a busca por uma equivalência perfeita (que falha) por uma equivalência estrutural baseada em invariantes combinatórios, utilizando uma ponte elegante entre códigos, árvores simétricas e grupos livres.