# Characterizing Finite Groups Using the Sum of the Orders of the Elements

Authors: Joshua Harrington; Lenny Jones; Alicia Lamarche
Journal: International Journal of Combinatorics
 (2014)

---

## Abstract

We give characterizations of various infinite sets of finite groupsG under the assumption that G and the subgroups H of G satisfy certain properties involving the sum of the orders of the elements of G and H. Additionally, we investigate the possible values for the sum of the orders of the elements of G.


---

## Body

## 1. Introduction

For any nonempty subsetX of a finite group G, we let ψ
(
X
) denote the sum of the orders of all elements of X (counting multiplicities). Amiri et al. [1] gave a characterization of cyclic groups using ψ. They showed that if C is a cyclic group and G is a noncyclic group of the same order, then ψ
(
G
)
<
ψ
(
C
). In 2011, H. Amiri and S. M. J. Amiri [2] turned their attention to the minimum value of ψ
(
G
), and they showed that, for nilpotent groups of a fixed order, the minimum value is attained when each Sylow subgroup has prime exponent. In addition, they showed that if there exists a nonnilpotent group of fixed order n, then the minimum value of ψ
(
G
), as G ranges over all groups of order n, will be attained for a nonnilpotent group. Moreover, this minimum value of ψ on such a nonnilpotent group is strictly smaller than the value of ψ on any nilpotent group of order n. In the same article, H. Amiri and S. M. J. Amiri conjectured that if H is a simple group and G is a nonsimple group of order |
H
|, then ψ
(
H
)
<
ψ
(
G
). However, this conjecture has recently been shown to be false [3]. In 2012, H. Amiri and S. M. J. Amiri [4] showed that ψ
(
H
)
<
ψ
(
A
n
) for all proper subgroups H
≠
A
n of S
n, where S
n is the symmetric group and A
n is the alternating group.In this paper, we give characterizations of various infinite sets of finite groupsG, given certain restrictions on ψ
(
G
) or ψ
(
H
) (or both), where H is a proper subgroup of G. More precisely, we prove the following.Theorem 1.
LetG be a finite abelian group. Then ψ
(
H
) divides ψ
(
G
) for every subgroup H of G if and only if G is cyclic of square-free order.Theorem 2.
LetG be a finite abelian group. Then ψ
(
H
)
<
|
G
| for every proper subgroup H of G if and only if
(1)
G
≃
Z
p
2
o
r
G
≃
Z
p
n
=
Z
p
×
⋯
×
Z
p
︸
n
-
f
a
c
t
o
r
s
,
for any prime p and any positive integer n.Theorem 3.
For any fixedϵ
>
0, there exist infinitely many finite groups G, both abelian and nonabelian that satisfy the conditions in each of the following situations: (1)
ψ
(
G
)
<
|
G
|
1
+
ϵ,
(2)
ψ
(
G
)
>
|
G
|
2
-
ϵ.Theorem 4.
Letn be a positive integer. Then
(2)
ψ
S
n
≤
n
!
log
⁡
(
3
)
/
log
⁡
(
2
)
∀
n
≥
1
.
Moreover, the number log
⁡
(
3
)
/
log
⁡
(
2
) is the smallest possible constant C such that ψ
(
S
n
)
≤
n
!
C for all n
≥
1.


## 2. Preliminaries and Notation

We assume that all groups in this paper are finite. For an elementg in a group G, we let o
(
g
) denote the order of g in G. For a group G, a prime p that divides |
G
|, and a positive integer z, we define
(3)
G
p
z
=
g
∈
G
∣
o
(
g
)
=
p
z
.
We let S
n and A
n denote, respectively, the symmetric group and the alternating group on the set {
1,2
,
…
,
n
}. We let ϕ denote Euler’s totient function.We now state, without proof, two useful results from the literature, the first of which was mentioned previously in Section1.Theorem 5 (see [1]).
IfC is a cyclic group and G is a noncyclic group of the same order, then ψ
(
G
)
<
ψ
(
C
).Lemma 6 (see [2]).
IfH and K are finite groups, then ψ
(
H
×
K
)
≤
ψ
(
H
)
ψ
(
K
), with equality if and only if g
c
d
(
|
H
|
,
|
K
|
)
=
1.The following lemma, which we also state without proof, is a special case of Theorem A in [2].Lemma 7.
Letp be a prime and let n be a positive integer. If G is an abelian group with |
G
|
=
p
n, then
(4)
ψ
(
G
)
≥
ψ
Z
p
n
.Lemma7 shows that the minimum value of ψ
(
G
), as G ranges over all abelian p-groups of fixed order p
n is achieved on the elementary abelian group of that order. Lemma 7 will be useful in proving Theorem 2.While not difficult to prove, the next proposition does not currently appear in the literature and will be useful throughout this paper. This result determines formulas forψ
(
G
) in specials cases.Proposition 8.
Leta and n be positive integers, and let p be a prime.Proof.
Letz
≤
a be a positive integer. Observe that ∑
s
=
0
z
‍
ϕ
(
p
s
)
=
p
z. Hence, the number of elements of order p
z in G is
(5)
∑
r
=
1
n
‍
n
r
ϕ
p
z
r
∑
s
=
0
z
-
1
‍
ϕ
p
s
n
-
r
=
p
z
n
-
p
(
z
-
1
)
n
,
and therefore
(6)
ψ
G
p
z
=
p
z
p
z
n
-
p
(
z
-
1
)
n
.
Thus,
(7)
ψ
G
=
1
+
∑
z
=
1
a
‍
ψ
G
p
z
=
1
+
∑
z
=
1
a
‍
p
z
p
z
n
-
p
(
z
-
1
)
n
=
p
(
n
+
1
)
(
a
+
1
)
-
p
a
(
n
+
1
)
+
1
+
p
-
1
p
n
+
1
-
1
.


## 3. The Proof of Theorem1

For the sake of convenience, we say thatG is a ψ-divisible group if ψ
(
H
) divides ψ
(
G
) for all subgroups H of G. We can deduce the following result concerning ψ-divisible groups from Lemma 6.Lemma 9.
LetH and K be finite groups with g
c
d
(
|
H
|
,
|
K
|
)
=
1, and let G
≃
H
×
K. Then G is a ψ-divisible group if and only if both H and K are ψ-divisible groups.Proof.
Suppose first thatG is a ψ-divisible group. Assume, by way of contradiction and without loss of generality, that K is not ψ-divisible. Then there is some subgroup B of K such that ψ
(
B
) does not divide ψ
(
K
). Consider the subgroup H
×
B of G. Using Lemma 6, since G is a ψ-divisible group, we have that
(8)
ψ
H
ψ
B
k
=
ψ
H
×
B
k
=
ψ
G
=
ψ
H
ψ
K
,
for some positive integer k. But then ψ
(
B
)
k
=
ψ
(
K
), which contradicts our assumption that ψ
(
B
) does not divide ψ
(
K
).
Suppose now that bothH and K are ψ-divisible, and let W be a subgroup of G. Since gcd(
|
H
|
,
|
K
|
)
=
1, it follows that W
≃
A
×
B, where A is a subgroup of H, and B is a subgroup of K. Then, by Lemma 6, we have that
(9)
ψ
(
G
)
ψ
W
=
ψ
H
ψ
A
ψ
K
ψ
B
∈
Z
,
which implies that G is a ψ-divisible group.In light of Lemma9, it is enough to focus our attention on p-groups, where p is a prime. Recall for a given positive integer z and a prime p that divides |
G
| that G
p
z is the subset of G containing all elements of order p
z in G. Note that ψ
(
G
p
z
)
≡
0
(
mod
⁡
p
) when z
≥
1. Two obvious, but useful, consequences of this observation are given below.Lemma 10.
Letp be a prime and let G be a p-group. Then ψ
(
G
)
≡
1
(
mod
⁡
p
).Proof.
Letp
a be the exponent of G. Then
(10)
ψ
G
=
∑
i
=
0
a
‍
ψ
G
p
i
=
1
+
∑
i
=
1
a
‍
ψ
G
p
i
≡
1
mod
⁡
p
.Corollary 11.
Letp be a prime and let G be a p-group. If G is a ψ-divisible group and H is any proper subgroup of G, then
(11)
ψ
(
G
)
ψ
(
H
)
≥
p
+
1
.Lemma 12.
Leta and n be positive integers, and let p be a prime. Suppose that G
≃
(
Z
p
a
)
n. Then G is a ψ-divisible group if and only if a
=
n
=
1.Proof.
Clearly,G is a ψ-divisible group if a
=
n
=
1, so assume that a
n
≥
2. First suppose that a
=
1, so that n
≥
2. Then, using Proposition 8 with a
=
1, we have
(12)
ψ
(
G
)
=
p
2
(
n
+
1
)
-
p
n
+
2
+
p
-
1
p
n
+
1
-
1
=
p
n
+
1
-
p
+
1
.
Let H be a subgroup of G such that H
≃
(
Z
p
)
n
-
1. Then ψ
(
H
)
=
p
n
-
p
+
1 by Proposition 8, and thus
(13)
ψ
(
G
)
ψ
(
H
)
=
p
n
+
1
-
p
+
1
p
n
-
p
+
1
=
p
+
p
2
-
2
p
+
1
p
n
-
p
+
1
∉
Z
,
since p
2
-
2
p
+
1
<
p
n
-
p
+
1. Hence, G is not a ψ-divisible group when a
=
1.
Now assume thata
≥
2, and let H be a subgroup of G such that H
≃
(
Z
p
a
-
1
)
n. Again, using Proposition 8, we can write
(14)
ψ
(
G
)
ψ
(
H
)
=
p
n
+
1
-
A
B
,
where
(15)
A
=
p
n
+
1
p
-
1
-
p
-
1
,
B
=
p
(
n
+
1
)
a
-
n
(
p
n
-
1
)
+
p
-
1
.
Since a
≥
2, it follows that A
<
B, and hence ψ
(
G
)
/
ψ
(
H
)
∉
Z. Thus, G is not a ψ-divisible group and the proof is complete.Lemma 13.
Letp be a prime and suppose that G
≃
Z
p
×
H, where
(16)
H
=
Z
p
a
1
×
Z
p
a
2
×
⋯
×
Z
p
a
t
,
is nontrivial, with a
1
≤
a
2
≤
⋯
≤
a
t. Then G is not a ψ-divisible group.Proof.
Let(
x
,
y
)
∈
Z
p
×
H, and define
(17)
A
=
(
x
,
y
)
∣
x
≠
0
,
y
≠
0
,
B
=
(
x
,
0
)
∣
x
≠
0
,
C
=
(
0
,
y
)
∣
y
∈
H
.
Then Z
p
×
H
=
A
∪
B
∪
C and
(18)
ψ
G
=
ψ
(
A
)
+
ψ
(
B
)
+
ψ
(
C
)
=
(
p
-
1
)
ψ
(
H
)
-
1
+
(
p
-
1
)
p
+
ψ
(
H
)
=
p
ψ
(
H
)
+
p
2
-
2
p
+
1
.
Thus
(19)
ψ
(
G
)
ψ
(
H
)
=
p
+
p
2
-
2
p
+
1
ψ
(
H
)
∉
Z
,
since
(20)
p
2
-
2
p
+
1
<
p
2
-
p
+
1
=
ψ
Z
p
≤
ψ
Z
p
t
≤
ψ
(
H
)
.Lemma 14.
Let(21)
G
=
Z
p
a
1
×
Z
p
a
2
×
⋯
×
Z
p
a
t
,
where a
1
≤
a
2
≤
⋯
≤
a
t are not all equal. Then
(22)
∑
i
=
0
a
t
-
1
ψ
G
p
i
ψ
G
p
a
t
<
1
p
2
-
p
.Proof.
Note thata
t
≥
2 and t
≥
2 since a
i are not all equal. Suppose that
(23)
a
1
≤
a
2
≤
⋯
≤
a
k
-
1
<
a
k
=
a
k
+
1
=
⋯
=
a
t
,
and define
(24)
b
i
=
a
i
if
i
<
k
a
i
-
1
if
k
≤
i
<
t
a
t
if
i
=
t
.
Let
(25)
G
^
=
Z
p
b
1
×
Z
p
b
2
×
⋯
×
Z
p
b
t
,
and observe that
(26)
∑
i
=
0
a
t
-
1
‍
ψ
G
p
i
=
∑
i
=
0
b
t
-
1
‍
ψ
G
^
p
i
,
ψ
G
p
a
t
≥
ψ
G
^
p
b
t
.
Thus, we may assume without loss of generality that k
=
t. Let H be a subgroup of G such that
(27)
H
≃
Z
p
a
1
×
Z
p
a
2
×
⋯
×
Z
p
a
t
-
1
.
Since ψ
(
H
)
=
∑
i
=
0
a
t
-
1
ψ
(
G
p
i
), we have that
(28)
ψ
G
p
a
t
=
p
a
t
ϕ
p
a
t
∏
i
=
1
t
-
1
‍
p
a
i
=
(
p
2
-
p
)
p
2
a
t
-
2
+
∑
i
=
1
t
-
1
a
i
>
(
p
2
-
p
)
p
2
a
t
-
2
+
∑
i
=
1
t
-
1
a
i
-
p
a
t
-
1
+
1
=
(
p
2
-
p
)
p
a
t
-
1
p
a
t
-
1
∏
i
=
1
t
-
1
‍
p
a
i
-
1
+
1
≥
(
p
2
-
p
)
ψ
(
H
)
=
(
p
2
-
p
)
∑
i
=
0
a
t
-
1
‍
ψ
G
p
i
,
from which the lemma follows.We are now in a position to establish Theorem1. For the convenience of the reader, we restate Theorem 1 below as Theorem 15 using the ψ-divisible terminology.Theorem 15.
LetG be an abelian group. Then G is a ψ-divisible group if and only if G is cyclic of square-free order.Proof.
IfG is cyclic of square-free order, then the fact that G is a ψ-divisible group follows immediately from Lemma 6. So, now assume conversely that G is a ψ-divisible group. To establish the theorem, it is enough, by Lemmas 6, 12, and 13, to show for a prime p that
(29)
G
=
Z
p
a
1
×
Z
p
a
2
×
⋯
×
Z
p
a
t
,
where t
≥
2 with 2
≤
a
1
≤
a
2
≤
⋯
≤
a
t not all equal, is not a ψ-divisible group. Let G be as in (29), and assume by way of contradiction that G is a ψ-divisible group. Let H be a subgroup of G with
(30)
H
≃
Z
p
a
1
-
1
×
Z
p
a
2
×
Z
p
a
3
×
⋯
×
Z
p
a
t
.
Note that ψ
(
G
p
a
t
)
=
p
ψ
(
H
p
a
t
). Using this observation, Lemma 14, and Corollary 11, it follows that
(31)
1
+
1
p
2
-
p
>
1
+
∑
i
=
0
a
t
-
1
ψ
G
p
i
ψ
G
p
a
t
=
ψ
(
G
)
ψ
G
p
a
t
=
ψ
(
G
)
p
ψ
H
p
a
t
≥
ψ
(
H
)
p
ψ
H
≥
p
+
1
p
.
Using the fact that p
>
0 to solve the inequality
(32)
1
+
1
p
2
-
p
>
p
+
1
p
,
we get that 1
<
p
<
2, which is impossible, and the proof is complete.The following is immediate from Theorem15.Corollary 16.
IfG is an abelian ψ-divisible group, then every proper subgroup of G is a ψ-divisible group.Remark 17.
The converse of Corollary16 is false. For example, let G
=
Z
p
×
Z
p, where p is a prime. Then every proper subgroup of G is a ψ-divisible group, but G is not a ψ-divisible group by Lemma 12.


### 3.1. A Remark on Nonabelianψ-Divisible Groups

The nonabelian situation is much less clear than the abelian case. In fact, we have been unable to find a single nonabelianψ-divisible group, although we are somewhat hesitant to conjecture their nonexistence. On the other hand, using Lemma 9, we are able to construct infinitely many nonabelian groups that are not ψ-divisible. Since ψ
(
S
3
)
=
13, we see that S
3 is not ψ-divisible. Then, by Lemma 9, it follows that G
≃
Z
p
×
S
3 is not ψ-divisible for any prime p.


## 3.1. A Remark on Nonabelianψ-Divisible Groups

The nonabelian situation is much less clear than the abelian case. In fact, we have been unable to find a single nonabelianψ-divisible group, although we are somewhat hesitant to conjecture their nonexistence. On the other hand, using Lemma 9, we are able to construct infinitely many nonabelian groups that are not ψ-divisible. Since ψ
(
S
3
)
=
13, we see that S
3 is not ψ-divisible. Then, by Lemma 9, it follows that G
≃
Z
p
×
S
3 is not ψ-divisible for any prime p.


## 4. The Proof of Theorem2

We say a groupG is a B
ψ-group if ψ
(
H
)
<
|
G
| for all proper subgroups H of G. For the convenience of the reader, we use this new terminology to restate Theorem 2 below as Theorem 18.Theorem 18.
LetG be a finite abelian group. Then G is a B
ψ-group if and only if
(33)
G
≃
Z
p
2
o
r
G
≃
Z
p
n
,
for any prime p and any positive integer n.Proof.
Using Proposition8, it is easy to show that if
(34)
G
≃
Z
p
2
or
G
≃
Z
p
n
,
for any prime p and any positive integer n, then G is a B
ψ-group.
So, assume conversely thatG is an abelian B
ψ-group, and write
(35)
G
≃
A
1
×
A
2
×
⋯
×
A
k
,
where |
A
i
|
=
p
i
α
i and p
1
<
p
2
<
⋯
<
p
k are primes. Assume first that k
≥
2, and let H be a subgroup of G such that
(36)
H
≃
B
1
×
A
2
×
⋯
×
A
k
,
where |
B
1
|
=
p
1
α
1
-
1. We claim that ψ
(
H
)
>
|
G
|. To see this, we have
(37)
ψ
H
G
=
ψ
B
1
∏
i
=
2
k
ψ
A
i
∏
i
=
1
k
p
i
α
i
by  Lemma
6
≥
ψ
Z
p
1
α
1
-
1
∏
i
=
2
k
ψ
Z
p
i
α
i
∏
i
=
1
k
p
i
α
i
by  Lemma
7
=
p
1
α
1
-
p
1
+
1
∏
i
=
2
k
p
i
α
i
+
1
-
p
i
+
1
∏
i
=
1
k
p
i
α
i
by  Proposition
8
=
1
-
p
1
-
1
p
1
α
1
∏
i
=
2
k
‍
p
i
-
p
i
-
1
p
i
α
i
≥
1
-
p
1
-
1
p
1
∏
i
=
2
k
‍
p
i
-
p
i
-
1
p
i
=
1
p
1
∏
i
=
2
k
‍
p
i
-
1
+
1
p
i
=
p
2
-
1
p
1
+
1
p
1
p
2
∏
i
=
3
k
‍
p
i
-
p
i
-
1
p
i
>
p
2
-
1
p
1
∏
i
=
3
k
‍
p
i
-
p
i
-
1
p
i
≥
1
,
which shows that G is not a B
ψ-group if k
≥
2. Hence, assume that k
=
1 so that G is a p-group for some prime p. Suppose that |
G
|
=
p
n and write
(38)
G
≃
Z
p
α
1
×
Z
p
α
2
×
⋯
×
Z
p
α
t
,
where
(39)
α
=
α
1
≤
α
2
≤
⋯
≤
α
t
=
β
.
Assume first thatt
≥
2. Let B
≃
Z
p
α
2
×
⋯
×
Z
p
α
t
-
1, where B is trivial if t
=
2, so that |
B
|
=
p
n
-
α
-
β. Let H be a subgroup of G such that
(40)
H
≃
Z
p
α
-
1
×
B
×
Z
p
β
.
Then(41)
G
=
p
n
>
ψ
H
>
ψ
H
p
β
≥
ϕ
p
β
p
β
·
Z
p
α
-
1
×
B
=
p
n
+
β
-
2
p
-
1
.
Thus β
=
1 and G
≃
(
Z
p
)
n, where n
≥
2.
Now suppose thatt
=
1 so that G
≃
Z
p
α. Let H be the subgroup of G with H
≃
Z
p
α
-
1. Then, using Proposition 8, we have
(42)
G
=
p
α
>
ψ
H
=
p
2
(
α
-
1
)
+
1
+
1
p
+
1
>
p
2
α
-
1
p
+
1
,
which implies that p
+
1
>
p
α
-
1. Hence, α
≤
2 and G
≃
Z
p or G
≃
Z
p
2, which completes the proof of the theorem.


## 5. Investigating the Range ofψ

It is easy to get bounds onψ
(
G
) as the next proposition shows.Proposition 19.
LetG be a finite group. Then
(43)
G
≤
ψ
(
G
)
≤
G
2
,
with equality holding in both inequalities in (43) if and only if G is trivial.Proof.
For anyg
∈
G, we have that 1
≤
o
(
g
)
≤
|
G
|. Thus, the proposition follows from the definition of ψ.A natural question to ask is whether there exist nontrivial groupsG with ψ
(
G
) arbitrarily close to the bounds given in (43). Theorem 3 provides an affirmative answer to this question.


### 5.1. The Proof of Theorem3

Proof of Theorem3.
To prove part (1) of Theorem3, first let G
≃
S
3
×
(
Z
p
)
n, where p
≥
13 is a prime and n is a positive integer. Then, using Lemma 6, and Proposition 8 with a
=
1, we have that
(44)
ψ
(
G
)
=
ψ
S
3
ψ
Z
p
n
=
13
p
n
+
1
-
p
+
1
.
Solving the equation
(45)
13
p
n
+
1
-
p
+
1
=
G
c
=
6
p
n
c
,
for c gives
(46)
c
=
log
⁡
13
p
n
+
1
-
p
+
1
log
⁡
6
p
n
.
Since
(47)
13
p
n
+
1
-
p
+
1
-
6
p
n
>
13
p
n
+
1
-
p
+
1
-
13
p
n
=
13
p
n
-
1
(
p
-
1
)
>
0
,
it follows that c
>
1. Then, since p
≥
13, we have
(48)
1
+
2
n
=
log
⁡
p
n
+
2
log
⁡
⁡
p
n
≥
log
⁡
13
p
n
+
1
log
⁡
⁡
p
n
>
log
⁡
13
p
n
+
1
log
⁡
(
6
p
n
)
>
c
>
1
.
A similar computation gives the same conclusion when G
≃
(
Z
p
)
n, and the proof of part (1) of Theorem 3 is complete.
To prove part (2) of Theorem3, first let G
≃
S
3
×
Z
p
a, where p
≥
13 is prime and a is a positive integer. Then, using Lemma 6, and Proposition 8 with n
=
1, we have that
(49)
ψ
(
G
)
=
ψ
S
3
ψ
Z
p
a
=
13
p
2
a
+
1
+
1
p
+
1
.
Solving the equation
(50)
13
p
2
a
+
1
+
1
p
+
1
=
G
c
=
6
p
n
c
for c gives
(51)
c
=
log
⁡
13
p
2
a
+
1
+
1
/
p
+
1
log
⁡
6
p
a
.
Since
(52)
13
p
2
a
+
1
+
13
<
36
p
2
a
+
1
+
36
p
2
a
=
36
p
2
a
(
p
+
1
)
,
it follows that c
<
2. Also, since p
2
>
p
+
1, we see that
(53)
p
2
a
-
1
<
p
2
a
-
1
·
p
2
p
+
1
=
p
2
a
+
1
p
+
1
<
p
2
a
+
1
+
1
p
+
1
.
Thus,
(54)
2
-
3
a
+
1
=
log
⁡
p
2
a
-
1
log
⁡
p
a
+
1
<
log
⁡
13
p
2
a
-
1
log
⁡
p
a
+
1
<
log
⁡
13
p
2
a
-
1
log
⁡
6
p
a
(
since
p
≥
13
)
<
c
(
by
(
53
)
)
.
Therefore,
(55)
2
-
3
a
+
1
<
c
<
2
.
A similar computation yields the same conclusion when G
≃
Z
p
a, which completes the proof of Theorem 3.


### 5.2. The Proof of Theorem4

It is clear that estimatingψ
(
S
n
) is, up to scaling, equivalent to estimating the average order μ
n
≔
ψ
(
S
n
)
/
n
! of an element in S
n. This problem was first raised by Erdös and Turán [5] in 1968 when they conjectured that
(56)
log
⁡
μ
n
=
O
n
log
⁡
n
.
Conjecture (56) was proven by Schmutz [6] in 1989 when he showed that
(57)
log
⁡
μ
n
≤
7.7
n
log
⁡
n
for
n
sufficiently  large
.
It follows from (57) that
(58)
ψ
S
n
≤
n
!
h
(
n
)
for
n
sufficiently  large
,
where
(59)
h
n
=
7.7
n
/
log
⁡
(
n
)
log
⁡
n
!
+
1
.
The proof of (57) is nontrivial and requires some very technical results concerning partitions. In 1991, Goh and Schmutz [7] sharpened (57) by proving that
(60)
log
⁡
μ
n
~
c
n
log
⁡
n
,
where
(61)
c
=
2
2
∫
0
∞
‍
log
⁡
log
⁡
e
1
-
e
-
t
d
t
.
The proof of (60) also requires some partition theory.In the spirit of Theorem3, it is our goal here to determine, if possible, the smallest possible constant C such that
(62)
ψ
S
n
≤
n
!
C
∀
n
≥
1
,
in a nontrivial manner. In other words, does there exist a smallest real number C
<
2 for which (62) is true, and can we determine it? Theorem 4 provides an affirmative answer to these questions. There are two advantages to the bound given for ψ
(
S
n
) in Theorem 4 over the results in [6, 7]. First of all, Theorem 4 is proven for all n
≥
1, not just for sufficiently large values of n. The second advantage is that the proof of Theorem 4 that we present here does not rely on any results from partition theory. We use the following result, due to Massias [8] in 1984.Theorem 20.
Letg
n denote the largest order of an element in S
n. Then
(63)
log
⁡
g
n
≤
1.05314
n
log
⁡
(
n
)
.In 1903, Landau [9] proved that log
⁡
g
n
~
n
log
⁡
(
n
), but Theorem 20 represents the first explicit upper bound for log(
g
n
). Although somewhat technical, Massias’ proof of Theorem 20 uses elementary analytic techniques requiring little more than calculus.We also need the following lemmas.Lemma 21.
Letn
≥
2 be an integer and let σ
,
τ
∈
S
n, with σ
=
(
a
b
). If τ fixes either a or b, then o
(
σ
τ
)
≤
n
·
o
(
τ
).Proof.
Observe that ifτ fixes both a and b, then
(64)
o
σ
τ
=
lcm
o
σ
,
o
τ
≤
o
σ
·
o
τ
=
2
·
o
(
τ
)
≤
n
·
o
(
τ
)
.
So, suppose that τ fixes b, but not a. Then we may write
(65)
τ
=
τ
1
τ
2
=
a
x
2
x
3
⋯
x
j
τ
2
,
for some j with 2
≤
j
≤
n
-
1, where τ
1 and τ
2 are disjoint, and x
i
≠
b for all i. Thus,
(66)
o
σ
τ
=
o
(
a
x
2
x
3
⋯
x
j
b
τ
2
)
=
lcm
j
+
1
,
o
τ
2
=
(
j
+
1
)
o
τ
2
gcd
j
+
1
,
o
τ
2
≤
n
·
o
τ
2
≤
n
·
o
τ
,
which completes the proof.Lemma 22.
Ifn
≥
4, then
(67)
n
-
1
n
3
/
2
-
1
>
n
2
-
n
.Proof.
Ifn
≥
4, then
(68)
n
2
=
n
1
/
2
·
n
3
/
2
≥
2
n
3
/
2
>
2
n
3
/
2
-
1
.
Thus,
(69)
n
3
/
2
-
1
=
n
3
/
2
-
1
2
=
n
3
-
2
n
3
/
2
-
1
>
n
3
-
n
2
=
n
n
-
1
,
from which the lemma follows.Lemma 23.
Ifn
≥
20 is an integer, then
(70)
n
-
2
!
>
e
2.10628
(
n
-
12
)
.Proof.
The lemma is easily verified forn
=
20. We proceed by induction on n. Then
(71)
n
+
1
-
2
!
=
(
n
-
1
)
(
n
-
2
)
!
>
n
-
1
e
2.10628
(
n
-
12
)
(
by  induction
)
=
n
-
1
e
2.10628
e
2.10628
(
n
-
11
)
>
e
2.10628
(
(
n
+
1
)
-
12
)
,
since n
-
1
>
e
2.10628 when n
≥
20, and the proof is complete.Lemma 24.
Letf
(
x
)
=
x
-
12
-
(
x
-
1
)
log
⁡
(
x
-
1
). Then f
(
x
)
>
0 for all x
≥
20.Proof.
The proof is straightforward using calculus.Lemma 25.
Ifn
≥
20 is an integer, then
(72)
n
-
1
!
log
⁡
3
/
log
⁡
⁡
2
-
1
n
log
⁡
3
/
log
⁡
⁡
2
-
1
>
n
(
n
-
1
)
e
1.05314
(
n
-
1
)
log
⁡
(
n
-
1
)
.Proof.
Let(73)
A
=
n
-
1
!
log
⁡
3
/
log
⁡
⁡
2
-
1
n
log
⁡
3
/
log
⁡
⁡
2
-
1
.
Since log(
3
)
/
log(2)
>
3
/
2, we have
(74)
A
>
(
n
-
1
)
!
n
3
/
2
-
1
=
n
-
1
n
3
/
2
-
1
n
-
2
!
>
n
2
-
n
e
1.05314
(
n
-
12
)
(
by  Lemmas
22
and
23
)
>
n
2
-
n
e
1.05314
(
n
-
1
)
log
⁡
(
n
-
1
)
(
by  Lemma
24
)
.Proof of Theorem4.
The proof is by induction onn. It is easy to verify computationally that the theorem is true for all n, with 1
≤
n
≤
20. For n
≥
20, let σ
1
=
(
1
) and σ
i
=
(
i
-
1
n
) for each i with 2
≤
i
≤
n. Then {
σ
1
,
σ
2
,
σ
3
,
…
,
σ
n
} is a complete set of left coset representatives for S
n
-
1 in S
n. Thus,
(75)
ψ
S
n
=
∑
i
=
1
n
‍
ψ
σ
i
S
n
-
1
=
∑
i
=
1
n
‍
∑
τ
∈
S
n
-
1
‍
o
σ
i
τ
=
ψ
S
n
-
1
+
∑
i
=
2
n
‍
∑
τ
∈
S
n
-
1
‍
o
σ
i
τ
≤
ψ
S
n
-
1
+
∑
i
=
2
n
‍
∑
τ
∈
S
n
-
1
‍
n
·
o
(
τ
)
(
by  Lemma
21
)
≤
ψ
S
n
-
1
+
∑
i
=
2
n
‍
∑
τ
∈
S
n
-
1
‍
n
·
e
1.05314
(
n
-
1
)
log
⁡
(
n
-
1
)
(
by  Theorem
20
)
=
ψ
S
n
-
1
+
(
n
-
1
)
!
·
n
(
n
-
1
)
·
e
1.05314
(
n
-
1
)
log
⁡
(
n
-
1
)
≤
n
-
1
!
log
⁡
(
3
)
/
log
⁡
(
2
)
+
(
n
-
1
)
!
·
n
(
n
-
1
)
·
e
1.05314
(
n
-
1
)
log
⁡
(
n
-
1
)
(
by  induction
)
<
n
!
log
⁡
(
3
)
/
log
⁡
(
2
)
(
by  Lemma
25
)
.In Table1, we compare the rounded values of ψ
(
S
n
), (
n
!
)
log
⁡
(
3
)
/
log
⁡
(
2
), (
n
!
)
2, and the bound for ψ
(
S
n
) given in (60), for n
=
2
,
…
,
10. The bound given in (58) is much worse for these small values of n than any bound given in Table 1, so we omit it.Table 1
Comparingψ
(
S
n
) and various upper bounds.
n
ψ
(
S
n
)
(
n
!
)
log
⁡
(
3
)
/
log
⁡
(
2
)
(
n
!
)
2
(60)
2
3
3
4
321
3
13
17
36
840
4
67
154
576
3858
5
471
1974
14400
23352
6
3271
33788
518400
171377
7
31333
738267
25401600
1464527
8
299223
19933214
1625702400
14220361
9
3291487
648658213
131681894400
154263165
10
39020911
24944707890
13168189440000
1846343649Remark 26.
The sequence{
ψ
(
S
n
)
}
n
=
1
∞ is listed in the On-Line Encyclopedia of Integer Sequences and can be found at http://oeis.org/A060014.We end with the following conjecture, which is supported by numerical evidence.Conjecture 27.
Letn be a positive integer. Then
(76)
ψ
A
n
≤
n
!
2
log
⁡
(
7
)
/
log
⁡
(
3
)
∀
n
≥
1
.
Moreover, the number log
⁡
(
7
)
/
log
⁡
(
3
) is the smallest possible constant C such that ψ
(
A
n
)
≤
(
n
!
/
2
)
C for all n
≥
1.Remark 28.
The sequence{
ψ
(
A
n
)
}
n
=
1
∞ is listed in the On-Line Encyclopedia of Integer Sequences and can be found at http://oeis.org/A060015.


## 5.1. The Proof of Theorem3

Proof of Theorem3.
To prove part (1) of Theorem3, first let G
≃
S
3
×
(
Z
p
)
n, where p
≥
13 is a prime and n is a positive integer. Then, using Lemma 6, and Proposition 8 with a
=
1, we have that
(44)
ψ
(
G
)
=
ψ
S
3
ψ
Z
p
n
=
13
p
n
+
1
-
p
+
1
.
Solving the equation
(45)
13
p
n
+
1
-
p
+
1
=
G
c
=
6
p
n
c
,
for c gives
(46)
c
=
log
⁡
13
p
n
+
1
-
p
+
1
log
⁡
6
p
n
.
Since
(47)
13
p
n
+
1
-
p
+
1
-
6
p
n
>
13
p
n
+
1
-
p
+
1
-
13
p
n
=
13
p
n
-
1
(
p
-
1
)
>
0
,
it follows that c
>
1. Then, since p
≥
13, we have
(48)
1
+
2
n
=
log
⁡
p
n
+
2
log
⁡
⁡
p
n
≥
log
⁡
13
p
n
+
1
log
⁡
⁡
p
n
>
log
⁡
13
p
n
+
1
log
⁡
(
6
p
n
)
>
c
>
1
.
A similar computation gives the same conclusion when G
≃
(
Z
p
)
n, and the proof of part (1) of Theorem 3 is complete.
To prove part (2) of Theorem3, first let G
≃
S
3
×
Z
p
a, where p
≥
13 is prime and a is a positive integer. Then, using Lemma 6, and Proposition 8 with n
=
1, we have that
(49)
ψ
(
G
)
=
ψ
S
3
ψ
Z
p
a
=
13
p
2
a
+
1
+
1
p
+
1
.
Solving the equation
(50)
13
p
2
a
+
1
+
1
p
+
1
=
G
c
=
6
p
n
c
for c gives
(51)
c
=
log
⁡
13
p
2
a
+
1
+
1
/
p
+
1
log
⁡
6
p
a
.
Since
(52)
13
p
2
a
+
1
+
13
<
36
p
2
a
+
1
+
36
p
2
a
=
36
p
2
a
(
p
+
1
)
,
it follows that c
<
2. Also, since p
2
>
p
+
1, we see that
(53)
p
2
a
-
1
<
p
2
a
-
1
·
p
2
p
+
1
=
p
2
a
+
1
p
+
1
<
p
2
a
+
1
+
1
p
+
1
.
Thus,
(54)
2
-
3
a
+
1
=
log
⁡
p
2
a
-
1
log
⁡
p
a
+
1
<
log
⁡
13
p
2
a
-
1
log
⁡
p
a
+
1
<
log
⁡
13
p
2
a
-
1
log
⁡
6
p
a
(
since
p
≥
13
)
<
c
(
by
(
53
)
)
.
Therefore,
(55)
2
-
3
a
+
1
<
c
<
2
.
A similar computation yields the same conclusion when G
≃
Z
p
a, which completes the proof of Theorem 3.


## 5.2. The Proof of Theorem4

It is clear that estimatingψ
(
S
n
) is, up to scaling, equivalent to estimating the average order μ
n
≔
ψ
(
S
n
)
/
n
! of an element in S
n. This problem was first raised by Erdös and Turán [5] in 1968 when they conjectured that
(56)
log
⁡
μ
n
=
O
n
log
⁡
n
.
Conjecture (56) was proven by Schmutz [6] in 1989 when he showed that
(57)
log
⁡
μ
n
≤
7.7
n
log
⁡
n
for
n
sufficiently  large
.
It follows from (57) that
(58)
ψ
S
n
≤
n
!
h
(
n
)
for
n
sufficiently  large
,
where
(59)
h
n
=
7.7
n
/
log
⁡
(
n
)
log
⁡
n
!
+
1
.
The proof of (57) is nontrivial and requires some very technical results concerning partitions. In 1991, Goh and Schmutz [7] sharpened (57) by proving that
(60)
log
⁡
μ
n
~
c
n
log
⁡
n
,
where
(61)
c
=
2
2
∫
0
∞
‍
log
⁡
log
⁡
e
1
-
e
-
t
d
t
.
The proof of (60) also requires some partition theory.In the spirit of Theorem3, it is our goal here to determine, if possible, the smallest possible constant C such that
(62)
ψ
S
n
≤
n
!
C
∀
n
≥
1
,
in a nontrivial manner. In other words, does there exist a smallest real number C
<
2 for which (62) is true, and can we determine it? Theorem 4 provides an affirmative answer to these questions. There are two advantages to the bound given for ψ
(
S
n
) in Theorem 4 over the results in [6, 7]. First of all, Theorem 4 is proven for all n
≥
1, not just for sufficiently large values of n. The second advantage is that the proof of Theorem 4 that we present here does not rely on any results from partition theory. We use the following result, due to Massias [8] in 1984.Theorem 20.
Letg
n denote the largest order of an element in S
n. Then
(63)
log
⁡
g
n
≤
1.05314
n
log
⁡
(
n
)
.In 1903, Landau [9] proved that log
⁡
g
n
~
n
log
⁡
(
n
), but Theorem 20 represents the first explicit upper bound for log(
g
n
). Although somewhat technical, Massias’ proof of Theorem 20 uses elementary analytic techniques requiring little more than calculus.We also need the following lemmas.Lemma 21.
Letn
≥
2 be an integer and let σ
,
τ
∈
S
n, with σ
=
(
a
b
). If τ fixes either a or b, then o
(
σ
τ
)
≤
n
·
o
(
τ
).Proof.
Observe that ifτ fixes both a and b, then
(64)
o
σ
τ
=
lcm
o
σ
,
o
τ
≤
o
σ
·
o
τ
=
2
·
o
(
τ
)
≤
n
·
o
(
τ
)
.
So, suppose that τ fixes b, but not a. Then we may write
(65)
τ
=
τ
1
τ
2
=
a
x
2
x
3
⋯
x
j
τ
2
,
for some j with 2
≤
j
≤
n
-
1, where τ
1 and τ
2 are disjoint, and x
i
≠
b for all i. Thus,
(66)
o
σ
τ
=
o
(
a
x
2
x
3
⋯
x
j
b
τ
2
)
=
lcm
j
+
1
,
o
τ
2
=
(
j
+
1
)
o
τ
2
gcd
j
+
1
,
o
τ
2
≤
n
·
o
τ
2
≤
n
·
o
τ
,
which completes the proof.Lemma 22.
Ifn
≥
4, then
(67)
n
-
1
n
3
/
2
-
1
>
n
2
-
n
.Proof.
Ifn
≥
4, then
(68)
n
2
=
n
1
/
2
·
n
3
/
2
≥
2
n
3
/
2
>
2
n
3
/
2
-
1
.
Thus,
(69)
n
3
/
2
-
1
=
n
3
/
2
-
1
2
=
n
3
-
2
n
3
/
2
-
1
>
n
3
-
n
2
=
n
n
-
1
,
from which the lemma follows.Lemma 23.
Ifn
≥
20 is an integer, then
(70)
n
-
2
!
>
e
2.10628
(
n
-
12
)
.Proof.
The lemma is easily verified forn
=
20. We proceed by induction on n. Then
(71)
n
+
1
-
2
!
=
(
n
-
1
)
(
n
-
2
)
!
>
n
-
1
e
2.10628
(
n
-
12
)
(
by  induction
)
=
n
-
1
e
2.10628
e
2.10628
(
n
-
11
)
>
e
2.10628
(
(
n
+
1
)
-
12
)
,
since n
-
1
>
e
2.10628 when n
≥
20, and the proof is complete.Lemma 24.
Letf
(
x
)
=
x
-
12
-
(
x
-
1
)
log
⁡
(
x
-
1
). Then f
(
x
)
>
0 for all x
≥
20.Proof.
The proof is straightforward using calculus.Lemma 25.
Ifn
≥
20 is an integer, then
(72)
n
-
1
!
log
⁡
3
/
log
⁡
⁡
2
-
1
n
log
⁡
3
/
log
⁡
⁡
2
-
1
>
n
(
n
-
1
)
e
1.05314
(
n
-
1
)
log
⁡
(
n
-
1
)
.Proof.
Let(73)
A
=
n
-
1
!
log
⁡
3
/
log
⁡
⁡
2
-
1
n
log
⁡
3
/
log
⁡
⁡
2
-
1
.
Since log(
3
)
/
log(2)
>
3
/
2, we have
(74)
A
>
(
n
-
1
)
!
n
3
/
2
-
1
=
n
-
1
n
3
/
2
-
1
n
-
2
!
>
n
2
-
n
e
1.05314
(
n
-
12
)
(
by  Lemmas
22
and
23
)
>
n
2
-
n
e
1.05314
(
n
-
1
)
log
⁡
(
n
-
1
)
(
by  Lemma
24
)
.Proof of Theorem4.
The proof is by induction onn. It is easy to verify computationally that the theorem is true for all n, with 1
≤
n
≤
20. For n
≥
20, let σ
1
=
(
1
) and σ
i
=
(
i
-
1
n
) for each i with 2
≤
i
≤
n. Then {
σ
1
,
σ
2
,
σ
3
,
…
,
σ
n
} is a complete set of left coset representatives for S
n
-
1 in S
n. Thus,
(75)
ψ
S
n
=
∑
i
=
1
n
‍
ψ
σ
i
S
n
-
1
=
∑
i
=
1
n
‍
∑
τ
∈
S
n
-
1
‍
o
σ
i
τ
=
ψ
S
n
-
1
+
∑
i
=
2
n
‍
∑
τ
∈
S
n
-
1
‍
o
σ
i
τ
≤
ψ
S
n
-
1
+
∑
i
=
2
n
‍
∑
τ
∈
S
n
-
1
‍
n
·
o
(
τ
)
(
by  Lemma
21
)
≤
ψ
S
n
-
1
+
∑
i
=
2
n
‍
∑
τ
∈
S
n
-
1
‍
n
·
e
1.05314
(
n
-
1
)
log
⁡
(
n
-
1
)
(
by  Theorem
20
)
=
ψ
S
n
-
1
+
(
n
-
1
)
!
·
n
(
n
-
1
)
·
e
1.05314
(
n
-
1
)
log
⁡
(
n
-
1
)
≤
n
-
1
!
log
⁡
(
3
)
/
log
⁡
(
2
)
+
(
n
-
1
)
!
·
n
(
n
-
1
)
·
e
1.05314
(
n
-
1
)
log
⁡
(
n
-
1
)
(
by  induction
)
<
n
!
log
⁡
(
3
)
/
log
⁡
(
2
)
(
by  Lemma
25
)
.In Table1, we compare the rounded values of ψ
(
S
n
), (
n
!
)
log
⁡
(
3
)
/
log
⁡
(
2
), (
n
!
)
2, and the bound for ψ
(
S
n
) given in (60), for n
=
2
,
…
,
10. The bound given in (58) is much worse for these small values of n than any bound given in Table 1, so we omit it.Table 1
Comparingψ
(
S
n
) and various upper bounds.
n
ψ
(
S
n
)
(
n
!
)
log
⁡
(
3
)
/
log
⁡
(
2
)
(
n
!
)
2
(60)
2
3
3
4
321
3
13
17
36
840
4
67
154
576
3858
5
471
1974
14400
23352
6
3271
33788
518400
171377
7
31333
738267
25401600
1464527
8
299223
19933214
1625702400
14220361
9
3291487
648658213
131681894400
154263165
10
39020911
24944707890
13168189440000
1846343649Remark 26.
The sequence{
ψ
(
S
n
)
}
n
=
1
∞ is listed in the On-Line Encyclopedia of Integer Sequences and can be found at http://oeis.org/A060014.We end with the following conjecture, which is supported by numerical evidence.Conjecture 27.
Letn be a positive integer. Then
(76)
ψ
A
n
≤
n
!
2
log
⁡
(
7
)
/
log
⁡
(
3
)
∀
n
≥
1
.
Moreover, the number log
⁡
(
7
)
/
log
⁡
(
3
) is the smallest possible constant C such that ψ
(
A
n
)
≤
(
n
!
/
2
)
C for all n
≥
1.Remark 28.
The sequence{
ψ
(
A
n
)
}
n
=
1
∞ is listed in the On-Line Encyclopedia of Integer Sequences and can be found at http://oeis.org/A060015.



---

*Source: 835125-2014-11-13.xml*