4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – ahulpke Feb 26 '15 at 22:12
  • $\begingroup$ 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$. $\endgroup$ – Bryce Sandlund Feb 26 '15 at 22:14
  • $\begingroup$ 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. $\endgroup$ – Matt Samuel Feb 27 '15 at 0:14
  • $\begingroup$ Sorry, @whacka, accidentally dropped the $!$. And yes, I mean $\Theta(\sqrt{n!})$; updated. $\endgroup$ – Bryce Sandlund Feb 27 '15 at 2:24
  • $\begingroup$ @MattSamuel, do you know what the order is prior to taking a logarithm? What is the example? $\endgroup$ – Bryce Sandlund Feb 27 '15 at 2:27
4
$\begingroup$

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}}$ .

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bryce Sandlund Feb 27 '15 at 2:29
  • $\begingroup$ @Bryce How exactly are you storing your subgroup? It's possible to write down the centralizer of a single permutation quite explicitly on paper. $\endgroup$ – whacka Feb 27 '15 at 2:34
  • 2
    $\begingroup$ This centralizer is a wreath product $C_2\wr S_{n/2}$ and one can write down generators in time $O(n)$. $\endgroup$ – ahulpke Feb 27 '15 at 3:28
  • $\begingroup$ 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. $\endgroup$ – Bryce Sandlund Feb 27 '15 at 7:04
  • $\begingroup$ 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. $\endgroup$ – Geoff Robinson Feb 27 '15 at 13:59

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.