<p>The answer is yes, we can improve the upper bound to $\mathrm{e}^{(1 + o(1))\sqrt{n\ln n}}$. It was proved in a more recent <a href="http://dl.acm.org/citation.cfm?id=1109557.1109648">paper</a> of Babai (Corollary 2.9).</p>

CC BY-SA 3.0
2014-11-29T10:42:48.777Z
2014-11-29T10:42:48.777Z
Pavel Panteleev
<p>Babai and Seress <a href="http://www.sciencedirect.com/science/article/pii/S0195669805800290" rel="nofollow noreferrer">proved</a> that given a subgroup $G \leq S_n$ and a generating set $S$ of $G$, any permutation in $G$ can be written as a product of generators and their inverses of length $e^{(1+o(1))\sqrt{n\log n}}$. This bound is optimal since $S_n$ has an element of order $e^{(1+o(1))\sqrt{n\log n}}$.</p>

<p>The classical fact that every element in $S_n$ has order at most $e^{(1+o(1))\sqrt{n\log n}}$, combined with the result of Babai and Seress, shows that given a subgroup $G \leq S_n$ and a generating set $S$ of $G$, any permutation in $G$ can be written as a product of generators of length at most $e^{2(1+o(1))\sqrt{n\log n}}$.</p>

<blockquote>
  <p>Can we improve the upper bound $e^{2(1+o(1))\sqrt{n\log n}}$ to $e^{(1+o(1))\sqrt{n\log n}}$?</p>
</blockquote>

<p>This question has been inspired by the recent question <a href="https://cstheory.stackexchange.com/questions/27072/automata-and-a-kind-of-pumping-lemma-on-state-transition-function">Automata and a kind of pumping lemma on state transition function</a>.</p>

<gr.group-theory>
Diameter of Cayley graphs of subgroups of $S_n$ without inverses
Yuval Filmus
# Diameter of Cayley graphs of subgroups of $S_n$ without inverses

(Asked by: username_0 on 2014-10-16)

Babai and Seress [proved](http://www.sciencedirect.com/science/article/pii/S0195669805800290) that given a subgroup $G \leq S\_n$ and a generating set $S$ of $G$, any permutation in $G$ can be written as a product of generators and their inverses of length $e^{(1+o(1))\sqrt{n\log n}}$. This bound is optimal since $S\_n$ has an element of order $e^{(1+o(1))\sqrt{n\log n}}$.

The classical fact that every element in $S\_n$ has order at most $e^{(1+o(1))\sqrt{n\log n}}$, combined with the result of Babai and Seress, shows that given a subgroup $G \leq S\_n$ and a generating set $S$ of $G$, any permutation in $G$ can be written as a product of generators of length at most $e^{2(1+o(1))\sqrt{n\log n}}$.

> Can we improve the upper bound $e^{2(1+o(1))\sqrt{n\log n}}$ to $e^{(1+o(1))\sqrt{n\log n}}$?

This question has been inspired by the recent question [Automata and a kind of pumping lemma on state transition function](https://cstheory.stackexchange.com/questions/27072/automata-and-a-kind-of-pumping-lemma-on-state-transition-function).

**Tags:** gr.group-theory


---

## 1 answers

### Answer by username_1 on 2014-11-29. Score: 7 | Accepted answer

The answer is yes, we can improve the upper bound to $\mathrm{e}^{(1 + o(1))\sqrt{n\ln n}}$. It was proved in a more recent [paper](http://dl.acm.org/citation.cfm?id=1109557.1109648) of Babai (Corollary 2.9).


---

