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:

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).
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. \end{cases}$

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.

Proof

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)^*$ .

Proof

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)^*$ .

[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.)
[Initialize] Set $g\set 2$ .
[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$ :

The minimal generator for $(\Z/25\Z)^*$ is $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$ .
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()
[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 $\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()
20
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)
zeta20^5
sage: -zeta^15
zeta20^5

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

[GCD] Compute $g=\gcd(a,N)$ . If $g>1$ , output $0$ and terminate.
[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.)
[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)^*$ .)

[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)}$
and

$a, ag,\, ag^2,\, \ldots, \, ag^{m-1}\qquad\qquad\text{(baby steps)}.$
[Find Match] Sort the two lists and find a match $g^{im} = a g^j$ . Then $a = g^{im-j}$ .

Proof

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

[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

$v\,\,[x \!\!\!\!\!\pmod{N}] = \eps(x).$
Notice that we index $v$ starting at $0$ .
[Add Value to Table] Set $v[n] \set z$ .
[Finished?] If each $a_i$ is one less than the order of $g_i$ , output $v$ and terminate.
[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)$ .

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

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

[Factor Character] Using Algorithm 4.16, find characters $\eps_i$ whose product is $\eps$ .
[Compute Orders] Using Algorithm 4.14, compute the orders $r_i$ of each $\eps_i$ .
[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$ .
[Adjust at $2$ ?] If $p_1=2$ and $\eps_1(5)\neq 1$ , set $c_1\set 2c_1$ .
[Finished] Output $c = \prod c_i$ and terminate.

Proof

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$ ,

$\kr{a}{p} = \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$.} \end{cases}$

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}$.} \end{cases}$

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} \end{cases}$

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} \end{cases}$

is a Dirichlet character of modulus $N$ .

Proof

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.

[Modulus] Compute $N$ as in Lemma 4.22.
[Minimal Generators] Compute minimal generators $g_i$ of $(\Z/N\Z)^*$ using Algorithm 4.4.
[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)
1
sage: kronecker(101,200)
-1
sage: kronecker(177,200)
1

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.

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

Proof

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

[Conductor] Compute the conductor of $\eps$ using Algorithm 4.19, and verify that $N'$ is divisible by the conductor and divides $N$ .
[Minimal Generators] Compute minimal generators $g_i$ for $(\Z/N'\Z)^*$ .
[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')$ .
[Output Character] Output the Dirichlet character of modulus $N'$ defined by $[\eps'(g_0),\ldots, \eps'(g_n)]$ .

Proof

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

Minimal Generators] Compute minimal generators $g_i$ for $(\Z/N'\Z)^*$ .
[Evaluate] Compute $\eps(g_i)$ for each $i$ . Since $(g_i,N')=1$ , we also have $(g_i,N)=1$ .
[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$ .

[Order of $\zeta$ ] Let $n$ be the order of the chosen root $\zeta\in R$ .
[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\}.$
[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).

Proof

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 n/(\gcd(s_i,n))},$

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

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

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

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)
-1
sage: e(-1)
-1
sage: e(5)
0

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)
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 $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. \end{cases}$

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

If $p$ is odd and $n$ is a positive integer, prove that $(\Z/p^n\Z)^*$ is cyclic.
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

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,\,+).$
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$.} \end{cases}$

Exercise 4.6

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

Dirichlet Characters¶

The Definition¶

Representing Dirichlet Characters¶

Evaluation of Dirichlet Characters¶

The Discrete Log Problem¶

Enumeration of All Values¶

Conductors of Dirichlet Characters¶

The Kronecker Symbol¶

Restriction, Extension, and Galois Orbits¶

Alternative Representations of Characters¶

Dirichlet Characters in Sage¶

Exercises¶

Table Of Contents

Previous topic

Next topic

This Page

Quick search

Purchase a hardcopy of this book from the AMS

Navigation

Dirichlet Characters¶

The Definition¶

Representing Dirichlet Characters¶

Evaluation of Dirichlet Characters¶

The Discrete Log Problem¶

Enumeration of All Values¶

Conductors of Dirichlet Characters¶

The Kronecker Symbol¶

Restriction, Extension, and Galois Orbits¶

Alternative Representations of Characters¶

Dirichlet Characters in Sage¶

Exercises¶

Table Of Contents

Previous topic

Next topic

This Page

Quick search

Purchase a hardcopy of this book from the AMS

Navigation