Dirichlet Characters

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:

  1. To compute the Eisenstein subspace \Eis_k(\Gamma_1(N)) of M_k(\Gamma_1(N)), we write down Eisenstein series attached to pairs of Dirichlet characters (the space \Eis_k(\Gamma_1(N)) will be defined in Chapter Eisenstein Series and Bernoulli Numbers).

  2. To compute S_k(\Gamma_1(N)), we instead compute a decomposition

    M_k(\Gamma_1(N)) = \bigoplus M_k(\Gamma_1(N), \eps)

    and then compute each factor (see Section Dirichlet Character Decomposition). Here the sum is over all Dirichlet characters \eps of modulus N.

Dirichlet characters appear frequently in many other areas of number theory. For example, by the Kronecker-Weber theorem, Dirichlet characters correspond to the 1-dimensional representations of \Gal(\Qbar/\Q).

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.

The Definition

Fix an integral domain R and a root \zeta of unity in R.

Definition 4.1

A Dirichlet character of modulus N over R is a map \eps:\Z\to R such that there is a homomorphism f:(\Z/N\Z)^* \to
\langle \zeta \rangle for which

\eps(a) = \begin{cases}
0 &\text{if }\gcd(a,N)>1,\\
f\,(a\!\!\!\!\mod{N}) &\text{if }\gcd(a,N)=1.

We denote the group of such Dirichlet characters by D(N,R). Note that elements of D(N,R) are in bijection with homomorphisms (\Z/N\Z)^* \to \langle \zeta \rangle.

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

Representing Dirichlet Characters

Lemma 4.2

The groups (\Z/N\Z)^* and D(N,\C) are isomorphic.


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

Corollary 4.3

We have \#D(N,R) \mid \vphi(N), with equality if and only if the order of our choice of \zeta\in R is a multiple of the exponent of the group (\Z/N\Z)^*.


This is because \#(\Z/N\Z)^* = \vphi(N).

Fix a positive integer N. To find the set of “canonical” generators for the group (Z/NZ)^*, write N=\prod_{i=0}^{n}
{p_i^{e_i}} where p_0<p_1<\cdots < p_n are the prime divisors of N. By Exercise 4.2, each factor (\Z/p_i^{e_i}\Z)^* is a cyclic group C_i=\langle g_i \rangle, except if p_0=2 and e_0\geq 3, in which case (\Z/p_0^{e_0}\Z)^* is a product of the cyclic subgroup C_0 = \langle -1 \rangle of order 2 with the cyclic subgroup C_1 = \langle 5\rangle. In all cases we have

(\Z/N\Z)^* \isom \prod_{0\leq i\leq n} C_i =
\prod_{0\leq i \leq n} \langle g_i \rangle.

For i such that p_i>2, choose the generator g_i of C_i to be the element of \{2,3,\ldots, p_i^{e_i}-1\} that is smallest and generates. Finally, use the Chinese Remainder Theorem (see [Coh93, Section 1.3.3]) to lift each g_i to an element in (\Z/N\Z)^*, also denoted g_i, that is 1 modulo each p_j^{e_j} for j\neq i.

Algorithm 4.4

Given a prime power p^r with p odd, this algorithm computes the minimal generator of (\Z/p^r\Z)^*.

  1. [Factor Group Order] Factor n=\phi(p^r) = p^{r-1}\cdot 2\cdot
((p-1)/2) as a product \prod p_i^{e_i} of primes. This is equivalent in difficulty to factoring (p-1)/2. (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.)
  2. [Initialize] Set g\set 2.
  3. [Generator?] Using the binary powering algorithm (see [Coh93, Section 1.2]), compute g^{n/p_i}\pmod{p^r}, for each prime divisor p_i of n. If any of these powers are 1, then g is not a generator, so set g\set g+1 and go to step (2). If no powers are 1, output g and terminate.

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

Example 4.5

A minimal generator for (\Z/49\Z)^* is 3. We have n=\vphi(49)=42=2\cdot 3\cdot 7 and

2^{n/2} \con 1, \qquad 2^{n/3} \con 18, \qquad 2^{n/7} \con 15 \pmod{49},

so 2 is not a generator for (\Z/49\Z)^*. (We see this just from 2^{n/2}\con 1\pmod{49}.) However 3 is a generator since

3^{n/2} \con 48, \qquad 3^{n/3} \con 30, \qquad 3^{n/7} \con 43 \pmod{49}.

Example 4.6

In this example we compute minimal generators for N=25, 100, and 200:

  1. The minimal generator for (\Z/25\Z)^* is 2.
  2. The minimal generators for (\Z/100\Z)^*, lifted to numbers modulo 100, are g_0=51 and g_1=77. Notice that g_0\con -1\pmod{4} and g_0\con 1\pmod{25} and that g_1\con 2\pmod{25} is the minimal generator modulo 25.
  3. The minimal generators for (\Z/200\Z)^*, lifted to numbers modulo 200, are g_0 = 151, g_1 = 101, and g_2=177. Note that g_0\con -1\pmod{4}, that g_1\con 5\pmod{8} and g_2\con 2\pmod{25}.

In Sage, the command Integers(N) creates \Z/N\Z.

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

The unit_gens command computes the minimal generators for (\Z/N\Z)^*, as defined above.

sage: R.unit_gens()
sage: Integers(25).unit_gens()
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 \zeta of finite multiplicative order in a ring R, and let D(N,R) denote the group of Dirichlet characters of modulus N over R, with image in \langle \zeta\rangle \union \{0\}. In most of this chapter, we specify an element \eps\in D(N,R) by giving the list

(1)[\eps(g_0), \eps(g_1), \ldots, \eps(g_n)]

of images of the generators of (\Z/N\Z)^*. (Note that if N is even, the number of elements of the list (1) does depend on whether or not 8\mid N—there are two factors corresponding to 2 if 8\mid N, but only one if 8\nmid N.) This representation completely determines \eps 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 \eps(g_i) by recording an integer j such that \eps(g_i) = \zeta^j, where \zeta \in R is a fixed root of unity. Then (1) is internally represented as an element of (\Z/m\Z)^{n+1}, where m is the multiplicative order of \zeta. 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 \zeta. See Section Alternative Representations of Characters for further discussion about ways to represent characters.

Example 4.8

The group D(5,\C) has elements \{[1], [i], [-1], [-i]\}, so it is cyclic of order \vphi(5)=4. In contrast, the group D(5,\Q) has only the two elements [1] and [-1] and order 2.

The command : DirichletGroup(N) with no second argument creates the group of Dirichlet characters with values in the cyclotomic field \Q(\zeta_n), where n is the exponent of the group (\Z/N\Z)^*. Every element in D(N,\C) takes values in \Q(\zeta_n), so D(N,\Q(\zeta_n)) \ncisom D(N,\C).

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

Evaluation of Dirichlet Characters

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

Example 4.9

If N=200, then g_0=151, g_1=101 and g_2=177, as we saw in Example 4.6. The exponent of (\Z/200\Z)^* is 20, since that is the least common multiple of the exponents of 4=\#(\Z/8\Z)^* and 20=\#(\Z/25\Z)^*. The orders of g_0, g_1, and g_2 are 2, 2, and 20. Let \zeta=\zeta_{20} be a primitive 20^{th} root of unity in \C. Then the following are generators for D(200,\C):

\eps_0 = [-1,1,1],\qquad
\eps_1 = [1,-1,1],\qquad
\eps_2 = [1,1,\zeta],

and \eps=[1,-1,\zeta^5] is an example element of order 4. To evaluate \eps(3), we write 3 in terms of g_0, g_1, and g_2. First, reducing 3 modulo 8, we see that 3 \con g_0 \cdot g_1\pmod{8}. Next reducing 3 modulo 25 and trying powers of g_2=2, we find that e\con g_2^7\pmod{25}. Thus

\eps(3) &= \eps(g_0 \cdot g_1 \cdot g_2^7)\\
&= \eps(g_0) \eps(g_1) \eps(g_2)^7\\
&= 1 \cdot (-1) \cdot (\zeta^5)^7\\
&= -\zeta^{35} = -\zeta^{15}.

We next illustrate the above computation of \eps(3) in Sage. First we make the group D(200,\Q(\zeta_8)) 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()
sage: G.gens()
([-1, 1, 1], [1, -1, 1], [1, 1, zeta20])

We construct \eps.

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 \eps at 3.

sage: eps(3)
sage: -zeta^15

Example 4.9 illustrates that if \eps is represented using a list as described above, evaluation of \eps is inefficient without extra information; it requires solving the discrete log problem in (\Z/N\Z)^*.

Remark 4.10

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

Algorithm 4.11

Given a Dirichlet character \eps of modulus N, represented by a list [\eps(g_0), \eps(g_1), \ldots, \eps(g_n)], and an integer a, this algorithm computes \eps(a).

  1. [GCD] Compute g=\gcd(a,N). If g>1, output 0 and terminate.
  2. [Discrete Log] For each i, write a\pmod{p_i^{e_i}} as a power m_i of g_i using some algorithm for solving the discrete log problem (see below). If p_i=2, write a\pmod{p_i^{e_i}} as (-1)^{m_0}\cdot 5^{m_1}. (This step is analogous to writing a vector in terms of a basis.)
  3. [Multiply] Output \prod \eps(g_i)^{m_i} as an element of R, and terminate. (This is analogous to multiplying a matrix times a vector.)

The Discrete Log Problem

Exercise 4.4 gives an isomorphism of groups

(1+p^{n-1}(\Z/p^n\Z),\,\times) \isom (\Z/p\Z,\,+),

so one sees by induction that step (2) is “about as difficult” as finding a discrete log in (\Z/p\Z)^*. There is an algorithm called “baby-step giant-step”, which solves the discrete log problem in (\Z/p\Z)^* in time O(\sqrt{\ell}), where \ell is the largest prime factor of p-1=\#(\Z/p\Z)^* (note that the discrete log problem in (\Z/p\Z)^* 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 \ell; it also uses O(\sqrt{\ell}) memory. We now describe this algorithm without any specific optimizations.

Algorithm 4.12

Given a prime p, a generator g of (\Z/p\Z)^*, and an element a\in (\Z/p\Z)^*, this algorithm finds an n such that g^n=a. (Note that this algorithm works in any cyclic group, not just (\Z/p\Z)^*.)

  1. [Make Lists] Let m=\lceil{} \sqrt{p}\rceil{} be the ceiling of \sqrt{p}, and construct two lists

    1,\, g^m,\, \ldots, \,g^{(m-1)m}
\qquad\qquad\text{(giant steps)}


    a, ag,\, ag^2,\, \ldots, \,
ag^{m-1}\qquad\qquad\text{(baby steps)}.

  2. [Find Match] Sort the two lists and find a match g^{im} = a
g^j. Then a = g^{im-j}.


We prove that there will always be a match. Since we know that a=g^k for some k with 0\leq k\leq p-1 and any such k can be written in the form im-j for 0\leq i,j\leq m-1, we will find such a match.

Algorithm 4.12 uses nothing special about (\Z/p\Z)^*, 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 (\Z/p\Z)^*, 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 p is large is still extremely difficult. For a more in-depth survey see [Gor04]. For computing Dirichlet characters in our context, p is not too large, so Algorithm 4.12 works well.

Enumeration of All Values

For many applications of Dirichlet characters to computing modular forms, N is fairly small, e.g., N<10^6, and we evaluate \eps 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 \eps, so that evaluation of \eps is extremely fast. The following algorithm computes a table of all values of \eps, and it does not require computing any discrete logs since we are computing all values.

Algorithm 4.13

Given a Dirichlet character \eps represented by the list of values of \eps on the minimal generators g_i of (\Z/N\Z)^*, this algorithm creates a list of all the values of \eps.

  1. [Initialize] For each minimal generator g_i, set a_i\set 0. Let n = \prod g_i^{a_i}, and set z\set 1. Create a list v of N values, all initially set equal to 0. When this algorithm terminates, the list v will have the property that

\!\!\!\!\!\pmod{N}] = \eps(x).

    Notice that we index v starting at 0.

  2. [Add Value to Table] Set v[n] \set z.

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

  4. [Increment] Set a_0\set a_0 + 1, n\set n\cdot g_0\pmod{N}, and z\set z\cdot \eps(g_0). If a_0\geq \ord(g_0), set a_0\to 0, and then set a_1\set a_1 + 1, n\set n\cdot
g_1\pmod{N}, and z\set z\cdot \eps(g_1). If a_1\geq
\ord(g_1), do what you just did with a_0 but with all subscripts replaced by 1. Etc. (Imagine a car odometer.) Go to step (2).

Conductors of Dirichlet Characters

The following algorithm for computing the order of \eps reduces the problem to computing the orders of powers of \zeta in R.

Algorithm 4.14

This algorithm computes the order of a Dirichlet character \eps\in D(N,R).

  1. Compute the order r_i of each \eps(g_i), for each minimal generator g_i of (\Z/N\Z)^*. The order of \eps(g_i) is a divisor of n=\#(\Z/p_i^{e_i}\Z)^* so we can compute its order by considering the divisors of n.
  2. Compute and output the least common multiple of the integers r_i.

Remark 4.15

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

The next algorithm factors \eps as a product of “local” characters, one for each prime divisor of N. 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 \eps.

Algorithm 4.16

Given a Dirichlet character \eps\in D(N,R), with N=\prod p_i^{e_i}, this algorithm finds Dirichlet characters \eps_i modulo p_i^{e_i}, such that for all a\in(\Z/N\Z)^*, we have \eps(a) = \prod \eps_i(a\!\!\pmod{p_i^{e_i}}). If 2\mid N, the steps are as follows:

  1. Let g_i be the minimal generators of (\Z/N\Z)^*, so \eps is given by a list

    [\eps(g_0),\ldots, \eps(g_n)].

  2. For i=2,\ldots, n, let \eps_i be the element of D(p_i^{e_i},R) defined by the singleton list [\eps(g_i)].

  3. Let \eps_1 be the element of D(2^{e_1},R) defined by the list [\eps(g_0), \eps(g_1)] of length 2. Output the \eps_i and terminate.

If 2\nmid N, then omit step (3), and include all i in step (2).

The factorization of Algorithm 4.16 is unique since each \eps_i is determined by the image of the canonical map (\Z/p_i^{e_i}\Z)^* in (\Z/N\Z)^*, which sends a\pmod{p_i^{e_i}} to the element of (\Z/N\Z)^* that is a\pmod{p_i^{e_i}} and 1 \pmod{p_j^{e_j}} for j\neq i.

Example 4.17

If \eps = [1,-1,\zeta^5] \in D(200,\C), then \eps_1 = [1,-1]\in D(8,\C) and \eps_2 = [\zeta^5]\in D(25,\C).

Definition 4.18

The conductor of a Dirichlet character \eps\in D(N,R) is the smallest positive divisor c\mid N such that there is a character \eps' \in D(c,R) for which \eps(a) = \eps'(a) for all a\in\Z with (a,N)=1. A Dirichlet character is primitive if its modulus equals its conductor. The character \eps' associated to \eps with modulus equal to the conductor of \eps is called the primitive character associated to \eps.

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 L functions are only valid for primitive characters.

Algorithm 4.19

This algorithm computes the conductor of a Dirichlet character \eps \in D(N,R).

  1. [Factor Character] Using Algorithm 4.16, find characters \eps_i whose product is \eps.
  2. [Compute Orders] Using Algorithm 4.14, compute the orders r_i of each \eps_i.
  3. [Conductors of Factors] For each i, either set c_i\to 1 if \eps_i is the trivial character (i.e., of order 1) or set c_i \set p_i^{\ord_{p_i}(r_i)+1}, where \ord_{p}(n) is the largest power of p that divides n.
  4. [Adjust at 2?] If p_1=2 and \eps_1(5)\neq 1, set c_1\set 2c_1.
  5. [Finished] Output c = \prod c_i and terminate.


Let \eps_i be the local factors of \eps, as in step (1)). We first show that the product of the conductors f_i of the \eps_i is the conductor f of \eps. Since \eps_i factors through (\Z/f_i\Z)^*, the product \eps of the \eps_i factors through (\Z/\prod f_i\Z)^*, so the conductor of \eps divides \prod f_i. Conversely, if \ord_{p_i}(f) < \ord_{p_i}(f_i) for some i, then we could factor \eps as a product of local (prime power) characters differently, which contradicts that this factorization is unique.

It remains to prove that if \eps is a nontrivial character of modulus p^n, where p is a prime, and if r is the order of \eps, then the conductor of \eps is p^{\ord_p(r)+1}, except possibly if 8\mid
p^n. Since the order and conductor of \eps and of the associated primitive character \eps' are the same, we may assume \eps is primitive, i.e., that p^n is the conductor of \eps; note that n>0, since \eps is nontrivial.

First suppose p is odd. Then the abelian group D(p^n,R) splits as a direct sum D(p,R)\oplus D(p^n,R)', where D(p^n,R)' is the p-power torsion subgroup of D(p^n,R). Also \eps has order u\cdot p^m, where u, which is coprime to p, is the order of the image of \eps in D(p,R) and p^m is the order of the image in D(p^n,R)'. If m=0, then the order of \eps is coprime to p, so \eps is in D(p,R), which means that n=1, so n=m+1, as required. If m>0, then \zeta\in R must have order divisible by p, so R has characteristic not equal to p. The conductor of \eps does not change if we adjoin roots of unity to R, so in light of Lemma 4.2 we may assume that D(N,R) \ncisom (\Z/N\Z)^*. It follows that for each n'\leq n, the p-power subgroup D(p^{n'},R)' of D(p^{n'},R) is the p^{n'-1}-torsion subgroup of D(p^n,R)'. Thus m=n-1, since D(p^n,R)' is by assumption the smallest such group that contains the projection of \eps. This proves the formula of step ((3). We leave the argument when p=2 as an exercise (see Exercise 4.5).

Example 4.20

If \eps = [1,-1,\zeta^5] \in D(200,\C), then as in Example 4.17, \eps is the product of \eps_1=[1,-1] and \eps_2 = [\zeta^5]. Because \eps_1(5)=-1, the conductor of \eps_1 is 8. The order of \eps_2 is 4 (since \zeta is a 20^{th} root of unity), so the conductor of \eps_2 is 5. Thus the conductor of \eps is 40=8\cdot 5.

The Kronecker Symbol

In this section all characters have values in \C.

Frequently quadratic characters are described in terms of the Kronecker symbol \kr{a}{n}, which we define for any integer a and positive integer n as follows. First, if n=p is an odd prime, then for any integer a,

= \begin{cases} \hfill 0 & \text{if $\gcd(a,p)\neq 1$,}\\
\hfill  1 & \text{if $a$ is a square mod $p$,}\\
-1 & \text{if $a$ is not a square mod $p$.}

If p=2, then

\kr{a}{2} =
\begin{cases} \hfill 0 & \text{if $a$ is even,}\\
\hfill 1 & \text{if $a \con \pm 1\pmod{8}$,}\\
-1 & \text{if $a \con \pm 3\pmod{8}$.}

More generally, if n=\prod p_i^{e_i} with the p_i prime, then

\kr{a}{n} = \prod \kr{a}{p_i}^{e_i}.

Remark 4.21

One can also extend \kr{a}{n} to n<0, but we will not need this. The extension is to set \kr{a}{-1} = -1 and \kr{a}{1} = 1, for a\neq 0, and to extend multiplicatively (in the denominator). Note that the map \kr{\bullet}{-1} is not a Dirichlet character (see Exercise 4.1).

Let M be the product of the primes p such that \ord_p(n) is odd. If M is odd, let N=M; otherwise, let N=8M.

Lemma 4.22

The function

\eps(a) = \begin{cases}
\kr{a}{n} & \text{if $\gcd(a,N)=1$,}\\
\hfill 0\hfill          & \text{otherwise}

is a Dirichlet character of modulus N. The function

\eps(a) = \begin{cases}
\kr{-1}{a} &\text{if `a` is odd,}\\
\hfill 0 \hfill & \text{if `a` is even}

is a Dirichlet character of modulus N.


When restricted to (\Z/N\Z)^*, each map \kr{\bullet}{p}, for p prime, is a homomorphism, so \eps a product of homomorphisms. The second statement follows from the definition and the fact that -1 is a square modulo an odd prime p if and only if p\con 1\pmod{4}.

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 \kr{a}{p} \con a^{(p-1)/2}\pmod{p}, when p is an odd prime.

Algorithm 4.23

Given n>0, this algorithm computes a representation of the Kronecker symbol \kr{\bullet}{n} as a Dirichlet character.

  1. [Modulus] Compute N as in Lemma 4.22.
  2. [Minimal Generators] Compute minimal generators g_i of (\Z/N\Z)^* using Algorithm 4.4.
  3. [Images] Compute \kr{g_i}{N} for each g_i using one of the algorithms of [Coh93, Section 1.1.4].

Example 4.24

We compute the Dirichlet character associated to \kr{\bullet}{200}. Using Sage, we compute the \kr{g_i}{200}, for i=0,1,2, where the g_i are as in Example 4.9:

sage: kronecker(151,200)
sage: kronecker(101,200)
sage: kronecker(177,200)

Thus the corresponding character is defined by [1,-1,1].

Example 4.25

We compute the character associated to \kr{\bullet}{420}. We have 420=4\cdot 3\cdot 5\cdot 7, and minimal generators are

g_0 = 211,\quad g_1=1, \quad g_2 = 281, \quad g_3=337, \quad g_4=241.

We have g_0\con -1\pmod{4}, g_2\con 2\pmod{3}, g_3\con 2\pmod{5} and g_4\con 3\pmod{7}. We find \kr{g_0}{420}=\kr{g_1}{420}=1 and \kr{g_2}{420}=\kr{g_3}{420}=\kr{g_4}{420}=-1. The corresponding character is [1,1,-1,-1,-1].

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 \eps of order 2 with modulus N, this algorithm writes \eps as a Kronecker symbol.

  1. [Conductor] Use Algorithm 4.19 to compute the conductor f of \eps.
  2. [Odd] If f is odd, output \kr{\bullet}{f}.
  3. [Even] If \eps(-1)=1, output \kr{\bullet}{f}; if \eps(-1)=-1, output \kr{\bullet}{f} \cdot \kr{-1}{\bullet}.


Since f is the conductor of a quadratic Dirichlet character, it is a square-free product g of odd primes times either 4 or 8, so the group (\Z/f\Z)^* does not inject into (\Z/g\Z)^* for any proper divisor g of f (see this by reducing to the prime power case). Since g is odd and square-free, the character \kr{\bullet }{g} has conductor g. For each odd prime p, by step (3) of Algorithm 4.19 the factor at p of both \eps and \kr{\bullet}{g} is a quadratic character with modulus p. By Exercise 4.2 and Lemma 4.2 the group D(p,\C) is cyclic, so it has a unique element of order 2, so the factors of \eps and \kr{\bullet}{g} at p are equal.

The quadratic characters with conductor a power of 2 are [-1], [1,-1], and [-1,-1]. The character [1,-1] is \kr{\bullet}{2} and the character [-1] is \kr{-1}{\bullet}.

Example 4.27

Consider \eps=[-1,-1,-1,-1,-1] with modulus 840=8\cdot 3\cdot 5\cdot 7. It has conductor 840, and \eps(-1)=-1, so for all a with \gcd(a,840)=1, we have \eps(a) = \kr{a}{840}\cdot \kr{-1}{a}.

Restriction, Extension, and Galois Orbits

The following two algorithms restrict and extend characters to a compatible modulus. Using them, it is easy to define multiplication of two characters \eps\in D(N,R) and \eps'\in D(N',R'), as long as R and R' 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 \lcm(N,N') and multiply.

Algorithm 4.28

Given a Dirichlet character \eps\in D(N,R) and a divisor N' of N that is a multiple of the conductor of \eps, this algorithm finds a characters \eps' \in D(N',R), such that \eps'(a) = \eps(a), for all a\in\Z with (a,N)=1.

  1. [Conductor] Compute the conductor of \eps using Algorithm 4.19, and verify that N' is divisible by the conductor and divides N.
  2. [Minimal Generators] Compute minimal generators g_i for (\Z/N'\Z)^*.
  3. [Values of Restriction] For each i, compute \eps'(g_i) as follows. Find a multiple aN' of N' such that (g_i+aN',\,N)=1; then \eps'(g_i) = \eps(g_i+aN').
  4. [Output Character] Output the Dirichlet character of modulus N' defined by [\eps'(g_0),\ldots, \eps'(g_n)].


The only part that is not clear is that in step (3) there is an a such that (g_i+aN', N)=1. If we write N=N_1\cdot N_2, with (N_1,N_2)=1 and N_1 divisible by all primes that divide N', then (g_i,N_1)=1 since (g_i,N')=1. By the Chinese Remainder Theorem, there is an x\in\Z such that x\con g_i\pmod{N_1} and x\con 1\pmod{N_2}. Then x = g_i + b N_1 = g_i + (bN_1/N')\cdot N' and (x,N)=1, which completes the proof.

Algorithm 4.29

Given a Dirichlet character \eps\in D(N,R) and a multiple N' of N, this algorithm finds a character \eps' \in D(N',R), such that \eps'(a) = \eps(a), for all a\in\Z with (a,N')=1.

  1. Minimal Generators] Compute minimal generators g_i for (\Z/N'\Z)^*.
  2. [Evaluate] Compute \eps(g_i) for each i. Since (g_i,N')=1, we also have (g_i,N)=1.
  3. [Output Character] Output the character [\eps(g_0),\ldots, \eps(g_n)].

Let F be the prime subfield of R, and assume that R\subset \overline{F}, where \overline{F} is a separable closure of F. If \sigma \in \Gal(\overline{F}/F) and \eps \in D(N,R), let (\sigma\eps)(n) = \sigma(\eps(n)); this defines an action of \Gal(\overline{F}/F) on D(N,R). Our next algorithm computes the orbits for the action of \Gal(\overline{F}/F) on D(N,R). This algorithm can provide huge savings for modular forms computations because the spaces M_k(N,\eps) and M_k(N,\eps') are canonically isomorphic if \eps and \eps' are conjugate.

Algorithm 4.30

Given a Dirichlet character \eps\in D(N,R), this algorithm computes the orbit of \eps under the action of G=\Gal(\overline{F}/F), where F is the prime subfield of \Frac(R), so F=\Fp or \Q.

  1. [Order of \zeta] Let n be the order of the chosen root \zeta\in R.

  2. [Nontrivial Automorphisms] If \Char(R)=0, let

    A = \{a : 2\leq a <n \text{ and }(a,n) = 1\}.

    If \Char(R)=p>0, compute the multiplicative order r of p\!\!\pmod{n}, and let

    A = \{p^m : 1\leq m < r\}.

  3. [Compute Orbit] Compute and output the set of unique elements \eps^a for each a\in A (there could be repeats, so we output unique elements only).


We prove that the nontrivial automorphisms of \langle \zeta\rangle in characteristic p are as in step (2). It is well known that every automorphism in characteristic p on \zeta\in\Fpbar is of the form x\mapsto x^{p^s}, for some s. The images of \zeta under such automorphisms are

\zeta, \zeta^p, \zeta^{p^2}, \ldots.

Suppose r>0 is minimal such that \zeta=\zeta^{p^r}. Then the orbit of \zeta is \zeta,\ldots, \zeta^{p^{r-1}}. Also p^r\con 1\pmod{n}, where n is the multiplicative order of \zeta, so r is the multiplicative order of p modulo n, which completes the proof.

Example 4.31

The Galois orbits of characters in D(20,\C^*) are as follows:

G_0 &= \{ [1,1,1]\},\\
G_1 &= \{[-1,1,1]\}, \\
G_2 &= \{[1,1,\zeta_4],\,\, [1,1,-\zeta_4]\}\\
G_3 &= \{[-1,1,\zeta_4],\,\, [-1,1,-\zeta_4]\}\\
G_4 &= \{[1,1,-1]\}, \\
G_5 &= \{[-1,1,-1]\}.

The conductors of the characters in orbit G_0 are 1, in orbit G_1 they are 4, in orbit G_2 they are 5, in G_3 they are 20, in G_4 the conductor is 5, and in G_5 the conductor is 20. (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]]

Alternative Representations of Characters

Let N be a positive integer and R an integral domain, with fixed root of unity \zeta of order n, and let D(N,R)=D(N,R,\zeta). As in the rest of this chapter, write N=\prod p_i^{e_i}, and let C_i=\langle g_i\rangle be the corresponding cyclic factors of (\Z/N\Z)^*. In this section we discuss other ways to represent elements \eps \in D(N,R). 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 \eps by giving a list [b_0,\ldots, b_r], where each b_i\in\Z/n\Z and \eps(g_i) = \zeta^{b_i}. Then arithmetic in D(N,R) is arithmetic in (\Z/n\Z)^{r+1}, 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 D(N,R). Also the choice of \zeta is less clear, which can cause confusion. Finally, the orders of the local factors is more opaque, e.g., compare [-1,\zeta_{40}] with [20,1]. 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 D(N,R) is very efficient and does not require any operations in the ring R.

Another way to represent \eps would be to give a list [b_0,\ldots,
b_r] of integers, but this time with b_i\in \Z/\gcd(s_i,n)\Z, where s_i is the order of g_i. Then

\eps(g_i) = \zeta^{b_i \cdot

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

D(N,R)\isom \bigoplus_i \Z/\gcd(s_i,n)\Z,

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 \zeta, so it is difficult to correctly compute natural maps D(N,R) \to
D(N,S), for R\subset S rings.

Dirichlet Characters in Sage

To create a Dirichlet character in Sage, first create the group D(N,R) of Dirichlet characters then construct elements of that group. First we make D(11,\Q):

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 (\Z/N\Z)^* (as discussed below).

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

The character \varepsilon takes the value -1 on the unit generator.

sage: G.unit_gens()
sage: eps(2)
sage: eps(3)

It is 0 on any integer not coprime to 11:

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 \Q(\zeta_4).

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

Then we define G = D(15,\Q({\zeta_4})).

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 G on various integers:

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

Finally we list all the values of e.

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 G, again represented by lists that give the images of each unit generator, as an element of \F_5.

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 G on several integers.

sage: e = G.1
sage: e(-1)
sage: e(2)
sage: e(5)
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 f:\Z\to\C be the map given by

f(a) = \begin{cases} \hfill 0 & \text{if }a=0,\\
-1 & \text{if } a <0,\\
\hfill 1  &\text{if } a > 0.

Prove that f is not a Dirichlet character of any modulus N.

Exercise 4.2

This exercise is about the structure of the units of \Z/p^n\Z.

  1. If p is odd and n is a positive integer, prove that (\Z/p^n\Z)^* is cyclic.
  2. For n\geq 3, prove that (\Z/2^n\Z)^* is a direct sum of the cyclic subgroups \langle -1 \rangle and \langle 5 \rangle, of orders 2 and 2^{n-2}, respectively.

Exercise 4.3

Prove that Algorithm 4.4 works, i.e., that if g\in(\Z/p^r\Z)^* and g^{n/p_i}\neq 1 for all p_i\mid n=\vphi(p^r), then g is a generator of (\Z/p^r\Z)^*.

Exercise 4.4

  1. Let p be an odd prime and n\geq 2 an integer, and prove that

    \bigl((1+p^{n-1}\Z/p^n\Z),\,\times\bigr) \isom (\Z/p\Z,\,+).

  2. Use the first part to show that solving the discrete log problem in (\Z/p^n\Z)^* is “not much harder” than solving the discrete log problem in (\Z/p\Z)^*.

Exercise 4.5

Suppose \eps is a nontrivial Dirichlet character of modulus 2^n of order r over the complex numbers \C. Prove that the conductor of \eps is

c = \begin{cases}
2^{\ord_2(r) + 1} & \text{if $\eps(5)=1$},\\
2^{\ord_2(r) + 2} & \text{if $\eps(5)\neq 1$.}

Exercise 4.6

  1. Find an irreducible quadratic polynomial f over \F_5.
  2. Then \F_{25} = \F_5[x]/(f). Find an element with multiplicative order 4 in \F_{25}.
  3. Make a list of all Dirichlet characters in D(25,\F_{25},\zeta).
  4. Divide these characters into orbits for the action of \Gal(\Fbar_5/\F_5).