Efficient Enumeration of Elements in a Group Defined by Generators

[ethylparaben]

Here is my problem:

i have group defined by generators, like:

< a, b | a^2 = b^3 = (ab)^5 = 1 >.

eg. from http://for.mat.bham.ac.uk/atlas/v2.0/alt/A5/

i can't find algorithm to enumerate all element of group ( 60 in this example ) based on generators.

thanks for any help :)

 

[Hurkyl]

Can you enumerate all strings of symbols consisting of the four letters a, b, c, and d?

 

[Hurkyl]

Assuming you can...

Just replace c with b^-1 and d with a^-1, and now you have an enumeration containing every element in the group.

All you have to do now is to remove redundant copies. I suggest looking for a simplification algorithm.

 

[ethylparaben]

I'm sorry i don't get it.

Why i should add extra c and d letter if c = a^-1 = a and d = b^-1 = bb so i will get the same strings just by enumerate all strings of symbols consisting a and b ( i don't have problem with it)

next steep, as you wrote, should be remove redundant copies. I do it in two steps.

1. check if string consist substring equal to 1 ( 'aa' or 'bbb' or 'ababababab' )
2. check if string is identical to element: eg.

i got string 'babababab' and i know that a*a = 1 i replace one a by string to get a*babababab = ababababab = ab^5 = 1 so i know that 'babababab' = a

but still i get much more elements than i should get.