# $q$-(and other)-analogs for counting index-$n$ subgroups in terms of Homs to $S_n$?

The following formula of astonishing beauty and power (imho):

$$\sum_{n \ge 0} \frac{| \mathrm{Hom}(G,S_n) | }{n! } z^n = \exp\left( \sum_{n \ge 1} \frac{|\text{Index}~n~\text{subgroups of}~ G|}nz^n \right)$$

can be found in e.g. Qiaochu Yuan blog , here $G$ is a finitely generated group, $| \mathrm{Hom}(G,S_n) |$ is the number of homomorphisms from $G$ to the symmetric group $S_n$ (pay attention that we count homomorphisms themselves - not up to conjugation). $|\mathrm{Index}~n~\text{subgroups of}~ G|$ is the number of index $n$ subgroups in $G$. (See examples below). It seems to me that Tao's post is related.

Keeping in mind the heuristics $S_n$ = $\mathrm{GL}$ (field with one element), it seems natural to think in the following direction:

Question 1a Is there $q$-analog of this formula of the following spirit: let us substitute $S_n$ in the left hand side by $\mathrm{GL}(n,\mathbf{F}_q)$. So we are interested in: $$\sum_{n \ge 0} \frac{| \mathrm{Hom}(G,\mathrm{GL}(n,\mathbf{F}_q)) | }{ [n]_q! } z^n = ???$$

or in the closely related:

$$\sum_{n \ge 0} \frac{| \mathrm{Hom}(G,\mathrm{GL}(n,\mathbf{F}_q)) | }{ |\mathrm{GL}(n,\mathbf{F}_q)| } z^n = ???$$

where $\mathrm{GL}(n,\mathbf{F}_q)$ is the general linear group over the finite field $\mathbf{F}_q$, the number of elements in it - almost $q$-factorial: $|\mathrm{GL}(n,\mathbf{F}_q)| = [n]_q! (q-1)^n q^{\frac{n(n-1)}{2}}$.

Question 1b At least if $G$ is a finite group, can one say something about the series appearing in the left-hand side? In the original formula we get $\exp(\text{Polynomial})$; what is an appropriate $q$-analog of it?

Example 1 Consider $G$ to be trivial group $G= \{\mathrm{Id}\}$ (just identity). The original formula reads:

$$\sum_{n \ge 0} \frac{1}{n! } z^n = \exp( z)$$

The $q$-analog-1 reads:

$$\sum_{n \ge 0} \frac{1}{[n]_q ! } z^n = e_q( z)$$

Ура! We got a bit of luck: $q$-exponential appeared in the right-hand side in complete analogy with original formula. Consideration of $q$-analog-2 also gives something closely related to the $q$-exponential expression.

Example 2 Consider $G$ to be $\mathbf{Z}$ (integers - free abelian group with one generator). The original formula reads:

$$\sum_{n \ge 0} \frac{n!}{n! } z^n = exp\left( \sum_{n \ge 1} \frac{z^n}n \right)$$

which is indeed true , since $1/(1-z)= \exp(-\log(1-z))$.

The $q$-analog-1 reads:

$$\sum_{n \ge 0} \frac{[n]_q ! (q-1)^n q^{\frac{n(n-1)}{2}} }{[n]_q ! } z^n = ???$$

It is not clear what should we get at the right-hand side, but at least the left-hand side looks not terrible: $[n]_q!$ cancels and we get expression similar to theta function. If we consider $q$-analog-2 we just get $1/(1-z)$ built-in.

Example 3 Consider $G$ to be $\mathbf{Z}\oplus \mathbf{Z}$ (pairs of integers - free abelian group with two generators). The left-hand side will involve the number of pairs of commuting elements in $S_n$ - which is equal to number of conjugacy classes in $S_n$ multiplied by the size of $S_n$, so original formula reads:

$$\mathrm{LHS} = \sum_{n \ge 0} \frac{p(n) n!}{n! } z^n = \sum_{n \ge 0} p(n) z^n$$

In the $q$-case, we again see that $[n]_q !$ cancels and we will get the generating function for number of conjugacy classes in $\mathrm{GL}(n,\mathbf{F}_q)$, which has a nice expression but is difficult to to recognize as $q$-exponential of what it should be.

Example ... Taking $G=\mathbf{Z}^k$, we will get generating function for number of commuting $k$-tuples in $S_n$ in the original formula; what should be the $q$-analog? Taking $G = \mathbf{Z}/2\mathbf{Z}$ we will get number of involutions; taking $G=\mathbf{Z}/n\mathbf{Z}$, the number of elements of order $n$.

Question 2 what are the analogs of the original formula if we substitute $S_n$ by the other Weyl groups? And $q$-analogs are other simple algebraic groups over $\mathbf{F}_q$?

Question 3 For compact Lie groups the left-hand side also has an analog - take $\mathrm{U}(n)$ instead of $S_n$ - consider volumes of $\mathrm{U}(n)/G$... Is there nice right-hand side?

PS: What is the history of the formula: author? references? Lubotzky seems to attribute it to Müller around the nineties...

Is there some intuitive explanation of the formula? How subgroups can be be related to homomorphisms to $S_n$?

• One way I think about that formula is that $G$ acts transitively on the $n$ cosets of a subgroup of index $n$, and permutation representations can be built from transitive permutation representations. – Douglas Zare Jun 12 '17 at 20:10
• "$q$-analogues of $S_n$" makes me think "Hecke algebra," though I'm not sure that makes that much sense here... – Timothy Chow Jun 14 '17 at 13:31
• @TimothyChow Well ... Hecke algebra is part of GL(n,F_q) - I mean consider group algebra and its part bi-invariant (left and right) for Borel subalgebra - that will be precisely Hecke algebra. (By Brua decopmposition GL = BorelS_nBorel -- so facrotring out Borel - the size will be like S_n, but the product will be deformed). In that way Hecke algebra appeared much earlier than "quantum groups". And its miracle that the same algebra appeared in Schur-Weyl duality for U_q(gl). On the other hand recent papers relate U_q(gl) and GL(n,F_q) see: – Alexander Chervov Jun 14 '17 at 17:01
• Quantum linear groups an representations of GLn(Fq) J Brundan, R Dipper, AS Kleshchëv - 2001 - books.google.com google.ru/… – Alexander Chervov Jun 14 '17 at 17:02

Yes, there's a $q$-analogue. See this paper of Yoshida from 1992, where $\sum_{n \ge 0} \frac{| \mathrm{Hom}(G,\mathrm{GL}(n,\mathbf{F}_q)) | }{ |\mathrm{GL}(n,\mathbf{F}_q)| } z^n$ is expressed in terms of some invariants of the group ring $\mathbb{F}_q G$, at least when $G$ is a finite group (page 27). Yoshida only states the result. A proof appears for instance in a follow up paper by Chigira, Takegahara and Yoshida from 2000. From their result it follows that when $(|G|,q)=1$, the generating function is a finite product of power series of the form $P(z^a,q^b)$ for various $a$ and $b$, where $$P(z,q) = \sum_{n \ge 0} \frac{z^n}{|GL(n,\mathbb{F}_{q})|}.$$
The original formula for $S_n$, in terms of generating functions, is due to Wohlfahert, see this paper from 1977. An earlier equivalent result, stated in a different fashion, is due to Dey (1965). Dress and Müller generalized the generating function result to a more general setting their paper from 1997, see Proposition 1.