# A group theoretic interpretation of Lagarias inequality

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?

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.
• 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? – orgesleka Apr 27 at 15:23
• To any group $G$. – Lucia Apr 27 at 15:27