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 of , we write down Eisenstein series attached to pairs of Dirichlet characters (the space will be defined in Chapter Eisenstein Series and Bernoulli Numbers).

2. 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.

The Definition¶

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 .

Representing Dirichlet Characters¶

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 .

1. [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.)
2. [Initialize] Set .
3. [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 :

1. The minimal generator for is .
2. The minimal generators for , lifted to numbers modulo , are and . Notice that and and that is the minimal generator modulo .
3. 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]]


Evaluation of Dirichlet Characters¶

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 .

1. [GCD] Compute . If , output and terminate.
2. [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.)
3. [Multiply] Output as an element of , and terminate. (This is analogous to multiplying a matrix times a vector.)

The Discrete Log Problem¶

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 .)

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

and

2. [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.

Enumeration of All Values¶

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 .

1. [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 .

2. [Add Value to Table] Set .

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

4. [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).

Conductors of Dirichlet Characters¶

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 .

1. 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 .
2. 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:

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

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

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

If , then omit step (3), and include all in step (2).

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 .

1. [Factor Character] Using Algorithm 4.16, find characters whose product is .
2. [Compute Orders] Using Algorithm 4.14, compute the orders of each .
3. [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 .
4. [Adjust at ?] If and , set .
5. [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 .

The Kronecker Symbol¶

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.

1. [Modulus] Compute as in Lemma 4.22.
2. [Minimal Generators] Compute minimal generators of using Algorithm 4.4.
3. [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.

1. [Conductor] Use Algorithm 4.19 to compute the conductor of .
2. [Odd] If is odd, output .
3. [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 .

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 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 .

1. [Conductor] Compute the conductor of using Algorithm 4.19, and verify that is divisible by the conductor and divides .
2. [Minimal Generators] Compute minimal generators for .
3. [Values of Restriction] For each , compute as follows. Find a multiple of such that ; then .
4. [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 .

1. Minimal Generators] Compute minimal generators for .
2. [Evaluate] Compute for each . Since , we also have .
3. [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 .

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

2. [Nontrivial Automorphisms] If , let

If , compute the multiplicative order of , and let

3. [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]]
]


Alternative Representations of Characters¶

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.

Dirichlet Characters in Sage¶

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]


Exercises¶

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 .

1. If is odd and is a positive integer, prove that is cyclic.
2. 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

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

2. 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

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

Previous topic

Modular Forms of Weight 2

Next topic

Eisenstein Series and Bernoulli Numbers