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