Computing Dirichlet character sums to a power-full modulus
This paper provides a practical method for computing Dirichlet character sums \(L(s, \chi)\), where \(\chi\) is a character modulo \(q\). This method is particularly efficient when \(q\) is smooth enough (\textit{the radical of \(q\) is small enough when compared with \(q\)}) or a \textit{power-full modulus}, that is, when \(q\) is a prime power or when the number of its prime factors is low.NEWLINENEWLINEHere is the main result:NEWLINENEWLINEThere are absolute constants \(A_1, A_2, \dots, A_5, \kappa_1, \kappa_2, \kappa_3\) such that for any real number \(\lambda\), any complex number \(s\) with \(1/2 \leq \mathrm{Re}(s) \leq 1\), any positive integer \(q = p_1^{\alpha_1}\dots p_h^{\alpha_h}\) (with distinct primes \(p_i\)) and any given character \(\chi\) mod \(q\), the value of the Dirichlet \(L\)-function \(L(s, \chi)\) can be computed to within \(q^{-1}(| s | + 1)^{-\lambda}\) using \(\leq A_1p_1^{\left\lceil \alpha_1/3\right\rceil}\dots p_h^{\left\lceil \alpha_h/3\right\rceil}(| s | + 1)^{1/3}(\lambda + 1)^{\kappa_1} \log^{\kappa_1}(q(| s | + 1))\) operations on numbers of \(\leq A_2(\lambda + 1)^4 \log^4(q(| s | + 1))\) bits, provided a precomputation, that depends on \(q\) only, costing \(A_3(p_1 + \dots + p_h)\log^{\kappa_2} q\) operations on numbers of \(\leq A_4 \log q\) bits, and requiring \(\leq A_5(p_1\dots + p_h)\log^{\kappa_3}q\) bits of storage.
- A fast algorithm to compute L(1/2, f _q)
- Estimates for character sums and Dirichlet L-functions to smooth moduli
- A fast amortized algorithm for computing quadratic Dirichlet L-functions
- On the character sums of polynomials and L-functions
- Numerical verification of Littlewood's bounds for \(|L(1,\chi)|\)
- A fast algorithm to compute L(1/2, f _q)
- A nearly-optimal method to compute the truncated theta function, its derivatives, and integrals
- An amortized-complexity method to compute the Riemann zeta function
- An approximate functional equation for Dirichlet L -functions
- Computing π(x): The Meissel-Lehmer Method
- Elementary thoughts on discrete logarithms
- Fast methods to compute the Riemann zeta function
- scientific article; zbMATH DE number 3115184 (Why is no real title available?)
- scientific article; zbMATH DE number 3968684 (Why is no real title available?)
- scientific article; zbMATH DE number 1542664 (Why is no real title available?)
- scientific article; zbMATH DE number 2121181 (Why is no real title available?)
- scientific article; zbMATH DE number 818427 (Why is no real title available?)
- scientific article; zbMATH DE number 2206373 (Why is no real title available?)
- scientific article; zbMATH DE number 3228666 (Why is no real title available?)
- Numerics of analytic functions and complexity
- On prime numbers in an arithmetic progression with a prime-power difference
- On zeros of Dirichlet's L-series
- Primes in progressions to prime-power modulus
- Quadratic class numbers and character sums
- Rapid computation of \(L\)-functions for modular forms
- Zeros of partial sums of L-functions
- A fast algorithm to compute L(1/2, f _q)
- An alternative to Riemann-Siegel type formulas
- An explicit hybrid estimate for \(L(1/2+it,\chi)\)
- A fast amortized algorithm for computing quadratic Dirichlet L-functions
- Computational Number Theory in Relation with L-Functions
- On computing L'/L(1,)
- Computing \(L\)-functions: a survey
- On the character sums moduloequal of the power prime number 2
This page was built for publication: Computing Dirichlet character sums to a power-full modulus
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q401979)
