Skip to main content
2 of 2
formatting, grammar and clarity corrections
Bill Thurston
  • 25.1k
  • 12
  • 99
  • 117

To elaborate on Sergei Ivanov's point with some futher observations:

By an argument similar to his, if you can obtain some element of any conjugacy class of bounded support with polynomial wordlength, the entire symmetric group has polynomial wordlength. That's because there are only polynomially many elements to the conjugacy class, and members of a fixed bounded conjugacy class generates the symmetric group in at most quadratic$(n)$ word length. (Transpositions require quadratic word length, using bubble sort. You can obtain a transposition in bounded wordlength once you have all elements of some conjugacy class). Furthermore, for fixed $k$, any $k$-tuple can be taken to any other $k$-tuple in polynomial$(n)$ word length, so a word that has polynomial length in terms of elements of the conjugacy class can be rewritten to have polynomial length in terms of the generators.

One strategy for trying to obtain elements of small support, given a few miscellaneous permutations, is to first take powers that halt some of their cycles. Once the support is small enough, you can take commutators of pairs of words whose support intersect only modestly to get still smaller support. These kinds of tricks make it hard to see how there could be counterexamples to the conjecture that the diameter of the group is a polynomial in n.

I think it would not be very hard to write a computer program that, given an arbitary generating set, would in practice produce a function $S_n \rightarrow $ polynomial-length word representative, because it shouldn't take many words to find permutations with reasonably arbitrary cycle shape. But it would be hard to prove it worked reliably.

I'd like to mention that there are well-known fast algorithms for analyzing the group generated by a collection of permutations, but they use recursive words, that is, words in words in words ... in generators, which gets around the group efficiently and quickly. Since permutation are easy to compose, the recursion is computationally cheap, and for many purposes, better than using words. (Actual experts should please elaborate or correct me if I'm mistaken).

Bill Thurston
  • 25.1k
  • 12
  • 99
  • 117