Skip to main content
MathOverflow

Return to Question

added 218 characters in body
Source Link
Vladimir Dotsenko
Vladimir Dotsenko
  • 16.9k
  • 1
  • 55
  • 114

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.

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?

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.

Source Link
Vladimir Dotsenko
Vladimir Dotsenko
  • 16.9k
  • 1
  • 55
  • 114

working with symmetric groups presented via nonstandard generators

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?