Sharper upper bounds for $q$-ary $B_2$ codes from Toeplitz SDPs

Título: Limites Superiores Mais Afiados para Códigos B2 q-ários a partir de SDPs de Toeplitz

Autor: Stefano Della Fiore (Universidade de Brescia, Itália)

---

1. Problema e Contexto

O artigo aborda o problema de determinar os limites superiores assintóticos da taxa (rate) de códigos B2 q-ários.

• Definição de Código B2: Um código $C_n$ sobre o alfabeto $\{0, \dots, q-1\}$ é um código B2 se todas as somas de pares de codewords (incluindo um codeword consigo mesmo) forem distintas. Formalmente, $c_i + c_j \neq c_k + c_l$ para todos os pares distintos $\{i, j\} \neq \{k, l\}$.
• Importância: Para $q=2$, isso equivale aos códigos 2-separáveis. O objetivo é encontrar o limite superior da taxa $R = \limsup_{n \to \infty} \frac{1}{n} \log_q |C_n|$.
• Estado da Arte: Limites anteriores foram estabelecidos por Lindström, Della Fiore-Dalai e Wang. O método padrão para obter esses limites envolve argumentos de informação teórica, especificamente analisando a entropia da diferença entre duas variáveis aleatórias independentes e identicamente distribuídas (i.i.d.) extraídas do código.

2. Metodologia

O autor refina a etapa crítica do método de "prefixo-sufixo" utilizado em trabalhos anteriores. A inovação central reside na exploração da estrutura analítica de Fourier completa da distribuição de diferença, em vez de usar apenas restrições probabilísticas simples.

A. Abordagem Anterior vs. Nova Abordagem

• Anterior (Trabalho [5]): A restrição utilizada era apenas a probabilidade de colisão: $P(X=Y) \geq 1/q$. Isso levou a um limite de entropia fechado, mas não tão apertado.
• Nova Abordagem: O autor observa que a função de massa de probabilidade (pmf) da diferença $D = X - Y$ é uma autocorrelação de uma pmf no domínio original.
  • Isso implica que a transformada de Fourier da distribuição de diferença, $\psi_D(\theta)$, é o módulo quadrado da transformada de Fourier da distribuição original: $\psi_D(\theta) = |\phi(\theta)|^2$.
  • Consequentemente, $\psi_D(\theta)$ deve ser um polinômio trigonométrico não negativo de grau no máximo $q-1$.

B. Formulação de Otimização Convexa

O problema de maximizar a entropia da diferença $H(X-Y)$ é reformulado como um problema de otimização convexa sobre as distribuições de diferença $r_k$:

• Objetivo: Maximizar $-\sum r_k \log r_k$.
• Restrições:
  1. Normalização e simetria ($r_{-k} = r_k$).
  2. Probabilidade de colisão ($r_0 \geq 1/q$).
  3. Nova Restrição Crucial: O polinômio trigonométrico $R(\theta) = \sum r_k e^{ik\theta}$ deve ser não negativo para todo $\theta \in [0, 2\pi]$.

C. Equivalência com SDPs de Toeplitz

O autor demonstra que a condição de não negatividade do polinômio trigonométrico é equivalente a um conjunto infinito de restrições de matrizes de Toeplitz semidefinidas positivas (PSD).

• Seja $T^{(N)}(r)$ a matriz de Toeplitz construída com os coeficientes $r_k$.
• A condição $R(\theta) \geq 0$ é equivalente a $T^{(N)}(r) \succeq 0$ para todo $N \geq 1$.
• Isso transforma o problema em um Programa Semidefinido (SDP). Na prática, o problema é resolvido numericamente truncando as matrizes para um tamanho máximo $N_{max}$ (ex: 100), fornecendo um limite superior certificado.

3. Principais Contribuições

1. Relaxação Analítica de Fourier: Introdução de uma relaxação para a distribuição de diferença i.i.d. que explora o fato de sua função característica ser um polinômio trigonométrico não negativo.
2. Caracterização via SDP: Estabelecimento explícito da equivalência entre a condição de não negatividade no domínio da frequência e uma família infinita de restrições de matrizes de Toeplitz PSD, conectando o problema a resultados clássicos de análise harmônica.
3. Melhoria do Limite de Entropia: A nova relaxação fornece um limite superior estritamente menor para a entropia $H(X-Y)$ em comparação com métodos anteriores que ignoravam a estrutura de autocorrelação.
4. Novos Limites de Taxa: Aplicação deste limite de entropia refinado ao método prefixo-sufixo para derivar novos limites superiores assintóticos para a taxa de códigos B2 q-ários.

4. Resultados Numéricos

O autor avaliou numericamente o novo limite para valores de $q \in \{9, 10, 11, 12, 13\}$ utilizando SDPs truncados.

• Comparação: Os novos limites ($R_{new}$) superam (são menores que) os melhores limites disponíveis na literatura, incluindo os de Lindström [3], Della Fiore-Dalai [5] e Wang [7].
• Exemplo de Dados (Tabela I do artigo):
  • Para $q=9$: O novo limite é 0.55792, melhorando o anterior de 0.56149 (Della Fiore-Dalai) e 0.57551 (Lindström).
  • Para $q=13$: O novo limite é 0.55206, superando o limite anterior de 0.55545.
• Estabilidade: Os resultados mostram convergência estável à medida que o tamanho da matriz de Toeplitz ($N_{max}$) aumenta.

5. Significado e Perspectivas Futuras

• Significado Teórico: O trabalho demonstra que ignorar a estrutura de autocorrelação (positividade de Toeplitz) em problemas de codificação combinatória leva a limites de entropia frouxos. A incorporação de ferramentas de análise harmônica e otimização convexa (SDP) permite refinar significativamente esses limites.
• Justificativa da Melhoria: A restrição $R(\theta) \geq 0$ elimina distribuições de alta entropia que satisfazem a condição de colisão ($r_0 \geq 1/q$) mas que não podem ser geradas por uma autocorrelação de uma distribuição de probabilidade válida.
• Futuro: O autor sugere extensões para:
  • Adicionar mais condições necessárias para autocorrelações (restrições de momento).
  • Adaptar o método para outras famílias de códigos baseadas em argumentos de prefixo-sufixo.
  • Explorar relaxações SDP de Toeplitz para somas de ordem superior (condições do tipo $B_h$).

Em resumo, o artigo apresenta uma melhoria técnica significativa na teoria de códigos combinatórios, utilizando otimização semidefinida para explorar estruturas matemáticas ocultas (Fourier/Toeplitz) que restringem a entropia de diferenças de variáveis aleatórias, resultando em limites de taxa mais rigorosos para códigos B2.