Contar elementos de una longitud determinada en un grupo a través de GAP

Question

Tengo un grupo G presentado finitamente en GAP, por ejemplo con los siguientes generadores y relaciones: generators = $[ f1, f2, f3, f4 ]$ relatores = $[ 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 ]$

Pregunta: ¿Cómo puedo contar el número de elementos G que tienen una longitud igual a $i$ (lo que significa que el elemento es un producto distinto de cero en G de exactamente $i$ generadores $f_i$ de forma mínima)?

Answer 1

En general, esto no se puede hacer para grupos presentados de manera finita, porque hay grupos con problemas de palabras indecidibles. Pero para grupos posiblemente infinitos presentados de forma finita que sean automáticos shortlex o tengan sistemas de reescritura completos, puede usar el paquete KBMAG para hacer esto.

Aquí hay un ejemplo sencillo con un grupo Coxeter infinito.

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);;

Puedes usar la función $\mathsf{EnumerateReducedWords}$para enumerar shortlex menos representantes de elementos de grupo de longitud especificada. Así por ejemplo,

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

nos dice que hay 16 elementos de longitud 0 a 3, y 9 elementos de longitud exactamente 4.

También puede calcular la función de crecimiento exacta del grupo como una función racional.

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)

Los coeficientes $a_n$ de la expansión de la serie Taylor $\sum_{n=0}^\infty a_nx^n$ de esto daría el número de elementos de longitud $n$, pero no sé si GAP tiene una función para calcular expansiones en serie.

Answer 2

Si su grupo es lo suficientemente pequeño (como es su ejemplo), y puede convertirlo en un grupo de permutación, puede usar 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 ]

Entonces hay 4 elementos de longitud 1, 9 de longitud 2, etc.

Si el grupo es mucho más grande (por lo que almacenar elementos es difícil) o incluso infinito, este es un problema mucho más difícil.