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

  • $\begingroup$ 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. $\endgroup$ Dec 30 '19 at 19:03
  • 1
    $\begingroup$ 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)})$. $\endgroup$ Dec 30 '19 at 19:08
  • $\begingroup$ 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. $\endgroup$ Dec 30 '19 at 19:10
  • $\begingroup$ 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. $\endgroup$ 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<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.

  • $\begingroup$ 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)$. $\endgroup$ Jan 4 '20 at 9:49

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.