General bound for the number of subgroups of a finite group

Question

I am interested in the following:

Let $G$ be a finite group of order $n$. Is there an explicit function $f$ such that $|s(G)| \leq f(n)$ for all $G$ and for all natural numbers $n$, where $s(G)$ denotes the set of subgroups of $G$?

Answer 1

A non-identity subgroup of a group of order $n$ can be generated by $\log_{2}(n)$ or fewer elements. There is quite a lot of duplication, but if you count the number of subsets of $G$ of cardinality at most $\log_{2}(n),$ you will have an upper bound (which could be made more precise with more care) and the case of elementary Abelian $2$-groups show that such a bound is of the right general shape if it is to cover all groups of all orders.

To be more precise, this gives an upper bound of approximately $\log_{2}(n)n^{\log_{2}(n)}$ for the total number of subgroups of a group of order $n,$ which is generically rather generous. On the other hand, the number of subgroups of an elementary Abelian group of order $n= 2^{r}$ is close to $\sum_{i=0}^{r}2^{i(r-i)},$ so generally larger that $n^{log_{2}(n)/4}.$

Answer 2

A theorem of Borovik, Pyber and Shalev (Corollary 1.6) shows that the number of subgroups of a group $G$ of order $n=\lvert G\rvert$ is bounded by $n^{(\frac{1}{4}+o(1)) \log_2(n)}$. This is essentially best possible, cf. Geoff Robinsons answer above.

Answer 3

There is a variant of this question which has received a lot of attention and which may be of interest here: namely how many maximal subgroups a finite group may have. In this context the relevant conjecture is due to Wall:

Conjecture The number of maximal subgroups of a finite group G is less than the order of G.

This has been the subject of much study with the landmark work (until recently) being the result of Liebeck, Pyber and Shalev which states that the number of maximal subgroups is at most $c|G|^{3/2}$ where $c$ is an absolute constant. They also show that the conjecture is true if the group G is simple, up to a finite number of exceptions.

In very recent work it has now been shown that Wall's conjecture is not true in general. An account of the demise of the conjecture can be found here. (This is not a paper, rather it's a very engaging description of the research which resulted in counter-examples being found.)

In light of this development, the bound $c|G|^{3/2}$ mentioned above assumes greater importance. Although, as the linked document mentions, it is likely that the index $\frac32$ can be reduced a great deal.

Whether one can deduce bounds on the number of non-maximal subgroups from the results of Liebeck, Pyber and Shalev, I don't know...

Answer 4

Can refine Stefan Kohl's suggestion by taking subsets containing the identity element of $G$ and of cardinality dividing $n$.

So the upper bound is $\sum_{d>1, d| n}^n {n-1\choose d-1}$

Answer 5

In a similar vein to Geoff Robinson's answer, observe that any proper subgroup of a group of order $n$ can be generated by at most $\Omega(n) - 1$ elements, where $\Omega$ counts the number of prime factors (with multiplicity) of $n$. This is tight, with equality in the case of a product of prime cyclic groups.

This gives an upper bound of:

$$ \binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{\Omega(n) - 1} + 1$$

subgroups, where the final $+ 1$ includes $G$ itself. Now we can invoke Michael Lugo's strict upper bound from https://mathoverflow.net/a/17236/39521 to obtain a closed-form upper bound:

$$ |s(G)| \leq \left\lceil \binom{n}{\Omega(n) - 1} \dfrac{n - \Omega(n) + 2}{n - 2 \Omega(n) + 2} \right\rceil \leq \dfrac{2 \times n^{\Omega(n) - 1}}{(\Omega(n) - 1)!}$$

Note that this is tight infinitely often: in the case where $n = p$ is prime (so $G = C_p$), we get:

$$ \dfrac{2 \times p^0}{0!} = 2 $$

where the two subgroups are the trivial group and $G$ itself.