# Construction of Subgroups of $S_n$ of a Certain Size

I am interested in constructing a subgroup of $S_n$ of size on the order of $\Theta(\sqrt{n!})$. The algorithm to construct such a subgroup should ideally also take around $O(\sqrt{n!})$ time.

One simple solution is to just choose $S_k$, $k < n$ such that $k!$ is around $\sqrt{n!}$. There is guaranteed to be a $k$ such that $\sqrt{n!} \leq k! \leq n \sqrt{n!}$ just by a simple counting argument. However, I am wondering if there is an entirely different idea that could construct a subgroup for any arbitrary $S_n$ that is tightly of size $\Theta(\sqrt{n!})$.

Any reference material such as textbooks or papers would be appreciated.

• Do you want one subgroup? All such subgroups? One with nice properties? Do you care about the asymptotic result, or about being close for practical values of $n$? Feb 26, 2015 at 22:12
• For my purposes I only need any one such subgroup, with any properties. Practicality is nice, but I am mostly concerned that the subgroup $H$ is within a constant factor of $\sqrt{n!}$ for any such $S_n$. Feb 26, 2015 at 22:14
• If you're willing to accept a subgroup the logarithm of whose order is asymptotically $\frac{1}{2}n\log n$, I've got an example. I don't believe it satisfies your condition though. Feb 27, 2015 at 0:14
• Sorry, @whacka, accidentally dropped the $!$. And yes, I mean $\Theta(\sqrt{n!})$; updated. Feb 27, 2015 at 2:24
• @MattSamuel, do you know what the order is prior to taking a logarithm? What is the example? Feb 27, 2015 at 2:27

I think that one reasonable candidate is the centralizer, $H$ say, of a product of $\lfloor \frac{n}{2} \rfloor$ disjoint $2$-cycles. This subgroup has order $2^{\lfloor \frac{n}{2} \rfloor} \lfloor \frac{n}{2} \rfloor!$. Stirling's formula shows that $\frac{|S_{n}|}{|H|^{2}}$ is relatively small. It's also possible to use character theory to obtain the crude estimate $|H| \geq \sqrt{\frac{n!}{p(n)}}$, where $p(n)$ is the number of partititions of $n,$ and it is well-known that $p(n) \sim e^{c\sqrt{n}}$ .
• The centralizer would take $O(|S_n|)$ time to compute, though, correct? I would like to be able to construct the subgroup in around $O(\sqrt{n!})$ time. Feb 27, 2015 at 2:29
• This centralizer is a wreath product $C_2\wr S_{n/2}$ and one can write down generators in time $O(n)$. Feb 27, 2015 at 3:28
• I need to enumerate each element of the subgroup. Wolfram tells me this subgroup is of order $\Theta(n^{1/4}\sqrt{n!})$, which is very close to what I want. I need to do some research on wreath products, as I have not heard of them before, but regardless this has been a great discussion. Feb 27, 2015 at 7:04
• It is also pretty easy to explicitly describe the elements of $H,$ if you take it to be centralizer of $(12)(34).....$. Each element is uniquely described by a pair $(\alpha, \beta)$, where $\alpha$ is an element of the base group $\langle (12) \rangle \times \langle (34) \rangle \times \ldots$ and $\beta$ is an element of $S_{\lfloor \frac{n}{2} \rfloor}$ which permutes the direct factors of the base group in the obvious way. Feb 27, 2015 at 13:59