Weight distributions of two classes of linear codes with few weights derived from Weil sums

Technische Samenvatting: Gewichtsverdelingen van twee klassen lineaire codes afgeleid van Weil-sommen

Probleemstelling
Lineaire codes met weinig gewichten zijn van groot belang in de coderingstheorie vanwege hun toepassingen in secret sharing-schema's, authenticatiecodes, associatieschema's en sterk reguliere grafen. Een primaire uitdaging in dit veld is de constructie van nieuwe families van lineaire codes met specifieke gewichtsverdelingen (dat wil zeggen, een klein aantal verschillende niet-nul gewichten) en het bepalen van hun parameters (lengte, dimensie en minimale afstand). Hoewel eerdere werken gebruik hebben gemaakt van definiërende verzamelingen gebaseerd op tracefuncties en specifieke polynomiale vormen om dergelijke codes te construeren, blijft er een behoefte aan het verkennen van nieuwe definiërende verzamelingen die gebruikmaken van geavanceerde evaluaties van exponentiële sommen, in het bijzonder binomiale Weil-sommen, om codes met diverse gewichtsstructuren te genereren.

Methodologie
De auteurs construeren twee onderscheidende klassen van $p$-aire lineaire codes over een eindig veld $\mathbb{F}_q$, waarbij $q = p^e$, waarbij $p$ en $\ell$ verschillende oneven priemgetallen zijn, en $e = \phi(\ell^k)$. De constructie steunt op de methode van de definiërende verzameling, waarbij een lineaire code $C_D$ wordt gedefinieerd als:
$$C_D = \{c(\gamma, \delta) = (\text{Tr}_1^e(\gamma x + \delta y))_{(x,y) \in D} : \gamma, \delta \in \mathbb{F}_q\}$$
Het artikel onderzoekt twee specifieke definiërende verzamelingen, $D_u$ en $D'$, die verschillen van eerdere constructies door een specifieke binomiale Weil-somstructuur te incorporeren.

1. Definiërende verzameling $D_u$: Gedefinieerd als $D_u = \{(x, y) \in \mathbb{F}_q^2 \setminus \{(0,0)\} : \text{Tr}_1^e(x + y^N) = u\}$, waarbij $N = \frac{q-1}{2\ell^k}$ en $u \in \mathbb{F}_p$.
2. Definiërende verzameling $D'$: Gedefinieerd als $D' = \{(x, y) \in \mathbb{F}_q^2 \setminus \{(0,0)\} : f(x) + \text{Tr}_1^e(y^N) = 0\}$, waarbij $f$ een zwak regelmatige bent-functie is van $\mathbb{F}_q$ naar $\mathbb{F}_p$ die voldoet aan specifieke homogeniteitsvoorwaarden op zijn duale.

De kernmethodologie omvat de gedetailleerde evaluatie van exponentiële sommen, specifiek de binomiale Weil-som $S_{2\ell^k}(a, b)$ en gerelateerde sommen over cyclotome velden. De auteurs maken gebruik van:

• Eigenschappen van canonieke additieve en kwadratische multiplicatieve karakters.
• Evaluaties van Gauss-sommen en Weil-sommen afgeleid van recent werk door Cheng, Gao en Sheng.
• De theorie van zwak regelmatige bent-functies en hun dualen.
• Het partitioneren van indexverzamelingen op basis van de orde van elementen in de multiplicatieve groep om de trace-condities af te handelen.

Door het aantal oplossingen van de definiërende vergelijkingen voor diverse paren $(\gamma, \delta)$ te berekenen, leiden de auteurs de Hamming-gewichten van de codewoorden en de bijbehorende frequenties af.

Belangrijkste Bijdragen en Resultaten
Het artikel biedt een volledige karakterisering van de parameters en gewichtsverdelingen voor de geconstrueerde codes onder diverse voorwaarden op $p$, $\ell$, $k$ en $u$.

1. Codes uit $D_u$:

   • De auteurs bepalen de gewichtsverdelingen voor vijf verschillende gevallen op basis van de waarde van $u$ en de congruentie van $\ell$ modulo $p$.
   • De resulterende codes vertonen twee, vier of zes niet-nul gewichten.
   • Specifiek, wanneer $u \neq 0$ en bepaalde voorwaarden met betrekking tot kwadratische niet-residuen worden vervuld, levert de constructie een oneindige familie van twee-gewichts lineaire codes op.
   • Onder specifieke condities (waarbij de ratio van het minimale tot het maximale gewicht groter is dan $\frac{p-1}{p}$), worden deze codes bewezen minimaal te zijn, wat ze geschikt maakt voor toepassingen in secret sharing.

2. Codes uit $D'$:

   • Door een zwak regelmatige bent-functie $f$ te incorporeren, construeren de auteurs codes met complexere gewichtsstructuren.
   • Afhankelijk van de congruentie van $p$ modulo 4 en de relatie tussen $\ell$ en $p$, vertonen de codes zes, acht of negen niet-nul gewichten.
   • De gewichtsverdelingen zijn expliciet getabelleerd voor alle gevallen, waarbij termen worden gebruikt die afgeleid zijn van het teken van de Walsh-transformatie van $f$ en kwadratische karakterevaluaties.

3. Optimaliteit:

   • Een significant resultaat is de identificatie van een oneindige familie van optimale twee-gewichts lineaire codes afgeleid van de $D_u$-constructie. Deze codes voldoen aan de Griesmer-grens, een fundamentele ondergrens op de lengte van een lineaire code gegeven zijn dimensie en minimale afstand.

Betekenis
Het artikel claimt significant te zijn op de volgende gebieden:

• Nieuwigheid van Definiërende Verzamelingen: De gebruikte definiërende verzamelingen introduceren een nieuwe binomiale Weil-somstructuur ($S_{2\ell^k}(a, b)$) die verschilt van eerdere constructies die in de literatuur worden samengevat (bijv. die gebruikmaken van eenvoudige tracefuncties of specifieke machtsfuncties).
• Diversiteit van Gewichtsverdelingen: Het werk breidt het bekende landschap van lineaire codes met weinig gewichten uit, door expliciete constructies te bieden voor codes met 2, 4, 6, 8 en 9 niet-nul gewichten.
• Optimaliteit en Minimaliteit: De constructie van een oneindige familie van optimale twee-gewichts codes die voldoet aan de Griesmer-grens is een opmerkelijke bijdrage aan de zoektocht naar efficiënte foutcorrigerende codes. Bovendien versterkt de identificatie van minimale codes onder specifieke condities het nut van deze constructies voor cryptografische toepassingen zoals secret sharing.
• Methodologische Rigor: Het artikel demonstreert een rigoureuze toepassing van Weil-sommen en cyclotome veldentheorie om het probleem van de bepaling van de gewichtsverdeling op te lossen, wat een model biedt voor het analyseren van vergelijkbare codeconstructies.

De auteurs concluderen dat hun werk succesvol eerdere methoden generaliseert en een rijke bron vormt voor nieuwe lineaire codes met gewenste eigenschappen voor zowel theoretisch onderzoek als praktische toepassing.