Function-Based Minimal Linear Codes over Galois Rings $\mathrm{GR}(p^{n}, \ell)$: Minimality Criteria and Infinite Constructions

Titel

Function-gebaseerde Minimale Lineaire Codes over Galois-ring GR(pn, ℓ): Minimaliteitscriteria en Oneindige Constructies

1. Probleemstelling en Context

Minimale lineaire codes vormen een fundamentele klasse van codes met directe toepassingen in geheime deling (secret sharing), multiparty computation (MPC) en verifieerbare geheime deling. Een code is "minimaal" als elke niet-nul codewoord zijn draagvlak (support) niet strikt bevat van een ander niet-nul codewoord, tenzij ze elkaars scalaire veelvouden zijn.

Hoewel er uitgebreid onderzoek is gedaan naar minimale codes over eindige velden, is de theorie over eindige ringen, en specifiek over Galois-ring $GR(p^n, \ell)$, minder ontwikkeld. De overgang van velden naar ringen introduceert aanzienlijke algebraïsche complexiteit door de aanwezigheid van nuldelers (zero divisors) en een rijkere module-structuur. Bestaande criteria voor minimaliteit over velden (zoals die van Wu et al., 2022) zijn niet direct toepasbaar op ringen vanwege deze structurele verschillen.

Het doel van dit artikel is:

1. Een noodzakelijke en voldoende voorwaarde te formuleren voor minimaliteit van lineaire codes over $GR(p^n, \ell)$.
2. Function-gebaseerde constructiemethoden uit het veld-geval te generaliseren naar Galois-ring.
3. Oneindige families van minimale lineaire codes over $GR(p^n, \ell)$ te construeren.

2. Methodologie

De auteurs hanteren een algebraïsche benadering die steunt op de structuurtheorie van Galois-ring en Frobenius-dualiteit.

• Algebraïsche Structuur: $GR(p^n, \ell)$ is een eindige lokale kettingring (chain ring) met een residuveld $\mathbb{F}_q$ (waarbij $q=p^\ell$). De auteurs benutten de $p$-adische decompositie van elementen en de hiërarchie van idealen $\langle p \rangle \supset \langle p^2 \rangle \supset \dots \supset \langle p^{n-1} \rangle$.
• Dualiteit en Orthogonaliteit: Omdat Galois-ring Frobenius-ring zijn, geldt de perfecte dualiteit $(C^\perp)^\perp = C$. Minimaliteit wordt geanalyseerd via orthogonale modules $v^\perp = \{x \mid v \cdot x = 0\}$.
• Classificatie van Vectoren: Een cruciale stap is het onderscheid maken tussen:
  • Root words: Vectoren waarvan ten minste één component een eenheid (unit) is (reductie modulo $p$ is niet-nul).
  • Niet-root words: Vectoren die volledig in het maximale ideaal $\langle p \rangle$ liggen (alle componenten zijn nuldelers of nul).
• McCoy-rang: Voor het bepalen van lineaire onafhankelijkheid over ringen gebruiken de auteurs de McCoy-rang, die equivalent is aan de rang van de reductie modulo $p$ over het residuveld.
• Function-gebaseerde Constructie: Codes worden geconstrueerd via een generatormatrix $G_{\Lambda_f}$ die wordt gegenereerd door een functie $f: GR(p^n, \ell)^m \to GR(p^n, \ell)$. De minimaliteit van de code wordt teruggebracht tot de analyse van specifieke "root words" in de gegenereerde code.

3. Belangrijkste Bijdragen en Resultaten

A. Karakterisering van Minimaliteit (Hoofdstuk 3 & 4)

De auteurs bewijzen dat voor een $m$-dimensionale code ($m \geq 2$) over $GR(p^n, \ell)$, de code minimaal is dan en slechts dan als alle root words in de code minimaal zijn.

• Dit is een krachtige reductie: de complexe torsie-structuur van de ring (veroorzaakt door nuldelers) creëert geen extra obstakels voor minimaliteit, zolang de root words aan de voorwaarden voldoen.
• Er worden noodzakelijke en voldoende voorwaarden afgeleid voor codewoorden die zijn geconstrueerd via een functie $f$. Deze voorwaarden hangen af van het type van het codewoord (gebaseerd op de eenheid/nuldeler-status van de coëfficiënten):
  1. Eenheid-gebaseerd: Vereist $f(\beta_i) = w \cdot \beta_i$.
  2. Nuldeler-gebaseerd: Vereist een "gesynchroniseerde" voorwaarde $p^r f(\beta_i) = w \cdot \beta_i$, waarbij $p^r$ de waarde (valuation) van de nuldeler weergeeft.

B. Parameters en Ondergrenzen

De auteurs leiden expliciete ondergrenzen af voor de lengte $k$ van een $m$-dimensionale minimale lineaire code over $GR(p^n, \ell)$:

• Voor $m \geq 3$: $k > (m-1)q^n + q^{n-m}$.
• Voor $m = 2$: $k > q^n + q^{n-2} + 1$ (voor $n \geq 3$).
• Ze tonen aan dat voor $m=2$ de minimale lengte exact gelijk is aan $k(2; GR(p^n, \ell)) = q^n + q^{n-1}$.

C. Oneindige Families van Constructies (Hoofdstuk 5)

De kern van het artikel is de constructie van oneindige families van minimale codes door specifieke functies $f$ te kiezen die voldoen aan algebraïsche voorwaarden.

• Theorema 40 & 43: De auteurs geven criteria voor functies $f$ (gebaseerd op het gewicht van vectoren en hun componenten als eenheden of nuldelers) die garanderen dat de gegenereerde code $C_f$ minimaal is.
• Polynomen (Theorema 45): Een concrete toepassing wordt gegeven voor multivariate polynomen. Als $f$ een som is van monomen met disjuncte ondersteuningen (supports) en bepaalde exponenten, dan is de resulterende code minimaal.
• Stabiliteit: Het artikel toont aan dat het verwijderen van vectoren die scalaire veelvouden zijn van nuldelers de minimaliteit niet beïnvloedt (voor $m \geq 2$), wat de constructie vereenvoudigt.

4. Significatie en Impact

1. Generalisatie van Bestaande Werk: Het artikel generaliseert de function-gebaseerde constructies van Wu et al. (die geldig waren voor eindige velden) naar de veel complexere setting van Galois-ring. Dit vult een belangrijke lacune in de literatuur over codes over ringen.
2. Unificatie van Theorie: Het biedt een unificerend raamwerk dat minimaliteitstheorie, module-dualiteit over Frobenius-ring en function-gebaseerde constructies verbindt.
3. Toepassingspotentieel:
   • Cryptografie: Minimale codes zijn essentieel voor veilige geheime delingsschema's. De constructies over Galois-ring bieden nieuwe mogelijkheden voor cryptografische protocollen die gebruikmaken van ring-structuren, zoals post-kwantum cryptografie (lattice-based) en gedecentraliseerde systemen (blockchain).
   • Distributed Storage: De flexibiliteit van ring-gebaseerde codes kan leiden tot verbeterde prestaties in gedistribueerde opslagsystemen.
4. Nieuwe Richtingen: De auteurs identificeren open problemen, zoals het bepalen van de gewichtsverdeling (weight distribution), het construeren van codes met weinig gewichten (few-weight codes), en het uitbreiden van de theorie naar willekeurige eindige Frobenius-ring.

Conclusie

Dit artikel levert een fundamentele bijdrage aan de coderingstheorie door de theorie van minimale lineaire codes succesvol uit te breiden van eindige velden naar Galois-ring. Door de complexe interactie tussen nuldelers en eenheden te analyseren via Frobenius-dualiteit en $p$-adische filtratie, slagen de auteurs erin om strikte minimaliteitscriteria te formuleren en concrete, oneindige families van optimale codes te construeren. Dit opent de deur voor nieuwe cryptografische toepassingen en verdere theoretisch onderzoek binnen de algebraïsche coderingstheorie.