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

Technische Samenvatting: Over Reed-Muller subcodes, Grassmanniaanse partities en somvrije functies

Probleemstelling
Het artikel behandelt drie onderling verbonden problemen in de coderingstheorie en eindige meetkunde:

1. Reed-Muller Subcodes: De constructie van lineaire subcodes van Reed-Muller codes $RM(r, n)$ die alle codewoorden met minimaal gewicht vermijden, waardoor een minimaal afstand wordt bereikt die strikt groter is dan die van de oudercode.
2. Existentie van Somvrije Functies: Het bepalen van de existentievoorwaarden en noodzakelijke grenzen voor $k$-de orde somvrije functies $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$. Een functie is $k$-de orde somvrij als de som van zijn waarden over elke $k$-dimensionale affiene deelruimte niet-nul is. Hoewel Carlet dit concept recent introduceerde en een oneindige familie van dergelijke functies leverde (waarbij $m=n$), blijft de existentie van dergelijke functies voor $m < n$ en voor specifieke ordes $k \ge 3$ grotendeels open.
3. Grassmanniaanse Partitie: Het probleem van het partitioneren van de verzameling van alle $k$-dimensionale lineaire deelruimten van $\mathbb{F}_2^n$ (de Grassmanniaan) in codes met constante dimensie. Dit is equivalent aan het bepalen van het chromatisch getal $\chi(J_2(n, k))$ van de Grassmann-graaf, waarbij hoekpunten $k$-ruimten zijn en randen ruimten verbinden die snijden in dimensie $k-1$.

Methodologie
De auteurs stellen een rigoureuze correspondentie vast tussen coderingstheorie en de eigenschappen van somvrije functies.

• Constructie van Correspondentie: Het artikel bewijst dat een niet-gedegenereerde $(n-r)$-de orde somvrije functie $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ equivalent is aan het bestaan van een lineaire subcode van $RM(r, n)$ met codimensie $m$ en minimaal gewicht $3 \cdot 2^{n-r-1}$. Dit wordt bereikt door een pariteitscheckmatrix voor de subcode te construeren met behulp van de evaluatievectoren van de functie $F$.
• Algebraïsche Analyse: De auteurs maken gebruik van de algebraïsche graad van Booleaanse functies, de eigenschappen van hogere-orde afgeleiden en de structuur van Reed-Muller codes (specifiek de karakterisering van codewoorden met minimaal en tweede-minimaal gewicht via vlakken en hun symmetrische verschillen) om noodzakelijke voorwaarden voor het bestaan van somvrije functies af te leiden.
• Grafkleuring via Functies: Het artikel maakt gebruik van de "witness-functie" $\omega_F(A) = \sum_{x \in A} F(x)$ om kleuringen op Grassmann-graaf te definiëren. Door ervoor te zorgen dat aangrenzende hoekpunten (deelruimten die snijden in dimensie $k-1$) afbeelden op verschillende niet-nul waarden, construeren de auteurs geldige kleuringen.
• Computational Verificatie: Voor kleine dimensies ($n=5, 6, 7$) voeren de auteurs computationele zoektochten uit om het bestaan van multi-orde somvrije functies (functies die somvrij zijn voor meerdere ordes $k$) te verifiëren onder bekende Bijna Perfect Niet-lineaire (APN) functies.

Belangrijkste Bijdragen en Resultaten

1. Equivalentiestelling (Stelling 1.1):
   Het artikel stelt een bijectieve correspondentie vast: Een niet-gedegenereerde $(n-r)$-de orde somvrije $(n, m)$-functie bestaat dan en slechts dan als er een lineaire subcode van $RM(r, n)$ met codimensie $m$ en minimaal gewicht $3 \cdot 2^{n-r-1}$ bestaat.

   • Betekenis: Dit levert een nieuwe familie van Reed-Muller subcodes op die alle codewoorden met minimaal gewicht van $RM(r, n)$ vermijden. Deze subcodes hebben een minimaal gewicht dat 1,5 keer zo groot is als dat van de originele code, met een codimensie van slechts $n$. Voor het bereik $2 < r < n-2$ lijken deze codes nieuw te zijn.

2. Nieuwe Ondergrenzen voor $m$ (Stelling 3.5):
   De auteurs leiden de eerste niet-triviale ondergrens af voor de uitvoerdimensie $m$ voor het bestaan van $k$-de orde somvrije functies. Voor $2 \le k \le n-2$, als een $(n, m)$-functie $k$-de orde somvrij is, dan geldt:
   $$m \ge \max\{n - k + 2, k + 2\}$$
   Dit resultaat impliceert dat voor $m < n$ dergelijke functies niet kunnen bestaan voor bepaalde bereiken van $k$, waardoor eerdere kennis, die beperkt was tot het geval $m=n$, wordt verfijnd.

3. Niet-gedegenereerdheid van Bekende Families (Stelling 3.6):
   Het artikel bewijst dat de oneindige familie van machtfuncties $F_{k,j}(x) = x^{(2^{jk}-1)/(2^j-1)}$, geïntroduceerd door Carlet, niet-gedegenereerd is voor $k < n$. Dit bevestigt dat deze functies werkelijk de volledige uitvoerruimtedimensie $n$ vereisen en niet kunnen worden gereduceerd tot lagere-dimensionale functies terwijl het somvrije eigenschap behouden blijft.

4. Verbeterde Grassmann-graaf Kleuringen (Stelling 5.1):
   De auteurs generaliseren eerdere kleuringresultaten. Zij tonen aan dat als er een functie $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ bestaat met algebraïsche graad $k$ die zowel $(k-1)$-de als $k$-de orde somvrij is, dan de Grassmann-graaf $J_2(n+1, k)$ een geldige kleuring toelaat met $\binom{m}{1}_2 = 2^m - 1$ kleuren.

   • Toepassing: Met behulp van de inverse functie in oneven dimensies (die $\{1, 2, n-2, n-1\}$-orde somvrij is), leiden de auteurs een kleuring af voor $J_2(n+1, n-1)$.
   • Specifiek Resultaat: Voor $n=5$ leidt het bestaan van kubische $\{2, 3\}$-orde somvrije functies ($x^7$ en $x^{21}$) tot de grens $\chi(J_2(6, 3)) \le 31$, wat een verbetering is op eerdere bekende bovengrenzen.

5. Computationele Bevindingen over Multi-orde Functies:
   Het artikel rapporteert dat voor $n=6$ geen bekende APN-functies derde- of vierde-orde somvrij zijn. Voor $n=7$ werden alleen functies die equivalent zijn aan Gold APN-functies ($x^{15}, x^{77}, x^{85}$) gevonden die vierde-orde somvrij zijn. Dit suggereert dat multi-orde somvrije functies zeldzaam zijn en moeilijk te construeren.

Betekenis en Beweringen
Het artikel beweert de eerste te zijn die een directe link legt tussen $k$-de orde somvrije functies en de constructie van Reed-Muller subcodes met verhoogde minimale afstanden. Deze connectie biedt een nieuw algebraïsch hulpmiddel voor het genereren van subcodes die codewoorden met minimaal gewicht vermijden.

Bovendien biedt het werk de eerste niet-triviale noodzakelijke voorwaarden voor het bestaan van somvrije functies met $m < n$, waarmee een specifieke open vraag van Carlet wordt aangepakt. Door deze functies te koppelen aan het chromatisch getal van Grassmann-graaf, biedt het artikel een methode om bovengrenzen voor $\chi(J_2(n, k))$ te verbeteren, met name voor gevallen waar $k > 2$.

De auteurs blijven bescheiden wat betreft de constructie van nieuwe somvrije functies, en merken op dat het construeren van echt nieuwe voorbeelden buiten de bekende machtfuncties om moeilijk blijft. Zij presenteren het bestaan van multi-orde somvrije functies voor $k \ge 3$ als een significant open probleem met implicaties voor zowel coderingstheorie (niet-lineaire codes) als grafentheorie.