On Reed-Muller subcodes, Grassmannian partitions and sum-free functions

Resumo Técnico: Sobre subcódigos de Reed-Muller, partições de Grassmanniana e funções sem soma

Declaração do Problema
O artigo aborda três problemas interconectados na teoria dos códigos e na geometria finita:

1. Subcódigos de Reed-Muller: A construção de subcódigos lineares de códigos de Reed-Muller $RM(r, n)$ que evitam todos os vetores de código de peso mínimo, alcançando assim uma distância mínima estritamente maior que a do código pai.
2. Existência de Funções Sem Soma: Determinação das condições de existência e limites necessários para funções sem soma de ordem $k$, $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$. Uma função é sem soma de ordem $k$ se a soma de seus valores sobre qualquer subespaço afim de dimensão $k$ for não nula. Embora Carlet tenha introduzido recentemente este conceito e fornecido uma família infinita de tais funções (onde $m=n$), a existência de tais funções para $m < n$ e para ordens específicas $k \ge 3$ permanece amplamente em aberto.
3. Particionamento de Grassmanniana: O problema de particionar o conjunto de todos os subespaços lineares de dimensão $k$ de $\mathbb{F}_2^n$ (a Grassmanniana) em códigos de subespaço de dimensão constante. Isso é equivalente a determinar o número cromático $\chi(J_2(n, k))$ do grafo de Grassmann, onde os vértices são $k$-espaços e as arestas conectam espaços que se intersectam em dimensão $k-1$.

Metodologia
Os autores estabelecem uma correspondência rigorosa entre a teoria dos códigos e as propriedades das funções sem soma.

• Construção da Correspondência: O artigo prova que uma função sem soma de ordem $(n-r)$ não degenerada $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ é equivalente à existência de um subcódigo linear de $RM(r, n)$ com codimensão $m$ e distância mínima $3 \cdot 2^{n-r-1}$. Isso é alcançado construindo uma matriz de verificação de paridade para o subcódigo usando os vetores de avaliação da função $F$.
• Análise Algébrica: Os autores utilizam o grau algébrico de funções booleanas, as propriedades de derivadas de ordem superior e a estrutura dos códigos de Reed-Muller (especificamente a caracterização de vetores de código de peso mínimo e segundo peso mínimo via planos e suas diferenças simétricas) para derivar condições necessárias para a existência de funções sem soma.
• Coloração de Grafos via Funções: O artigo utiliza a "função testemunha" $\omega_F(A) = \sum_{x \in A} F(x)$ para definir colorações em grafos de Grassmann. Ao garantir que vértices adjacentes (subespaços que se intersectam em dimensão $k-1$) mapeiem para valores não nulos distintos, os autores constroem colorações válidas.
• Verificação Computacional: Para pequenas dimensões ($n=5, 6, 7$), os autores realizam buscas computacionais para verificar a existência de funções sem soma multiordem (funções que são sem soma para múltiplas ordens $k$) entre funções Não-Lineares Quase Perfeitas (APN) conhecidas.

Principais Contribuições e Resultados

1. Teorema de Equivalência (Teorema 1.1):
   O artigo estabelece uma correspondência biunívoca: Uma função $(n, m)$ sem soma de ordem $(n-r)$ não degenerada existe se e somente se existir um subcódigo linear de codimensão $m$ de $RM(r, n)$ com distância mínima $3 \cdot 2^{n-r-1}$.

   • Significado: Isso gera uma nova família de subcódigos de Reed-Muller que evitam todos os vetores de código de peso mínimo de $RM(r, n)$. Esses subcódigos têm uma distância mínima 1,5 vezes a do código original, com uma codimensão de apenas $n$. Para o intervalo $2 < r < n-2$, esses códigos parecem ser novos.

2. Novos Limites Inferiores para $m$ (Teorema 3.5):
   Os autores derivam o primeiro limite inferior não trivial para a dimensão de saída $m$ para a existência de funções sem soma de ordem $k$. Para $2 \le k \le n-2$, se uma função $(n, m)$ é sem soma de ordem $k$, então:
   $$m \ge \max\{n - k + 2, k + 2\}$$
   Este resultado implica que, para $m < n$, tais funções não podem existir para certos intervalos de $k$, refinando o conhecimento anterior que se limitava ao caso $m=n$.

3. Não-Degeneração de Famílias Conhecidas (Teorema 3.6):
   O artigo prova que a família infinita de funções potência $F_{k,j}(x) = x^{(2^{jk}-1)/(2^j-1)}$ introduzida por Carlet é não degenerada para $k < n$. Isso confirma que essas funções exigem genuinamente a dimensão completa do espaço de saída $n$ e não podem ser reduzidas a funções de dimensão inferior enquanto mantêm a propriedade sem soma.

4. Colorações de Grafos de Grassmann Melhoradas (Teorema 5.1):
   Os autores generalizam resultados anteriores de coloração. Eles mostram que, se existir uma função $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ de grau algébrico $k$ que seja simultaneamente sem soma de ordem $(k-1)$ e de ordem $k$, então o grafo de Grassmann $J_2(n+1, k)$ admite uma coloração válida com $\binom{m}{1}_2 = 2^m - 1$ cores.

   • Aplicação: Usando a função inversa em dimensões ímpares (que é sem soma de ordem $\{1, 2, n-2, n-1\}$), os autores derivam uma coloração para $J_2(n+1, n-1)$.
   • Resultado Específico: Para $n=5$, a existência de funções sem soma de ordem cúbica $\{2, 3\}$ ($x^7$ e $x^{21}$) leva ao limite $\chi(J_2(6, 3)) \le 31$, melhorando os limites superiores conhecidos anteriormente.

5. Descobertas Computacionais sobre Funções Multiordem:
   O artigo relata que, para $n=6$, nenhuma função APN conhecida é sem soma de terceira ou quarta ordem. Para $n=7$, apenas funções equivalentes às funções APN de Gold ($x^{15}, x^{77}, x^{85}$) foram encontradas como sendo sem soma de quarta ordem. Isso sugere que funções sem soma multiordem são raras e difíceis de construir.

Significado e Alegações
O artigo afirma ser o primeiro a estabelecer uma ligação direta entre funções sem soma de ordem $k$ e a construção de subcódigos de Reed-Muller com distâncias mínimas aprimoradas. Essa conexão fornece uma nova ferramenta algébrica para gerar subcódigos que evitam vetores de código de peso mínimo.

Além disso, o trabalho fornece as primeiras condições necessárias não triviais para a existência de funções sem soma com $m < n$, abordando uma questão aberta específica levantada por Carlet. Ao vincular essas funções ao número cromático de grafos de Grassmann, o artigo oferece um método para melhorar os limites superiores de $\chi(J_2(n, k))$, particularmente para casos onde $k > 2$.

Os autores permanecem modestos quanto à construção de novas funções sem soma, observando que a construção de exemplos genuinamente novos além das funções potência conhecidas permanece difícil. Eles enquadram a existência de funções sem soma multiordem para $k \ge 3$ como um problema aberto significativo com implicações tanto para a teoria dos códigos (códigos não lineares) quanto para a teoria dos grafos.