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