Editing Subgroup growth (section)

==Subgroup growth and coset representations==
Let <math> G </math> be a group, <math> U </math> a subgroup of index <math> n</math>. Then <math> G </math> acts on the set of left [[coset]]s of <math> U</math> in <math> G</math> by left shift:

:<math>g(hU)=(gh)U.</math>

In this way, <math> U </math> induces a [[homomorphism]] of <math> G </math> into the [[symmetric group]] on <math>G/U</math>. <math> G</math> acts transitively on <math>G/U</math>, and vice versa, given a transitive action of <math> G </math> on

:<math>\{1, \ldots, n\},</math>

the stabilizer of the point 1 is a subgroup of index <math> n</math> in <math> G </math>. Since the set

:<math>\{2, \ldots, n\}</math>

can be permuted in

:<math>(n-1)!</math>

ways, we find that <math>s_n(G)</math> is equal to the number of transitive [[Group action (mathematics)|<math> G</math>-actions]] divided by <math>(n-1)!</math>. Among all <math>G </math>-actions, we can distinguish transitive actions by a [[sifting argument]], to arrive at the following formula

:<math>
s_n(G) = \frac{h_n(G)}{(n-1)!} - \sum_{\nu=1}^{n-1} \frac{h_{n-\nu}(G)s_\nu(G)}{(n-\nu)!},
</math>

where <math>h_n(G)</math> denotes the number of homomorphisms

:<math>\varphi:G\rightarrow S_n.</math>

In several instances the function <math>h_n(G)</math> is easier to be approached then <math>s_n(G)</math>, and, if <math>h_n(G)</math> grows sufficiently large, the sum is of negligible order of magnitude, hence, one obtains an [[asymptotic expansion|asymptotic]] formula for <math>s_n(G)</math>.

As an example, let <math>F_2</math> be the [[free group]] on two generators. Then every map of the generators of <math>F_2</math> extends to a homomorphism

:<math>F_2\rightarrow S_n,</math>

that is

:<math>h_n(F_2)=(n!)^2.</math>

From this we deduce

:<math>s_n(F_2)\sim n\cdot n!.</math>

For more complicated examples, the estimation of <math>h_n(G)</math> involves the [[representation theory]] and [[statistical properties of symmetric groups]].