Let $G$ be a finite group, $S \subset G$ a generating set. Set $\sigma(G):=\sum_{U \subset G} |U| $, where the sum runs over all subgroups $U$ of $G$. Set $H_G := \sum_{g \in G} \frac{1}{|g|+1}$, where $|g|:= $ word length (with respect to $S$). For $G:=\mathbb{Z}/(n)$ we get $\sigma(G) = \sigma(n)=$ sum of divisors of $n$. and $H_{\mathbb{Z}/(n)} = H_n=n$-th harmonic number, where $S=\{+1\}$. My naive conjecture inspired by Lagarias inequality is $$ \sigma(G) \le H_G + \exp(H_G) \log(H_G)$$

For $G:=\mathbb{Z}/(n)$ and $S:=\{+1\}$ this is the Lagarias inequality. I have checked in Sagemath for the symmetric group up to $n=6$:

def sigmaGr(G):
    return sum([len(U.list()) for U in (G.subgroups())])

def wordLen(g):
    return g.length()

def HG(G):
    return sum([1/(wordLen(g)+1) for g in G.list()])

def LG(G):
    H = HG(G)
    return (H+exp(H)*log(H)).N()

for n in range(1,6):
    G = SymmetricGroup(n)
    print sigmaGr(G),LG(G)

My question is, if this inequality can be proved for the generating set $S:=G$ or if there are finite groups and generating sets for which this inequality is false?

For $S=G$ it is $H_G=(|G|+1)/2$ and for $G$ the cyclic group, the inequality reduces to

$$\sigma(n)\le (n+1)/2+\exp((n+1)/2)\log((n+1)/2)$$

so the question is if one can prove this inequality?

Related: https://math.stackexchange.com/questions/3204237/a-group-theoretic-interpretation-of-lagarias-inequality

Edit 24.05.2019: It seems that it is better to define $\sigma(G)$ as $= \sum_{H \le G} [G:H]$ which in the case of cyclic groups is equal to the first definiton $=\sigma(n)$. Also this notion of $\sigma(G)$ is related to the zeta function of the finite group $G$ as we have:

$$\zeta_G(-1) = \sigma(G)$$

where $$\zeta_G(s) = \sum_{H \le G} \frac{1}{[G:H]^s}$$


The general inequality is interesting, but the special case you want is easy to prove -- at least if $n$ is large, but the proof can easily be quantified.

Note that every finite group $G$ of size $n$ can be generated by at most $\lfloor \log n/\log 2 \rfloor$ elements. You can see this greedily. Suppose a set $S$ generates a subgroup of $G$ of size $k$. Add an element not in this subgroup to $S$. The group generated by $S$ plus this element has size at least $2k$.

Therefore the number of subgroups of $G$ is bounded by the number of all possible subsets of $G$ with size at most $\lfloor \log n/\log 2\rfloor$, which is $$ \sum_{k=0}^{\lfloor \log n/\log 2\rfloor} \binom{n}{k}. $$ (See also General bound for the number of subgroups of a finite group ) Thus $$ \sigma(G) \le n \sum_{k=0}^{\lfloor \log n/\log 2\rfloor} \binom{n}{k} =\exp(O((\log n)^2), $$ which is certainly smaller than $\exp(n/2)$. It should be easy enough to compute a reasonable value of $n$ from which the inequality holds.

  • $\begingroup$ Thank you for your answer. Does this apply to the general case where $G$ is an arbitrary finite group, or only where $G$ is the cyclic group? $\endgroup$ – orgesleka Apr 27 at 15:23
  • $\begingroup$ To any group $G$. $\endgroup$ – Lucia Apr 27 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.