# Upper bound for the sum of the orders in a finite group

This is a cute question that I found in ML. I thought a little bit about it and couldn't complete it to a solution.

Let $G$ be a non-cyclic finite group of order $n.$ Let $S(G)=\sum_{g \in G} o(g)$ where $o(g)$ is the order of $g$ in $G.$ Prove that $S(G)<S(\mathbb{Z}/n\mathbb{Z}).$

My thoughts:

For any $d|n,$ there is a unique cyclic subgroup of $\mathbb{Z}/n\mathbb{Z}$ of order $d,$ and the number of generators of such a cyclic subgroup is $\varphi(d).$ Therefore, $S(\mathbb{Z}/n\mathbb{Z})=\sum_{d|n} \varphi(d)d.$

Let $s_d$ be the number of elements of $G$ of order $d.$ Then $S(G)=\sum_{d|n}s_dd.$ By Frobenius theorem, the number of elements $g \in G$ s.t. $g^d=1$ is a multiple of $d,$ thus $0 \leq s_d \leq dk_d$ for some non-negative integer $k_d.$

Case 1: If for some divisor $d$ we have $dk_d=n,$ then $S(G) \leq 1+(n-1)d<1+n(n-1)/2.$

Case 2: If $dk_d \neq n$ for all divisors $d,$ then $k_d \leq \frac{n}{d}-1$ and $dk_d \leq n-d.$ Hence, $S(G) \leq \sum_{d|n}nd-d^2.$

Now we have to show that $\sum_{d|n} \varphi(d)d$ is strictly greater than the maximum of both cases 1, 2, which I couldn't prove. (I tried induction on $n,$ but it was unsuccessful!)

1. How should one prove the inequalities?

2. Is there any closed/simplified form for $\sum_{d|n} \varphi(d)d?$

Curiosity:

What is $\lim_{n \to \infty} \frac{S(G)}{S(\mathbb{Z}/n\mathbb{Z})}?$

Added: I must confess that I came up with the last question without any thinking when I was writing the whole question, which the limit, of course, is absurd if one doesn't specify a group!

-
Surely $\lim\limits_{n\to\infty}\frac{S(G)}{S({\bf Z}/n{\bf Z})}$ is going to depend on choices of $G$? – anon Apr 6 '13 at 2:25
Nice Question Ehsan $+^+$ – Babak S. Apr 6 '13 at 6:55

This is quite a difficult problem! There are two published solutions of which I am aware.

1)

The first is the answer to AMM 6636(ii) by F. Schmidt. (The problem proposer submitted this second part without solution!)

The citation is:

F. Schmidt, Richard Stong and John H. Lindsey. The American Mathematical Monthly , Vol. 98, No. 10 (Dec., 1991), pp. 970-972.

2)

The second is in the paper whose citation is:

Amiri, H., Jafarian Amiri, S. M., & Isaacs, I. M. (2009). Sums of element orders in finite groups. Communications in Algebra, 37(9), 2978-2980.

FYI: I became aware of these solutions in trying to figure out this MO problem. (As evidenced by the comment I left there.)

-
Oh! I thought it is an elementary problem. I wasn't aware of them at all. Thank you btw. – Ehsan M. Kermani Apr 6 '13 at 2:35
You're welcome! – Benjamin Dickman Apr 6 '13 at 2:40
@B.D Ah! I thought immediately of that MO problem too. – Alexander Gruber Apr 6 '13 at 4:34
@AlexanderGruber I'm waiting somewhat impatiently for that problem to be resolved. I am quite sure it will be true, but I don't have the tools at my disposal to make a serious attack. Perhaps you do! – Benjamin Dickman Apr 6 '13 at 4:39

Answers to the two easier parts of the problem:

$f(n) = \sum_{d\mid n} d\phi(d)$ is the sum of a multiplicative function over all divisors of $n$; this is itself a multiplicative function of $n$. Thus if the prime-power factorization of $n$ is $n=p_1^{r_1}\cdots p_k^{r_k}$, we know that $f(n) = f(p_1^{r_1})\cdots f(p_k^{r_k})$. Therefore it suffices to calculate $f(p^k)$ for any prime power $p^k$, and that is not difficult: the answer is $f(p^k) = 1 + (p^{2k}-1)p/(p+1)$.

$\lim_{n\to\infty} S(G)/S(\mathbb Z/n\mathbb Z)$ doesn't exist. When $G = \mathbb Z/2\mathbb Z \times \mathbb Z/2\mathbb Z \times \mathbb Z/p\mathbb Z$ (where $p$ always denotes a prime), the ratio is $7/11$, while when $G = \mathbb Z/p\mathbb Z \times \mathbb Z/p\mathbb Z$, the ratio is $(p^3-p+1)/(p^4-p^3+p^2-p+1)$ which tends to $0$.

-