A nearly-optimal method to compute the truncated theta function, its derivatives, and integrals (Q640803)

This paper describes an iterative procedure for the approximate evaluation of exponential sums of the form \[ F(K,j;a,b):=K^{-j}\sum_{k=0}^K k^j\exp(2\pi iak+2\pi ibk^2), \] for non-negative integers \(j\) and real parameters \(a\) and \(b\). It is shown that there are absolute constants \(\kappa\) and \(A\) with the following property. If \(\varepsilon<e^{-1}\), and if \(\nu:=(j+1)\log(K/\varepsilon)\) then for any positive integer \(K\), any non-negative integer \(j\), and any real \(a,b\in[0,1)\), one can evaluate \(F(K,j;a,b)\) to within \(\pm A\nu^{\kappa}\varepsilon\), using at most \(A\nu^{\kappa}\) arithmetic operations on numbers of at most \(A\nu^2\) bits. Loosely speaking this means that one can evaluate \(F(K,j;a,b)\) in polynomial time. The basic idea is to normalize \(F(K,j;a,b)\) so that \(0\leq b\leq 1/4\). One then applies the van der Corput B-process so as to transform \(F(K,j;a,b)\) into a linear combination of terms \(F(K',j';a',b')\) with \(K'=[a+2bK]\), together with various error terms which are considered at length. Since \(K'\) is (essentially) at most \(K/2\) one reaches sums of trivial length in \(O(\log K)\) iterations. The basic theorem is applied in the author's work on computing the Riemann zeta-function [Ann. Math. (2) 174, No. 2, 891--946 (2011; Zbl 1243.11118)]. A second application, described in the present paper, shows that one can find the number of solutions to a congruence of the form \[ \sum_{i=1}^n(a_1k_i+b_ik_i^2)\equiv 0\pmod{M} \] with integers \(0\leq k_i\leq K\), in time \(M(MK)^{o(1)}\).