Efficient Enumeration of Elements in a Group Defined by Generators

  • Thread starter Thread starter ethylparaben
  • Start date Start date
  • Tags Tags
    Elements Group
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
3 replies · 2K views
ethylparaben
Messages
2
Reaction score
0
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 :)
 

Discussion

Physics news on Phys.org
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.
 
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.