Counting elements of a given length in a group via GAP

Question

I have a finitely presented group G in GAP, for example with the following generators and relations: generators = $[ f1, f2, f3, f4 ]$ relators = $[ 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: How can I count the number of elements G that have length equal to $i$ (which means that the element is a non-zero product in G of exactly $i$ generators $f_i$ in a minimal way)?

Answer 1

This cannot be done for finitely presented groups in general, because there are groups with undecidable word problems. But for possibly infinite finitely presented groups that are shortlex automatic or have complete rewriting systems, you can use the KBMAG package to do this.

Here is an easy example with an infinite Coxeter group.

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

You can use the function $\mathsf{EnumerateReducedWords}$ to list shortlex least representatives of group elements of specified length. So, for example,

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

tells us that there are 16 elements of lengths 0 to 3, and 9 elements of length exactly 4.

You can also compute the exact growth function of the group as a rational function.

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)

The coefficients $a_n$ of the Taylor series expansion $\sum_{n=0}^\infty a_nx^n$ of this would give the number of elements of length $n$, but I don't know whether GAP has a function to compute series expansions.

Answer 2

If your group is sufficiently small (as your example is), and you can convert into a permutation group, you can use 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 ]

So there are 4 elements of length 1, 9 of length 2, and so on.

If the group is much larger (so storing elemnts is hard) or even infinite, this is a much harder problem.