Let \(G\) be generated by \(n\) elements. Find an upper bound \(N(n,k)\) for the number of subgroups \(H\le G\) with \[ [G:H]=k. \]
Solution
Fix generators \[ g_1,\ldots,g_n \] of \(G\).
1. The number of homomorphisms\[ \rho:G\longrightarrow S_k \]is at most\[ (k!)^n. \]
A homomorphism is uniquely determined by the images of the generating set \[ g_1,\ldots,g_n. \] Each generator has at most \[ \abs{S_k}=k! \] possible images. Thus there are at most \((k!)^n\) homomorphisms.
2. Let \(H\leq G\) have index \(k\). Every bijection\[ \beta:G/H\longrightarrow\{1,\ldots,k\} \]with\[ \beta(H)=1 \]defines a homomorphism\[ \rho_{H,\beta}:G\longrightarrow S_k \]whose stabilizer of \(1\) is exactly \(H\).
The group \(G\) acts on its left cosets by \[ g\cdot xH=(gx)H. \] Transport this action through \(\beta\) to obtain \(\rho_{H,\beta}\). An element \(g\in G\) fixes \(1=\beta(H)\) exactly when \[ gH=H, \] which is equivalent to \(g\in H\). Hence \[ \operatorname{Stab}_{\rho_{H,\beta}}(1)=H. \]
3. For a fixed index-\(k\) subgroup \(H\), the\[ (k-1)! \]bijections \(\beta\) satisfying \(\beta(H)=1\) give distinct homomorphisms\(\rho_{H,\beta}\).
There are \((k-1)!\) such bijections because the remaining \(k-1\) cosets may be labeled arbitrarily by \(2,\ldots,k\).
Suppose two such labelings \(\beta\) and \(\beta'\) give the same homomorphism. Then \[ \sigma\coloneqq\beta'\beta^{-1} \] is a permutation of \(\{1,\ldots,k\}\) that fixes \(1\) and commutes with the common transitive \(G\)-action. For any point \(j\), transitivity gives \[ j=\rho(g)(1) \] for some \(g\in G\). Therefore \[ \sigma(j) = \sigma\rho(g)(1) = \rho(g)\sigma(1) = \rho(g)(1) =j. \] Thus \(\sigma\) is the identity, so \(\beta=\beta'\).
4. Homomorphisms arising from two distinct index-\(k\) subgroups aredistinct.
By step 2, the subgroup can be recovered from the homomorphism as the stabilizer of \(1\). Therefore one homomorphism cannot arise from two different subgroups.
5. If \(M(n,k)\) denotes the number of index-\(k\) subgroups of \(G\), then\[ M(n,k)(k-1)!\leq(k!)^n. \]
By steps 3 and 4, every index-\(k\) subgroup contributes \((k-1)!\) distinct homomorphisms \(G\to S_k\), and the contributions from different subgroups are disjoint. Step 1 bounds the total number of homomorphisms.
6. One may take\[ \boxed{ N(n,k) = \frac{(k!)^n}{(k-1)!} = k(k!)^{n-1} }. \]
Divide the inequality in step 5 by \((k-1)!\).
7. Q.E.D.
Step 6 gives an upper bound depending only on \(n\) and \(k\).