$55.11., “hm.

Ft.

3',
!,

' ’5‘.

u.
.
‘

3H,.
3.9;.
s. .

.7: hf
.2111
. .1: AT,

.1... 1»:
. unit.
».:5. 34

 

.52)". gu‘wau 1.. .14

 

v J» L .
._ is... ... f if ,

2.6.5“. «as.
. ‘ .i x

agfigfififig ‘

.ai. )4.

THESES
I
(-7003
3/3545”

 

LIBRARY
Michigan State
University

 

 

 

This is to certify that the
dissertation entitled

Generating Function Proofs
of Identities and Congruences

presented by

Szu-En Cheng

has been accepted towards fulfillment
of the requirements for

ph n degree in Mathematim

 

:4 :7
Major WW

 

Date April 28, 2003

MS U is an Affirmative Action/Equal Opportunity Institution 0-12771

PLACE IN RETURN Box to remove this checkout from your record.
To AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6/01 cJClRC/DateDuepfis-sz

 

 

GENERATING FUNCTION PROOFS OF IDENTITIES AND
CONGRUENCES

By
Szu-En Cheng

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY
Department of Mathematics

2003

ABSTRACT

GENERATING FUNCTION PROOFS OF IDENTITIES AND
CONGRUENCES

By

Szu-En Cheng

In this study, we combine some ideas from formal power series and symmetric func-
tions to provide a uniform framework for proving congruences and identities. This setting
permits us to uniformly explain relationships between Waring’s Formulas, Newton’s Iden-
tity, symmetric functions, and linear recurrence relations.

We have several different applications. In the first application, we use the cycle indi-
cator Cn of the symmetric group and the Lagrange inversion Theorem to derive various
identities connecting several famous combinatorial sequences. In the second application,
we discuss the relationship between the number of periodic points in a dynamical system,
linear recurrence relations, and the power sum symmetric function in the characteristic
roots of the recurrence relation. In the final application, we use our results to give explicit
formulas for universal polynomials of universal A-rings. Moreover, we provide a connec-

tion of our work with ghost rings, necklace rings, and Witt vectors.

ACKNOWLEDGEMENTS

I felt that I was in a dream when I passed my thesis defense, not only because I came
back to MSU from Taiwan just one day before the defense, but also I finished my dis-
sertation with such a busy schedule. Hence, I would like to express my deepest gratitude
to my advisor, Professor Bruce E. Sagan, for his useful instruction, patient guidance, and
enormous help during my graduate career.

Thanks also go to members of my thesis committee, Professors Jonathan I. Hall, Tien-
Yren Li, Susan E. Schuur, and Peter Magyar, for their time and participation. Professors
Susan E. Schuur and Peter Magyar proofread this thesis — I owe them a sincere debt of
gratitude. I want to thank Professors Tien-Yren Li and Jonathan 1. Hall for guidance and
support.

I would also like to express appreciation for the support of my friends, especially Chih-
Hsiung Tsai for sharing a lot of good times and hard times together in the Mathematics
Department. Daniel Selahi Durusoy has shared his talents for being a mathematician and
runner — we had a lot of fun running together. Thanks go to Mei-Yu Tsai for her wisdom
and kindly help. Leah C. Howard is a very special friend at MSU; I will remember that we
exchanged many things about culture and life experience as well as a trip to Taiwan.

Finally, it is with greatest pleasure that I thank my wife, Chia-Lin, for her understanding
and confidence in me. Of course, I would like to thank my parents for their support and
encouragement. There are still many people I need to thank. So, thanks again for all who

love me and support me. Without them I could not make my dream come true!

iii

TABLE OF CONTENTS

0 Introduction

2

3

1 Preliminaries
1.1 Formal power series ..............................
1.2 Arithmetic functions .............................
Main Results
2.1 The types ...................................
2.1.1 Type I .................................
2.1.2 Type H ................................
2.1.3 Type III ................................
2.1.4 Type IV ................................
2.2 Some operations ................................
2.3 Congruences .................................
2.3.1 Type I .................................
2.3.2 Type H ................................
2.3.3 Type HI ................................
2.3.4 Type IV ................................
2.3.5 Some characterizations ........................
2.4 Basic identities ................................
2.5 Symmetric functions, linear recurrence relations and matrices ........
2.5.1 Symmetric functions .........................
2.5.2 Linear recurrence relations ......................
2.5.3 Matrices ................................
2.6 Various examples ...............................
2.6.1 Congruences .............................
2.6.2 Identities ...............................
Applications
3.1 Cycle indicators and combinatorial sequences ................
3.1.1 The Lagrange Inversion Theorem ..................
3.2 Dynamical Systems ..............................
3.2. 1 Introduction ..............................
3.2.2 Du’s Theorems and Conjectures ...................
3.3 Universal li-rings, ghost rings, necklace rings, and Witt vectors .......

iv

47
50

57
57
62
67
67
68
76

4 Open problems

BIBLIOGRAPHY

79

82

Chapter 0

Introduction

Formal power series (or generating functions) and symmetric functions are powerful tools
in algebraic combinatorics. In this study, we combine some ideas from both to provide a
uniform framework for proving congruences and identities. Specifically, let R (z) = 1 +
alz + 0222 + - -- be a fixed formal power series in C[[z]]. Since the constant term of R(z)

is 1, 1 / R (z) is still a formal power series over C with constant term 1. So, we can define
H(z)=l+h1z+h2z2+---e1+zC[[z]],

E(z)=1+e1z+ezz2+---e 1+zC[[z]],

and

P(z) = p1z+ p222 + ° -- 6 zCIIZII

by the equations

1
11(2): m:

E (z) = R(-z),

and

R’(z) _ zH’(z)
R(z) _ H(2)'

 

P(z) = -z

 

We then factor R(z) as

R<z> = 110+ Ran)“.

nzl

where the Rn (z) are formal power series in C[[z]] having z" as the smallest power with

nonzero coefficient. By using the following four types of factorizations:

Type I R(z) = “(l - Z")M”,

n21

Nn

Type II R(z)=H(l+z"+---+z(q‘”") ,

n21

(1 -Z")" 0"

Type III R(Z) = H (—ITZ—q‘n— ,

n21
Type IV th> = Ha — an")

n21

where q 3 2 is a positive integer, we derive various congruences and identities.

In the special case where R(z) is a polynomial, H (z), E (z), and P(z) become the gen-
erating functions for the complete homogeneous, elementary, and power sum symmetric
functions in the inverses of the roots of R(z). This setting permits us to uniformly ex-
plain relationships between Waring’s Formulas, Newton’s Identity, symmetric functions,
and linear recurrence relations.

We also give some characterizations of those coefficient sequences {pn}n21 of P(z)

which satisfy

ZMde/d a 0 (mod n)
dirt

or

Z#(d)Pn/d a 0 (mod q’n)
dln
(M

where q is a prime and t is a positive integer. Moreover, using our model, we settle several
conjectures in the literature and generalize some known theorems.

We have several different applications. In the first, we use the cycle indicator, C", of
the symmetric group

1 t1 kl ’2 k2 In kn
Cn(ti,t2,...,tn)= Z: k1!k2!---kn!(T) (2) .5

k1+2k2+m+nkn=n

 

to express relationships between R (z), H (z), E (z) and P(z). Moreover, we use the cy-
cle indicator and the Lagrange Inversion Theorem to derive various identities connecting
several famous combinatorial sequences.

In the second application, we discuss the relationship between the number of periodic
points in a dynamical system, linear recurrence relations, and the power sum symmetric
function in the characteristic roots of the recurrence relation. Moreover, we prove the
conjectures of Du in [15, 16, 17] and give algebraic proofs of some of his theorems.

In the final application, we use our results to give explicit formulas for universal poly-
nomials of universal i-rings. Moreover, we provide a connection of our work with ghost

rings, necklace rings, and Witt vectors.

Chapter 1

Preliminaries

We use the following notation: P is the positive integers, N is the nonnegative integers,
Z is the integers, Q is the rational numbers, R is the real numbers, and C is the complex

numbers.

1.1 Formal power series

We recall some definitions and properties of formal power series. Details can be found in

[24, 61].

Definition 1.1.]. The algebra of formal power series in 2 over C is

aneC foralanO

C[[z]] = Zanz"

n20

 

C[[z]] is an algebra under the operations:

Addition: zanz" + 212,2" =z(an+b,,)z".

n20 n20 n20

Product: Zanz" anz" = chz" where C" = 221:0 aibn—i-

n20 n20 n20
Scalar multiplication: c Zanz" = Z(c an)z" where c e C. I
n20 n20

If F (2) and G(z) are elements of C[[z]] satisfying F (z)G(z) = 1, then we write G(z) =
F(z)‘l.

Theorem 1.1.2. Let F(z) -_- anoanz" e C[[z]]. Then F(z)—1 exists ifand only ifao as 0.

We commonly write a0 = F (0), even through F (2) is not considered to be a function
of z.
We need to deal with infinite sums and products in C[[z]]. Hence, we need the concept

of convergence. For that, we need the following definition.
Definition 1.1.3. The order of nonzero F (z) e C[[z]] is

ordF(z) = the smallest n such that 2” has nonzero coefficient in F (z).

The leading coefficient of F (z) is the coefficient of zordnzl.

Definition 1.1.4. Let Fn (z) e C[[z]] for n 2 0. Then the limit Inigo Fn (z) = F (2) exists if
n

lim ord(F(z) — E, (z)) = 00. I
"—900
Now, we can define infinite sums and products.
Definition 1.1.5. Let Fn(z) e C[[z]] for n 2 O.

(i) The sum F(z) = ano Fn (2) exists in C[[z]] if and only if F(z) = lingo Sn (2) exists

where Sn(z) = Fo(z) + F1(z) + - - - + Fn(z)-

(ii) The product F(z) = “"20 F" (2) exists in C[[z]] if and only if F(z) = "11,120 B, (2)
exists where P,,(z) = Fo(z)F1 (z) - - - E, (z). I

Proposition 1.1.6.

(1') Let 17,,(2) e C[[z]]forn 2 0. Then 2,00 F" (z) converges ifand only if 13130 oran (z) =
- n

00.

(ii) Let F" (2) e C[[z]] with 17,,(0) = Oforn 2 0. Then 11,1200 + Fn (z)) converges ifand

only if lim oran (z) = 00. I
11—)00
We can now define the important composition operation.

Definition 1.1.7. Let F (z) = anoanz", G (z) = ano bnz" with b0 2 0, then we can de-

fine the composition F (G (z)) := 2a,, 0(2)". Note that be = O guarantees the convergence

n20

of the sum for F (G (z)). I
We will need the following particular series and operations in the next chapters.
Definition 1.1.8. We define the following formal power series.

(i) Exponential
2

Z
eXp(z):=l+z+§+°--
(ii) Logarithm
22 23
l 1 := —— ——--- I
og(+z) z 2+3

Definition 1.1.9. Let F(z) = anoanz" e C[[z]]. Then F(z) has

(i) formal derivative

F’(z) := 201 +1)a.+lz".

n20

(i i) formal integral

[Z F(x)dx:=2%z". I

0 n_>_l
Definition 1.1.10. Let F (2) = ano anz", 6(2) 2 anobnz" e C[[z]]. Then the Hadamard
product of F (2) and G(z) is defined by

F(z)®G(z) := Zanbnz". I

n20

1.2 Arithmetic functions

We also recall some definitions and properties of arithmetic functions (see e.g [2, 28]).

Definition 1.2.1. A complex-valued function defined on the positive integers is called an

arithmetic function. I

Definition 1.2.2. Let a and ,B be two arithmetic functions. The Dirichlet product (or

Dirichlet convolution) of a and ,8 is defined by

(a mo.) = Za(d)/3(n/d)- -

dln

We have some algebraic properties of the Dirichlet product.

Proposition 1.2.3. For any arithmetic fimctions a, ,8 and y we have

atfl = fl*a
(atfl)*y = a*(fl*y).

That is, the Dirichlet product is commutative and associative. I

Definition 1.2.4. The arithmetic function I given by

1 i =1
I(n)= l" ’
0 1fn>l.

is called the identity function.
The identity function I is the identity element for the Dirichlet product.
If a and ,6 are arithmetic functions satisfying a It ,8 = I , then we write ,8 = a"1 and call

,8 the Dirichlet inverse of a. I

Theorem 1.2.5. Let a be an arithmetic function. Then a”1 exists if and only if a(1) 75 0.

Definition 1.2.6. We define the unit function u to be the arithmetic function such that

u(n) = 1 for all n 21. I

We have the celebrated Mobius function and Mobius Inversion Theorem.

Definition 1.2.7. The Mobius function ,u (n) is defined by

1 if n = l,
u(n) = (—1)" ifn = p1p2---pk.
0 otherwise.
Note that u and ,u are the Dirichlet inverses of each other. I

Miibius Inversion Theorem. Let a (n) and ,8 (n) be arithmetic functions. Then
a(n)=Z,B(d), foralln 21.
d In
if and only if
,8(n)=Zu(d)a(n/d), foralln 2 1. I

dln

We also need the definition of the following function.

Definition 1.2.8. The Euler totient ¢(n) is defined to be the number of positive integers

g n which are relatively prime to n. I

Proposition 1.2.9. We have
Zo (d) = n. .

dln

In order to get congruences and identities in the next chapter, we need the following

notation.

Definition 1.2.10. We use the notation F (z) E G(z) (mod z") where F (2), 6(2) 6 C[[z]]
to mean F(z) - 0(2) 6 z"C[[z]].

If q e P, we also use the notation F (2) E G(z) (mod q) to mean that F (2) — G(z) e
qZ[[z]]. In other words, for each power of z, the difference between the corresponding
coefficients of F (2) and 0(2) is an integral multiple of q (even though the coefficients

themselves may be complex). I

Other definitions will be introduced as needed.

Chapter 2

Main Results

In this chapter, we use formal power series to obtain some general results for proving

identities and congruences.

2.1 The types

Let R(z) = l + alz + azz2 + - - - be a fixed formal power series in C[[z]]. Since the constant
term of R (z) is 1, 1/R(z) is still a formal power series over C with constant term 1. So, we
can define

H(z) = l+hlz+h2z2+m e l+zC[[z]],
15(2) = l+elz+e2z2+~~ e 1+zC[[z]],

and

P(z) = plz +P222 + - -- e z<C[[z]]

by the equations

H(z)=%z), (2.1)

E (z) = R(-z), (2.2)

and
R’(Z) = H ’(2)

R(z) z H(z) ' (2'3)

F(z) = -z

 

 

It is useful to write equation (2.3) as

R(z) = exp (—/0 Pix) dx) = exp — 25:51" . (2.4)

n21

 

As we will see in Subsection 2.5.1, if R(z) is a polynomial then H (z), E (z) and P(z)
are just the generating functions for the complete homogeneous, elementary, and power
sum symmetric functions in the reciprocals of the roots of R(z).

We will be interested in how various factorizations of R(z) translate in terms of H (z),

E (z) and P(z). But first we need some preliminary results.
Theorem 2.1.1. If Rn (z), for all n 2 l are formal power series in C[[z]] with oran (z) = n,
then there are unique C,, e C, n 2 1, with

R(z) = [10+ ma)“.

n21

Proof: Notice that

(1+ Rn(z))Cn =1+rnCnZn +"°

where ru 75 O is the leading coefficient of R, (z). Also multiplying any formal power series
by 1+ Rn (z) changes only the 21 terms for j 2 n. So, it is enough to show that we can find

C1,C2,~- sothat

n
R(z) E 1+a1z+---+anz" E H(l + Rj(z))Cj (mod z'H’l),
i=1

for all n e P.
We prove this by induction on n. For n = 1, let

0]
C1=—.
71

We have

R(z)sl+a1z E (1+ R1(z))Cl (mod zz).

Assume that there exist unique C j, for 1 S j S n — 1 such that

n-I
R(z); l+a1z+~-+a,,_1z"-l—:— H(l+ Rj(Z))Cj (mod 2").
j=1

10

Write

 

n—l
H(1+Rj(Z))C’=1+arz+---+an—1z"'1+&nz" + - --,
i=1
and let
c,, = a" 7a". (2.5)
rn
Then

n
H(1+Rj(z))ci = (1+a1z+---+a,,_1z""+a,,z"+-~-)(1+R,,(z))C"

i=1

= (1+a1z+-~+a,._1z"_1+Einz"+---)(l+(a,,-Zz,,)z"+---)

= l+aiz+-~+anz"+---
So,

It
R(z)-=-1+a1z+~-+a,,z" 2 Ha +Rj(z))C/ (mod 5'“)
i=1

Therefore, by induction, we are done. I

We need the following lemma and corollary to prove various integer congruences.
Lemma 2.1.2. Let q, t e P. If R(z) e qu[[z]], then
(1+ R(z))qH E 1 (mod q').

Proof: Induct on t. For t = 1, the result is trivial.

Assume the lemma is true for t — l 2 1, that is
(1+ R(z))"t_2 = 1 +q’"1R(z)

for some R(z) e zZ[[z]]. Then

(1+ R(z))q'”‘ = ((1+ R(z))q"2)q
= (1+q”11§(z))q
.. .. 2 ..
= 1+qq"1R(z) + (g) (q"lR(z)) + - - - + (qt—1R(z))q)
51 (mod q’)
since (q"l)i = q("1)i and (t — 1)i 2 t, fori 2 2, t 2 2. I

11

Corollary 2.1.3. Let q,t e P. Given Rn (z), for all n 2 l as in Theorem 2.1.1 with Rn (z) e
qz" (:I:l +zZ[[z]]) for all n 2 1. Then

R(Z) E 1+Q'ZZIIZII

ifand onlyif
c, e q'-'z foralln 21.

Proof: (<2) This follows from Lemma 2.1.2.

(=>) We proceed by induction on n as in the proof of Theorem 2.1.1. It is clear that
C16 q"1Z. Assume that C} e q"'Z, for 1 5 j g n — 1, then 5,, e q'Z by Lemma 2.1.2.
Therefore, by equation (2.5), C" e q"‘Z since an e q’Z and rn = :Eq. I

We will now introduce the four types of factorization that will concern us for the rest of

this thesis.

2.1.1 Type I

Let
Rn(z) = —z" Vn 21.

Using these polynomials, we have the next theorem.

Theorem 2.1.4. Let R(z) = 1+a1z +a2z2 + - .. e 1 + zC[[z]]. There are unique Mn 6

C,n 2 l, with

R(z) = no — z")M"- (2.6)

n21

Moreover; we have

p, = 2:de Vn 2 1 (2.7)

dln
and
1
M. = ; Zfl(d)Pn/d Vn 2 1. (2.8)
dln

12

Proof: The first statement is clear because of Theorem 2.1.1.
Now taking the logarithmic derivative on both sides of (2.6), and multiplying by —z

gives

 

That is,
P(Z) = ann(Zn +22" ‘i' ‘ ' ').

n21

Comparing the coefficients on both sides, we get
p, = Zde Vn 21.
d In
Finally, equation (2.8) follows by applying the Mobius Inversion Theorem to (2.7). I
We can now obtain the Cyclotomic Identity (see e.g. [40]) which has important appli-

cations in combinatorics.

Corollary 2.1.5 (Cyclotomic Identity). If a e P, then we have

1 ( 1 )M" 1 d
= H where Mn = —Zp(d)a"/ -
1—az n21 l—z" n

dln

 

 

Proof: Let R (z) = l —az. We get p" = a" from equation (2.3). Hence, by equation (2.6)
and (2.8), we have the desired result. I
Remark: It is worth noting that Mn = £26,", u(d)a"/d is the number of primitive

necklaces with n beads and a colors.

2.1.2 Type II

Let q > 1 be a positive integer and let
Rn(Z) =z"+---+z(‘"”" Vn 21.

Before we can state the analog of Theorem 2.1.4 in this context, we need the following

definition and lemma.

13

Definition 2.1.6. Let q > 1 be a positive integer. If n = mq‘ , where q [m, then we define

ordq (n) = s.

Lemma 2.1.7. Let {an}n21 and {,Bn},,21 be two sequences. Let q > 1 be a positive integer

and c be a constant. Then

 

r2:0ch ifCII",
db:
,= 2.9
’3 lzarcza. ifqln ‘ ’
dht

ifandonlyif
an=Z/t(d)fl5 +CZ#(d)flq% +~ +c 2mm...
dht dl” dlfr

where s = ordq (n).

Proof: Using equation (2.9), we define

ordb(n)

B(n):= Z Cifln/qr

i=0
= .Bn "I'CIBn/q 'l' ' ' ' 'I' csfln/qs

= Zad— CEIEad +c Zad-Czad + ~S+C Zad

dln dl— dl-z dl—g
H:-
dht
Hence, we have
fl __ B(n) ifqin,
n_ B(n)—cB(n/q) ifqln.

14

Now, by Mobius Inversion Theorem, we obtain

a. = Z#(n/d)3(d)

dm
ord§(d)
=Zu(n/d) z Cfld/q
dm
onQOG
= Z Z#(—q, 7i)6fld
i =0 dlfi
ordh(n)
= Z Zamor—
=0 .1];
=Z#(d)flg, “Zion/3,; +-- +CZ#(d)fl—-
dm ”I dPT
This establishes the result. I

Theorem 2.1.8. Let R(z) = l+alz +azz2 + e 1+zC[[z]]. There are unique Nn e

C,n 2 1, with

 

N.
R(z)=l—j[(l+z"+w+z(q’”") . (2.10)
n21
Moreover; V
—Zde ifqln:
dln (211)
p :4 °
" —Zde+quNd ifqln
dm dfi
and
Na: HZMdmn/qumdw +---+q‘Z/1(d)pq_gg (2.12)
dm dlg d%}

where s = ordq (n).

Proof: The first statement is clear because of Theorem 2.1.1.

We may rewrite

n Nn
R(z) = H(l+zn+...+z(Q-l)n)Nn = 1161:?!) . (2.13)

n21 n21

 

15

Now taking the logarithmic derivative on both sides of (2.13), and multiplying by —z gives

R’(z) qnzq” "Z"
_ = N — .
zR(z) Z "(l—z‘l" l—z")

n21

 

 

That is,

P(z) = anNn(zq" +z2q" +---)—ZnN,,(z" +z2"+---).
n21 n21

Comparing the coefficients on both sides, we get equation (2.11). Finally, by Lemma 2.1.7

(using an = —nN,,, ,8" = pn and c = q ), we have the last conclusion. I

2.1.3 Type 111

Let q > 1 be a positive integer and

(I-Z”)" _

l q" 1 Vn2l.
'—Z

Rn (Z) =

Using these R", we obtain the next theorem. Its proof is similar to that of Theorem 2.1.8

and so is omitted.

Theorem 2.1.9. Let R(z) = l +alz +a222 + - -- e l + zC[[z]]. There are unique 0,, e

 

C,n 2 1, with
_ (1 -2")" 0"
n21
Moreover: .
quOd ifq in.
dln
Pn = 1 (2-15)
9 ZdOd-Zdod ifélln
dln dlg
and
1
o. = 7 Ewan/1+ ZM‘DPqu + - - - + Zoom, (2.16)
q dln dlg dlj'j-
where s = ordq (n). I

The following corollary will be needed to establish the fundamental congruence for

Type III in Theorem 2.3.4.

16

Corollary 2.1.10. If q is a prime, we can write

1
0n = 72#(d)pn/d-
q dln
aid

Proof: We have

211 (d)Pn/d = 211 (d)Pn/d - Z#(d)pn/d

dln dln dln
qid qld
= Ztt (d)Pn/d - z#(qd)pq—';,
dln dIg-
= Dom/1 — ”(q) 214mg
dln dlg
W
= 2;! (d)Pn/d + Z# (0019;,
dln dig
(rid
= Emma/d +Zp(d)p,2, + - - . + Zp(d)p,g,
dln d]; dlé’y
where s = ordq (n). Comparing this equation with equation (2.16) gives the result. I
2.1.4 Type IV

In the subsection, we will study a different way to factor R(z). Rather than fixing Rn (z)
and finding the corresponding exponents, the exponents will all equal one and this will

determine appropriate Rn (z).

Theorem 2.1.11. Let R(z) = 1+a1z +61222 + - -- 6 1+ zC[[z]]. There are unique Q" e

C,n 2 l, with
R(z) = [In — an"). (2.17)
n21
Moreover, we have
pn = Zde/d Vn 21. (2.18)
dln

17

Proof: Comparing the coefficients on both sides of (2.17), we have

a.= z (—1)ro.,o..~-o.,

k1+k2+m+kr=n
lSk1<k2 <--' <k,$n

= Z (‘1)er1Qk2”'Qk, _Qn~
k1+k2+m+kr=n
15k] <k2<---<k, <n

Thus, we can recursively determine Q1, Q2, - - -.

Now, taking the logarithmic derivative on both sides of (2.17), and multiplying by —z

gives

R’ z z"

-2512. ._. Zn'fQL—n'
(Z) n21 - an
That is,
P(z) = Zn(Q.z" + Qizz” + - - -)

n21

Comparing the coefficients on both sides, we get equation (2.18). I

Remark: In this situation the p,, are called the ghost components of the Q" (see e.g.
[33, p.330]). We will discuss them in more detail in Section 3.3.

The analogue of Corollary 2.1.3 in this context is as follows.

Corollary 2.1.12. Let q e P and R (z) E 1 +le[[z]]. Then
R(z) e l+qu[[z]]

ifandonly if
Q" e qZ Vn 2 1.

Proof: (<=) This direction is obvious.
(=>) In the proof of Theorem 2.1.11, it is easy to see that if Qj e qZ, for 1 5 j 5 n —1

then Q" E qZ. Hence, we are done by induction. I

18

2.2 Some operations

We wish to express the relationships between the exponents in the Type I, II and IH factor-
izations. Let q > 1 be a positive integer. If

R(z) = H(1 -Z")M"

n21

= H(1+z" +...+z(q—1)n)”"

n21

_ (l-z”)" 0"
- (l-z‘l")

n21

then we have the following relations.
Corollary 2.2.1. If s = ordq (n) then

(i) Nn = _(Mn+Mn/q+'”+Mn/q5)a

.. 1 l 1
(ll) 0n=;(Mn+;MIl/q+'”+; n/qs),

’Nn ifqln’

(iii) M = _
n ["Nn'l'Nn/q tfqin.

Proof: Equations (i) and (ii) follow from Theorems 2.1.4, 2.1.8, and 2.1.9. Equation
(iii) follows directly from (i). I
It will be necessary to see how various operations on power series R(z) translate to the

corresponding P(z) series. We will start with product, quotient, and substitution.
Proposition 2.2.2. Suppose R(z), R(z) 6 1+ zC[[z]].

(i) We have
R(z) = R(z)li(z)

ifand only if
P(z) = P(z) + P(z)

where P(z) and P(z) are related to R(z) and R(z) as in equation (2.3).

19

(ii) Similarly, we have

R(Z) = R(z)/1%)

ifand only if
P(z) = P(z) - F(z)-

(iii) Let r E P and R(z) e l+zC[[z]]. We have
R(z) = R(z’)

ifand only if
P(z) =rP(z').

Proof: (i) (:>) By equation (2.3), we have

R’(z)

R(z)

_z R'(z)R‘(z) + R(z)R’(z)
R(2)R(Z)

P(z) _ Z Ii’(Z)

R(z) R(z)

= 13(2) + 13(2).

 

P(z) = -z

 

 

(4:) By (2.4), we obtain
R(z) = exp (- f0. Pixldx)
exp(- [OZ ( P(x) : P(x))dx)
z p z I;
= exp(-/0 ix)dx)exp(—/o 30(1):)

(ii) and (iii) are proved similarly.

 

 

 

 

We now consider an operation that will give the Hadamard product. We use [i , j] to

denote the least common multiple ofi and j and (i, j) to the great common divisor ofi and
j.

20

Proposition 2.2.3. Let R(z) and R(z) 6 1+ zC[[z]]. We have

R(z) = [Ia—N“.

n21
where
Mn = Z (LN/WM}
[i,jl=n
and 1171,, and Mn are related to [3,, and 13,, as in equation (2.7),or equivalently (2.8), if and
only if
Pzfiefi

Proof: (<=) From the definition of Hadamard product, we have p" = [in [3,. Hence, by

(2.7) and (2.8), we have

1
M. = ;;p(d)p./.
n

1
== ; Zita/cop.

dln

l - .
= - E ,#(n/d)pdpd
n
dln

= %Z#(n/d)ZiM,- 2;ij (by (2.7))

dln ild jld

1 .~ .~ "
= Z.EzMrJMj 2 'u (d[i,j])

 

"[i,-1:.
= Z (i,j)1i4,—M,- (sinceij=[i,j](i.j)).
[i,-1:.

(=>) Using the above calculation, we know

M. = Z (ADM-M,-
[i.jl=n

l - ..
=-Z#(n/d)Pde v. 21.
n dln

21

Hence, by Mobius Inversion Theorem and (2.7), we have

p. = szd = 5,13,, Vn 21.
dln

In this way we obtain the desired result. I

2.3 Congruences

In this section, we will use Types I—IV to derive the fundamental congruences for use in our

examples and applications.

2.3.1 Type I

The next result is equivalent to various results of Carlitz [7, 8] in number theory and of

Dold [13] in dynamical systems.

Theorem 2.3.1. The following three conditions are equivalent
(1') R(Z) e l+zZ[[z]i.
(ii) Mn 6% Vn 21,

(iii) Zuni»)... E 0 (mod n) Vn 2 1.
dln
Proof: (i) 4:) (ii) follows from Corollary 2.1.3 with q = t = 1.
(ii) ¢=> (iii) is clear from (2.8). I
Remark: It is important to note that in this result and others like it to follow, even
though the individual terms in the sum could be complex numbers, the sum itself is an

integer and divisible by the modulus.

As a special case, we obtain Fermat’s famous Little Theorem.

Corollary 2.3.2 (Fermat’s Little Theorem). Let a e Z and q be a prime, then

a" E a (mod q).

22

Proof: Let R(z) = l —az. We obtain p" = a" from equation (2.3). Hence, by Theo-

rem (2.3.1) we have

Zu(d)pq/d=aq—a_=_0 (mod q). I
dlq

2.3.2 Type 11

Theorem 2.3.3. Let q > 1 be a positive integer: Then the following three conditions are

equivalent
(1') R(Z)e 1+zZ[[z]].
(ii) N” 6% Vn 21,

(iii) Z#(d)Pn/d +qZu(d)p,a, + - - - +q‘ Zp(d)p,+, a 0 (mod n) v. 2 1.
dln dlg- dlcT”;
where s = ordq (n).

Proof: (i) <2 (ii) follows from Theorem 2.3.1 and Corollary 2.2.1. Since
R(z)el+zZ[[z]]ch,,eZ Vn2l<=>NneZ Vn2l.
(ii) <:> (iii) is clear from equation (2.12). I

2.3.3 Type III

Theorem 2.3.4. Let q be a prime and t be a positive integer: Then the following three

conditions are equivalent
(1') R(Z)€1+4'ZZ[IZII.
(ii) 0,, e q"lZ Vn 21,

(iii) 2 ”((1),)“, a 0 (mod q'n) Vn 2 1.
dln
4’14

23

Proof: (i) <=> (ii) follows by noticing that if q is prime then

(1 - z")q a 1— zq" (mod q).

That is,
(1 -z")"
W E 1+qZZ[[Z]].
Now, if
(1 -z")q 0"
R(z) - H (W ’
n21

then the result follows from Corollary 2.1.3.
(ii) 4: (iii) is from Corollary 2.1.10. I
The next theorem is similar to Dieudonné-Dwork’s Lemma for p-adic numbers. See,

for example, [50, 32].

Theorem 2.3.5. Let q be a prime. Then
R(Z) E 1+ zZHzl]
if and only if

R(z)q
R(z")

 

E 1+42ZIIZII-

Proof: Write
R(Z) = H(1 -z")M",

n21

~ R(zv (1 —z")q M"
R(Z) = R(zq) = "11 (——1_zqn ) .

Then, we have 0,, = Mn for all n 2 1. Hence,

and let

 

R(z) e 1+zZ[[z]] 4:) Mn 6 Z Vn 2 1 (By Theorem 2.3.1)

<=>OneZ Vn21

¢:> R(z) = R(z)q e 1+qu[[z]] (By Theorem 2.3.4).

 

This completes the proof. I

To use Theorem 2.3.4 in practice, we need to recast it in the following way.

24

Proposition 2.3.6. Let q be a prime andt e P. Suppose R(z), Ii (z) e l + zC[[z]]. Then

R(z) .=_ R(z) (mod q')

ifand only if
Z#(d)r3n/d E z#(d)13./d (mod 61’") Vn 2 1.
dln dln
qid qid
Proof: Let
R(z) = R(z)/R(z).
Then

R(z) ..——_ R(z) (mod q')
a» R(z) = R(z)/R(z) 21 (mod q')

¢:> Z ,u(d)p,,/d E 0 (mod q'n) Vn 2 1 (By Theorem 2.3.4)

dln
qid
‘27 Zl‘(d)PN/d E Z#(d)l3n/d (mOd qt") V" Z 1-
dln dln
qid qid

The last equivalence is because of Proposition 2.2.2.

The next two corollaries give examples of how Proposition 2.3.6 can be used.
Corollary 2.3.7. Fix a positive integer l.

(i) For the prime 2,
R(z) _=_ 1+zl (mod 2)

if and only if
1 (mod 2n) forn =12k, k 2 0,
2201);)... a .
dln 0 (111011 2n) otherwrse.
Zid

(ii) Letq 5£ 2 be aprime. Then
R(z) E 1+z’ (mod q)

25

if and only if

—1 (mod qn) forn = lq", k 2 0,
211mm,). 5 21 (mod qn) forn = zqu, k 2 o,

d I '
(Ii; 0 (mod qn) otherwrse.

Proof: (i) Let R(z) = 1—z’ -=- R(z) (mod 2). It is easy to see that 1171,- = ,1.
Now Corollary 2.2.1 shows that

.. .. - n ..
2n0,,=nM,,+ Mrt/2+"'+‘2's‘ n/2-‘

NIB

where s = ord2(n). Moreover, 2n 0,, has nonzero value if and only if 11711 appears on the
right-hand side of the above equation.
Hence, by Corollary 2.1.10, we get
2mm). = 2n 0. a

d In
2fd

1 (mod 2n) forn=12k, k20,
0 (mod 2n) otherwise.

Finally, by Proposition 2.3.6, we get the desired equivalence.
(ii) Let R(z) = l+zl = (1 -z')-1(1 -z21). It is easy to see that

—1 ifn = l,
M,, = 1 ifn = 21,
0 otherwise.

Now Corollary 2.2.1 shows that
A: ~ n ~ ’2 "’
qn0n=nMn+g n/q+”°+;Mn/q5

where s = ordq (n). Moreover, qn 0,, has nonzero value if and only if M; or 117121 appear on
the right-hand side of the above equation.

Hence, by Corollary 2.1.10, we get

—I (mod qn) forn = lq", k 2 0,
Zircon/d = qno, a 21 (mod qn) forn = 21qk, k 2 o,

g]; 0 (mod qn) otherwise.
Again, we use Proposition 2.3.6 to get the desired equivalence. I

26

Corollary 2.3.8. Let q be a prime.

(i) Supposel 2 2 andl #qsforanys 2 1. Then
R(z)21+z+---+z"1 (modq)

if and only if

—1 (modqn) forn=qk, k20,

Zu(d)p,,/d .=_- 1 (mod qn) forn = lq", k 2 0,

dl -
(Ii; 0 (mod qn) otherwrse.

(ii) Supposel 2 2 andl =q‘ for some s 2 1. Then
R(z) E 1+z+---+zl‘l (mod q)

if and only if

-1 (modqn) forn=qk, Osk<s,

Z#(d)Pn/d'_=' l—l (modqn) forn=qk, k2s,

dl '
fl; 0 (mod qn) otherwzse.

Proof: Let R(z) = 1+z+ - --+z"l = (l —z)“(l —z’). It is easy to see that

-1 ifn = 1,
Mn = l ifn = l,
0 otherwise.

Now the proof is finished in the same manner as in previous corollary.

2.3.4 Type IV
Theorem 2.3.9. Let q,t e P. IfR(z) e 1+q’zZ[[z]], then

pmqs E 0 (mod qt“)

forallm e Pands e N.

27

Proof: For q = 1 the result follows from the definition of P(z). Assume q 2 2. Notice
that, by Corollary 2.1.12, we have q’ | Q", for all n.
Let d be a divisor of mq‘. If ordq (d) = i and ordq (mq‘) = j then

ordq (d QZ'qS/d) 2 ordq (d) +ordq (QZqS/d)
2 i+tqj‘i (because q’ | Qd)
2i+t(j—i+1) (becauseq22)
=i+tj—ri+t
=(t—1)(j—i)+t+j

2t+s (becauset2l,j2iandj2s).
Therefore, by Theorem 2.1.11

dlmq‘

forallmePandseN. I

Remark: The converse of the above theorem is not true in general. For example, let

t=1and

_ qs+1 ifn=q", s 20,
p. _ 0 otherwise.

Then the pn satisfy the condition in the above theorem. Now let q be a prime not dividing

q. We have

2mm). = p. —m =0—q 20 (mod it
dlti

Therefore, by Theorem 2.3.1, R(z) ¢ l+zZ[[z]]. Hence, R(z) ¢ 1+qu[[z]].
However, in the next subsection, we will show that by adding one condition, the con-

verse will become true.

Proposition 2.3.10. Let q,t e r». IfR(z) a R(z) (mod q’) then

qu‘ E fimqs (mOd qt+3)

forallm e P, s e N.

28

Proof: Since

R
—.:£z—) E (mod qt).
R(z)
The conclusion follows by Theorem 2.3.9 and Proposition 2.2.2. I

2.3.5 Some characterizations

In this subsection, we will give some characterizations for {pnlnzb the sequence of coeffi-

cients of P(z). First, we need the following two results.
Lemma 2.3.11. Let a, ,B be arithmetic functions with integer values.

(i) Let q e P. Ifa(n) E. 0 (mod n) and ,B(n) E 0 (mod qn) for all n 2 1, then (a :1:
PM") E 0 (mod qn)for all n 2 1.

(ii) Ifa(l) = :l:l and a(n) E 0 (mod n)for alln 2 1, then a"1(n)E 0 (mod n)for all

n 2 1. Where 0(-1 is the Dirichlet inverse of a.
Proof:

(1) We have

(a too) = Emmet/d)

dln

= dedqgkg/d for some kd and kg/d e Z
dln

= Z‘lnkdkiz/d
dln

E 0 (mod qn).

(ii) Let a't(n) = u(n)/n which is integer-valued. Since 61(1) = :l:l, (it-1 exists and is still

integer-valued. So, a’1(n) = no?"1 (n) a 0 (mod n). I

The next theorem is a generalization of Jarden’s result in [30], here we give a simpler

proof.

29

Theorem 2.3.12. Let a, ,B be arithmetic functions with a (l) = i1 and for all n 2 2
zdln a(d) E 0 (mod n). Then

Zp(d),8(n/d) E 0 (mod n) for alln 2 l

dln
ifand only if

Za(d),8(n/d)20 (mod n) f0ralln2 1.

dln

Proof: ”=>” We are given (a a: u)(n) E 0 (mod n) and (,u *fl)(n) a 0 (mod n) for all
n 2 1. Therefore, by Lemma 2.3.1 1(i), we have

(a *fl)(n) = (a 4: u) at (p *fl)(n) E 0 (mod n) for all n 21.
”<=” Since (a * u)(n) E 0 (mod n) for all n 2 l, by Lemma 2.3.11(ii) we have
(a a: u)-1(n) E 0 (mod n) for all n 21.
Again, by Lemma 2.3.11(i) and (a *fl)(n) E 0 (mod n) for all n 2 1, we get

((a.u)-1.(a.fl))(n)so (mod n) foralln2l.

On the other hand,
mm)“ *(aw) = (u“ *a")*(a*fl)
= (#*a_l)*(a*.3)
=#*fl-
That is (p *fl)(n) E 0 (mod n) for all n 2 1. I

Remark: In particular, we may choose a to be Euler’s totient ¢ function or Jordan’s
totient Jk function since Zdln ¢(d) = n and Zdln Jk(d) = it". However a need not be a
multiplicative function. For example, in [30] Jarden used this result on the function defined
by a(1)=1, Zdlnaw) = —n for n > 1. Now a(2) = -3, and a(3) = —4, a(6) = 0,
showing that the conditions on a in Theorem 2.3.12 do not imply that a is multiplicative.

Now, we have the following characterizations for {pn },,21.

3O

Theorem 2.3.13. The following are equivalent:

(1') exp 25:12" el+zZ[[z]],

n21

(ii) imam/d E 0 (mod n) for all n 2 1,
dln

(iii) za(d)p,,/d E 0 (mod n) for all n 2 l, where a is an arithmetic function with
dln

a(l) = :l:1 and Zd|na(d) E 0 (mod n)for all n 2 2,
(iv) pmqs E pmqs-l (mod q‘)for all primes q andm,s 6 IP’.
Proof: (i) 4:) (ii) Note that

R(z) = exp —Z%-z" e 1+zZ[[z]]

n21

if and only if

exp Z-pf-z" el+zZ[[z}]-

n21

Now we can apply Theorem 2.3.1 to get the result.
(ii) 4: (iii) follows by writing p(n) = pn and applying Theorem 2.3.12.

(iv) => (ii) Ifq | n, we can write it = mqs where s = 0rd,,(n). Thus

Z#(d)pn/d = Z#(d)pn/d + Z#(d)pn/d

dln dln dln
(lid qld
= Z#(d)pmq5/d + Z.“(qd)pmq5‘1/d
dlm dlm
= ZINC” (qus/d - qus‘l/d)
dlm

s 0 (mod q‘) (by (iv))-

Since the above congruence is true for any prime q | n, we have established (ii).

(i) => (iv) Let

 

which is in l +qu[[z]] by Theorem 2.3.5. Hence, by Theorem 2.3.9

for all m,s e P.

On the other hand, by Proposition 2.2.2, we have
13(2) = qP(2) -qP(zq)-

That is
13mqs = 61(19qu - pmqs-n) E 0 (mod 61‘“)
for all m, s 6 IP’. Thus we have (iv). I
Remark: (i) a) (iv) has been proved by Beukers [5]. Stanley [62, p.72] also give a
proof of the equivalence of (i), (ii) and (iv) for 1 5 n 5 N, where N is a fixed positive
integer.
We have an analogous characterization using Type III. Before we can state the result,

we need some another definition and a couple of results.

Definition 2.3.14. Let (1, fl be arithmetic functions and q be a prime. We define a *q ,6 as

follows.
(a *q fl)(n) = ((1 *fl)(n) + (a *fi)(n/q) + - - - + (a *fl)(n/q‘)

where s = ordq (n).

Lemma 2.3.15. We have
a*(fi*qv)=(a*fl)*q7-

Proof: This follows directly from the definitions. I

We now have an analogue of Theorem 2.3. 12 for Type III.

Theorem 2.3.16. Let q be a prime and t 6 IP’. Let a, ,6 be arithmetic functions with a (1) =
:l:1 and Zdlnaul) E 0 (mod n)for all n 2 2. Then

([1 *q ,8)(n) _=. 0 (mod q’n) for alln 2 1

32

ifand only if
(a *q ,8)(n) E 0 (mod q’n) for all n 2 1.

Proof: ”=>” Since (a *u)(n) E 0 (mod n) and (p *q ,8)(n) :-=- 0 (mod q’n) for all n 2 1.
By Lemmas 2.3.ll(i) and 2.3.15, we have

(a*qfl)(n)=(a*u)*(p *qfl)(n)50 (mod q’n) foralln21.

”<=” We know

(a*u)-l(n)EO (mod n) foralln2l.

Again by Lemma 2.3.11(i) and (a *q p)(n) s 0 (mod q’n) for all n 2 1, we get
((a *u)-1 :1: (a Mm) (n) E 0 (mod q'n) for all n _>_ 1.

On the other hand,

(a*u)-l*(a *qfl) = (u‘1*a_l)*(a *qfl)
= (para-1)::(a *qfl)
= p *q ,6 (by Lemma 2.3.15).

That is (p *q ,B)(n) E 0 (mod q’n) for all n 2 1. I

Now we have the following characterization.
Theorem 2.3.17. Let q be a prime and t 6 IP’. The following are equivalent:

(i) exp flz"\ e 1+q'zzllzll.
n21 n /

(ii) Zp(d)pn/d E 0 (mod q'n)foralln 21,
dln
aid

(iii) (a *q p)(n) E 0 (mod q'n)for all n 2 1, where p(n) = pn and a is an arithmetic

function with a(1)= :l:1 and Zdlnaw) E 0 (mod n)for all n 2 2,

(iv) pm}: E pmém (mod cf) and pmqs E 0 (mod q’“) for all primes 2; other than q

andm,s E 11’.

33

Proof: (i) 4: (ii) Note that

exp 2 %z" e 1+q'zZ[[z]]-

n21

if and only if
exp (— Z éz" 6 1+q'zZ[[z]].

n21

Now we can apply Theorem 2.3.4 to get the result.
(ii) a» (iii) follows by noticing that
(n *q M) = Emma/d)

d In
aid

from the proof of Corollary 2.1.10. Now apply Theorem 2.3.16.
(iv) => (ii) Let 2; ba a prime other than q. If a; | n, we can write n = mq‘ where

s = ordq (n). Thus

prmm: 2 mam/1+ 2 ”(com

dln dln dln
qld (lid. ciid qid. éld
= ZMdqu-Vd + iguana-1M
dlm dlm
qld qld
= Z#(d) (Pmc‘iS/d _ qus-l/d)
dlm
aid

5 0 (mod q‘) (by (iv)).
For q, if q | n then we can write it = mq’ where s = ordq (n). Hence

2 ,u (d)pn/d = Z # (d)qu‘/d

dln dlm
qld

E 0 (mod qt“) (by (iv)).

Combining the above two congruences, we establish (ii).
(i) z: (iv) Since R(z) e 1+q'zZ[[z]] C 1+ zZ[[z]], Theorems 2.3.13 and 2.3.9 com-
bine to give pmqs E pmqs—l (mod .75) and pmqs E 0 (mod q’”) for all primes q and

m,selP’. I

34

2.4 Basic identities

In this section, we will show how equations (2.3) and (2.4) lead to generalizations for
various famous identities.

First, we have an identity which generalizes Newton’s power sum formula from his
book “Arithmetica Universalis” ([44, pp. 107—108] [46, pp. 361—362]) and which follows

easily from equation (2.3).

Theorem 2.4.1. We have
P(z)R(z) + zR’(z) = 0.

Equivalently,

Pn+alpn—1+---+an_1p1+nan=0 Vn2l. I

Newton did not actually prove his formula. There are many different proofs in the
literature (e. g. [4, 39, 69]) but this is arguably the shortest and easiest.
Second, we obtain three identities which generalizes Waring’s Formulas [67]. See also

[10, 11, 38].

Theorem 2.4.2. We have

k1+-°'+k k k
= —l k1+"'+k" n ( n)a la 2mak”, 2.19
p" k1+2k2;+nk,,=n( ) kl+"'+kn k1.-.-.kn 1 2 n ( )

 

 

 

2: __ k|+m+k k k
= _1 kl+ +kn 1 n ( ”)1: lhz...hk"’ 2_20
p" k1+2k2+...+nkn=n( ) k1+ ' ' ' +kn kl: - - - , kn l 2 n ( )
n k1+"'+kn k k k
= 2‘ _1k2+k4+ I 2... n. 2.21
p" ( ) kl+°"+kn( k1....,kn )e‘ 62 e" ( )

k1+2k2+m+nkn=n

Proof: To obtain the first expression for pn, use equation (2.4) to get

2%2" = — log(R(z))

n21

= —log (1 +(az-1zl +azzz+-~))

= 21(11):. (a121+a222 + . ~ )

i2l

 

i

35

The conclusion follows by comparing the coefficients of z" on both sides.
The other two identities are obtained similarly. I
Next, we can use equation (2.4) to obtain some identities which are inverses to our

generalizations of Waring’s Formulas.

Theorem 2.4.3. We have

(_1)k1+k2+"'+k,,

 

 

 

 

[<1 ’62 k
a": Z k 1k 1 kn 'plpzmpn", (2'22)
k1+2k2+~~+nkn=nl 1161.2 2k2.---n kn.
1 k k k
h,,= Z 1 plpz-np” (2.23)
'lkl...knllz '1’
k1+2k2+---+nk,,=nl lk1.2 Zkz. n k,,.
(_1)k2+k4+~- In [(2 k
e": Z k 1k 1 I... 1p1p2 "'pnn' (2'24)
k1+2k2+m+nkn=nl 1k1.2 2k2.---n kn.
Proof: By equation (2.4),
_ a ,.
2.... —exp( 2,2
n21 n21
l
= - a,» /,.
120 n21 n
_1 i r
= (.) (p1 1+‘p—222+ )
_ t! 1 2
120
The conclusion follows by comparing the coefficients of 2" on both sides.
Again, the other two identities are obtained similarly. I

We can simplify the notation in the previous two theorems by using partitions. A par-

tition of n, denoted A t—n, is a sequence of positive integers
A = (11912:... :11)

with 212 112 2 2 A, and 22,- = n. We also write 11 = (1k12k2-nnkn) where k,- is the
multiplicity ofi in )1.

The length of A is the number of parts of 1,
1(1) =k1 +k2+---+k,,.

36

The weight of A is

Ill=11+12+”-+AI=k1+2k2+---+nkn=n.

We also use the following notation:

z) = 1k1k112k2k2!-~nk"k,,!,
_ 1(2)!
_ k1!k2!---k,,!

 

#1
and

6}. =(_1)|l|—l(l).
For f = a,h,e or p and A l—n, we write

f1=f11f12-°°f1,=f1k‘f2k2-nff".

Thus, we can rewrite Theorems 2.4.2 and 2.4.3 in a manner that will be familiar to the

reader conversant with symmetric functions.

Theorem 2.4.4. We have

1(1)

n
Pa = Z(—1)lm_l—Mht,
“_n 1(1)

n
1).. = Zea—#161-
11—" 1(1)

n
p. = z(-1)'m—#1ar.
.11—n

Theorem 2.4.5. We have

an = Z(-1)M)2I1m.
11-11

h” = ZZIlpt,
11-11

-1
en = ZGAZ) p).-
111—1!

37

(2.25)

(2.26)

(2.27)

The next two theorems contain other relations between the coefficients of our power

series.
Theorem 2.4.6. We have
hn+a1hn_1+~-+an_1h1+a,, =0 Vn 21, (2.28)

and

h. = 2mm...
Al—n

Proof: Since R(z)H (z) = 1, we have the first identity.

From H(z) = R(z)", we get

—1
1+h1z+h2z2+m=(1+(a1zl+a2z2+~-))

= Z(-l)i(a1z'+azz2+-~)i

:20

Now compare the coefficients of 2" on both sides to get the second identity. I
Theorem 2.4.7. We have
(i) Pn = -(arhn—1+202hn—2 + - - - + (n -1)an—1h1+nan) W Z 1.
(ii) pn = hlan—l +2hza,,_2 +~~+ (n — l)h,,_1a1+nh,, Vn 21.
Proof: These follow directly by writing equation (2.3) as
P(z) = -zR’(z)H(z),

and

P(z) = zH’(z)R(z). I

Combining equation (2.25) with our previous results, we can get expressions for the

Type I and HI exponents in terms of the coefficients of R(z).

38

Theorem 2.4.8. We have

(d)
W2 # Z(_l) )1(,1)l_/(‘I:)%

dln .11—3

and if q is a prime then

#001101 #1
71-72 Z} 1) ’75)“-

W

Proof: By equation (2.8), we have

— " _nZfl(d)Pn/d

ndln

=-Z#<d>Z(-1>“”§ to) Mar <by(2.25>)

d
=2 "( —)dZ(—1)““I(v Mar

dln 11-;
Hence, we get the first identity. The second one is also obtained similarly using Corol-
lary 2.1.10. I

We conclude this section by giving one simple example for demonstration. More ex-

amples will be given in Section 2.6.

Example 2.4.9. Let R (z) = l — z. Then by equations (2.1)——(2.3) we have

H(z): 1+z+zz+m
E(z)=1+z

P(z)=z+z2+---

Hence, by Theorem 2.4.5 we have

0 = Z(—1)’“>z;1 forn > 1, (2.29)
,1

1: 22;], (2.30)
.11-n

39

and

0:24.312;1 forn >1.
ll-n

Identity (2.29) is Cayley’s Identity [9] and identity (2.30) is well-known as Cauchy’s Iden-
tity [49].

Moreover, by equation (2.26) we have

1: —1'<i>—‘—"— , f 0.
§( ) [(1)/11 orn>

This is equivalent to an identity in [10, 59]. I

2.5 Symmetric functions, linear recurrence relations and
matrices

In this section, we will discuss the case when R (z) is a polynomial.

2.5.1 Symmetric functions

When R(z) = l+a1z1 + - - -+a,z’ is a polynomial of degree r in C[z], there is a connection

with symmetric functions. First, define
r l
F(Z) = Z R 2 .

F(z) = z'+a12'-l+---+ar_1z+ar.

That is,

Assume that al, a2, - -- , a, e (C are the roots of F (z). We can write

r

F(z) = 1'[(z — an,
i=1
or equivalently
R(z) = ['10- aiz). (2.31)
i=1

4O

Now define the following symmetric functions:

The nth complete homogeneous symmetric function in the roots of F (z) is

h" I: E ail-nag".

ISiIS"'SinST

The nth elementary symmetric function in the roots of F (2) is

en := E ail main.

151.1 <"'<insr

The nth power sum symmetric function in the roots of F (2) is

r
pn := Zaf‘.
i=1

The corresponding generating functions are

   

k
H(z) := 212%”:
n20 i1:
k
E(Z) I: Zenzn=n(l+012)
n20 i1:
P(z) := anz" = zzah"
n21 n21 i=1
k
= 2201M)"
i= ln2l

 

Z “'2
I—aiz

Comparing these last three equations with (2.31), we see that H(z), E (z), P(z) and
R(z) satisfy the equations (2.1)-(2.3) and so all of the results from the previous sections
apply. Specializing Theorem 2.4.1 to this case where an = O for n > r, we immediately

have Newton’s original power sum formula.
Theorem 2.5.1. We have
pn +aan—l +---+an—1p1 +nan = 0 ifl S n s r.

41

and

Pn+01pn—1+---+arp,,_,=0 ifn>r.

In the same manner, Theorem 2.4.4 gives Waring’s formulas. For example,

Theorem 2.5.2. We have

n
Pi: = Z (“DMD—#101-
11-1. 1(11)

Mgr

Similarly, Theorem 2.4.6 specializes to the following theorem.

Theorem 2.5.3. We have
hn+a1hn_1+---+an_1h1+an=0 iflgnsr,

hn+alhn_]+°"+arhn—r=O ifn>r

and

1...: gem/1w.
.11-11

1151'

The next example will be used in Subsection 3.2.2.

Example 2.5.4. Fix a positive integer r 2 2 and a, b e C. Let

R(z)=1—az -bz’.

42

(2.32)

(2.33)

(2.34)

(2.35)

By Theorem 2.5.2 we have

p" = Z (_1)k1+--~+kr____’_l__(kl+.”+k’)(_a)k10k2...0kr-1(_b)kr

k1+2k2+---+rk,=n kl+--.+kr kl,..-,kr

k k,
= z (‘1)k1+kr—kl:k ( 1: )(_a)kl(_b)kr

kl +rk, =n

k k,
= Z n l + aklbkr
k1 + k, k,

k1+rk,=n

 

121
= 2 " (<n-rkr>+kr)a._,k,bk.
kr=0 (n _ rkr) + kr kr

b] n n—(r- l)k "_rk k
= 27:17 k a b -
k=0n (r )

In particular, we have

 

a" for l g n < r,
P n = n n-r '
a +na b forr 5n <2r.
2.5.2 Linear recurrence relations
Given a linear recurrence relation
An+alAn—l+”'+arAn—r=0 forn>r
with initial conditions A1, A2, - -- , A,, where a,- E (C, l 5 i 5 r. The characteristic polyno-

mial of the recurrence relation is
F(z) = z’ +alz'-1 + - --+ar.

and its roots a1, a2, - -- , a, e C are called the characteristic roots. Note that the solution of
the recurrence relation is determined uniquely by the initial conditions A1, A2, - .. , A,.
We wish to see what initial conditions must be imposed so that the solution to our recur—
rence will just be the nth power sum of the characteristic roots or] , a2, - .. , a,. Combining
Newton’s Formula (2.32) (for the recurrence relation) and Waring’s Formula (2.33) (for the

initial conditions), we get the desired constraints.

43

Theorem 2.5.5. The solution of the recurrence relation
An+a1An_1+---+anAn_r=O forn>r

with initial conditions
A 1 = —a1

a? — 2a2

.>
N
H

. I n
A, = Z(—1)"“———mar
h 1('1)

AISI'
is
An =or’l'+a’2'+----l—oz;I

where the ai are the characteristic roots of the recurrence relation. I

Similarly, combining equation (2.34) (for the recurrence relation) and equation (2.35)
(for the initial conditions), we get the initial conditions and recurrence relation for the nth

complete homogeneous symmetric function in the characteristic roots a1, a2, - -- , (1,.

Theorem 2.5.6. The solution of the recurrence relation
An+a1An_1+-~+anA,,_r=0 forn>r

with initial conditions

3?
11

A2 a]2 — a2

A. = Emma.
.11-n
AISI'

is

ISiIS'"SinSr

where the a; are the characteristic roots of the recurrence relation. I

Just as in Proposition 2.2.2, we will need to know how to handle addition and substrac-

tion of power sums of the characteristic roots. Here, we provide a more general result.

44

Theorem 2.5.7. Let {An },,21 be the solution of the recurrence relation
An+a1An_1+---+&,A,,_,=o forn > r (2.36)

with initial conditions A1, A2, - -- , 21,. Also, let {An},,31 be the solution of the recurrence

relation
An+&1/i,,_1+~-+a,/i,,_,=0 forn>s (2.37)
with initial conditions {11, A2, - -- , 145. Then the solution of the recurrence relation
An+a1An_1+---+a,+sA,,_(,+s) =0 forn > r+s (2.38)

where a,- = d,- + @4511 + - - - + &1&;_1 + (2;, with initial conditions
An=flAn+yAn for15n5r+sandfl,yeC,
is
AnzflAn+yAn forn2l.
Proof: The characteristic polynomial of the recurrence relation (2.38) is
(z' +1512"1 + -~+Zz,)(zs +6116" + - - - +&,).

Since 2' + 2312”] + ---+Zz, is the characteristic polynomial of (2.36) and z‘ +a1zs—1 +
---+&s is the characteristic polynomial of (2.37), we have {Anhzl and {Anhzl are the
solutions of the recurrence relation (2.38) with initial conditions A", 1 5 n S r +s and A",
l 5 n _<_ r + s respectively. Therefore, by the superposition principle, we obtain the desired
result. I

The next theorem will be used in proving some conjectures of Du in Subsection 3.2.2.

Theorem 2.5.8. Factor R (z) = l +alz + - - - +ar+sz’+5 as R(z) = R(z)fi(z) for polyno-

mials R(z), R(z) of degree r and s. Then the solution of the recurrence relation
An+a1An_1+---+a,+sA,,_(,+s) =0 forn > r+s

45

with initial conditions
Anzpn—pn for15n_<_r+s
is
An=j3,,—;3,, foralln21.

Proof: This follows directly from the previous theorem with A" = fin, A" = [3”, ,6 = l,

andy =—1. I

2.5.3 Matrices

We can also connect our work with the determinant and the trace of a matrix.

Let X be a matrix in er,(C). The characteristic polynomial of X is
F(z) = det(zl — X).
Paralleling the development in Subsection 2.5.1, define
, l
R(z) := 2 F (-) = det(I —zX).
Z

Let a1, a2, - -- , a, be the roots of F (2). It is a well-known result that
r
pn = 2a? = tr(X").
i=1

Therefore, we have

P(z) = Z pnz" = Ztr(X")z". (2.39)

n21 n21

Hence, we have the following theorem which connects the determinant and the trace of

a matrix.

Theorem 2.5.9. We have

t X ”
det(I —zX)"l = exp Eli—)2" . (2.40)
n
n21
Proof: This follows from equation (2.39) and (2.4). I

46

Corollary 2.5.10. Let 2 be a matrix in M,x,(<C) and 2 in M,,.,(<1:). We have

 

tr()2'") tr(52")zn

det(1 —z)?®x)“ =exp 2 (2.41)
n
n21
where (8) is the tensor product.
Proof: Let
X=r®2.
Then we have
tr(X”) =1r(x") u(x") for all n 2 1.
Hence, by Theorem 2.5.9 we are done. I

2.6 Various examples

In this section, we use our techniques to derive various congruences and identities, some of

which have appeared in the literature.

2.6.1 Congruences

The next example follows immediately from Theorem 2.3.4, Proposition 2.3.6, and Corol—

laries 2.3.7—2.3.8.

Example 2.6.1. We have the following results.

(i)
R(z) E 1 (mod 2)
if and only if
Enema 2 0 (mod 2n).
dln
2m

47

(ii)
R(z) E l+z (mod 2)

if and only if
1 (mod 2n) forn = 2k, k 2 o,
Z#(d)pn/d E .
(1|); 0 (mod 2n) otherwrse.
2+d
(iii)
R(z) E 1+z2 (mod 2)
if and only if
2 (mod 2n) forn = 2k, k 31,
Emma/d a _
4|" 0 (mod 2n) otherwrse.
2M
(i 0)
R(z) E 1+z+z2 (mod 2)
if and only if

—1 (mod2n) forn=2k, k20,
2#(d)Pn/d5 3 (mod2n) forn=3-2", 1:20.

dl -
2t; 0 (mod 2n) otherwrse.
I
A conjecture of P. Filipponi
The following two examples generalize the results in [1, 21].
In [21], P. Filipponi defined a sequence {Anln20 by
An - An_1— CAn_2 = 0 for n 2 2 (2.42)

with initial conditions A0 = 2 and A1 = I, where c 2 1 is a natural number. He showed

that if c = q where q is an odd prime then

Aqs E 1 (mod q") for all s e 11’.

48

Moreover, he conjectured that if c = q — l and q 2 5 is a prime then the above congruence
is also true.

Later, in [1], R. André-Jeannin proved the above conjecture and also generalized it as
follows.

If q 2 1 is a natural number and c E 0 (mod q) then
Aqs 21 (mod qSH) for all s e N.
And, if q 2 5 is a prime and c E —1 (mod q) then
11¢ 51 (mod qs+l) for all s e N.

In order to use our results and techniques to get congruences, we need to use A1 and
A2 as the initial conditions. Since from (2.42) we know A2 = 1 + 2c, we get the initial

conditions A1 = l and A2 = 1 + 2c. Now, by Theorem 2.5.5, we obtain
Anzpn foralln21

where p" is the n-th power sum in the characteristic roots of the recurrence relation (2.42).

Note also that (2.42) corresponds to
R(z) = 1— z —czz.

So the next theorem has André-Jeannin’s first congruence as the special case when t = m =

1.

Theorem 2.6.2. Let q,t e 11". IfR(z) E 1 — 2 (mod q’) then

qu‘ E 1 (mOd qH-s)

forallm ell”, s 6N.

Proof: Let R(z) = l — 2. Then from (2.3)

So, 13,, = l for all n 6 1?. We now apply Proposition 2.3.10 to get the conclusion. I
Similarly André-Jeannin’s second congruence follows from the next result when t = 1

because if q 2 5 is prime then q E i1 (mod 6).

Theorem 2.6.3. Let q,t e 11». IfR(z) _=_ 1 — z + z2 (mod q’) then

[2 (mod q‘“) ifq a- 0 (mod 6),
1 (mod q‘“) ifq E :l:l (mod 6),
—1 (mod qs“) ifq E 21:2 (mod 6),
.‘2 (mod q‘“) ifq a 3 (mod 6)

pqu<

 

for all s 6 11’.

Proof: Let R(z) = 1—z+zz. Since

 

~ l+z3
Rz =l—z+zz= .
() 1+2
We have, using (2.3),
P(z)—:—32—3+L—3(—z3+z6- )+(z—z2+---)
1+z3 1+z_ '

So,

'2 ianO (mod 6),
,_ 1 ifn E :tl (mod 6),
—1 ifn E :l:2 (mod 6),
_—2 ifn E 3 (mod 6).

Notice that iq‘ E iq (mod 6) for all q, s e 1?. Again, we apply Proposition 2.3.10 to get

 

the desired result. I

2.6.2 Identities

We can use our machinery to get interesting factorizations of exponentials.

Theorem 2.6.4. Let q > 1 be a positive integer:

o) 110 -z")"(")/" = exr)(-z).

n21

50

#(n)/n
) =exr)(z—z").

(ii) H (1+ z" + - - - +z‘q‘1)"

n21

_ n #(IO/n
(iii) H(— (1 z ——)q) =exp(—qz+z").

n21 l—zqn
Proof: (i) Let
R(z) = H(l -z")”(")/".

n21
By equation (2.7)
ifn = 1,
"fl—HZ = )2” (d )= {0 otherwise.
dln dln

Therefore, P(z) = 2. Hence, by equation (2.4), we have the desired result.

(ii) Let

~ u(n)/n
R(z) = H (1+z" + - - - +z‘q‘1’")

n21

Using the result in (i), we get

R(Z") _ eXp(-zq)
R(z) — exp(—z)

A 1_ n q (“M/’1
R(Z)=H((T::q—.).)

n21

 

R(z) =

= exp(z - 2").

(iii) Let

Again, using the result in (i), we obtain

R (2)4 _ CXP(-Z)q

_ _ q
R(z‘l) _ exp(—z‘l) _exp( qz+z ).

R(z) =

Theorem 2.6.5. Let q > 1 be a positive integer:

(i) H(l—z" WV" —exp( 1.22)

n21

 

_ n ¢(n)/n z 2"
(..)n(...n+...+.<qn) _..,( _ ).

n21

 

51

Proof: (i) Let
R(z) = H(l — z")¢(")/".

n21

By equation (2.7)

19.: Elf—L): Z¢(d>=n.

dm dm

Therefore,

P(z)=z+2z2+3z3+~-

Hence, by equation (2.4), we have

R(z)=exp(—z-22-z3—---) =exp(;Z—).

l — z
(i i) and (iii) follow by the same method as in Theorem 2.6.4. I

For the next result, we recall the definition of Liouville’s function and one of its prop-

erties from number theory (see, e. g. [2]).

Definition 2.6.6. Liouville ’5 function Mn) is defined by

ifn=1,

l
l n == I
( ) l(_1)a1+---+ak ifn_ — pllpgzn pzk

Proposition 2.6.7. We have

0 otherwise.

Zl(d)=[l ifnisasquare, I

Theorem 2.6.8. Let q > 1 be a positive integer:

n2

(i)1_[(1—z")’1(")/"=exp ‘25:? .

n21 n21
l(n)/n
<ii>H(1+z+ +z“’ "”) =exp 23,—": #2 .
n21 n21" n21
(1_ Zn)q .1(n)/n— qzn2 an2
<zii>r1(T_7—-z—+z—,—
n21 n21 n21

52

Proof: Let
R(z) = [In —z")“">/".

n21
By Equation (2.7)
Md) 1 if n is a square,
= d —— = ,1 d =
p" dz: d 2 ( ) [0 otherwise.
In dln
Therefore,

P(z) = z+z4+29+---
Hence, by equation (2.4), we have

2"2

R(z)=exp -2;2-

n21

(ii) and (iii) follow by the same method as in Theorem 2.6.4.

Theorem 2.6.9. Let q > 1 be a prime. We have

(i) H(1 -z")‘”‘"’/" = exp (21)

n21 s20 qS
qt"
n
-- _ n —¢(n)/n_ Z
«one z> _e... 2,...) .
n21 n21
qt"

 

2 s
_ z’" ‘1
(m) H(l—z") 100/" =exp 22’"qu .
n21 SZOMZI
qin qim
Proof: Let
R(Z) = H(1 -Z")""(")/"-
n21
qin
By equation (2.7)
(d
pn 2 ”Ed Ld ) = —Z/.l(d).
dln dln
q’rd arid

53

However,

Zu(d) = Z ,u(d) where s = ordq (n).

dln (11%.
(lid 0
That is,
1 if n: 5, s 20,
Z#(d)= 7
d 0 otherwrse.
In
qid
Therefore,

P(z)=-—z—zq—zq2+---

Hence, by equation (2.4), we have the desired result.

(ii) and (iii) follow by noting that

Z¢(d) = z¢(d) =:—s where s = ordq (n).

:12:
and
211W) = 2W) = 1 if a"; isa square, where s = ordq(n),
,, 0 otherwrse.
qid
N ow apply the same method as in (i). I

Note that (i) is so-called the Artin-Hasse exponential (see e. g [32, 50]).

Example 2.6.10. Let

R(Z) = (1 -Z)”.

where c e C. Then, by equation (2.3) we have
P(z) = cz+czz+m

Hence, by Theorem 2.4.5, we have

(- 1)" (Z) = Z(—c)’mz;l, (2.43)

M—n
(C+n—1)=ch(l)z;l, (244)
n 11-"

54

C ._..
( )2 z€)C[(l)Zl 1.
n Ill—n

Note that identity (2.44) is Sylvester’s Identity [63].

If c is a positive integer, then from (2.43) and (2.45) we get
0 = Z(—c)’(’1)z;1 for n > C,
11-71
and
0 = 261CI(A)Z;I forn > c.
.11—n
Example 2.6.11. Let
R(z) = 1-cz—cz2---- = (1—z)'1(1—(c+l)z),
where c e C. Then, by Proposition 2.2.2, we have

P(z) = Z<<c+1r —1)z".

n21

Hence, by Theorem 2.4.4, we get
n
(c+1)" — 1 = ch(”)—u).
11-" 1(1)

If c = 1, then the previous identity becomes

which is an identity in [10].

Example 2.6.12. Let q > 1 be a positive integer and
R(Z) = (1- Z)"/(1- 2").

By Proposition 2.2.2, we get

__ l0 ifq In,
It — .
q otherwrse.

55

(2.45)

Moreover, from

R(z) = (1—z)q(1 —z")_1 = (1 —z)4(1+zq+224+~-)

we have
0 ifqoddandnEO (modq): n21,
an: 2 ifqevenandnsO (modq), n21,
(—1)"’ (3,) otherwise, where n’ = n — q [n/q].
And from
H(z) = (1 - Z")(l - z)"’ = (1 -Z)"’ -zq(1- Z)”
we get

q + n -l (n -1)
h" = _ .
q —1 q —1
Hence, by Theorem 2.4.5, we obtain
0 ifqoddandnEO (mod q). n21,

(-q)“’)
Z 2 = 2 ifqevenandnEO (modq), n21.
A A (—1)"'(:,) otherwise, where n’ = n - q [n/ 611

q’“)_(q+n—l) (n—l)
Zr _ q-l q—l ’

 

and

0 ifqoddandnEO (mod q). n 21,
2617-: 2 ifq even andnEO (mod q). n 21,
1 A (3,) otherwise, where n’ = n — q [n/q]

where the summation is over all partitions ,1 of n into parts are not divisible by q.

(2.46)

(2.47)

(2.48)

Note that identity (2.47) is an identity in [41]. In particular, if q = 2 then we get Schur’s

Identity [56, 57]
21(1) 2

1.21

where the summation is over all partitions ,1 of n into odd parts.

56

Chapter 3

Applications

Now we apply our results in the previous chapter to several different problems.

3.1 Cycle indicators and combinatorial sequences

In this section,we will study the connection with cycle indicators and combinatorial se-

quences. We start with the definition of cycle indicators.

Definition 3.1.1. The cycle indicator Cn of the nth symmetric group is

1 I] h t2 k2 tn k"
C"(t"’2""’t”)= Z k1!k2!---kn!(T) (3) I ' '

k1+2k2+~~+nkn =n

 

We wish to express the relationships between R(z), H (z), E (z) and P (z) in terms of

C". Using our results in Section 2.4, we can get the following expressions.

Theorem 3.1.2. We have

an : Cn(—Pl:_P2a”' a—pn)9 (31)
hn = Cn(p1, P2, '° ° a Pit). (3-2)
e. = cn<p1,—p2,---,(—1)"“p.) (3.3)

57

and

ch(_p19 —p2a ' H 9 —pn)zn = exp _Z-p—n-zn ’ (34)
n20 n21 n
ZCn(p1,p2,-~,pn)z"=exp Zflz" . (3.5)
n20 n21 n
ZCn(p1.-p2,---,(-1)"‘1pn)z"=exP ZEN—15:13? . (3.6)
n20 n21

Proof: These identities are obtained directly from Theorem 2.4.3, equations (2.4), (2.1)
and (2.2). l
Note that equation (3.5) is a well-know expression in algebraic combinatorics (see e. g

[23, 27, 49, 62]).

There are many interesting specialization of Theorem 3.1.2 related to combinatorial
sequences and special polynomials. For instance, Gessel [23], Hsu and Shine [26, 27], and
Riordan [49] had some identities which can be expressed in terms of C”. Our machinery
can easily be applied to reprove these and get various others.

For example, we can rewrite equations (2.43)—(2.45) in Example 2.6.10 as

(_l)n (fl) = Cn (_C9 —C, 9 —C),

(c+n—l) = Cn(c,c,..o,c),
n

(2) = Cn (c, —c, - -- , (—1)"—1c)

where c e (C.

58

Similarly, by equations (2.46)—(2.48) in Example 2.6.12, we have

Cn(_q9°” 9—q909 _Hq9 _q9 99 q—9 “)
q 24
O ifqoddandnEO (modq) n21,
2 ifqevenandnEO (modq) n21,
(— l)" (3) otherwise, where n’ = n -q[n/q],
q+n—1 n—l
)= ,
q—l

Cn(q9”' 9q929q9n' 9q9 O q99

c.(q,--- . (—1>‘I‘2q.g. (—1>"q.--- .(—1)24‘2q. 1;, <—1)2"q.-~)
‘1 24
O ifqoddandnEO (modq) n21,
= 2 ifqevenandnEO (modq) n21,
CC) otherwise, where n’ = n —q[n/q].

The definitions of the combinatorial sequences and their generating functions in the

following examples can be found in [12, 49, 61, 62].

Theorem 3.1.3 ([26, 27]). Let Fn and L, be the Fibonacci and Lucas numbers, respec-
tively. We have
Fn = Cn(L19L29°" 9Ln)'

Proof: The generating function for the Fibonacci numbers Fn is

anz"= 1———zl’—z2

n20

and the generating function of the Lucas numbers Ln is

z+222
E ann— — 2.

l—z- z
n21

Now, let H(z) = (l - z - z2)_1 = 2,20 Fnz”. Then, by equation (2.3), we have

z+222
P -— L
(Z)— l—Z— z2 =2 "Zn.

Hence, by equation (3.2), we obtain the desired result. I
Note that in the next few examples, we will use exponential generating functions instead

of ordinary generating functions. Hence, factorial factors will appear in our identities.

59

Theorem 3.1.4 ( [26, 27]). Let BEn be the Bell numbers. We have

1 1 l
BEn=n!C,, (0—!,fi,°”,"(n—:l—)!).

Proof: Recall that the exponential generating function of the Bell numbers is

 

BE, n
2 n, 2' =exr)(exv(z)-l).

n20
Now, let H (z) = exp (exp(z) — 1) 6 1+ zC[[z]]. Hence, by equation (2.3), we have

2 23

Z
P(Z)=ZCXP(z)=z+fi+§E+-~

The result now follows from equation (3.2). I

Theorem 3.1.5. Let En and Tn be the Euler and tangent numbers, respectively. We have

T0 T1 T2 Tn—l )

En=n!cn (E’TT’E’M’W

Proof: Note that the exponential generating functions of the Euler and tangent numbers

are

E" n T" n
ZFZ =sec(z) and Z—'z =tan(z).

n20 ' n20 n.

H(z) = sec(z) e 1+z<C[[z]].
Then, by equation (2.3), we have
P(z) = ztan(z).

Hence, by Theorem 3.1.2, we get the desired result. I

Remark: There are alternate Euler numbers and tangent numbers defined by

E" 2
2—72" = _6329)? = sech(z),
"20 n. exp( z)+
and
T; n exp(2z) — 1
Z n! Z exp(2z) + 1 an (Z)

60

In this case, we have

 

apnnq(—% -E _E Sflfii).

oz’u’2!””m—m

Theorem 3.1.6 ([23]). Let Dn be the derangement numbers. We have
Dn =n!C,,(O,l,--- ,1).

Proof: The exponential generating function of theyderangement number is

 

2:12,. _ eXp(-2)
m ‘ ha"
n20

The result now follows by using the usual techniques.

Theorem 3.1.7. Let B" be the Bernoulli numbers. We have

 

B —B —B -B
Bn=n!Cn(—l 2—'—3' n)

u’m’m’m’m
and
_ Bl Bz n+IB"
Bn_n!cn(-fi9—-2_!9"'9(_l) 3;!— '

Proof: Note that the exponential generating function of the Bernoulli numbers is

B" n _ 2
Let
H(z) = exp(:) —1 e 1+zC[[z]].

Then, by equation (2.3), we have

zexp(z) _ z

 

 

Pz =1————_1-z——-——-=1—z—Hz.
() exp(z)-l exp(z)—1 ()
Hence, by equation (3.2)
—B1—1 —82 —B3 -B,,
B"""!C”( 1! ’21 ’ 3! n!)

61

or equivalently,

 

 

Br -32 -Bn
_ 1 _ _
m‘”“(u’m’ ’m)
since B1 = :21 and —B1—1= ‘71 = B].
Moreover, if we write
zexp(z) —z
Pz=l————= — =1—H—z,
( ) exp(z) — 1 exp(-z) — l ( )
Then we get the second identity. I

3.1.1 The Lagrange Inversion Theorem

In order to obtain more interesting identities, we utilize the remarkable Lagrange Inversion
Theorem to calculate the coefficients in a formal power series.
We recall the Lagrange Inversion Theorem and one of its corollaries (see e.g. [12, 24,

62, 68]).
Lagrange Inversion Theorem. Let G (2') e [[2]] with G(O) 9e 0, and let F (z) be defined by
F(z) = zG(F(z)).

Then
n[z"]F(Z)" = klz”"‘lG(Z)"

where k, n e Z.

Note that if k < 0 then F (2)" is the Laurent series of the form

Zanz".
Corollary 3.1.8. Let L(z), G(z) e C[[z]] with G(O) =,£ 0, and let F (2) be defined by
F(Z) = zG(F(Z))-

Then we have

n1z"1L(F(z))=tz"“1L’(z)G(z)"

62

and

nlz"llog(F -(—z)) = [2"]G(Z)". I

Theorem 3.1.9. We have

—(n—l)n—1=H!Cn(—i'a_i ...,_£_),

1. n!
l 4 n"
"—1— ——..I _—
(n+l) —n!cn(l!92!9 ,7”),
1 4 n
n—l____ __ __ _ n— 1
0—") “"!C"(1!’ 2!’ ’( ) n1).

Proof: Consider the functional equation

F (z) = zexp(F(z)).

By using the Lagrange Inversion Theorem, we have

 

kn n-—k 1
my: 201 n —k)!zn

where k e Z.

Now, let R(z) = exp(—F(z)) e 1+z<C[[z]]. Then we have

_ _ n—l
R(z)=exp(—F(z))=zF(z)—1=2 (n 1) z",

 

"20 n!
_ n+1 n—l

H(z) = exp(F(z)) = z lF(Z) = Z (——,l—z".

n.

n20
l— n—l

E(z) = exp (—F(-z)) = -zl'7(-z)_l = ZLfl—z",

"20 n!
P(z)— — zF’ (z)— — Z—z".

n21
The result now follows by applying Theorem 3.1.2. I

Remark: The number (n + l)"'1 is the number of labelled trees on n + 1 vertices [49,

62].

63

Theorem 3.1.10. Let

 

C”: 1 (2n)
n+1 n
be the nth Catalan number. We have
1 3 2n—1
_.,,_,-.,,(_(0),-(),...,_(n_1»,
1 3 2n—l
C»-C~((o)’(1)~~(._1)):
1 3 2n—1
_ n—l = _ __ n—l .
( 1) Cit—1 Cn((0)9 (1)9 9( 1) ("_l))

Proof: Note that the generating function of the Catalan numbers
C(z) := Co+ C121+sz2 + - ~-

satisfies

C(z) = 1 +zC(z)2. (3.7)

Now, let H (z) = C (2) e l +z<C[[z]]. By equation (3.7), we have

1: C(z)"l +zC(z).

 

Hence,
R(z) = C(z)" =1—zC(z).
E(z) = R(—z) = 1+zC(—z),
and
an = —C,,._1 forn 21,
en = (—1)"—‘C,,_, forn 21.
Also,
_ 2’12
P(Z) ‘ 2 cm
_ C(z)2 +z2C(z)C’(z)
_ C(z)
= zC(z)+222C'(z).

64

So,

pn = Cn—1+2(n — l)Cn—l
l 2 — 2
= (2n —1)-( " )
n n — 1
_ (2n — l
_ n - l '
Therefore, by Theorem 3.1.2, we obtain the desired result. I

We conclude this section by giving one more application.

Theorem 3.1.11. Let

 

Mon=.i.,z(":“‘)("::i:")

(_l,_,.,,_,;©(..)),

M0,, = “(13,... z(?)(n-i—i))
0,,(_,,._,;©(.7»

be the Motzkin numbers. We have

—M0n—2 = Cr:

(-1)"-1M0n-2 = C3:
forn 2 2.
Proof: Note that the generating function of the Motzkin numbers
M0(z) := M00+M01z+M0222+m

satisfies

M0(z) = 1 +zM0(z)+zzM0(z)2. (3.8)

Let 1176(2) = zM 0(z). Then equation (3.8) becomes

1176a) =z(1+17o(z)+1\71‘o(z)2).

65

So, to use the Lagrange Inversion Theorem, we will need the expansion

(1+z + 2:2)" = z (1:) (z +22)"_i

i20

= (’.1)z""'(l+z)"“i
.20 z

a.(?)z"-iz(";")zj

1'20

n n—i _- -
= (i)( ' )2. 1+1,
i,j>o 1

Now, let H(z) = M0(z) = [111%(2) e 1+z<C[[z]]. Then

R(z) = M0(z)_1= zn’r‘oorl.

 

and
an = [z"]M0(z)'l
= [2"‘111171?5(Z)’I
= gal—”2’10 + z + 22)"_1 (by Lagrange Inversion)
—1 n -1 n — l —i .
=n-llZ( i )( i—l ) (bytheexpansron)
= -M0n—2
forn 2 2.

Also, rewrite equation (2.3) as

10g(H(z)) = Z 5:152”,
n21

we have
pn = 1112"] 10g (H 8))
= n[z"]log (MTG)
= [2"](1 +2 +22)" (by Corollary 3.1.8)

= E (n) (n — l) (by the expansion).
_ l i
1

Again, we apply Theorem 3.1.2 to establish the formulas.

 

66

3.2 Dynamical Systems

There is a strong connection between number theory and dynamical systems. In particular,
the number of periodic points in a dynamical system satisfies a congruence relation, (3.12)
below. Various authors have applied (3.12) to get congruences for dynamical systems [6,
15, 16, 17, 22, 34, 35, 36,47].

Du [15, 16, 17] has obtained several interesting results about counting the periodic
points using linear recurrence relations. Moreover, he made extensive use of the computer
to formulate conjectures about congruences for these sequences which he could not prove
using dynamical-systems techniques. He also asked if number-theoretic proofs were pos-
sible for his theorems. At the first glance, there is no obvious way to obtain a relationship
between the initial conditions and the recurrence relations in Du’s theorems and conjec-

tures. However, we are able to prove Du’s conjectures and theorems using our techniques.

3.2.1 Introduction

In this subsection,we recall some basic definitions and results from dynamical systems (see
e.g. [16, 47]).
For a map T : X —> X on a set X, we denote the nth iterate of T by T". We call a point

x e X a periodic point of period n under T if
T" (x) = x,
for some n 2 1. Call x a periodic point of least period n under T if
T"(x) =x and Tk(x) 75x for l 5 k < n.
We denote the number of points of period n under T by
Per,,(T) = #{x e X l T"(x) = x},
and the number of points of least period n under T by

LPern =#{x e x | T"(x) =x and Tk(x) ¢x for 1 5 k < n}.

67

We assume Pern (T) is finite for all n 2 1.
It is easy to see that x is a periodic point of n if and only if x is a periodic point of least

period d for some d | n. Hence we have

Per” = ZLPerd. (3.9)
d In

Furthermore, if x is a periodic point of least period n under T, then the points x, T(x),

---, T"-1 (x) are all distinct and are all periodic points of least period n. We call the set
{7%) l k 2 01 = 1x. T(x), , T"“‘(x)}
the (periodic) orbit of x under T. Then the number of orbits of length n under T is
Orbn (T) = i—LPerAT). (3.10)
Hence, by (3.9) and (3.10), we have

Per" = ZdOrbd Vn 2 l.
dln

Then, by the Mobius Inversion Theorem, we get

1
n dln

Since Orbn is a nonnegative integer, we get the following congruence

Zy(d)Pern/d E 0 (mod n) Vn 2 1. (3.12)
dln

3.2.2 Du’s Theorems and Conjectures

In this section, we will show that the initial conditions and recurrence relations in Du’s
conjectures and theorems are connected with the power sums in the characteristic roots of
the recurrence relations. Hence, we are able to prove these congruences by using Theo-
rem 2.3.1. First, we give some examples which algebraically prove theorems which Du
demonstrated using the theory of dynamical systems. We then use the same techniques to
prove Du’s conjectures in [16, 17].

The next two examples deal with linear recurrence relations of order 2 and order 3.

68

Example 3.2.1. Let a1 and a2 be integers and {An} satisfy the recurrence relation

with initial conditions

A1=—a1 and A2=ai7'—2a2.

So, by Theorem 2.5.5, An is the nth power sum in the roots of F (z) = 22 +alz +02. Hence,

by Theorem 2.3. 1, we have

Zach/1,”), 5 0 (mod n) for all n 21. .
dln
Remark: When a1 = —l,a2 = —1, we get

A1 =1,A2=3,A3=4,A4=7,A5= 11,-~-
so that An = L", the nth Lucas number (see e.g [19, 65]).
Example 3.2.2. Let a1, a2 and a3 be integers and {An} satisfy the recurrence relation
An+a1An_1+a2An_2+a3An-3 =0 forn > 3
with initial conditions
A; = —a1, A2 = a? —2a2 and A3 = —a13+3a1a2 — 3a3.

So, by Theorem 2.5.5, An is the nth power sum of the roots of F (2) = 23 +a1z2 +azz +a3.
Hence, by Theorem 2.3.1, we have
Zp(d)A,,/d E 0 (mod n) for all n 21. I
dln
Remark: This example generalizes the result in [16, Theorem 4], and also gives the explicit

initial conditions that Du was asking for.

69

Du’s Theorems

We now give algebraic proofs of Du’s theorems.

Theorem 3.2.3 ([15, Theorem 3]). Fix r 2 1 and let
An—An_1—A,,_2—---—A,,_,=0 forn>r

with initial conditions
An=2”—l, forl 5n 5r.
Then

Z#(d)An/d E 0 (mod n) foralln 2 l.
dln

Proof: We will show that An is the nth power sum in the roots of the characteristic
polynomial

F(Z)=Zr—Zr_l—Zr—2—'H—l.

To prove this, let

R(z): l—z—zz-m—z'

= (1 —2z+z'+‘)/(1 —z).

Now, let R(z) = 1 — 22 + z’“ and R(z) = 1 - 2. It follows easily from Example 2.5.4 that

~

pn=2" and 13,,=1 forlsnsr.

Thus, by Proposition 2.2.2, we get p" = 2" — l for l 5 n S r. Now Theorem 2.5.5 shows
that pn and An satisfy the same initial conditions and recurrence relation. Hence they must

be equal for all n 2 1. Therefore, by Theorem 2.3.1, we have

Zy(d)An/d 20 (mod n) for all n 21. I
dln

7O

Theorem 3.2.4 ([15, Theorem 4], [16, Theorem 3]). Fix integer r 2 1 and let

2r
A, — A,,_1—Z(—1)‘A,,_,- =0 forn > 2r
i=2
with initial conditions
AZn—l = l f0r1£n5n
A2,, = 2"+1—1f0r15n 5r.

Then

zp(d)An/d E 0 (mod n) foralln 2 l.
dln

Proof: We will show that An is the nth power sum in the roots of the characteristic

polynomial
2r
F(Z) = ZZr _ Z2r—l _ Z(_l)iZZr—i.
i=2
To show this, let
2r
R(z)=1- z — Z(—1)"z"
i=2

= (1 —222-22'+')/(1+z).

Now, let R(z) = 1 — 2z2 — 22’“ and R(z) = l + z. By a method similar to Example 2.5.4,

we have
fiZn—l = 0 for 1 S n S r,
[52,, = 2""?1 for 1 S n S r.

Also, fin = (—1)", for all n 2 1. Hence, by Proposition 2.2.2, we get

p2,,_1 = 1 forlSngr,
Pzn = 2”+1—1 forlsngr.

Arguing as in the previous proof, p” = An for all n 2 1. Therefore, by Theorem 2.3.1, we

have

Zp(d)A,,/d E 0 (mod n) for all n 21. I
dln
Remark: In [15], Du used a more complicated recurrence relation for the sequence in

this theorem. Later, he discovered a simpler recurrence relation in [16]. Here, we have

simplified the recurrence relation even further.

71

Theorem 3.2.5 ([16, Theorem 2]). Fix r 2 2 and let
An—3An_1+An_2+---+An_,=0 forn>r

with initial conditions
An=2n+l—l, forl 3n 5r.
Then

Z#(d)An/d 50 (mod n) foralln 21.
dln

Proof: We will show that An is the nth power sum in the roots of the characteristic
polynomial

F(z)=z'—3z"'l+z"2+---+1.

To show this, let

R(z) = l —3z+z2+---+z'
= (1 —4z+4z2 — zr+1)/(1- 2).
Now, let R(z) = 1 — 42 +422 — 2'“ and R(z) = l — 2. From Theorem 2.5.2 it follows that
for n 5 r then nth power sum in the roots of R(z) are the same as that sum for l — 42 +422.

So

p',,=2"+1 and 13,,=1 forlsnsr.

Thus, by Proposition 2.2.2, we get pn = 2"+1 — l for l 5 n 5 r. The proof is finished in

the usual manner. I

Theorem 3.2.6 ([17, Theorem 5]). Fix r 2 2 and let

r 2r—l
A" — 2(21' — 1)A,,_,- — 2 (4r - 2i — 1)A,,_. = 0 forn 2 2r
i=1 i=r+l
with initial conditions
A __ 3"-2 forlsnsr.
n _ 3"—4n-3"""1—2 forr <n < Zr.

72

Then

Z#(d)An/d E 0 (mod n) for alln 2 1.
dln

Proof: The reader will be familiar with the method by now, so we will only provide the

main steps. Let

r 2r—l
R(z)=1— Z(2i — l)z‘ — Z (4r—2i — 1)zi
i=1 i=r+l

= (1—3Z+4Zr+l_zzr _ZZr+I)/(l -Z)2~

Now, let B(z) = 1 - 32 +42“r1 - 22' - 22’+1 and R(z) = (l — z)2. From Theorem 2.5.2,
the power sums for R(z) and 1 — 3z + 4z'+1 are the same for n < 2r. So by Example 2.5.4

~ _ 3" forlsnSr,
’9’” 3"—4n-3""”1 forr<n<2r.

Also, [3,, = 2, for all n 2 1. Thus, by Proposition 2.2.2, we get

_ 3"—2 forlgnsr,
p’" 3"—4n-3"_'—1—2 forr<n<2r.
Since Anzpn foralln21,we are done. I

Du’s Conjectures

Using the same methods, we can prove Du’s conjectures in [16, 17] which he could not
obtain using dynamical-systems techniques.

The next theorem resolves the conjecture in [16].

Theorem 3.2.7. Fix r 2 2 and let
An—3A,,_1+An_2+~-+A,,_2,+1 =0 forn 2 2r

with initial conditions

A _ 1 f0r15n<r,
n_ 2nc2""+l forr5n<2r.

Then

Z#(d)An/d E 0 (mod n) for all n 2 l.
dln

73

Proof: Notice that the characteristic polynomial of the recurrence relation is

Z2r_l_3Z2r—2+er—3+”°+l

____ (Zr _ zzr-l _ ”(Zr—1 _ zr—Z _ . . . _1).
We will show that A" is difference of the nth power sums in the roots of
zr—22”l —l and z"1 -z'_2----— 1.

So, let

R(z)=1-2z—z'

and

R(z)=1—z—---—z’_1

= (1 —2z+z')/(l —z).

It follows easily from Example 2.5.4 and Proposition 2.2.2 that

- _ 2" forlgn<r,
Pn— 2"+n-2"" forr 5n <2r.
and
. _’,2"—1 for15n<r,
Pn— 2"-no2""—1 forr5n<2r.

Thus, we have
1 for 1 5 n < r,

Pn-Pn= l2n-2"“’+l forr _<_n <2r.

Now applying Theorem 2.5.8 we obtain An = [5,, — ,3, for all n 2 1. Since by Theorem 2.3.1

both 13,, and 13,, satisfy the desired congruence, so does their difference. I

The next theorem proves the conjecture in [17]

Theorem 3.2.8. Fix r 2 2 and let

r 2r-l
A, — 2(21' — 1)A,,_,- — 2 (4r -2i—1)A,,_i = 0 forn _>_ 2r
i=1 i==r+1

74

with initial conditions

3" for15n<r,
An: 3'—2r forn=r,
3"—4n-3"""‘1 forr < n < 2r.

Then

Zp(d)An/d a 0 (mod n) for all n 2 1.
dln

Proof: Notice that the characteristic polynomial of the recurrence relation is

,. 2r—1
ZZr—I _ Z<2i _ 1)Z2r-l-i _ Z (4,, _ 2i—1)22r—1_i
i=1 i=r+l
= (z' —22'_1—22'—2 —~-—22— 1)(z"l +z"2+---+1).

We will show that A, is difference of the powers sum of the roots of

zr_22r—l —22r-2—-“—22-1
and
z"1 +z"2+---+ 1.
So, let
R(z):1—2z—2z2—---—2z”'—z'
= (1—3z+z'+z’+1)/(1—z)
and

R(z): 1+z+z2+~-+z'—1

=(1—z')/(1-z).

Using the usual techniques we get

3"—l for15n<r,
fin: 3"—r-1 forn=r,
3"—4n-3"—'_‘—1 forr <n <2r.

75

and
. [r—l forrln,

p" — —1 otherwise.
Thus, we get
3" for 1 S n < r,
fin_fin= 3n—2r forn=r,
3" —4n-3"""‘l forr < n < 2r.
Now we are done as in the proof of the previous theorem. I

Actually, Du in [16, 17] used dynamical systems to prove that the sequences {An},,21

in Theorems 3.2.7 and 3.2.8 satisfy the following congruences.

1 mod 2n forn=2", k 20,
Z #(d)A../d -=- ( ) , (3.13)
d1). 0 (mod 2n) otherwrse.
d: odd

Recently, Du, Huang and Li [18] used a different approach to prove the congruences
Zp(d)A,,/d a 0 (mod n) for all n 21.
d In

from (3.13).

3.3 Universal k-rings, ghost rings, necklace rings, and Witt
vectors

The main purpose of this section is to give explicit formulas for universal polynomials of
universal k-rings and to give a connection of our viewpoint with ghost rings, necklace rings,
and Witt vectors.

Universal l-rings [14, 25, 31] are an important tool from commutative algebra, and have
numerous applications to several areas of mathematics [3, 14, 25, 31, 40, 52]. In the litera-
ture the construction of universal A-rings is by universal polynomials. However, to the best
of our knowledge, no explicit formulas for universal polynomials have been established in
the literature. Since universal polynomials are the building blocks of universal k-rings, it

would be helpful to have such formulas for them. We will derive such expressions shortly.

76

Since we have already been working over (C, we will continue to do so in this section.
However, these results remain true over suitable commutative rings.
We first consider a ring structure on zC[[z]]. We use the usual addition operation but

Hadamard product 0 for the multiplication. This ring is called the ghost ring Gh(<C)

 

[33, 40, 52].
We define the ghost map
gh . l+z<C[[z]] —> zC[[zll
by
gh(R(z)) = #2:; = no

We wish to define the ring structure on 1+ zC[[zl] for which the ghost map becomes
an isomorphism of rings. By Proposition 2.2.2, we must define addition in 1+ zC[[zD to
be the usual multiplication of formal power series. Now, we define the multiplication ... on
1 + zC[[ZII by

R(z) =1 R(z) = gh“ (gh (R(z)) ogh (1%)) .

where

 

2 P n n
gh-1(P(Z))=Cxp(_V/0 ix)dx) =exp _Z%z

n21

This ring structure on 1 + zC[[z]] is called the universal A-ring.
Suppose R(z) = 1+Ei1z +5222 + and R(z) = l+&1z +65222 + Let R(z) =

[1(2) :1: R(z) = 1+ alz + azz2 + - - -. Then there exist polynomials

Sn[xl9°” ,xn;}’l,"° aYnI

such that

an = Silk-319°” 9&n;&19'” 92in]-

These polynomials, Sn, are called the universal polynomials of the universal A-ring. No
explicit formulas for universal polynomials has been given in the literature. However, we

can get an (and thus S.) by applying our results in Section 2.4.

77

Theorem 3.3.1. We have

(‘1)10’) n 1(1) " ~ ((1') " ~ kg
an= Z Zv H((AZHX-l) mfllal)(z(-l) mil/11%)) -

u=(1*12k2...nkn)(_,, i=1 AIH

 

Proof: By equation (2.27),

a. = 2 (-1)"”’z.7‘p.

v=(1*12’<2--.nkn)1—u

= Z (—1)"”’z:‘m..

v=(l"12"2---n"n)l-n
Now applying equation (2.25) finishes the proof. I

The first few examples are

(12 = 5%512 “l-Etzc‘iiZ — 2&2512
a3 = —5?&3 — 5351? + 3&152a3 + 35351152 - 515251632 — 35353.
Since, R(z) e l + zC[[z]] can write as
R(z) = [In —z")M".
n21
Hence, we can define a ring structure on the necklace vector (M 1, M2, - - -) 6 CP [14, 40].
Addition is the usual componentwise addition and the multiplication is defined by
Mn = z (iaj)MiMj
[1.jl=n
which we already used in Proposition 2.2.3. This ring is called the necklace ring N r(<C)
[14,40].
Similarly, write R(z) 6 1+ zC[[z]] as
R(z) = 1‘10 — an").
n21
We can define a ring structure on the Witt vector (Q1, Q2, - . -) 6 (CI? [33, 40]. However, we

are unable to give explicit definitions of addition and multiplication for Witt vectors.

78

Chapter 4

Open problems

In this thesis, we obtained our results from generalizations of the elementary, complete
homogeneous, and power sum symmetric functions. However, there are still serval im-
portant bases for the algebra of symmetric functions, for example Schur symmetric func-
tions [37, 55], which we have not yet considered. We predict that by similarly generalizing
Schur symmetric functions and other bases, we will obtain more results in the future. We
also intend to investigate multivariate analogues and q-analogues of our results

In the following, we will outline some questions which arise naturally in our work.

In Theorem 2.1.11 we showed

p. = Zde/d, Vn _>_ 1.
d In

But now we can not apply the Mobius Inversion Theorem directly to write down Q, in
terms of p". Because of this, in Section 3.3 the ring structure of Witt vectors (Q1, Q2, - - -)
is still a mystery. It would be wonderful to find an explicit formula to help in understanding

this structure.
Question 1. What is an explicit formula for Q” in terms of p"?

In Theorem 2.3.1, we proved

Xenon/.1 a 0 (mod n).
dln

79

The number thIn ,u (d)p,,/d counts objects arising in combinatorics, dynamical systems
and finite fields. Hence, we would like to find condition(s) on p,, such that
1
- Z/1(d)Pn/d E N. (4-1)
n
d In

In Theorems 2.3.1 and 2.3.13 we gave conditions which guarantee 91-2“ )1 (d) pn /d e Z.

Question 2. What condition(s) would characterize those sequences {pn},,21 satisfying

(4.1)?

Similarly, in Theorem 2.3.4, we have

zp(d)p,,/d E 0 (mod q'n).
dln
4101

However, we do not know of a combinatorial interpretation for the numbers

1
— Z l1 (d)Pn/d
qt" dln
4101

except in the special case when R(z) = 1 - q‘z this sum counts the number of irreducible

polynomials of degree n over GF (q‘) with given nonzero trace [54].

Question 3. Do the numbers ‘71; 2(1)le ,u (d) pn/d count anything?
(I
We also have the analogue of our second question in this context.

Question 4. What condition(s) would characterize those sequences { pn },,21 satisfying

1
7'; Zfl(d)Pn/d E N?
q dln
4101

In Section 2.3, we derived various congruences involving the power sum symmetric
functions. It seems that this method might work for other symmetric functions. The Witt

symmetric functions (see [64]) are defined by

1 d
ln = ;Z#(d)p3/ -
dln

80

 

Rota and Sagan [53] use group actions to get congruences for some special Witt symmetric

functions.

Question 5. What identities and congruences for Witt symmetric functions can be obtained

using our methods?

In Section 3.1, we used cycle indicators to relate combinatorial sequences. We can also
apply these techniques to special functions such as the Hermite and Gegenbauer Polyno-

mials [12]. But that work will appear elsewhere.

81

BIBLIOGRAPHY

[1] Richard André-Jeannin, On a conjecture of Piero Filipponi, Fibonacci Quart, 32
(1994), no. 1, 11-14.

[2] Tom M. Apostol, Introduction to analytic number theory, Springer-Verlag, New York,
1976.

[3] M. F. Atiyah and D. 0. Tall, Group representations, k-rings and the J-
homomorphism, Topology, 8 (1969), 253—297.

[4] Elwyn R. Berlekamp, Algebraic coding theory, McGraw-Hill Book Co., New York,
1968.

[5] F. Beukers, Some congruences for the Apéry numbers, J. Number Theory, 21 (1985),
no.2, 141—155.

[6] Jozef Bobok and Lfibomr’r Snoha, Periodic points and little Fermat theorem, Nieuw
Arch. Wisk. (4), 10 (1992), no.1-2, 33—35.

[7] Leonard Carlitz, Note on a paper of Dieudonné, Proc. Amer. Math. Soc, 9 (1958),
32—33.

[8] Leonard Carlitz, A note on power series with integral coefficients, Boll. Un. Mat. Ital.
(3), 19 (1964), 1-3.

[9] Arthur Cayley, Note on the theory of Determinants, The London, Edinburgh and
Dublin Philosophical Magazine and Journal of Science, 4th series, 21 (1861), 180—
185.

[10] William Y. C. Chen, Ko-Wei Lih, and Yeong Nan Yeh, Cyclic tableaux and symmetric
functions, Studies in Applied Mathematics, 94 (1995), no. 3, 327—339.

[1 1] William Y. C. Chen and James D. Louck, The combinatorial power of the companion
matrix, Linear Algebra and its Applications, 232 (1996), 261—278.

[12] Louis Comtet, Advanced combinatorics, D. Reidel Publishing Co., Dordrecht, en-
larged edition, 1974.

[13] A. Dold, Fixed point indices of iterated maps, Inventiones Mathematicae, 74 (1983),
no. 3, 419—435.

82

[14] Andreas W. M. Dress and Christian Siebeneicher, The Burnside ring of the infinite
cyclic group and its relations to the necklace algebra, A-rings, and the universal ring
of Witt vectors. Adv. Math, 8 (1989), no.1, 1—41.

[15] Bau-Sen Du, A simple method which generates infinitely many congruence identities,
Fibonacci Quart, 27 (1989), no.2, 116—124.

[16] Bau-Sen Du, Congruence identities arising from dynamical systems, Appl. Math.
Lett., 12 (1999), no.5, 115-119.

[17] Bau-Sen Du, Obtaining new dividing formulas n | Q(n) from the known ones, Fi-
bonacci Quart, 38 (2000), no.3, 217—222.

[18] Bau-Sen Du, Sen-Shan Huang, and Ming-Chia Li, Generalized Fermat, double Fer-
mat and Newton sequences, Journal of Number Theory, 98 (2003), no.1, 172-183.

[19] Richard A. Dunlap, The golden ratio and Fibonacci numbers, World Scientific Pub-
lishing Co. Inc., River Edge, NJ, 1997.

[20] G. Everest, A. J. van der Poorten, Y. Puri, and T. Ward, Integer sequences and periodic
points, J. Integer Seq., 5 (2002), no. 2, Article 02.2.3, 10 pp. (electronic).

[21] Piero Filipponi, A note on a class of Lucas sequences, Fibonacci Quart, 29 (1991),
no. 3, 256—263.

[22] Michael Frame, Brenda Johnson, and Jim Sauerberg, Fixed points and Fermat: a
dynamical systems approach to number theory, Amer: Math. Monthly, 107 (2000),
no.5, 422—428.

[23] Ira M. Gessel, Combinatorial proofs of congruences, Enumeration and design, Aca-
demic Press, Toronto, ON, 1984, 157—197.

[24] I. P. Goulden and D. M. Jackson, Combinatorial enumeration, John Wiley & Sons
Inc., New York, 1983.

[25] Michiel Hazewinkel, Formal groups and applications, Acadenric Press Inc. [Harcourt
Brace Jovanovich Publishers], New York, 1978.

[26] L. C. Hsu and Peter J. S. Shiue, Representation of various special polynomials via the
cycle indicator of symmetric group, In Combinatorics and graph theory ’95, Vol. 1
(Hefei), World Sci. Publishing, River Edge, NJ, 1995, 157—162.

[27] Leetsch C. Hsu and Peter Jau-Shyong Shiue, Cycle indicators and special functions,
Annals of Combinatorics, 5 (2001), no. 2, 179—196.

[28] Kenneth Ireland and Michael Rosen, A classical introduction to modern number the-
ory, Springer—Verlag, New York, second edition, 1990.

83

[29] Von W. Janichen, Uber die Verallgemeinerung einer Gauss’schen formal aus der

theorie der hoheren kongruenzen, Sitzungsberichte der Berliner Mathematischen
Gesellschaft, 20 (1921), 23—29.

[30] Dov Jarden, Arithmetical properties of sums of powers, Amer: Math. Monthly, 56
(1949), 457—461.

[31] Donald Knutson, l-rings and the representation theory of the symmetric group,
Springer-Verlag, Berlin, 1973.

[32] Neal Koblitz, p-adic numbers, p-adic analysis, and zeta-fimctions, 2nd Edition,
Springer-Verlag, New York, 1984.

[33] Serge Lang, Algebra, Springer-Verlag, New York, third edition, 2002.

[34] Lionel Levine, Fermat’s little theorem: a proof by function iteration, Math. Mag, 72
(1999), no.4, 308—309.

[35] Chyi-Lung Lin, Obtaining dividing formulas n l Q(n) from iterated maps, Fibonacci
Quart, 36 (1998), no.2, 118—124.

[36] Chyi-Lung Lin, A unified way for obtaining dividing formulas n | Q(n), Taiwanese J.
Math, 2 (1998), no.4, 469—481.

[37] I. G. Macdonald, Symmetric fimctions and Hall polynomials, Oxford Mathematical
Monographs. The Clarendon Press Oxford University Press, New York, second edi-
tion, 1995.

[38] Percy A. MacMahon, Combinatory analysis, 2 vols, Cambridge Univ. Press, Cam-
bridge, England, 1915—16; reprinted in one volume by Chelsea Publishing Co., New
York, 1960.

[39] D. G. Mead, Newton’s identities, The American Mathematical Monthly, 99 (1992),
no. 8, 749-751.

[40] N. Metropolis and Gian-Carlo Rota, Witt vectors and the algebra of necklaces, Adv.
in Math, 50 (1983), no.2, 95—125.

[41] Alun 0. Morris, Generalizations of the Cauchy and Schur identities, J. Combinatorial
Theory Set: A, 11 (1971), 163—169.

[42] R. F. Muirhead, Some proofs of Newton’s theorem on sums of powers of roots, Pro-
ceedings of the Edinburgh Mathematical Society, 23 (1904), 66—70.

[43] R. F. Muirhead, A proof of Waring’s expression for Za’ in terms of the coefficients
of an equation, Proceedings of the Edinburgh Mathematical Society, 23 (1904), 71—
74.

[44] Isaac Newton, The mathematical works of Isaac Newton Vol. II, Assembled with an
introduction by Derek T. Whiteside, Johnson Reprint Corp., New York, 1967.

84

[45] Isaac Newton, The mathematical papers of Isaac Newton Vol. I: 1664—1666, Edited
by D. T. Whiteside, Cambridge University Press, London, 1967.

[46] Isaac Newton, The mathematical papers of Isaac Newton Vol V: 1683—1684, Edited
by D. T. Whiteside, Cambridge University Press, New York, 1972.

[47] Yash Puri and Thomas Ward, A dynamical property unique to the Lucas sequence,
Fibonacci Quart, 39 (2001), no 5, 398—402.

[48] Yash Puri and Thomas Ward, Arithmetic and growth of periodic orbits, J. Integer Seq. ,
4 (2001), no. 2, Article 01.2.1, 18 pp. (electronic).

[49] John Riordan, An introduction to combinatorial analysis, John Wiley & Sons Inc.,
New York, 1958.

[50] Alain M. Robert, A course in p-adic analysis, Springer-Verlag, New York, 2000.

[51] Fred S. Roberts, Applied combinatorics, Prentice Hall Inc., Englewood Cliffs, NJ,
1984.

[52] Leslie G. Roberts, The ring of Witt vectors, In The Curves Seminar at Queen ’s, Vol.
XI (Kingston, ON, 1997), volume 105 of Queen ’5' Papers in Pure and Appl. Math.,
Queen’s Univ., Kingston, ON, 1997, 2—36.

[53] Gian-Carlo Rota and Bruce Sagan, Congruences derived from group action, European
J. Combin., 1 (1980), 67—76.

[54] F. Ruskey, C. R. Miers, and J. Sawada, The number of irreducible polynomials and
Lyndon words with given trace, SIAM J. Discrete Math., 14 (2001), no. 2, 240—245.

[55] Bruce E. Sagan, The symmetric group, Springer-Verlag, New York, second edition,
2001.

[56] I. Schur, Uber die Darstellung der symmetrischen und der alternierenden Gruppen
durch gebrochene lineare substitutionen, J. Reine Angew. Math., 139 (1911), 155—
250.

[57] I. Schur, On the representation of the symmetric and alternating groups by fractional
linear substitutions, Intemat. J. Theoret. Phys, 40 (2001), no. 1, 413—458. Translated
from the German [I Reine Angew. Math. 139 (1911), 155—250] by Marc-Felix Otto.

[58] Issai Schur, Arithmetische Eigenschaften der potenzsummen einer algebraischen Gle-
ichung, Compositio Math., 4 (1937), 432—444.

[59] J. Sheehan, An identity, Amer Math. Monthly, 77 (1970), 168.

[60] C. J. Smyth, A coloring proof of a generalisation of Fermat’s little theorem, The
American Mathematical Monthly, 93 1986, no. 6, 469-471.

85

[61] Richard P. Stanley, Enumerative combinatorics. Vol. 1, Cambridge University Press,
Cambridge, 1997.

[62] Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge University Press,
Cambridge, 1999.

[63] J. J. Sylvester, On a generalization of a theorem of Cauchy, The London, Edinburgh
and Dublin Philosophical Magazine and Journal of Science, 4th series, 22 (1861),
378—382.

[64] Jean-Yves Thibon, The cycle enumerator of unimodal permutations, Ann. Comb, 5
(2001), no.3-4, 493—500.

[65] S. Vajda, Fibonacci & Lucas numbers, and the golden section: Theory and applica-
tions, Ellis Horwood Ltd., Chichester, 1989.

[66] Francois Viete, Albert Girard, and Florimond de Beaune, The early theory of equa-
tions: on their nature and constitution, Translations of three treatises from the Latin
and French by Robert Schmidt and Ellen Black, Golden Hind Press, Fairfield, CT,
1986.

[67] Edward Waring, Meditationes algebraicce, edited and translated from the Latin by
Dennis Weeks, American Mathematical Society, Providence, RI, 1991.

[68] Herbert S. Wilf, Generatingfimctionology, Academic Press Inc., Boston, MA, second
edition, 1994.

[69] Doron Zeilberger, A combinatorial proof of Newton’s identities, Discrete Mathemat-
ics, 49 (1984), no. 3, 319.

86

 

IIIIIIIIIIIIIIIIIIIIIIIIIIIIII

1 11111 11111111111111