Say we have a finite group $G$ generated by $g_1,\cdots,g_n$. Are there any algorithms or techniques to write any element $g$ as a product of these generators?

Ofcourse we could just try all combinations, but I hope there are more elegant ways, like in a vector space, you can just project your element on the generators.

I'm asking because this is the group theoretic generalisation of solving a Rubik's cube. By labeling the stickers with natural numbers, we see that moves are permutations, and every legal position is one too. The Rubik's cube group is then the group that is generated by the legal moves:

$$G=<R,L,U,D,F,B>$$ In standard notation

To solve the cube is the same as to write an element of this group as a product of these generators, so in this case there are many algorithms to do this.

What algorithms exist for the general case?

  • $\begingroup$ Algorithms need inputs. How would you input an element of $G$? $\endgroup$ – Lee Mosher Mar 18 '16 at 2:03
  • $\begingroup$ for example, the disjoint cycle decomposition $\endgroup$ – Jens Renders Mar 18 '16 at 2:05
  • $\begingroup$ Are you assuming that $G$ is a group of permutations of something? $\endgroup$ – Lee Mosher Mar 18 '16 at 2:06
  • $\begingroup$ every group is isomorfic to a group of permutations, also every group is isomorfic to a group of matrices, which could also be a nice input format... $\endgroup$ – Jens Renders Mar 18 '16 at 2:08
  • 1
    $\begingroup$ You can do this efficiently if you extend the initial generating set to a strong generating set. If you then rewrite in terms of the original generators, you might end up with a very long word. Thegeneral problem of expressing an element as a short word in the given generators is diffficult (as you can judge from the difficulty of the Rubik Cube problem). Fortunately, for may computational applications it is not necessary to do this. $\endgroup$ – Derek Holt Mar 18 '16 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.