Skip to content

DirichletCharacter

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description

DirichletCharacter[k, j, n]

gives the Dirichlet character chi_{k,j}(n) with modulus k and index j.

DirichletCharacter[k, j, g] = Exp[2 Pi I (j-1)/(k-1)]). The value is 0

Notes There are EulerPhi\[k\] characters mod k, j = 1 being the principal one; the ordering is Mathematica's (a primitive root g of a prime k has when GCD\[n, k\] \> 1, else a root of unity, given exactly. Periodic in n with period k and completely multiplicative. Threads over lists; k must be below 2^63.

Examples (12)

Every input below was run against the current Mathilda build and its output recorded.

Basic examples (3)

In[1]:= Table[DirichletCharacter[5, 2, n], {n, 1, 5}]
Out[1]= {1, I, -I, -1, 0}

In[2]:= Table[DirichletCharacter[8, j, n], {j, 1, 4}, {n, 1, 8}]
Out[2]= {{1, 0, 1, 0, 1, 0, 1, 0}, {1, 0, -1, 0, -1, 0, 1, 0}, {1, 0, -1, 0, 1, 0, -1, 0}, {1, 0, 1, 0, -1, 0, -1, 0}}

In[3]:= DirichletCharacter[45, 8, 7]
Out[3]= -I E^((-2/3*I) Pi)

Applications (9)

The non-principal character mod 4

In[4]:= Table[DirichletCharacter[4, 2, n], {n, 1, 8}]
Out[4]= {1, 0, -1, 0, 1, 0, -1, 0}

For prime k, the value at the primitive root is Exp[2 Pi I (j - 1)/(k - 1)]

In[5]:= Table[DirichletCharacter[5, j, PrimitiveRoot[5]], {j, 1, 4}]
Out[5]= {1, I, -1, -I}

For modulus 8 the sign component <-1> is the most significant digit, then <5>

In[6]:= Table[DirichletCharacter[8, j, n], {j, 1, 4}, {n, 1, 8}]
Out[6]= {{1, 0, 1, 0, 1, 0, 1, 0}, {1, 0, -1, 0, -1, 0, 1, 0}, {1, 0, -1, 0, 1, 0, -1, 0}, {1, 0, 1, 0, -1, 0, -1, 0}}

The quadratic character mod 7 is the Legendre symbol

In[7]:= Table[DirichletCharacter[7, 4, n], {n, 1, 7}] == Table[JacobiSymbol[n, 7], {n, 1, 7}]
Out[7]= True

A composite modulus factors over its prime-power parts

In[8]:= {DirichletCharacter[45, 8, 7], DirichletCharacter[9, 2, 7] DirichletCharacter[5, 4, 7]}
Out[8]= {-I E^((-2/3*I) Pi), -I E^((-2/3*I) Pi)}

Complete multiplicativity

In[9]:= DirichletCharacter[7, 3, 15] == DirichletCharacter[7, 3, 3] DirichletCharacter[7, 3, 5]
Out[9]= True

A packed integer buffer: a real character returns 0 and +-1

In[10]:= DirichletCharacter[12, 3, Range[1, 12]]
Out[10]= {1, 0, 0, 0, 1, 0, -1, 0, 0, 0, -1, 0}

A large prime modulus through Pohlig-Hellman discrete logs

In[11]:= DirichletCharacter[10^12 + 39, 5, 3]
Out[11]= E^((4/500000000019*I) Pi)

An index beyond EulerPhi[5] emits DirichletCharacter::invl and stays unevaluated

In[12]:= DirichletCharacter[5, 6, 2]
Out[12]= DirichletCharacter[5, 6, 2]

Algorithm

dirichlet_character.c -- DirichletCharacter[k, j, n].

The Dirichlet character chi_{k,j}(n) in Mathematica's labelling (see dirichlet.h). Values are exact: 0, a unit (+-1, +-I) or unit * E^(I Pi r).

Attributes: Protected (as in Mathematica). DirichletCharacter is NOT Listable, yet it threads over lists in every argument; that is done here.

Packed / NDArray surface: an int64 buffer of n with scalar k, j is answered straight from the character table. A real character (values 0, +-1) returns an int64 array of the same shape and presentation; a complex character returns a List of exact roots of unity -- those are not machine numbers, so there is no buffer to return (recorded in the array-exactness EXEMPT list). DirichletCharacter is exact-valued, so it has no Compile[] lowering (compile-coverage EXEMPT).

Implementation notes

Algorithm. builtin_dirichletcharacter checks arity, sends an NDArray or packed argument to dc_ndarray, and threads over List arguments itself through dc_thread; the head is only Protected, not Listable. It validates (k, j) with dch_validate_kj, which emits the intp and invl messages, and fetches the cached table from dch_get. The labelling is the one src/special_functions/dirichlet.h documents as reverse-engineered from Mathematica 14, not the Conrey labelling. k is factored with primes ascending, and (Z/kZ)* splits into cyclic components. An odd p^a gives one component, generated by the smallest primitive root mod p^a. The modulus 4 gives one component, generated by 3. A power 2^a with a ≥ 3 gives two: the sign component ⟨-1⟩, then ⟨5⟩. j - 1 is written in mixed radix over the components, with the first component most significant, and χ(g_c) = exp(2πi d_c/ord_c). A value χ(n) is 0 when gcd(n, k) > 1. Otherwise dch_exp takes a discrete log in each component (dlog_comp), using Pohlig–Hellman over the component order with baby-step giant-step in each prime-order subgroup (dlog_prime). It sums the exponents in Z/ord(χ), and dch_root_of_unity_expr renders the result exactly as a unit times E^(I Pi r) with r ∈ (-1, 1).

Data structures. A DchTable (cached and immutable once published, so threaded Compile loops can share it) holds the components and digits, the order, parity and conductor f, the primitive inducing character χ*, and the Euler-factor primes. For f ≤ 2^22 (DCH_TABLE_MAX) it also holds dense tables over 0..f-1 of exact exponents and machine values, plus the root number. The dense tables are built by walking powers of each generator, with no logs. All modular arithmetic is overflow-safe on uint64_t for k < 2^63 (dch_mulmod, dch_powmod). An int64 buffer n gives an int64 buffer of 0, ±1 for a real character, and a List of exact roots of unity otherwise.

Complexity / limits. A dense value costs O(1), and a single value for a large modulus costs about O(Σ e_i √q_i) per component. A component order whose largest prime factor exceeds 2^44 leaves the call unevaluated. A non-integer n emits DirichletCharacter::int. The values are exact, so there is no Compile[] lowering; the head is on the compile-coverage EXEMPT list.

Attributes: Protected.

References

See also: NDArray

Notes & additional examples

Notes

  • Labelling. Mathilda reproduces Mathematica's index j = 1..EulerPhi[k], which is not the Conrey labelling used by LMFDB and arb. k is factored with primes ascending into cyclic components: one per odd p^a, generated by its smallest primitive root; one for 4, generated by 3; and two for 2^a with a ≥ 3, ⟨-1⟩ then ⟨5⟩. j - 1 is read in mixed radix with the first component most significant, and χ(g_c) = exp(2πi d_c/ord_c). j = 1 is the principal character. For a prime k, DirichletCharacter[k, j, PrimitiveRoot[k]] = Exp[2 Pi I (j-1)/(k-1)].
  • Values are exact: 0, a unit (±1, ±I), or a unit times E^(I Pi r).
  • DirichletCharacter::invl (j > EulerPhi[k]), ::intp and ::int all route through the message funnel, so Quiet and Check work.
  • Attributes: Protected only, as in Mathematica; the builtin threads over lists itself. An int64 packed n with a real character returns an int64 buffer. There is no Compile[] lowering, because the values are exact.
  • See also: DirichletL, PrimitiveRoot, JacobiSymbol, MultiplicativeOrder.