Число подгрупп группы

[B@R5uk]

Как быстро может расти число подгрупп группы G с ростом её порядка n? Как вообще подходить к этой задаче?

Единственный подход к оценке мне видится через рассмотрение наихудшего случая. Единственное, что приходит в голову — это группа

$$G=\mathbb{Z}_2^r$$

У неё каждый элемент образует группу (с нейтральным), каждая пара элементов образует группу (после замыкания) и так далее. В результате число подгрупп:

$$s=\sum\limits_{k=0}^{r}C_n^{\min(k,\;r-k)}\simeq O\left(n^{r/2}\right)=O\left(\exp\frac{\ln^2n}{2\ln 2}\right)$$

Но является ли этот пример наихудшим, и правильно ли я прикинул число подгрупп?

[dgwuqtj]

Вот тут есть обсуждение, в качестве верхней оценки на число подгрупп упоминается $O(n^{(1/4 + o(1)) \log_2 n})$

[B@R5uk]

dgwuqtj, спасибо. Оценка похоже чем-то на мою в общих чертах, хотя я и не правильно число подгрупп у $\mathbb{Z}_2^r$ почитал. Не говоря про то, что вместо n надо было взять n-1, многие подгруппы в моей формуле выше повторяются из-за того, что одну и ту же подгруппу можно задать несколькими способами. Контр-пример: у группы $\mathbb{Z}_2^4$ подгрупп вида $\mathbb{Z}_2^2$ имеется 35 штук, а не $C_{15}^2=105$.