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?
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.
sciencedirect.com is broken, but the article can be found at doi:10.1016/0097-3165(88)90033-7 (Zbl 0649.20002).
$\endgroup$
Commented
May 13, 2023 at 15:57
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).
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.
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.
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.
