Fast methods to compute the Riemann zeta function

Abstract

The Riemann zeta function on the critical line can be computed using a straightforward application of the Riemann-Siegel formula, Schönhage’s method, or Heath-Brown’s method. The complexities of these methods have exponents 1/2, 3/8, and 1/3 respectively. In this article, three new fast and potentially practical methods to compute zeta are presented. One method is very simple. Its complexity has exponent 2/5. A second method relies on this author’s algorithm to compute quadratic exponential sums. Its complexity has exponent 1/3. The third method, which is our main result, employs an algorithm developed here to compute cubic exponential sums with a small cubic coefficient. Its complexity has exponent 4/13 (approximately, 0.307).

  • [BK] Go to document M. V. Berry and J. P. Keating, "A new asymptotic representation for $\zeta(\frac12+it)$ and quantum spectral determinants," Proc. Roy. Soc. London Ser. A, vol. 437, iss. 1899, pp. 151-173, 1992.
    @article {BK, MRKEY = {1177749},
      AUTHOR = {Berry, M. V. and Keating, J. P.},
      TITLE = {A new asymptotic representation for {$\zeta(\frac12+it)$} and quantum spectral determinants},
      JOURNAL = {Proc. Roy. Soc. London Ser. A},
      FJOURNAL = {Proceedings of the Royal Society. London. Series A. Mathematical, Physical and Engineering Sciences},
      VOLUME = {437},
      YEAR = {1992},
      NUMBER = {1899},
      PAGES = {151--173},
      ISSN = {0962-8444},
      CODEN = {PRLAAZ},
      MRCLASS = {11M06 (11M41 11Z50 58F20 81Q50)},
      MRNUMBER = {1177749},
      MRREVIEWER = {Jack Quine},
      DOI = {10.1098/rspa.1992.0053},
      ZBLNUMBER = {0776.11048},
      }
  • [BF] Go to document E. Bombieri and J. B. Friedlander, "Dirichlet polynomial approximations to zeta functions," Ann. Scuola Norm. Sup. Pisa Cl. Sci., vol. 22, iss. 3, pp. 517-544, 1995.
    @article {BF, MRKEY = {1360548},
      AUTHOR = {Bombieri, E. and Friedlander, J. B.},
      TITLE = {Dirichlet polynomial approximations to zeta functions},
      JOURNAL = {Ann. Scuola Norm. Sup. Pisa Cl. Sci.},
      FJOURNAL = {Annali della Scuola Normale Superiore di Pisa. Classe di Scienze. Serie IV},
      VOLUME = {22},
      YEAR = {1995},
      NUMBER = {3},
      PAGES = {517--544},
      ISSN = {0391-173X},
      CODEN = {PSNAAI},
      MRCLASS = {11M06 (11M41)},
      MRNUMBER = {1360548},
      MRREVIEWER = {Kohji Matsumoto},
      URL = {http://www.numdam.org/item?id=ASNSP_1995_4_22_3_517_0},
      ZBLNUMBER = {0837.11051},
      }
  • [Da] H. Davenport, Multiplicative Number Theory, Third ed., New York: Springer-Verlag, 2000, vol. 74.
    @book {Da, MRKEY = {1790423},
      AUTHOR = {Davenport, Harold},
      TITLE = {Multiplicative Number Theory},
      SERIES = {Grad. Texts in Math.},
      VOLUME = {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},
      }
  • [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, "A nearly-optimal method to compute the truncated theta function, its derivatives, and integrals," Ann. of Math., vol. 174, pp. 859-989, 2011.
    @article{Hi,
      author={Hiary, G. A.},
      TITLE={A nearly-optimal method to compute the truncated theta function, its derivatives, and integrals},
      journal = {Ann. of Math.},
      volume = {174},
      year = {2011},
      pages = {859--989},
      doi = {10.4007/annals.2011.174.2.3},
     }
  • [Ga] W. Gabcke, Neue Herleitung und explicite Restabschätzung der Riemann-Siegel-Formel, 1979.
    @misc{Ga,
      author={Gabcke, W.},
      TITLE={Neue {H}erleitung und explicite {R}estabschätzung der {R}iemann-{S}iegel-{F}ormel},
      NOTE={Ph.D. dissertation, Göttingen},
      YEAR={1979},
      }
  • [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},
      }
  • [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},
      URL={www.dtc.umn.edu/~odlyzko},
      }
  • [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},
      }
  • [Ru] Go to document M. Rubinstein, "Computational methods and experiments in analytic number theory," in Recent Rerspectives 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 Rerspectives 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},
      }
  • [Tu] Go to document A. M. Turing, "Some calculations of the Riemann zeta-function," Proc. London Math. Soc., vol. 3, pp. 99-117, 1953.
    @article {Tu, MRKEY = {0055785},
      AUTHOR = {Turing, A. M.},
      TITLE = {Some calculations of the {R}iemann zeta-function},
      JOURNAL = {Proc. London Math. Soc.},
      FJOURNAL = {Proceedings of the London Mathematical Society. Third Series},
      VOLUME = {3},
      YEAR = {1953},
      PAGES = {99--117},
      ISSN = {0024-6115},
      MRCLASS = {65.0X},
      MRNUMBER = {0055785},
      MRREVIEWER = {D. H. Lehmer},
      DOI = {10.1112/plms/s3-3.1.99},
      ZBLNUMBER = {0050.08101},
      }

Authors

Ghaith Ayesh Hiary

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