# A good upper-bound for the cardinal of an interval of finite groups

This post is a relative version of General bound for the number of subgroups of a finite group

Let $[H,G]$ be a interval of finite groups with $|G:H| = n$.

Question: What is a good upper-bound of $|[H,G]|$, as a function of $n$?

If $H=\{ e\}$, then the best possible upper-bound is essentially $n^{(\frac{1}{4}+o(1)) \log_2(n)}$ (here, Corollary 1.6).
Should we expect the same in general?

There is an OEIS page for the maximal cardinal of a subgroup lattice for a group of order $n$: A018216
1, 2, 2, 5, 2, 6, 2, 16, 6, 8, 2, 16, 2, 10, 4, 67, 2, 28, 2, 22, 10, 14, 2, 54, 8, 16, 28, 28, 2, 28, 2, 374, 4, 20, 4, 78, 2, 22, 16, 76, 2, 36, 2, 40, 12, 26, 2, 236, 10, 64, 4, 46, 2, 212, 14, 98, 22, 32, 2, 80, 2, 34, 36, 2825, 4, 52, 2, 58, 4, 52, 2, 272

I didn't find an OEIS page for the maximal cardinal of an interval of finite groups, at index $n$.
This should be computable for the indices $<32$, using GAP or MAGMA.

Remark: Because an element $K \in [H,G]$ admits a unique partition by cosets $Hg$, we have:
$$|[H,G]| < \sum_{k \mid n} {n \choose k}$$ See this post for a discussion on the estimate of this sum.
We have slightly better with $\sum_{k>1, k|n}^n {n-1\choose k-1}$.

• A pretty good estimate is (n-1) choose ((n/p) - 1) for p the smallest prime factor of n. This is because sum of n choose i for i ranging from 0 to j is dominated by (n choose j)( 1 + j/(n-2j+1)), which is less than (3/2)(n choose j) when 4j is at most n. Even if n is divisible by twelve, the sum is less than (n choose (n/4))/2 + n choose n/2 + n choose n/3 + n choose n/4. Gerhard "How Close Do You Need?" Paseman, 2016.06.03. – Gerhard Paseman Jun 3 '16 at 21:24
• @GerhardPaseman: As close as possible. We are more interested in an estimate, as for the full subgroup lattice, of the form $n^{(\frac{1}{4}+o(1)) \log_2(n)}$. – Sebastien Palcoux Jun 3 '16 at 21:45
• Is it even clear that the interval has at least (n-1) choose ((n/p)-1) subgroups? If so, then the answer will be close to this value. Otherwise I suspect the sum over k dividing n of n choose k will be too far off. Gerhard "Binomial Coefficients Are Big Hammers" Paseman, 2016.06.03. – Gerhard Paseman Jun 3 '16 at 21:57
• Similar question: math.stackexchange.com/q/1331326/84284 – Sebastien Palcoux Jun 5 '16 at 11:34

A chain in $[H,G]$ has length $\leq\Omega(|G:H|)$, where $\Omega$ denotes the number of prime factors counted with multiplicity. If $H=H_0<H_1<\dots<H_k=G$ is a maximal chain, then there are elements $g_1, \ldots, g_k$, such that $H_i=\langle H_{i-1}, g_i\rangle$. If $g_iH=g_i'H$, then $\langle g_i H_{i-1}\rangle = \langle g'_i H_{i-1}\rangle$, hence, the number of subgroup chains is bounded above by the number of sequences of cosets of $H$ in $G$, of length $\leq\Omega(|G:H|)$. Hence for $n=|G:H|$ the number of subgroups is $\leq \Omega(n) \frac{n!}{(n-\Omega(n))!}$ $\le\Omega(n) n^{\Omega(n)}$ $\leq \log_2(n) n^{\log_2(n)}$ $\leq n^{1+\log_2(n)}$.
To gain the missing factor 4 in the exponent you have to use the fact that there are different choices for the $g_i$, and that a group $K$ can occur in many different chains. However, this will be quite difficult. If you look at $C_p^n$, you see that most subgroups have index $\approx p^{n/2}$, thus a local argument will not work.
The same reasoning applies when $H \lhd G$ as when $H = 1$, so when $H \lhd G$ the general bound can't be improved. Since the worst case of the general bound occurs when $G$ is Abelian, you can't really expect any improvement (if $H \lhd G$ and $G/H$ is an elementary Abelian $2$-group, the number of subgroups between $H$ and $G$ will be close to $n^{\frac{\log_{2}(n)}{4}}$). In any case, an argument like that given in my answer to the previous question shows that there is a general upper bound of around $\log_{2}(n) n^{\log_{2}(n)}$ (this is similar to, but cruder than, the argument in the above answer of Jan-Christoph Schlage-Puchta).