In this chapter we develop a theory for computing with Dirichlet characters, which are extremely important to computations with modular forms for (at least) two reasons:

To compute the Eisenstein subspace of , we write down Eisenstein series attached to pairs of Dirichlet characters (the space will be defined in Chapter

*Eisenstein Series and Bernoulli Numbers*).To compute , we instead compute a decomposition

and then compute each factor (see Section

*Dirichlet Character Decomposition*). Here the sum is over all Dirichlet characters of modulus .

Dirichlet characters appear frequently in many other areas of number theory. For example, by the Kronecker-Weber theorem, Dirichlet characters correspond to the -dimensional representations of .

After defining Dirichlet characters in Section *The Definition*, in
Section *Representing Dirichlet Characters* we describe a good way to represent Dirichlet
characters using a computer. Section *Evaluation of Dirichlet Characters* is about how
to evaluate Dirichlet characters and leads naturally to a discussion
of the baby-step giant-step algorithm for solving the discrete log
problem and methods for efficiently computing the Kronecker symbol.
In Section *Conductors of Dirichlet Characters* we explain how to factor Dirichlet
characters into their prime power constituents and apply this to the
computations of conductors. We describe how to carry out a number
of standard operations with Dirichlet characters in
Section *Restriction, Extension, and Galois Orbits* and discuss alternative ways
to represent them in Section *Alternative Representations of Characters*.
Finally, in Section *Dirichlet Characters in Sage* we give a very
short tutorial about how to compute with Dirichlet characters using Sage.

Fix an integral domain and a root of unity in .

Definition 4.1

A *Dirichlet character* of modulus over is a map
such that there is a homomorphism for which

We denote the group of such Dirichlet characters by . Note that elements of are in bijection with homomorphisms .

A familiar Dirichlet character is the Legendre symbol , with an odd prime, that appears in quadratic reciprocity theory. It is a Dirichlet character of modulus that takes the value on integers that are congruent to a nonzero square modulo , the value on integers that are congruent to a nonzero nonsquare modulo , and on integers divisible by .

Lemma 4.2

The groups and are isomorphic.

Proof

We prove the more general fact that for any finite abelian group , we have that . To deduce this latter isomorphism, first reduce to the case when is cyclic by writing as a product of cyclic groups. The cyclic case follows because if is cyclic of order , then contains an root of unity, so is also cyclic of order . Any two cyclic groups of the same order are isomorphic, so and are isomorphic.

Corollary 4.3

We have , with equality if and only if the order of our choice of is a multiple of the exponent of the group .

Proof

This is because .

Fix a positive integer . To find the set of “canonical”
generators for the group , write where are the prime divisors
of . By *Exercise 4.2*, each factor
is a cyclic group ,
except if and , in which case
is a product of the cyclic subgroup of
order with the cyclic subgroup . In all
cases we have

For such that , choose the generator of to be
the element of that is smallest and
generates. Finally, use the Chinese Remainder Theorem (see
[**Coh93**, Section 1.3.3]) to lift each to an element in
, also denoted , that is modulo each
for .

Algorithm 4.4

Given a prime power with odd, this algorithm computes the minimal generator of .

- [Factor Group Order] Factor as a product of primes. This is
equivalent in difficulty to factoring . (See, e.g.,
[
**Coh93**, Ch.8, Ch. 10] for an excellent discussion of factorization algorithms, though of course much progress has been made since then.) - [Initialize] Set .
- [Generator?] Using the binary powering algorithm (see
[
**Coh93**, Section 1.2]), compute , for each prime divisor of . If any of these powers are , then is not a generator, so set and go to step*(2)*. If no powers are , output and terminate.

See *Exercise 4.3* for a proof that this algorithm is correct.

Example 4.5

A minimal generator for is . We have and

so is not a generator for . (We see this just from .) However is a generator since

Example 4.6

In this example we compute minimal generators for , , and :

- The minimal generator for is .
- The minimal generators for , lifted to numbers modulo , are and . Notice that and and that is the minimal generator modulo .
- The minimal generators for , lifted to numbers modulo , are , , and . Note that , that and .

In Sage, the command `Integers(N)` creates .

```
sage: R = Integers(49)
sage: R
Ring of integers modulo 49
```

The `unit_gens` command computes the minimal generators for
, as defined above.

```
sage: R.unit_gens()
[3]
sage: Integers(25).unit_gens()
[2]
sage: Integers(100).unit_gens()
[51, 77]
sage: Integers(200).unit_gens()
[151, 101, 177]
sage: Integers(2005).unit_gens()
[402, 1206]
sage: Integers(200000000).unit_gens()
[174218751, 51562501, 187109377]
```

Fix an element of finite multiplicative order in a ring , and let denote the group of Dirichlet characters of modulus over , with image in . In most of this chapter, we specify an element by giving the list

(1)

of images of the generators of . (Note that if is
even, the number of elements of the list (1)
*does* depend on whether or not —there are two factors
corresponding to if , but only one if .) This
representation completely determines and is convenient for
arithmetic operations. It is analogous to representing a linear
transformation by a matrix.

Remark 4.7

In any actual implementation (e.g., the one in Sage), it
is better to represent the by recording an integer
such that , where
is a fixed root of unity. Then (1) is
internally represented as an element of , where
is the multiplicative order of . When
the representation of (1) is needed for an algorithm,
it can be quickly computed on the fly using a table of the powers
of .
See Section *Alternative Representations of Characters* for further discussion about
ways to represent characters.

Example 4.8

The group has elements , so it is cyclic of order . In contrast, the group has only the two elements and and order .

The command : `DirichletGroup(N)`
with no second argument creates the group of
Dirichlet characters with values in the
cyclotomic field , where
is the exponent of the group .
Every element in takes values
in , so .

```
sage: list(DirichletGroup(5))
[[1], [zeta4], [-1], [-zeta4]]
sage: list(DirichletGroup(5, QQ))
[[1], [-1]]
```

This section is about how to compute , where is a Dirichlet character and is an integer. We begin with an example.

Example 4.9

If , then , and , as
we saw in *Example 4.6*. The
exponent of is , since that
is the least common multiple of the exponents of
and .
The orders of , , and are , , and .
Let be a primitive root of
unity in . Then the following are generators
for :

and is an example element of order . To evaluate , we write in terms of , , and . First, reducing modulo , we see that . Next reducing modulo and trying powers of , we find that . Thus

We next illustrate the above computation of in Sage. First we make the group and list its generators.

```
sage: G = DirichletGroup(200)
sage: G
Group of Dirichlet characters of modulus 200 over
Cyclotomic Field of order 20 and degree 8
sage: G.exponent()
20
sage: G.gens()
([-1, 1, 1], [1, -1, 1], [1, 1, zeta20])
```

We construct .

```
sage: K = G.base_ring()
sage: zeta = K.0
sage: eps = G([1,-1,zeta^5])
sage: eps
[1, -1, zeta20^5]
```

Finally, we evaluate at .

```
sage: eps(3)
zeta20^5
sage: -zeta^15
zeta20^5
```

*Example 4.9* illustrates that if is represented using
a list as described above, evaluation of is inefficient without
extra information; it requires solving the discrete log problem in
.

Remark 4.10

For a general character , is calculation
of at least as hard as finding discrete
logarithms? Quadratic characters
are easier—see *Algorithm 4.23*.

Algorithm 4.11

Given a Dirichlet character of modulus , represented by a list , and an integer , this algorithm computes .

- [GCD] Compute . If , output and terminate.
- [Discrete Log] For each , write as a power of using some algorithm for solving the discrete log problem (see below). If , write as . (This step is analogous to writing a vector in terms of a basis.)
- [Multiply] Output as an element of , and terminate. (This is analogous to multiplying a matrix times a vector.)

*Exercise 4.4* gives an isomorphism
of groups

so one sees by induction that step *(2)* is “about as
difficult” as finding a discrete log in . There is an
algorithm called “baby-step giant-step”, which solves the discrete
log problem in in time , where is
the largest prime factor of (note that the discrete
log problem in reduces to a series of discrete log
problems in each prime-order cyclic factor). This is unfortunately
still exponential in the number of digits of ; it also uses
memory. We now describe this algorithm without
any specific optimizations.

Algorithm 4.12

Given a prime , a generator of , and an element , this algorithm finds an such that . (Note that this algorithm works in any cyclic group, not just .)

[Make Lists] Let be the ceiling of , and construct two lists

and

[Find Match] Sort the two lists and find a match . Then .

Proof

We prove that there will always be a match. Since we know that for some with and any such can be written in the form for , we will find such a match.

*Algorithm 4.12* uses nothing special about
, so it works in a generic group. It is a theorem that
there is no faster algorithm to find discrete logs in a “generic
group” (see [**Sho97**, **Nec94**]). There are
much better subexponential algorithms for solving the discrete log
problem in , which use the special structure of this
group. They use the number field sieve (see, e.g.,
[**Gor93**]), which is also the best-known algorithm for
factoring integers. This class of algorithms has been very well
studied by cryptographers; though sub-exponential, solving discrete
log problems when is large is still extremely difficult. For a
more in-depth survey see [**Gor04**].
For computing Dirichlet characters in our context, is not
too large, so *Algorithm 4.12* works well.

For many applications of Dirichlet characters to computing modular
forms, is fairly small, e.g., , and we
evaluate on a *huge* number of random elements, inside
inner loops of algorithms. Thus for such purposes it will often be
better to make a table of all values of , so that evaluation
of is extremely fast. The following algorithm computes a table
of all values of , and it does not require computing any
discrete logs since we are computing *all* values.

Algorithm 4.13

Given a Dirichlet character represented by the list of values of on the minimal generators of , this algorithm creates a list of all the values of .

[Initialize] For each minimal generator , set . Let , and set . Create a list of values, all initially set equal to . When this algorithm terminates, the list will have the property that

Notice that we index starting at .

[Add Value to Table] Set .

[Finished?] If each is one less than the order of , output and terminate.

[Increment] Set , , and . If , set , and then set , , and . If , do what you just did with but with all subscripts replaced by . Etc. (Imagine a car odometer.) Go to step

*(2)*.

The following algorithm for computing the order of reduces the problem to computing the orders of powers of in .

Algorithm 4.14

This algorithm computes the order of a Dirichlet character .

- Compute the order of each , for each minimal generator of . The order of is a divisor of so we can compute its order by considering the divisors of .
- Compute and output the least common multiple of the integers .

Remark 4.15

Computing the order of is potentially difficult.
Simultaneously using a different representation of Dirichlet
characters avoids having to compute the order of elements of
(see Section *Alternative Representations of Characters*).

The next algorithm factors as a product of “local” characters,
one for each prime divisor of . It is useful for other algorithms,
e.g., for explicit computations with trace formulas
(see [**Hij74**]). This factorization is easy to compute
because of how we represent .

Algorithm 4.16

Given a Dirichlet character , with , this algorithm finds Dirichlet characters modulo , such that for all , we have . If , the steps are as follows:

Let be the minimal generators of , so is given by a list

For , let be the element of defined by the singleton list .

Let be the element of defined by the list of length . Output the and terminate.

The factorization of *Algorithm 4.16* is unique since each
is determined by the image of the canonical map
in , which sends
to the element of that is
and for .

Example 4.17

If , then and .

Definition 4.18

The *conductor* of a Dirichlet character
is the smallest positive divisor such that
there is a character for which
for all with .
A Dirichlet character is *primitive* if its modulus equals
its conductor. The character associated to
with modulus equal to the conductor of is called
the *primitive character associated to* .

We will be interested in conductors later, when computing new subspaces of spaces of modular forms with character. Also certain formulas for special values of functions are only valid for primitive characters.

Algorithm 4.19

This algorithm computes the conductor of a Dirichlet character .

- [Factor Character] Using
*Algorithm 4.16*, find characters whose product is . - [Compute Orders] Using
*Algorithm 4.14*, compute the orders of each . - [Conductors of Factors] For each , either set if is the trivial character (i.e., of order ) or set , where is the largest power of that divides .
- [Adjust at ?] If and , set .
- [Finished] Output and terminate.

Proof

Let be the local factors of , as in step *(1)*).
We first show that the product of the conductors of the is
the conductor of . Since factors through ,
the product of the factors through ,
so the conductor of divides . Conversely, if
for some , then we could factor
as a product of local (prime power) characters differently, which contradicts
that this factorization is unique.

It remains to prove that if is a nontrivial character of modulus , where is a prime, and if is the order of , then the conductor of is , except possibly if . Since the order and conductor of and of the associated primitive character are the same, we may assume is primitive, i.e., that is the conductor of ; note that , since is nontrivial.

First suppose is odd.
Then the abelian group splits as a direct sum ,
where is the -power torsion subgroup of .
Also has order , where , which
is coprime to , is the order of the image of
in and is the order of the image in .
If , then the order of is coprime to , so
is in , which means that ,
so , as required. If , then
must have order divisible by , so has characteristic not
equal to . The conductor of does not change if we
adjoin roots of unity to , so in light of *Lemma 4.2*
we may assume that .
It follows that for each , the -power subgroup
of is the -torsion
subgroup of . Thus , since
is by assumption the smallest such group that
contains the projection of . This proves the
formula of step (*(3)*. We leave the argument
when as an exercise (see *Exercise 4.5*).

Example 4.20

If , then
as in *Example 4.17*,
is the product of and .
Because , the conductor of is .
The order of is (since is a
root of unity), so the conductor of is .
Thus the conductor of is .

In this section all characters have values in .

Frequently quadratic characters are described in terms of the Kronecker symbol , which we define for any integer and positive integer as follows. First, if is an odd prime, then for any integer ,

If , then

More generally, if with the prime, then

Remark 4.21

One can also extend to , but we will not need this.
The extension is to set and , for
, and to extend multiplicatively (in the denominator).
Note that the map is not a Dirichlet
character (see *Exercise 4.1*).

Let be the product of the primes such that is odd. If is odd, let ; otherwise, let .

Lemma 4.22

The function

is a Dirichlet character of modulus . The function

is a Dirichlet character of modulus .

Proof

When restricted to , each map , for prime, is a homomorphism, so a product of homomorphisms. The second statement follows from the definition and the fact that is a square modulo an odd prime if and only if .

This section is about going between representing quadratic
characters as row matrices and via Kronecker symbols. This is
valuable because the algorithms in
[**Coh93**, Section 1.1.4] for computing Kronecker symbols
run in time quadratic in the number of digits of the input.
They do
not require computing discrete logarithms; instead,
they use, e.g., that
, when is an odd prime.

Algorithm 4.23

Given , this algorithm computes a representation of the Kronecker symbol as a Dirichlet character.

- [Modulus] Compute as in
*Lemma 4.22*. - [Minimal Generators] Compute minimal generators of
using
*Algorithm 4.4*. - [Images] Compute for each using one
of the algorithms of [
**Coh93**, Section 1.1.4].

Example 4.24

We compute the Dirichlet character associated to .
Using Sage, we compute the , for , where the
are as in *Example 4.9*:

```
sage: kronecker(151,200)
1
sage: kronecker(101,200)
-1
sage: kronecker(177,200)
1
```

Thus the corresponding character is defined by .

Example 4.25

We compute the character associated to . We have , and minimal generators are

We have , , and . We find and . The corresponding character is .

Using the following algorithm, we can go in the other direction, i.e., write any quadratic Dirichlet character as a Kronecker symbol.

Algorithm 4.26

Given of order with modulus , this algorithm writes as a Kronecker symbol.

- [Conductor] Use
*Algorithm 4.19*to compute the conductor of . - [Odd] If is odd, output .
- [Even] If , output ; if , output .

Proof

Since is the conductor of a quadratic Dirichlet character,
it is a square-free product of odd primes times either
or , so the
group does not inject into for
any proper divisor of (see this by
reducing to the prime power case).
Since is odd and square-free, the character
has conductor .
For each odd prime ,
by step *(3)* of *Algorithm 4.19*
the factor at of both and
is a quadratic character with modulus .
By *Exercise 4.2* and *Lemma 4.2*
the group is cyclic, so it has a unique element
of order , so
the factors of and at are equal.

The quadratic characters with conductor a power of are , , and . The character is and the character is .

Example 4.27

Consider with modulus . It has conductor , and , so for all with , we have .

The following two algorithms restrict and extend characters to a compatible modulus. Using them, it is easy to define multiplication of two characters and , as long as and are subrings of a common ring. To carry out the multiplication, extend both characters to a common base ring, and then extend them to characters modulo and multiply.

Algorithm 4.28

Given a Dirichlet character and a divisor of that is a multiple of the conductor of , this algorithm finds a characters , such that , for all with .

- [Conductor] Compute the conductor of using
*Algorithm 4.19*, and verify that is divisible by the conductor and divides . - [Minimal Generators] Compute minimal generators for .
- [Values of Restriction] For each , compute as follows. Find a multiple of such that ; then .
- [Output Character] Output the Dirichlet character of modulus defined by .

Proof

The only part that is not clear is that in step *(3)*
there is an such that . If
we write , with and divisible
by all primes that divide , then since
. By the Chinese Remainder Theorem,
there is an such that and
. Then
and , which completes the proof.

Algorithm 4.29

Given a Dirichlet character and a multiple of , this algorithm finds a character , such that , for all with .

- Minimal Generators] Compute minimal generators for .
- [Evaluate] Compute for each . Since , we also have .
- [Output Character] Output the character .

Let be the prime subfield of , and assume that , where is a separable closure of . If and , let ; this defines an action of on . Our next algorithm computes the orbits for the action of on . This algorithm can provide huge savings for modular forms computations because the spaces and are canonically isomorphic if and are conjugate.

Algorithm 4.30

Given a Dirichlet character , this algorithm computes the orbit of under the action of , where is the prime subfield of , so or .

[Order of ] Let be the order of the chosen root .

[Nontrivial Automorphisms] If , let

If , compute the multiplicative order of , and let

[Compute Orbit] Compute and output the

*set*of unique elements for each (there could be repeats, so we output unique elements only).

Proof

We prove that the nontrivial automorphisms of
in characteristic are as in step *(2)*. It is
well known that every automorphism in characteristic on
is of the form , for some .
The images of under such automorphisms are

Suppose is minimal such that . Then the orbit of is . Also , where is the multiplicative order of , so is the multiplicative order of modulo , which completes the proof.

Example 4.31

The Galois orbits of characters in are as follows:

The conductors of the characters in orbit are , in orbit they are , in orbit they are , in they are , in the conductor is , and in the conductor is . (You should verify this.)

Sage computes Galois orbits as follows:

```
sage: G = DirichletGroup(20)
sage: G.galois_orbits()
[
[[1, 1]],
[[1, zeta4], [1, -zeta4]],
[[1, -1]],
[[-1, 1]],
[[-1, zeta4], [-1, -zeta4]],
[[-1, -1]]
]
```

Let be a positive integer and an integral domain, with fixed root of unity of order , and let . As in the rest of this chapter, write , and let be the corresponding cyclic factors of . In this section we discuss other ways to represent elements . Each representation has advantages and disadvantages, and no single representation is best. It is easy to convert between them, and some algorithms are much easier using one representation than when using another. In this section we present two other representations, each having advantages and disadvantages. There is no reason to restrict to only one representation; for example, Sage internally uses both.

We could represent by giving a list , where
each and . Then arithmetic in
is arithmetic in , which is very efficient.
A drawback to this approach (in practice) is that it is easy to
accidently consider sequences that do not actually correspond to
elements of . Also the choice of is less clear, which
can cause confusion. Finally, the orders of the local factors is more
opaque, e.g., compare with . Overall this
representation is not too bad and is more like representing a linear
transformation by a matrix. It has the *advantage* over the
representation discussed earlier in this chapter that arithmetic in
is very efficient and does not require any operations in the
ring .

Another way to represent would be to give a list of integers, but this time with , where is the order of . Then

which is already pretty complicated. With this representation we set up an identification

and arithmetic is efficient. This approach is seductive because every sequence of integers determines a character, and the sizes of the integers in the sequence nicely indicate the local orders of the character. However, giving analogues of many of the algorithms discussed in this chapter that operate on characters represented this way is tricky. For example, the representation depends very much on the order of , so it is difficult to correctly compute natural maps , for rings.

To create a Dirichlet character in Sage, first create the group of Dirichlet characters then construct elements of that group. First we make :

```
sage: G = DirichletGroup(11, QQ); G
Group of Dirichlet characters of modulus 11 over
Rational Field
```

A Dirichlet character prints as a matrix that gives the values of the character on canonical generators of (as discussed below).

```
sage: list(G)
[[1], [-1]]
sage: eps = G.0 # 0th generator for Dirichlet group
sage: eps
[-1]
```

The character takes the value on the unit generator.

```
sage: G.unit_gens()
[2]
sage: eps(2)
-1
sage: eps(3)
1
```

It is on any integer not coprime to :

```
sage: [eps(11*n) for n in range(10)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
```

We can also create groups of Dirichlet characters taking values in other rings or fields. For example, we create the cyclotomic field .

```
sage: R = CyclotomicField(4)
sage: CyclotomicField(4)
Cyclotomic Field of order 4 and degree 2
```

Then we define .

```
sage: G = DirichletGroup(15, R)
sage: G
Group of Dirichlet characters of modulus 15 over
Cyclotomic Field of order 4 and degree 2
```

Next we list each of its elements.

```
sage: list(G)
[[1, 1], [-1, 1], [1, zeta4], [-1, zeta4], [1, -1],
[-1, -1], [1, -zeta4], [-1, -zeta4]]
```

Now we evaluate the second generator of on various integers:

```
sage: e = G.1
sage: e(4)
-1
sage: e(-1)
-1
sage: e(5)
0
```

Finally we list all the values of .

```
sage: [e(n) for n in range(15)]
[0, 1, zeta4, 0, -1, 0, 0, zeta4, -zeta4,
0, 0, 1, 0, -zeta4, -1]
```

We can also compute with groups of Dirichlet characters with values in a finite field.

```
sage: G = DirichletGroup(15, GF(5)); G
Group of Dirichlet characters of modulus 15
over Finite Field of size 5
```

We list all the elements of , again represented by lists that give the images of each unit generator, as an element of .

```
sage: list(G)
[[1, 1], [4, 1], [1, 2], [4, 2], [1, 4], [4, 4],
[1, 3], [4, 3]]
```

We evaluate the second generator of on several integers.

```
sage: e = G.1
sage: e(-1)
4
sage: e(2)
2
sage: e(5)
0
sage: print [e(n) for n in range(15)]
[0, 1, 2, 0, 4, 0, 0, 2, 3, 0, 0, 1, 0, 3, 4]
```

Exercise 4.1

Let be the map given by

Prove that is not a Dirichlet character of any modulus .

Exercise 4.2

This exercise is about the structure of the units of .

- If is odd and is a positive integer, prove that is cyclic.
- For , prove that is a direct sum of the cyclic subgroups and , of orders 2 and , respectively.

Exercise 4.3

Prove that *Algorithm 4.4* works, i.e., that if
and for all
, then is a generator of .

Exercise 4.4

Let be an odd prime and an integer, and prove that

Use the first part to show that solving the discrete log problem in is “not much harder” than solving the discrete log problem in .

Exercise 4.5

Suppose is a nontrivial Dirichlet character of modulus of order over the complex numbers . Prove that the conductor of is

Exercise 4.6

- Find an irreducible quadratic polynomial over .
- Then . Find an element with multiplicative order in .
- Make a list of all Dirichlet characters in .
- Divide these characters into orbits for the action of .