Computing Dirichlet character sums to a power-full modulus
type: Item
instance of: scholarly article
title: Computing Dirichlet character sums to a power-full modulus
zbMATH Open document ID: 1320.11079
published in: Journal of Number Theory
publication date: 2014-08-27T00:00:00Z
full work available at URL: https://arxiv.org/abs/1205.4687
reviewed by: Stelian Mihalas
Mathematics Subject Classification ID: 11M06
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11L03
Mathematics Subject Classification ID: 11L40
zbMATH DE Number: 6334894
zbMATH Keywords: character sums
zbMATH Keywords: exponential sums
zbMATH Keywords: Dirichlet \(L\)-functions
zbMATH Keywords: algorithms
zbMATH Keywords: power-full modulus
author: Ghaith A. Hiary
MaRDI profile type: Publication
OpenAlex ID: W2043136487
arXiv ID: 1205.4687
cites work: On prime numbers in an arithmetic progression with a prime-power difference
cites work: Q4855774
cites work: Quadratic class numbers and character sums
cites work: Q5317673
cites work: Q4520255
cites work: An approximate functional equation for Dirichlet L -functions
cites work: Primes in progressions to prime-power modulus
cites work: Q5516895
cites work: A nearly-optimal method to compute the truncated theta function, its derivatives, and integrals
cites work: Fast methods to compute the Riemann zeta function
cites work: An amortized-complexity method to compute the Riemann zeta function
cites work: On zeros of Dirichlet's \(L\)-series
cites work: Q4830109
cites work: Computing π(x): The Meissel-Lehmer Method
cites work: Q3615927
cites work: Q3229483
cites work: Numerics of analytic functions and complexity
cites work: Q3735790
cites work: Rapid Computation of L-functions for Modular Forms
cites work: A fast algorithm to compute \(L(1/2, f\times \chi_q)\)
DOI: 10.1016/J.JNT.2013.12.005
review text: 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.
description: scientific article; zbMATH DE number 6334894