Generating words in a finitely presented group in SAGE

Question

I'm trying to get a list of all words of length $n$ (in the word metric sense) in some finitely presented group. I have tried some very naive enumerations but it is very slow. Is there an efficient way of doing this?

Answer 1

It might be too naive, but you can iterate on the elements of the free group, then use these elements to compute a representative in the group. It works decently well on the example I picked from GAP documentation, but it is certainly not perfect. If you give a more concrete example of a group you're looking at this can certainly be optimized.

m1 := [ [ Z(3)^0, Z(3)^0,   Z(3) ],
        [   Z(3), 0*Z(3),   Z(3) ],
        [ 0*Z(3),   Z(3), 0*Z(3) ] ];;
m2 := [ [   Z(3),   Z(3), Z(3)^0 ],
        [   Z(3), 0*Z(3),   Z(3) ],
        [ Z(3)^0, 0*Z(3),   Z(3) ] ];;
G := Group( m1, m2 );


hom:=EpimorphismFromFreeGroup(G:names:=["a", "b"]);;


PreImagesRepresentative( hom, m1*m2^(-1) );

iter := Iterator(G);
##test if we iterate directly on the matrix group, not very efficient


F2:=FreeGroup("a","b");

iterF2 := Iterator(F2);
##iterator on the free group, used to get the reduced words


toMatrixGp:=function(gen,w)
##computes the element in G via a->m1 and b->m2
    local temp;
    x:=gen[1]^0;
    for i in [1..NumberSyllables(w)] do

            temp:=(gen[GeneratorSyllable(w,i)]^(ExponentSyllable(w,i)));
        x:=x*temp;  


    od;

    return x;
end;



elmtSet:=Set([]);
##set of all different elements 
for i in [1..1000] do
    w:=UnderlyingElement(NextIterator(iterF2));
    g:=toMatrixGp(gen,w);
    elmt:=(PreImagesRepresentative( hom, g ));
    Print(elmt,"\n");
    AddSet(elmtSet,elmt);
od;