3

Prove that in a finite group $G$ the number of subgroups of index $n$ is at most $n^{2\text{log}_2{|G|}}$.

I think it has something to do with the fact that a finite group $G$ can be generated by a subset of at most $\text{log}_2{n}$ elements, but I don't see the connection.

Teddy
  • 31
  • This sounds like an abstract algebra homework problem. – JoshuaZ Oct 23 '21 at 23:23
  • @JoshuaZ: No it does not look as an abstract algebra HW. Note the $\log$. By the way, should it be $\log_2|G|$ in the second paragraph? – markvs Oct 23 '21 at 23:27
  • @markvs Yes, you are right. – Teddy Oct 23 '21 at 23:52
  • @JoshuaZ this problem was given at Miklos Schweitzer so is definitely a hard problem. – Teddy Oct 23 '21 at 23:52
  • The problem reduces to finding the number of transitive actions of the free group with $k$ generators on an $n$-element set (up to conjugacy by a permutation of the set). The claim is that it is at most $n^{2k}$. – markvs Oct 24 '21 at 00:14
  • @Teddy . I withdraw my comment. In fact, I thought this followed from the Lemma that a finite group $G$ has a generating set with at most $\log_2 |G|$ elements, but the steps to get there are not obvious. – JoshuaZ Oct 24 '21 at 00:20
  • @Teddy: Are you sure the result is correct? Where did you get it from? – markvs Oct 24 '21 at 00:37
  • 1
    This seems to be Problem 4 in the 1996 Miklós Schweitzer competition. There is a book with solutions for the problems from 1962 - 1991, for this problem I don't find a solution online. – spin Oct 24 '21 at 04:19
  • @spin: Is there a file on the Web containing the problem? – markvs Oct 24 '21 at 06:38
  • @markvs: Here: link – spin Oct 24 '21 at 06:53
  • @spin: This does not link to the problem, but to several large collections of problems. It is not clear at all that this problem is there. – markvs Oct 24 '21 at 08:05
  • 2
    @markvs Subgroup growth of free groups is known, and Corollary 2.1.2 in the Lubotzky-Segal book says that $F_k$ has $\ge n!^{k-1}$ subgroups of index $n$ for every $n$. This is much more than $n^{2k}$. But I don't see contradiction with the original claim, just that it doesn't boil down to free groups. – YCor Oct 24 '21 at 08:15
  • Here is a link to the formulation (in English): https://artofproblemsolving.com/community/c7h2691653p23365317 It differs from the OP but not significantly. – markvs Oct 24 '21 at 08:27
  • @markvs: Well, as mentioned in my comment it is Miklós Schweitzer, 1996, Problem 4. It is there a few clicks away. Unfortunately it doesn't seem to be possible to give a direct link from that website. – spin Oct 24 '21 at 08:55
  • @spin: I have posted a direct link – markvs Oct 24 '21 at 10:19
  • 2
    The number of subgroups of index $n$ in $G$ is at most $nd$, where $d$ is the number of conjugacy classes of subgroups of index $n$ in $G$. Then $d$ is the number of transitive $G$-sets $X$, up to equivalence. Let $b$ be the minimal base size in such a $X$, and let $r$ be the size of a minimal generating set in $G$. The action of any of the generators is determined by the action on $b$ points in a minimal base, so $d \leq n^{br}$. It is known that $b,r \leq \log_2 |G|$ so there are $\leq n^{1+(\log_2|G|)^2}$ subgroups of index $n$. Not sure how to get $2 \log_2|G|$.. – spin Oct 24 '21 at 14:01
  • 1
    The number of subgroups of index $n$ is at most the number of transitive actions of $G$ on ${1,2,...,n}$ (because for every subgroup $H$, $G$ acts transitively on the Schreier graph $G/H$ and for every transitive action of $G$ on ${1,2,...,n}$ the stabilizer of $1$ has index $n$. ) – markvs Oct 24 '21 at 18:45
  • @spin: Why is $b<\log_2 |G|$? The fact that $r<\log_2 |G|$ is easy. – markvs Oct 25 '21 at 03:38
  • What about the answers of the following post? https://mathoverflow.net/q/132675/34538 – Sebastien Palcoux Oct 25 '21 at 04:49
  • 1
    @markvs: The proof is similar as the usual one for $r \leq \log_2 |G|$. Say $B = {\alpha_1, \ldots, \alpha_b }$ is a minimal base. Denote by $H_k$ the intersection of the stabilizers $H_k = \bigcap_{j = 1}^k G_{\alpha_j}$, for $1 \leq k \leq b$. (So $H_b = {1}$ since $B$ is a base.) Then $G = H_0 > H_1 > \cdots > H_b = {1}$. By minimality the inclusions $H_i > H_{i+1}$ are proper, so $|G| = [H_0 : H_1][H_1:H_2] \cdots [H_{b-1} : H_b] \geq 2^b$. – spin Oct 25 '21 at 05:08

0 Answers0