11
$\begingroup$

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}$$

$\endgroup$

1 Answer 1

10
$\begingroup$

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.

$\endgroup$
2
  • $\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$
    – user6671
    Apr 27, 2019 at 15:23
  • $\begingroup$ To any group $G$. $\endgroup$
    – Lucia
    Apr 27, 2019 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.