Algebraic Expander Codes

Titel: Algebraic Expander Codes

Auteurs: Swastik Kopparty en Itzhak Tamo
Datum: 27 maart 2026

1. Het Probleem

Expander-codes (of Tanner-codes) combineren dunne grafen met lokale beperkingen om codes te creëren met lineaire tijd-decodering en asymptotisch goede afstands-ratio trade-offs. Een fundamenteel probleem in het ontwerp van deze codes is de inherente spanning tussen de snelheid (rate) van de lokale code en de gegarandeerde snelheid van de globale code.

• De Bestaande Barrière: Voor een expander-code gedefinieerd op een reguliere graaf met lokale codes van snelheid $r$, levert een standaard argument voor het tellen van beperkingen een ondergrens op voor de globale snelheid: $R \ge 2r - 1$.
• De "Low-Rate" Regime: Dit betekent dat er alleen een positieve globale snelheid gegarandeerd kan worden als $r > 1/2$. In het regime waar $r \le 1/2$ (de "low-rate" regime), wordt deze ondergrens niet-positief.
• Praktische Relevantie: Dit regime is echter cruciaal voor toepassingen die algebraïsche lokale beperkingen vereisen, zoals Reed-Solomon (RS) codes. Een specifiek voorbeeld is de vermenigvuldigings-eigenschap (Schur-product): het componentsgewijze product van twee codewoorden uit een RS-code met snelheid $r$ behoort tot een RS-code met snelheid $\approx 2r$. Om te zorgen dat het product een niet-triviale error-correcting code blijft (d.w.z. snelheid $< 1$), moet de initiële code $r < 1/2$ hebben.
• De Uitdaging: Er bestaat een behoefte aan expliciete expander-codes die lokale RS-beperkingen met $r \le 1/2$ ondersteunen, maar toch een positieve globale snelheid en lineaire afstand behouden. Bestaande algebraïsche constructies (zoals LRC's) gebruiken vaak commutatieve subgroepen, wat leidt tot dichte grafen of faalt in het garanderen van een positieve snelheid in dit regime.

2. Methodologie

De auteurs introduceren een puur algebraïsche aanpak die afwijkt van het traditionele "graaf + lokale code" paradigma. In plaats van een expander-graaf en lokale codes onafhankelijk te kiezen en te "lijmen", definiëren ze de code als een orbit-evaluatiecode.

• Algebraïsche Opzet:

  • De code wordt gedefinieerd door het evalueren van een gestructureerde deelruimte van polynomen op een orbit $\Omega$ van een groep $A = \langle G, H \rangle$ binnen de affiene groep $AGL(1, \mathbb{F})$.
  • Niet-commutatieve Subgroepen: Het kernidee is het gebruik van twee subgroepen van tegengestelde algebraïsche typen:
    1. $G$: Een additieve subgroep (translaties: $x \mapsto x + g$).
    2. $H$: Een multiplicatieve subgroep (schalingen: $x \mapsto hx$).
  • Omdat translaties en schalingen niet commuteren, is de gegenereerde groep $A$ aanzienlijk groter dan het product van de grootte van $G$ en $H$. Dit resulteert in een dunne (sparse) coset-geometrie in plaats van de dichte, rooster-achtige structuren die ontstaan bij commutatieve subgroepen.

• Nieuw Concept: $u$-Base Graad:

  • Om de globale snelheid te bewijzen in het regime $r \le 1/2$, introduceren de auteurs een nieuwe definitie van polynoomgraad: de $u$-base graad.
  • Voor een polynoom $u(X)$ wordt elke polynoom $f(X)$ uniek geschreven als $f(X) = \sum c_i(X)u(X)^i$ met $\deg(c_i) < \deg(u)$. De $u$-base graad is het maximum van de graden van de coëfficiënten $c_i$.
  • Ze bewijzen dat deze graad sub-additief is ($\deg_u(fg) \le \deg_u(f) + \deg_u(g)$). Dit stelt hen in staat om de voorwaarden voor de boodschap-polynomen om te zetten in lineaire beperkingen op hun coëfficiënten, waarna de dimensie wordt geschat via het volume van een hoog-dimensionale polytoop.

• Spectrale Expansie:

  • De expansie van de onderliggende graaf wordt bewezen door de tweede singuliere waarde van de genormaliseerde bi-adjacentiematrix te analyseren.
  • Dit wordt gedaan via karakter-sommen (character sums). De eigenwaarden worden uitgedrukt als sommen van additieve karakters over de multiplicatieve subgroep $H$. Klassieke schattingen (zoals Gauss-sommen) worden gebruikt om te tonen dat de tweede singuliere waarde klein is ($O(1/\sqrt{p})$), wat sterke spectrale expansie garandeert.

3. Belangrijkste Bijdragen

1. Algebraic Expander Codes: Een expliciete familie van Tanner-type codes waarbij de lokale beperkingen Reed-Solomon codes zijn.
2. Doorbreken van de $2r-1$ Barrière: De constructie garandeert een positieve globale snelheid voor elke vaste lokale snelheid $r \in (0, 1)$, inclusief het kritieke regime $r \le 1/2$.
3. Behoud van Algebraïsche Structuur: De lokale codes zijn strikt Reed-Solomon, wat de code geschikt maakt voor toepassingen die de vermenigvuldigings-eigenschap vereisen (zoals kwantum-LDPC codes en High-Dimensional Expanders).
4. Dunne Geometrie: Door het gebruik van niet-commutatieve subgroepen (translatie en schaling) wordt een dunne graaf verkregen, in tegenstelling tot de dichte grafen van eerdere algebraïsche constructies met commutatieve subgroepen.
5. Twee Expliciete Instantiaties:
   • Instantiatie I: Gebruikt de volledige multiplicatieve groep van een veld, wat leidt tot een zeer symmetrische graaf en een schone spectrale analyse via orthogonaliteit.
   • Instantiatie II: Gebruikt een cyclische subgroep van de multiplicatieve groep, wat een instelbare parameter $\gamma$ introduceert om de graad en de lokale snelheid te balanceren.

4. Resultaten

Voor een vaste lokale snelheid $r$ en een parameter $m \ge 2$ (bepalend voor de graad), bestaan er expliciete lineaire codes met de volgende eigenschappen (voor oneindig veel bloklengtes $n$):

• Lokale Beperkingen: Elke coördinaat participeert in twee lokale RS-beperkingen met snelheid $r + o(1)$.
• Globale Snelheid ($R$): De globale snelheid is begrensd door een expliciete positieve constante die afhangt van $r$ en $m$.
  • Voor $D=n$ (geen extra globale graadbeperking) geldt bijvoorbeeld: $R \ge \frac{r^{2m+1}}{(2m+1)!}$ (voor Instantiatie I).
  • Dit is significant omdat het positief blijft zelfs als $r \le 1/2$.
• Relatieve Afstand ($\delta$): De globale relatieve afstand voldoet aan $\delta \ge (1-r)^2 - o(1)$. Dit volgt uit de spectrale expansie van de graaf en de lokale afstand van de RS-codes.
• Spectrale Expansie: De onderliggende bipartiete graaf is een sterke spectrale expander met een genormaliseerde tweede singuliere waarde $\sigma_2 \le O(1/\sqrt{p})$, waarbij $p$ het karakteristiek van het veld is.
• Decodering: De codes ondersteunen lineaire tijd-decodering via iteratieve expander-decodering. Daarnaast bieden ze algebraïsche decoderingsmogelijkheden door de globale polynoomstructuur.

Beperkingen:

• De alfabetgrootte groeit polynomsch met de bloklengte (niet constant).
• De graad van de graaf is polynomsch in $n$ (ongeveer $n^{1/(m+1)}$), in plaats van constant. Het bereiken van constante graad blijft een open vraag.

5. Betekenis en Toekomstperspectief

Dit werk is van groot belang voor de theorie van codering en de praktische implementatie van geavanceerde codes:

• Kwantum Computing: De constructie maakt het mogelijk om kwantum-LDPC codes te bouwen met transversale niet-Clifford-poorten, wat afhankelijk is van het vermenigvuldigen van algebraïsche codes met snelheid onder de helft.
• High-Dimensional Expanders (HDX): De methode biedt een nieuwe manier om HDX's te construeren met de vereiste algebraïsche vermenigvuldigings-eigenschappen.
• Theoretische Doorbraak: Het lost het probleem op van het verkrijgen van positieve snelheid in het "low-rate" regime voor expander-codes, een gebied waar eerdere methoden faalden.

Open Vragen:
De auteurs wijzen op enkele open problemen, waaronder het verbeteren van de ondergrens voor de snelheid (die momenteel factorieel afneemt met $m$), het bereiken van constante graad in de grafen, en het onderzoeken van lokale testbaarheid en generalisaties naar hogere dimensies (2D simpliciale complexen).

Kortom, dit artikel introduceert een krachtig nieuw algebraïsch raamwerk dat de beperkingen van traditionele expander-codes doorbreekt en een brug slaat tussen combinatorische expansie en algebraïsche structuren die essentieel zijn voor moderne toepassingen.