dirichlet.h – Dirichlet characters¶
Warning: the interfaces in this module are experimental and may change without notice.
This module allows working with Dirichlet characters algebraically. For evaluations of characters as complex numbers, see acb_dirichlet.h – Dirichlet L-functions, Riemann zeta and related functions.
Dirichlet characters¶
Working with Dirichlet characters mod q consists mainly in going from residue classes mod q to exponents on a set of generators of the group.
This implementation relies on the Conrey numbering scheme introduced in the L-functions and Modular Forms DataBase, which is an explicit choice of generators allowing to represent Dirichlet characters via the pairing
We call number a residue class \(m\) modulo q, and log the corresponding vector \((a_i)\) of exponents of Conrey generators.
Going from a log to the corresponding number is a cheap operation we call exponential, while the converse requires computing discrete logarithms.
Multiplicative group modulo q¶
-
type
dirichlet_group_struct
¶
-
type
dirichlet_group_t
¶ Represents the group of Dirichlet characters mod q.
An dirichlet_group_t is defined as an array of dirichlet_group_struct of length 1, permitting it to be passed by reference.
-
void
dirichlet_group_init
(dirichlet_group_t G, ulong q)¶ Initializes G to the group of Dirichlet characters mod q.
This method computes a canonical decomposition of G in terms of cyclic groups, which are the mod \(p^e\) subgroups for \(p^e\|q\), plus the specific generator described by Conrey for each subgroup.
In particular G contains:
the number num of components
the generators
the exponent expo of the group
It does not automatically precompute lookup tables of discrete logarithms or numerical roots of unity, and can therefore safely be called even with large q.
For implementation reasons, the largest prime factor of q must not exceed \(10^{12}\) (an abort will be raised). This restriction could be removed in the future.
-
void
dirichlet_subgroup_init
(dirichlet_group_t H, const dirichlet_group_t G, ulong h)¶ Given an already computed group G mod \(q\), initialize its subgroup H defined mod \(h\mid q\). Precomputed discrete log tables are inherited.
-
void
dirichlet_group_clear
(dirichlet_group_t G)¶ Clears G. Remark this function does not clear the discrete logarithm tables stored in G (which may be shared with another group).
-
ulong
dirichlet_group_size
(const dirichlet_group_t G)¶ Returns the number of elements in G, i.e. \(\varphi(q)\).
-
ulong
dirichlet_group_num_primitive
(const dirichlet_group_t G)¶ Returns the number of primitive elements in G.
-
void
dirichlet_group_dlog_precompute
(dirichlet_group_t G, ulong num)¶ Precompute decomposition and tables for discrete log computations in G, so as to minimize the complexity of num calls to discrete logarithms.
If num gets very large, the entire group may be indexed.
-
void
dirichlet_group_dlog_clear
(dirichlet_group_t G, ulong num)¶ Clear discrete logarithm tables in G. When discrete logarithm tables are shared with subgroups, those subgroups must be cleared before clearing the tables.
Character type¶
-
type
dirichlet_char_struct
¶
-
type
dirichlet_char_t
¶ Represents a Dirichlet character. This structure contains both a number (residue class) and the corresponding log (exponents on the group generators).
An dirichlet_char_t is defined as an array of dirichlet_char_struct of length 1, permitting it to be passed by reference.
-
void
dirichlet_char_init
(dirichlet_char_t chi, const dirichlet_group_t G)¶ Initializes chi to an element of the group G and sets its value to the principal character.
-
void
dirichlet_char_clear
(dirichlet_char_t chi)¶ Clears chi.
-
void
dirichlet_char_print
(const dirichlet_group_t G, const dirichlet_char_t chi)¶ Prints the array of exponents representing this character.
-
void
dirichlet_char_log
(dirichlet_char_t x, const dirichlet_group_t G, ulong m)¶ Sets x to the character of number m, computing its log using discrete logarithm in G.
-
ulong
dirichlet_char_exp
(const dirichlet_group_t G, const dirichlet_char_t x)¶ Returns the number m corresponding to exponents in x.
-
ulong
_dirichlet_char_exp
(dirichlet_char_t x, const dirichlet_group_t G)¶ Computes and returns the number m corresponding to exponents in x. This function is for internal use.
-
void
dirichlet_char_one
(dirichlet_char_t x, const dirichlet_group_t G)¶ Sets x to the principal character in G, having log \([0,\dots 0]\).
-
void
dirichlet_char_first_primitive
(dirichlet_char_t x, const dirichlet_group_t G)¶ Sets x to the first primitive character of G, having log \([1,\dots 1]\), or \([0, 1, \dots 1]\) if \(8\mid q\).
-
void
dirichlet_char_set
(dirichlet_char_t x, const dirichlet_group_t G, const dirichlet_char_t y)¶ Sets x to the element y.
-
int
dirichlet_char_next
(dirichlet_char_t x, const dirichlet_group_t G)¶ Sets x to the next character in G according to lexicographic ordering of log.
The return value is the index of the last updated exponent of x, or -1 if the last element has been reached.
This function allows to iterate on all elements of G looping on their log. Note that it produces elements in seemingly random number order.
The following template can be used for such a loop:
dirichlet_char_one(chi, G); do { /* use character chi */ } while (dirichlet_char_next(chi, G) >= 0);
-
int
dirichlet_char_next_primitive
(dirichlet_char_t x, const dirichlet_group_t G)¶ Same as
dirichlet_char_next()
, but jumps to the next primitive character of G.
-
ulong
dirichlet_index_char
(const dirichlet_group_t G, const dirichlet_char_t x)¶ Returns the lexicographic index of the log of x as an integer in \(0\dots \varphi(q)\).
-
void
dirichlet_char_index
(dirichlet_char_t x, const dirichlet_group_t G, ulong j)¶ Sets x to the character whose log has lexicographic index j.
-
int
dirichlet_char_eq
(const dirichlet_char_t x, const dirichlet_char_t y)¶
-
int
dirichlet_char_eq_deep
(const dirichlet_group_t G, const dirichlet_char_t x, const dirichlet_char_t y)¶ Return 1 if x equals y.
The second version checks every byte of the representation and is intended for testing only.
Character properties¶
As a consequence of the Conrey numbering, all these numbers are available at the level of number and char object. Both case require no discrete log computation.
-
int
dirichlet_char_is_principal
(const dirichlet_group_t G, const dirichlet_char_t chi)¶ Returns 1 if chi is the principal character mod q.
-
ulong
dirichlet_conductor_ui
(const dirichlet_group_t G, ulong a)¶
-
ulong
dirichlet_conductor_char
(const dirichlet_group_t G, const dirichlet_char_t x)¶ Returns the conductor of \(\chi_q(a,\cdot)\), that is the smallest \(r\) dividing \(q\) such \(\chi_q(a,\cdot)\) can be obtained as a character mod \(r\).
-
int
dirichlet_parity_ui
(const dirichlet_group_t G, ulong a)¶
-
int
dirichlet_parity_char
(const dirichlet_group_t G, const dirichlet_char_t x)¶ Returns the parity \(\lambda\) in \(\{0,1\}\) of \(\chi_q(a,\cdot)\), such that \(\chi_q(a,-1)=(-1)^\lambda\).
-
ulong
dirichlet_order_ui
(const dirichlet_group_t G, ulong a)¶
-
ulong
dirichlet_order_char
(const dirichlet_group_t G, const dirichlet_char_t x)¶ Returns the order of \(\chi_q(a,\cdot)\) which is the order of \(a\bmod q\).
-
int
dirichlet_char_is_real
(const dirichlet_group_t G, const dirichlet_char_t chi)¶ Returns 1 if chi is a real character (iff it has order \(\leq 2\)).
-
int
dirichlet_char_is_primitive
(const dirichlet_group_t G, const dirichlet_char_t chi)¶ Returns 1 if chi is primitive (iff its conductor is exactly q).
Character evaluation¶
Dirichlet characters take value in a finite cyclic group of roots of unity plus zero.
Evaluation functions return a ulong, this number corresponds to the power of a primitive root of unity, the special value DIRICHLET_CHI_NULL encoding the zero value.
-
ulong
dirichlet_pairing
(const dirichlet_group_t G, ulong m, ulong n)¶
-
ulong
dirichlet_pairing_char
(const dirichlet_group_t G, const dirichlet_char_t chi, const dirichlet_char_t psi)¶ Compute the value of the Dirichlet pairing on numbers m and n, as exponent modulo G->expo.
The char variant takes as input two characters, so that no discrete logarithm is computed.
The returned value is the numerator of the actual value exponent mod the group exponent G->expo.
-
ulong
dirichlet_chi
(const dirichlet_group_t G, const dirichlet_char_t chi, ulong n)¶ Compute the value \(\chi(n)\) as the exponent modulo G->expo.
-
void
dirichlet_chi_vec
(ulong *v, const dirichlet_group_t G, const dirichlet_char_t chi, slong nv)¶ Compute the list of exponent values v[k] for \(0\leq k < nv\), as exponents modulo G->expo.
-
void
dirichlet_chi_vec_order
(ulong *v, const dirichlet_group_t G, const dirichlet_char_t chi, ulong order, slong nv)¶ Compute the list of exponent values v[k] for \(0\leq k < nv\), as exponents modulo order, which is assumed to be a multiple of the order of chi.
Character operations¶
-
void
dirichlet_char_mul
(dirichlet_char_t chi12, const dirichlet_group_t G, const dirichlet_char_t chi1, const dirichlet_char_t chi2)¶ Multiply two characters of the same group G.
-
void
dirichlet_char_pow
(dirichlet_char_t c, const dirichlet_group_t G, const dirichlet_char_t a, ulong n)¶ Take the power of a character.
-
void
dirichlet_char_lift
(dirichlet_char_t chi_G, const dirichlet_group_t G, const dirichlet_char_t chi_H, const dirichlet_group_t H)¶ If H is a subgroup of G, computes the character in G corresponding to chi_H in H.
-
void
dirichlet_char_lower
(dirichlet_char_t chi_H, const dirichlet_group_t H, const dirichlet_char_t chi_G, const dirichlet_group_t G)¶ If chi_G is a character of G which factors through H, sets chi_H to the corresponding restriction in H.
This requires \(c(\chi_G)\mid q_H\mid q_G\), where \(c(\chi_G)\) is the conductor of \(\chi_G\) and \(q_G, q_H\) are the moduli of G and H.