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

1 Answer 1

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

$\endgroup$
5
  • $\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$ Feb 27, 2015 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, 2015 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, 2015 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$ Feb 27, 2015 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$ Feb 27, 2015 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.