Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Enumerete elements of group

  1. Jan 13, 2010 #1
    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 cant find algorithm to enumerate all element of group ( 60 in this example ) based on generators.

    thanks for any help :)
     
  2. jcsd
  3. Jan 13, 2010 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Can you enumerate all strings of symbols consisting of the four letters a, b, c, and d?
     
  4. Jan 13, 2010 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  5. Jan 14, 2010 #4
    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook