Characters in the Conrey numbering

A Dirichlet character modulo q is a homomorphism \chi : (\mathbb{Z}/q\mathbb{Z})^\times \to \mathbb{C}^\times, extended to \mathbb{Z} by \chi(n) = 0 for \gcd(n, q) > 1. There are \varphi(q) characters, forming a group isomorphic to (\mathbb{Z}/q\mathbb{Z})^\times, but the isomorphism is not canonical: naming the characters requires a choice. This module uses the choice of Conrey, adopted by the LMFDB [LMFDB], which is reviewed here; the mathematics is described in Dirichlet characters.

Numbers and logs#

dirichlet_group_init decomposes (\mathbb{Z}/q\mathbb{Z})^\times into cyclic components, one for each odd prime power p^e \| q and up to two for the power of 2, and fixes a generator g_k of order \varphi_k for each: for p odd, the smallest primitive root modulo p^2; for 2^e, the elements -1 (if 4 \mid q) and 5 (if 8 \mid q). Every m \in (\mathbb{Z}/q\mathbb{Z})^\times is then

where \tilde g_k is the generator lifted to q (congruent to g_k modulo the prime power and to 1 modulo the rest of q). The integer m is the number and the vector (a_k) the log. A dirichlet_char_t stores both. Going from the log to the number is a product of powers (_dirichlet_char_exp); going from the number to the log needs discrete logarithms (dirichlet_char_log).

The character with number m is

where (a_k) and (b_k) are the logs of m and n. This pairing is symmetric in m and n, and the map m \mapsto \chi_q(m, \cdot) is an isomorphism, so the structure of a character can be read from its number: its order is the order of m modulo q, and it is real if m^2 \equiv 1. The character \chi_q(1, \cdot) is principal.

Values as exponents#

All values of the characters modulo q are powers of \zeta = e^{2\pi i/e}, where e = G->expo is the exponent of the group (the least common multiple of the \varphi_k). The functions return the exponent v \in [0, e) of \chi(n) = \zeta^v, which is exact, or the special value DIRICHLET_CHI_NULL for \chi(n) = 0. The _order variants of the vector functions take another modulus for the exponents, any multiple of the order of \chi: with the order itself, the exponents are the smallest possible. Complex values are obtained with acb_dirichlet, for example from a table of the powers of \zeta.

A single value dirichlet_chi(G, chi, n) costs a discrete logarithm of n in each component. For many values use dirichlet_chi_vec, which either enumerates the whole group once or sieves the discrete logarithms of all k < \mathit{nv} from those of the primes, or precompute tables with dirichlet_group_dlog_precompute.

Example#

The program prints all characters modulo 15 in the order of dirichlet_char_next, with their logs, conductors, parities, orders and the exponents of their values at n = 1, \ldots, 14 (a dot for 0). The group exponent is 4, so the exponent v stands for i^v: the character \chi_{15}(2, \cdot) has \chi(2) = i^3 = -i. The components are the group modulo 3, generated by \tilde g_0 = 11 (\equiv 2 \bmod 3), and modulo 5, generated by \tilde g_1 = 7 (\equiv 2 \bmod 5). Three characters, those with conductor 15, are primitive, and the character of number 4, the Legendre symbol modulo 5, has conductor 5.

#include <flint/flint.h>
#include <flint/dirichlet.h>

int main(void)
{
    dirichlet_group_t G;
    dirichlet_char_t chi;
    ulong v[15];
    slong k;

    dirichlet_group_init(G, 15);
    dirichlet_char_init(chi, G);

    flint_printf("%wu characters, exponent %wu, %wu primitive\n",
        dirichlet_group_size(G), G->expo, dirichlet_group_num_primitive(G));

    dirichlet_char_one(chi, G);
    do
    {
        flint_printf("m = %2wu  log ", chi->n);
        dirichlet_char_print(G, chi);
        flint_printf("  cond %2wu  %s  order %wu ",
            dirichlet_conductor_char(G, chi),
            dirichlet_parity_char(G, chi) ? "odd " : "even",
            dirichlet_order_char(G, chi));
        dirichlet_chi_vec(v, G, chi, 15);
        for (k = 1; k < 15; k++)
        {
            if (v[k] == DIRICHLET_CHI_NULL)
                flint_printf(" .");
            else
                flint_printf(" %wu", v[k]);
        }
        flint_printf("\n");
    }
    while (dirichlet_char_next(chi, G) >= 0);

    dirichlet_char_clear(chi);
    dirichlet_group_clear(G);
    return 0;
}

8 characters, exponent 4, 3 primitive
m =  1  log [0, 0]  cond  1  even  order 1  0 0 . 0 . . 0 0 . . 0 . 0 0
m =  7  log [0, 1]  cond  5  odd   order 4  0 1 . 2 . . 1 3 . . 0 . 3 2
m =  4  log [0, 2]  cond  5  even  order 2  0 2 . 0 . . 2 2 . . 0 . 2 0
m = 13  log [0, 3]  cond  5  odd   order 4  0 3 . 2 . . 3 1 . . 0 . 1 2
m = 11  log [1, 0]  cond  3  odd   order 2  0 2 . 0 . . 0 2 . . 2 . 0 2
m =  2  log [1, 1]  cond 15  even  order 4  0 3 . 2 . . 1 1 . . 2 . 3 0
m = 14  log [1, 2]  cond 15  odd   order 2  0 0 . 0 . . 2 0 . . 2 . 2 2
m =  8  log [1, 3]  cond 15  even  order 4  0 1 . 2 . . 3 3 . . 2 . 1 0

The table illustrates the symmetry of the pairing: the exponent in row m and column n equals the one in row n and column m, for instance \chi_{15}(7, 13) = \chi_{15}(13, 7) = i^3.