11
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\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$
    – Gerhard Paseman
    Commented Dec 30, 2019 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$
    – H A Helfgott
    Commented Dec 30, 2019 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$
    – H A Helfgott
    Commented Dec 30, 2019 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$
    – Gerhard Paseman
    Commented Dec 30, 2019 at 19:56

1 Answer 1

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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$
    – H A Helfgott
    Commented Jan 4, 2020 at 9:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .