Ramanujan J https://doi.org/10.1007/s11139-018-9992-z

Subgroups of cyclic groups and values of the Riemann zeta function Mahannah El-Farrah1 · Dominic Lanphier1

Received: 4 April 2017 / Accepted: 4 January 2018 © Springer Science+Business Media, LLC, part of Springer Nature 2018

Abstract Let k be a positive integer, x a large real number, and let Cn be the cyclic group of order n. For k ≤ n ≤ x we determine the mean average order of the subgroups of Cn generated by k distinct elements and we give asymptotic results of related averaging functions of the orders of subgroups of cyclic groups. The average order is expressed in terms of Jordan’s totient functions and Stirling numbers of the second kind. We have the following consequence. Let k and x be as above. For k ≤ n ≤ x, the mean average proportion of Cn generated by k distinct elements approaches ζ (k + 2)/ζ (k + 1) as x grows, where ζ (s) is the Riemann zeta function. Keywords Cyclic groups · Riemann zeta function · Jordan’s totient functions Mathematics Subject Classification Primary 20P05 · 11A25; Secondary 11B73

1 Introduction The average order of the elements of symmetric groups and cyclic groups has been studied extensively, see [2,10,12–14,18,19,23]. A similar classical problem is whether a pair of elements, chosen at random with uniform probability, generates a group. This problem, with emphasis on the symmetric group, has been studied in [5,7] and [8], for example. Here we consider a related problem. Fix a positive integer k and let x be

B

Dominic Lanphier [email protected] Mahannah El-Farrah [email protected]

1

Department of Mathematics, Western Kentucky University, Bowling Green, KY 42101, USA

123

M. El-Farrah, D. Lanphier

large. For k ≤ n ≤ x, we investigate the mean average size of the subgroups of the cyclic group Cn generated by k distinct elements, as x grows. More precisely, let G be a finite group of order n and set G = {g1 , . . . , gn }. For any subset S of G, let S denote the subgroup of G generated by S and let P(S) denote the probability that S is chosen from G, with respect to a given probability distribution. For fixed integers 1 ≤ k ≤ n and m ≥ 1, if one chooses k elements from G then the m th moment of the average order of the subgroup generated by those elements is Mk,m (G) =



  P(i 1 , . . . , i k ) | gi1 , . . . , gik |m ,

(1)

{i 1 ,...,i k }⊆{1,...,n}

where the i 1 , . . . , i k are distinct. With the discrete uniform probability distribution and m = 1, this is the average order of all of the subgroups of G generated by k elements of G. We will assume that all groups have the uniform probability distribution in the sequel. In particular, M1,1 (G) =

|g1 | + · · · + |gn | n

is the average order of the elements of G. It is natural to investigate the size of Mk,m (G) for given groups G. Because of their simplicity and arithmetic properties, we consider cyclic groups here. The average order of the elements of a cyclic group was studied in [12]. See also [2,14], and in particular Theorem 10 of [15]. Further, the sum of the orders of the elements of a finite group has recently been used as a means to identify a group or certain subgroups [2–4,17,20]. Note that Mk,m (G) ≤ |G|m and in general we expect Mk,m (G) to be large for large k. From Lagrange’s Theorem, for example, when k > |G|/2 we have Mk,1 (G) = |G|. In the sequel let Cn = {a | a n = 1} be the cyclic group of order n. Quantitative results about the asymptotic mean of M1,1 (Cn ) have been studied. Recall that ζ (s) is the Riemann zeta function and f (x) = O(g(x)) means that f (x) ≤ Mg(x) for a constant M and x sufficiently large. In [12] the following result was obtained. Theorem 1 (Theorem 3.1, [12]) For x ≥ 3,   ζ (3) 1  x + O (log x)2/3 (log log x)4/3 . M1,1 (Cn ) = x 2ζ (2) 1≤n≤x

A motivation for the present work is to study similar sums and in particular determine asymptotically the average order of the subgroups of Cn generated by k distinct elements, for fixed k. Toward that end, our main result is the following. Theorem 2 Let k, , m be integers with k, m ≥ 1, and  ≥ 0. If k ≥ 2 and m >  then   1  Mk,m (Cn ) ζ (k + m + 1) x m− + O x m−−1 . =  x n (m −  + 1)ζ (k + 1) k≤n≤x

123

Subgroups of cyclic groups and values...

If k = 1 and m ≥ , or k ≥ 1 and m = , then the same result holds with error term O(x m−−1 log x). If m + 1 =  then

1 ζ (k + m + 1) log x 1  Mk,m (Cn ) +O . = x ζ (k + 1) x x n k≤n≤x

If k = 1 and m + 1 <  then

1 1  M1,m (Cn ) ζ ( − m)ζ (1 + ) 1 +O . =  x ζ (1 +  − m) x x2 n 1≤n≤x

 Note that for m + 1 <  it is trivial that (1/x) k≤n≤x Mk,m (Cn )/n  = O (1/x). Taking k = 1 we get the more precise result above. We distinguish two cases of Theorem 2. Taking  = 0 we get the following expansion of Theorem 1. For k ≥ 2 and m ≥ 1,   ζ (k + m + 1) m 1  x + O x m−1 Mk,m (Cn ) = x (m + 1)ζ (k + 1) k≤n≤x

and for k = 1 the error term is O(x m−1 log x). For the k = m = 1 case studied in [12], the error term that we get with the methods here is O(log x). For the better error term from Theorem 1, the authors of [12] refer to a result from Chapter IV of [26] derived using exponential sum estimates. For k ≥ 1 and  = m = 1, we have lim

x→∞

ζ (k + 2) 1  Mk,1 (Cn ) = . x n ζ (k + 1)

(2)

k≤n≤x

In a sense, (2) is a more natural way to study average orders of subgroups than Theorem 1. That is because the terms Mk,1 (Cn )/n that occur in (2) give the average proportion of the subgroup Cn generated by subsets of k distinct elements. As such, it is more natural to use these terms to compare averages between different groups. Whereas the terms M1,1 (Cn ) are the average orders of subgroups generated by 1 element, and the sum in Theorem 1 is heavily weighted toward those terms with large n. This accounts for the 1/2 factor that appears in Theorem 1 but not in (2). Expression (2) has an interesting interpretation. As examples, for k = 1 the value of (2) is ζ (3)/ζ (2) ≈ 0.73076 and for k = 2 the value of (2) is ζ (4)/ζ (3) ≈ 0.90039. Therefore, with the discrete uniform probability distribution, randomly choosing a group Cn for 1 ≤ n ≤ x with x sufficiently large and randomly choosing an element from that group, then the subgroup of Cn generated by that element will, on average, consist of about 73.076% of the group. Similarly, randomly choosing 2 ≤ n ≤ x, on average the subgroup generated by 2 distinct elements of Cn will consist of about 90.039% of the group. We state the general case as the following.

123

M. El-Farrah, D. Lanphier

Corollary 1 Let k ∈ Z>0 be fixed and let x be a large real number. For k ≤ n ≤ x, the mean average proportion of Cn generated by k distinct elements approaches ζ (k + 2)/ζ (k + 1) as x grows. In other words, if we randomly choose n ∈ Z>0 between k and x, for large x, and we randomly choose k distinct elements from Cn , then the expected order of the subgroup generated by those k elements is about nζ (k + 2)/ζ (k + 1). In [12], the multiplicativity of M1,1 (Cn ) with respect to n is crucial. However, for k ≥ 2 it is easy to see that the function Mk,m (Cn ) is not multiplicative. Nevertheless, we can explicitly write Mk,m (Cn ) in terms of multiplicative functions. In the next section, we introduce the arithmetic functions that we study and prove some relevant properties of these functions. In Sect. 3 we prove asymptotic results that will be necessary for the main result. In Sect. 4 we prove Theorem 2 by first giving an explicit expression for Mk,m (Cn ) in terms of known arithmetic functions and then using the asymptotic results of Sect. 3. We also give examples of sequences of cyclic groups Cn where the average order of an element goes to n or is arbitrarily small with respect to n, as n grows. In the last section, we give some results about the dominant term of Mk,m (Cn ).

2 Preliminary results on arithmetic functions In this section, we introduce the arithmetic functions that we use and prove some relevant properties. The Möbius function μ(n) [16] is defined on positive integers n by μ(n) = (−1)r if n = p1 p2 . . . pr , where the pi are distinct primes, μ(n) = 0 if n is divisible by a square, and μ(1) = 1. Recall that the Möbius Inversion Formula (Theorem 266 of [16]) states that if f (n) and g(n) are multiplicative functions of n ∈ Z then f (n) = the positive integers so that g(n) = d|n f (d) for every  ∞ −s>0 μ(d)g The Riemann zeta function is ζ (s) = with Re(s) > 1 (n/d). d|n n=1 n ∞ −s and from [16], for example, we have n=1 μ(n)n = 1/ζ (s) for Re(s) > 1. Let (i 1 , . . . , i n ) denote the greatest common divisor of i 1 , . . . , i k ∈ Z>0 . For n, k ∈ Z>0 with k ≤ n let Jk (n) denote the number of non-ordered k-tuples (as in [22], p.122) 1 ≤ i 1 , . . . , i k ≤ n so that ((i 1 , . . . , i k ), n) = 1. Note that the i 1 , . . . , i k need not be distinct. The function Jk (n) is called Jordan’s totient function and is a generalization of Euler’s totient function. Some well-known properties of Jk (n) are in [1], for example. A formula for Jk (n) [21] is

1 1− k . Jk (n) = n p k

(3)

p|n

From expression (3) we see that the function Jk (n) is multiplicative and it follows that  Jk (d) is multiplicative. For p a prime, Jk ( p j ) = p jk − p ( j−1)k and it follows that d|n  k Inversion gives the expression Jk (n) = d|n μ(d) (n/d)k . d|n Jk (d) = n . Möbius



 For m, n ∈ Z>0 let mn be a Stirling number of the second kind. That is, mn is the number of ways of partitioning a set of n labelled elements into m non-empty, unlabelled sets. See 1.4 of [25] for basic properties of Stirling numbers of the second kind.

123

Subgroups of cyclic groups and values...

For convenience, we introduce a related arithmetic function. These objects occur naturally here and we show how they can be expressed in terms of Jordan’s totient functions. Let Jk (n) denote the number of non-ordered k-tuples 1 ≤ i 1 , . . . , i k ≤ n so that ((i 1 , . . . , i k ), n) = 1 and where the i 1 , . . . , i k are distinct. Note that the number of ordered k-tuples 1 ≤ i 1 < · · · < i k ≤ n so that ((i 1 , . . . , i k ), n) = 1 is Jk (n)/k!. We first consider the following result. Lemma 1 Let k, n ∈ Z>0 with n ≥ k. Then Jk (n) = Jk (n) −

k−1    k j=1

j

Jj (n).

Proof Consider the set Sk of non-ordered k-tuples 1 ≤ i 1 , . . . , i k ≤ n so that ((i 1 , . . . , i k ), n) = 1. By the definition of Jordan’s totient function we have Jk (n) = |Sk |. The number of k-tuples in Sk where exactly j elements of each k-tuple are distinct is equal to the number

of ways of placing k labelled balls into j unlabelled bins. This number is precisely kj . Further, the number of ways of labelling the j distinct balls is Jj (n). It follows that if we take the set Sk and remove the k-tuples where exactly j

 elements are distinct, then we have removed kj Jj (n) such k-tuples. After removing all of the k-tuples which have elements that are non-distinct, we are left with those k-tuples 1 ≤ i 1 , . . . , i k ≤ n with ((i 1 , . . . , i k ), n) = 1 and all the i j distinct. This is  exactly Jk (n) k-tuples. Index the set of ordered partitions of k − j by {ν} for ν ranging from 1 to 2k− j−1 . Thus for k − j = i 1 + · · · + il with i h ∈ Z>0 for all 1 ≤ h ≤ l, there is an index ν = ν(i 1 , . . . , il ). For k > j set Ak, j =

j−1 k− j 2k−  



(−1)

l+1

ν=1 l=1

k k − i1



   k − i1 k − i 1 − · · · − il−1 ··· . (4) k − i1 − i2 j

k  Note that Ak,k−1 = k−1 . For clarity, we distinguish the partition ν = ν(k − j), which is simply the partition of k − j consisting of k − j itself. Therefore we can write Ak, j

  k = + j

j−1 2k− 

     k− j  k k − i1 k −i 1 − · · · − il−1 ··· , (−1)l+1 k − i1 k − i1 − i2 j

ν=1 l=2 ν =ν(k− j)

where the range of l in the summation above begins at 2 because the l = 1 partition is accounted for by the kj term. Lemma 2 Let j, k ∈ Z>0 , and k > j + 1. Then Ak, j =

  k−1    k k Al, j . − l j l= j+1

Proof In definition (4) of Ak, j , the index ν = ν(i 1 , . . . , il ) indices the ordered partitions of k − j, where {i 1 , . . . , il } ranges over the ordered partitions. Thus the partitions

123

M. El-Farrah, D. Lanphier

are indexed by ν = ν(i 1 , . . . , il ) where l ranges from 1 to k − j and ν ranges from 1 to 2k− j−1 . The first subindex i 1 also ranges from 1 to k − j, so we can classify the partitions according to the values of i 1 . Let νt index the set {partition ν | i 1 = t} for 1 ≤ t ≤ k − j − 1. So the sum over the indices ν in (4) can be written as a double sum over t and νt . We label the first term in a partition by t, and then the partitions can be classified by νt = νt (t, i 2 , . . . , il ). There are at most k − t − j terms in the partition k − t − j = i 2 + · · · + il and so the index l ranges from 2 to k − t − j + 1, and νt indices the ordered partitions of k − t − j. There are 2k−t− j−1 such partitions. Thus the double sum in (4) over ν and l can be written as a triple sum over the indices t, νt , and l with ranges 1 to k − j − 1 as t = k − j, 1 to 2k−t− j−1 , and 2 to k − t − j + 1, respectively. We have

Ak, j

  k = + j

=

j−1 2k− 

     k− j  k k − i1 k − i 1 − · · · − il−1 ··· (−1)l+1 k − i1 k − i1 − i2 j

ν=1 l=2 ν =ν(k− j)

  k− j−1  k + j t=1

2k−t− j−1

×



k−t− j+1

νt =1

l=2



(−1)

l+1

k k−t



   k−t k − t − · · · − il−1 ··· . k − t − i2 j

For the partition k − t − j = i 2 + · · · + il , the number of terms ranges from 1 to k − t − j. So relabeling the partition (i 2 , . . . , il ) as ( j1 , . . . , jl  ), the index l  ranges  from 1 to k − t − j and (−1)l+1 = −(−1)l +1 . Thus we can write

Ak, j

   k− j−1   k k = − k−t j t=1

×

j−1 2k−t−  k−t− j

νt =1

l  =1



(−1)l +1

   k−t k − t − · · · − jl  −1 . ··· j k − t − j1



(5)

As the set of indices νt index the set of ordered partitions of k − t − j, the inner double sum over νt and l in (5) is precisely Ak−t, j . It follows that (5) is    k−   j−1  k−1     k k k k Ak−t, j = Al, j . − − k−t l j j t=1

l= j+1

 The main result of this section demonstrates how the functions Jk (n) can be explicitly written in terms of Jordan’s totient functions.

123

Subgroups of cyclic groups and values...

Lemma 3 Let k, n ∈ Z>0 with n ≥ k. Then Jk (n) = Jk (n) −

k−1 

Ak, j J j (n).

j=1

Proof As J1 (n) = J1 (n), the result holds for k = 1. Assume the result for all k  with 1 ≤ k  < k. By Lemma 1 and the induction hypothesis, k−1    k

k−1    k

  k  J1 (n) J j (n) − j j 1 j=1 j=2 ⎞ ⎛   j−1 k−1     k ⎝ k A j,l Jl (n)⎠ − J1 (n). = Jk (n) − J j (n) − j 1

Jk (n) = Jk (n) −

Jj (n) = Jk (n) −

j=2

l=1

This expression can be rewritten as Jk (n) −

k−1    k j=1

j

J j (n) +

j−1   k−1   k j=2 l=1

j

A j,l Jl (n)

k−1    k

k−2  k−1    k J j (n) + A j,l Jl (n) = Jk (n) − j j j=1 l=1 j=l+1 ⎞ ⎛ k−1   k−2 k−1      k k J j (n) + A j,l ⎠ . Jl (n) ⎝ = Jk (n) − j j j=1

l=1

j=l+1

Switching the labels of the indices l and j in the double summation and combining the terms we get ⎛ ⎞     k−2 k−1     k k k ⎝ ⎠ J j (n) Al, j − Jk−1 (n) + Jk (n) = Jk (n) − l k−1 j j=1

 = Jk (n) −



k Jk−1 (n) − k−1

k−2 

l= j+1

Ak, j J j (n),

j=1



where we used Lemma 2 in the last step.

3 Arithmetic sums and asymptotics The lemmas below are asymptotic results on certain sums of arithmetic functions that arise as terms in the mean sums of Mk,m (Cn ). Lemma 4 Let  ∈ Z≥0 and k, m ∈ Z≥1 . If k + m ≥  and k ≥ 2 then  1    ζ (k + m + 1) d m Jk (d) = x k+m−+1 + O x k+m− .  (k + m −  + 1)ζ (k + 1) n

1≤n≤x

d|n

123

M. El-Farrah, D. Lanphier

If k + m ≥  and k = 1 then the same expression holds but with error term O(x k+m− log x). If k + m + 1 =  then  1  ζ (k + m + 1) d m Jk (d) = log x + O(1).  ζ (k + 1) n

1≤n≤x

d|n

If k + m + 1 <  then

 1  1 ζ ()ζ ( − m − k) m + O . d J (d) = k  ζ ( − m) x n

1≤n≤x

d|n

Proof We have  1   1 m d J (d) = a m Jk (a) k  n (ab)

1≤n≤x

d|n

1≤ab≤x



=

1≤ab≤x

1 a −m

 1  1 1 Jk (a) = Jk (a).   −m b b x a 1≤b≤x

1≤a≤ b

(6) From the expression for Jk (n) given in Sect. 2,  1≤a≤ bx

1 a −m

Jk (a) =



1

1≤a≤ bx

=

a −m





μ(d)

d|a

1

1≤dd  ≤ bx

 a k

(dd  )−m−k

d

=

 1≤a≤ bx

 μ(d)

1 a −m−k

 μ(d) μ(d) = k −m d x d 1≤d≤ b

d|a

 x 1≤d  ≤ db

dk 1 d −m−k

.

(7) Consider the case k + m ≥ . Then (7) can be written  μ(d) −m x d

1≤d≤ b



d m+k− ,

(8)

x 1≤d  ≤ db

where the exponents of d  are non-negative. The well-known sums of powers of integers formula [6] are s  d=1

123

dr =



r r +1 1  B j s r +1− j , (−1) j j r +1 j=0

(9)

Subgroups of cyclic groups and values...

where B j is the j th Bernoulli number. This formula, known as Faulhaber’s formula, has a long history [9]. Applying (9) to (8) we get that (8) equals ⎛ ⎞

  m+k−   μ(d) m+k−+1− j 1 m +k − + 1 x ⎝ ⎠, Bj (−1) j −m m +k −+1 db j x d j=0

1≤d≤ b

(10) where · is the floor function. Then (10) is  μ(d) −m x d



1≤d≤ b

   x m+k−+1   db x m+k− +O m+k−+1 db

 μ(d) = −m x d



   x m+k− . +O m+k−+1 db

1≤d≤ b

 x m+k−+1 db

It follows that (6) is  1  μ(d) −m b x d

1≤b≤x

=

1≤d≤ b

x m+k−+1



   x m+k− +O m+k−+1 db  x m+k−+1 db



1

 μ(d) k+1 x d

m+k−+1 1≤b≤x 1≤d≤ b ⎛ ⎞ m+k−   x 1 μ(d) ⎠ +O⎝ . m+k−+1 bm+k dk x bm+k+1

1≤b≤x

(11)

1≤d≤ b

   For a ≥ 2 we have 1≤b≤x 1/ba = ζ (a) + O 1/x a−1 , for a = 1 we have  a m+k− ) 1≤b≤x 1/b = log x + O(1). If k > 1 then the error term in (11) is O(x and if k = 1 then the error term is O(x m+k− log x). So from properties of ζ (s) from Sect. 2, (11) is   x m+k−+1 ζ (m + k + 1) + O x m+k− m + k −  + 1 ζ (k + 1) for k > 1 with error term O(x m+k− log x) for k = 1. Consider  > k + m. Then (6) and (7) give  1   1  μ(d) m d J (d) = k −m n b x d

1≤n≤x

d|n

1≤b≤x

1≤d≤ b

 x 1≤d  ≤ db

1 , d −m−k

(12)

123

M. El-Farrah, D. Lanphier

where  − m − k is positive. If  − m − k = 1 then (12) becomes  1≤b≤x

1 bk+m+1

 μ(d) k+1 x d

1≤d≤ d

 x 1≤d  ≤ db

1 ζ (k + m + 1) = log x + O(1).  d ζ (k + 1)

If  − m − k > 1 then (12) becomes  1  μ(d) −m b x d

1≤b≤x

1≤d≤ d

 x 1≤d  ≤ db

1 d −m−k

ζ ()ζ ( − m − k) +O = ζ ( − m)



1 . x 

The error terms here are not necessarily the best possible, see [12] and [26], for example. We are interested in the main term, so we do not give an argument as in [12]  −1 to get improved estimates. The lemma below gives nk = k!/n k + Ok (n −(k+1) ), but we state it in the following form for use in Sect. 4. R 1 k! Lemma 5 For sufficiently large n, n  = k + k+1 where 0 ≤ R ≤ ck for ck n n k independent of n.   Proof As n k /k! ≥ nk we have R ≥ 0. We can assume that k ≥ 2 (otherwise the result is trivial) and so

1 1 − (n − 1) · · · (n − k + 1) n k−1

ak n k−2 + · · · + (−1)k (k − 1)! k! = k , n n k−1 − ak n k−2 + · · · + (−1)k (k − 1)!

k! 1 k! n  − k = n n k

where (n − 1) · · · (n − k − 1) = n k−1 − ak n k−2 + · · · + (−1)k (k − 1)! and ak > 0 where ak is independent of n. Therefore for n sufficiently large, bk ak n k−2 + · · · + (−1)(k − 1)! ≤ k−1 k−2 k n − ak n + · · · + (−1) (k − 1)! n for bk > 0 and independent of n. Thus, 1 k! bk k! k!bk n  − k ≤ k = k+1 n n n n k and this gives the result.

123



Subgroups of cyclic groups and values...

4 Proof of Theorem 2 We first obtain an explicit formula for Mk,m (Cn ). Note that M1,1 (Cn ) = (see [12]) and we can directly compute that

 d|n

dφ(d)/n

⎞ ⎛   1 ⎝ d J2 (n) − dφ(d)⎠ . M2,1 (Cn ) = n(n − 1) d|n

d|n

We find a similar expression for Mk,m (Cn ) in terms of such arithmetic functions. Proposition 1 Let k, , m be integers with k, m ≥ 1, and  ≥ 0. Then ⎞ ⎛ k−1   1 ⎝ m Mk,m (Cn ) = n  d Jk (d) − Ak, j d m J j (d)⎠ . k! k d|n j=1 d|n Proof For d|n, the number of distinct non-ordered k-tuples 1 ≤ i 1 , . . . , i k ≤ n n = 1} we have =  d is Jk (n/d). Note so Cn = {a|a  that for   i that ((i 1i ,. . . , ik ),(i n) ,...,i ) ((i ,...,i ),n) i i 1 1 1 1 k k = a and | a , . . . , a k | = |a (i1 ,...,ik ) | = a ,...,a k = a n/((i 1 , . . . , i k ), n) (as in Chapter 4 of [11]). Therefore, 

|a , . . . , a | = i1

1≤i 1
=

d|n

=

d

ik

m

 1≤i 1 <···


n ((i 1 , · · · , i k ), n)

m

× #{ordered k-tuples ((i 1 , . . . , i k ), n) = d with il = i m for l = m}

  n m Jk ( n ) 1  m d = d Jk (d). d k! k! d|n

d|n

Equipping the set {1, a, . . . , a n−1 } with the discrete uniform probability   distribution, each set of distinct k elements in Cn is chosen with probability 1/ nk . By definition (1) and Lemma 3 we get the explicit formula 1  m |a i1 , . . . , a ik |m = n  d Jk (d) k 1≤i 1 <···
1 Mk,m (Cn ) = n 





123

M. El-Farrah, D. Lanphier

Applying Lemma 5 and Proposition 1, 1  Mk,m (Cn ) x n k≤n≤x

=

k−1  1  1  m 1  1  d J (d) − Ak, j d m J j (d) k k+ k+ x x n n k≤n≤x

+

d|n

k≤n≤x

j=1

d|n

k−1    1  R R 1  m d J (d) − A d m J j (d). k k, j x k!n k++1 x k!n k++1 k≤n≤x

d|n

k≤n≤x

j=1

d|n

This expression can be rewritten as ⎛ ⎞ k−1   1  1  1  m 1 m d Jk (d) − Ak, j ⎝ d J j (d)⎠ x x n k+ n k+ k≤n≤x d|n j=1 k≤n≤x d|n ⎞ ⎛ k−1   1  m 1 R 1 R1  d Jk (d) − Ak, j ⎝ d m J j (d)⎠ , + k! x n k++1 k! x n k++1 k≤n≤x

d|n

j=1

k≤n≤x

d|n

(13) where R is as in Lemma 5. We distinguish 4 cases: (i) m ≥  and k ≥ 2, (ii) m ≥  and k = 1, (iii) m + 1 = , and (iv) m + 1 < . We take each case in turn and consider each of the 4 terms of (13) separately. Note that  k≤n≤x

1  n k+

d m Jk (d) =

 1≤n≤x

d|n

1  n k+

d m Jk (d) + O(1).

d|n

For case (i) we have k ≥ 2 and m ≥ . Lemma 4 gives for the first term

1 1  1  m 1  1  m d Jk (d) = d Jk (d) + O k+ k+ x n x n x k≤n≤x

1≤n≤x

d|n

d|n

ζ (k + m + 1) x m− + O(x m−−1 ). = (m −  + 1)ζ (k + 1) For the second term in (13) we have

1  1  m 1  1  m 1 , d J (d) = d J (d) + O j j k+ k+ x x x n n k≤n≤x

d|n

1≤n≤x

d|n

where 1 ≤ j ≤ k − 1. When m + j ≥ k +  we get that (14) is   ζ ( j + m + 1) x m+ j−k− + O x m+ j−k−−1 , ( j + m − k −  + 1)ζ ( j + 1)

123

(14)

Subgroups of cyclic groups and values...

and these are O(x m−−1 ) for each j. When m + j + 1 = k +  then we get that (14) is



1 log x ζ ( j + m + 1) log x +O =O . ζ ( j + 1) x x x When  m + j + 1 < k+  then we get O (1/x). For the third term of (14), (1/x) k≤n≤x 1/n k++1 d|n d m Jk (d), when m ≥  + 1 then we get O(x m−−1 ). When  m =  then from Lemma  4 we get that this term is O (log x/x). The fourth term is (1/x) k≤n≤x 1/n k++1 d|n d m J j (d) where 1 ≤ j ≤ k−1. When j +m ≥ k++1 then this term is O(x m+ j−k−−1 ) = O(x m−−1 ). If j + m + 1 = k +  + 1 thenthis  expression is O (log x/x). If j + m + 1 < k +  + 1 then this expression is O x1 . For m >  all of these terms are O(x m−−1 ). As a consequence, for this case we get from Lemma 4 that for m > , expression (13) is 1  Mk,m (Cn ) 1  1  m = d Jk (d) x x n n k+ k≤n≤x

k≤n≤x

d|n

  ζ (k + m + 1) x m− + O x m−−1 = (m −  + 1)ζ (k + 1)

(15)

and if m =  then the same expression holds but with error term O (log x/x). For case (ii), so that k = 1 and m ≥ , Lemma 4 gives for the first term 1  1  m ζ (m + 2) x m− + O(x m−−1 log x). d Jk (d) = k+ x n (m −  + 1)ζ (2) 1≤n≤x

d|n

The second and fourth terms do not occur in case (ii). For the third term, for m ≥  + 1 we get 1  1  m ζ (m + 2) m−−1 x d Jk (d) = + O(x m−−2 ) = O(x m−−1 ) x (m − )ζ (2) n k++1 1≤n≤x

d|n

and if m =  then this term is ζ (m + 2)/ζ (2) · log x/x + O (1/x). Thus in this case, we get that the whole expression (13) can be written as ζ (m + 2) x m− + O(x m−−1 log x). (m −  + 1)ζ (2)

(16)

For case (iii), we have m + 1 = . By Lemma 4 the first term is

 1 1 ζ (m + k + 1) log x 1  m +O . d Jk (d) = x n k+m+1 ζ (k + 1) x x k≤n≤x

d|n

  The second term is (1/x) k≤n≤x 1/n k+m+1 d|n d m J j (d) for 1 ≤ j ≤ k − 1. Then j + m + 1 < k + m + 1 for all j, so by Lemma 4 this expression is O (1/x). Similarly

123

M. El-Farrah, D. Lanphier

we can show that the third and fourth terms are O (1/x). Thus for case (iii), expression (13) is ζ (m + k + 1) log x +O ζ (k + 1) x



1 . x

(17)

For case (iv), we have m + 1 <  and so k +  > k + m + 1 and the first term of (13) is

1 1  1  m . d Jk (d) = O k+ x n x k≤n≤x

d|n

To apply Lemma 4 here we take k = 1 and we get

1  1  m 1 ζ ( + 1)ζ ( − m) 1 . + O d J (d) = k k+ x n ζ ( + 1 − m) x x2 1≤n≤x

(18)

d|n

The other terms follow in a similar fashion. Putting (15), (16), (17), and (18) together proves Theorem 2. As M1,m (Cn ) is multiplicative, we can obtain a different exact formula than the this case. From the above argument, M1,m (Cn ) =  onem in Proposition 1 for r d|n d φ(d)/n. Let n = p for p a prime. Then 1  m d φ(d) pr d| pr



1 1 1 m rm r + ··· + p p 1 − = r 1+ p p 1− p p p

  1 1 m+1 m+1 2 m+1 r = r 1+ 1+ p + (p ) + · · · + (p ) −1 1− p p    

1 1 p (m+1)(r +1)−1 1− −1 = r 1+ p p m+1 − 1 p

M1,m (C pr ) =

=

p mr +m+r +1 − p mr +m+r + p m − 1 . pr ( p m+1 − 1)

Taking the factorization n = M1,m (Cn ) =



i=1

piri we get

 mr +m+ri +1 − pimri +m+ri + pim − 1 1 pi i . n pim+1 − 1

(19)

i=1

In particular, from the factorization of the sum of divisors function σk (n) (see Theorem 274 of [16], for example) we have M1,1 (Cn ) = (1/n)σ2 (n 2 )/σ1 (n 2 ). This expression for M1,1 (Cn ) is known, see [15], for example. Further, we get

123

Subgroups of cyclic groups and values...

M1,2 (Cn ) =

 3r +2 1 pi i + pi + 1 n pi2 + pi + 1 i=1

and we have a formula for the variance σ 2 (Cn ) of the orders of the elements of Cn , 1 σ (Cn ) = M1,2 (Cn ) − M1,1 (Cn ) = n 2

2

  3r +2 p i + pi + 1 i i=1

pi2 + pi + 1

1 − n



σ2 (n 2 ) σ1 (n 2 )

2  .

We consider a couple of examples of sequences of cyclic groups {Cn } where the average size of an element is arbitrarily close to n or arbitrarily small with respect to  n. As M1,1 (Cn ) = d|n φ(d)d/n, taking n = p k for p a prime, from (19) we have M1,1 (C pk ) =

p 2k+3 − p 2k+2 + p 2 − p < pk . p k+3 − p k+1

As p gets large this term approaches p k . In particular, M1,1 (C pk )/ p k gets arbitrarily close to 1 as p gets large. Therefore the average size of an element of C pk gets arbitrarily close to p k as p gets large. For n = p1 · · · pk , the first k primes, from (19) we have  M1,1 Ck

j=1

 pj

=

k j=1

pj − 1 +

1 pj

and     k M1,1 Ck p j 1 1 j=1 = + 2 . 1− k pj pj j=1 p j j=1

(20)

The product on the right-hand side of (20) converges or diverges just as the sum  ∞ −1 −2 j=1 p j − p j does, and this sum diverges. As each term in the product in (20) is less than 1 and the series above diverges, the product on the right-hand-side of (20) must go to 0. Thus for k sufficiently large, the average order of an element of these cyclic groups is arbitrarily small with respect to the order of the group.

5 Asymptotics of Mk,m (Cn ) In this section, we study the asymptotics of Mk,m (Cn ). Note that J j (n) = O(n j ) ≤ n log(n) for sufficiently large n, then and as σk (n) ≤ ζ (k)n k for k > 1 and σ1 (n)  m J (d) = O(n m+ j ) for m > 1 and m m+ j+ ) for m = 1 d j d|n d|n d J j (d) = O(n and any  > 0. From Proposition 1 therefore, we have Mk,m (Cn ) = O(n m+ ) for any  > 0. As it is well-known that nk k! ∼ n k (see [24] page 57, for example) then

123

M. El-Farrah, D. Lanphier

⎞ ⎛ k−1   1 ⎝ m Mk,m (Cn ) = n  d Jk (d) − Ak, j d m J j (d)⎠ k k! d|n j=1 d|n 1  m = n  d Jk (d) + O(n m−1+ ) k! k d|n    for any  > 0. Thus a good approximation for Mk,m (Cn ) is (1/ nk k!) d|n d m Jk (d), for large n. Analogous to Theorem 2.2 of [12], it is of interest to know how much contribution to this main term comes from k-tuples (i 1 , . . . , i k ) so that ((i 1 , . . . , i k ), n) = 1. Toward that end, we consider the ratio  αk,m (n) =

m d|n d Jk (d) . n m Jk (n)

 Set Ak,m = ζ (2k) p prime (1 − p −2k + p −k−m + p −2k−m ). For k > 1 this  can be simplified slightly to Ak,m = ζ (k) p prime (1 − p −k + p −k−m ). Clearly limk→∞ Ak,m = limm→∞ Ak,m = 1. Theorem 3 For integers n > 0, k, m ≥ 1 with k ≤ n, 1 < αk,m (n) ≤

p|n

1+

p −k−m , 1 − p −k

lim inf n→∞ αk,m (n) = 1, and lim supn→∞ αk,m (n) = Ak,m . Proof Note that αk,m (n) > 1. As αk,m (n) is multiplicative, for p a prime we compute αk,m ( p  ) = =

1 + p m Jk ( p) + · · · + p m Jk ( p  ) , p m Jk ( p  ) 1 + ( p k+m + ( p k+m )2 + · · · + ( p k+m ) )(1 −

p (k+m) − p (k+m)−k  k+m +1  1 + ( p pk+m) −1−1 − 1 ( p k − 1) = , p (k+m)+k − p (k+m) p (k+m)(+1) − p (k+m)+m + p m − 1 . = p (k+m)−k ( p k − 1)( p k+m − 1)

Setting f (x) =

123

p (k+m)(x+1) − p (k+m)x+m + p m − 1 A(x) , = B(x) p (k+m)x−k

1 ) pk

,

Subgroups of cyclic groups and values...

it is straightforward to show that A (x)B(x) − A(x)B  (x) = p (k+m)x−k (k + m) log( p)(− p m + 1) < 0. Thus f (x) is decreasing, and as a consequence αk,m ( p  ) is decreasing in  and so αk,m ( p) > αk,m ( p  ) for  > 1. It is straightforward that αk,m ( p) = For n =

1 − p −k + p −2k−m − p −2k−2m p −k−m 1 − p −k + p −k−m =1+ . = −k −k−m −k (1 − p )(1 − p ) 1− p 1 − p −k

j i=1

piei for pi distinct primes, we have

1 < αk,m (n) =

j

αk,m ( piei )

i=1

≤

j

αk,m ( pi ) =

i=1

p|n

1+

p −k−m . 1 − p −k

(21)

 It is straightforward that lim supn→∞ αk,m (n) = p prime αk,m ( p) = Ak,m . Taking  n = p and p large in (21) we have lim inf n→∞ αk,m (n) = 1. Note that if k = m then Ak,k =

p prime

=

p prime

αk,k ( p) =

1 − p −k + p −3k − p −4k , (1 − p −k )(1 − p −2k )

p prime

ζ (2k)ζ (3k) 1 − p −6k = . −2k −3k (1 − p )(1 − p ) ζ (6k)

Compare Theorem 2.2 of [12]. Also, for large k and n with k  n we have Mk,m (Cn ) ∼ n m−k Jk (n) and for large m and n we have Jk (n) Mk,m (Cn ) ∼ n  n m . k k!

References 1. Adhikari, S.D., Sankaranarayanan, A.: On an error term related to the Jordan totient function Jk (n). J. Number Theory 34, 178–188 (1990) 2. Amiri, H., Amiri, S.M.J., Isaacs, I.M.: Sums of element orders in finite groups. Commun. Algebra 37(9), 2978–2980 (2009) 3. Amiri, H., Amiri, S.M.J.: Sums of element orders on finite groups of the same order. J. Algebra Appl. 10(2), 187–190 (2011) 4. Amiri, H., Amiri, S.M.J.: Sums of element orders of maximal subgroups of the symmetric group. Commun. Algebra 40(2), 770–778 (2012) 5. Babai, L.: The probability of generating the symmetric group. J. Combin. Theory Ser. A 52(1), 148–153 (1989) 6. Beardon, A.F.: Sums of powers of integers. Am. Math. Mon. 103, 201–213 (1996) 7. Dixon, J.D.: The probability of generating the symmetric group. Math. Z. 110, 199–205 (1969)

123

M. El-Farrah, D. Lanphier 8. Dixon, J.D.: Asymptotics of generating the symmetric and alternating groups. Electron. J. Combin. 12 (2005), Research Paper 56 9. Edwards, A.W.F.: Sums of powers of integers: a little of the history. Math. Gaz. 66, 22–29 (1982) 10. Erd˝os, P., Turán, P.: On some problems of a statistical group theory IV. Acta Math. Acad. Scient. Hung. 19, 413–435 (1968) 11. Gallian, J.: Contemporary Abstract Algebra, 6th edn. Houghton Mifflin Company, Boston (2006) 12. Gathen, J., Knopfmacher, A., Luca, F., Lucht, L.G., Shparlinski, I.E.: Average order in cyclic groups. J. de Théorie des Nombres de Bordeaux 16, 107–123 (2004) 13. Goh, W.M., Schmutz, E.: The expected order of a random permutation. Bull. Lond. Math. Soc. 23(1), 34–42 (1991) 14. Gould, H.W., Shonhiwa, T.: Functions of GCD’s and LCM’s. Indian J. Math. 39(1), 11–35 (1997) 15. Gould, H.W., Shonhiwa, T.: A generalization of Cesàro’s function and other results. Indian J. Math. 39(2), 183–194 (1997) 16. Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers, 6th edn. Oxford University Press, Oxford (2008) 17. Harrington, J., Jones, L., Lamarche, A.: Characterizing finite groups using the sum of the orders of the elements. Int. J. Comb. vol. (2014), Article 835125 18. Hu, Y., Pomerance, C.: The average order of elements in the multiplicative group of a finite field. Involv. J. Math. 5(2), 229–236 (2012) 19. Luca, F.: Some mean values related to average multiplicative orders of elements in finite fields. Ramanujan J. 9, 33–44 (2005) 20. Marefat, Y., Iranmanesh, A., Tehranian, A.: On the sum of element orders of finite simple groups. J. Algebra Appl. 10(2) (2013) 21. McCarthy, J.P.: Introduction to Arithmetical Functions. Springer, New York (1986) 22. Rosen, K.H.: Discrete Mathematics and Its Applications, 7th edn. McGraw-Hill, New York (2007) 23. Schmutz, E.: Proof of a conjecture of Erd˝os and Turán. J. Number Theory 31(3), 260–271 (1989) 24. Spencer, J.: (with L. Florescu), Asymptopia (Student Mathematical Library), vol. 71. American Mathematical Society, Providence (2014) 25. Stanley, R.P.: Enumerative Combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge (1997) 26. Walfisz, A.: Weylsche Exponentialsummen in der neueren Zahlentheorie, Mathematische Forschungsberichte 15 VEB Deutscher Verlag der Wissenschaften, Berlin (1963)

123