3
$\begingroup$

This is follow-up to my earlier question.

Suppose that we have elements $\sigma_1,\ldots,\sigma_k\in S_n$, and that we established that these elements actually generate $S_n$. Since that previous question, I learned that the Bratus-Pak algorithm for recognising symmetric groups actually also produces a way to express every element of $S_n$ as a word in sigmas.

However, in some specific applications I have in mind (where $n$ is about 60), the transpositions $(i,j)$ in $S_n$ are thus expressed as words of length about 800 in sigmas, and I have strong reasons to suspect that there are much shorter ways to represent them (shorter than 100). Are there some methods that are known [in practice] to produce reasonably short words in the word group in such situation?

EDIT: in principle, I can even reduce my problem a little bit, and ask just for a representatives in cosets of transpositions modulo $H$, where $H$ is some explicitly given subgroup of $S_n$. Maybe that could help.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I realize that you want tofind reasonably short words for elements of $S_n$ in a given generating set, but it is worth observing that, in many of the applications to computational group theory, we do not try to do that, partly because it is just too difficult. Instead, we write them as short straight line programs in the given generating set, which means that we can define new generators as short words in existing generators, and use them when writing elements as words in the generators. In some contexts, such as evaluating images of elements under homomorphisms, this is very effective. $\endgroup$
    – Derek Holt
    Commented Mar 26, 2018 at 13:01
  • $\begingroup$ @DerekHolt thank you for the comment! You certainly are one of people whose input on the matter is absolutely invaluable. Short SLPs are completely fine with me, and in fact the "length 800" claim in my post is rather the length of the corresponding SLPs (that I computed with Magma). My general issue is that everything that I can compute, within my very limited knowledge of the field, seems to be much longer than the "expected" length, and this worries me. $\endgroup$
    – Vladimir Dotsenko
    Commented Mar 26, 2018 at 15:58

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .