arXiv:1710.10069v1 [] 27 Oct 2017

THE MULTIPLICITIES OF ROOT NUMBER FUNCTIONS
STEFAN-CHRISTOPH VIRCHOW
Abstract. We consider the qth root number function for the symmetric
group. Our aim is to develop an asymptotic formula for the multiplicities
of the qth root number function as q tends to ∞. We use character theory,
number theory and combinatorics.

1. Introduction
Let q be a positive integer. We define the qth root number function rq : Sn → N0
via
rq (π) := #{σ ∈ Sn : σ q = π}.
Obviously, rq is a class function of the symmetric group Sn . For each irreducible
character χ of Sn let
mχ(q) := hrq , χi
be the multiplicity of χ in rq .
Scharf [7] proved that the qth root number functions rq are proper characters,
(q)
that is, the multiplicities mχ are non-negative integers. A good account of results
on root number functions can be found in [3, Chapter 6.2 and 6.3].
(q)
We now pay attention to the multiplicities mχ . Müller and Schlage-Puchta
(q)
established estimates for the multiplicities mχλ (cf. [5, Proposition 2 and 3]). In
addition, they showed the following: Let ∆ ∈ N be fixed and let q > 2 be an integer.
Given a partition µ ⊢ ∆, there exists some constant Cµq , depending only on µ and
q, such that for n sufficiently large and for a partition λ = (λ1 , . . . , λl ) ⊢ n with
(q)
λ\λ1 := (λ2 , . . . , λl ) = µ, we have mχλ = Cµq . In particular, we get
q
C(1)
= σ0 (q) − 1

1
(σ1 (q) + σ0 (q)2 − 3σ0 (q) + σ0′ (q))
2
1
= (σ1 (q) + σ0 (q)2 − 3σ0 (q) − σ0′ (q)) + 1,
2

q
C(2)
=
q
C(1,1)

where σ0′ (q) is the number of odd divisors of q.
Our aim is to generalize this result. We establish an asymptotic formula for the
(q)
multiplicities mχλ as q tends to ∞. More precisely, we claim the following:
log q
Theorem 1.1. Let q ∈ N be sufficiently large and let ∆ ∈ N with ∆ 6 log
2 . In
addition, let n > ∆q be an integer. Then, for partitions λ ⊢ n and µ ⊢ ∆ with
1

2

STEFAN-CHRISTOPH VIRCHOW

λ\λ1 = µ, we have


σ0 (q) + O(1)





 1 σ1 (q) + O (σ0 (q))2
2
(q)
mχλ = χµ (1)

1 (q))

6 σ2 (q) + O(σ0 (q)σ





 χµ (1) σ∆−1 (q) + O χµ (1) q ∆−2 ∆σ0 (q) + 2∆ 
∆!
∆!

if ∆ = 1
if ∆ = 2
if ∆ = 3
if ∆ > 4.

The O-constant is universal.

Remark 1.2. The error term in our asymptotic formula is essentially optimal.
The proof of our Theorem proceeds as follows: At first, we realize that for π ∈ Sn
the value χλ (π) is a polynomial in the number ci (π) of i-cycles of the permutation
π for i = 1, . . . , n. We use this result to establish a formula with main and error
(q)
term for mχλ , where the random variables ci appear again. Secondly, we summarize
identities and estimates for Stirling numbers of the first and second kind and then
we review bounds for the divisor function. Thirdly, we examine the distribution of
cycle in Sn and compute the mean of (ck1 )m1 · . . . · (ckj )mj . The formula for the
mean includes Stirling numbers of the second kind. Finally, we calculate the main
(q)
and the error term of mχλ obtained in the first step using the outcomes of step two
and three.
Some notation. A partition of n is a sequence λ = (λ1 , λ2 , . . . , λl ) of positive
integers such that λ1 > λ2 > . . . > λl and λ1 + λ2 + . . . + λl = n. We write
λ ⊢ n to indicate that λ is a partition of n. By λ\λ1 we mean the partition
Pl
λ\λ1 = (λ2 , λ3 , . . . , λl ). The weight |λ| of λ is |λ| = j=1 λj . For partitions λ, µ
we write µ ⊂ λ, if µj 6 λj for all j.
We denote by χλ the irreducible character of the symmetric group Sn corresponding
to the partition λ of n.
For a permutation π ∈ Sn and 1 6 i 6 n let ci (π) be the number of i-cycles of π.
Furthermore, for α ∈ R let
X
dα
σα (q) :=
d|q

be the divisor function. As usual, we denote by ζ(s) the Riemann zeta function
and we write (n,
 k) forthe greatest common divisor of n and k.
We denote by nk and nk the Stirling numbers of the first and second kind, respectively. Finally, (x)n denotes the falling factorial.
2. Proof of the Theorem

In this section, we use character theory to derive a formula with main and error
(q)
term for the multiplicities mχλ . We apply this result to prove our Theorem.
Müller and Schlage-Puchta [5, Lemma 7] established the following.
Lemma 2.1. Let λ ⊢ n be a partition, µ = λ\λ1 , and let π ∈ Sn be a permutation.
Then
X
X
Y ci (π)
|µ̃|
χλ (π) =
(−1)
,
χµ,µ̃ (c)
ci
µ̃⊆µ
µ̃1 61

c⊆S|µ|−|µ̃|

i6|µ|

THE MULTIPLICITIES OF ROOT NUMBER FUNCTIONS

3

where c runs over all conjugacy classes of S|µ|−|µ̃| , χµ,µ̃ (c) denotes the number of
ways to obtain µ̃ from µ by removing rim hooks according to the cycle structure of
c, counted with the sign prescribed by the Murnaghan-Nakayama rule1, and ci is
the number of i-cycles of an element of c.
This result shows that χλ (π) is a polynomial in ci (π) for i = 1, . . . , |µ| with leading
term χµ (1)(|µ|!)−1 c1 (π)|µ| . We now observe:
Lemma 2.2. Let λ ⊢ n and µ ⊢ ∆ be partitions with µ = λ\λ1 , and let π ∈ Sn be
a permutation. Then we have





∆ 
X
c
(π)
+
.
.
.
+
c
(π)
c1 (π)
1
j+1
.
χλ (π) = χµ (1)
+ O χµ (1)
∆
−
j
∆
j=1

Proof. Applying Lemma 2.1, we obtain


 X
c1 (π)
χλ (π) = χµ (1)
+
(−1)|µ̃|
∆
µ̃⊆µ
µ˜1 61

X

c⊆S∆−|µ̃|

Y ci (π)
χµ,µ̃ (c)
,
ci
i6∆

where c runs over all conjugacy classes of S∆−|µ̃| except the trivial class of S∆ .
Therefore, we realize the expected main term. We shall show that the second term
in the above formula can be absorbed into the error term.
At first, we observe that |χµ,µ̃ (c)| 6 χµ (1) for a conjugacy class c of S∆−|µ̃| . Secondly, let c be a conjugacy class of Sk with 1 6 k 6 ∆ and let ci be the number
of i-cycles of an element of c. Suppose that c1 + c2 + . . . + c∆ = ∆ − j for some
positive integer j. Then we have ci = 0 for all i > j + 2.
Therefore, it follows that the absolute value of the considered second term in the
preceding formula is bounded above by

∆ 
∆
Y ci (π)
X
X
X
c1 (π) + . . . + cj+1 (π)
.
6 χµ (1)
χµ (1)
∆−j
ci
j+1
j=1
j=1
i6j+1
(c1 ,...,cj+1 )∈N0
1c1 +...+(j+1)cj+1 6∆
c1 +...+cj+1 =∆−j

This yields our assertion.



Due to
mχ(q)
=
λ

1 X
χλ (π q ),
n!
π∈Sn

we obtain as immediate consequence of the preceding Lemma the following result.
Proposition 2.3. Let λ ⊢ n and µ ⊢ ∆ be partitions with µ = λ\λ1 , and let q ∈ N.
Then we get



∆ X 
q
q
X c1 (π q )
X
χ
(1)
c
(π
)
+
.
.
.
+
c
(π
)
χ
(1)
µ
1
j+1
µ
.
mχ(q)
=
+O
λ
n!
n! j=1
∆
∆−j
π∈Sn

Now, we give the

1Cf. for instance [6, Theorem 4.10.2]

π∈Sn

4

STEFAN-CHRISTOPH VIRCHOW
(q)

Proof of Theorem 1.1. We stated a formula with main and error term for mχλ in
Proposition 2.3. In section 5, we will evaluate the main term: see Proposition 5.3.
In section 6, we will estimate the error term: cf. Lemma 6.2. Therefore, the proof of
our Theorem is completed. Moreover, the error term in our Theorem is essentially
optimal due to the Remark 5.4.

In the next two sections, we shall establish some auxiliary results.
3. Combinatorics and number theory
In this section we review some results about Stirling numbers of the first and
second kind as well as basic facts about the divisor function.
Definition 3.1.
Let n and k be positive integers. The Stirling numbers of the

second kind nk count the number of ways to partition a set of n labeled objects
into k nonempty unlabeled subsets.
Lemma 3.2. Let n and k be positive
 n integers.

1) We have n2 = 2n−1 − 1 and n−1
= n2 .
2) In addition, we state the recurrence
 
 
k−1
X
n
k!
n
n
.
k!
=k −
(k
−
j)!
j
k
j=1
Proof. 1) follows from the definition. For the proof of 2) see [4, Theorem 7.2.6]. 

This recurrence yields an upper bound for nk . Next, we would like to represent
the ordinary powers xn by falling factorials (x)k := x(x − 1) · . . . · (x − k + 1).
Lemma 3.3. Let n be a positive integer. Then the identity
n  
X
n
n
x =
(x)k
k
k=1

holds.

Proof. See for instance [1, Formula (6.10)].



Now, we pay attention to the Stirling numbers of the first kind.
Definition
3.4. Let n and k be positive integers. The Stirling numbers of
 
 the
 first
kind nk count the number of ways to arrange n objects into k cycles. So nk equals
the number of permutations of n elements with exactly k disjoint cycles.
Lemma 3.5. Let n and k be positive integers.
1) We have the recurrence
 

 

n
n−1
n−1
= (n − 1)
+
.
k
k
k−1
2) We obtain the estimate
 


(n − 1)!
n
n
6
.
k
k!
k−1

THE MULTIPLICITIES OF ROOT NUMBER FUNCTIONS

5

Proof. 1) Cf. [1, Formula (6.8)].
2) By induction over n: Obviously, the estimate is true for n 6 k. Applying the
recurrence 1) yields for n > k








k
n! n + 1
n
n
n!
n+1
+
6
.
6
k!
n k−2
k! k − 1
k−1
k

Stirling numbers of the first kind are (up to sign) the coefficients of ordinary powers
that yield the falling factorial (x)n . More precisely, we get
Lemma 3.6. Let n be a positive integer. Then the identity
 
n
X
n k
x
(x)n =
(−1)n−k
k
k=1

holds.

Proof. See for instance [1, Formula (6.13)].



Finally, we state results about the divisor function.
log q

Lemma 3.7. 1) Let ǫ > 0. Then we have σ0 (q) 6 (2 + ǫ) log log q for all q > q0 (ǫ).
2) σ1 (q) ≪ q log log q for all q > q0 .
3) Let k > 2. Then q k 6 σk (q) 6 ζ(2)q k .
Proof. For 1) and 2) see [2, Theorem 317 and Theorem 323].
3) The lower bound is obvious. The upper bound follows from the fact
X 1
.
σk (q) = q k
dk
d|q


4. Statistics of the symmetric group
Müller and Schlage-Puchta [5, Lemma 13] showed that, for π ∈ Sn chosen at
random, the distribution of ck (π) converges to a Poisson distribution with mean
1
→ ∞. In addition, they proved that the mean of (ck (·))m converges to
k as n
P
m m
−s
as n → ∞. We generalize this result and make it more explicit.
s=1 s k
Proposition 4.1. Let k1 , . . . , kl be distinct positive integers and let mj ∈ N for
j = 1, . . . , l. Then
!

mj 
l
l
X
Y
 mj
1 X Y
mj −s
.
kj
6
ckj (π)
s
n!
j=1 s=1
j=1
π∈Sn

If

Pl

j=1

kj mj 6 n is fulfilled, then we have an equality.

Proof. 1) Let k1 , . . . , kl be distinct positive integers and let sj ∈ N for j = 1, . . . , l.
We observe

Pl
 0
l 
if
X Y
ckj (π)
j=1 kj sj > n


−1
=
Ql
Pl
sj
n!
sj
if
j=1 kj sj !
j=1 kj sj 6 n.
j=1
π∈Sn

6

STEFAN-CHRISTOPH VIRCHOW

You can see this equality as follows.
Pl
Case 1: Let
j=1 kj sj > n. Then there exists no π ∈ Sn such that ckj (π) > sj
for all j = 1, . . . , l. Therefore, the considered sum is equal to 0.
Pl
Case 2: Let
j=1 kj sj 6 n. Then the left hand side of the equation is equal to
the number of tuples (τ1 , . . . , τl+1 ), which satisfy the following condition: There
exists distinct, disjoint cycles σij and a non-negative integer sl+1 such that τj =
σ1j · . . . · σsj j for all j = 1, . . . , l + 1, the cycles σij have length kj for all j = 1, . . . , l
Ql+1 Qsj
σij is the cycle decomposition for a permutation from Sn . Finally,
and j=1 i=1
the number of these tuples is equal to
n!
(n − k1 s1 )!
· ...
s2
− k1 s1 )! k2 s2 !(n − k1 s1 − k2 s2 )!


Pl−1

l
n − j=1 kj sj ! 
X

 n−
kj sj !
...·
Pl
klsl sl ! n − j=1 kj sj !
j=1

k1s1 s1 !(n

Canceling yields our assertion.
2) It follows from 1) that

l

1 X Y
ckj (π) s =
j
n!
j=1
π∈Sn

(

0
Ql

−sj

j=1

kj

Pl
if
kj sj > n
Pj=1
l
if
j=1 kj sj 6 n.

3) Eventually, we compute the desired mean of a product of random variables ck (·).
Applying Lemma 3.3 and 2) yields
! l  
!
l
l
Y mi
Y
X
Y
mj
(ckj )sj
E
=
ckj
E
si
i=1
j=1
j=1
(s1 ,...,sl )
16sj 6mj

6

X

(s1 ,...,sl )
16sj 6mj

=

l
Y

j=1

Obviously, we have an equality if

Pl

 
l 
Y
mj
−s
kj j
sj
j=1


mj 
X
mj −s
kj
s
s=1

j=1

!

.

kj mj 6 n is fulfilled.



Furthermore, Müller and Schlage-Puchta [5, Formula (33)] established the following
useful identity.
Lemma 4.2. Let d and q be positive integers and let π ∈ Sn . Then
X
cd (π q ) =
(k, q)ck (π).
k
k/(k,q)=d

5. The main term
We carry out the first step of the plan formulated in the proof at the end of
section 2: We compute the main term in Proposition 2.3. At first, we draw our
attention to the mean of a power of c1 (π q ).

THE MULTIPLICITIES OF ROOT NUMBER FUNCTIONS

Lemma 5.1. Let q ∈ N be sufficiently large and let δ ∈ N with
addition, let n > δq be an integer. Then we obtain


σ0 (q)
if




2
δ σ1 (q) + (σ0 (q))
if
1 X
c1 (π q ) =

n!
σ2 (q) + O(σ0 (q)σ1 (q))
if

π∈Sn






σδ−1 (q) + O q δ−2 δσ0 (q) + 2δ
if

7

δ 6

log q
log 2 .

In

δ=1
δ=2
δ=3
δ > 4.

The O-constant is universal.
Proof. 1) At first, we consider the case δ ∈ {1, 2}. We sketch the argument for
δ = 2 (the case δ = 1 is similar). Using Lemma 4.2 we get
2 X 1 X
X
1 X
1 X
2
k2
c1 (π q ) =
k1 k2
(ck (π)) +
ck1 (π)ck2 (π).
n!
n!
n!
π∈Sn

π∈Sn

k|q

(k1 ,k2 )
ki |q
k1 6=k2

π∈Sn

Since n > 2q, it follows with Proposition 4.1 that the considered mean is equal to
σ1 (q) + (σ0 (q))2 . This shows our claim for δ = 2.
2) We generalize this method for an arbitrary δ. Let n > δq. Applying Lemma 4.2
and Proposition 4.1 yields
δ
δ X
1 X
c1 (π q ) =
n!
π∈Sn

X

X

l=1 {M1 ,...,Ml } (k1 ,...,kl )
ki |q
ki 6=kj (i6=j)


j| 
l |M
X
Y
|Mj | |Mj |−s
kj
,
s
j=1 s=1

where the second sum on the right is over all set partitions of {1, . . . δ} in exactly
l sets M1 , . . . , Ml .
3) We direct our attention to
Tm

m  
m  
XX
m m−s X m
σm−s (q).
k
=
:=
s
s
s=1
s=1
k|q

log q
Let q be sufficiently large and m 6 log
2 . Then


if m = 1
σ0 (q)
Tm 6 σ0 (q) + σ1 (q) if m = 2

 m−1
3q
if m > 3.

In particular, we have T2 6 qσ0 (q).
You can see this estimate as follows: The cases m = 1 and m = 2 are obvious. Let
m > 3. It results from Lemma 3.2 and Lemma 3.7 for a constant C > 0
m−2
X m
2
m−1
Tm 6 Cm q log log q + ζ(2)q
q −s+1 .
s
s=1

8

STEFAN-CHRISTOPH VIRCHOW

Applying the estimate

m

6 sm (s!)−1 (see Lemma 3.2) we find that

s

m−2
X
s=1


m −s+1
q
6e−1
s

This proves our assertion.
4) Let q be sufficiently large and δ 6
m1 + . . . + ml = δ, we have
l
Y

j=1

log q
log 2 .

Then, for positive integers mi such that


l
Tmj 6 q δ−l max{3, σ0 (q)} .

This results immediately from 3).
5) Using the outcomes of step 2) and 4), we obtain

δ  
δ
δ X X
X
δ
1 X
k δ−s + O 
c1 (π q ) =
n!
s
s=1
π∈Sn

where

X

l
Y

l=2 {M1 ,...,Ml } j=1

k|q


= σδ−1 (q) + O F1 + F2 + F3 ,




T|Mj | 

δ  
X
δ
σδ−s (q),
s
s=2
X
T|M1 | T|M2 | ,
F2 :=

F1 :=

{M1 ,M2 }

F3 :=

δ  
l
X
δ δ−l 
max{3, σ0 (q)} .
q
l
l=3

The sum in F2 is over all set partitions of {1, . . . , δ} in exactly two sets M1 , M2 .
Therefore, we realize the expected main term. We shall show that the error term
is sufficiently small.
6) For the rest of the proof let 3 6 δ 6
F1 ≪

(

log q
log 2 .

σ1 (q)
2δ q δ−2

Lemma 3.7 and Lemma 3.2 yield
if δ = 3
if δ > 4

and
F3 ≪ 2δ q δ−2 ,
which is sufficiently small.

THE MULTIPLICITIES OF ROOT NUMBER FUNCTIONS

9

7) Finally, we examine F2 . The term F2 determines the order of the error term.
More precisely, we get
 
 
X
δ
δ
T|M1 | T|M2 |
F2 6
T1 Tδ−1 +
T2 Tδ−2 +
1
2
{M1 ,M2 }
|Mi |>3



if δ = 3
σ0 (q)σ1 (q)
≪ σ0 (q)q 2
if δ = 4


 δ−2
δ
q
δσ0 (q) + 2
if δ > 5.

In the last estimate, we used the outcome of step 3). In addition, we applied
the inequality (σ1 (q))2 6 98 σ0 (q)q 2 for δ = 4 and the fact that δ 2 σ1 (q)q −1 6
δ 2 (log σ0 (q) + 1) ≪ max{2δ , δσ0 (q)} for the case δ > 5. Therefore, the proof is
completed.

Our next aim is to show that the result stated in Lemma 5.1 is essentially optimal.
log q
Lemma 5.2. Let q be prime and let δ 6 log
2 be a positive integer. In
n > δq be an integer. Then we get

σ0 (q)

δ 
1 X
q
c1 (π ) = σ1 (q) + (σ0 (q))2

n!

π∈Sn
σ (q) + q δ−2 δ + 2δ−1 − 1 + O 3δ q δ−3 
δ−1

addition, let
if δ = 1
if δ = 2
if δ > 3.

The O-constant is universal.

Proof. 1) For δ ∈ {1, 2} see Lemma 5.1. So let δ > 3. Since q is prime, Lemma 4.2
and Proposition 4.1 yield
δ  
δ
1 X X δ
1 X
c1 (π q ) =
(c1 (π))δ−k (qcq (π))k
n!
n!
k
π∈Sn

π∈Sn k=0

= σδ−1 (q) + q δ−2 (δ + 2δ−1 − 1) + F1 + F2 + F3 ,

where
δ  
X
δ δ−t
q ,
t
s
t=3
s=2
!
! k  
δ−2   δ−k
X
X k
X δ − k 
δ
k−t
,
F2 :=
q
t
s
k
t=1
s=1
k=1


X
δ−1 
δ − 1 δ−1−t
δ
F3 :=
q
.
t
δ − 1 t=2

F1 :=

δ  
X
δ

+

So we found the expected main term. We shall show that F1 , F2 and F3 can be
absorbed into the error term.
δ
q
δ
−1
2) Taking into account that 3 6 δ 6 log
, we obtain
log 2 and t 6 t (t!)
!
 
  X


δ
δ
δ
δ 3−t
F1 ≪
+ q δ−3
+
q
≪ 3δ q δ−3 ,
2
3
t
t=4

10

STEFAN-CHRISTOPH VIRCHOW

and
!
δ−2   δ−k
δ−2  
X
X
X δ − k 
δ
δ
k−1
δ−3
F2 ≪
q
≪q
6 2δ q δ−3
s
k
k
s=1
k=1

as well as

k=1

F3 ≪ 2δ q δ−3 δ.
So we are done.



Proposition 5.3. Let q ∈ N be sufficiently large and let ∆ ∈ N with
addition, let n > ∆q be an integer. Then

σ0 (q)







1

2
q
1 X c1 (π )
2 σ1 (q) + O (σ0 (q))
= 1
 σ2 (q) + O(σ0 (q)σ1 (q))
n!
∆

π∈Sn
6



1
1 ∆−2
∆σ0 (q) + 2∆
∆! σ∆−1 (q) + O ∆! q

∆6

log q
log 2 .

In

if ∆ = 1
if ∆ = 2
if ∆ = 3
if ∆ > 4.

The O-constant is universal.
Proof. 1) It follows from Lemma 3.6 that


1 X c1 (π q )
1 X
∆!
=
(c1 (π q ))∆ + O(F ),
n!
n!
∆
π∈Sn

π∈Sn

where
F :=

∆−1
X
δ=1


∆ 1 X
(c1 (π q ))δ .
δ n!
π∈Sn

The main term in the above formula is the mean we computed in Lemma 5.1.
Applying this Lemma, we get the expected main and error term. Therefore, it only
remains to be examined whether the error term F is sufficiently small.
2) Before we analyze the error term, we give two technical estimates.
q
Let ∆ 6 log
log 2 . Then Lemma 3.5 yields:
 
∆−3
i) For ∆ > 3 and δ ∈ {1, 2} we have ∆
.
δ ≪q
∆
ii) For ∆ > 4 and 1 6 δ 6 ∆ − 1 we get δ 6 ∆2 q ∆−δ−1 .

3) Now we estimate the error term F . For ∆ = 1 we obtain F = 0. For ∆ = 2
Lemma 5.1 yields, that F = σ0 (q). So let ∆ > 3. Applying Lemma 5.1, Lemma
3.7 and the upper bounds of step 2) we get
F ≪ q ∆−3 σ1 (q) +

∆−1
X
δ=3

which is sufficiently small.

∆2 q ∆−δ−1 σδ−1 (q) 6 q ∆−2




σ1 (q)
+ ∆3 ,
q


Remark 5.4. The error term in the preceding Proposition is essentially optimal:
Confer Lemma 5.2 and step 1) in the above proof.

THE MULTIPLICITIES OF ROOT NUMBER FUNCTIONS

11

6. The error term
We implement the second step of our plan: We compute the error term in Proposition 2.3.
Lemma 6.1. Let q ∈ N be sufficiently large and let 1 6 r 6 exp(q 1/3 ). In addition
log q
let δ ∈ N with δ 6 log
2 and n be a positive integer. Then

1 X
n!

π∈Sn

where Hr :=

Pr


σ0 (q)Hr



!δ

r

X
(σ0 (q))2 Hr2 + σ1 (q)Hr
cd (π q )
≪

q 2 Hr
d=1


 δ−1 2
q
Hr

1
d=1 d .

if δ = 1
if δ = 2
if δ = 3
if δ > 4,

The O-constant is universal.

Proof. 1) Similar to step 2) in the proof of Lemma 5.1, we obtain


!δ

|Mj | 
r
δ
l
X
X
Y X
X |Mj |

1 X X

cd (π q )
k −s 
(k, q)|Mj |
6

,
n!
s
s=1
j=1
π∈Sn

d=1

l=1 {M1 ,...,Ml }

k
k6(k,q)r

where the second sum on the right is over all set partitions of {1, . . . δ} in exactly
l sets M1 , . . . , Ml .
2) We draw our attention to
X

(k, q)m

k
k6(k,q)r

 
r
m
m  
X
m −s X X 1 m
k =
s
ds s
s=1
s=1
d=1

X

k
k=(k,q)d

 m−s
k
d

r
m  
X
1X m
σm−s (q)
6
d s=1 s
d=1

= Hr T m ,

where Tm is defined as in step 3) in the proof of Lemma 5.1.
3) The previous considerations in combination with Step 4) in the proof of Lemma
5.1 yield
!δ
r
1 X X
q
cd (π )
n!
π∈Sn

d=1

6 Hr Tδ + Hr2

X

{M1 ,M2 }

T|M1 | T|M2 | +

δ
X
l=3

Hrl

 
l
δ δ−l 
q
max{3, σ0 (q)} .
l

Taking into account that Hr 6 log r + 1, our claim follows from step 3) and 7) in
the proof of Lemma 5.1 and from the estimates in Lemma 3.2 and 3.7.


12

STEFAN-CHRISTOPH VIRCHOW

q
Lemma 6.2. Let q ∈ N be sufficiently large and let ∆ ∈ N with ∆ 6 log
log 2 . In
addition, let n be a positive integer. Then


1
if ∆ = 1




∆ X 

q
q
X
σ0 (q)
if ∆ = 2
1
c1 (π ) + . . . + cj+1 (π )
≪

n! j=1
∆−j
σ
(q)
if
∆=3
1

π∈Sn


 1 q ∆−2 if ∆ > 4.
(∆−1)!

The O-constant is universal.

Proof. 1) The case ∆ = 1 is obvious. So let ∆ > 2. For 1 6 i 6 ∆ consider


i! X c1 (π q ) + . . . + c∆−i+1 (π q )
Q(i, ∆) : =
n!
i
π∈Sn
!δ
 
i
X
X ∆−i+1
X
i−δ i 1
q
=
(−1)
cd (π ) .
δ n!
δ=1

π∈Sn

The above equality is true due to Lemma 3.6. It
of Proposition 5.3 and with Lemma 6.1 that


σ0 (q)H∆
2
Q(i, ∆) ≪ σ1 (q)H∆−1

 i−1 2
q H∆−i+1

d=1

follows with step 2) in the proof
if i = 1
if i = 2
if i > 3.

In the case i = 2 we also used the estimate (σ0 (q))2 6 2σ1 (q).
2) Finally, we look at


∆−1
∆
X Q(i, ∆)
1 X X c1 (π q ) + . . . + cj+1 (π q )
.
=1+
R∆ :=
n! j=1
i!
∆−j
i=1
π∈Sn

Due to the result of step 1), we find that


σ0 (q)
R∆ ≪ σ1 (q)

 1 q ∆−2
(∆−1)!

So we are done.

if ∆ = 2
if ∆ = 3
if ∆ > 4.


References
[1] R. L. Graham, D. E. Knuth, O. Patashnik: Concrete Mathematics, Addison-Wesley, Reading, Massachusetts (1991).
[2] G. H. Hardy, E. M. Wright: An Introduction to the Theory of Numbers, Clarendon, Oxford
(1954).
[3] A. Kerber: Algebraic Combinatorics Via Finite Group Actions, BI-Wissenschaftsverlag,
Mannheim-Wien-Zürich (1991).
[4] V. H. Moll: Numbers and Functions, AMS, Providence, Rhode Island (2012).
[5] T. W. Müller, J.-C. Schlage-Puchta: Character theory of symmetric groups, subgroup
growth of Fuchsian groups, and random walks, Adv. Math. 213 (2007), 919-982.
[6] B. E. Sagan: The Symmetric Group, Springer, New York (2001).
[7] T. Scharf: Die Wurzelanzahlfunktion in symmetrischen Gruppen, J. Algebra 139 (1991),
446-457.

THE MULTIPLICITIES OF ROOT NUMBER FUNCTIONS

Author information
Stefan-Christoph Virchow, Institut für Mathematik, Universität Rostock
Ulmenstr. 69 Haus 3, 18057 Rostock, Germany
E-mail: stefan.virchow@uni-rostock.de

13

