Dirichlet characters

A Dirichlet character modulo q is a group homomorphism \chi : (\mathbb{Z}/q\mathbb{Z})^\times \to \mathbb{C}^\times, extended to \mathbb{Z} by periodicity and by \chi(n) = 0 for \gcd(n, q) > 1. For the theory see [Apo1976, Chapter 6] and [IR1990, Chapter 4]; the numbering is that of Conrey, used by the LMFDB [LMFDB].

The unit group#

By the Chinese remainder theorem (\mathbb{Z}/q\mathbb{Z})^\times \cong \prod_{p^e \| q} (\mathbb{Z}/p^e\mathbb{Z})^\times, and the factors have the following structure [IR1990, Theorem 2 of Chapter 4].

Theorem 1. For an odd prime p, (\mathbb{Z}/p^e\mathbb{Z})^\times is cyclic of order p^{e-1}(p - 1), and an integer g generates it for every e \ge 1 if and only if g generates (\mathbb{Z}/p^2\mathbb{Z})^\times. For e \ge 3, (\mathbb{Z}/2^e\mathbb{Z})^\times is the direct product of the subgroup \{\pm 1\} and the cyclic subgroup of order 2^{e-2} generated by 5; (\mathbb{Z}/4\mathbb{Z})^\times = \{\pm 1\} and (\mathbb{Z}/2\mathbb{Z})^\times is trivial.

The Conrey generators are: for odd p, the smallest positive integer that is a primitive root modulo p^2; for 8 \mid q, the two generators -1 and 5 of the 2-part; for 4 \| q, the generator -1. For all primes up to 10^{16} except p = 40487 and p = 6692367337, the smallest primitive root modulo p is also a primitive root modulo p^2, so FLINT computes it with n_primitive_root_prime and treats the two exceptions separately (the generators are 10 and 7); larger prime factors are not supported. Each generator g_k of order \varphi_k is lifted to \tilde g_k \equiv g_k \pmod{p^e}, \tilde g_k \equiv 1 \pmod{q/p^e}, so that every m \in (\mathbb{Z}/q\mathbb{Z})^\times is uniquely

m = \prod_k \tilde g_k^{\,a_k}, \qquad 0 \le a_k < \varphi_k.

The vector (a_k) is the log of m. The exponent of the group is e = \operatorname{lcm}_k \varphi_k.

Characters and the Conrey pairing#

A character is determined by its values on the generators, which are \varphi_k-th roots of unity. Conrey's choice is

\chi_q(m, n) = \exp\left(2 \pi i \sum_k \frac{a_k b_k}{\varphi_k}\right)

for m, n with logs (a_k) and (b_k). This is a nondegenerate symmetric bilinear pairing on (\mathbb{Z}/q\mathbb{Z})^\times, so m \mapsto \chi_q(m, \cdot) is an isomorphism from the group onto its dual. As a consequence, the character group operations are those of the numbers (\chi_q(m, \cdot)\chi_q(m', \cdot) = \chi_q(mm', \cdot)), the order of \chi_q(m, \cdot) is the multiplicative order of m, and by symmetry \chi_q(m, -1) = \chi_q(-1, m). Values are exact roots of unity \zeta_e^v with v = \sum_k a_k b_k (e/\varphi_k) \bmod e, which the module returns as the exponent v.

Conductor, parity and primitivity#

A character modulo q is induced by a character modulo f \mid q if it is the composition with the reduction (\mathbb{Z}/q\mathbb{Z})^\times \to (\mathbb{Z}/f\mathbb{Z})^\times. The conductor is the smallest such f, and \chi is primitive if its conductor is q.

Proposition 2. The conductor of \chi_q(m, \cdot) is the product over the components of the following factors. For an odd p^e \| q with log entry a: 1 if a = 0, and p^{e - v_p(a)} otherwise. For the 2-part: 1 if both log entries are zero; 4 if only the entry of -1 is nonzero; 2^{e - v_2(a)} if the entry a of 5 is nonzero.

Proof. The character is induced modulo f if and only if it is trivial on the kernel of the reduction modulo f, which is a product over the components. For a cyclic component generated by g of order \varphi = \varphi(p^e), the kernel of the reduction to p^f is generated by g^{\varphi(p^f)}, and \chi(g^{\varphi(p^f)}) = \exp(2\pi i\, a \varphi(p^f)/\varphi(p^e)) is 1 if and only if p^{e-f} \mid a. The smallest such f is e - v_p(a). The 2-part is analogous, with the kernel of the reduction from 2^e to 2^f, f \ge 3, generated by 5^{2^{f-2}}, and to 4 by 5.

From the number m instead of the log, the p-part of the conductor is p^{1 + t}, where t \ge 0 is the least integer with m^{(p-1)p^t} \equiv 1 \pmod{p^e} (and 1 if m \equiv 1 \pmod {p^e}), since the order of m in the component determines v_p(a). The parity follows from the symmetry of the pairing:

Proposition 3. \chi_q(m, -1) = \epsilon \cdot \left(\frac{m}{q'}\right), where q' is the product of the distinct odd primes dividing q, (\cdot/\cdot) is the Jacobi symbol, and \epsilon = -1 if 4 \mid q and m \equiv 3 \pmod 4, otherwise \epsilon = 1.

Proof. \chi_q(m, -1) = \chi_q(-1, m). In an odd component, -1 = g^{\varphi/2} has log entry \varphi/2, contributing \exp(\pi i b) = (-1)^b where b is the log entry of m; b is even exactly when m is a square modulo p, so the contribution is the Legendre symbol (m/p). In the 2-part, -1 has entry 1 on the generator -1 and 0 on 5, contributing (-1)^{a_0} with a_0 = 1 exactly when m \equiv 3 \pmod 4.

Counting the logs that give conductor q in each component, the number of primitive characters is multiplicative: p - 2 for p \| q, (p - 1)^2 p^{e-2} for p^e \| q with e \ge 2, and for the 2-part 0, 1 and 2^{e-2} for 2 \| q, 4 \| q and 2^e \| q with e \ge 3.

Computing values#

The value \chi_q(m, n) requires the log of n, hence a discrete logarithm in each odd component; the 2-part needs only n \bmod 4 and a 2-adic logarithm. These are computed with the dlog module (Discrete logarithm tables): a single logarithm with dlog_once, or with tables precomputed for many calls.

For the vector of values \chi(0), \ldots, \chi(N-1) there are two strategies.

Loop over the group. Enumerating the logs in lexicographic order (dirichlet_char_next), each step multiplies the number by one generator and adds a constant to the value exponent, so all \varphi(q) values cost O(\varphi(q)) operations without any discrete logarithm. This is best when N is comparable with q.
Sieve. Since \chi is completely multiplicative, it suffices to know \chi(p) for the primes p < N; dlog_vec_add computes the discrete logarithms of the small primes directly and obtains those of the larger primes cheaply from relations found by a partial extended Euclidean algorithm, then fills in all k < N by multiplicativity. Each odd component contributes its part of the exponent, and the 2-part is added directly. This is best for N much smaller than q.

Use in FLINT#

dirichlet_group_init factors q and computes the Conrey generators and their lifts; dirichlet_group_dlog_precompute builds dlog_precomp_modpe_init tables for each component.
dirichlet_char_log computes the log of a number with dlog_once, dlog_mod2e_1mod4 or the precomputed tables; _dirichlet_char_exp goes back with modular powers.
dirichlet_conductor_char, dirichlet_parity_char and dirichlet_order_char use the log (Proposition 2); the _ui versions use the number, with modular powers, a Jacobi symbol (Proposition 3) and the factorisation of the group exponent.
dirichlet_chi_vec uses the loop over the group when 2N > \varphi(q) and the sieve otherwise.
acb_dirichlet builds on these functions for the numerical values, Gauss sums and L-functions.

int dirichlet_group_init(dirichlet_group_t G, ulong q)

void dirichlet_char_log(dirichlet_char_t x, const dirichlet_group_t G, ulong m)

ulong dirichlet_chi(const dirichlet_group_t G, const dirichlet_char_t chi, ulong n)

void dirichlet_chi_vec(ulong * v, const dirichlet_group_t G, const dirichlet_char_t chi, slong nv)

ulong dirichlet_conductor_ui(const dirichlet_group_t G, ulong a)

int dirichlet_parity_ui(const dirichlet_group_t G, ulong a)