4
$\begingroup$

Suppose I have $G < S_n,$ with generators $g_1, \dots, g_k,$ and I have some $g\in G.$ I want to write $g$ as a word in the generators. How hard is this, computationally? And is there a simple algorithm someone can point me to? I assume Gap and Magma have this built in...

$\endgroup$
  • 1
    $\begingroup$ gap-system.org/Manuals/doc/ref/chap39.html#X7E19F92284F6684E $\endgroup$ – Francesco Polizzi Oct 19 '16 at 15:24
  • 1
    $\begingroup$ See in particular the section 39.5 Expressing Group Elements as Words in Generators $\endgroup$ – Francesco Polizzi Oct 19 '16 at 15:24
  • $\begingroup$ It is a difficult problem in general, if you are looking for a word that is close to being of shortest possible length. The Rubik cube group is a notoriously hard example to solve completely. For many applications, a straight line program for the group element is good enough and that can be found efficienjtly. More precisely, you can extend the given set of generators to a set of strong generators, and use those for your word. $\endgroup$ – Derek Holt Oct 19 '16 at 15:27
  • $\begingroup$ @DerekHolt I don't really care about the "shortest" aspect. Is the straight line program algorithm in your book? $\endgroup$ – Igor Rivin Oct 19 '16 at 15:33
  • $\begingroup$ The Schreier-Sims algorithm and the like are explained in detail in the Handbook of Computational Group Theory. -- I think this is what you need, isn't it? $\endgroup$ – Stefan Kohl Oct 19 '16 at 16:32
5
$\begingroup$

In general the problem is very difficult. There has been quite some work on the diameter of the Cayleygraph of $S_n$, the best results being due to Helfgott-Seress for the general case, and Helfgott-Seress-Zuk for the random case. However, as far as I know these proofs are non-constructive in the sense that they only show the existence of a word of small length, but do not give an algorithm to find this word.

One approach that sometimes works is to generate short words in the given generators, until you find a word you understand so well that the representation problem becomes trivial. For example, suppose you can find an element which contains a single 2-cycle and no other cycle of even length. Taking powers you get an explicit description of a transposition. Then you construct a 2-transitive subset, and get a representation for any transposition. Finally write the element $g$ as a product of transpositions.

Bratus and Pak (J. Symbolic Comput. 29 (2000), 33-57) used this approach to give a fast randomized algorithm to find an isomorphism between a black box group and $S_n$. I used it to give an algorithm which for almost all $\pi, \sigma$ finds in polynomial running time a word of length $O(n^3\log n)$ representing any given $g$ ( Combinatorica 32 (2012), 309–323).

$\endgroup$
  • 1
    $\begingroup$ Appendix B of Helfgott-Seress-Zuk sketches out how to convert the main theorem of the paper into an algorithm: arxiv.org/pdf/1311.6742.pdf $\endgroup$ – Nick Gill Oct 21 '16 at 11:35
  • $\begingroup$ Ah, I only looked at the "construction of small cycles" part. So "As far as I know" was not that far. $\endgroup$ – Jan-Christoph Schlage-Puchta Oct 21 '16 at 11:42

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.