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

Resumen Técnico: Sobre subcódigos de Reed-Muller, particiones de Grassmann y funciones sin suma

Enunciado del Problema
El artículo aborda tres problemas interconectados en la teoría de códigos y la geometría finita:

1. Subcódigos de Reed-Muller: La construcción de subcódigos lineales de los códigos de Reed-Muller $RM(r, n)$ que eviten todos los vectores de código de peso mínimo, logrando así una distancia mínima estrictamente mayor que la del código padre.
2. Existencia de Funciones Sin Suma: La determinación de las condiciones de existencia y los límites necesarios para funciones sin suma de orden $k$, $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$. Una función es sin suma de orden $k$ si la suma de sus valores sobre cualquier subespacio afín de dimensión $k$ es distinta de cero. Aunque Carlet introdujo recientemente este concepto y proporcionó una familia infinita de tales funciones (donde $m=n$), la existencia de tales funciones para $m < n$ y para órdenes específicos $k \ge 3$ sigue siendo en gran medida un problema abierto.
3. Particionamiento de Grassmann: El problema de particionar el conjunto de todos los subespacios lineales de dimensión $k$ de $\mathbb{F}_2^n$ (la Grassmanniana) en códigos de subespacios de dimensión constante. Esto es equivalente a determinar el número cromático $\chi(J_2(n, k))$ del grafo de Grassmann, donde los vértices son subespacios de dimensión $k$ y las aristas conectan espacios que se intersecan en dimensión $k-1$.

Metodología
Los autores establecen una correspondencia rigurosa entre la teoría de códigos y las propiedades de las funciones sin suma.

• Construcción de la Correspondencia: El artículo demuestra que una función sin suma de orden $(n-r)$ no degenerada $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ es equivalente a la existencia de un subcódigo lineal de $RM(r, n)$ con codimensión $m$ y distancia mínima $3 \cdot 2^{n-r-1}$. Esto se logra construyendo una matriz de verificación de paridad para el subcódigo utilizando los vectores de evaluación de la función $F$.
• Análisis Algebraico: Los autores utilizan el grado algebraico de las funciones booleanas, las propiedades de las derivadas de orden superior y la estructura de los códigos de Reed-Muller (específicamente la caracterización de los vectores de código de peso mínimo y segundo mínimo mediante planos y sus diferencias simétricas) para derivar condiciones necesarias para la existencia de funciones sin suma.
• Coloración de Grafos mediante Funciones: El artículo utiliza la "función testigo" $\omega_F(A) = \sum_{x \in A} F(x)$ para definir coloraciones en grafos de Grassmann. Al asegurar que los vértices adyacentes (subespacios que se intersecan en dimensión $k-1$) se mapeen a valores distintos y no nulos, los autores construyen coloraciones válidas.
• Verificación Computacional: Para dimensiones pequeñas ($n=5, 6, 7$), los autores realizan búsquedas computacionales para verificar la existencia de funciones sin suma multiorden (funciones que son sin suma para múltiples órdenes $k$) entre las funciones conocidas Cuasi Perfectamente No Lineales (APN).

Contribuciones y Resultados Clave

1. Teorema de Equivalencia (Teorema 1.1):
   El artículo establece una correspondencia biyectiva: Existe una función $(n, m)$ sin suma de orden $(n-r)$ no degenerada si y solo si existe un subcódigo lineal de codimensión $m$ de $RM(r, n)$ con distancia mínima $3 \cdot 2^{n-r-1}$.

   • Significado: Esto genera una nueva familia de subcódigos de Reed-Muller que evitan todos los vectores de código de peso mínimo de $RM(r, n)$. Estos subcódigos tienen una distancia mínima 1.5 veces mayor que la del código original, con una codimensión de solo $n$. Para el rango $2 < r < n-2$, estos códigos parecen ser nuevos.

2. Nuevos Límites Inferiores sobre $m$ (Teorema 3.5):
   Los autores derivan el primer límite inferior no trivial sobre la dimensión de salida $m$ para la existencia de funciones sin suma de orden $k$. Para $2 \le k \le n-2$, si una función $(n, m)$ es sin suma de orden $k$, entonces:
   $$m \ge \max\{n - k + 2, k + 2\}$$
   Este resultado implica que para $m < n$, tales funciones no pueden existir para ciertos rangos de $k$, refinando el conocimiento previo que se limitaba al caso $m=n$.

3. No Degeneración de Familias Conocidas (Teorema 3.6):
   El artículo demuestra que la familia infinita de funciones potencia $F_{k,j}(x) = x^{(2^{jk}-1)/(2^j-1)}$ introducida por Carlet es no degenerada para $k < n$. Esto confirma que estas funciones requieren genuinamente la dimensión completa del espacio de salida $n$ y no pueden reducirse a funciones de dimensión inferior manteniendo la propiedad sin suma.

4. Mejoras en las Coloraciones del Grafo de Grassmann (Teorema 5.1):
   Los autores generalizan resultados previos de coloración. Demuestran que si existe una función $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ de grado algebraico $k$ que es simultáneamente sin suma de orden $(k-1)$ y de orden $k$, entonces el grafo de Grassmann $J_2(n+1, k)$ admite una coloración válida con $\binom{m}{1}_2 = 2^m - 1$ colores.

   • Aplicación: Utilizando la función inversa en dimensiones impares (que es sin suma de orden $\{1, 2, n-2, n-1\}$), los autores derivan una coloración para $J_2(n+1, n-1)$.
   • Resultado Específico: Para $n=5$, la existencia de funciones cúbicas sin suma de orden $\{2, 3\}$ ($x^7$ y $x^{21}$) conduce a la cota $\chi(J_2(6, 3)) \le 31$, mejorando las cotas superiores conocidas previamente.

5. Hallazgos Computacionales sobre Funciones Multiorden:
   El artículo reporta que para $n=6$, ninguna función APN conocida es sin suma de tercer o cuarto orden. Para $n=7$, solo se encontró que las funciones equivalentes a las funciones APN de Gold ($x^{15}, x^{77}, x^{85}$) son sin suma de cuarto orden. Esto sugiere que las funciones sin suma multiorden son raras y difíciles de construir.

Significado y Afirmaciones
El artículo afirma ser el primero en establecer un vínculo directo entre las funciones sin suma de orden $k$ y la construcción de subcódigos de Reed-Muller con distancias mínimas mejoradas. Esta conexión proporciona una nueva herramienta algebraica para generar subcódigos que evitan los vectores de código de peso mínimo.

Además, el trabajo proporciona las primeras condiciones necesarias no triviales para la existencia de funciones sin suma con $m < n$, abordando una pregunta abierta específica planteada por Carlet. Al vincular estas funciones con el número cromático de los grafos de Grassmann, el artículo ofrece un método para mejorar las cotas superiores de $\chi(J_2(n, k))$, particularmente para los casos donde $k > 2$.

Los autores mantienen una postura modesta respecto a la construcción de nuevas funciones sin suma, señalando que construir ejemplos genuinamente nuevos más allá de las funciones potencia conocidas sigue siendo difícil. Enmarcan la existencia de funciones sin suma multiorden para $k \ge 3$ como un problema abierto significativo con implicaciones tanto para la teoría de códigos (códigos no lineales) como para la teoría de grafos.