Symmetric Tensor Decompositions over Finite Fields

Technische Samenvatting: Symmetrische Tensorenontbindingen over Eindige Velden

Probleemstelling
Het artikel behandelt het probleem van het bepalen van de symmetrische tensorrang van de vermenigvuldigingsafbeelding $M_{q^m}: \mathbb{F}_{q^m} \times \mathbb{F}_{q^m} \to \mathbb{F}_{q^m}$ over eindige velduitbreidingen. Hoewel de standaard bilineaire complexiteit $\mu_q(m)$ (het minimum aantal niet-scalaire vermenigvuldigingen dat vereist is) een centraal onderwerp is in de algebraïsche complexiteitstheorie, legt de symmetrische tensorrang $\mu_q^{\text{sym}}(m)$ een extra beperking op: de twee lineaire vormen in elke rang-eenheidscomponent van de ontbinding moeten samenvallen. Hoewel $\mu_q^{\text{sym}}(m) \ge \mu_q(m) \ge 2m-1$, blijft het bepalen van exacte waarden voor $\mu_q^{\text{sym}}(m)$ moeilijk buiten specifieke regimes (bijvoorbeeld wanneer $q \ge 2m-2$). Bestaande methoden vertrouwen vaak op algebraïsche meetkunde of specifieke constructies, waardoor er een gat bestaat in constructieve benaderingen voor algemene parameters.

Methodologie
De auteurs ontwikkelen een constructief raamwerk gebaseerd op gelineariseerde polynomen (ook bekend als $q$-polynomen). De kernmethodologie berust op het vaststellen van een rangbehoudende correspondentie tussen drie wiskundige objecten:

1. Symmetrische gelineariseerde polynomen in de algebra $L_{m,q}$.
2. Symmetrische bilineaire vormen op $\mathbb{F}_{q^m}$ over $\mathbb{F}_q$, gedefinieerd via de veldspoor $\text{Tr}_{q^m/q}(xy)$.
3. Symmetrische matrices in $\mathbb{F}_q^{m \times m}$.

De auteurs identificeren dat een symmetrische tensorenontbinding van lengte $R$ overeenkomt met het bestaan van $R$ rang-eenheid symmetrische gelineariseerde polynomen die de ruimte van gelineariseerde polynomen die de vermenigvuldigingsafbeelding voorstellen, opspannen. Specifiek maken zij gebruik van het resultaat dat rang-eenheid symmetrische gelineariseerde polynomen de vorm $\alpha \text{Tr}_{q^m/q}(\beta x)$ aannemen, waarbij $\alpha/\beta \in \mathbb{F}_q$.

Om deze opspanningsvoorwaarde om te zetten in een computationeel hanteerbaar probleem, nemen de auteurs de volgende stappen:

• Zij kiezen een generator $\xi$ van $\mathbb{F}_{q^m}$ over $\mathbb{F}_q$.
• Zij vertalen de opspanningsvoorwaarde naar een stelsel expliciete lineaire vergelijkingen over $\mathbb{F}_q$.
• Zij maken gebruik van de Frobenius-automorfisme om deze stelsels te vergroten. Door Frobenius-geconjugeerden van de vergelijkingen toe te voegen, leiden zij een criterium af waarbij het bestaan van een oplossing in $\mathbb{F}_q^R$ een geldige symmetrische tensorenontbinding garandeert. Deze vergroting zorgt ervoor dat gevonden oplossingen vastgehouden worden door de Frobenius-afbeelding, en dus in het grondveld liggen.

Belangrijkste Bijdragen en Resultaten

1. Constructief Criterium: Het artikel biedt een noodzakelijke en voldoende voorwaarde voor $\mu_q^{\text{sym}}(m) \le R$ in termen van de oplosbaarheid van specifieke lineaire stelsels die machten van elementen in $\mathbb{F}_{q^m}$ en hun Frobenius-geconjugeerden omvatten (Stelling 3.2).
2. Expliciete Ontbindingen voor Kleine $m$: De auteurs passen hun criterium toe om expliciete symmetrische tensorenontbindingen te verkrijgen voor uitbreidingsgraden $m \in \{2, 3, 4\}$:
   • Geval $m=2$: Zij herstellen de bekende waarde $\mu_q^{\text{sym}}(2) = 3$ en bieden een expliciete ontbinding die drie spoorfuncties omvat, geldig voor elke $q$.
   • Geval $m=3$: Zij tonen aan dat $\mu_q^{\text{sym}}(3) \le 6$ voor alle $q$, met gelijkheid voor $q \in \{2, 3\}$. Voor $q \ge 4$ is de waarde 5. Zij bieden een methode om de vereiste elementen te vinden met behulp van het niet-verdwijnen van een specifieke determinantpolynoom.
   • Geval $m=4$: Met behulp van computationele verificatie (via MAGMA) bieden zij expliciete ontbindingen voor $q \in \{2, 3, 4, 5\}$. Zij herstellen optimale waarden voor $q=2$ ($\mu=9$), $q=4$ ($\mu=8$) en $q=5$ ($\mu=8$), en bieden een ontbinding van lengte 9 voor $q=3$.
3. Coderingstheoretische Interpretatie: De auteurs introduceren de symmetrische tensorrang van een symmetrische rang-metriek code, gedefinieerd als het minimum aantal rang-eenheid symmetrische matrices waarvan de $\mathbb{F}_q$-opspanning de code bevat. Zij tonen aan dat de eerste-slice-ruimte van de vermenigvuldigings-tensor equivalent is aan de een-dimensionale Gabidulin-code $G_1(m, q) = \langle x \rangle_{\mathbb{F}_{q^m}}$. Bijgevolg is $\mu_q^{\text{sym}}(m)$ exact de symmetrische tensorrang van deze specifieke Gabidulin-code.

Betekenis
Het artikel claimt betekenis door een constructieve en algoritmische aanpak te bieden voor symmetrische tensorenontbindingen, die verder gaat dan existentiebewijzen of grenzen die zijn afgeleid uit algebraïsche meetkunde. Door het probleem te herformuleren als een lineair algebraïsch probleem over eindige velden dat Frobenius-stabiele stelsels omvat, bieden de auteurs een praktische methode voor:

• Het verifiëren van kandidaat-ontbindingen.
• Het produceren van expliciete voorbeelden voor parameters waarvoor exacte waarden eerder onbekend waren of slechts begrensd waren.
• Het overbruggen van de kloof tussen tensorrangtheorie en rang-metriek coderingstheorie, specifiek door de symmetrische tensorrang van vermenigvuldiging te interpreteren als een invariant van symmetrische rang-metriek codes.

De auteurs merken op dat hoewel hun methode succesvol kleine uitbreidingsgraden behandelt, het bepalen van exacte waarden voor grotere $m$ en het vinden van uniforme families van elementen die voldoen aan de lineaire voorwaarden, open uitdagingen blijven. Het raamwerk wordt gepresenteerd als een hulpmiddel voor verder onderzoek naar de symmetrische bilineaire complexiteit van vermenigvuldiging in eindige velden.