15
$\begingroup$

Let $G = S_n$ (the permutation group on $n$ elements). Let $A\subset G$ such that $A$ generates $G$.

Is there an $n$-cycle $g$ in $G$ that can be expressed as

$g = a_1 a_2 ... a_k$

where $a_i\in A \cup A^{-1}$ and $k\leq c_1 n^{c_2}$, where $c_1$ and $c_2$ are constants?

What about $2$-cycles, or elements of any other particular form?

$\endgroup$
7
  • $\begingroup$ @David Eppstein,@H A Helfgott, mea culpa. I misread the question and thus answered the wrong question. I can either edit away my answer or delete it. I've voted to delete it since I answered the wrong question. $\endgroup$ Sep 8, 2010 at 3:31
  • 3
    $\begingroup$ Just to clarify, even though this should be clear: your question really is "are there constants $c_1$ and $c_2$ such that for all $n$, whenever $A$ generates $S_n$, then there is an $n$-cycles that is a product of no more than $c_1n^{c_2}$ elements of $A\cup A^{-1}$, right? $\endgroup$ Sep 8, 2010 at 8:48
  • $\begingroup$ Can't you use Schreirer-Sims to construct a generating set then use a modification of the membership test to construct the product of strong generators and show that the number of strong generators is polynomial in the size of n? The number of strong generators needed by Schreirer-Sims is quadratic in n. At worst you can write out each original permutation as the product of your strong generators...all guaranteeing a polynomial product length...Am I mis interpreting the problem? $\endgroup$ Sep 8, 2010 at 17:27
  • $\begingroup$ @Stefan Geschke: yes. $\endgroup$ Sep 9, 2010 at 3:14
  • $\begingroup$ @dorkusmonkey: Let me turn your last sentence backwards, and ask a question - are the strong generators constructed by this algorithm given by products of elements of $A\cup A^{-1}$ of length at most $O(n^c)$? If yes, this is very good - if not, your comment seems a bit hard to use. $\endgroup$ Sep 9, 2010 at 4:20

5 Answers 5

9
$\begingroup$

That all elements in a symmetric group with a specified arbitrary generating set can be reached in a polynomial amount of steps is a known open problem, and has been investigated for some time now. This long-standing conjecture has been proven for most choices of generating sets. Heuristically one expects this to be true for the reasons mentioned by Colin Reid above. That is, if certain conjectures are true, then every Cayley graph has a Hamiltonian cycle and so is expected to have exponentially many such cycles. So one expects to be able to reach any element of the group pretty fast.

For the symmetric group the problem of determining tight bounds on the diameter of its Cayley graph has been studied (and partially resolved) by L. Babai and coauthors. In the paper "On the diameter of cayley graphs of the symmetric group" it is proved that one can reach any elements using words of length at most $e^{\sqrt{n\log n}(1+o(1))}$ for any generating set, while the optimal bound should be $O(n^{c})$. Here and here more partial results are proved, showing evidence that polynomial bounds are in fact the true asymptotic. I will remark again that one expects this behavior for all nonabelian finite simple groups too.

These papers are a good survey of what is currently known about this problem, I don't know if restricting your target to specific conjugacy classes of elements (such as n-cycles) makes the problem easier so I will think about it a bit more.

$\endgroup$
1
7
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ "Words in words in ..." are called "straight line programs" to the algorithmic folks, and yes they are used quite a bit. Actual words take a long time to multiply (in the free group, on a computer), just because word lengths get large (exponentially large when using the standard computational algorithms for permutation groups). However, to multiply the 3rd word by the 4th word, you just write down [3,4] in a straight line program, eliminating concerns about word length. Unfortunately, this also means many algorithms used in practice produce exponentially long words. $\endgroup$ Sep 12, 2010 at 14:51
  • $\begingroup$ The argument that "you can take commutators of pairs of words whose support intersects only modestly ... " is the heart of the proof by Babai, Beals and Seress (paper referred to above by Zaimi) that if there is any element in the generating set with support of size less than n/3 then the diameter of the Cayley graph is polynomially bounded. So, as you say, it seems difficult to imagine how there could be counterexamples, but I can't see any strategy to prove it. $\endgroup$ Sep 14, 2010 at 10:50
5
$\begingroup$

Concerning the second question (about 2-cycles). If some transposition (= 2-cycle) can be obtained as as a product of a polynomial number of generators (= elements of $A\cup A^{-1}$), then all elements of the symmetric group can be obtained this way. Thus the question is equivalent to the open problem that Gjergji Zaimi mentioned in his answer.

The proof follows the suggestion that jp made in his comment to Roland Bacher's answer. Suppose that some transposition is a product of $N$ generators. All transpositions are conjugate to this one, and since there are only $n(n-1)/2$ of them, each can be reached by at most $n(n-1)/2$ conjugations by generators. Hence every transposition is a product of at most $N+n(n-1)$ generators. It remains to recall that every permutation is a product of at most $n-1$ transpositions.

$\endgroup$
3
$\begingroup$

A partial answer for transpositions:

If $A$ contains a generating set given by transpositions, there is an $n-$cycle given by the product of $n-1$ generators. Indeed, consider the graph $G$ with vertices $1,\dots,n$ and edges defined by all transpositions in the generating set $A$. The subset of transpositions in $A$ generates $S_n$ if and only if $G$ is a connected graph. Up to throwing away a few generators, we can thus assume that $G$ is a tree. Drawing this tree in the plane and choosing an initial leaf of $G$, we consider the product of all transpositions corresponding to the order in which we encounter the edges of $G$ when walking around $G$ in counterclockwise order. This defines the $n-$cycle obtained by writing down all vertices of $G$ accordingly to their last sighting during the walk.

$\endgroup$
1
  • $\begingroup$ Can you maybe extend your answer to the case that A contains one transposition by looking at its conjugates that can be obtained by conjugating with short products? $\endgroup$
    – j.p.
    Sep 10, 2010 at 8:51
3
$\begingroup$

This is not really an answer so much as some vague thoughts on the matter, but it's a bit long for a comment.

The $n$-cycle case seems particularly promising as the $n$-cycles are so numerous: a random element of $S_n$ is an $n$-cycle with probability $1/n$. So it would be enough to show that $n$-cycles are sufficiently 'evenly distributed' in any Cayley graph that we can never be too far from one.

Here's a vague idea:

Suppose the Cayley graph has a collection of $n$-cycles of size $f(n)$ which are clumped together, that is, all a short distance $2r$ from each other ($r$ is allowed to be polynomial in $n$). Then perhaps one can show that there are two $n$-cycles $x$ and $y$ in or close to this clump such that $xy^{-1}$ is an $n$-cycle, as long as we can break out of some special situations, such as our clump being contained in a coset of a subgroup that has no $n$-cycles.

Suppose there are no such clumps. Then if we draw discs of radius $r$ around every $n$-cycle, then any given vertex cannot be contained in too many discs (as otherwise it would be in the middle of a clump). It follows that each disc has area at most $nf(n)$. To get a contradiction here we have to prove something about word growth, in order to show that the discs cannot have such a small area.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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