×

A nearly-optimal method to compute the truncated theta function, its derivatives, and integrals. (English) Zbl 1243.11117

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)}\).

MSC:

11Y16 Number-theoretic algorithms; complexity
11L15 Weyl sums
11Y35 Analytic computations

Citations:

Zbl 1243.11118
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] H. Davenport, Multiplicative Number Theory, Third ed., New York: Springer-Verlag, 2000. · Zbl 1002.11001
[2] H. M. Edwards, Riemann’s Zeta Function, Mineola, NY: Dover Publications, 2001. · Zbl 1113.11303
[3] S. W. Graham and G. Kolesnik, Van der Corput’s Method of Exponential Sums, Cambridge: Cambridge Univ. Press, 1991, vol. 126. · Zbl 0713.11001 · doi:10.1017/CBO9780511661976
[4] D. R. Heath-Brown, Private communication to A. M. Odlyzko.
[5] G. A. Hiary, Fast methods to compute the Riemann zeta function, Ann Arbor, MI: ProQuest LLC, 2008. · Zbl 1243.11118 · doi:10.4007/annals.2011.174.2.4
[6] M. N. Huxley, Area, Lattice Points, and Exponential Sums, New York: Oxford Science Publications, The Clarendon Press Oxford Univ. Press, 1996, vol. 13. · Zbl 0861.11002
[7] M. E. H. Ismail, Classical and Quantum Orthogonal Polynomials in One Variable, with two chapters by Walter Van Assche and a foreword by Richard A. Askey, Cambridge: Cambridge Univ. Press, 2005, vol. 98. · Zbl 1082.42016
[8] E. A. Karatsuba, ”Approximation of sums of oscillating summands in certain physical problems,” J. Math. Phys., vol. 45, iss. 11, pp. 4310-4321, 2004. · Zbl 1064.11086 · doi:10.1063/1.1797552
[9] N. M. Korobov, Exponential Sums and their Applications, Dordrecht: Kluwer Academic Publishers Group, 1992, vol. 80. · Zbl 0754.11022
[10] J. Liu, T. D. Wooley, and G. Yu, ”The quadratic Waring-Goldbach problem,” J. Number Theory, vol. 107, iss. 2, pp. 298-321, 2004. · Zbl 1056.11055 · doi:10.1016/j.jnt.2004.04.011
[11] D. Mumford, Tata Lectures on Theta. I, Boston, MA: Birkhäuser, 1983, vol. 28. · Zbl 0509.14049 · doi:10.1007/978-1-4899-2843-6
[12] A. M. Odlyzko and A. Schönhage, ”Fast algorithms for multiple evaluations of the Riemann zeta function,” Trans. Amer. Math. Soc., vol. 309, iss. 2, pp. 797-809, 1988. · Zbl 0706.11047 · doi:10.2307/2000939
[13] A. M. Odlyzko, The \(10^{20}\)-th zero of the Riemann zeta function and 175 million of its neighbors.
[14] M. Rubinstein, ”Computational methods and experiments in analytic number theory,” in Recent Perspectives in Random Matrix Theory and Number Theory, Cambridge: Cambridge Univ. Press, 2005, vol. 322, pp. 425-506. · Zbl 1168.11329 · doi:10.1017/CBO9780511550492.015
[15] A. Schönhage, ”Numerik analytischer Funktionen und Komplexität,” Jahresber. Deutsch. Math.-Verein., vol. 92, iss. 1, pp. 1-20, 1990. · Zbl 0797.68090
[16] E. C. Titchmarsh, The Theory of the Riemann zeta-Function, Second ed., New York: The Clarendon Press Oxford University Press, 1986. · Zbl 0601.10026
[17] I. M. Vinogradov, Elements of Number Theory, New York: Dover Publications, 1954. · Zbl 0057.28201
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.