8
$\begingroup$

Let $G$ be a finitely generated group. I am trying to count the number of permutation representations on $n$ elements, i.e. homomorphisms from $G$ to the symmetric group $S_n$. Equivalently this is the number of ways that $G$ can act on the set $\{1,2,\ldots,n\}$. Let $a_{G,n}$ be the number of homomorphisms from $G$ to $S_n$. Let $\alpha(G) = \lim_n \frac{\log(a_{G,n})}{n\log n}$. How can we determine $\alpha(G)$?

For example, if $G = \mathbb Z$ we have $a_{G,n} = n!$, since a homomorphism $\mathbb Z \to S_n$ is determined by the image of its generator. By Stirling's approximation we have $\alpha(\mathbb Z) = 1$. More generally, for $G = F_s$ the free group on $s$ generators, we get $\alpha(F_s) = s$. For $G = \mathbb Z/2$, a morphism $G\to S_n$ can be seen as an order 2 element in $S_n$. We can create such a permutation by dividing the elements of $\{1,2,\ldots,n\}$ in to pairs, which can be done in $\frac{n!}{(n/2)!2^{n/2}}$ ways. This is asymptotically $\exp(\frac12 n\log n)$. There are some more permutations of order 2 that have fixed points, but not enough to change the asymptotic result. So $\alpha(\mathbb Z/2) = \frac12$. More generally, for any finite group $G$ we have $\alpha(G) = 1-\frac1{|G|}$.

How can we determine $\alpha(G)$ for an arbitrary group?

$\endgroup$
3
  • 2
    $\begingroup$ This doesn't directly answer your question, but if $G$ has $j_d(G)$ subgroups of index $d$ then $$ \sum_{n\geq 0} \alpha_{G,n}\frac{x^n}{n!} =\exp \sum_{d\geq 1}j_d(G)\frac{x^d}{d}. $$ See Enumerative Combinatorics, vol. 2, Exercise 5.13. $\endgroup$ Jan 12, 2023 at 18:30
  • 2
    $\begingroup$ Continuing my comment, the formula does determine the asymptotic behavior of $\alpha_{G,n}$ when $G$ is finite, since the asymptotic behavior of the coefficients of $e^{p(x)}$ when $p(x)$ is a polynomial is known. $\endgroup$ Jan 12, 2023 at 19:08
  • 1
    $\begingroup$ The study of $j_d(G)$ is called subgroup growth $\endgroup$ Jan 13, 2023 at 0:25

1 Answer 1

5
$\begingroup$

In general it is not known whether $\alpha(G)$ exists as a limit (as opposed to limsup). For virtually solvable groups of finite rank (whose subgroup growth is at most polynomial) the relation between subgroup growth and representation growth given in the comments shows that $\alpha(G) \le 1$ (and equals it if the group is residually finite).

For finite groups $\alpha(G) = 1 - \tfrac 1{|G|}$ (this is likely provable by elementary means, much more precise results on the asymptotic behaviour of $a_{G, n}$ in this case are given by Müller https://zbmath.org/0862.20019).

An opposite situation is that of so-called large groups (which have a finite-index subgroup surjecting onto the free group $F_2$). For these $\alpha(G) > 0$ if it exists, and it has been computed exactly for a few families, for example:

There also are relevant sporadic examples in another paper of Müller--Schlage-Puchta (https://zbmath.org/1127.20022). In particular they observe that the 2-generator 1-relator group $$ G = \langle a, b | a^mb^n \rangle $$ admits the free product $C_m * C_n$ as a quotient and hence it satisfies that $\alpha(G) \ge 2 - \tfrac 1n - \tfrac 1m$ (more generally you can get 1-relator $d$-generated groups with $\alpha(G)$ arbitrarily close to $d$).

$\endgroup$
2
  • $\begingroup$ Great! I didn't realize it would be so complicated. $\endgroup$
    – Squala
    Jan 31, 2023 at 16:10
  • $\begingroup$ I suspect calculating $\alpha(G)$ is in general an undecidable problem; I wonder if determining whether (say) $\alpha(G)= 1$, or a related property, is a Markov property. $\endgroup$ Jan 31, 2023 at 19:13

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.