Free ebooks ==> www.Ebook777.com

CONTEMPORARY
MATHEMATICS
487

Arithmetic, Geometry,
Cryptography and Coding
Theory
International Conference
November 5–9, 2007
CIRM, Marseilles, France

Gilles Lachaud
Christophe Ritzenthaler
Michael A. Tsfasman
Editors

American Mathematical Society

www.Ebook777.com


This page intentionally left blank


Free ebooks ==> www.Ebook777.com

Arithmetic, Geometry,
Cryptography and Coding
Theory

www.Ebook777.com


This page intentionally left blank


Free ebooks ==> www.Ebook777.com

CONTEMPORARY
MATHEMATICS
487

Arithmetic, Geometry,
Cryptography and Coding
Theory
International Conference
November 5–9, 2007
CIRM, Marseilles, France
Gilles Lachaud
Christophe Ritzenthaler
Michael A. Tsfasman
Editors

American Mathematical Society
Providence, Rhode Island

www.Ebook777.com



Editorial Board
Dennis DeTurck, managing editor
George Andrews

Abel Klein

Martin J. Strauss

2000 Mathematics Subject Classification. Primary 11G10, 11G20, 14G10, 14G15, 14G50,
14Q05, 11M38, 11R42.

Library of Congress Cataloging-in-Publication Data
Arithmetic, geometry, cryptography and coding theory / Gilles Lachaud, Christophe Ritzenthaler,
Michael Tsfasman, editors.
p. cm. — (Contemporary mathematics ; v. 487)
Includes bibliographical references.
ISBN 978-0-8218-4716-9 (alk. paper)
1. Arithmetical algebraic geometry—Congresses. 2. Coding theory—Congresses. 3. Cryptography—Congresses. I. Lachaud, Gilles. II. Ritzenthaler, Christophe, 1976– III. Tsfasman,
M.A. (Michael A.), 1954–
QA242.5.A755
510—dc22

2009
2008052063

Copying and reprinting. Material in this book may be reproduced by any means for educational and scientific purposes without fee or permission with the exception of reproduction by
services that collect fees for delivery of documents and provided that the customary acknowledgment of the source is given. This consent does not extend to other kinds of copying for general
distribution, for advertising or promotional purposes, or for resale. Requests for permission for
commercial use of material should be addressed to the Acquisitions Department, American Mathematical Society, 201 Charles Street, Providence, Rhode Island 02904-2294, USA. Requests can
also be made by e-mail to

Excluded from these provisions is material in articles for which the author holds copyright. In
such cases, requests for permission to use or reprint should be addressed directly to the author(s).
(Copyright ownership is indicated in the notice in the lower right-hand corner of the first page of
each article.)
c 2009 by the American Mathematical Society. All rights reserved.
The American Mathematical Society retains all rights
except those granted to the United States Government.
Copyright of individual articles may revert to the public domain 28 years
after publication. Contact the AMS for copyright status of individual articles.
Printed in the United States of America.
∞ The paper used in this book is acid-free and falls within the guidelines

established to ensure permanence and durability.
Visit the AMS home page at />10 9 8 7 6 5 4 3 2 1

14 13 12 11 10 09


Free ebooks ==> www.Ebook777.com

Contents
Preface

vii

On the fourth moment of theta functions at their central point
Amadou D. Barry, St´
ephane R. Louboutin

1


On the construction of Galois towers
Alp Bassa, Peter Beelen

9

Codes defined by forms of degree 2 on quadric varieties in P4 (Fq )
Fr´
ed´
eric A. B. Edoukou

21

Curves of genus 2 with elliptic differentials and associated Hurwitz spaces
Gerhard Frey, Ernst Kani

33

A note on the Giulietti-Korchmaros maximal curve
Arnaldo Garcia

83

Subclose families, threshold graphs, and the weight hierarchy of Grassmann
and Schubert codes
Sudhir R. Ghorpade, Arunkumar R. Patil, Harish K. Pillai

87

Characteristic polynomials of automorphisms of hyperelliptic curves

Robert M. Guralnick, Everett W. Howe

101

Breaking the Akiyama-Goto cryptosystem
Petar Ivanov, Jos´
e Felipe Voloch

113

Hyperelliptic curves, L-polynomials, and random matrices
Kiran S. Kedlaya, Andrew V. Sutherland

119

On special finite fields
Florian Luca, Igor E. Shparlinski

163

Borne sur le degr´e des polynˆomes presque parfaitement non-lin´eaires
Franc
¸ ois Rodier

169

How to use finite fields for problems concerning infinite fields
Jean-Pierre Serre

183


On the generalizations of the Brauer-Siegel theorem
Alexey Zykin

195

v

www.Ebook777.com


This page intentionally left blank


Free ebooks ==> www.Ebook777.com

Preface
The 11th conference on Arithmetic, Geometry, Cryptography and Coding Theory (AGC2 T 11) was held in Marseilles at the “Centre International de Rencontres
Math´ematiques” (CIRM), during November 5-9, 2007. This international conference has been a major event in the area of applied arithmetic geometry for more
than 20 years and included distinguished guests J.-P. Serre (Fields medal, Abel
prize winner), G. Frey, H. Stichtenoth and other leading researchers in the field
among its 77 participants.
The meeting was organized by the team “Arithm´etique et Th´eorie de l’Information”
(ATI) from the “Institut de Math´ematiques de Luminy” (IML). The program consisted of 15 invited talks and 18 communications. Among them, thirteen were
selected to form the present proceedings. Twelve are original research articles covering asymptotic properties of global fields, arithmetic properties of curves and
higher dimensional varieties, and applications to codes and cryptography. The final article is a special lecture of J.-P. Serre entitled “How to use finite fields for
problems concerning infinite fields”.
The conference fulfilled its role of bringing together young researchers and specialists. During the conference, we were also happy to celebrate the retirement of
our colleague Robert Rolland with a special day of talks.
Finally, we thank the organization commitee of CIRM for their help during the

conference and the Calanques for its inspiring atmosphere.

vii

www.Ebook777.com


This page intentionally left blank


Free ebooks ==> www.Ebook777.com

Contemporary Mathematics
Volume 487, 2009

On the fourth moment of theta functions at their central
point
Amadou Diogo BARRY and St´ephane R. LOUBOUTIN
Abstract. Let χ be a Dirichlet character of
Pprime conductor p ≥ 3. Set A =
(χ(1) − χ(−1))/2 ∈ {0, 1} and let θ(x, χ) = n≥1 nA χ(n) exp(−πn2 x/p) (x >
0) be its associated theta series whose functional equation is used to obtain
the analytic continuation and functional equation of the L-series L(s, χ) =
P
−s . These functional equations depend on some root numbers
n≥1 χ(n)n
W (χ), complex numbers of absolute values equal to one. In particular, if
θ(1, χ) = 0, then numerical approximations to W (χ) = θ(1, χ)/θ(1, χ) can
be efficiently computed, which leads to a fast algorithm for computing class
numbers and relative class numbers of real or imaginary abelian number fields

(see the bibliography). According to numerical computations, it is reasonable
to conjecture that θ(1, χ) = 0 for any primitive Dirichlet character χ. One way
to prove that this conjecture at least holds true for infinitely many primitive
P
characters is to study the moments χ |θ(1, χ)|2k for k ∈ Z≥1 , where χ ranges
over all the even or odd primitive Dirichlet characters of conductor p. This
paper is devoted to proving a lower bound on these moments for 2k = 4.

1. Introduction
We restrict ourselves to even characters of prime conductors. Let p > 3 be a
prime. Let Xp+ be the set of the (p − 3)/2 primitive even Dirichlet characters of
conductor p. For χ ∈ Xp+ , set
χ(n)e−πn

2

θ(x, χ) =

x/p

(x > 0).

n≥1

The analytic continuation and the functional equation satisfied by the Dirichlet
−s
L-series L(s, χ) =
(s) > 0, stem from the functional equation
n≥1 χ(n)n ,
satisfied by the associated theta function (see [Dav, Chapter 9]):

W (χ)
θ(1/x, χ),
¯
x1/2
√
where W (χ) = τ (χ)/ p (the Artin root number, a complex number of absolute
value equal to 1 ) with τ (χ) = pk=1 χ(k)e2πik/p (Gauss sum).
(1)

θ(x, χ) =

1991 Mathematics Subject Classification. 2000 Mathematics Subject Classification. Primary
11R42, 11N37. Secondary 11M06.
Key words and phrases. Dirichlet characters, Artin root numbers, Theta functions, Divisor
function.
1
1

www.Ebook777.com


´
AMADOU DIOGO BARRY AND STEPHANE
R. LOUBOUTIN

2

Define the moments of order 2k:
|θ(1, χ)|2k


S2k (p) =

(k ∈ Z≥1 ).

χ∈Xp+

Proposition 1. S2 (p) is asymptotic to c2 p3/2 as p → ∞, where c2 =

√1 .
4 2π

Proof. Recall that
⎧
⎪
⎨(p − 3)/2 if b ≡ ±a (mod p) and gcd(a, p) = gcd(b, p) = 1,
χ(a)χ(b)
¯ = −1
if b ≡ ±a (mod p) and gcd(a, p) = gcd(b, p) = 1,
⎪
⎩
+
χ∈Xp
0
otherwise.
It follows that
S2 (p) =

∗

p−1

2
b≡±a

e−π(a

2

+b2 )/p

∗

−

e−πa

2

/p

2

a

a,b
(mod p)

(where starred sums indicate sums over indices not divisible by p). The desired
result follows.
Proposition 2. (See [Lou99]). There exists c > 0 such that S4 (p) ≤ cp2 log p
for p > 3.

Corollary 3. It holds that that θ(1, χ) = 0 for at least
characters χ ∈ Xp+ .

p/ log p of the

Proof. The Cauchy-Schwarz inequality yields that θ(1, χ) = 0 for at least
S2 (p)2 /S4 (p) of the χ’s in Xp+ .
Remark 4. For such a character χ, we have W (χ) = θ(1, χ)/θ(1, χ), by (1)
(hence numerical approximations to W (χ) can be efficiently computed, which leads
to a fast algorithm for computing class numbers and relative class numbers of real
or imaginary abelian number fields (see [Lou98], [Lou02] and [Lou07]).
The aim of this paper is to prove the following new result:
Theorem 5. There exists c > 0 such that S4 (p) ≥ cp2 log p for p > 3.
According to Proposition 2, Corollary 3, Theorem 5 and extended numerical
computations, we conjecture that θ(1, χ) = 0 for any primitive Dirichlet character
χ = 1, and the more precise behavior (see [Bar]):
Conjecture 6. There exists c4 > 0 such that S4 (p) is asymptotic to c4 p2 log p
as p → ∞.
As for the second and fourth moments of the values of Dirichlet L-functions
L(s, χ) at their central point s = 1/2, the following asymptotics are known:
|L(1/2, χ)|2 ∼ p log p
1=χ mod p

(see [Rama, Remark 3]) and
|L(1/2, χ)|4 ∼
1=χ mod p

1
p log4 p
2π 2



Free ebooks ==> www.Ebook777.com

ON THE FOURTH MOMENT OF THETA FUNCTIONS AT THEIR CENTRAL POINT

3

(see [HB, Corollary (page 26)]). It is also conjectured that for k ∈ Z≥1 there exists
a positive constant C(k) such that
2

|L(1/2, χ)|2k ∼ C(k)p logk p
1=χ mod p

and it is known that (see [RS]))
2

|L(1/2, χ)|2k

k

p logk p.

1=χ mod p

2. The second moment of the restricted divisor function
Our proof of Theorem 5 is based on a new method: the study of the moment
of order 2 of the restricted divisor function (see Proposition 7 below). It is known
that (see [Ten]):

√
S(x) =
1 = x(log x + 2γ − 1) + O( x).
1≤m
It follows that for c > 1 the first moment of the restricted divisor function
1 = S(x) − 2

Sc (x) =
1≤m
= S(x) − 2
d< 1c

√
x

1
1≤m
d|m
1 √m≤d≤c√m
c

d|m
√
d< 1 m
c

√

x
− c2 d + O(1) = 2(log c)x + O( x)
d

is asymptotic to 2(log c)x as x → ∞. Now,
2

T (n) =

1
1≤m
is asymptotic to π12 x log3 x as x → ∞. We give an asymptotic for the second
moment of the restricted divisor function:
Proposition 7. Fix c > 1. Then,
2

Tc (x) =

1
1≤m
=

d|m
1 √m≤d≤c√m
c

12 log2 c
x log x + O(x).

π2

It follows that
e−π(m/d−d)

Λ(n) =

2

/n

2

n log n.

1≤m
Remark 8. It holds that Λ(n)

n log n, by [Lou99, Lemme 2].
√
√
Proof. Let us prove the second assertion. Fix c > 1. If 1c m ≤ d ≤ c m,
then (m/d − d)2 /n ≤ (c − 1/c)2 m/n ≤ (c − 1/c)2 for 1 ≤ m ≤ n. It follows that
2

Λ(n) ≥ e−2π(c−1/c) Tc (n).
Let us now prove the first assertion. We have
Tc (x) =

1.
1≤m
d1 |m
1 √m≤d ≤c√m
1
c

d2 |m
1 √m≤d ≤c√m
2
c

www.Ebook777.com


´
AMADOU DIOGO BARRY AND STEPHANE
R. LOUBOUTIN

4

Since
1 = Sc (x) = O(x)
d1 |m
1 √m≤d ≤c√m
1
c

1≤m

we may assume that d2 = d1 , or even that d2 < d1 . Since
1 if gcd(D1 , D2 ) = 1
0 otherwise,

µ(δ) =
δ|D1
δ|D2

we have
Tc (x) = 2Uc (x) + O(x),

(2)
where
Uc (x)

=

1
1≤m
=

=

d1 |m
1 √m≤d ≤c√m
1
c

√
√
dd

√
√
dd

d2 |m
1 √m≤d 2
1
c

1
D2 gcd(D1 ,D2 )=1

m=kdD1 D2 d2 D 2 /c2 ≤m≤c2 d2 D 2 , i∈{1,2}
i
i

µ(δ)

1
√
D1 < cdδx

D2
m=kdδ 2 D1 D2 d2 δ 2 D 2 /c2 ≤m≤c2 d2 δ 2 D 2 , i∈{1,2}
i
i

(write di = dDi with gcd(D1 , D2 ) = 1 and m = kdD1 D2 , then change Di into δDi
and m into kdδ 2 D1 D2 ).
Hence,
Uc (x) =

(3)

√
√
dd

µ(δ)Mc (d, δ, x),

where
Mc (d, δ, x) =

Nc (d, δ, D1 , D2 , x),
√
D1 < cdδx

D2

with Nc (d, δ, D1 , D2 , x) being the number of positive integers k such that
x
(4)
k< 2
dδ D1 D2
√
√
1
2
2
and c kdδ D1 D2 ≤ dδDi ≤ c kdδ D1 D2 for i ∈ {1, 2}, i.e. such that
c2 dD2
dD1
≤
k
≤
,
c2 D2
D1

(5)

which implies D1 /c2 ≤ D2 .
To begin with, Uc (x) is not too large. Indeed, by (5), we have d/c2 ≤ k ≤ c2 d and
Nc (d, δ, D1 , D2 , x) ≤ (c2 − 1/c2 + 1)d. Therefore,
x
1 ≤ (c4 + c2 − 1) 2
Mc (d, δ, x) ≤ (c2 − 1/c2 + 1)d
dδ

√
√
c x
c x
D1 <

and Uc (x) ≤

√
d
√
δ
dδ

Mc (d, δ, x)
Tc (x)

D2 <

dδ

x log x. Thus, by (2), we have

x log x.

To prove our Proposition, we use (2), (3) and the following Lemma 9.

Free ebooks ==> www.Ebook777.com

ON THE FOURTH MOMENT OF THETA FUNCTIONS AT THEIR CENTRAL POINT

Lemma 9. It holds that Mc (d, δ, x) = (2 log2 c) dδx2 + O(
Proof. In the range D1 <

√
c x
dδ

√
x
δ )

+ O( d2xδ2 ).

we have

x
dD1
< 2
.
2
c D2
dδ D1 D2
Hence, (4) and (5) are equivalent to
c2 dD2
D1
x

dδ 2 D1 D2

dD1
≤k≤
c2 D2

(6)
In setting

√

if D2 ≤ cdδx
otherwise.

√

x
,
cdδ
we obtain that Nc (d, δ, D1 , D2 , x) is the number of k’s such that
X=

c2 dD2
D1
c2 dX 2
D1 D2

dD1
≤k≤
c2 D2

(7)

if D2 ≤ X
otherwise.

Therefore, we have:
Mc (d, δ, x) =

Nc (d, δ, D1 , D2 , x)
D1
=
D1
c2 dD2
dD1
− 2
+ O(1)
D1
c D2

⎧
⎨

+
X≤D1
⎩

D1 /c2 ≤D2 ≤X

c2 dD2
dD1
− 2
+ O(1)
D1
c D2
2

+
X≤D2
=

c2 d
D1
−

d
c2

c dX
dD1
− 2
+ O(1)
⎭
D1 D2
c D2

D2
+ c2 d
D1

D1
X≤D1
X≤D1
1
D1 D2

+O(X 2 )
c2 d
1
c2 d
(1 − 4 ) D1 + O(1) +
2
c
2
D1
d
− 2
c

X≤D1

X2
1
− 4 D1 + O(1)
D1
c

D1 log(c2 ) + O(1)
D1
+c2 dX 2
X≤D1
D2
D1

D1
D2

+c2 dX 2

=

⎫
⎬

2

log(D1 /X)
1
)

+ O(
D1
D1 X

2

+O(X )

www.Ebook777.com

5


´
AMADOU DIOGO BARRY AND STEPHANE
R. LOUBOUTIN

6

and
Mc (d, δ, x) =

=

1
c2 d
(1 − 4 ) X 2 + O(X)
4
c
c2 d

1
+
X 2 log(c2 ) + O(X) − 4 (c4 − 1)X 2 + O(X) + O(X)
2
2c
d log(c2 ) 4 2
c X + O(X)
−
2c2
c2 X
log(u/X)
1
2
2
+c dX
du + O( )
u
X
X
+O(X 2 )
2c2 d(log2 c)X 2 + O(dX) + O(X 2 ),

which proves the Lemma.
3. Proof of Theorem 5
Set
e−π(m/d−d)

0 < λn (m) =

2

/n

.

d|m

Then,
−π(a
χ(ab)χ(cd)e
¯

S4 (p) =

2

+b2 +c2 +d2 )/p

χ∈Xp+ a,b,c,d
∗

=

e−π(a

−

2

+b2 +c2 +d2 )/p

+

a,b,c,d
∗

≥

−

4

−πa2 /p

e
a

≥

∞

−

e−πu

2

/p

p−1

+
2
4

du

+

0

=

≥

−p2 /16 +

−p2 /16 +

p−1
2
p−1
2

p−1
2

∗

e−π(a
j=1

p−1
2

ab≡j

2

2

+b2 )/p

a,b
(mod p)

p−1

e−π(a
j=1

m≡j

m≥1
(mod p)

2

+m2 /a2 )/p

a|m

λp (m)e−2πm/p
m≡j

+b2 +c2 +d2 )/p

p−1

p−1

j=1

2

a,b,c,d
cd≡±ab (mod p)

2

m≥1
(mod p)

p−1

λp (j)2 e−4πj/p
j=1
p−1

≥

e−π(a

p − 1 −4π
p − 1 −4π
e
e
−p /16 +
λp (j)2 = −p2 /16 +
Λ(p).
2
2
j=1
2

By Proposition 7, it follows that
S4 (p)

p2 log p.

2


Free ebooks ==> www.Ebook777.com

ON THE FOURTH MOMENT OF THETA FUNCTIONS AT THEIR CENTRAL POINT

7

References
[Bar] A. D. Barry. Moments of theta functions at their central point. PhD Thesis, ongoing work.

[Dav] H. Davenport. Multiplicative Number Theory. Springer-Verlag, Grad. Texts Math. 74, Third
Edition, 2000.
[HB] D. R. Heath-Brown. The fourth power mean of Dirichlet’s L-function. Analysis 1 (1981),
25–32.
[Lou98] S. Louboutin. Computation of relative class numbers of imaginary abelian number fields.
Experimental Math. 7 (1998), 293–303.
[Lou99] S. Louboutin. Sur le calcul num´
erique des constantes des ´
equations fonctionnelles des
fonctions L associ´
ees aux caract`
eres impairs. C. R. Acad. Sci. Paris S´er. I Math. 329 (1999),
347–350.
[Lou02] S. Louboutin. Efficient computation of class numbers of real abelian number fields. Algorithmic Number Theory (Sydney, 2002), Lectures Notes in Computer Science 2369 (2002),
134–147.
[Lou07] S. Louboutin. Efficient computation of root numbers and class numbers of parametrized
families of real abelian number fields. Math. Comp. 76 (2007), 455–473.
[Rama] K. Ramachandra. Some remarks on a Theorem of Montgomery and Vaughan. J. Number
Theory 11 (1979), 465–471.
[RS] Z. Rudnick and K. Soundararajan. Lower bounds for moments of L-functions. Proc. Natl.
Acad. Sci. USA 102 (2005), 6837–6838.
[Ten] G. Tenenbaum. Introduction a
` la th´
eorie analytique et probabiliste des nombres. Cours
Sp´
ecialis´es. Soci´et´
e Math´ematique de France, Paris, 1995.
Institut de Math´
ematiques de Luminy, UMR 6206. 163, avenue de Luminy. Case 907.
13288 Marseille Cedex 9, FRANCE

E-mail address: ,

www.Ebook777.com


This page intentionally left blank


Free ebooks ==> www.Ebook777.com

Contemporary Mathematics
Volume 487, 2009

On the Construction of Galois Towers
Alp Bassa and Peter Beelen
Abstract. In this paper we study an asymptotically optimal tame tower over
the field with p2 elements introduced by Garcia-Stichtenoth. This tower is
related with a modular tower, for which explicit equations were given by Elkies.
We use this relation to investigate its Galois closure. Along the way, we obtain
information about the structure of the Galois closure of X0 (pn ) over X0 (pr ),
for integers 1 < r < n and prime p and the Galois closure of other modular
towers (X0 (pn ))n .

1. Introduction
Using Goppa’s construction of codes from curves over finite fields, Tsfasman–
Vladut–Zink [13] constructed sequences of codes of increasing length with limit
parameters above the Gilbert–Varshamov bound and hence better than those of
all previously known such sequences. Their construction is mainly based on the
existence of curves over a finite field of high genus with many rational points. This
enhanced the interest in towers of curves over finite fields. Subsequently, other

applications of such towers in coding theory and cryptography were discovered, for
instance for the construction of hash functions, low discrepancy sequences etc.
A natural idea is to search for such sequences of curves, with some additional
structure, which would reflect itself in some additional structure of the objects
constructed from them. Stichtenoth [12] constructed for example sequences of selfdual and transitive codes attaining the Tsfasman–Vladut–Zink bound over finite
fields with square cardinality. This was done by using a tower of function fields
E0 ⊆ E1 ⊆ E2 ⊆ . . ., where all extensions En /E0 are Galois.
Motivated by this, we study Galois closures of the modular towers (X0 (pn ))n .
In particular, we investigate the Galois closure of a tower M over Fp2 introduced
by Garcia–Stichtenoth [3], which is recursively defined by
X2 + 1
.
2X
This tower corresponds to the modular tower (X0 (2n ))n , for which explicit equation
were given by Elkies [2]. Using this interpretation of M as a modular tower, we
find the exact degrees of extensions in the Galois closure of it and study the Galois
Y2 =

1991 Mathematics Subject Classification. Primary:14H05, Secondary:11R32.
Key words and phrases. Function field, modular curve, Galois tower.
c 0000
(copyright Society
holder)
c 2009 American
Mathematical

1
9

www.Ebook777.com

10
2

ALP BASSA AND PETER BEELEN

groups that appear. We show that the function fields of the Galois closure can be
obtained as a compositum of three different embeddings of the function fields in
the tower M.
For more definitions and further details about (explicit) towers of algebraic
function fields, we refer to [5].
2. Groups of Galois closure
In this section the field of definition is always assumed to be C, the field of
complex numbers. Let p be a prime number and n > 1 an integer. The following
group is standard in the theory of modular curves:
a
c

Γ0 (pn ) :=

b
d

∈ SL(2, Z) : c ≡ 0 (mod pn ) .

Associated to this group is the modular curve X0 (pn ) which has been studied
extensively in the literature, cf. [7, 8].
Let 0 < r < n be integers. The Galois closure of X0 (pn ) over X0 (pr ) has Galois
group Γ0 (pr )/∆r (pn ) with

σΓ0 (pn )σ −1 .

∆r (pn ) :=
σ∈Γ0 (pr )
n

The group ∆r (p ) is the largest normal subgroup of Γ0 (pr ) contained in Γ0 (pn ),
since if H
Γ0 (pr ) and H ⊂ Γ0 (pn ), then H ⊂ σ∈Γ0 (pr ) σΓ0 (pn )σ −1 = ∆r (pn ).
The maximality of ∆r (pn ) with respect to the above property will be used later.
The goal of this section is to compute the order of the groups Γ0 (pr )/∆r (pn )
and to obtain information about its group structure. We start by describing the
group ∆r (pn ) in more detail.
Proposition 2.1.
a
∆r (pn ) =
c

b
d

∈ Γ0 (pn ) : pn−r |a − d − bpr and pn−r |2bpr

Proof. We denote by H the group on the right-hand side of above equality.
For an element
a b
h=
c d
of SL(2, Z) to be in H it needs to satisfy three things:
1) pn |c,

2) pn−r |a − d − bpr and
3) pn−r |2bpr .
Clearly H ⊂ Γ0 (pn ), so to prove the proposition it is enough to show that
H
Γ0 (pr ) and that ∆r (pn ) ⊂ H, since then ∆r (pn ) ⊃ H follows from the
maximality of ∆r (pn ).
First we prove that H Γ0 (pr ). Conjugating an element h ∈ H with a matrix
m=

α
γpr

β
δ

,

from Γ0 (pr ) we find that
mhm−1 =

−pr γ(αb + βd) + (αa + βc)δ
pr γ(a − d)δ − bp2r γ 2 + cδ 2

α2 b + αβ(d − a) − β 2 c
p γ(αb − βa) + (αd − βc)δ
r

.

Free ebooks ==> www.Ebook777.com

11
3

ON THE CONSTRUCTION OF GALOIS TOWERS

We need to check that this an element of H. First we show that it is an element of
Γ0 (pn ). We have
pr (a − d)γδ − bp2r γ 2 + cδ 2 ≡ bp2r γ(δ − γ) ≡ 0 (mod pn ).
The first equality follows from properties 1) and 2) of h listed above. The last
equality follows directly from property 3) of h if p = 2. If p = 2, then it only
implies that 2n−1 divides bp2r , but δ has to be odd if p = 2, implying that in this
case 2 divides γ(δ − γ).
Using again that a ≡ d + bpr (mod pn−r ) and c ≡ 0 (mod pn−r ), we see that
the second condition for mhm−1 to be in H is equivalent to the statement
bpr (pr β(α + γ) − α(α + 2γ − δ)) ≡ 0 (mod pn−r ).
From property 3) of h we see that this is satisfied if p = 2, while if p = 2, then
2n−r−1 |bpr and 2|α(α − δ), since δ is odd if p = 2.
It remains to check that the third condition is satisfied, but this can easily be
seen to hold as well. We conclude that mhm−1 ∈ H and hence that H Γ0 (pr ).
Now we wish to prove that ∆r (pn ) ⊂ H. In order to do this we introduce the
element
1 0
.
A :=
pr 1
Then for any h ∈ Γ0 (pn ) we have that
AhA−1 =

b
a − bpr
c + p (a − d − bpr ) d + bpr
r

,

which implies that if AhA−1 ∈ Γ0 (pn ), then pn−r |a − d − bpr . Similarly, if A−1 hA ∈
Γ0 (pn ), then pn−r |a−d+bpr . Therefore, if h ∈ Γ0 (pn )∩AΓ0 (pn )A−1 ∩A−1 Γ0 (pn )A,
then pn |c, pn−r |a − d − bpr and pn−r |a − d + bpr , which is equivalent to conditions
1),2) and 3) above. In other words:
∆r (pn ) ⊂ Γ0 (pn ) ∩ AΓ0 (pn )A−1 ∩ A−1 Γ0 (pn )A ⊂ H,
which concludes the proof.
Corollary 2.2. We have
∆r (pn ) = Γ0 (pn ) ∩ AΓ0 (pn )A−1 ∩ A−1 Γ0 (pn )A,
with
A :=

1
pr

0
1

.

Proof. In the above proposition we saw that
∆r (pn ) ⊂ Γ0 (pn ) ∩ AΓ0 (pn )A−1 ∩ A−1 Γ0 (pn )A ⊂ H,
but we have also seen that H ⊂ ∆r (pn ).
The group ∆r (pn ) has some further properties we wish to ascertain. For a

group G, we denote by [G, G] its commutator subgroup.
Lemma 2.3. Suppose that n > r > 0. We have
[∆r (pn ), ∆r (pn )] ⊂ ∆r (pn+1 )
and
g ∈ ∆r (pn ) ⇒ g p ∈ ∆r (pn+1 ).
As a consequence, the group ∆r (pn )/∆r (pn+1 ) is an elementary abelian p-group.

www.Ebook777.com


12
4

ALP BASSA AND PETER BEELEN

Proof. A direct calculation shows that [∆r (pn ), ∆r (pn )] ⊂ Γ0 (pn+1 ). Also,
since ∆r (pn ) Γ0 (pr ), we find that for any σ ∈ Γ0 (pr ) we have
σ[∆r (pn ), ∆r (pn )]σ −1 = [σ∆r (pn )σ −1 , σ∆r (pn )σ −1 ] = [∆r (pn ), ∆r (pn )].
This implies that
σ[∆r (pn ), ∆r (pn )]σ −1 ⊂ ∆r (pn+1 ).

[∆r (pn ), ∆r (pn )] =
σ∈Γ0

(pr )

To prove the second item, we use that
a
cpn

−d
ak + O(pn )
b aa−d
+ O(pn )
n ak −dk
2n
k
cp a−d + O(p )
d + O(pn )
k

k

b
d

=

k

,

where O(pm ) denotes some number divisible by pm . This can be showed directly
using induction on k. If k = p, then cpn (ap −dp )/(a−d) ≡ cpn (a−d)p−1 mod pn+1 .
Since g ∈ ∆r (pn ) we have that pn−r |a − d − bpr , implying that p|a − d. Hence
g p ∈ Γ0 (pn+1 ). By definition of ∆r (pn ), we have that for any σ ∈ Γ0 (pr ), the
element σ −1 gσ is in Γ0 (pn ), implying that (σ −1 gσ)p = σ −1 g p σ ∈ Γ0 (pn+1 ). This
implies that g p ∈ σ∈Γ0 (pr ) σΓ0 (pn+1 )σ −1 = ∆r (pn+1 ).
The final statement of the lemma follows directly from the first two statements.

3. The order of the group ∆r (pn )/Γ(pn )
The following congruence group is well-known:
Γ(pn ) :=

a
c

b
d

∈ SL(2, Z) :

a
c

b
d

≡

1 0
0 1

(mod pn ) .

It is the kernel of the reduction modulo pn map: ϕ : SL(2, Z) → SL(2, Z/pn Z) and
one can show that this map is surjective ([9, section 1.6]). Also it is well known [9]
that
(3.1)

#SL(2, Z/pn Z) = p3n − p3n−2 .

Note that by Proposition 2.1 the group Γ(pn ) is a (normal) subgroup of ∆r (pn ).
The goal of this section is to compute the cardinality of the group ∆r (pn )/Γ(pn ).
We will start by giving several lemmas.
Lemma 3.1. We have that
∆r (pn )/Γ(pn ) ∼
=

a b
0 d

∈ SL(2, Z/pn Z) : pn−r |a − d − bpr and pn−r |2bpr .

Proof. This follows directly from Proposition 2.1 using the reduction modulo
pn map ϕ.
Lemma 3.2. Let n > r > 0 be integers and suppose that p is an odd prime.
Then we have that
#∆r (pn )/Γ(pn ) =

2pr+n
2p3r

if n ≤ 2r,
else.


Free ebooks ==> www.Ebook777.com

ON THE CONSTRUCTION OF GALOIS TOWERS

13
5

Proof. Using Lemma 3.1 and the assumption that p is odd, it is enough to
count the number of triples (a, b, d) ∈ (Z/pn Z)3 satisfying pn |ad − 1, pn−r |a − d and
pn−r |bpr .
We claim that the number of (a, d) ∈ (Z/pn Z)2 satisfying pn |ad−1 and pn−r |a−
d equals 2pr . From the conditions, it is clear that pn−r |a2 − 1, which implies
that a ≡ ±1 (mod pn−r ). This leaves exactly 2pr possibilities for a. Given any
a satisfying the last congruence, there exists exactly one d ∈ Z/pn Z such that
pn |ad − 1 and by reducing modulo pn−r we see that d ≡ ±1 ≡ a. This means that
pn−r |a − d is satisfied for this d as well.
We claim that the number of b ∈ Z/pn Z such that pn−r |bpr is equal to pn if
n ≤ 2r and equal to p2r if n > 2r. Indeed, if n ≤ 2r, the condition pn−r |bpr is
always satisfied, so that all b’s in Z/pn Z are possible. If n > 2r, then the condition
simplifies to pn−2r |b, meaning that all p2r multiples of pn−2r in Z/pn Z are solutions.
Multiplying the number of possibilities for (a, d) with that for b, the lemma
follows.
Lemma 3.3. Let n > r > 0 be integers.
⎧ 2r+1
2
⎪
⎪
⎪
⎪
24
⎪
⎪
⎪

2r+3
⎪
2
⎪
⎪
⎨ 5
2
#∆r (2n )/Γ(2n ) =
⎪ 28
⎪
⎪
⎪
22r+5
⎪
⎪
⎪
⎪
2n+r+2
⎪
⎪
⎩ 3r+3
2

Then we have that
if
if
if
if
if
if

if
if

n − r = 1,
n = 3 and r = 1,
n − r = 2 and r > 1,
n = 4 and r = 1,
n = 5 and r = 2,
n − r = 3 and r > 2,
n − r > 3 and n ≤ 2r,
n − r > 3 and n > 2r.

Proof. Using Lemma 3.1 it is enough to count the number of triples (a, b, d) ∈
(Z/2n Z)3 satisfying
1) 2n |ad − 1,
2) 2n−r |a − d − b2r and
3) 2n−r−1 |b2r .
Since 2n−r−1 |b2r , we see that b2r ≡ 0 mod 2n−r or b2r ≡ 2n−r−1 mod 2n−r .
Combining with 2), we see that d ≡ a mod 2n−r or d ≡ a + 2n−r−1 mod 2n−r .
Substituting in 1) gives that a2 ≡ 1 mod 2n−r or a2 ≡ 1 + a2n−r−1 mod 2n−r .
Since from 1), we can deduce that a is odd, the latter congruence simplifies to
a2 ≡ 1 + 2n−r−1 mod 2n−r . We now distinguish several cases.
Case 1, n − r = 1. In this case all solutions are characterized by choosing a ∈
Z/2n Z to be odd, d its multiplicative inverse modulo 2n and arbitrary b ∈ Z/2n Z.
Thus there are 22n−1 = 22r+1 possibilities.
Case 2, n − r = 2. We have seen that a2 ≡ 1 mod 4 or a2 ≡ 3 mod 4. The latter
is not possible, so we deduce that a2 ≡ 1 mod 4, which implies that a ≡ d mod 4 and
b2r ≡ 0 mod 4. All in all we get that we can choose a ≡ ±1 mod 4, b2r ≡ 0 mod 4
and d ≡ a−1 mod 2n . For r = 1 this gives 16 possibilities for (a, b, d) and for r > 1
exactly 22r+3 .

Case 3, n − r = 3. First we get that a2 ≡ 1 mod 8 or a2 ≡ 5 mod 8, but
the latter is again not possible, since 8|a2 − 1 for any odd number a. This means
that b2r ≡ 0 mod 8. Moreover, the condition that a2 ≡ 1 mod 8 implies that
a ≡ ±1 or ± 3 mod 8. Counting similarly as above, we find that there are 32
possibilities for (a,b,d) if r = 1, 256 if r = 2 and 22r+5 if r > 2.

www.Ebook777.com


14
6

ALP BASSA AND PETER BEELEN

Case 4, n − r > 3. First we assume that b2r ≡ 0 mod 2n−r , which means
that there are 22r possibilities for b if n > 2r and 2n otherwise. Then we found
that a2 ≡ 1 mod 2n−r , which implies that a ≡ ±1 or ± 1 + 2n−r−1 mod 2n−r ,
leaving 4 · 2r possibilities for a. Now we can choose d to be the multiplicative
inverse of a modulo 2n and a direct computation shows that a ≡ d mod 2n−r . All
in all we find 2n+r+2 possibilities if n ≤ 2r and 23r+2 if n > 2r, still assuming
that b2r ≡ 0 mod 2n−r . Now assume that b2r ≡ 2n−r−1 mod 2n−r . This can
only occur if r ≤ n − r − 1, or equivalently if n > 2r and then the number of
possibilities for b is 22r . We saw that a2 ≡ 1 + 2n−r−1 mod 2n−r , implying that
a ≡ ±1 + 2n−r−2 or ± 1 − 2n−r−2 mod 2n−r . As before we choose d to be the
inverse of a, but now we find that d ≡ a + 2n−r−1 mod 2n−r , so that condition 2)
is satisfied. Condition 3) is satisfied automatically. We find 23r+2 possibilities if
n > 2r, but none if n ≤ 2r. In total for case 4, we find 2n+r+2 possibilities for
(a, b, d) if n ≤ 2r and 23r+3 otherwise.

4. Degrees and structure of Galois closure

Given n > r > 0 and a prime p, we will now determine the degree of the Galois
closure of X0 (pn ) over X0 (pr ). We quote the following well-known facts [9, section
1.6]: Let m be a positive integer. The degree of the covering X(pm ) → X(1) equals
p3m−2 (p2 − 1)/2, unless p = 2 and m = 1 in which case it equals 6. The degree of
the extension X0 (pm ) → X(1) equals (p + 1)pm−1 . As a consequence we see that
the degree of X(pm+1 ) → X(pm ) equals p3 unless p = 2 and m = 1, in which case it
equals 4. Also the degree of X0 (pm+1 ) → X0 (pm ) equals p. This together with the
previous results enables us to compute all degrees in the tower obtained by taking
the Galois closure of X0 (pn ) over X0 (pr ) for running n and fixed r.
Lemma 4.1. Let n > r > 0 be integers, p an odd prime and let X˜0r (pn ) denote
the Galois closure of X0 (pn ) over X0 (pr ). Then
⎧
⎨ p(p − 1)/2 if n = r + 1,
p2
if r + 1 < n ≤ 2r,
deg(X˜0r (pn ) → X˜0r (pn−1 )) =
⎩ 3
if n > 2r.
p
For n > r + 1, the covering X˜0r (pn ) → X˜0r (pn−1 ) is elementary abelian.
Proof. From Lemma 3.2 we can calculate all degrees of the coverings X(pn ) →
Indeed, since −I ∈ ∆r (pn ) and −I ∈ Γ(pn ), the only thing we need to do
is divide #∆r (pn )/Γ(pn ) by 2. Further, since deg(X0 (pr ) → X(1)) = (p + 1)pr−1
and deg(X(pr ) → X(1)) = (p2 − 1)p3r−2 /2, we find that deg(X(pr ) → X0 (pr )) =
(p−1)p2r−1 /2. All in all we now know all degrees of the coverings X(pm ) → X˜0r (pm )
for m ≥ r. Combined with the fact that deg(X(pm+1 ) → X(pm )) = p3 , the first
part of the lemma follows. The second part follows directly from Lemma 2.3.

X˜0r (pn ).

Free ebooks ==> www.Ebook777.com

ON THE CONSTRUCTION OF GALOIS TOWERS

15
7

Lemma 4.2. Let n > r > 0 be integers and let X˜0r (2n ) denote the Galois closure
of X0 (2n ) over X0 (2r ). Then
⎧
2 if n = r + 1,
⎪
⎪
⎪
⎪
2 if n = r + 2 and r > 1,
⎪
⎪
⎪
⎪
2 if n = r + 3 and r > 2,
⎪
⎪
⎪
⎪
4 if n = r + 2 and r = 1,
⎪
⎪
⎨

4 if n = r + 3 and r = 1, 2,
n
n−1
)) =
deg(X˜0r (2 ) → X˜0r (2
4 if n = r + 4 and r = 1, 2,
⎪
⎪
⎪
⎪
4 if r + 4 ≤ n ≤ 2r + 1,
⎪
⎪
⎪
⎪
8 if n > 2r + 3 and r = 1,
⎪
⎪
⎪
⎪
8 if n > 2r + 2 and r = 2,
⎪
⎪
⎩
8 if n > 2r + 1 and r > 2.
Proof. The proof is similar to that of the previous lemma, but now we use
Lemma 3.3.
Lemma 4.3. Let n > r > 0 be integers and p a prime. The extension X0 (pn ) →
X0 (pr ) is Galois if and only if
(1) p = 2 and n − r = 1,

(2) p = 2, r > 1 and n − r = 2,
(3) p = 2, r > 2 and n − r = 3,
(4) p = 3 and n − r = 1.
In all of these cases the Galois group is cyclic.
Proof. Since deg(X0 (pn ) → X0 (pr )) = pn−r , we can use Lemmas 4.1 and 4.2
to check when this degree is the same as deg(X˜0r (pn ) → X0 (pr )). Assuming the
covering X0 (pn ) → X0 (pr ) is Galois of order pn−r , we also see that its Galois group
is Γ0 (pr )/∆r (pn ). However, the element A mod ∆r (pn ), with A as in Corollary 2.2,
has order pn−r .
5. Reduction mod .
Let p be a prime. Until now, we have assumed that all the modular curves
we considered were defined over the field C. However, it is well known that the
curves X0 (pn ) have a model defined over Q [6]. Denote by ζpn a primitive pn -th
root of unity. The curve X(pn ) has a model defined over Q(ζpn ) and the covering
X(pn ) → X(1) is still Galois and has the same degree as when working over C.
Since the Galois closure of X0 (pn ) over X0 (pr ) is contained in X(pn ), it also has a
model defined over Q(ζpn ) and all degrees computed before are still correct when
working over this field. These models have good reduction modulo a prime if
= p. The Galois covering X(pn ) → X0 (pr ) is not necessarily Galois after this
reduction, but will be so when we consider it over a field containing a pn -th root of
unity. After having done so, the Galois group will be the same as before reducing
and in particular its degree is the same. All group theoretic arguments used before
are then still valid for the reductions, as long as the field of definition contains a
pn -th root of unity.
The following Lemmas will be useful:
Lemma 5.1. Let F be a function field over a perfect field K and let f (T ) ∈
F [T ] be a separable irreducible polynomial over F . Let α ∈ Ω be a root of f (T )
in some fixed algebraically closed field Ω ⊃ F . Let K be a separable algebraic

www.Ebook777.com