6
$\begingroup$

Let $G$ be a finite group. Define $\tau(G)$ as the minimal number, such that $\forall X \subset G$ if $|X| > \tau(G)$, then $XXX = \langle X \rangle$. Is there some sort of formula for $\tau(S_n)$, for the symmetric group $S_n$?

Here $XXX$ stands for $\{abc| a, b, c \in X\}$.

Similar problems for some different classes of groups are already answered:

1) $\tau(\mathbb{C}_n) = \lceil \frac{n}{3} \rceil + 1$, where $\mathbb{C}_n$ is cyclic of order $n$;

2) Gowers, Nikolov and Pyber proved the fact that $\tau(\mathrm{SL}(n, p)) \leq 2|\mathrm{SL}(n, p)|^{1-\frac{1}{3(n+1)}}$ for prime $p$.

However, I have never seen anything like that for $S_n$. It will be interesting to know if there is something...

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Your claim in (2) can't be true, since the right-hand term is not an integer. Maybe you mean asymptotics, and it's better if you say in which sense (be careful of the parameter $p$ too). Also say whether you assume $p$ prime, or prime power. $\endgroup$
    – YCor
    Commented Jun 15, 2019 at 9:47
  • $\begingroup$ @YCor, yes you are correct. That should have been not an exact equality but an upper bound. $p$ is prime. $\endgroup$
    – Chain Markov
    Commented Jun 15, 2019 at 10:04
  • 2
    $\begingroup$ Take $X=S_n-A_n$. Then $XXX=S_n-A_n$. So you should probably assume $1\in X$. $\endgroup$
    – YCor
    Commented Jun 15, 2019 at 13:53
  • 2
    $\begingroup$ Let me assume $1\in X$ in the definition. You have $\tau(S_n)\ge 2(n-5)!\sim 2n!/n^5$. Indeed in $S_n$ there the subgroup $S_{n-5}\times C_5$. This has some (symmetric) generating subset $X$ with $X^3$ not the whole subgroup, namely $X=S_{n-5}\times\{0,1\}$, of size $2(n-5)!$. (Or similarly $3(n-7)!$ is $X$ is also assumed to be symmetric). Probably the interesting definition is when you force $X$ to generate, in which case one could expect $\tau$ to be much smaller. $\endgroup$
    – YCor
    Commented Jun 15, 2019 at 13:54

1 Answer 1

Reset to default
5
$\begingroup$

Here is a lower bound: let $H$ be a subgroup of $S_{n}$ containing $(12)$ and let $\sigma$ be the $n$-cycle $(12 \ldots n)$. Let $X = H \cup \{\sigma \}$ and note that $\langle X \rangle = S_{n}$ since we already have $S_{n} = \langle (12),\sigma \rangle.$

Suppose that we have chosen $H$ so that $|X| > \tau(S_{n}).$ Then we must have $S_{n} = XXX$. But $XXX = H \cup H\sigma \cup H\sigma H \cup H\sigma^{2} \cup \sigma H \cup \sigma H \sigma \cup \sigma^{2}H \cup \sigma^{3}$ has cardinality at most $|H|^{2} + 6|H| + 1,$ so we must have $|H| + 3 > \sqrt{n!}.$

Hence we may choose $k$ minimal so that $k! \geq \tau(S_{n}).$ Then taking $H$ to be the natural copy of $S_{k}$ inside $S_{n}$, we must have $(k! + 3)^{2} > n!$. Then we must have $\tau(S_{n}) > \frac{\sqrt{n!} - 3}{k} \geq \frac{\sqrt{n!} - 3}{n}.$

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the accept, but I hope someone comes up with a better answer $\endgroup$
    – Geoff Robinson
    Commented Jun 21, 2019 at 13:09

You must log in to answer this question.

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