Symmetric Tensor Decompositions over Finite Fields

Sintesi Tecnica: Decomposizioni di Tensori Simmetrici su Campi Finiti

Enunciato del Problema
Il lavoro affronta il problema di determinare il rango tensoriale simmetrico della mappatura di moltiplicazione $M_{q^m}: \mathbb{F}_{q^m} \times \mathbb{F}_{q^m} \to \mathbb{F}_{q^m}$ su estensioni di campi finiti. Mentre la complessità bilineare standard $\mu_q(m)$ (il numero minimo di moltiplicazioni non scalari richieste) è un argomento centrale nella teoria della complessità algebrica, il rango tensoriale simmetrico $\mu_q^{\text{sym}}(m)$ impone un vincolo aggiuntivo: le due forme lineari in ciascun sommando di rango uno della decomposizione devono coincidere. Sebbene $\mu_q^{\text{sym}}(m) \ge \mu_q(m) \ge 2m-1$, determinare i valori esatti per $\mu_q^{\text{sym}}(m)$ rimane difficile al di fuori di regimi specifici (ad esempio, quando $q \ge 2m-2$). I metodi esistenti si basano spesso sulla geometria algebrica o su costruzioni specifiche, lasciando un vuoto negli approcci costruttivi per parametri generali.

Metodologia
Gli autori sviluppano un quadro costruttivo basato sui polinomi linearizzati (noti anche come polinomi $q$). La metodologia fondamentale si basa sull'istituzione di una corrispondenza che preserva il rango tra tre oggetti matematici:

1. Polinomi linearizzati simmetrici nell'algebra $L_{m,q}$.
2. Forme bilineari simmetriche su $\mathbb{F}_{q^m}$ su $\mathbb{F}_q$, definite tramite la traccia di campo $\text{Tr}_{q^m/q}(xy)$.
3. Matrici simmetriche in $\mathbb{F}_q^{m \times m}$.

Gli autori identificano che una decomposizione tensoriale simmetrica di lunghezza $R$ corrisponde all'esistenza di $R$ polinomi linearizzati simmetrici di rango uno che generano lo spazio dei polinomi linearizzati che rappresentano la mappatura di moltiplicazione. Nello specifico, essi utilizzano il risultato secondo cui i polinomi linearizzati simmetrici di rango uno assumono la forma $\alpha \text{Tr}_{q^m/q}(\beta x)$ dove $\alpha/\beta \in \mathbb{F}_q$.

Per trasformare questa condizione di generazione in un problema computazionalmente trattabile, gli autori:

• Fissano un generatore $\xi$ di $\mathbb{F}_{q^m}$ su $\mathbb{F}_q$.
• Traducono la condizione di generazione in un sistema di equazioni lineari esplicite su $\mathbb{F}_q$.
• Impiegano l'automorfismo di Frobenius per ingrandire questi sistemi. Aggiungendo i coniugati di Frobenius delle equazioni, derivano un criterio in cui l'esistenza di una soluzione in $\mathbb{F}_q^R$ garantisce una decomposizione tensoriale simmetrica valida. Questo ingrandimento assicura che le soluzioni trovate siano fissate dalla mappa di Frobenius, risiedendo così nel campo base.

Contributi e Risultati Chiave

1. Criterio Costruttivo: Il lavoro fornisce una condizione necessaria e sufficiente per $\mu_q^{\text{sym}}(m) \le R$ in termini della risolubilità di specifici sistemi lineari che coinvolgono potenze di elementi in $\mathbb{F}_{q^m}$ e i loro coniugati di Frobenius (Teorema 3.2).
2. Decomposizioni Esplicite per Piccoli $m$: Gli autori applicano il loro criterio per ottenere decomposizioni tensoriali simmetriche esplicite per gradi di estensione $m \in \{2, 3, 4\}$:
   • Caso $m=2$: Ripristinano il valore noto $\mu_q^{\text{sym}}(2) = 3$ e forniscono una decomposizione esplicita che coinvolge tre funzioni traccia, valida per qualsiasi $q$.
   • Caso $m=3$: Dimostrano che $\mu_q^{\text{sym}}(3) \le 6$ per ogni $q$, con uguaglianza per $q \in \{2, 3\}$. Per $q \ge 4$, il valore è 5. Forniscono un metodo per trovare gli elementi richiesti utilizzando la non nullità di un polinomio determinante specifico.
   • Caso $m=4$: Utilizzando la verifica computazionale (tramite MAGMA), forniscono decomposizioni esplicite per $q \in \{2, 3, 4, 5\}$. Ripristinano i valori ottimali per $q=2$ ($\mu=9$), $q=4$ ($\mu=8$) e $q=5$ ($\mu=8$), e forniscono una decomposizione di lunghezza 9 per $q=3$.
3. Interpretazione nella Teoria dei Codici: Gli autori introducono il rango tensoriale simmetrico di un codice simmetrico a metrica di rango, definito come il numero minimo di matrici simmetriche di rango uno il cui $\mathbb{F}_q$-span contiene il codice. Dimostrano che lo spazio della prima fetta del tensore di moltiplicazione è equivalente al codice di Gabidulin unidimensionale $G_1(m, q) = \langle x \rangle_{\mathbb{F}_{q^m}}$. Di conseguenza, $\mu_q^{\text{sym}}(m)$ è esattamente il rango tensoriale simmetrico di questo specifico codice di Gabidulin.

Significato
Il lavoro rivendica importanza nel fornire un approccio costruttivo e algoritmico alle decomposizioni tensoriali simmetriche, andando oltre le prove di esistenza o i limiti derivati dalla geometria algebrica. Riformulando il problema come un problema di algebra lineare su campi finiti che coinvolge sistemi stabili rispetto a Frobenius, gli autori offrono un metodo pratico per:

• Verificare le decomposizioni candidate.
• Produrre esempi espliciti per parametri in cui i valori esatti erano precedentemente sconosciuti o solo limitati.
• Colmare il divario tra la teoria del rango tensoriale e la teoria dei codici a metrica di rango, in particolare interpretando il rango tensoriale simmetrico della moltiplicazione come un invariante dei codici simmetrici a metrica di rango.

Gli autori notano che, sebbene il loro metodo gestisca con successo piccoli gradi di estensione, determinare i valori esatti per $m$ più grandi e trovare famiglie uniformi di elementi che soddisfano le condizioni lineari rimangono sfide aperte. Il quadro è presentato come uno strumento per ulteriori indagini sulla complessità bilineare simmetrica della moltiplicazione in campi finiti.