$2$-quasi-perfect Lee codes and abelian Ramanujan graphs: a new construction and relationship

1. Problema e Contexto

O artigo aborda um problema fundamental na teoria de códigos: a construção de códigos de Lee quase-perfeitos (quasi-perfect Lee codes).

• Códigos de Lee: São códigos corretores de erros definidos sob a métrica de Lee (distância de Lee), relevante para canais de comunicação com ruído de fase ou em sistemas de modulação.
• O Desafio: Encontrar códigos "perfeitos" (que preenchem o espaço de forma ideal) é um problema clássico, mas a conjectura de Golomb-Welch sugere que códigos perfeitos para certos parâmetros não existem. Portanto, o foco deslocou-se para códigos quase-perfeitos ($t$-quase-perfeitos), que são $t$-corretivos e $(t+1)$-cobrantes.
• A Lacuna: A construção de famílias infinitas explícitas de códigos quase-perfeitos de comprimento arbitrariamente grande é um problema aberto e desafiador. Até o momento, as construções conhecidas (como as de Camarero-Martínez e Mesnager-Tang-Qi) parecem ser famílias isoladas derivadas de polinômios específicos, sem uma estrutura unificada clara que explique por que certas estruturas algébricas geram tais códigos. Além disso, a relação entre esses códigos e os grafos Ramanujan abelianos (grafos ótimos em termos de lacuna espectral) não havia sido totalmente formalizada.

2. Metodologia

O autor emprega uma abordagem interdisciplinar que combina:

• Teoria de Códigos e Álgebra Linear: Utiliza a construção genérica de códigos de Lee baseada em subespaços vetoriais e conjuntos geradores.
• Geometria Algébrica: Utiliza o estudo de curvas algébricas (especificamente curvas cúbicas e curvas de gênero um) sobre corpos finitos para provar a existência de soluções para equações polinomiais necessárias às propriedades do código.
• Teoria Espectral de Grafos: Analisa a conexão entre as propriedades de cobertura dos códigos e o diâmetro/raio espectral de grafos de Cayley abelianos, especificamente grafos Ramanujan.
• Teoria dos Números: Utiliza estimativas de somas de Weil e limites de Hasse-Weil para contar pontos em curvas sobre corpos finitos.

A metodologia central envolve definir um código linear $C(\Gamma, H)$ onde $\Gamma$ é um espaço vetorial e $H$ é um conjunto gerador. Para que o código seja 2-quase-perfeito, o conjunto $H$ deve satisfazer condições rigorosas sobre as somas de Minkowski $H^{(i)}$ (conjuntos de pontos a distância $i$ da origem), garantindo que o diâmetro do grafo de Cayley associado seja pequeno (especificamente 3) e que certas contagens de pontos sejam exatas.

3. Contribuições Principais

A. Nova Construção Explícita (Teorema 4)

O autor apresenta uma nova família infinita explícita de códigos de Lee $p$-ários 2-quase-perfeitos.

• Parâmetros: Comprimento $n = \frac{q-1}{2}$ e dimensão $k = \frac{q-1}{2} - 2k$ (onde $q = p^k \ge 14$ e $p \ge 5$ é primo).
• Construção: O código é derivado do conjunto gerador $H_q = \{(a, a^3) \mid a \in \mathbb{F}_q^*\}$, que corresponde aos pontos na curva cúbica $y = x^3$ sobre o corpo finito $\mathbb{F}_q$.
• Diferenciação: Esta construção é distinta das anteriores. Enquanto as construções de Mesnager-Tang-Qi utilizam curvas relacionadas a formas quadráticas (círculos ou hipérboles), esta utiliza uma curva cúbica. O autor demonstra que, para certos primos ($p \equiv 1, 7 \pmod{12}$), esta construção fornece códigos com parâmetros que não eram cobertos pelas famílias anteriores.

B. Ponte Teórica com Grafos Ramanujan

O artigo estabelece uma ligação unificada entre códigos de Lee quase-perfeitos e grafos Ramanujan abelianos bem estudados:

1. Conexão com Grafos de Li: Mostra que a construção de Mesnager-Tang-Qi (baseada em normas de corpos quadráticos) corresponde exatamente aos Grafos de Li (Cayley sobre $\mathbb{F}_{q^2}$ com geradores de norma 1).
2. Conexão com Grafos Euclidianos Finitos: Demonstra que todas as construções de Mesnager-Tang-Qi podem ser unificadas sob o conceito de Grafos Euclidianos Finitos (Cayley definidos por formas quadráticas não degeneradas).
3. Novo Grafo: A nova construção do autor (baseada em $y=x^3$) gera um grafo de Cayley que é um grafo Ramanujan "quase" (almost Ramanujan), descoberto recentemente por Forey et al., mas que não é isomorfo aos grafos associados aos códigos conhecidos anteriormente.

4. Resultados Técnicos Chave

• Prova de 2-Quase-Perfeição: O autor prova que o código $C(\mathbb{F}_q^2, H_q)$ satisfaz as condições do Lema 2 (de Mesnager et al.):

  1. O número de pontos na soma $H_q^{(2)}$ atinge exatamente o limite necessário para a correção de erros.
  2. A soma $H_q^{(3)}$ cobre todo o espaço vetorial $\mathbb{F}_q^2$.
  3. As condições de cardinalidade estritas são satisfeitas para $q \ge 14$.
  • A prova utiliza o Limite de Hasse-Weil para garantir que a curva cúbica $F_{a,b}(x,y)=0$ possui pontos suficientes fora de certas retas proibidas, garantindo a cobertura do espaço.

• Unificação de Famílias: O artigo prova (Proposição 18) que qualquer código de Lee 2-quase-perfeito derivado de uma forma quadrática não degenerada é equivalente (via permutações e mudanças de sinal) a um dos códigos de Mesnager-Tang-Qi. Isso classifica completamente a família baseada em formas quadráticas.

• Exemplos Numéricos: O autor fornece matrizes de verificação de paridade para pequenos primos ($p=17, 19, 23, 5^2$), demonstrando explicitamente que as matrizes geradas por sua nova construção são diferentes das geradas pela construção de Mesnager-Tang-Qi, mesmo quando os parâmetros de comprimento e dimensão coincidem.

5. Significado e Conclusão

• Avanço na Existência: O trabalho resolve parcialmente o problema de construir códigos quase-perfeitos de comprimento arbitrariamente grande, oferecendo uma nova família baseada em curvas cúbicas.
• Estrutura Unificada: A maior contribuição teórica é a unificação. O autor demonstra que a existência de códigos quase-perfeitos está intrinsecamente ligada à existência de grafos de Cayley abelianos com diâmetro pequeno e propriedades espectrais de Ramanujan.
• Dicotomia Espectral vs. Estrutural: O autor observa uma dicotomia fascinante: os grafos subjacentes são "pseudo-aleatórios" no sentido espectral (distribuição de autovalores convergindo para a distribuição semicircular, típica de grafos aleatórios), mas possuem uma estrutura local extremamente rígida e determinística (necessária para a propriedade de quase-perfeição). Isso sugere que a indistinguibilidade espectral não impede a existência de estruturas locais altamente ordenadas.
• Futuro: O trabalho abre caminho para investigar se outros grafos Ramanujan abelianos podem gerar novas famílias de códigos, sugerindo que a teoria de códigos de Lee e a teoria espectral de grafos estão profundamente entrelaçadas.

Em resumo, o artigo não apenas fornece uma nova construção de códigos, mas também oferece o arcabouço teórico necessário para entender por que certas estruturas algébricas (curvas cúbicas, formas quadráticas) produzem códigos ótimos, conectando-os à teoria de grafos Ramanujan.