10
$\begingroup$

Babai and Seress proved 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.

$\endgroup$
7
$\begingroup$

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 of Babai (Corollary 2.9).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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