15
$\begingroup$

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

Improve this question
$\endgroup$
6
  • 6
    $\begingroup$ Yes. -- You can take $f(n) := 2^n$, which is the total number of subsets of $G$. $\endgroup$
    – Stefan Kohl ♦
    Jun 3, 2013 at 21:21
  • $\begingroup$ For n bigger than 4, you can even take a quarter of that. Gerhard "Except For Exceptions, Of Course" Paseman, 2013.06.03 $\endgroup$
    – Gerhard Paseman
    Jun 3, 2013 at 21:54
  • $\begingroup$ 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. $\endgroup$
    – Name
    Jun 3, 2013 at 22:13
  • 1
    $\begingroup$ Maximal number of subgroups of a group with $n$ elements is tabulated at oeis.org/A018216 $\endgroup$
    – Gerry Myerson
    Jun 3, 2013 at 23:53
  • $\begingroup$ 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. $\endgroup$
    – user13040
    Jun 4, 2013 at 5:09

5 Answers 5

Reset to default
23
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Regarding the last sentence, did you intend "of an elementary abelian group" instead? $\endgroup$
    – user13040
    Jun 8, 2013 at 18:12
14
$\begingroup$

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.

Improve this answer
$\endgroup$
10
$\begingroup$

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

Improve this answer
$\endgroup$
3
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Jun 4, 2013 at 0:20
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I think that if $G$ is a direct product of cyclic groups of distinct prime orders, every subgroup of $G$ is cyclic, so this seems be different from that suggested by your second sentence when there are three or more different primes (and $G$ is cyclic of squarefree order). Also, by a theorem of Guralnick and Lucchini (which uses classification of finite simple groups), that if $|G| = \prod_{i=1}^{m}p_{i}^{a_{i}}$ with the $p_{i}$ distinct primes, and $a_{j} = {\rm max}\{a_{i}\}$, then each subgroup of $G$ is generated by at most $a_{j}+1$ elements, usually less that $\Omega(n)-1$ $\endgroup$
    – Geoff Robinson
    May 3, 2019 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.