# General bound for the number of subgroups of a finite group

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

-
Yes. -- You can take $f(n) := 2^n$, which is the total number of subsets of $G$. –  Stefan Kohl Jun 3 '13 at 21:21
For n bigger than 4, you can even take a quarter of that. Gerhard "Except For Exceptions, Of Course" Paseman, 2013.06.03 –  Gerhard Paseman Jun 3 '13 at 21:54
It seems that among all groups of order $n$, the abelian group whose $p$-sylow subgroups are $p$-elementary has the largest number of subgroups and it is not difficult task to count them. –  Name Jun 3 '13 at 22:13
Maximal number of subgroups of a group with $n$ elements is tabulated at oeis.org/A018216 –  Gerry Myerson Jun 3 '13 at 23:53
It seems that elementary abelian $p$-groups dominate. Since these groups have $\Theta (p^{\frac{(\log n)^2}{4}}) = \Theta(n^{c \log n})$, it is plausible that some sub-exponential bound of this sort holds for all finite groups, but I am not aware of any relevant work. –  user13040 Jun 4 '13 at 5:09

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}.$

-
Regarding the last sentence, did you intend "of an elementary abelian group" instead? –  user13040 Jun 8 '13 at 18:12
Ye, I meant the elementary Abelian case, but I meant elementary Abelian 2-group. –  Geoff Robinson Jun 8 '13 at 18:27

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...

-

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

-
By considering inverses, you can cut the figure down further unless there are a lot of elements of order 2. For that case you can look at the subproblem of counting vector spaces over F_2. Gerhard "Which Has Already Been Studied" Paseman, 2013.06.03 –  Gerhard Paseman Jun 4 '13 at 0:20