Comptage d'éléments d'une longueur donnée dans un groupe via GAP

Question

J'ai un groupe G de présentation finie dans GAP, par exemple avec les générateurs et relations suivants: générateurs = $[ f1, f2, f3, f4 ]$ relateurs = $[ f1^2, f2^2, f3^2, f4^2, (f3*f2)^2, (f2*f1)^3, (f1*f4)^3, (f3*f1)^3, (f4*f3)^3, (f2*f4)^3 ]$

Question: Comment puis-je compter le nombre d'éléments G qui ont une longueur égale à $i$ (ce qui signifie que l'élément est un produit non nul dans G d'exactement $i$ générateurs $f_i$ de manière minimale)?

Answer 1

Cela ne peut pas être fait pour les groupes à présentation finie en général, car il existe des groupes avec des problèmes de mots indécidables. Mais pour des groupes éventuellement infinis à présentation finie qui sont automatiques en shortlex ou qui ont des systèmes de réécriture complets, vous pouvez utiliser le package KBMAG pour ce faire.

Voici un exemple simple avec un groupe Coxeter infini.

gap> LoadPackage("kbmag");
true
gap> F := FreeGroup(3);;
gap> G := F/[F.1^2, F.2^2, F.3^2, (F.1*F.2)^2, (F.1*F.3)^3, (F.2*F.3)^7];;
gap> R := KBMAGRewritingSystem(G);;
gap> A := AutomaticStructure(R);;

Vous pouvez utiliser la fonction $\mathsf{EnumerateReducedWords}$pour lister le shortlex le moins représentatif des éléments du groupe de longueur spécifiée Ainsi, par exemple,

gap> Length(EnumerateReducedWords(R,0,3));
16
gap> Length(EnumerateReducedWords(R,4,4));
9

nous dit qu'il y a 16 éléments de longueurs 0 à 3 et 9 éléments de longueur exactement 4.

Vous pouvez également calculer la fonction de croissance exacte du groupe en tant que fonction rationnelle.

gap> GrowthFunction(R);
(x_1^10+4*x_1^9+8*x_1^8+11*x_1^7+12*x_1^6+12*x_1^5+12*x_1^4+11*x_1^3+8*x_1^2+4\
*x_1+1)/(x_1^10+x_1^9-x_1^7-x_1^6-x_1^5-x_1^4-x_1^3+x_1+1)

Les coefficients $a_n$ de l'extension de la série Taylor $\sum_{n=0}^\infty a_nx^n$ de cela donnerait le nombre d'éléments de longueur $n$, mais je ne sais pas si GAP a une fonction pour calculer les extensions de séries.

Answer 2

Si votre groupe est suffisamment petit (comme dans votre exemple) et que vous pouvez le convertir en groupe de permutation, vous pouvez utiliser GrowthFunctionOfGroup:

gap> p:=Image(IsomorphismPermGroup(G));
Group([ (2,3)(4,5)(6,8), (1,2)(5,7)(8,9), (2,4)(3,5)(9,10), (4,6)(5,8)(7,9) ])
gap> GrowthFunctionOfGroup(p);
[ 1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1 ]

Il y a donc 4 éléments de longueur 1, 9 de longueur 2, et ainsi de suite.

Si le groupe est beaucoup plus grand (le stockage des éléments est donc difficile) ou même infini, c'est un problème beaucoup plus difficile.