# What is the underlying algorithm for GroupElementToWord?

What algorithm is Mathematica 9 using for GroupElementToWord[group, g]?

-
interesting question and i've to say when it is up to group theory and especially to abstract algebra mathematica seems to be a construction place. here are some links for you: maths.usyd.edu.au/u/murray/research/essay.pdf demonstrations.wolfram.com/… i don't want to say that it lacks totally support for group theory, but it does feel not natural to deal with it in mathematica, which is strange, since of its magnificent support for symbolics... –  Stefan Jul 15 '13 at 23:14

The help page of GroupElementToWord shows that it has a Method option. The documentation for that option says that "GroupElementToWord uses the Minkwitz algorithm, with a number of parameters", and shows some examples on how changing those parameters can result in shorter words in the generators.

The Minkwitz algorithm (Torsten Minkwitz, 1998) is based on the construction of a table of coset representatives of the group stabilizers associated to a given base of the group. Constructing this table may take some time for large groups, but once the table is available it will be fast to factorize new elements of that group.

For example, generate some random group:

In[1]:= group = PermutationGroup[{RandomPermutation[10], RandomPermutation[40]}];
In[2]:= GroupOrder[group]
Out[2]= 26049952856435659486554583203840000000


Take a random element of that group and factorize it:

In[3]:= perm = RandomPermutation[group];
In[4]:= GroupElementToWord[group, perm]; // Timing
Out[4]= {1.179742, Null}


Now take another element of the same group and factorize it. This time the computation is faster:

In[5]:= perm = RandomPermutation[group];
In[6]:= GroupElementToWord[group, perm]; // Timing
Out[6]= {0.035460, Null}

-

I am just sharing my small idea here and someone can correct me if I am wrong somewhere. Computational group theory algorithms are used in mathematical software. Group is never stored as it is in any data structure and actually generated on the run using its generating sets.
Strong generating sets(not exactly simple generating sets) are generated using "Schreier–Sims algorithm" and after that most probably these are permuted together to see which combination generated the element.
I have written a small program to see how a group is generated from generating sets. Though it is exactly opposite to what you are asking but if you are beginner like me than it might be useful.

-
I don't believe that this answer deserved a downvote. Maybe it is not that germane to the question, but it is somewhat relevant and was provided in good faith. –  Oleksandr R. Jun 17 '14 at 12:27
I agree with @Oleksandr R. Moreover, one can always offset a downvote with an upvote.. –  Daniel Lichtblau Jun 17 '14 at 14:09