How many non-isomorphic abelian subgroups of the permutation group $S_n$?

Question

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?

Answer 1

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).

Answer 2

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.

Answer 3

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

Answer 4

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

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

Update 2

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