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

Résumé technique : Sous-codes de Reed-Muller, partitions de Grassmann et fonctions sans somme

Énoncé du problème
L'article traite de trois problèmes interconnectés en théorie des codes et en géométrie finie :

1. Sous-codes de Reed-Muller : La construction de sous-codes linéaires des codes de Reed-Muller $RM(r, n)$ qui évitent tous les mots de code de poids minimal, atteignant ainsi une distance minimale strictement supérieure à celle du code parent.
2. Existence de fonctions sans somme : La détermination des conditions d'existence et des bornes nécessaires pour les fonctions sans somme d'ordre $k$, notées $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$. Une fonction est sans somme d'ordre $k$ si la somme de ses valeurs sur tout sous-espace affine de dimension $k$ est non nulle. Bien que Carlet ait récemment introduit ce concept et fourni une famille infinie de telles fonctions (où $m=n$), l'existence de telles fonctions pour $m < n$ et pour des ordres spécifiques $k \ge 3$ reste largement ouverte.
3. Partitionnement de Grassmann : Le problème de partitionner l'ensemble de tous les sous-espaces linéaires de dimension $k$ de $\mathbb{F}_2^n$ (la grassmannienne) en codes de sous-espaces de dimension constante. Cela équivaut à déterminer le nombre chromatique $\chi(J_2(n, k))$ du graphe de Grassmann, où les sommets sont les $k$-espaces et les arêtes relient les espaces s'intersectant en dimension $k-1$.

Méthodologie
Les auteurs établissent une correspondance rigoureuse entre la théorie des codes et les propriétés des fonctions sans somme.

• Construction de la correspondance : L'article démontre qu'une fonction sans somme d'ordre $(n-r)$ non dégénérée $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ est équivalente à l'existence d'un sous-code linéaire de $RM(r, n)$ de codimension $m$ et de distance minimale $3 \cdot 2^{n-r-1}$. Cela est réalisé en construisant une matrice de contrôle de parité pour le sous-code à l'aide des vecteurs d'évaluation de la fonction $F$.
• Analyse algébrique : Les auteurs utilisent le degré algébrique des fonctions booléennes, les propriétés des dérivées d'ordre supérieur et la structure des codes de Reed-Muller (spécifiquement la caractérisation des mots de code de poids minimal et de second poids minimal via les plans et leurs différences symétriques) pour dériver des conditions nécessaires à l'existence de fonctions sans somme.
• Coloration de graphes via fonctions : L'article utilise la « fonction témoin » $\omega_F(A) = \sum_{x \in A} F(x)$ pour définir des colorations sur les graphes de Grassmann. En s'assurant que les sommets adjacents (sous-espaces s'intersectant en dimension $k-1$) sont mappés vers des valeurs non nulles distinctes, les auteurs construisent des colorations valides.
• Vérification computationnelle : Pour de petites dimensions ($n=5, 6, 7$), les auteurs effectuent des recherches computationnelles pour vérifier l'existence de fonctions sans somme multi-ordre (fonctions sans somme pour plusieurs ordres $k$) parmi les fonctions non linéaires presque parfaites (APN) connues.

Contributions et résultats clés

1. Théorème d'équivalence (Théorème 1.1) :
   L'article établit une correspondance bijective : une fonction $(n, m)$ sans somme d'ordre $(n-r)$ non dégénérée existe si et seulement s'il existe un sous-code linéaire de codimension $m$ de $RM(r, n)$ avec une distance minimale de $3 \cdot 2^{n-r-1}$.

   • Signification : Cela produit une nouvelle famille de sous-codes de Reed-Muller qui évitent tous les mots de code de poids minimal de $RM(r, n)$. Ces sous-codes ont une distance minimale 1,5 fois supérieure à celle du code original, avec une codimension de seulement $n$. Pour la plage $2 < r < n-2$, ces codes semblent nouveaux.

2. Nouvelles bornes inférieures sur $m$ (Théorème 3.5) :
   Les auteurs dérivent la première borne inférieure non triviale sur la dimension de sortie $m$ pour l'existence de fonctions sans somme d'ordre $k$. Pour $2 \le k \le n-2$, si une fonction $(n, m)$ est sans somme d'ordre $k$, alors :
   $$m \ge \max\{n - k + 2, k + 2\}$$
   Ce résultat implique que pour $m < n$, de telles fonctions ne peuvent pas exister pour certaines plages de $k$, affinant les connaissances antérieures limitées au cas $m=n$.

3. Non-dégénérescence des familles connues (Théorème 3.6) :
   L'article démontre que la famille infinie de fonctions puissances $F_{k,j}(x) = x^{(2^{jk}-1)/(2^j-1)}$ introduite par Carlet est non dégénérée pour $k < n$. Cela confirme que ces fonctions nécessitent véritablement la dimension complète de l'espace de sortie $n$ et ne peuvent pas être réduites à des fonctions de dimension inférieure tout en conservant la propriété sans somme.

4. Colorations améliorées des graphes de Grassmann (Théorème 5.1) :
   Les auteurs généralisent les résultats antérieurs de coloration. Ils montrent que s'il existe une fonction $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ de degré algébrique $k$ qui est à la fois sans somme d'ordre $(k-1)$ et d'ordre $k$, alors le graphe de Grassmann $J_2(n+1, k)$ admet une coloration valide avec $\binom{m}{1}_2 = 2^m - 1$ couleurs.

   • Application : En utilisant la fonction inverse dans les dimensions impaires (qui est sans somme d'ordre $\{1, 2, n-2, n-1\}$), les auteurs dérivent une coloration pour $J_2(n+1, n-1)$.
   • Résultat spécifique : Pour $n=5$, l'existence de fonctions cubiques sans somme d'ordre $\{2, 3\}$ ($x^7$ et $x^{21}$) conduit à la borne $\chi(J_2(6, 3)) \le 31$, améliorant les bornes supérieures précédemment connues.

5. Résultats computationnels sur les fonctions multi-ordre :
   L'article rapporte que pour $n=6$, aucune fonction APN connue n'est sans somme d'ordre trois ou quatre. Pour $n=7$, seules des fonctions équivalentes aux fonctions APN de Gold ($x^{15}, x^{77}, x^{85}$) ont été trouvées comme étant sans somme d'ordre quatre. Cela suggère que les fonctions sans somme multi-ordre sont rares et difficiles à construire.

Signification et affirmations
L'article revendique être le premier à établir un lien direct entre les fonctions sans somme d'ordre $k$ et la construction de sous-codes de Reed-Muller avec des distances minimales améliorées. Cette connexion fournit un nouvel outil algébrique pour générer des sous-codes évitant les mots de code de poids minimal.

De plus, le travail fournit les premières conditions nécessaires non triviales pour l'existence de fonctions sans somme avec $m < n$, répondant à une question ouverte spécifique posée par Carlet. En reliant ces fonctions au nombre chromatique des graphes de Grassmann, l'article offre une méthode pour améliorer les bornes supérieures sur $\chi(J_2(n, k))$, en particulier pour les cas où $k > 2$.

Les auteurs restent modestes concernant la construction de nouvelles fonctions sans somme, notant que construire de nouveaux exemples authentiques au-delà des fonctions puissances connues reste difficile. Ils présentent l'existence de fonctions sans somme multi-ordre pour $k \ge 3$ comme un problème ouvert majeur ayant des implications tant pour la théorie des codes (codes non linéaires) que pour la théorie des graphes.