Let $A$ be a set of generators of $S\_n$, or of a doubly transitive
subgroup of $S\_n$. Assume $e\in A$, $A=A^{-1}$. What is the least $k$
such that $A^k$ is doubly transitive as a set? That is, what is the least $k$ such that there is a pair $x = (i,j)$, $i,j\in \{1,\dotsc,n\}$, $i\ne j$, for which $A^k x$ is
the set of all pairs of distinct elements of $\{1,2,\dotsc, n\}$?


The bound $k = O(n^2)$ is very easy. Can we prove $k =
O(n \log n)$? $k = O(n)$? As a starting exercise, can we at least
prove $k = O(n^{3/2})$?


Alternatively, can one construct a counterexample to $k=O(n)$? (Note the classical example $A = \{(1 2), (1 2 \dotsc n)\}$ is not a counterexample.)



How many steps are required for double transitivity?
It seems that this is a lower bound of $\Omega(n^2)$.


Take an $n$ and an $a=\Theta( n) $ coprime with $n$ (with $a<n/2$). Then the permutations $\sigma=(12\dots n) $ and $\tau=(1, a+1) $ generate $S\_n$.


On the other hand, all residues modulo $n$ form a cycle where the neighbors differ by $a$. The only way to change this cyclic order is to apply $\tau$. If you need to shift a residue several times along the cycle, you need to apply $\sigma^a$ between $\tau$'s. You may need to perform $\Theta(n) $ such shifts, hence the bound. 


