Algebraic Expander Codes

Titolo: Algebraic Expander Codes

Autori: Swastik Kopparty e Itzhak Tamo
Data: 27 marzo 2026 (preprint)

---

1. Il Problema: Il Dilemma del Tasso nei Codici Espander

I codici espander (o codici di Tanner) combinano grafi sparsi con vincoli locali per ottenere codici con buone proprietà di distanza e tasso, decodificabili in tempo lineare. Tuttavia, esiste un ostacolo fondamentale nella loro progettazione:

• Il limite del conteggio dei vincoli: Per un codice espander definito su un grafo regolare con codici locali di tasso $r$, l'argomento standard di conteggio dei vincoli fornisce un limite inferiore per il tasso globale $R \ge 2r - 1$.
• Il regime a basso tasso: Questo limite implica che per garantire un tasso globale positivo ($R > 0$), il tasso locale deve soddisfare $r > 1/2$. Nel regime "a basso tasso" ($r \le 1/2$), il limite $2r - 1$ diventa non positivo, offrendo alcuna garanzia di tasso positivo.
• L'importanza del regime $r \le 1/2$: Questo regime è cruciale per applicazioni avanzate come il calcolo quantistico fault-tolerant e gli Espander ad Alta Dimensione (HDX). In particolare, le proprietà algebriche dei codici di Reed-Solomon (RS), come la proprietà di moltiplicazione (prodotto di Schur), richiedono che il tasso locale sia strettamente inferiore a $1/2$ affinché il codice prodotto sia un codice di correzione errori non banale.

Obiettivo: Costruire esplicitamente una famiglia di codici espander che mantenga vincoli locali di tipo Reed-Solomon (per preservare la struttura algebrica necessaria) e che garantisca un tasso globale positivo anche quando $r \le 1/2$, superando il limite classico $2r - 1$.

---

2. Metodologia: Un Approccio Puramente Algebrico

Gli autori abbandonano il paradigma standard "grafo + codice locale" (dove si sceglie un grafo espander e un codice locale indipendentemente) per un approccio puramente algebrico basato su azioni di gruppo.

A. Struttura Algebrica e Geometria dei Coset

• Definizione del Codice: Il codice è definito valutando un sottospazio strutturato di polinomi su un'orbita $\Omega$ di un sottogruppo $A$ del gruppo affine $AGL(1, \mathbb{F})$.
• Sottogruppi Non Commutativi: Il nucleo dell'innovazione risiede nella scelta di due sottogruppi di $AGL(1, \mathbb{F})$ di tipo opposto:
  1. Un sottogruppo additivo $G$ (traslazioni: $x \mapsto x + g$).
  2. Un sottogruppo moltiplicativo $H$ (scalature: $x \mapsto hx$).
• Geometria Sparsa: Poiché $G$ e $H$ non commutano, il gruppo generato $A = \langle G, H \rangle$ è molto più grande del prodotto delle loro dimensioni. Questo genera una geometria di coset sparsa (un grafo bipartito), a differenza delle geometrie dense (tipo griglia) che emergono quando si usano sottogruppi commutativi dello stesso tipo.

B. Spazio dei Messaggi e Grado u-Base

Per dimostrare che il tasso globale è positivo anche per $r \le 1/2$, gli autori introducono una nuova nozione di grado polinomiale:

• Grado u-Base: Dato un polinomio $u(X)$, ogni polinomio $f(X)$ ha un'unica espansione in base $u$. Il "grado u-base" è il massimo grado tra i coefficienti di questa espansione.
• Sottospazio dei Messaggi: Lo spazio dei messaggi $W_{r,D}$ è definito come l'insieme dei polinomi che hanno:
  1. Grado globale $< D$.
  2. Grado $g$-base $< r|G|$.
  3. Grado $h$-base $< r|H|$.
• Dimostrazione del Tasso: La sfida è dimostrare che la dimensione di questo sottospazio è sufficientemente grande. Gli autori usano un argomento di conteggio del volume di un poliedro ad alta dimensione, approssimando il numero di monomi validi tramite un'integrazione continua delle variabili normalizzate.

C. Espansione Spettrale

La proprietà di espansione del grafo sottostante è dimostrata analizzando il secondo valore singolare della matrice di adiacenza normalizzata.

• Metodo: Si riduce il problema alla stima di somme di caratteri additivi su sottogruppi moltiplicativi.
• Risultato: Utilizzando limiti classici (somme di Gauss e ortogonalità dei caratteri), si dimostra che il secondo valore singolare è dell'ordine di $O(1/\sqrt{p})$, dove $p$ è la caratteristica del campo, garantendo una forte espansione spettrale.

---

3. Risultati Chiave

Gli autori presentano due istanze esplicite del framework generale, entrambe con le seguenti proprietà:

1. Vincoli Locali Reed-Solomon: Ogni coordinata del codice partecipa a due vincoli locali (uno per ogni orbita di $G$ e uno per $H$), che sono codici di Reed-Solomon di tasso $r$. Questo preserva la proprietà di moltiplicazione necessaria per le applicazioni quantistiche.
2. Tasso Globale Positivo: Il codice ottiene un tasso globale $R$ limitato inferiormente da una costante positiva dipendente da $r$ e dal parametro di sparsità $m$, anche quando $r \le 1/2$. Questo supera il limite $2r-1$.
3. Distanza Lineare: Il codice ha una distanza relativa globale $\delta \ge (1-r)^2 - o(1)$, garantita dall'espansione spettrale del grafo.
4. Decodifica: Il codice ammette sia la decodifica combinatoria iterativa tipica dei codici espander, sia (nel caso di vincoli globali aggiuntivi) algoritmi di decodifica algebrica basati sui vincoli di grado.

Dettagli delle Istanze:

• Istanza 1: Usa $H = \mathbb{F}_{p^m}^\times$ (tutto il gruppo moltiplicativo). Offre un'analisi spettrale molto pulita basata sull'ortogonalità dei caratteri, ma richiede un campo di dimensione maggiore.
• Istanza 2: Usa un sottogruppo ciclico $H$ di indice costante in $\mathbb{F}_{p^{m+1}}^\times$. Introduce un parametro $\gamma$ per bilanciare i gradi dei nodi e utilizza limiti di somme di Gauss.

---

4. Significato e Impatto

• Superamento di una Barriera Teorica: Il lavoro risolve un problema aperto nella teoria dei codici, dimostrando che è possibile costruire codici espander con vincoli locali algebrici (RS) che mantengono un tasso positivo anche nel regime a basso tasso, dove i metodi precedenti fallivano.
• Abilitazione di Applicazioni Quantistiche: La capacità di utilizzare codici RS con $r \le 1/2$ è fondamentale per la costruzione di codici LDPC quantistici con porte non-Clifford trasversali e per la costruzione di Espander ad Alta Dimensione (HDX) con proprietà di moltiplicazione.
• Nuovo Paradigma Algebrico: L'uso di sottogruppi non commutativi (traslazioni e scalature) per generare grafi sparsi con forte espansione apre una nuova direzione nella progettazione di codici basati su geometrie algebriche, distinguendosi dai metodi basati su grafi casuali o strutture commutative.

5. Limitazioni e Domande Aperte

• Dimensione dell'Alfabeto: La dimensione dell'alfabeto non è costante, ma cresce polinomialmente con la lunghezza del blocco (tipico dei codici RS e LRC algebrici).
• Grado del Grafo: Sebbene il grafo sia più sparso rispetto alle costruzioni commutative, il grado dei nodi cresce polinomialmente con $n$ (come $n^{1/(m+1)}$), invece di essere costante. Ottenere un grado costante o polylogaritmico rimane una sfida aperta.
• Tightness del Limite di Tasso: Il limite inferiore sul tasso globale derivato sembra non essere stretto (satura quando il grado globale supera il tasso locale e decade fattorialmente con la sparsità $m$), suggerendo che l'analisi attuale potrebbe sottostimare la dimensione reale del codice.

In sintesi, questo lavoro fornisce una costruzione esplicita e potente di codici espander che unisce la robustezza della teoria degli espander con la ricchezza strutturale dei codici algebrici, aprendo la strada a nuove applicazioni nella computazione quantistica e nella teoria degli espander ad alta dimensione.