Counting Group Actions from a Finite Group to Itself

Question

Given a finite group $G$, how many group homomorphisms $G \to \mathrm{Perm}(G)$ are there? Alternatively, in how many ways can a finite group act on itself?

Answer 1

Here are some food for thoughts, this is far from an answer as I don't know it.

• If $G$ is cyclic, then $G$ can acts on itself through $|G|!$ different ways. Indeed, if $x\in G$ is a generator of $G$, there are as many homomorphisms from $G$ to $S(G)$ as there are elements in $S(G)$, since a group homomorphism from $G$ is uniquely determined by the image of $x$.

• Let $G_1$, $G_2$ be two finite groups and let $G:=G_1\oplus G_2$. If $\varphi$, respectively $\psi$, is a group homomorphism from $G_1$ to $S(G_1)$, respectively from $G_2$ to $S(G_2)$, then $\varphi\oplus\textrm{id}_{G_2}$, respectively $\textrm{id}_{G_1}\oplus\psi$ is a group homomorphism from $G_1\times G_2$ to $S(G)$. Furthermore, distincts $\varphi$, respectively distincts $\psi$, leads to distincts $\varphi\oplus\textrm{id}_{G_1}$, respectively distincts $\textrm{id}_{G_2}\oplus\psi$. Besides, if $\varphi$ or $\psi$ is not the identity of $G_1$ or $G_2$, then $\varphi\oplus\textrm{id}_{G_2}$ is distinct from $\textrm{id}_{G_2}\oplus\psi$. Therefore, one has: $$|\textrm{Hom}(G,S(G))|\geqslant|\textrm{Hom}(G_1,S(G_1))|\times|\textrm{Hom}(G_2,S(G_2))|-1.$$ I believe this lower bound is far from being optimal.

• If $G$ is finite abelian, then $G$ is a direct product of a finite number of cyclic groups. This follows from the classification of finitely generated modulus on principal ideal domains. If $\displaystyle G=\bigoplus_{i=1}^n\mathbb{Z}/(d_i)$, according to the following point, there is at least $d_1!\cdots d_n!-n+1$ group actions of $G$ on itself. Notice that whenever $G$ is cyclic, this lower bound is reached. It would be an interesting question to ask when this lower bound is reached, but I have no clue at that moment.

Answer 2

Every $G$-set $X$ decomposes into orbits on which $G$ acts transitively, and all transitive $G$-sets are isomorphic (as $G$-sets) to a left coset space $G/H$ for some $H$ which is unique up to conjugation.

So let's determine the number of group actions of $G$ on a set of size $n$. The only thing special about the case $n=|G|$ is that when $X$ has the same underlying set as $G$ there is a canonical action as in the statement of Cayley's theorem (called the regular action), so there's no reason to restrict to that special case. In fact we don't even need to assume that the group $G$ is finite, although we should assume $n=|X|$ is.

On the one hand, an action of $G$ on $\{1,\cdots,n\}$ is just a homomorphism $G\to S_n$, so what we're trying to count (or characterize) is the cardinality $|\hom(G,S_n)|$ using purely group-theoretic numerical invariants of $G$. We will consider the associated exponential generating function and find an alternative description of it.

Let's figure out how many ways we can have $G$ act on $X$ giving $e_k$ orbits of size $k=1,2,3,\cdots$, for some numbers $e_1,e_2,e_3,\cdots$ satisfying $1e_1+2e_2+3e_3+\cdots=n$.

First, we must partition $X$ into $e_k$ subsets of size $k$ for each $k$. The number of ways to do that is

$$ \frac{n!}{1!^{e_{\large 1}}e_1!~2!^{e_{\large 2}}e_2!~3!^{e_{\large 3}}e_3!\,\cdots}. $$

One way of thinking about this is the orbit-stabilizer theorem: the group $S_n$ acts on the set of all of these partitions transitively, and all point-stabilizers are isomorphic to a direct product of wreath products of symmetric groups $(S_1\wr S_{e_{\large 1}})\times(S_2 \wr S_{e_{\large 2}})\times( S_3\wr S_{e_{\large 3}})\times\cdots$.

Next, given a particular subset $Y\subseteq X$ of size $k$, how many ways can we imbue it with a transitive action of $G$? Construct a list $H_1,H_2,\cdots,H_{\ell}$ of representatives of each conjugacy class of subgroup of $G$ of index $k$. (Exercise: the $G$-sets $G/H$ and $G/H'$ are isomorphic if and only if $H\sim H'$ are conjugate subgroups.) Suppose there are $n_1,n_2,\cdots,n_{\ell}$ conjugates of each respectively. If we have $G$ act by conjugation on each conjugacy class of subgroup and apply orbit-stabilizer we obtain the formula $n_i=[G:N_G(H_i)]$.

To make $Y$ a $G$-set isomorphic to $G/H_i$, we must pick a bijection $Y\to G/H_i$. Since both $Y$ and $G/H_i$ have size $k$, there are $k!$ ways to do this. However, there is some redundancy: two bijections $Y\to G/H_i$ induce the same $G$-action on $Y$ if there is a $G$-set automorphism $G/H_i\to G/H_i$ which relates the two. We have $\mathrm{Aut}_{G\textrm{-set}}(G/H_i)\cong N_G(H_i)/H_i$ (see my answer here).

Putting this together, the number of transitive actions of $G$ on $Y$ equals

$$ \begin{array}{ll} \displaystyle k!\,\sum_{i=1}^{\ell} \frac{1}{|N_G(H_i):H_i]} & \displaystyle =\frac{k!}{[G:H_i]}\sum_{i=1}^{\ell} \frac{[G:H_i]}{[N_G(H_i):H_i]} \\ & \displaystyle = \frac{k!}{k} \sum_{i=1}^{\ell} [G:N_G(H_i)] \\ & \displaystyle =(k-1)!\sum_{i=1}^{\ell} n_i. \end{array} $$

If $a_k$ denotes the number of subgroups of $G$ of index $n$, this is $(k-1)!a_k$.

We do this for every subset $Y\subseteq X$ of size $k$ for all $k$, multiply the counts together, and we obtain the following exponential generating function:

$$\begin{array}{ll} F(z) & \displaystyle = \sum_{n=0}^\infty\frac{|\hom(G,S_n)|}{n!} z^n \\ & \displaystyle =\sum_{n=0}^\infty \left[\sum_{n=1e_1+2e_2+\cdots} \frac{n!}{1!^{e_{\large 1}}e_1!~2!^{e_{\large 2}}e_2!~3!^{e_{\large 3}}e_3!\,\cdots} (0! a_1 )^{e_{\large 1}}(1! a_2)^{e_{\large 2}}(2! a_3)^{e_{\large 3}} \cdots\right]\frac{z^n}{n!} \\ & \displaystyle =\sum_{e_1,e_2,\cdots}\frac{1}{e_1!e_2!e_3!\cdots}\left(\frac{a_1}{1}z^1\right)^{e_{\large 1}} \left(\frac{a_2}{2}z^2\right)^{e_{\large 2}} \left(\frac{a_3}{3}z^3\right)^{e_{\large 3}}\cdots \\ & \displaystyle = \sum_{m=0}^\infty \frac{1}{m!}\sum_{e_1+e_2+\cdots=m}\binom{m}{e_1,e_2,e_3,\cdots} \left(\frac{a_1}{1}z^1\right)^{e_{\large 1}} \left(\frac{a_2}{2}z^2\right)^{e_{\large 2}} \left(\frac{a_3}{3}z^3\right)^{e_{\large 3}}\cdots \\ & \displaystyle = \sum_{m=0}^\infty \frac{1}{m!}\left(\frac{a_1}{1}z^1+\frac{a_2}{2}z^2+\frac{a_3}{3}z^3+\cdots\right)^m \\ & \displaystyle = \exp\left(\sum_{k=1}^\infty\frac{a_k}{k} z^k\right). \end{array}$$

One may categorify this argument to make it much slicker: the exponential generating function $F(z)$ is the weighted groupoid cardinality of the category of finite $G$-sets with isomorphisms, which is equivalent to the free symmetric monoidal category on the finite groupoid of finite transitive $G$-sets with automorphisms, in which case we can use the "categorical exponential formula." Qiaochu Yuan writes about this in a blog post here.