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)