Construction of codes over a commutative non-unital ring from simplicial complexes and their applications

Sintesi Tecnica: Costruzione di Codici su un Anello Commutativo Non-Unitale da Complessi Simpliciali e loro Applicazioni

Problema e Contesto
Il documento affronta la costruzione di codici lineari su anelli finiti, concentrandosi specificamente su un anello commutativo non-unitale $I$ di ordine $p^2$ e sulla sua estensione $S$ di grado $r$. Mentre i codici lineari su campi finiti e anelli unitali sono ben stabiliti, lo studio dei codici su anelli non-unitali è uno sviluppo più recente. Lavori precedenti hanno esplorato codici quasi auto-duali e auto-ortogonali su anelli non-unitali, incluso l'anello non commutativo $E$ di ordine $p^2$. Questo lavoro estende l'indagine all'anello commutativo non-unitale $I$ e alla sua estensione $S$, con l'obiettivo di costruire codici con parametri ottimali utilizzando insiemi definitori derivati da complessi simpliciali. L'obiettivo primario è determinare la distribuzione dei pesi, la minimale e l'ottimalità di questi codici e esplorare le loro applicazioni in schemi di condivisione del segreto (secret-sharing), codici localmente recuperabili (LRC) e nella costruzione di grafi fortemente regolari.

Metodologia
Gli autori impiegano il metodo dell'insieme definitorio per costruire codici lineari sull'anello $S$.

1. Struttura dell'Anello: L'anello $S$ è definito come un'estensione dell'anello commutativo non-unitale $I = \langle a, b \mid pa=0, pb=0, a^2=b, ab=0 \rangle$. Gli elementi in $S$ sono della forma $as + bt$ dove $s, t \in \mathbb{F}_q$ ($q=p^r$).
2. Costruzione del Codice: Un codice lineare $C_D$ di lunghezza $|D|$ è definito su $S$ utilizzando un multiset ordinato $D \subseteq S^m$ come insieme definitorio:
   $$C_D = \{ (v \cdot d)_{d \in D} : v \in S^m \}$$
   dove il prodotto $v \cdot d$ è definito tramite le regole di moltiplicazione dell'anello.
3. Complessi Simpliciali: Gli insiemi definitori $D$ sono costruiti utilizzando complessi simpliciali $\Delta$ su $\mathbb{F}_q^m$. Nello specifico, gli autori considerano insiemi della forma $D = a\Delta_1 + b\Delta_2$, dove $\Delta_1$ e $\Delta_2$ sono complessi simpliciali (potenzialmente con molteplici elementi massimali) e i loro complementi.
4. Analisi del Peso:
   • Peso di Lee: Il peso di Lee dei codici viene analizzato utilizzando la mappa di Gray $\Phi: S \to \mathbb{F}_q^2$ definita da $\Phi(as+bt) = (t, s+t)$. Il peso di Lee è calcolato come il peso di Hamming della immagine di Gray.
   • Codici di tipo Subfield-like: Una mappa di proiezione $\tau: S \to \mathbb{F}_q$ definita da $\tau(as+bt) = t$ è utilizzata per costruire codici di tipo subfield-like $\tau(C_D)$ su $\mathbb{F}_q$.
5. Strumenti Analitici: Gli autori utilizzano somme di caratteri, il principio di inclusione-esclusione e le proprietà dei complessi simpliciali (specificamente elementi massimali e le loro intersezioni) per derivare distribuzioni di peso e parametri espliciti.

Contributi Chiave e Risultati

1. Distribuzioni di Peso e Parametri Espliciti:
   Il documento determina le distribuzioni del peso di Lee per i codici $S$-lineari dove gli insiemi definitori sono formati da combinazioni di complessi simpliciali e i loro complementi. Vengono analizzati cinque casi distinti di insiemi definitori ($D = a\Delta_1 + b\Delta_2$, $a\Delta_1 + b\Delta_2^c$, ecc.).

   • I parametri (lunghezza, dimensione e distanza di Lee minima) dei codici $S$-lineari sono stabiliti.
   • Si dimostra che le immagini di Gray $\Phi(C_D)$ e i codici subfield-like $\tau(C_D)$ sono codici lineari su $\mathbb{F}_q$.
   • Vengono fornite distribuzioni di peso esplicite per i casi in cui i complessi simpliciali hanno singoli elementi massimali, rivelando che molti dei codici risultanti sono few-weight (specificamente 1-weight o 2-weight) e divisibili.

2. Minimalità e Ottimalità:

   • Minimalità: Sono stabilite condizioni sufficienti sotto le quali i codici immagine di Gray e i codici subfield-like sono minimali. Un codice è minimale se ogni cod codeword non nullo copre solo i suoi multipli scalari. Gli autori derivano disuguaglianze che coinvolgono le dimensioni degli elementi massimali dei complessi simpliciali e la dimensione del campo $q$ che garantiscono la minimalità.
   • Ottimalità: Il documento investiga l'ottimalità di questi codici rispetto al limite di Griesmer. Diverse famiglie di codici sono mostrate come ottimali sotto specifiche condizioni sui parametri $m, |M|, |N|$, e $q$.

3. Auto-ortogonalità:
   Vengono fornite condizioni affinché i codici immagine di Gray e i codici subfield-like siano euclidei o ermitiani auto-ortogonali. Queste condizioni dipendono dalla divisibilità dei pesi dei codici e dai valori specifici di $q$ (ad esempio, $q=2, 3, 4$).

4. Applicazioni:

   • Codici Localmente Recuperabili (LRCs): Gli autori costruiscono famiglie di LRC con località 2 e 3. Questi codici sono derivati dai codici subfield-like $\tau(C_D)$ selezionando specifici insiemi definitori correlati agli elementi non nulli dei complessi simpliciali.
   • Schemi di Condivisione del Segreto (SSS): Sono determinati le strutture di accesso minimali degli schemi di condivisione del segreto basati sui duali dei codici minimali costruiti. Il documento specifica il numero di insiemi di accesso minimali e la frequenza di partecipazione di ciascun partecipante.
   • Grafi Fortemente Regolari (SRG): Sfruttando la corrispondenza tra i codici proiettivi a due pesi e gli SRG, il documento costruisce diverse famiglie di grafi di Cayley fortemente regolari. I parametri $(N, K, \lambda, \mu)$ di questi grafi sono determinati esplicitamente. Inoltre, viene dimostrato che i grafi complementari di questi SRG sono anch'essi fortemente regolari, con i relativi parametri calcolati esplicitamente.

Significato e Rivendicazioni
Il documento rivendica di far avanzare la teoria dei codici su anelli non-unitali applicando con successo l'approccio del complesso simpliciale all'anello commutativo non-unitale $I$ e alla sua estensione $S$. La significatività risiede nel:

• Generare nuove famiglie di codici divisibili e a pochi pesi su campi finiti tramite immagini di Gray e costruzioni subfield-like.
• Fornire criteri espliciti affinché questi codici siano minimali, ottimali e auto-ortogonali, aspetti cruciali per le applicazioni in crittografia e combinatoria.
• Dimostrare la versatilità della costruzione, che produce codici adatti per i Codici Localmente Recuperabili (critici per l'archiviazione distribuita) e per gli Schemi di Condivisione del Segreto (critici per la distribuzione sicura dei dati).
• Stabilire un legame diretto tra queste costruzioni algebriche e i Grafi Fortemente Regolari, fornendo un metodo per generare SRG con parametri specifici dai principi della teoria dei codici.

Il lavoro non propone implementazioni sperimentali o estensioni teoriche future oltre l'ambito dei codici costruiti e delle loro immediate applicazioni. Si concentra sulla derivazione algebrica dei parametri e sulla verifica delle loro proprietà all'interno del quadro stabilito della teoria dei codici.