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

  • 1
    $\begingroup$ 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. $\endgroup$ – Douglas Zare Jun 12 '17 at 20:10
  • $\begingroup$ "$q$-analogues of $S_n$" makes me think "Hecke algebra," though I'm not sure that makes that much sense here... $\endgroup$ – Timothy Chow Jun 14 '17 at 13:31
  • $\begingroup$ @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: $\endgroup$ – Alexander Chervov Jun 14 '17 at 17:01
  • $\begingroup$ Quantum linear groups an representations of GLn(Fq) J Brundan, R Dipper, AS Kleshchëv - 2001 - books.google.com google.ru/… $\endgroup$ – 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.

| cite | improve this answer | |
  • 6
    $\begingroup$ The attribution to Wohlfahrt is not quite accurate, since an equivalent result (but not in generating function form) was given by I. Dey, Proc. Glasgow Math. Soc. 7 (1965), 61-79. For some additional aspects, see Exercise 5.13 of Enumerative Combinatorics, vol. 2. $\endgroup$ – Richard Stanley Jun 13 '17 at 5:16
  • $\begingroup$ @RichardStanley Thank you Stanley for you comment. I should have guessed that your book discusses this problem! I added a reference to Dey's paper. $\endgroup$ – Ofir Gorodetsky Jun 13 '17 at 5:54
  • $\begingroup$ Thank you very much for your answer ! The papers are very interesting. If you would have comment on further questions: 1) The RHS of q-analog looks different from the orginal formula - how to get q->1 limit ? or we get different fomula 2) The q-analog does not seem to apply to infinite group, in particular Z^n, so not clear how to describe e.g. n-tuples of commuting elements. $\endgroup$ – Alexander Chervov Jun 18 '17 at 17:03
  • $\begingroup$ @RichardStanley is q-analog discussed in your book ? (Sorry I do not have EC2). Is the number of commuting m-tuples in GL(n,F_q) known ? (For S_n it follows from the formula, but q-analog mentioned by Ofir does not seems to apply). $\endgroup$ – Alexander Chervov Jun 18 '17 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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