12
$\begingroup$

I am interested in how many (pairwise non-isomorphic) subgroups of the permutation group $S_n$ are abelian. ($n \in \mathbb{N}$ arbitrary and possibly big)

Are you aware of any references which treat this problem?

$\endgroup$
2
  • 20
    $\begingroup$ Let $G = C_{q_1} \times C_{q_2} \times \cdots \times C_{q_k}$, where $q_1, \dots, q_k$ are prime powers. Then $G$ is isomorphic to a subgroup of $S_n$ if and only if $q_1 + q_2 + \cdots + q_k \leq n$. $\endgroup$ Commented Dec 1, 2021 at 14:11
  • 8
    $\begingroup$ The number is tabulated (up to $n=10000$) at oeis.org/A023893 – no lliterature is noted. $\endgroup$ Commented Dec 1, 2021 at 22:31

4 Answers 4

10
$\begingroup$

Claim 1: (same as my comment) Let $q_1, \dots, q_k > 1$ be prime powers. Then $G = C_{q_1} \times \cdots \times C_{q_k}$ is isomorphic to a subgroup of $S_n$ if and only if $q_1 + \cdots + q_k \leq n$.

Proof: If $q_1 + \cdots + q_k \leq n$ we can choose disjoint cycles of lengths $q_1, \dots, q_k$, so the condition is clearly sufficient. Conversely suppose $G \leq S_n$. Let $O_1, \dots, O_t$ be the orbits of $G$ and let $G_i$ be the transitive abelian subgroup of $\mathrm{Sym}(O_i)$ induced by $G$. Since transitive abelian groups are regular we have $|G_i| = |O_i|$ so $|G_1| + \cdots + |G_t| = n$. Since $G \leq G_1 \times \cdots \times G_t$, $|G_1| + \cdots + |G_t|$ is at least $q_1 + \cdots + q_k$. $\square$

It follows that, now considering 1 to also be a prime power, the number of isomorphism classes of abelian subgroups of $S_n$ is the number $f(n)$ of partitions of $n$ into prime powers, as asserted on OEIS.

Claim 2: $ \log f(n) \sim 2\pi / \sqrt{3} (n / \log n)^{1/2}.$

Sketch: As explained in the answer of @2734364041, $f(n) \geq p_\mathbb{P}(n)$, where $p_\mathbb{P}(n)$ is the number of partitions of $n$ into prime parts, and the claimed asymptotic was proved for $p_\mathbb{P}(n)$ by Roth and Szekeres, so that gives the lower bound. Upper bounds in saddle-point arguments are easier, so it's probably fine, as in Flajolet--Sedgewick VIII.26. [Edit: Actually Roth and Szekeres prove a general result that applies equally to prime powers.] $\square$

There are some interesting variants. For example, what is the number of isomorphism classes of abelian 2-subgroups of $S_n$? Answer: it is the number $g(n)$ of partitions of $n$ into powers of 2, and $$\log g(n) \sim \frac{(\log n)^2}{2 \log 2}$$ (see Flajolet--Sedgewick VIII.27).

$\endgroup$
1
  • $\begingroup$ I was hesitant to commit to your Claim 2 because I was thinking about asymptotics for $f(n)$, and I am unfamiliar with the underlying methods. But a saddle-point argument for the upper bound, while too lossy for an asymptotic for $f(n)$, should be plenty to get an asymptotic for $\log f(n)$. Very nice! $\endgroup$
    – 2734364041
    Commented Dec 2, 2021 at 20:46
9
$\begingroup$

Based on Sean Eberhard's comment, it follows that if $f(n)$ is the number of non-isomorphic abelian subgroups of $S_n$, then $f(n)\geq p_{\mathbb{P}}(n)$, where $p_{\mathbb{P}}(n)$ is the number of partitions of $n$ into prime parts. It was proved by Roth and Szekeres that

$$\log p_{\mathbb{P}}(n) = \frac{2 \pi}{\sqrt{3}}\Big(\frac{n}{\log n}\Big)^{1/2}\Big(1+O\Big(\frac{\log\log n}{\log n}\Big)\Big).$$

Per https://oeis.org/A023893, $f(n)$ is the number of partitions of $n$ into prime power parts (1 included). I think that it is reasonable to guess that there exists a constant $C>0$ such that

$$\log f(n) = (C+o(1)) \Big(\frac{n}{\log n}\Big)^{1/2}$$

based on the fact that there are $\ll\sqrt{x}$ prime powers $p^k$ with $k\geq 2$ such that $p^k\leq x$. See work of Gafni and Yang for closely related work on partitions into prime powers.

$\endgroup$
1
  • $\begingroup$ I changed the constant to what I think is the correct value. Roth and Szekeres actually mainly discuss partition into distinct prime parts, and give the previously cited asymptotic, and only briefly discuss the other one and give a complicated expression. There is lots of discussion at oeis.org/search?q=A000607 which gives the asymptotic above, which is larger by a factor of $\sqrt{2}$ $\endgroup$ Commented Dec 3, 2021 at 15:09
2
$\begingroup$

We denote by $\mathbb{Z}/m$ the cycle group of order $m$.

Some examples: The finite groups $\mathbb{Z}/{p_1^{a_1}}\oplus \cdots \oplus \mathbb{Z}/p_k^{a_k}$, where the $p_i$ are pairwise distinct primes and the $a_i$ are positive integers such that $\sum_i p_i^{a_i}\leq n$, can be clearly embedded into $S_n$.

Edit: I also thought to be true that whenever $n=m\cdot k$, for positive integers $m$ and $k$, we have a copy of $(\mathbb{Z}/k)^m\oplus (\mathbb{Z}/m)$ inside $S_n$. However, the construction I had in mind actually yields to wreath products $(\mathbb{Z}/k)\wr (\mathbb{Z}/m)$.

In a more recent answer, Sean already gives a proof that rules out other abelian subgroups and completely answers the question.

More details: Now let me explain how the previous examples can be ensured. We know that every permutation $\sigma \in S_n$ can be expressed as the product of cycles of disjoint support, and that, up to ordering of these factors, these decomposition is unique (mutually disjoint cycles commute).

We view $S_n$ as the premutation group of the set $\{1, \dots, n\}$. Given a cycle $c$, expressed in usual notation $c=(c_1\, c_2\, \dots \, c_n)$, it is clear that the conjugation $\sigma \cdot c\cdot \sigma^{-1}$ is again a cycle. In fact, it equals exactly $(\sigma (c_1)\, \dots \, \sigma (c_n))$. Given a product of disjoint cycles $c_1\cdots c_k$, its order as element of $S_n$ is equal to the least common multiple of the lengths of the involved $c_i$. Also, from the previous decomposition,

We know that any finite abelian group $A$ admits a decomposition as above, $A\cong \mathbb{Z}/{p_1^{a_1}}\oplus \cdots \oplus \mathbb{Z}/{p_k^{a_k}}$, where the $p_1<\dots <p_k$ are primes and the $a_i$ are positive integers; and these decomposition is unique. The case $A=1$ corresponds to $k=0$.

If $\sum_{i=1}^k p_i^{a_i}\leq n$, we define, for $1\leq j\leq k$, the disjoint cycles $$c_j= (q_j+1,\, \, q_j+2,\, \dots \,\, q_j+p_j^{a_j}),$$ where $q_j=\sum_{i=1}^{j-1} p_i^{a_i}$. It is easy to see that they generate in $S_n$ a subgroup isomorphic to $\mathbb{Z}/{p_1^{a_1}}\oplus \cdots \oplus \mathbb{Z}/{p_k^{a_k}}$.

Now, suppose that $n=m\cdot k$. Consider the $m$ following $k$-cycles $c_{*,1}$ $$\{c_{t,1}=\big(k(t-1)+1,\,\, k(t-1)+2 ,\dots \,\, kt \big) : \mbox{for $1\leq t\leq m$}\}.$$ These are clearly mutually disjoint cycles and they generate a subgroup isomorphic to $\mathbb{Z}/k^m$. In addition to these cycles, consider the $k$ following $m$-cycles $$\{c_{j,2}=\big(j,\,\, k+j, \dots \,\, k(m-1)+j \big) : \mbox{for $1\leq j\leq k$}\}$$ and define their product $$c_2=c_{1,2}\cdots c_{k, 2}.$$ It is not difficult to see that these $m+1$ permutations $\{c_{1,1}, \dots, c_{m,1}, c_2\}$ generate a subgroup isomorphic to $(\mathbb{Z}/k)\wr (\mathbb{Z}/m)\cong (\mathbb{Z}/k)^m\rtimes \mathbb{Z}/m $. In fact, $c_2$ verifies that $c_2 c_{t,1}c_2^{-1}=c_{t+1,1}$ by using the previous conjugation formula. It would rest to check to check that the subgroup $H_1=\langle c_{j, 1}\rangle$ generated by the $m$ first $k$-cycles does not intersect the subgroup $H_2$ generated by $c_2$. This is simply due to the fact that the support of any cycle of the cycle decomposition of any element in $H_1$ intersects the support of any cycle of the cycle decomposition of any element in $H_2$ in at most one element. In particular, the cycle decomposition of any element in $H_1\cap H_2$ must only have cycles of length 1. In other words, $H_1\cap H_2=\{1\}$.

$\endgroup$
7
  • 16
    $\begingroup$ I'd have expected Gollum to answer questions about rings rather than groups. $\endgroup$ Commented Dec 1, 2021 at 23:46
  • 2
    $\begingroup$ @Carl-FredrikNybergBrodda If you refer to the Precious, they stole us... and this helps in detox. $\endgroup$
    – Gollum
    Commented Dec 2, 2021 at 0:04
  • 2
    $\begingroup$ So $S_4$ contains $(\mathbb{Z}/2\mathbb{Z})^3$? I do not think so: Sylow subgroup looks to be $D_4$ which is not Abelian. Actually your $c_2$ does not seem to commute with the cycles $c_{t,1}$ $\endgroup$ Commented Dec 2, 2021 at 7:10
  • $\begingroup$ I'm pretty sure $c_{t,1}^{c_2} = c_{t,2}$, and the group they generate is the wreath product $C_k \wr C_m$. $\endgroup$ Commented Dec 2, 2021 at 9:07
  • 1
    $\begingroup$ @Gollum: What are you planning to do with this post now? Reformulate it? Delete it? $\endgroup$
    – Alex M.
    Commented Dec 2, 2021 at 9:48
2
$\begingroup$

This is a (cw) post to illustrate Claim 2 from the answer by Sean Eberhard. Below is the plot of the list $(\frac1n,\frac{\log f(n)}{\pi\sqrt{2/3}(n/\log n)^{1/2}})$ for $n$ from $1000$ to $10000$.

enter image description here

I used the list of values from OEIS A023893.

As you see after $n$ about 3000 the sequence sort of changes behavior; at about $n=5000$ (to be precise, at $5226$) it achieves a (local ?) maximum and then starts to drop with increasing speed.

It looks so strange that I suspected some error in the computation of values. But then I recomputed it myself in Mathematica using power series expansion and obtained precise coincidence.

Update

I now extended computations to $n\leqslant100000$ and it seems that the tendency continues, so that at least in the range from $10000$ to $100000$ $\log f(n)$ grows qualitatively slower than $\sqrt{\frac n{\log n}}$...

enter image description here

Update 2

With the constant $2\pi/\sqrt3$ instead of $\pi\sqrt{2/3}$ it is

enter image description here

$\endgroup$
9
  • 4
    $\begingroup$ Well, the ratio is supposed to tend to $1$ in the limit, so if it got all the way up to $1{.}76$, it has to start falling back down at some point. $\endgroup$ Commented Dec 2, 2021 at 16:35
  • 3
    $\begingroup$ @EmilJeřábek Hard to disagree. Still, I find this kind of behavior somehow surprising. Besides, the curve is quite smooth so maybe somebody can guess some more precise statement about asymptotics... $\endgroup$ Commented Dec 2, 2021 at 19:50
  • 2
    $\begingroup$ The correct constant is actually $2 \pi / \sqrt{3}$ rather than $\pi \sqrt{2/3}$. That brings the peak down to about 1.24 (but doesn't change the surprising shape). There is some similar discussion at oeis.org/search?q=A000607 of the numerics. $\endgroup$ Commented Dec 3, 2021 at 15:12
  • 1
    $\begingroup$ I guess what is happening is lower order terms are something like $\exp(c \sqrt{n / \log n})$ for smaller constants $c$, and it takes a while before these are insignificant compared to the main term. $\endgroup$ Commented Dec 3, 2021 at 15:15
  • $\begingroup$ @SeanEberhard In fact the proposed asymptotic for A000607 has an opposite property. They supply the list up to 50000 and the ratio there grows with increasing speed, crossing 1 at $n=13194$. $\endgroup$ Commented Dec 4, 2021 at 5:47

Your Answer

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

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