# How many steps are required for double transitivity?

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

• Do you have any figures for k generating the whole subgroup, or all of S_n? If you imagine a chain of subgroups, shouldn't there be bounds based on the size of the chain members? As a wild guess, I will say the sum of the indices of each group inside the next largest member in the chain is a weak upper bound. Gerhard "Weak Guesses Can Be Wild" Paseman, 2019.12.30. – Gerhard Paseman Dec 30 '19 at 19:03
• AFAIK the best bounds for $k$ such that $A^k = S_n$ (assuming $\langle A\rangle = S_n$) are still those in my 2014 Annals paper with A. Seress, namely, $k\ll \exp((\log n)^{4+o(1)})$. – H A Helfgott Dec 30 '19 at 19:08
• And yes, if you want a bound for $k$ generating the entire group, and your group is not simple, then you get a bound for $k$ in terms of the diameters of the quotients in the subnormal decomposition (using Schreier generators). The bound is non-optimal, though, and involves a product rather than a sum. – H A Helfgott Dec 30 '19 at 19:10
• Really? A product of indices (which I guess is like or linearly related to a diameter)? I guess moving a subgroup from coset to coset is more expensive than I thought. Gerhard "Must Consider Cost Of Moving" Paseman, 2019.12.30. – Gerhard Paseman Dec 30 '19 at 19:56

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). 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.
• I see - let me put it in my own words. If we intend to express an element $g$ fixing $n$ ($=0 \mod n$), we need a word that is a product of elements of the form $\sigma^{-k} \tau \sigma^{k} = (k+1, k+a+1)$. Now, if we want $g$ to send $1$ to $2$ (say), we must have transpositions of the form $(1,a+1)$, $(a+1,2a+1)$,\dots,$((r-1) a + 1, r a + 1)$, where $r = a^{-1}$, in whatever order, or else transpositions of the form $(1,-a+1)$, $(-a+1,-2 a +1)$, etc. If $r$ and $-r$ are far from $0$ mod $n$, then $\Theta(n)$ distinct transpositions are needed, and the total length must be $\Theta(n^2)$. – H A Helfgott Jan 4 '20 at 9:49