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...
$\begingroup$
$\endgroup$
9
asked Oct 19, 2016 at 14:52
-
1$\begingroup$ gap-system.org/Manuals/doc/ref/chap39.html#X7E19F92284F6684E $\endgroup$– Francesco PolizziCommented Oct 19, 2016 at 15:24
-
1$\begingroup$ See in particular the section 39.5 Expressing Group Elements as Words in Generators $\endgroup$– Francesco PolizziCommented Oct 19, 2016 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 HoltCommented Oct 19, 2016 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 RivinCommented Oct 19, 2016 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 ♦Commented Oct 19, 2016 at 16:32
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
2
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).
answered Oct 21, 2016 at 10:05
Jan-Christoph Schlage-PuchtaJan-Christoph Schlage-Puchta
9,1772 gold badges30 silver badges56 bronze badges
-
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$ Commented Oct 21, 2016 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$ Commented Oct 21, 2016 at 11:42