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

Abstract

A poly-log time method to compute the truncated theta function, its derivatives, and integrals is presented. The method is elementary, rigorous, explicit, and suited for computer implementation. We repeatedly apply the Poisson summation formula to the truncated theta function while suitably normalizing the linear and quadratic arguments after each repetition. The method relies on the periodicity of the complex exponential, which enables the suitable normalization of the arguments, and on the self-similarity of the Gaussian, which ensures that we still obtain a truncated theta function after each application of the Poisson summation. In other words, our method relies on modular properties of the theta function. Applications to the numerical computation of the Riemann zeta function and to finding the number of solutions of Waring type Diophantine equations are discussed.

  • [Da] H. Davenport, Multiplicative Number Theory, Third ed., New York: Springer-Verlag, 2000.
    @book {Da, MRKEY = {1790423},
      AUTHOR = {Davenport, Harold},
      TITLE = {Multiplicative Number Theory},
      SERIES = {Grad. Texts in Math.},
      NUMBER = {74},
      EDITION = {Third},
      NOTE = {Revised and with a preface by Hugh L. Montgomery},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {2000},
      PAGES = {xiv+177},
      ISBN = {0-387-95097-4},
      MRCLASS = {11-02 (11-01 11Mxx 11Nxx)},
      MRNUMBER = {1790423},
      ZBLNUMBER = {1002.11001},
      }
  • [Ed] H. M. Edwards, Riemann’s Zeta Function, Mineola, NY: Dover Publications, 2001.
    @book {Ed, MRKEY = {1854455},
      AUTHOR = {Edwards, H. M.},
      TITLE = {Riemann's Zeta Function},
      NOTE = {reprint of the 1974 original [Academic Press, New York; MR0466039]},
      PUBLISHER = {Dover Publications},
      ADDRESS = {Mineola, NY},
      YEAR = {2001},
      PAGES = {xiv+315},
      ISBN = {0-486-41740-9},
      MRCLASS = {11M06 (11M26)},
      MRNUMBER = {1854455},
      ZBLNUMBER = {1113.11303},
      }
  • [GK] Go to document S. W. Graham and G. Kolesnik, Van der Corput’s Method of Exponential Sums, Cambridge: Cambridge Univ. Press, 1991, vol. 126.
    @book {GK, MRKEY = {1145488},
      AUTHOR = {Graham, S. W. and Kolesnik, G.},
      TITLE = {van der {C}orput's Method of Exponential Sums},
      SERIES = {London Math. Soc. Lecture Note Ser.},
      VOLUME = {126},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {1991},
      PAGES = {vi+120},
      ISBN = {0-521-33927-8},
      MRCLASS = {11L07},
      MRNUMBER = {1145488},
      MRREVIEWER = {Zun Shan},
      DOI = {10.1017/CBO9780511661976},
      ZBLNUMBER = {0713.11001},
      }
  • [HB] D. R. Heath-Brown, Private communication to A. M. Odlyzko.
    @misc{HB,
      author={Heath-Brown, D. R.},
      TITLE={private communication to {A. M. O}dlyzko},
      }
  • [Hi] Go to document G. A. Hiary, Fast methods to compute the Riemann zeta function, Ann Arbor, MI: ProQuest LLC, 2008.
    @book{Hi,
      author={Hiary, G. A.},
      TITLE={{\rm Fast methods to compute the {R}iemann zeta function}},
      NOTE={Ph.D. thesis, University of Minnesota},
      PUBLISHER={ProQuest LLC},
      ADDRESS={ Ann Arbor, MI},
      YEAR={2008},
      MRNUMBER = {2712221},
      URL = {http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:3328310},
      }
  • [Hu] M. N. Huxley, Area, Lattice Points, and Exponential Sums, New York: Oxford Science Publications, The Clarendon Press Oxford Univ. Press, 1996, vol. 13.
    @book {Hu, MRKEY = {1420620},
      AUTHOR = {Huxley, M. N.},
      TITLE = {Area, Lattice Points, and Exponential Sums},
      SERIES = {London Math. Soc. Monogr. New Series},
      VOLUME = {13},
      PUBLISHER = {Oxford Science Publications, The Clarendon Press Oxford Univ. Press},
      ADDRESS = {New York},
      YEAR = {1996},
      PAGES = {xii+494},
      ISBN = {0-19-853466-3},
      MRCLASS = {11L07 (11J54 11P21)},
      MRNUMBER = {1420620},
      MRREVIEWER = {R. C. Baker},
      ZBLNUMBER = {0861.11002},
      }
  • [Is] 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.
    @book {Is, MRKEY = {2191786},
      AUTHOR = {Ismail, Mourad E. H.},
      TITLE = {Classical and Quantum Orthogonal Polynomials in One Variable, {\rm with two chapters by Walter Van Assche and a foreword by Richard A. Askey}},
      SERIES = {Encyclopedia Math. Appl.},
      VOLUME = {98},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {2005},
      PAGES = {xviii+706},
      ISBN = {978-0-521-78201-2; 0-521-78201-5},
      MRCLASS = {33-02 (05A30 05E35 33C45 33D50 42C05)},
      MRNUMBER = {2191786},
      MRREVIEWER = {Bruce C. Berndt},
      ZBLNUMBER = {1082.42016},
      }
  • [Ka] Go to document E. A. Karatsuba, "Approximation of sums of oscillating summands in certain physical problems," J. Math. Phys., vol. 45, iss. 11, pp. 4310-4321, 2004.
    @article {Ka, MRKEY = {2098139},
      AUTHOR = {Karatsuba, Ekatherina A.},
      TITLE = {Approximation of sums of oscillating summands in certain physical problems},
      JOURNAL = {J. Math. Phys.},
      FJOURNAL = {Journal of Mathematical Physics},
      VOLUME = {45},
      YEAR = {2004},
      NUMBER = {11},
      PAGES = {4310--4321},
      ISSN = {0022-2488},
      CODEN = {JMAPAQ},
      MRCLASS = {11Z05 (34H05)},
      MRNUMBER = {2098139},
      MRREVIEWER = {Arkady L. Kholodenko},
      DOI = {10.1063/1.1797552},
      ZBLNUMBER = {1064.11086},
      }
  • [Ko] N. M. Korobov, Exponential Sums and their Applications, Dordrecht: Kluwer Academic Publishers Group, 1992, vol. 80.
    @book {Ko, MRKEY = {1162539},
      AUTHOR = {Korobov, N. M.},
      TITLE = {Exponential Sums and their Applications},
      SERIES = {Math. Appl. (Soviet Series)},
      VOLUME = {80},
      NOTE = {translated from the 1989 Russian original by Yu. N. Shakhov},
      PUBLISHER = {Kluwer Academic Publishers Group},
      ADDRESS = {Dordrecht},
      YEAR = {1992},
      PAGES = {xvi+209},
      ISBN = {0-7923-1647-9},
      MRCLASS = {11Lxx (65D32)},
      MRNUMBER = {1162539},
      ZBLNUMBER = {0754.11022},
      }
  • [LWY] Go to document J. Liu, T. D. Wooley, and G. Yu, "The quadratic Waring-Goldbach problem," J. Number Theory, vol. 107, iss. 2, pp. 298-321, 2004.
    @article {LWY, MRKEY = {2072391},
      AUTHOR = {Liu, Jianya and Wooley, Trevor D. and Yu, Gang},
      TITLE = {The quadratic {W}aring-{G}oldbach problem},
      JOURNAL = {J. Number Theory},
      FJOURNAL = {Journal of Number Theory},
      VOLUME = {107},
      YEAR = {2004},
      NUMBER = {2},
      PAGES = {298--321},
      ISSN = {0022-314X},
      CODEN = {JNUTA9},
      MRCLASS = {11P32 (11N36 11P05 11P55)},
      MRNUMBER = {2072391},
      MRREVIEWER = {Koichi Kawada},
      DOI = {10.1016/j.jnt.2004.04.011},
      ZBLNUMBER = {1056.11055},
      }
  • [Mu] D. Mumford, Tata Lectures on Theta. I, Boston, MA: Birkhäuser, 1983, vol. 28.
    @book {Mu, MRKEY = {0688651},
      AUTHOR = {Mumford, David},
      TITLE = {Tata Lectures on Theta. {\rm I}},
      SERIES = {Progr. Math.},
      VOLUME = {28},
      NOTE = {with the assistance of C. Musili, M. Nori, E. Previato and M. Stillman},
      PUBLISHER = {Birkhäuser},
      ADDRESS = {Boston, MA},
      YEAR = {1983},
      PAGES = {xiii+235},
      ISBN = {3-7643-3109-7},
      MRCLASS = {14K25 (11E45 11G10 14C30)},
      MRNUMBER = {0688651},
      MRREVIEWER = {M. Kh. Gizatullin},
      ZBLNUMBER = {0509.14049},
      }
  • [OS] Go to document 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.
    @article {OS, MRKEY = {0961614},
      AUTHOR = {Odlyzko, A. M. and Sch{ö}nhage, A.},
      TITLE = {Fast algorithms for multiple evaluations of the {R}iemann zeta function},
      JOURNAL = {Trans. Amer. Math. Soc.},
      FJOURNAL = {Transactions of the American Mathematical Society},
      VOLUME = {309},
      YEAR = {1988},
      NUMBER = {2},
      PAGES = {797--809},
      ISSN = {0002-9947},
      CODEN = {TAMTAM},
      MRCLASS = {11M06 (11M26 11Y35 65E05 68Q25)},
      MRNUMBER = {0961614},
      MRREVIEWER = {H. J. Godwin},
      DOI = {10.2307/2000939},
      ZBLNUMBER = {0706.11047},
      }
  • [Od] Go to document A. M. Odlyzko, The $10^{20}$-th zero of the Riemann zeta function and 175 million of its neighbors.
    @misc{Od,
      author={Odlyzko, A. M.},
      TITLE={The $10^{20}$-th zero of the {R}iemann zeta function and 175 million of its neighbors},
      NOTE={manuscript},
      URL={www.dtc.umn.edu/~odlyzko},
      }
  • [Ru] Go to document 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.
    @incollection {Ru, MRKEY = {2166470},
      AUTHOR = {Rubinstein, Michael},
      TITLE = {Computational methods and experiments in analytic number theory},
      BOOKTITLE = {Recent Perspectives in Random Matrix Theory and Number Theory},
      SERIES = {London Math. Soc. Lecture Note Ser.},
      VOLUME = {322},
      PAGES = {425--506},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {2005},
      MRCLASS = {11Y35 (11M41)},
      MRNUMBER = {2166470},
      MRREVIEWER = {Robert Juricevic},
      DOI = {10.1017/CBO9780511550492.015},
      ZBLNUMBER = {1168.11329},
      }
  • [Sc] A. Schönhage, "Numerik analytischer Funktionen und Komplexität," Jahresber. Deutsch. Math.-Verein., vol. 92, iss. 1, pp. 1-20, 1990.
    @article {Sc, MRKEY = {1037441},
      AUTHOR = {Sch{ö}nhage, A.},
      TITLE = {Numerik analytischer {F}unktionen und {K}omplexität},
      JOURNAL = {Jahresber. Deutsch. Math.-Verein.},
      FJOURNAL = {Jahresbericht der Deutschen Mathematiker-Vereinigung},
      VOLUME = {92},
      YEAR = {1990},
      NUMBER = {1},
      PAGES = {1--20},
      ISSN = {0012-0456},
      CODEN = {JDMVA7},
      MRCLASS = {68Q40 (65E05 68Q25)},
      MRNUMBER = {1037441},
      MRREVIEWER = {Helmut Alt},
      ZBLNUMBER={0797.68090},
      }
  • [Ti] E. C. Titchmarsh, The Theory of the Riemann zeta-Function, Second ed., New York: The Clarendon Press Oxford University Press, 1986.
    @book {Ti, MRKEY = {0882550},
      AUTHOR = {Titchmarsh, E. C.},
      TITLE = {The Theory of the {R}iemann zeta-Function},
      EDITION = {Second},
      NOTE = {edited and with a preface by D. R. Heath-Brown},
      PUBLISHER = {The Clarendon Press Oxford University Press},
      ADDRESS = {New York},
      YEAR = {1986},
      PAGES = {x+412},
      ISBN = {0-19-853369-1},
      MRCLASS = {11M06},
      MRNUMBER = {0882550},
      MRREVIEWER = {Matti Jutila},
      ZBLNUMBER = {0601.10026},
      }
  • [Vi] I. M. Vinogradov, Elements of Number Theory, New York: Dover Publications, 1954.
    @book {Vi, MRKEY = {0062138},
      AUTHOR = {Vinogradov, I. M.},
      TITLE = {Elements of Number Theory},
      NOTE = {translated by S. Kravetz},
      PUBLISHER = {Dover Publications},
      ADDRESS = {New York},
      YEAR = {1954},
      PAGES = {viii+227},
      MRCLASS = {10.0X},
      MRNUMBER = {0062138},
      ZBLNUMBER = {0057.28201},
      }

Authors

Ghaith Ayesh Hiary

Pure Mathematics
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1