# Upper bounds for the number of intermediate subgroups

Assume that $G$ is a finite group, and $H\le G$ a subgroup of index $n>1$.

What can we say about the number of distinct intermediate subgroups $K$, i.e. groups such that $H\subset K\subset G$?

Thoughts: No matter how large $n$ is, it is possible that no such subgroups $K$ exist. An example of that is: $G=S_n$ and $H=S_{n-1}$ (= a point stabilizer).

Therefore the general lower bound is trivial, but upper bounds are more interesting. Let us denote by $S(n)$ the maximum number of such intermediate subgroups (keep $n$ fixed, but allow $G$ and $H$ to vary any which way you want as long as $[G:H]=n$).

To get a simple upper bound we can do the following. Assume that $K$ is such a subgroup with $[K:H]=d$, $1<d<n, d\mid n$. Then, in addition to $H$, $K$ contains $d-1$ cosets of $H$. There are $\binom{n-1}{d-1}$ ways of selecting those. This gives us a trivial upper bound $$S(n)\le\sum_{d\mid n, 1<d<n}\binom{n-1}{d-1}.$$ This bound is tight in the case $n=4$, because $H\unlhd G, G/H\cong K_4$ meets it. In general it is clearly loose. Also we already see that the prime factor $p=2$ of $n$ may contribute a lot.

Because $d=n/2$ is the largest possible value, the above bound implies as a weaker version $$S(n)\le\sum_{i=1}^{n/2-1}\binom{n-1}{i}=2^{n-2}-1.$$

Motivation: This question arises as the Galois correspondence translation of the question asking for bounds on the number of intermediate subfields between a perfect field $K$ and its degree $n$ extension $F$. See this question and this question.

• The case $|H|=1, |G|=n$, has surely been studied. I included the more general variant in case it matters, because it is needed in the field-theoretical application.
• In the case of a fixed $K$ the field-theoretical application needs, in addition to more precise information about $S(n)$, also an affirmative answer to the inverse Galois theory question of realizing $G$ as a Galois group $Gal(F/K)$.
• Some light may be shed by László Pyber, Groups of intermediate subgroup growth and a problem of Grothendieck, Duke Math. J. Volume 121, Number 1 (2004), 169-188 (possibly available, if you have a subscription, via projecteuclid.org/euclid.dmj/1072058752). The abstract says, Let $f$ be a function such that for every $\epsilon>0$, $n^{\log n}\le f(n)\le n^{\epsilon n}$ holds if $n$ is sufficiently large. Suppose that $\log f(n)/\log n$ is nondecreasing. [Continued...] Commented Jun 19, 2015 at 10:47
• [...continuation] For every such $f$ we construct a 4-generator group $\Gamma$ such that $s_n(\Gamma)$, the number of subgroups of index at most $n$ in $\Gamma$, grows like $f(n)$. Even if this result is not directly applicable, there may be useful ideas or information in the paper. Commented Jun 19, 2015 at 10:49
• The topic of "subgroup growth" is usually studied for infinite groups, but on page 4 of sfu.ca/~arajaram/files/subgroupgrowth.pdf the author stops to pay some attention to finite groups. Commented Jun 19, 2015 at 10:55
• In fact I don't know whether my claim about elementary abelian $2$-groups has been proved, so I have deleted my previous comment. The problem is discussed in mathoverflow.net/questions/132675 Commented Jun 19, 2015 at 11:28

This is an annotated summary of what I learned from the study of Geoff's answer in MO and the material Gerry linked to.

Adding an element to a finite group not already in it at least doubles its size. Therefore any subgroup $K, H\subset K\subset G,$ is generated by at most $\log_2n$ cosets of $H$. There are $n$ choices for each coset, so we get (a not too tight) upper bound $$S(n)\le n^{\log_2n}=2^{(\log_2n)^2}.$$ As a special case where we get a large number of such subgroups let us consider the case $H\unlhd G$, where $G/H$ is an elementary abelian 2-group, $n=2^k.$

Then we can view $G/H$ as a $k$-dimensional subspace over the field of two elements and all the subgroups are also subspaces. The number of $\ell$-dimensional subspaces, $0<\ell<k,$ is $$N(\ell)=\frac{(2^k-1)(2^k-2)(2^k-4)\cdots(2^k-2^{\ell-1})} {(2^\ell-1)(2^\ell-2)(2^\ell-4)\cdots (2^\ell-2^{\ell-1})}.$$ Here the numerator counts the number of ordered linearly independent subsets of size $\ell$, and the denominator does the same when we constrain the subset to come from a specific $\ell$-dimensional subspace. This has been explained in detail on our site many times.

By approximating each of the factors in the above formula by its leading term we get the rough estimate $N(\ell)\approx2^{\ell(k-\ell)}$. Clearly the term $N(k/2)\approx 2^{k^2/4}$ dominates in the sum $S(G/H)=\sum_{\ell=1}^{k-1}N(\ell)$.

This shows that the maximum is of approximate form $$S(n)=2^{C\cdot(\log_2n)^2}$$ for some constant $C\in[1/4,1]$.

• Accepting this for now to let the question drift to the background. If somebody has something to add, I will gladly upvote and accept that instead. Commented Jun 26, 2015 at 16:21
• Perhaps my recent (duplicate) MO question admits answers with something new: mathoverflow.net/q/240351/34538 Commented Jun 5, 2016 at 11:30