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
    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
    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
    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
    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
    Jun 21, 2019 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.