Algorithmes pour les représentations unitaires de groupes finis

Oct 22 2020

Donné un $d$-dimensionnelle $\mathbb C$-présentation linéaire d'un groupe fini $G$, ie $\pi \!: G \to \mathrm {GL}_d(\mathbb C)$, on peut utiliser l'astuce unitaire de Weyl pour construire un produit interne$\langle v, w\rangle_\mathrm U$ pour $v, w \in \mathbb C^d$sous lequel cette représentation est unitaire. Pour ce faire, on commence un produit intérieur arbitraire$\langle v, w\rangle_a$, comme le trivial $\langle v, w\rangle_1 = v^\dagger w$, et calcule $$ \langle v, w\rangle_\mathrm U = \frac 1 {|G|} \sum_{g \in G} \left \langle \pi (g) v, \pi(g) w \right \rangle_a. $$ Maintenant, $\forall g,\,v \! : \, \langle \pi(g) v, \pi(g) v\rangle_\mathrm U = \langle v, v\rangle_\mathrm U$.

Naïvement, évaluer un tel produit intérieur nécessite $O(d^3|G|)$multiplications, qui deviennent rapidement irréalisables pour des représentations non triviales de groupes intéressants. Quelqu'un peut-il suggérer un moyen d'utiliser la structure du groupe pour réduire$|G|$facteur de la complexité de cet algorithme? Alternativement, tout moyen efficace de calculer une représentation équivalente qui est unitaire sous le produit intérieur trivial$\langle v, w\rangle_1$, alors $\forall g \! : \, \pi(g) \in \mathrm U(d)$, répondrait également à mes besoins.

Réponses

2 OzoneNerd Oct 23 2020 at 05:12

Je déteste répondre à ma propre question moins de vingt-quatre heures après l'avoir publiée, mais j'ai trouvé une solution. Utilisation d'un petit nombre d'éléments de groupe$g_1, \ldots g_n \in G$ et la base orthornormale standard $\mathbf B = \left [ \mathbf e_j \in \mathbb C^d \! : \, j \in 1, \ldots, d \, \right ]$, on peut construire des contraintes sur un produit intérieur satisfaisant $ \left \langle \pi \! \left ( g_i \right ) \mathbf e_j, \pi \! \left ( g_i \right ) \mathbf e_k \right \rangle_\mathbf U = \left \langle \mathbf e_j, \mathbf e_k \right \rangle_\mathbf U$.

Dans mon cas de test, les deux générateurs non orthogonaux $g_1$ et $g_2$d' un 20 dimensions$\mathbb R$-présentation linéaire du $\mathrm M_{11}$un groupe sporadique (d'ordre deux et quatre, respectivement) était suffisant pour résoudre les éléments de matrice symétriques réels d'un produit intérieur satisfaisant, jusqu'à la normalisation.

De là, on peut effectuer un changement de base sur $\pi$à partir d'une base orthonormée ( par exemple construite en utilisant le processus de Gram – Schmidt) par rapport à$\langle v, w \rangle_\mathbf U$ à la base standard $\mathbf B$, qui est orthonormé par rapport au produit intérieur trivial $\langle v, w \rangle_1 $, pour obtenir une représentation qui est dans $\mathbf U(d)$.

Mettre à jour:$\:$ Le rang des contraintes de $g_1$ seul est de 96, tandis que celui de $g_2$ est 154. Ensemble, ils obtiennent 209 des $210 = d(d + 1)/2$ éléments de matrice indépendants du produit intérieur unitaire, ne laissant que la normalisation non fixée.

Mise à jour 2:$\:$ De mon "simple" $\mathrm M_{11} \! \to \mathrm{SL}_{20}(\mathbb R)$cas de test, il semble que les rangs des contraintes soient une fonction de la classe de conjugaison de l'élément. J'ai calculé:

  • $\hphantom{1} 1A \hphantom{/B} : \: \: \hphantom{00} 0$
  • $\hphantom{1} 2A \hphantom{/B} : \: \: \hphantom{0} 96$
  • $\hphantom{1} 3A \hphantom{/B} : \: \: 138$
  • $\hphantom{1} 4A \hphantom{/B} : \: \: 154$
  • $\hphantom{1} 5A \hphantom{/B} : \: \: 168$
  • $\hphantom{1} 6A \hphantom{/B} : \: \: 170$
  • $\hphantom{1} 8A/B : \: \: 182$
  • $11A/B : \: \: 190$

J'étais malheureusement incapable de relier ces valeurs à la table de caractères de manière significative, bien qu'elles semblent être une "fonction de classe" quelque peu intéressante, quoique dépendante de la représentation, au sens de la théorie des groupes.

Mise à jour 3:$\:$ Ma méthode prend environ une minute pour que les représentations $\mathrm {GL}_{77} (\mathbb Z)$. En attendant, pour un 77 dimensions, absolument irréductible,$\mathbb Z$-présentation linéaire du groupe simple sporadique, paria, fini$\mathrm J_1$, Magma's InvariantForms trouve un produit interne valide dans$80\,\mathrm {ms}$. Comme leur logiciel est de source fermée, je ne sais pas quel algorithme ils utilisent. Je vais devoir faire plus de recherches sur les formes invariantes. J'ai également contacté les développeurs de Magma pour une raison essentiellement indépendante, mais j'ai inclus une question secondaire demandant comment la InvariantFormsfonction fonctionne.

Tout autre aperçu serait apprécié.