Symmetric Tensor Decompositions over Finite Fields

Résumé Technique : Décompositions de Tenseurs Symétriques sur les Corps Finis

Énoncé du Problème
L'article aborde le problème de la détermination du rang tensoriel symétrique de l'application de multiplication $M_{q^m}: \mathbb{F}_{q^m} \times \mathbb{F}_{q^m} \to \mathbb{F}_{q^m}$ sur les extensions de corps finis. Alors que la complexité bilinéaire standard $\mu_q(m)$ (le nombre minimum de multiplications non scalaires requises) est un sujet central en théorie de la complexité algébrique, le rang tensoriel symétrique $\mu_q^{\text{sym}}(m)$ impose une contrainte supplémentaire : les deux formes linéaires dans chaque terme de rang un de la décomposition doivent coïncider. Bien que $\mu_q^{\text{sym}}(m) \ge \mu_q(m) \ge 2m-1$, la détermination des valeurs exactes pour $\mu_q^{\text{sym}}(m)$ reste difficile en dehors de régimes spécifiques (par exemple, lorsque $q \ge 2m-2$). Les méthodes existantes reposent souvent sur la géométrie algébrique ou des constructions spécifiques, laissant un vide dans les approches constructives pour des paramètres généraux.

Méthodologie
Les auteurs développent un cadre constructif basé sur les polynômes linéarisés (également connus sous le nom de polynômes $q$). La méthodologie centrale repose sur l'établissement d'une correspondance préservant le rang entre trois objets mathématiques :

1. Polynômes linéarisés symétriques dans l'algèbre $L_{m,q}$.
2. Formes bilinéaires symétriques sur $\mathbb{F}_{q^m}$ sur $\mathbb{F}_q$, définies via la trace du corps $\text{Tr}_{q^m/q}(xy)$.
3. Matrices symétriques dans $\mathbb{F}_q^{m \times m}$.

Les auteurs identifient qu'une décomposition tensorielle symétrique de longueur $R$ correspond à l'existence de $R$ polynômes linéarisés symétriques de rang un qui engendrent l'espace des polynômes linéarisés représentant l'application de multiplication. Plus précisément, ils utilisent le résultat selon lequel les polynômes linéarisés symétriques de rang un prennent la forme $\alpha \text{Tr}_{q^m/q}(\beta x)$ où $\alpha/\beta \in \mathbb{F}_q$.

Pour transformer cette condition d'engendrement en un problème traitable computationnellement, les auteurs :

• Fixent un générateur $\xi$ de $\mathbb{F}_{q^m}$ sur $\mathbb{F}_q$.
• Traduisent la condition d'engendrement en un système d'équations linéaires explicites sur $\mathbb{F}_q$.
• Utilisent l'automorphisme de Frobenius pour élargir ces systèmes. En adjoint les conjugués de Frobenius des équations, ils dérivent un critère où l'existence d'une solution dans $\mathbb{F}_q^R$ garantit une décomposition tensorielle symétrique valide. Cet élargissement assure que les solutions trouvées sont fixes par l'application de Frobenius, et donc qu'elles appartiennent au corps de base.

Contributions et Résultats Clés

1. Critère Constructif : L'article fournit une condition nécessaire et suffisante pour $\mu_q^{\text{sym}}(m) \le R$ en termes de résolubilité de systèmes linéaires spécifiques impliquant des puissances d'éléments dans $\mathbb{F}_{q^m}$ et leurs conjugués de Frobenius (Théorème 3.2).
2. Décompositions Explicites pour de Petits $m$ : Les auteurs appliquent leur critère pour obtenir des décompositions tensorielles symétriques explicites pour les degrés d'extension $m \in \{2, 3, 4\}$ :
   • Cas $m=2$ : Ils retrouvent la valeur connue $\mu_q^{\text{sym}}(2) = 3$ et fournissent une décomposition explicite impliquant trois fonctions de trace, valable pour tout $q$.
   • Cas $m=3$ : Ils montrent que $\mu_q^{\text{sym}}(3) \le 6$ pour tout $q$, avec égalité pour $q \in \{2, 3\}$. Pour $q \ge 4$, la valeur est 5. Ils fournissent une méthode pour trouver les éléments requis en utilisant la non-annulation d'un polynôme déterminant spécifique.
   • Cas $m=4$ : En utilisant une vérification computationnelle (via MAGMA), ils fournissent des décompositions explicites pour $q \in \{2, 3, 4, 5\}$. Ils retrouvent les valeurs optimales pour $q=2$ ($\mu=9$), $q=4$ ($\mu=8$) et $q=5$ ($\mu=8$), et fournissent une décomposition de longueur 9 pour $q=3$.
3. Interprétation en Théorie des Codes : Les auteurs introduisent le rang tensoriel symétrique d'un code de rang métrique symétrique, défini comme le nombre minimum de matrices symétriques de rang un dont l'enveloppe $\mathbb{F}_q$ contient le code. Ils démontrent que l'espace de la première tranche du tenseur de multiplication est équivalent au code de Gabidulin unidimensionnel $G_1(m, q) = \langle x \rangle_{\mathbb{F}_{q^m}}$. Par conséquent, $\mu_q^{\text{sym}}(m)$ est exactement le rang tensoriel symétrique de ce code de Gabidulin spécifique.

Signification
L'article revendique une importance en fournissant une approche constructive et algorithmique aux décompositions de tenseurs symétriques, allant au-delà des preuves d'existence ou des bornes dérivées de la géométrie algébrique. En reformulant le problème comme un problème d'algèbre linéaire sur les corps finis impliquant des systèmes stables par Frobenius, les auteurs offrent une méthode pratique pour :

• Vérifier les décompositions candidates.
• Produire des exemples explicites pour des paramètres où les valeurs exactes étaient auparavant inconnues ou seulement bornées.
• Combler le fossé entre la théorie du rang tensoriel et la théorie du codage à métrique de rang, spécifiquement en interprétant le rang tensoriel symétrique de la multiplication comme un invariant des codes de rang métrique symétriques.

Les auteurs notent que si leur méthode gère avec succès les petits degrés d'extension, la détermination des valeurs exactes pour de plus grands $m$ et la recherche de familles uniformes d'éléments satisfaisant les conditions linéaires restent des défis ouverts. Le cadre est présenté comme un outil pour de nouvelles investigations sur la complexité bilinéaire symétrique de la multiplication dans les corps finis.