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

Sintesi Tecnica: Sottocodici di Reed-Muller, partizioni di Grassmann e funzioni senza somma

Enunciato del Problema
Il lavoro affronta tre problemi interconnessi nella teoria dei codici e nella geometria finita:

1. Sottocodici di Reed-Muller: La costruzione di sottocodici lineari dei codici di Reed-Muller $RM(r, n)$ che evitano tutti i codeword di peso minimo, raggiungendo così una distanza minima strettamente maggiore di quella del codice genitore.
2. Esistenza di Funzioni Senza Somma: La determinazione delle condizioni di esistenza e dei limiti necessari per le funzioni senza somma di ordine $k$, $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$. Una funzione è senza somma di ordine $k$ se la somma dei suoi valori su qualsiasi sottospazio affine di dimensione $k$ è non nulla. Sebbene Carlet abbia recentemente introdotto questo concetto e fornito una famiglia infinita di tali funzioni (dove $m=n$), l'esistenza di tali funzioni per $m < n$ e per ordini specifici $k \ge 3$ rimane in gran parte aperta.
3. Partizionamento di Grassmann: Il problema di partizionare l'insieme di tutti i sottospazi lineari di dimensione $k$ di $\mathbb{F}_2^n$ (la Grassmanniana) in codici di sottospazi a dimensione costante. Questo equivale a determinare il numero cromatico $\chi(J_2(n, k))$ del grafo di Grassmann, dove i vertici sono sottospazi di dimensione $k$ e gli archi connettono spazi che si intersecano in dimensione $k-1$.

Metodologia
Gli autori stabiliscono una corrispondenza rigorosa tra la teoria dei codici e le proprietà delle funzioni senza somma.

• Costruzione della Corrispondenza: Il lavoro dimostra che una funzione senza somma di ordine $(n-r)$ non degenere $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ è equivalente all'esistenza di un sottocodice lineare di $RM(r, n)$ con codimensione $m$ e distanza minima $3 \cdot 2^{n-r-1}$. Ciò è ottenuto costruendo una matrice di controllo di parità per il sottocodice utilizzando i vettori di valutazione della funzione $F$.
• Analisi Algebrica: Gli autori utilizzano il grado algebrico delle funzioni booleane, le proprietà delle derivate di ordine superiore e la struttura dei codici di Reed-Muller (in particolare la caratterizzazione dei codeword di peso minimo e secondo-minimo tramite piani e le loro differenze simmetriche) per derivare condizioni necessarie per l'esistenza di funzioni senza somma.
• Colorazione di Grafi tramite Funzioni: Il lavoro utilizza la "funzione testimone" $\omega_F(A) = \sum_{x \in A} F(x)$ per definire colorazioni sui grafi di Grassmann. Assicurando che i vertici adiacenti (sottospazi che si intersecano in dimensione $k-1$) mappino su valori non nulli distinti, gli autori costruiscono colorazioni valide.
• Verifica Computazionale: Per dimensioni piccole ($n=5, 6, 7$), gli autori eseguono ricerche computazionali per verificare l'esistenza di funzioni senza somma multiordine (funzioni che sono senza somma per più ordini $k$) tra le note funzioni quasi perfette non lineari (APN).

Contributi e Risultati Chiave

1. Teorema di Equivalenza (Teorema 1.1):
   Il lavoro stabilisce una corrispondenza biunivoca: esiste una funzione $(n, m)$ senza somma di ordine $(n-r)$ non degenere se e solo se esiste un sottocodice lineare di codimensione $m$ di $RM(r, n)$ con distanza minima $3 \cdot 2^{n-r-1}$.

   • Significato: Ciò genera una nuova famiglia di sottocodici di Reed-Muller che evitano tutti i codeword di peso minimo di $RM(r, n)$. Questi sottocodici hanno una distanza minima 1,5 volte quella del codice originale, con una codimensione di soli $n$. Per l'intervallo $2 < r < n-2$, questi codici sembrano essere nuovi.

2. Nuovi Limiti Inferiori su $m$ (Teorema 3.5):
   Gli autori derivano il primo limite inferiore non banale sulla dimensione di uscita $m$ per l'esistenza di funzioni senza somma di ordine $k$. Per $2 \le k \le n-2$, se una funzione $(n, m)$ è senza somma di ordine $k$, allora:
   $$m \ge \max\{n - k + 2, k + 2\}$$
   Questo risultato implica che per $m < n$, tali funzioni non possono esistere per certi intervalli di $k$, affinando le conoscenze precedenti che erano limitate al caso $m=n$.

3. Non Degenerazione delle Famiglie Note (Teorema 3.6):
   Il lavoro dimostra che la famiglia infinita di funzioni potenza $F_{k,j}(x) = x^{(2^{jk}-1)/(2^j-1)}$ introdotta da Carlet è non degenere per $k < n$. Ciò conferma che queste funzioni richiedono genuinamente l'intera dimensione dello spazio di uscita $n$ e non possono essere ridotte a funzioni di dimensione inferiore mantenendo la proprietà senza somma.

4. Miglioramenti nelle Colorazioni dei Grafi di Grassmann (Teorema 5.1):
   Gli autori generalizzano i risultati precedenti sulle colorazioni. Mostrano che se esiste una funzione $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ di grado algebrico $k$ che è sia senza somma di ordine $(k-1)$ che di ordine $k$, allora il grafo di Grassmann $J_2(n+1, k)$ ammette una colorazione valida con $\binom{m}{1}_2 = 2^m - 1$ colori.

   • Applicazione: Utilizzando la funzione inversa in dimensioni dispari (che è senza somma di ordine $\{1, 2, n-2, n-1\}$), gli autori derivano una colorazione per $J_2(n+1, n-1)$.
   • Risultato Specifico: Per $n=5$, l'esistenza di funzioni cubiche senza somma di ordine $\{2, 3\}$ ($x^7$ e $x^{21}$) porta al limite $\chi(J_2(6, 3)) \le 31$, migliorando i limiti superiori precedentemente noti.

5. Risultati Computazionali sulle Funzioni Multiordine:
   Il lavoro riporta che per $n=6$, nessuna funzione APN nota è senza somma di terzo o quarto ordine. Per $n=7$, solo funzioni equivalenti alle funzioni APN di Gold ($x^{15}, x^{77}, x^{85}$) sono state trovate essere senza somma di quarto ordine. Ciò suggerisce che le funzioni senza somma multiordine sono rare e difficili da costruire.

Significato e Affermazioni
Il lavoro afferma di essere il primo a stabilire un legame diretto tra le funzioni senza somma di ordine $k$ e la costruzione di sottocodici di Reed-Muller con distanze minime potenziate. Questa connessione fornisce un nuovo strumento algebrico per generare sottocodici che evitano i codeword di peso minimo.

Inoltre, il lavoro fornisce le prime condizioni necessarie non banali per l'esistenza di funzioni senza somma con $m < n$, affrontando una specifica domanda aperta posta da Carlet. Collegando queste funzioni al numero cromatico dei grafi di Grassmann, il lavoro offre un metodo per migliorare i limiti superiori su $\chi(J_2(n, k))$, in particolare per i casi in cui $k > 2$.

Gli autori mantengono una posizione modesta riguardo alla costruzione di nuove funzioni senza somma, notando che costruire esempi genuinamente nuovi oltre alle note funzioni potenza rimane difficile. Inquadrano l'esistenza di funzioni senza somma multiordine per $k \ge 3$ come un significativo problema aperto con implicazioni sia per la teoria dei codici (codici non lineari) che per la teoria dei grafi.